Search And Stop Problem

1

Search and Stop Problem

Consider a game: At each period of the game, you draw a random offer x from a uniform distribution from 0 to 1. You can then choose either: A) Accept the payoff x immediately and end the game. B) Reject the payoff and draw again a period later (Repeat game). All draws are independent. Rejections are costly because the agent discounts the future at an exponential discount factor ρ = 0.01. At what value of x should you accept the offer? Solution 1. Write problem in Bellman form. v(xt ) | {z }

= max {xt ,

V alue f rom strategy choice of x

δEv(xt+1 ) | {z }

}

discounted f uture expected value

2. Realise that goal is to identify a threshold value x∗ . Thus, your optimal strategy v(x) would be to:  ACCEP T and get x if x ≥ x∗ v(x) = REJECT and get x∗ if x < x∗ 3. Solve: If you randomly draw the offer x∗ , you should be indifferent between stopping and continuing. v(x∗t ) = x∗

= δEv(xt+1 ) Z x=x∗ Z ∗ = δ x f (x)dx + δ

x=1

xf (x)dx

x=x∗

x=0



1

1 2 x 2 x∗ 1 1 = δx∗2 + δ − δ (x∗ )2 2 2 δ = (1 + x∗2 ) 2 x∗

= δ [x∗ x]0 + δ

Solve: x∗ =

√ δ 1 − 1 − δ2 (1 + x∗2 ) ⇒ x∗ = 2 δ

4. Since your discount factor ρ (i.e. cost of retrying) is 0.01 every period, Discount rate δ = exp(−ρ) = exp(−0.01) = 0.99 ⇒ x∗ = 0.87 Optimal strategy: Keep playing until you draw at least 0.87. Then you would accept and end the game. 1