The Least Unique Game

by Kevin Lin

"I am not a great fool, so I can clearly not choose the wine in front of you. But you must have known I was not a great fool, you would have counted on it, so I can clearly not choose the wine in front of me."

- Vizzini, in "The Princess Bride"

Playing "1" seems like a good strategy since no one can play anything lower. But surely at your opponents will consider playing one. And if they both play "1", then you would be better off playing "2". Again, though, your opponents may reach the same conclusion. What about playing some random number between 10 and 10,000,000? If your both opponents are using some strategy that ties half the time, you'd win half the time. But this gambit would lose badly if they both played random numbers from 1-10.

Like Vizzini in the Princess Bride, it appears as though you are trapped in an infinite regression of second guessings. If you believe strategy "A" to be the best strategy then at least one other player should play that strategy as well. If a third player can expect a better return with strategy "B," then "A" is not the best strategy to adopt.

Is there a strategy "S" such that if you play "S" and one opponent plays "S", the third opponent cannot see a better return with any other strategy?

In game theory parlance, a game is in a Nash Equilibrium if given a particular set of strategies for each player no one player can benefit by changing her strategy while the other players preserve theirs. In this case, we're looking for a Nash Equilibrium (NE) that is symmetric with respect to all players. (If two players always choose "1" and the third player always chose "2" the game would be in equilibrium. However given that all players are equally rational this situation is unlikely to arise-- two players will have a strong motivation to break the equilibrium.)

It should be obvious that all players playing the same number with 100% probability (a "pure" strategy) will not be in NE. So what we're looking for is a "mixed" strategy-- one where numbers are chosen randomly but with a predetermined frequency. For example, flipping a coin and choosing "1" if it's heads and "2" if it's tails.

Unfortunately, that strategy won't work because if two players adopt it they will tie half the time and the third player can improve her win rate by choosing "3" every time.

What we're looking for is a strategy for two players where no number chosen by a third player enjoys any advantage.

It turns out that there is just such a mixed strategy:

Choose "1" with a probability of 1 in 2,
Choose "2" with a probability of 1 in 4,
Choose "3" with a probability of 1 in 8, etc.

All integers are chosen with diminishing probability. Given this mixed strategy, the third player cannot improve (or even change) his or her return by deviating from this strategy, whether she always chooses one or one million. If all players adopt this strategy they will be in a mixed, symmetric Nash Equilibrium and no one will have a motivation to change strategies.

Back to the Puzzle