Saturday, May 28, 2011

Cake paradox resolved - an excursion into Game Theory

In the last posting we elaborated the cake paradox. In short, if we agree to bring in a cake on any day within the following week, Friday (the last day) is not a good choice, because then, the people can predict this already after there was no cake until Thursday. Iterating this argument we end up that no day is good for a surprise.

Actually, we need to clarify certain things in the model here. First, a situation where one is expecting a cake, but it is not brought is also a kind of surprise, though a disappointing one.
Second, if the colleagues are forced to choose one day, the odds are simply 1 out of 5 to guess the day right. Waiting until Thursday to place the bet does not help the guesser here, because in this case you have a high chance to have already lost because the cake was brought before.

However, the game becomes interesting, if the colleagues get the possibility to put a bet on a day at any time before that day but making betting optional. So if you are a cautious person, you might not bet at all, or would wait until Thursday evening, and place the sure bet in case the was not brought before. What is the best strategy for this set up?

Let's look at the payoff table for a situation where only Thursday and Friday are left, the cake has not been brought in yet and no bet was made so far. Player A has to bring in the cake, while player B tries to place the bet.

Player A brings cake on Thursday Player A brings cake on Friday
Player B places bet on Thursday (-1,1) Player B guessed it right (1,-1) Player B guessed it wrong
Player B waits and eventually places bet on Friday (0,0) No bet was placed, game is over (because cake is there) (-1,1) Player B guessed it right

This situation has no pure-strategy Nash Equilibrium. For the best mixed strategy, Player A should chose Thursday with a probability of 2/3, otherwise Friday. In contrast, Player B's best strategy is to bet on Friday with a probability of 2/3. The expected payoff for Player A is then -1/3, which means an advantage for B.

Now we can set up a payout table for the "Wednesday or Later" game. The "Later"-Payoff in the case that neither the cake has been brought yet nor Player B has used her bet so far is the 1/3 derived from the previous payout table.

Player A brings cake on Wednesday Player A brings cake later
Player B places bet on Wednesday (-1,1) Player B guessed it right (1,-1) Player B guessed it wrong
Player B waits (0,0) No bet was placed, game is over (because cake is there) (1/3,-1/3) Game defaults to previous situation

This way we can iterate the game until we end up on Monday. Assuming optimum mixed strategies, the best strategy for Player A to bring in the cake calculates to
16/31 for Monday
8/31 for Tuesday
4/31 for Wednesday
2/31 for Thursday
and 1/31 for Friday.

The guessing player has the same probabilities but increasing from 1/31 for Monday until 16/31 for Friday because the chances favor the guesser towards the end of the week. These mixed strategies establish a Nash equilibrium, thus none of the players has a benefit on changing the strategy. In overall, the game slightly favors the guesser, who is expected to win 3% more often.

Now, we earned ourselves a cake - bon appetit!

1 comment:

  1. If you could place a bet any day, then that would be like getting to see everybody's hand in poker before deciding on folding or calling. If the betting could only be placed monday, then things could get interesting.