Recursive Game Values

Hard5–6 hrsDynamic ProgrammingGame TheoryBellman EquationOptimal Play

Overview

Recursive game value problems are the hardest class of quant interview questions. They require you to find the VALUE of the game, not just describe a strategy. The Bellman equation is the key tool: the value of the game today equals the cost of playing today plus the expected value of playing optimally tomorrow. For threshold games (like The Picking Hat), the optimal threshold is found by differentiating the expected payoff with respect to the threshold and setting to zero. The self-consistency condition V = V(τ) where τ = argmax V(τ) lets you verify your answer.

How to Recognize

→'You play optimally — what is the expected value?'
→Game where you choose between stop/continue at each step
→Multi-stage games where future value depends on current state
→'The Picking Hat', dice-rolling games with stopping decisions
→Any problem asking for 'value of the game with optimal strategy'

Step-by-Step Approach

1.Define V(state) = expected value from this state under optimal play
2.Bellman equation: V(s) = max(stop payoff, E[V(next state)] - cost)
3.Work backwards from terminal states (boundary conditions)
4.For threshold problems: stop if current draw exceeds continuation value
5.The threshold = value of future opportunities (set equal, solve)

Key Formulas

V = -c + E[\max(X,\, V)] \quad

(stop if

X > V

;

c

= cost per draw)

V = \frac{E[X \mid X > \tau]\cdot P(X>\tau)}{1 - P(X \le \tau)} - c \cdot E[\text{draws}]

\tau^* = \arg\max_\tau \left[\tfrac{\tau+x_{\max}}{2} - \frac{c}{P(X \ge \tau)}\right]

V(\text{Picking Hat, 1--100}) = \tfrac{187}{2} - \tfrac{100}{14} = \tfrac{1209}{14} \approx \

86.36$

Worked Examples

0Quick Example

Picking Hat: threshold τ satisfies ∂V/∂τ=0 → τ ≈ 101−10√2 ≈ 87. Stop if draw ≥ 87. E[prize]=93.5, E[draws]=100/14≈7.1. Net value ≈ $86.36.

Problem

A hat contains numbers 1–100 (with replacement). Each round you draw a number, write it down, and pay $1. You may stop at any time; you receive the last number written. What is the optimal strategy and the fair value of this game?

Solution

Let τ = threshold: stop if current draw X ≥ τ.

P(stop each draw) = p = (101-τ)/100. Expected draws = 1/p = 100/(101-τ).

E[prize | stop] = mean of {τ, τ+1, ..., 100} = (τ+100)/2.

V(τ) = E[prize] − E[cost] = (τ+100)/2 − 100/(101−τ).

Optimize: dV/dτ = 1/2 − 100/(101−τ)² = 0 → (101−τ)² = 200 → τ* = 101 − 10√2 ≈ 86.86 → use τ=87.

V(87) = (87+100)/2 − 100/(101−87) = 187/2 − 100/14 = 93.5 − 50/7 = 1209/14 ≈ $86.36.

Answer

$V \approx \$ 86.36$. Optimal strategy: keep drawing until you draw ≥ 87. Expected number of draws ≈ 7.1. Verify self-consistency: V ≈ 86.36 < 87 = τ, confirming you should stop at exactly τ=87.

Common Mistakes

!
Using the WRONG continuation value as the threshold. The threshold should equal the continuation value (net of costs), not just E[next draw].
!
Not accounting for the per-round cost. If draws cost c each, the threshold is E[future game value], which is LOWER than E[prize] by the expected cost.
!
Assuming the threshold is the same as the expected value of the final prize. The threshold τ and the game value V are related by V(τ) — you need to optimize.
!
For finite-horizon games, forgetting to work backwards. With N=3 rolls the threshold is different from N→∞.

Practice Problems

Click "Show Answer" to reveal

A hat has numbers 1–10 (with replacement). Each draw costs $0.50. What is the optimal threshold and expected net value?

Hint: V(τ) = (τ+10)/2 − 0.5 × 10/(11−τ). Differentiate with respect to τ and set to zero.

You flip a fair coin repeatedly. You win $2ⁿ if the first head appears on flip n. But each flip costs$ 1. What is the expected net value? (Modified St. Petersburg)

Hint: E[prize] = Σ(1/2ⁿ)×2ⁿ = Σ1 = ∞ (classic St. Petersburg). With cost $1/flip: should you play? E[net] = E[prize] − E[flips]. E[flips] = 2 (geometric(1/2)). So E[net] = ∞ − 2 = ∞. But in practice, prizes are capped.

You have a single fair die. You can roll it at most 3 times, and you keep the result of your LAST roll (you must declare 'last' before rolling). What is the optimal strategy?

Hint: On roll 3 (must take it): E=3.5. On roll 2: stop if X > E[roll 3]=3.5, else declare roll 2 as last. On roll 1: compare to the value of having 2 rolls left.

Back to Study Plan

Gambler's Ruin Solving Recurrences Analytically