Problem 60 Solution

Regardless of the reasonable point at which player 2 will switch with the deck player 1 will maximize his expected outcome by switching on 7 or less. Assuming player 1 switches on 7 or less player 2 will maximize his expected outcome by switching on 8 or less. Given that the first player swithces on 7 or less and the second player switches on 8 or less the expected gain of the first player is ~ 0.081930. This was all calculated using a spreadsheet.

Following is an e-mail sent by Steve Schaefer, arguing that a random strategy on the part of player 1 is better than a fixed on.


I agree with your answer to #60, but I'm unconvinced by your solution.  I'm
pretty sure that you didn't sufficiently verify the answer.

I agree that you found the best answer with integer solutions using a
spreadsheet, but I don't think you ruled out non-integer solutions.

I found the integer solution P1 trades when holding 7 or less and P2 draws
when holding 8 or less, but I wasn't convinced that P1's optimum might not
involve trading _sometimes_ when holding an 8.

As it turns out, the integer solution is the best for that choice of rules. 
If P1 trades the 8 with probablility p, while P2 continues to draw for 8 or
less, then P1's expected outcome is (180-2p)/2197.  If P1 holds the 7 with
probability q, while P2 continues to draw for 8 or less, then P1's expected
outcome is (180-29q)/2197.  In this case, minor variations from the optimum
integer solution result in a lower expected outcome for P1.

If, however, we change the rules for ties, we can get a different situation.
Consider rules where P2 wins all ties, but P2 is required to draw to break a
tie if P1 and P2 just traded equal cards.  (Incidentally, this seems to be
the best game on several different levels.)

The best integer solution for P1 is to trade 7 and below.  If P1 doesn't
trade, then P2 will draw to 8 and below.  The expected outcome is in P2's
favor, but it is only 3/2197.  If P1 trades eights as well, then P2 will
change strategies and draw to a nine; then P2's expected outcome improves to
5/2197.  But, it is wrong to conclude that P1 should never trade eights!

If P1 occasionally trades eights, then P2 can't afford to shift strategy. 
In fact if P1 trades eights five out of seven times (at random), then P2's
expected outcome is reduced to 1.571/2197.  (That's 11/15379).

If P1 executes this strategy, it doesn't matter whether P2 draws to a nine
or not.  Except that if P2 always draws to a nine, then P1 might want to try
cheating a little to trade eights less than five out of seven times.  If P1
could cheat completely and stop trading eights altogether, then P1 could
have an advantage of 7/2197!  Similarly, if P2 never draws to a nine, then
P1 might want to try cheating the other way.  If P1 could cheat completely
and always trade eights, then P1's advantage would only be 1/2197.

So, P2 needs a randomized strategy, too!  In fact, the equation for P2's
expected outcome is:

2197*y = x2*(-7+12*x1)+(1-x2)*(3-2*x1),

where x1 is the probability that P1 will trade an eight and x2 is the
probability that P2 will draw to a nine.  If each player tries to maximize
their own outcome against an opponent doing the same, then the two partial
derivatives will be zero:

0 = 2197* dy/dx1 = 14*x2 - 2
0 = 2197* dy/dx2 = 14*x1 - 10

So, we get x1 = 5/7 and x2 = 1/7.  That is, player 1 will always trade a
seven or less and will never trade a nine or more, but will trade an eight
five times out of seven at random.  When player 1 elects not to trade, then
player 2 will always draw to an eight or less and will always keep a ten or
more, but will draw to a nine one time out of seven at random.

As it turns out, this variation on the rules gives the smallest margin for
either player that I could find.

In short, your solution sounded like you only considered integer strategies,
whereas non-integer strategies are definitely possible.  If we pick more
interesting rules, then we get a more interesting solution.


Michael Shackleford, ASA