Optimal Sequential Search

You visit shops one by one, hunting for the best price.

Each extra shop costs you money. So you set one cutoff value in advance. An offer better than the cutoff, you buy at once. An offer worse than the cutoff, you keep looking. That cutoff is the reservation value in the formula below.

For example, you shop around for a 👕 shirt. Each extra shop costs 1,000 won in 🚌 bus fare. You decide in advance: under 50,000 won, I buy immediately. At 60,000 won you walk out. At 48,000 won you buy on the spot.

c=E[(X−r)+]=(M−r)22M,r∗=M−2Mcc = E[(X - r)^+] = \frac{(M - r)^2}{2M}, \qquad r^* = M - \sqrt{2Mc}
V(r)=M+r2−cMM−r,V(r∗)=r∗V(r) = \frac{M + r}{2} - \frac{cM}{M - r}, \qquad V(r^*) = r^*

Examples & Exercises

Let X∼Uniform[0,100]X \sim \text{Uniform}[0, 100] and search cost c=4c = 4.

Derive the reservation value r∗r^* from the indifference condition c=E[(X−r)+]c = E[(X - r)^+], and verify numerically the expected number of searches under the optimal policy and V(r∗)=r∗V(r^*) = r^*.

c=E[(X−r)+]=∫rMx−rM dx=(M−r)22Mc = E[(X - r)^+] = \int_r^M \frac{x - r}{M}\,dx = \frac{(M - r)^2}{2M}
r∗=M−2Mcr^* = M - \sqrt{2Mc}
c=4c = 4, M=100M = 100 — r∗≈71.72r^* \approx 71.72.
Show proof

  1. Holding an offer of rr, one more search has expected gain ∫r100(x−r)/100 dx=(100−r)2/200\int_r^{100} (x - r)/100\,dx = (100 - r)^2/200. Setting this equal to the cost c=4c = 4 gives (100−r)2=800(100 - r)^2 = 800, i.e. r∗=100−800≈71.72r^* = 100 - \sqrt{800} \approx 71.72.

  2. Each round stops with probability P(X≥r∗)=(100−r∗)/100≈0.2828P(X \ge r^*) = (100 - r^*)/100 \approx 0.2828, so the number of searches until stopping is geometric with mean 1/0.2828≈3.541/0.2828 \approx 3.54.

  3. V(r∗)=(100+r∗)/2−4⋅100/(100−r∗)≈85.86−14.14=71.72=r∗V(r^*) = (100 + r^*)/2 - 4 \cdot 100/(100 - r^*) \approx 85.86 - 14.14 = 71.72 = r^* — at the indifference point the value of searching exactly equals the offer in hand.

    V(r∗)=M+r∗2−cMM−r∗=r∗V(r^*) = \frac{M + r^*}{2} - \frac{cM}{M - r^*} = r^*

With X∼Uniform[0,100]X \sim \text{Uniform}[0, 100] and c=8c = 8, find r∗r^* and show that V(r∗)=r∗V(r^*) = r^* holds exactly in integer arithmetic.

r∗=100−2⋅100⋅8=100−40=60r^* = 100 - \sqrt{2 \cdot 100 \cdot 8} = 100 - 40 = 60
c=8c = 8, M=100M = 100 — r∗=60r^* = 60, expected searches 2.52.5.
Show proof

  1. Since 2Mc=1600=4022Mc = 1600 = 40^2, r∗=100−40=60r^* = 100 - 40 = 60. The stopping probability is 40/100=0.440/100 = 0.4, so the expected number of searches is 1/0.4=2.51/0.4 = 2.5.

  2. V(60)=(100+60)/2−8⋅100/40=80−20=60=r∗V(60) = (100 + 60)/2 - 8 \cdot 100/40 = 80 - 20 = 60 = r^* — exact, with no rounding error.

18. Economics of Information