Krdytkyu

A deck contains 3 cards with +1 value and 3 cards with -1 value. The dealer shuffles the cards and deals them face up one by one. After each card is dealt, you have the option of stopping the game. Once the game is stopped, you get paid according to the total value of the cards that were dealt. E.g. if you stop the game after +1, +1, +1, you get +3. What is the expected value of the optimal strategy for this game.

My stab at it:

Since the net sum of the cards is zero, you will never lose any points on each round. If your trailing score is negative, you can keep drawing to get to at least flat.

Strategy: Draw until you get a cumulative score of +1 and stop.

Since there are a total of 20 permutations 6!/(3!*3!) of this game, only 5 sequences will give you a trailing score of 0 or below. So the expected value of this strategy: .75*1 + .25*0 = .75

Strategy 2: Draw two cards, if you have a cumulative score that is greater than 1, stop. Otherwise draw until you get a score of 1 and stop.

I was unable to figure out how to do the math for this strategy, but I did simulate it and apparently it has an expected value of .85. Can someone walk me through the math of the second strategy? If the second strategy is not the optimal one, what is a better strategy?

You can directly compute the optimal strategy and its expected value with a dynamic program (backward induction).

Consider the possible states of the game, which can be completely described by the (number of -1 cards remaining, number of +1 cards remaining), with 16 possibilities.

Arrange them in a square grid as follows (it might be better on paper if you make it a diamond with (3,3) on the left and (0,0) on the right)

$$begin{array}{ccccccc}
stackrel{(0)}{(3,3)} & rightarrow & stackrel{(1)}{(3,2)} & rightarrow & stackrel{(2)}{(3,1)} & rightarrow & stackrel{(3)}{(3,0)}\
downarrow && downarrow && downarrow && downarrow\
stackrel{(-1)}{(2,3)} & rightarrow & stackrel{(0)}{(2,2)} & rightarrow & stackrel{(1)}{(2,1)} & rightarrow & stackrel{(2)}{(2,0)}\
downarrow && downarrow && downarrow && downarrow\
stackrel{(-2)}{(1,3)} & rightarrow & stackrel{(-1)}{(1,2)} & rightarrow & stackrel{(0)}{(1,1)} & rightarrow & stackrel{(1)}{(1,0)}\
downarrow && downarrow && downarrow && downarrow\
stackrel{(-3)}{(0,3)} & rightarrow & stackrel{(-2)}{(0,2)} & rightarrow & stackrel{(-1)}{(0,1)} & rightarrow & stackrel{(0)}{(0,0)}\
end{array}
$$
The entries are on top (score if you stop here), bottom (#-1, #+1) remaining in the deck.

The trick is to work backwards from the (0,0) corner and decide at each state whether you want to continue or not. Examples:

• There is no decision at (0,0), it is worth 0.


• At (0,1) the choice is between taking -1, or drawing a card which gets 0. Since drawing is better, we now know (0,1) is also worth 0.


• At (1,0) we take 1 instead of drawing which gets 0.


• At (1,1) a real decision comes up. Stopping is worth 0. Drawing gets you 1/2 chance to move to (1,0) [worth 1] and 1/2 chance to move to (0,1) [worth 0]. So drawing is worth 1/2 on average, and it is optimal to do so.

You can continue filling in all the states to find the optimal strategy. Note that unequal card counts matter: at say (1,2), drawing gives you 1/3 chance to move to (0,2) and 2/3 chance to move to (1,1).

The filled in square looks like:
$$begin{array}{ccccccc}
stackrel{17/20}{(3,3)} & rightarrow & stackrel{6/5}{(3,2)} & rightarrow & stackrel{mathbf{2}}{(3,1)} & & stackrel{mathbf{3}}{(3,0)}\
downarrow && downarrow && &&\
stackrel{1/2}{(2,3)} & rightarrow & stackrel{2/3}{(2,2)} & rightarrow & stackrel{mathbf{1}}{(2,1)} & rightarrow^{?} & stackrel{mathbf{2}}{(2,0)}\
downarrow && downarrow && downarrow^{?} &&\
stackrel{1/4}{(1,3)} & rightarrow & stackrel{1/3}{(1,2)} & rightarrow & stackrel{1/2}{(1,1)} & rightarrow & stackrel{mathbf{1}}{(1,0)}\
downarrow && downarrow && downarrow &&\
stackrel{0}{(0,3)} & rightarrow & stackrel{0}{(0,2)} & rightarrow & stackrel{0}{(0,1)} & rightarrow & stackrel{mathbf{0}}{(0,0)}\
end{array}$$

States where you stop have their value bolded. At (2,1) it doesn't matter if you draw or stop.

Since you have made value-maximizing choices at every step including the effects of later choices, Strategy 2 is proven optimal, with value exactly 17/20.