Let’s start with a simple policy: I accept the first offer that exceeds some threshold \(q\) that remains fixed for the entire sales period. This threshold policy can be formulated in terms of the 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

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.

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.

1. What is the probability that I will obtain the best price?
2. What is the marginal value of increasing the number of house viewings by one?
3. Suppose each viewing costs \(c\in [0, 1]\), what is the optimal number of house viewings?

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 levels when we have \(1 \leq k \leq n\) 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 satisfies the recursion

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

The optimal policy can 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. I 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

and the stopping time \(\tau^*= \inf\{ i\leq n: Y_i = X_i\}\). Then,

1. the sequence \(\{Y_i\}\) is a super martingale, i.e., \(Y_i \geq \E{Y_{i+1} | \F_{i}}\) a.s.;
2. \(\E{Y_1} = \E{Y_{\tau^*}} = \E{X_{\tau^*}} = \sup_{\tau\in T} \E{Y_\tau}\), where \(T\) is the set of stopping times smaller or equal to \(n\);
3. 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,

since just before period \(n\), we have \(k=1\) buyers to go. From this, using independence,

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 theorem the stopping time \(\tau^*\) is optimal among all sellers (policies) that are willing to have \(n\) house visits.

A simple policy to select a house is like this: choose a level \(r>1\), reject the first \(r-1\) houses visited, then continue sampling and choose house \(k \geq r\) when house \(k\) 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 threshold \(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\),

So, let us follow the policy to reject the first \(r-1\) houses. Then,

The best house can be visited at any visit from \(r, r+1, \ldots, n\). Thus, using the above,

The best sampling level \(r\) maximizes \(P(r)\). Now, heuristically, \(P(r)\) must first increase as a function of \(r\), and then decrease. 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 \(P(r)\) starts to decrease.

Consequently, the best \(r\) is given by

Note that for \(n > 2\), the policy with \(r=1\) can be ruled out right away as not optimal.

We formalize the problem specification so that we can apply Snell’s envelope to prove that the sampling policy with threshold \eqref{orgfa898cb} just developed 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\); 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,

All permutation of the rankings are equally likely, implying that,

1. \(\P{\xi_i = 1} = 1/i\) for \(i=1, \ldots n\),
2. 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.

Hello from Nicky’s remark block.

Suppose we would stop according to stopping rule \(\tau\), the probability we have the best house is given by

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\}\),

With regard to the Snell envelope of \(X_n\), and using independence,

To see whether we can spot a pattern, consider next \(X_{n-1}\). By independence and the above,

since \(n-1 > 1\) (recall \(n\geq 2\) by assumption). Therefore,

Based on this, let’s guess that for \(i\) sufficiently large,

Then

If \(i\) is in fact so large that \(1 \geq \sum_{k=i+1}^{n} \frac{1}{k-1}\),

This validates, by induction, our earlier guess. However, if \(1 < \sum_{k=i+1}^{n} \frac{1}{k-1}\),

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.