Optimal Strategy for a Three-Card Game

Worked Solution

How to Think About It: This is a classic optimal stopping problem with three options. The trick is that you don't know $n$, so you can't evaluate a single card in isolation, so you can only compare cards you've seen. This is a miniature version of the secretary problem. Your first card is pure information: it tells you where you likely sit in the distribution. The optimal strategy must be a threshold rule based on relative ranking, not absolute value.

Quick Estimate: There are $3! = 6$ equally likely orderings. If you always take the first card, your expected payoff is $n + 1$ (the average). If you always skip to the second, and then use comparison logic, you should do better. The best strategy should yield something above $n + 1$. A quick enumeration suggests around $n + 5/3 \approx n + 1.67$.

Approach: Enumerate all 6 orderings and determine the optimal decision at each stage using backward induction.

Formal Solution:

Label the card values as $L = n$ (low), $M = n+1$ (middle), $H = n+2$ (high). There are 6 equally likely orderings of the three positions.

Second-card decision (if you discarded the first): You've seen the first card's value $v_1$ and now see $v_2$. If you discard $v_2$, you get $v_3$ (the remaining card). Since you know two values, you can infer the third:

• If $v_2 > v_1$: staying gives $v_2$, and the remaining card could be higher or lower. But since $v_2 > v_1$, taking $v_2$ is good because the remaining card is equally likely to be above or below. The precise rule: stay if $v_2 > v_1$ (you've improved), discard if $v_2 < v_1$ (you've gotten worse, gamble on the last card).

Actually, let's be more precise. If you see $v_2$ at stage 2, the third card is the remaining value. You should stay with $v_2$ if $v_2 \geq v_3$, i.e., if $v_2$ is not the smallest remaining value. But you don't know $v_3$. However, you know $v_1$ and $v_2$, and the three values are consecutive. So:

• If $v_2 > v_1$: the remaining card $v_3$ satisfies $v_3 < v_2$ (since $v_2$ is at least the middle value). Stay.
• If $v_2 < v_1$: the remaining card might be larger. Discard.

To make this precise, we enumerate all cases below.

First-card decision: The key question is whether to stay with $v_1$. If you move on, you play the second-card game optimally. We need to compare $v_1$ to the expected payoff from continuing.

Optimal second-stage strategy (given you skipped $v_1$): Stay with $v_2$ if $v_2 > v_1$; otherwise take $v_3$.

Let's enumerate all 6 orderings and compute the payoff under the strategy "skip the first card, then stay with the second if it's better than the first, otherwise take the third":

| Order $(v_1, v_2, v_3)$ | Skip $v_1$, compare $v_2$ vs $v_1$ | Payoff | |---|---|---| | $(L, M, H)$ | $M > L$, stay with $M$ | $M = n+1$ | | $(L, H, M)$ | $H > L$, stay with $H$ | $H = n+2$ | | $(M, L, H)$ | $L < M$, take $v_3 = H$ | $H = n+2$ | | $(M, H, L)$ | $H > M$, stay with $H$ | $H = n+2$ | | $(H, L, M)$ | $L < H$, take $v_3 = M$ | $M = n+1$ | | $(H, M, L)$ | $M < H$, take $v_3 = L$ | $L = n$ |

Expected payoff from always skipping the first card: $$E = \frac{1}{6}[(n+1) + (n+2) + (n+2) + (n+2) + (n+1) + n] = \frac{6n + 8}{6} = n + \frac{4}{3}$$

That's worse than $n + 1.67$, so always skipping is not optimal. We need a first-card threshold.

Optimal first-card strategy: Stay with $v_1$ if $v_1 = H = n+2$. But you don't know $n$, so you can't identify $H$ directly.

The resolution: since you don't know $n$, you cannot use an absolute threshold. However, you can adopt the following strategy:

• Always skip the first card (use it as a reference value).
• Stay with the second card if $v_2 > v_1$, otherwise take the third card.

This gives $E = n + 4/3$ as computed above.

But we can do better with a modified approach. Consider: "Stay with the first card if it equals $n+2$." Since you don't know $n$, you can't implement this directly. The problem, however, says the values are $n, n+1, n+2$, so they are consecutive integers. Once you see the first card, you know that the other two are within 1 or 2 of it.

Refined strategy: After seeing $v_1$, the remaining values are exactly the two values from $\{n, n+1, n+2\} \setminus \{v_1\}$. You don't know $n$, but consider the conditional expected payoff from continuing:

• If $v_1 = H = n+2$: remaining are $\{n, n+1\}$. Best continuation: $\max(v_2, v_3)$ from the second-stage strategy. On average this gives $(n + n+1)/2 + $ something. Actually: if remaining are $\{L, M\}$ in random order, and you use "stay if $v_2 > v_1$", then $v_2$ is either $L$ or $M$, both less than $v_1 = H$, so you always take $v_3$, giving expected $(L + M)/2 = n + 1/2$. You should have stayed with $H = n+2$.

• If $v_1 = L = n$: remaining are $\{n+1, n+2\}$. Continue: stay with $v_2$ if $v_2 > n$, which is always true. Get expected $(n+1 + n+2)/2 = n + 3/2$. Better than staying with $n$.

• If $v_1 = M = n+1$: remaining are $\{n, n+2\}$. Continue: if $v_2 = n+2 > v_1$, stay with $n+2$. If $v_2 = n < v_1 = n+1$, discard $v_2$ and take $v_3 = n+2$. Either way you get $n+2$. Expected: $n + 2$. This is better than staying with $n + 1$.

So the optimal strategy is:

• If $v_1$ is the max ($H$): you should stay. Expected payoff: $n+2$.
• If $v_1$ is the middle ($M$): you should skip (continuing gives $n+2$ for certain!).
• If $v_1$ is the min ($L$): you should skip (continuing gives $n + 3/2$).

But you don't know which case you're in! The problem is that without knowing $n$, the value $v_1$ alone doesn't tell you your rank. Any integer could be $L$, $M$, or $H$.

The honest answer: Without knowing $n$ (or any prior on $n$), no strategy can identify whether the first card is the max, middle, or min. The best you can do is the "always skip the first card" strategy with the comparison rule, yielding:

$$E = n + \frac{4}{3}$$

If you DO know $n$ (or equivalently, know the set of values), the optimal strategy is: stay with the first card only if it's the maximum value $n+2$; otherwise skip and use the comparison strategy on the second card. This yields:

$$E = \frac{1}{3}(n+2) + \frac{1}{3}(n+2) + \frac{1}{3}\left(n + \frac{3}{2}\right) = n + \frac{2 + 2 + 3/2}{3} = n + \frac{11}{6}$$

Answer: If you know $n$: stay on the first card only if it equals $n+2$; otherwise skip and stay on the second card if it improves on the first, else take the third. Expected payoff: $n + 11/6$. If you do not know $n$: always skip the first card and use it as a benchmark for comparison. Expected payoff: $n + 4/3$.