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!

Tuesday, May 17, 2011

The cake paradox

There will be cake today
At the institute we have a (recent) tradition to bring home-made cake for the group. Each co-worker is assigned one week within he or she can freely choose one workday to bring the cake. So the actual day when there is cake will be a surprise to the others.
Unless... there is one problem when the process is viewed from a logical perspective.
Consider me having made a cake and planning to bring it in on Friday. Friday is the last workday in the week, so the others could predict the cake to be brought on Friday as soon as they see on Thursday that there is no cake. So I will not choose Friday, because it won't be a surprise on that day.
However, assuming totally logical actors, also Thursday is not an option, since the others will come to the same conclusion that Friday is off the list and they would know on Wednesday evening, when no cake appeared so far, that I will bring it on Thursday. So Thursday is not a surprise day either. We can iterate this argument and end up with the interesting situtation that I have to bring the cake on Monday, since all other days would not be a surprise. Having decided that even Monday is no surprise either.
So it looks like that it is impossible to bring a cake on a weekday as a surprise if everybody knows that I have to bring a cake within this week.
The paradox is interesting but it is also obvious that there is a difference between totally logical and natural actors. Asking people, they usually agree on the argument that Friday would be no surprise, but every other day would be. What do you think?

If you like this kind of puzzles, I recommend the book of Zbigniew Michalewicz and his son on Puzzle-Based Learning.