House Selling and Buying, Snell’s Envelope
1. Problem Setting
I have a house for sale and I am prepared to organize at most \(n\geq 1\) house viewings. Assume that offers are idd rvs \(\sim \Unif{[0,1]}\), and that I have to accept an offer on the spot or reject it. If rejected, the offer is retracted.1In other words, I cannot accept it at a later date. Under these rules, what policy maximizes the expected price I can receive for the house?
Once my house is sold, I want to buy a new house. As buying a new house is a multi-objective optimization problem, I don’t want to use just the price of the house to decide to buy it or not. In this case, I just assume I can rank the houses from best to worse.
The optimal policies for these two problems must be different. In the house selling case, all offers are capped by \(1\), and when the very first bid is already very close to \(1\), I know that that the probability of getting a better offer at a later date will be small. Hence, in such a case, I’ll accept the first offer. However, contrary to when selling a house, when buying a house I don’t have an absolute benchmark. The only knowledge I assume to have is that I can rank the houses from good to bad, more specifically, after visiting house \(j\), I can rank it with respect to the earlier houses.
Both these problems can be solved as an optimal stopping problem. So, let’s see how to do this, partly with Snell’s envelope. I include some python code to get numerical output.
2. Selling a House
When selling a house, at most \(n\) buyers will present their offers \(\{X_i\}_{i=1}^n\) , assumed to be iid rvs uniform on \([0,1]\), one after the other. Rejected offers are lost. What policy maximizes the probability to get the highest price? 2I used this site, where the same problem is discussed in terms of the Secretary Problem.
2.1. Best Price Under a Fixed Threshold Policy
Let’s start with a simple policy: fix a threshold \(q\), and accept the first offer that exceeds \(q\). This threshold policy can be formulated in terms of the following stopping time: \(\tau = \Inf{i : X_i \geq q}\), where \(\inf \varnothing = \infty\) so that \(\tau=\infty\) when all \(X_i < q\). The expected sales price becomes
\begin{equation} \label{org7925b9e} \E{X_{\tau}} = \sum_{i=1}^n \E{X_i\1{\tau = i}} + \E{X_n \1{\tau=\infty}}, \end{equation}because the event \(\{\tau = i \}\) implies that the offer \(X_i\) of buyer \(i\) exceeds \(q\), and when \(\tau=\infty\) the threshold \(q\) was too high so that I have to accept the offer \(X_n\) of the last buyer.
Why is \(\E{X_i \1{\tau=i}} = q^{i-1} \frac{1-q^{2}}{2}\) for \(i < n\)?
Solution
By independence, for \(i\leq n-1\),
\begin{align*} \E{X_i \1{\tau=i}} &= \E{X_i \1{X_i \geq q} \prod_{k=1}^{i-1} \1{X_k < q}} = q^{i-1} \E{X_i \1{X_i \geq q}} \\ &= q^{i-1} \int_q^1 x \d x = q^{i-1} \frac{1-q^{2}}{2}, \end{align*}Why is \(\E{X_n \1{\tau=\infty}}= \frac{q^{n+1}}2\) for \(n\)?
Solution
\begin{align*} \E{X_n \1{\tau=\infty}} &= \E{X_n \1{X_n < q} \prod_{k=1}^{n-1} \1{X_k < q}} = q^{n-1} \int_0^q x \d x = \frac{q^{n+1}}2. \end{align*}Conclude from \eqref{org7925b9e} that:
\begin{align*} v_{n}(q) := \E{X_{\tau}} &= \frac{1}{2}(1-q^{n} + q). \end{align*}Solution
\begin{align*} \E{X_{\tau}} &= \frac{1-q^{2}}{2} \sum_{i=0}^{n-1} q^{i} + \frac{q^{n+1}}2 = \frac{1+q}{2} (1-q^{n}) + \frac{q^{n+1}}2 \\ &= \frac{1}{2}(1-q^{n} + q) =: v_n(q). \end{align*}Show that for given \(n\) the optimal \(q\) is equal to:
\begin{align*} q = \left({\frac{1}{n}}\right)^{\frac{1}{n-1}}. \end{align*}Solution
Solve for \(q\) in \(\d v_n(q)/ \d q = -n q^{n-1} + 1 = 0\).
Here is an example in code to see how to implement all this.
def best_q(n):
return (1 / n) ** (1 / (n - 1))
def v(n, q):
res = 1 - q**n + q
return res / 2
n = 10
q = best_q(n)
value = v(n, q)
print(f"{q=}")
print(f"{v(n, q)=}")
q=0.7742636826811271 v(n, q)=0.8484186572065071
For the future I might consider some additional questions.
- What is the probability that I will obtain the best price?
- What is the marginal value of increasing the number of house viewings by one?
- Suppose each viewing costs \(c\in [0, 1]\), what is the optimal number of house viewings?
2.2. Best Price Under a Dynamic Threshold Policy
A fixed threshold policy cannot be optimal, because the less visits we have left, the lower the acceptance threshold should be. We next find the optimal level as a function of \(k\) when we have \(k\) visits to go.
Suppose we have rejected the first \(n-1\) offers, so that we have only \(k=1\) visits to go. Then our expected price is \(v_1 = \E{X_n} = 1/2\). In general we accept offer \(X_{i}\) of buyer \(i\) when this exceeds the expected price \(v_{k}\) of the remaining \(k=n-i\) visits. Otherwise, we reject this offer. In other words, the expected price for \(k\) periods to go should satisfy the recursion
\begin{align*} v_k &:= \E{\Max{X_{n-k}, v_{k-1}}} = \int_{v_{k-1}}^1 x \d x + \int_0^{v_{k-1}} v_{k-1} \d x = \frac{1}{2}(1-v_{k-1}^2) + v_{k-1}^2 \\ &= \frac{1}{2}(1 + v_{k-1}^2). \end{align*}Note that \(v_{k} > v_{k-1}\) when \(v_{k-1}\neq 1\) because \(1 + v_{k-1}^2 > 2 v_{k-1} \iff v_{k-1} \neq 1\). Thus, a policy with a fixed threshold is not optimal.
With caching/memoization the code is very simple.
from functools import cache
@cache
def v(k):
if k == 1:
return 1 / 2
return (1 + v(k - 1) ** 2) / 2
print(f"{v(10)=}")
v(10)=0.861098212205712
2.3. Snell’s Envelope
The optimal policy can also be found by using a more general, but more abstract, framework, namely by means of Snell’s envelope. Perhaps the easiest way to see how this works is to start with a theorem, stripped from some of its technical clutter. 3I copied it from `Promenade alétoire’ by M. Benaïm and N. El Karoui.
Consider a sequence of rvs \(\{X_i\}_{i=1}^n\) adapted to a filtration \(\{\F_{i}\}_{i=1}^{n}\). Introduce the sequence of rvs \(\{Y_i\}\) by backward recurrence as
\begin{align*} Y_i &= \Sup{\E{Y_{i+1}|\F_{i}}, X_{i}}, \quad i < n, & Y_n &= X_{n}, \end{align*}and the stopping time \(\tau^*= \Inf{ i\leq n: Y_i = X_i}\). Then,
- the sequence \(\{Y_i\}\) is a super martingale, i.e., \(Y_i \geq \E{Y_{i+1} | \F_{i}}\) a.s.;
- \(\E{Y_1} = \E{Y_{\tau^*}} = \E{X_{\tau^*}} = \SSup{\tau\in T}{\E{Y_\tau}}\), where \(T\) is the set of stopping times smaller or equal to \(n\);
- the stopping time \(\tau^{*}\) is optimal.
The rv \(Y_i\) is the Snell envelope of \(X_i\), which is defined as the smallest super martingale \(\geq X_i\).
Let’s apply this theorem to the house selling problem. Take \(\F_{i} = \sigma\{X_k : k \leq i\}\). Starting the recursion from right to left,
\begin{align*} \E{Y_{n}} &= \E{X_{n}} = v_{1}, \end{align*}since just before period \(n\), we have \(k=1\) buyers to go. From this, using independence,
\begin{align*} \E{Y_{n} |\F_{n-1}} &= \E{X_{n}|\F_{n-1}} = \E{X_{n}} = v_{1}, \\ Y_{n-1} &= \Max{\E{Y_{n} |\F_{n-1}}, X_{n-1}} = \Max{v_1, X_{n-1}}, \\ \E{Y_{n-1}|\F_{n-2}} &= \E{\Max{v_1, X_{n-1}}} = v_{2}, \end{align*}as just before buyer \(n-1\) makes an offer, we have \(2\) offers to go. Continuing like this we retrieve our earlier values \(v_k\). Morever, when \(Y_i = X_i\) for the first time \(i\), then \(X_i \leq v_{n-i}\), that is, \(X_i\) is the first offer that exceeds the expected price when continuing. But this is precisely the policy we found above. By the above theorem, the stopping time \(\tau^*\) is the optimal selling policy for sellers that are willing to have \(n\) house visits.
3. Buying a House
Now we move on to the second problem: given a set of houses that I can mutually compare (hence, can rank), find a policy that maximizes the probability to buy the best house.
To understand how to apply Snell’s envelope to the house selection problem, I used these two resources besides `Promenade aléatoire’ by M. Benaïm and N. El Karoui.
- Bodineau, Modélisation de phénomènes aléatoires
- Ferguson lecture notes. These notes provide a formal statement of the house selection problem and some interesting discussions on further work.
These accounts are clear, but leave quite a bit of work to the reader. The idea here is to also do this work.
We assume that \(n > 2\), because when \(n=1,2\) the problem is not interesting.
3.1. A heuristic procedure
A simple policy to select a house is like this: choose a sample size \(r, 1\leq r \leq n\). Reject the first \(r-1\) houses, then continue visiting and choose the first house \(k, k \geq r\), that is the best so far. Thus, the first \(r-1\) visits form a sampling set and the threshold is the best of the houses in this sampling set. The problem is to find the sample size \(r\) that maximizes the probability of selecting the best house of all \(n\) houses. As it turns out, this is the also the best policy overall. Before developing notation and using Snell’s envelope to prove the optimality, we discuss this policy in heuristic terms.
We approach the problem in steps. Suppose we would choose house \(k\) no matter what. Then, clearly, for any \(k\),
\begin{align*} \P{\text{House $k$ is best}} = \frac{1}{n}. \end{align*}Next, suppose we reject the first \(r-1\) houses, and then accept the first house that is the best so far. Under this policy,
\begin{align*} \P{\text{Select house $k$, given that house $k$ is best}} = \frac{r-1}{k-1}. \end{align*}Explain this result.
Solution
Under this policy, to select house \(k\) it is necessary that house \(k\) is better than all earlier houses, and that all houses \(r, r+1, \ldots, k-1\) are worse than the best house in \(1, 2, \ldots r-1\). In other words, for the policy to select house \(k\), the second best house of all \(k\) houses must lie in the set \(1, 2, \ldots, r-1\). Since all sequences of houses are equaly likely, the probability that this second best house occurs in the first \(r-1\) visits of the \(k-1\) visits before house \(k\), is \((r-1)/(k-1)\).
The best house can be visited at any visit from \(r, r+1, \ldots, n\). Thus, using the above,
\begin{align*} f(r)&:=\P{\text{Select the best house}} \\ &= \sum_{k=r}^{n} \P{\text{Select the best house, house $k$ is best}} \\ &= \sum_{k=r}^{n} \P{\text{Select the best house, given house $k$ is best}} \P{\text{House $k$ is best}} \\ &= \frac{r-1}{n}\sum_{k=r}^{n} \frac{1}{k-1}. \end{align*}The best sampling size \(r\) maximizes \(f(r)\). Now, heuristically, \(f(r)\) must first increase as a function of \(r\), and then decrease. To see this, note that when \(r\) is small, the threshold to accept a house is too low because we did not sample enough houses, while if \(r\) is large, it is likely that the best house will rejected because it will lie in the sampling set. So, we have to look for the \(r\) after which \(f(r)\) starts to decrease.
Show that \(f(r) \geq f(r+1) \iff 1 \geq \sum_{k=r}^n \frac{1}{k-1}\).
Solution
\begin{align*} f(r) \geq f(r+1) &\iff \frac{r-1}{n} \sum_{k=r}^n \frac{1}{k-1} \geq \frac{r}{n} \sum_{k=r+1}^n \frac{1}{k-1} \\ &\iff r\left( \sum_{k=r}^n \frac{1}{k-1} - \sum_{k=r+1}^n \frac{1}{k-1} \right) \geq \sum_{k=r}^n \frac{1}{k-1} \\ &\iff \frac{r}{r-1} \geq \frac{1}{r-1} + \sum_{k=r+1}^n \frac{1}{k-1}\\ &\iff 1 \geq \sum_{k=r+1}^n \frac{1}{k-1}. \end{align*}Consequently, the best \(r\) is given by
\begin{equation} \label{org194cf40} r^{*} = \Min{r > 1: f(r) > f(r+1) } = \Min{r>1 : \sum_{k=r}^n \frac{1}{k-1} \geq 1}. \end{equation}Note that for \(n > 2\), the policy with \(r=1\) can be ruled out right away as not optimal.
3.2. The formal procedure
We formalize the problem specification so that we can apply Snell’s envelope to prove that the sampling policy with sample size \(r^*\) of \eqref{org194cf40} is optimal.
If we have seen all houses, we can rank them so that \(R_i\) is the rank of the \(i\)th house visited; we say that house \(i\) is better than house \(j\) when \(R_i < R_j\). Thus, the best house overall has rank \(1\). The problem, once again, is to maximize the probability to find the best house.
Write \(\xi_i = 1\) if house \(i\) is the highest ranked so far and \(\xi_i=0\) otherwise, that is,
\begin{align*} \xi_i := \1{R_i < \Min{R_{1}, \ldots, R_{i-1}}}. \end{align*}All permutation of the rankings are equally likely, implying that,
- \(\P{\xi_i = 1} = 1/i\) for \(i=1, \ldots n\),
- The rvs \(\{\xi_i\}\) are independent.
Let \(\F_{i}\) be \(\sigma\{\xi_1, \ldots, \xi_i\}\), and \(\{\F_{i}\}_{i=0}^{n}\) the associated filtration.
Prove properties 1 and 2.
Solution
For 1, observe that \(\{\xi_i=1\}\) imposes the condition that of all permutations only the ones are allowed such that the best ranking of the first \(i\) visits appears at visit \(i\). By symmetry, the probability that visit \(i\) is the best of all \(i\) visits is equal to \(1/i\).
For 2, suppose that \(j>i\). By 1, the probability that \(\xi_j = 1\) is \(1/j\). Next, consider the subset of permutations such that \(\xi_j=1\). All of these permutations have the same probability. Thus, the probability that one of these permutations is such that \(\xi_i=1\) is \(1/i\). Therefore,
\begin{align*} \P{\xi_i=\xi_j=1} = \frac{1}{ij} = \frac{1}{i}\frac{1}{j}= \P{\xi_i=1}\P{\xi_j=1}. \end{align*}By recursion, this argument applies to any number of \(\xi_k\).
Here is a second proof for property 1, by means of an example. Suppose we do \(26\) visits, and rank the quality from \(a\) (lowest) to \(z\) (highest). The number of permutations of the 26 letters of the English alphabet such that the letter \(g\), i.e, the seventh letter, appears at the fourth position and is the best so far is \(6\cdot 5\cdot 4 \cdot (26-4)!\), because for the first position we can choose one letter from the set \(\{a, b, c, d, e, f\}\), for the second position we have 5 letters left, for the third position just 4 letters, and after the fourth position (occupied by the letter \(g\)) any permutation of the remaining \(26-4\) is allowed. For the case with the houses, the number of permutations such that of all \(n\) houses the seventh best house is at position \(4\), is equal to
\begin{align*} (n-4)! (7-1)(7-2)(7-3). \end{align*}More generally, the number of permutations such that best of four houses appears at the fourth place is
\begin{align*} (n-4)! \sum_{i=4}^n (i-1)(i-2)(i-3), \end{align*}with \(n=26\). The probability of the event \(\{\xi_4=1\}\) is therefore
\begin{align*} \P{\xi_4=1} \ &= \frac{(n-4)!}{n!} \sum_{i=4}^n (i-1)(i-2)(i-3) \\ &= \frac{3!(n-4)!}{n!}\, \sum_{i=3}^{n-1} \frac{i(i-1)(i-2)}{3!} \\ &= \frac{1}{4} \frac{1}{{n \choose 4}} \sum_{i=3}^{n-1} {i \choose 3}. \end{align*}With induction it is simple to prove that \(\sum_{i=3}^{n-1} {i \choose 3} = {n \choose 4}\). It is also evident that the number \(4\) places no special role, so property 1 follows.
Suppose we would stop according to stopping rule \(\tau\), the probability we have the best house is given by
\begin{align*} \E{\1{R_{\tau}=1}} = \P{R_{\tau} = 1} = \P{\xi_{\tau} = 1, \xi_{\tau+1} = \cdots = \xi_n = 0}. \end{align*}There is a fundamental problem with the event \(\{\xi_{i} = 1, \xi_{i+1} = \cdots = \xi_n = 0\}\) because this is not an element of \(\F_{i}\) since \(\xi_{j} \not \in \F_{i}\) for \(j> i\). Let us therefore look instead at the rvs that are adapted to \(\{F_i\}\):
\begin{align*} X_i &= \E{\1{R_i=1}|\F_{i}} \\ &= \P{\xi_{i} = 1, \xi_{i+1} = \cdots = \xi_n = 0|\F_i} \\ &=\xi_{i} \P{\xi_{i+1} = \cdots = \xi_n = 0|\F_i}, \\ &=\xi_{i} \frac{i}{i+1} \times \cdots \times \frac{n-1}{n} = \xi_i \frac{i}{n}. \end{align*}With regard to the Snell envelope of \(X_n\), and using independence,
\begin{align*} Y_n &= X_n = \xi_n \frac{n}{n}, & \E{Y_n | \F_{n-1}} &= \E{X_{n}} = \E{\xi_{n}} = \frac{1}{n}. \end{align*}To see whether we can spot a pattern, consider next \(X_{n-1}\). By independence and the above,
\begin{align*} Y_{n-1} &= \Max{X_{n-1}, \E{Y_{n}|\F_{n-1}}} \\ &= \Max{\xi_{n-1}\frac{n-1}{n}, \frac{1}{n}} = \frac{1}{n} + \frac{n-2}{n} \xi_{n-1}. \end{align*}since \(n-1 > 1\) (recall \(n\geq 2\) by assumption).
Explain this formula.
Solution
If \(\xi_{n-1}=1\), then \(\Max{(n-1)/n, 1/n} = (n-1)/n = 1/n + (n-2)/n\). If \(\xi_{n-1}=0\), then \(\Max{(n-1)/n\times 0, 1/n} = 1/n + (n-2)/n \times 0\).
Continuing with the argument,
\begin{align*} \E{Y_{n-1}|\F_{n-2}} &= \E{\frac{1}{n} + \frac{n-2}{n}\xi_{n-1}\given\F_{n-2}} \\ &= \frac{1}{n} + \frac{n-2}{n}\E{\xi_{n-1}} \\ &=\frac{n-2}{n}\frac{1}{n-2} + \frac{n-2}{n} \frac{1}{n-1} \\ &= \frac{n-2}{n} \sum_{k=n-1}^n \frac{1}{k-1}. \end{align*}Based on this, let’s guess that for \(i\) sufficiently large,
\begin{align*} \E{Y_{i+1}|\F_{i}} = \frac{i}{n} \sum_{k=i+1}^n \frac{1}{k-1}. \end{align*}Then
\begin{align*} Y_{i} &= \Max{X_{i}, \E{Y_{i+1}|\F_{i}}} = \Max{\xi_i \frac{i}{n}, \E{Y_{i+1}|\F_{i}}} \\ &= \frac{i}{n}\Max{\xi_i , \sum_{k=i+1}^n \frac{1}{k-1}}. \end{align*}If \(i\) is in fact so large that \(1 \geq \sum_{k=i+1}^{n} \frac{1}{k-1}\),
\begin{align*} \E{Y_{i}|F_{i-1}} &= \frac{i}{n}\left(\P{\xi_{i}=1} + \P{\xi_{i}=0}\sum_{k=i+1}^n \frac{1}{k-1}\right) \\ &= \frac{i}{n}\left(\frac{1}{i} + \frac{i-1}{i}\sum_{k=i+1}^n \frac{1}{k-1}\right) \\ &= \frac{i-1}{n} \sum_{k=i}^n \frac{1}{k-1}. \end{align*}This validates, by induction, our earlier guess. However, if \(1 < \sum_{k=i+1}^{n} \frac{1}{k-1}\),
\begin{align*} Y_{i} &= \frac{i}{n}\Max{\xi_i , \sum_{k=i+1}^n \frac{1}{k-1}} = \frac{i}{n}\sum_{k=i+1}^n \frac{1}{k-1}. \end{align*}Use Snell’s theorem to explain that the stopping time \eqref{org194cf40} is optimal.
Solution
Compute Snell’s envelope with the formulas above. It is evident for all \(i\) that \(\xi_i = 0 \implies 0 = X_{i} < Y_i\). Next, starting from \(i=1\), as long as \(i\) is such that \(1 < \sum_{k=i+1}^{n} \frac{1}{k-1}\), \(X_{i} < Y_i\) even when \(\xi_i = 1\). The earliest visit such that \(X_i = Y_i\) becomes possible is when \(\xi_i=1 > \sum_{k=i+1}^{n} \frac{1}{k-1}\). But this \(i\) is precisely the threshold given by \eqref{org194cf40}.
In conclusion, it is optimal to select house \(i\) when \(i\geq r^{*}\) and when \(\xi_{i} = 1\), i.e., when house \(i\) is the best house seen among the first \(i\) visits.