Dynamic Programming for Optimal Stopping in a Card Game
Summary
This discussion presents a finite-horizon optimal stopping problem using a shuffled deck with equal numbers of red and black cards. A red card adds to the player’s payoff and a black card subtracts from it. The state is represented by the counts of each color remaining; at any state the player compares stopping for the current payoff with continuing, using the probabilities of drawing each color next. This yields a dynamic programming recurrence for the best expected payoff.
The answers clarify why a boundary value can be zero when no black cards remain: if only red cards remain, the player can continue until the payoff reaches zero rather than stopping at a loss. If only black cards remain, stopping preserves the current positive payoff. A spreadsheet calculation reports an initial optimal expected payoff of 2.498 dollars for the described deck. The method assumes the player can observe each card and choose when to stop, and the response gives no independent proof of the numerical result or detailed optimal stopping policy.
Key ideas
- Represent the game state by the remaining counts of black and red cards.
- At each state, compare the payoff from stopping with the probability-weighted value of continuing.
- Dynamic programming computes the optimal expected payoff recursively from terminal states.
- When only red cards remain, continuing can bring a negative payoff back to zero.
- The cited spreadsheet result gives an expected optimal payoff of 2.498 dollars for the initial deck.
Tags
Full text
# Dynamic Programming: Dynamic Card Game
# Dynamic Programming: Dynamic Card Game
I'm reading an interview book called A Practical Guide to Quantitative Finance Interview and I have some doubts about the solution provided by the book, so I really appreciate your advice if my doubt is correct or not.
Question description (from Chap 5 Stochastic Process and Stochastic Calculus/5.3 Dynamic Programming/Dynamic Card Game):
A casino offers a card game with the standard 52 cards (26 red, 26 black). The cards are thoroughly shuffled and the dealer draws cards one by one. (Drawn cards are not returned to the deck). You can ask the dealer to stop at any time you like. For each red card drawn, you win 1 dollar; for each black card drawn, you lose 1 dollar. What is the optimal stopping rule in terms of maximizing expected payoff and how much are you willing to pay for this game?
Solution: Let $(b,r)$ represent the number of back and red cards left in the deck, respectively. By symmetry, we have:
$RedCardsDrawn-Black Cards Drawn = Black Cards Left - Red Cards Left$
At each $(b,r)$, we face the decision whether to stop or keep on playing. If we ask the dealer to stop at $(b,r)$, the payoff is $b-r$. If we keep on playing, there is $b/(b+r)$ probability that the next card will be black-in which case the state change to $(b-1,r)$-and $r/(b+r)$ probability that the next card will be red-in which case the state changes to $(b,r-1)$. We stop if and only if the expected payoff of drawing more cards is less than $b-r$. That also gives us the system equation:
$E[f(b,r)]= max(b-r,(b/(b+r))*E[f(b-1,r)]+(r/(b+r))*E[f(b,r-1)])$
Using the boundary condition:
$f(0,r)=0$
My doubt: I think the above boundary condition should be $f(0,r)=-r$ instead because:$RedCardsDrawn-Black Cards Drawn = Black Cards Left - Red Cards Left = 0-r$ I'm wondering if my understanding is correct?
## Answer by Attack68 (score 1, accepted)
https://quant.stackexchange.com/a/50203
I did this in excel with the boundary conditions:
$$f(0,r)=0 \quad f(b,0)=b$$
And
$$f(x,y) = \max \left (x-y,\; \frac{x}{x+y}f(x-1,y) + \frac{y}{x+y}(x,y-1) \right)$$
The answer I got was $f(26,26) = 2.498$
## Answer by novembermirrors (score 0)
https://quant.stackexchange.com/a/78583
The game assumes that the player always plays optimally. In this regard, if you are at a point of $f(0,r)$ your payoff would end up at 0 since you are currently at some negative payoff and you will ask the dealer to deal all the remaining red cards to get you to 0.
The key here is to see that you will always do what is optimal for you which is what $f(b,r)$ represents. In the same vein, the other boundary condition is:
$f(b,0) = b$
Why? Because if I come to a point where I only have black cards remaining to be dealt, I will ask the dealer to stop dealing and my payoff is whatever I am at right now.Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.