4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Why not "draw until less than half the unknown cards" are "+1"? That is , draw until the expected return on the next card is negative. $\endgroup$ – Eric Towers Nov 24 '18 at 1:15
  • $\begingroup$ that's strategy 1: Draw until you get +1 and stop. $\endgroup$ – tiger88 Nov 24 '18 at 1:16
  • $\begingroup$ No. The sequence "-1, +1, +1, stop" satisfies my strategy, but is not "stop after the first +1". $\endgroup$ – Eric Towers Nov 24 '18 at 1:18
  • $\begingroup$ I'm sorry, i meant draw until you get a cumulative score of +1 $\endgroup$ – tiger88 Nov 24 '18 at 1:20
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you switched the order of the cards? (number of -1 cards, number of +1 cards) But this is an excellent answer thanks! $\endgroup$ – tiger88 Nov 24 '18 at 1:56
  • $\begingroup$ Thanks, fixed it $\endgroup$ – obscurans Nov 24 '18 at 1:57
  • $\begingroup$ is this trick just something youll find in a generic game theory book? $\endgroup$ – Tim kinsella Nov 24 '18 at 2:00
  • 2
    $\begingroup$ In game theory, this technique is known as backward induction. It will work for any finite game (no possibility of cycling back to the same game state), although the number of states could be immense (say chess with threefold repetition). $\endgroup$ – obscurans Nov 24 '18 at 2:04
  • $\begingroup$ From looking at your end states in the second diagram, what is the syntax to determine the optimal strategy? $\endgroup$ – tiger88 Nov 24 '18 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.