Half of What a Prophet Gets

A House, Ten Buyers and No Second Chances

You are selling a house. The buyers come one at a time, and each makes an offer and wants an answer before walking out of the door. Say no and that buyer is gone for good; say yes and the ones still to come never get a word in. You know roughly how offers run on your street, around $500,000, most of them within a tenth either way. What you do not know is what the next buyer will say.

Probabilists have names for the two people in this story. The prophet sees every offer in advance and takes the best. The gambler, you, must decide each one on the spot. The prophet never does worse. The surprise is how little the gambler needs to know to stay within reach.

Set one bar: the price that the best of all the offers has an even chance of reaching. Take the first offer at or above it. Whatever the offers are, all alike or wildly different, you will get on average at least half of what the prophet gets. And no rule, however clever, can promise more than half.

With ten buyers around $500,000, the prophet’s best offer averages $584,200. The best rule there is, worked out backwards from the last buyer, gets $569,500. The one-bar rule asks for $580,800. If the seller takes the last offer when nobody reaches the bar, it gets $551,200; if the seller walks away instead, as the theorem has it, it gets $303,700, barely more than half. Both numbers matter, and the second one is not a mistake.

One Number

Write the offers as $X_1, \dots, X_n$: independent, never negative, each with a law $F_i$ you know, arriving in an order you know. The bar $\tau$ is the median of the best offer, and $T$ is the first buyer who reaches it; if nobody does, you get nothing:

$$\begin{gathered} F_1(\tau)\,F_2(\tau)\cdots F_n(\tau) = \tfrac12, \qquad T = \min\{\, i : X_i \ge \tau \,\} \\[6pt] \mathbb{E}\big[X_T\big] \;\ge\; \tfrac12\,\mathbb{E}\Big[\max_{i} X_i\Big] \end{gathered}$$

$(1)$

The constant came first. In 1977 Ulrich Krengel and Louis Sucheston proved that, for independent offers, the prophet’s average is at most a fixed multiple of what the gambler can secure. They had shown only that the multiple lies between 2 and 4; that it can be taken equal to 2, they wrote, is due to D. Garling. They also showed that 2 cannot be improved. In 1984 Ester Samuel-Cahn, a statistician at the Hebrew University of Jerusalem, showed that the gambler needs no strategy at all to get there: one fixed bar is enough, and the median of the best offer is such a bar. Robert Kleinberg and S. Matthew Weinberg later gave a proof that works just as well with a second bar, half the prophet’s average, $\tau = \tfrac12\,\mathbb{E}[\max_i X_i]$.

Three Lines

The proof fits on a napkin. Write $(x)^+$ for $\max(x, 0)$ and let $p$ be the chance that some offer clears the bar. Whenever you stop, you collect the bar, plus the amount by which your offer beats it. Offer $i$ is still open to you whenever no earlier offer cleared the bar, which happens with chance at least $1-p$. The prophet, for his part, can never do better than the bar plus the amount by which the best offer beats it, and that is no more than all the offers’ excesses added up:

$$\begin{gathered} \mathbb{E}[X_T] \;\ge\; p\,\tau + (1-p)\sum_{i=1}^{n} \mathbb{E}\big[(X_i – \tau)^+\big] \\[6pt] \mathbb{E}\Big[\max_i X_i\Big] \;\le\; \tau + \mathbb{E}\Big[\big(\max_i X_i – \tau\big)^+\Big] \;\le\; \tau + \sum_{i=1}^{n}\mathbb{E}\big[(X_i – \tau)^+\big] \\[6pt] p = \tfrac12 \;\;\Longrightarrow\;\; \mathbb{E}[X_T] \;\ge\; \tfrac12\,\mathbb{E}\Big[\max_i X_i\Big] \end{gathered}$$

$(2)$

The median is the bar that makes the two weights equal: half the time you are paid the bar, and half the time you are still waiting, with every offer’s excess still in play. For ten offers drawn from an exponential law with mean 1, the three lines read in numbers: the bar is 2.70, the excesses add up to 0.67, the first line promises the gambler at least 1.69, the second caps the prophet at 3.37, exactly twice as much. The gambler actually gets 1.85, and the prophet 2.93.

Nothing Promises More

Two offers. The first is worth 1 for certain. The second is worth $1/\varepsilon$ with a small chance $\varepsilon$, and nothing otherwise.

$$\begin{gathered} \text{prophet} \;=\; (1-\varepsilon)\cdot 1 + \varepsilon\cdot\frac{1}{\varepsilon} \;=\; 2 – \varepsilon \\[6pt] \text{every rule} \;=\; 1, \qquad \frac{\text{gambler}}{\text{prophet}} \;=\; \frac{1}{2-\varepsilon} \;\longrightarrow\; \tfrac12 \end{gathered}$$

$(3)$

Take the first offer and you have 1. Refuse it and you hold a lottery ticket worth $\varepsilon \cdot 1/\varepsilon = 1$ on average. Every rule there is, including the best one, found by working backwards from the last offer, gets exactly 1, while the prophet, who knows when the ticket wins, gets $2 – \varepsilon$. At $\varepsilon = 0.001$ the gambler’s share is 0.5003. Here one fixed number is as good as the cleverest strategy, and both are held to a half.

The worst case: a sure offer of 1, then an offer of 1/ε with chance ε. Left: the prophet's average, 2 − ε, and the gambler's, 1 under every rule. The circles are computed by the same formulas as the rest of the post (backward induction and the prophet's integral); the lines are the closed forms.… — **Figure 1.** The worst case: a sure offer of 1, then an offer of 1/ε with chance ε. Left: the prophet’s average, 2 − ε, and the gambler’s, 1 under every rule. The circles are computed by the same formulas as the rest of the post (backward induction and the prophet’s integral); the lines are the closed forms. Right: the gambler’s share, 1/(2 − ε), falls to one half as the jackpot grows rarer.

Ten Offers, Four Markets

A guarantee describes the worst day. To see ordinary ones, I took ten offers from each of four laws, the same law for every buyer: the house, a lognormal law with a typical spread of 10% around $500,000; an exponential law; a lognormal law with $\sigma = 1$; and a Pareto law with tail index 1.5, heavy enough that its variance is infinite.

For each I computed the rules exactly, with no simulation in the numbers: the prophet’s average as an integral, the best rule by backward induction (with one offer left you must take it; with more left you take an offer only if it beats what waiting is worth), and the two bars of the theorem in two versions each. Strict walks away with nothing if no offer clears the bar; it is the rule the theorem is about. Forced takes the last offer whatever it is, which is what a seller does. Every exact share then agreed with a million simulated streams of ten offers, within three standard errors.

Algorithm — One Bar for Offers That Come One at a Time

input:  the laws F₁, …, Fₙ of the offers, in the order they come

τ ← the price with F₁(τ) · F₂(τ) ⋯ Fₙ(τ) = ½, by bisection
        # the best of the n offers clears τ with chance one half
for i = 1, …, n:
    if offer i ≥ τ:  take it and stop
    else:            refuse it; that buyer is gone
if no offer cleared τ:
    strict:  walk away with nothing      # the rule the theorem covers
    forced:  take the last offer         # what a seller does
guarantee (strict or forced):  E[what you take] ≥ ½ · E[best offer]

what it is worth, for n offers with one law F and q = F(τ):
    strict  ← E[X; X ≥ τ] · (1 + q + … + q^(n−1))
    forced  ← E[X; X ≥ τ] · (1 + q + … + q^(n−2)) + q^(n−1) · E[X]
    prophet ← ∫₀^∞ (1 − F(x)ⁿ) dx

Move the bar and watch what it is worth. With ten exponential offers, a bar at zero takes the first offer, worth 1 on average. A very high bar, strict, almost always walks away with nothing, and forced, almost always ends with the last offer. In between it peaks: the best single bar, forced, sits at 1.97 and gets 0.84 of the prophet, not far below the best rule’s 0.863. The two bars of the theorem sit on either side of that peak, the half-mean bar at 1.46 and the median bar at 2.70. Neither is the best bar, and both are well above the floor.

Ten exponential offers with mean 1: what the seller gets on average against the bar τ, strict (coral: walk away if no offer clears the bar) and forced (amber: take the last offer). The prophet gets 2.93 and the best rule 2.53; the dashed line is the guaranteed half, 1.46. The blue lines are the two… — **Figure 2.** Ten exponential offers with mean 1: what the seller gets on average against the bar τ, strict (coral: walk away if no offer clears the bar) and forced (amber: take the last offer). The prophet gets 2.93 and the best rule 2.53; the dashed line is the guaranteed half, 1.46. The blue lines are the two bars of the theorem: half the prophet’s average, 1.46, and the median of the best offer, 2.70.

Across the four markets the best rule gets between 82.1% and 97.5% of the prophet, and the forced median bar between 77.0% and 94.3%. The half-mean bar is the cheap one. On the house it is $292,100, so far below the usual offers that it almost always takes the first buyer, and that is worth 86.0% of the prophet.

Ten offers from each of four laws, every rule as a share of the prophet's average, computed exactly. The dashed white line is the floor of one half, which holds for any independent offers. The dotted blue lines are the higher floors for identical offers: 1 − 1/e for the bar each offer clears with… — **Figure 3.** Ten offers from each of four laws, every rule as a share of the prophet’s average, computed exactly. The dashed white line is the floor of one half, which holds for any independent offers. The dotted blue lines are the higher floors for identical offers: 1 − 1/e for the bar each offer clears with chance 1/10, and 0.745 for the best rule. The exponential’s 0.632 under the strict median bar lands on the 1 − 1/e line by coincidence: that floor belongs to a different bar.

The Tamest Market Comes Closest to Half

Read the strict bars in figure 3 from left to right and something looks backwards. The theorem’s own rule does best on the wildest market, 72.3% of the prophet for the Pareto offers, and worst on the tamest, 52.0% on the house, within a whisker of its floor.

The house explains it. Its bar is $580,800, and by construction half the time no buyer reaches it; then the strict seller walks away with nothing. When a buyer does reach it, the seller gets $607,400 on average, hardly more than the prophet’s $584,200, because the offers are so close together that clearing the bar is worth little more than the bar itself. Half of a little more than the prophet is a little more than half. The worst case of the last section is held to a half for another reason, a single offer that can dwarf all the rest; the narrow house gets there with offers that barely differ.

So the theorem is a floor, not a recipe. When offers sit close together, a seller who takes the last offer comes near the prophet: the best rule gets 97.5% on the house and the forced median bar 94.3%. The best rule asks $566,600 of the first buyer and lowers its price as buyers run out, down to $502,500, the average offer, for the ninth. The one rule that comes close to the floor is the one that refuses to take the last offer.

**Figure 4.** The number of offers, from 2 to 100 (log scale). Left: exponential offers; right: the house. The best rule (teal) stays high; the median bar loses ground as offers multiply, slowly when the last offer is taken (amber) and towards one half when the seller walks away (coral).

More buyers make it worse for the median bar, not better. With exponential offers the strict bar’s share falls from 0.743 with two offers to 0.632 with ten and 0.576 with a hundred; on the house it hugs the floor all the way, 0.530 with two and 0.514 with a hundred. The forced bar falls too, from 0.906 to 0.669 for the exponential and from 0.980 to 0.904 on the house. The best rule holds its ground: 0.912, 0.863 and 0.895 for the exponential at two, ten and a hundred offers, and 0.984, 0.975 and 0.979 on the house.

When Every Buyer Looks Alike

All four markets above have identical offers, and for identical offers the floor is higher. A bound of $1 – 1/e \approx 0.632$ goes back to Hill and Kertz in 1982, and a single bar earns it: the bar each offer clears with chance $1/n$, so that on average exactly one of the $n$ offers clears it. That is a lower bar than the median, and a different rule. The strict median bar got 0.520 on the house, far under $1-1/e$, while the $1/n$ bar, strict, gets between 0.665 and 0.743 on the four markets here.

The best rule does better still. Hill and Kertz described the worst identical offers in 1982, and Kertz showed in 1986 that they hold the best rule to about 0.745 of the prophet. In 2017 José Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk and Tjark Vredeveld showed that 0.745 can always be reached, with a bar that falls from one buyer to the next.

They were not thinking about houses. Their paper is about posted prices: a seller with one item, customers arriving one at a time, each offered a price to take or leave. That link was drawn in 2007 by MohammadTaghi Hajiaghayi, Robert Kleinberg and Tuomas Sandholm, who pointed out that Samuel-Cahn’s rule is already a posted price: sell to the first bidder whose bid reaches the bar. A price that never moves has a property auction designers prize, since no buyer gains by lying about when he arrived or when he will leave. Among their examples were online ticket sales and the sale of a house.

What One Number Is Worth

Half sounds like little. It is the most anyone can promise without knowing more about the offers, and one number buys it, a number you can work out before the first buyer rings the bell. On every market in this post the same number did far better than its promise as soon as the seller allowed the obvious amendment, taking the last offer rather than walking away: 94.3% of the prophet on the house, between 77.0% and 79.9% on the other three. The best rule does better again, but it is a list of prices, one for each buyer, and when the offers can be anything at all, no list of prices, however clever, guarantees more than the one bar does.

If you are ever the seller: decide your price before the first buyer arrives, the price the best of them has an even chance of offering, and do not turn away the last one.

Sources

U. Krengel and L. Sucheston, “Semiamarts and finite values”, Bulletin of the American Mathematical Society 83 (1977) 745–747.
J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk and T. Vredeveld, “Recent developments in prophet inequalities”, ACM SIGecom Exchanges 17 (2018) 61–70.
E. Samuel-Cahn, “Comparison of threshold stop rules and maximum for independent nonnegative random variables”, The Annals of Probability 12 (1984) 1213–1216.
Ester Samuel-Cahn at the Hebrew University of Jerusalem: her biography, “Ester Samuel-Cahn”, Wikipedia.
R. Kleinberg and S. M. Weinberg, “Matroid prophet inequalities”, Proceedings of the 44th Annual ACM Symposium on Theory of Computing (2012) 123–136; journal version, “Matroid prophet inequalities and applications to multi-dimensional mechanism design”, Games and Economic Behavior 113 (2019) 97–115.
T. P. Hill and R. P. Kertz, “Comparisons of stop rule and supremum expectations of i.i.d. random variables”, The Annals of Probability 10 (1982) 336–345.
R. P. Kertz, “Stop rule and supremum expectations of i.i.d. random variables: a complete comparison by conjugate duality”, Journal of Multivariate Analysis 19 (1986) 88–112.
J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk and T. Vredeveld, “Posted price mechanisms for a random stream of customers”, Proceedings of the 2017 ACM Conference on Economics and Computation (2017) 169–186; journal version, “Posted price mechanisms and optimal threshold strategies for random arrivals”, Mathematics of Operations Research 46 (2021) 1452–1478.
M. T. Hajiaghayi, R. Kleinberg and T. Sandholm, “Automated online mechanism design and prophet inequalities”, Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence (2007) 58–65.

Every number in the text and the charts is computed exactly by the script archived with this post, from results saved once, and checked against a million simulated streams of offers for each law.

Interested in applying these ideas to your work? Get in touch.

Also on

YouTubeWhen Should You Accept an Offer? The Prophet Inequality in Plain WordsThis essay in plain words, in a few minutes.Watch on YouTube →FacebookThe walkthrough on our Facebook PageThe short film, with its comments.Discuss on Facebook →