You sit down with a well mixed deck containing A cards marked "+" and B cards marked "—". You may draw cards from this deck as long as you want, i.e., you can stop playing at any point. Each time you draw a + card you are given $1 and each time you draw a — card you have to pay $1. Cards are not replaced after having been drawn.

What would be a fair amount to pay for the right to play (i.e., what is the expected payoff) and under what circumstance should a player cease drawing?

(In reply to Winning Strategy by ed bottemiller)

Forget the entry fee; it's just a way of asking what the expected value of the game is.

If at some point in the game, there are A +s left, and B -s, the decision on whether to draw again only depends on A and B, and not on how the game has progressed so far. To decide whether to keep playing at (A,B), we simply compare the expected value of stopping, which is 0, to the expected value of continuing, which depends on the values of smaller games. Given the expected values of all smaller games, we compute the winning strategy at A,B, and use this to compute the expected value of the game A,B. That is, we compute the expected value and the winning strategy simultaneously; they are inextricably linked.

I don't know of any way to simply divine the winning strategy without also computing the expected value. There is no particular reason to believe we should always stop when A<B. The simplest counterexample is (A,B)=(2,3). If the optimal strategy were to stop playing at (2,3), its expected value would be 0. But we can compute the expected value as 1/5. It is this fact alone that tells us we should keep playing at (2,3).

Let W(A,B) be the expected value of the game starting with A,B. Suppose W(a,b) has been computed for all a,b with a+b < A+B. We have two choices: play or stop. If we play, the expected value is F(A,B) = A/(A+B)(1+W(A-1,B)) + B/(A+B)(-1+W(A,B-1)). If we stop, the expected value is 0. Whichever of these two numbers is greater determines our strategy.

The erroneous solution posted assumes that W(A,B) = F(A,B). This is not the case. If F(A,B) < 0, then it makes no sense to continue, so we stop, and W(A,B)=0. Only if F(A,B)>0 do we continue, and in this case W(A,B) = F(A,B).

If we have computed W(a,b) for all a,b with a+b < A+B, then we simply compute F(A,B), the sign of which determines whether to continue playing or not. We then set W(A,B) = Max(0, F(A,B)).

One can compute these numbers explicitly given this recurrence. If we do that, we find:

When A=1, play iff B <= 1. When A=2 or 3, play iff B <= A+1. When A=4,5,6 or 7, play iff B <= A+2.

Try a few games if you don't believe it. You will find that this strategy outperforms any other.

Posted by Eigenray on 2008-03-13 20:57:28