## Friday, November 30, 2007

I read the other day an article by Douglas Hofstadter on his game Mediocrity: three players choose a number each and the winner is that who has chosen the number in the middle. Hofstadter describes the game and then go on with designing arrangements for several types of tournaments, but he does not devote much time to the optimum strategy of the basic game itself; this is somewhat surprising because thinking about how to best play induces some kind of interesting circular reasoning. The following is an attempt to do that analysis. The game is dependent on the number of choices each player is given.

The N-option Mediocrity game: For a fixed N≥1, player A can only choose among 1,4,...,3N-2, player B among 2,5,...,3N-1 and player C among 3,6,...,3N. The winner is the player who has chosen the number in the middle.

Observe that there cannot be ties. For the purposes of our investigation, let's add some constraints:

• Coalitions are not allowed.
• The players are assumed to be perfectly rational, i.e. they are motivated exclusively by their own payoff and will be able to pursue any logical argument to that end; moreover, they know that each player knows about their opponents' perfect rationality.

"I must choose among 1,4,...,3N-2. Clearly 1 can never be in the middle, so I discard it. Player B, however, knows I won't play 1, so she won't choose 2, and thus player C, who can also deduce this, won't play 3. Hence 4 is not an option for me either, and this implies B won't play 5,..."

So it seems like A cannot rationally choose any number, and similar reasonings can be derived for B and C. But of course in the end they must choose some number and someone has to win. This puzzle is reminiscent of the much debated Surprise Examination Paradox; the difference, however, is that Mediocrity involves no modal statements about belief and such, so maybe it is easier to solve.

When N is small the analysis of the game is in fact straightforward:

The 1-option game

 1 2 3 A B C

As each player has only one number to play to, the automatic winner is B.

The 2-option game

 1 2 3 4 5 6 A B C A B C

A can't play 1, so she chooses 4 and C can't go for 6 so she plays 3. B loses regardless of her choice, so there are two possible outcomes with no particular preference: (A←4,B←2,C←3) and (A←4,B←5,C←3), bolds mark the winner.

When N≥3 things look considerably harder. We will look at this in a later entry.