Opinion
Computing Applications Last byte

Puzzled: Solutions and Sources

Posted
  1. Article
  2. Author
  3. Footnotes
hand holding pen

Last month (February 2014) we posted three games in which you were asked to pick a positive integer. The question in each was: What is the highest number you should think about picking? Here, we offer solutions to all three. How did you do?

1. Found dollar.

Alice and Bob are vying for a found dollar, with lowest number the winner and a tie winning it for neither. Sadly, the only "Nash equilibrium" solution is for both players to choose "1" and the dollar to go unclaimed—a mini "prisoner’s dilemma." Collaboration could have won each of them 50 cents.

2. Zero sum.

Here, the writer of the lower number wins $1 from the other player, unless it is lower by only 1, in which case the player with the higher number would win $2 from the other player. A tie would result in no money changing hands. This problem was published by Martin Gardner, appearing as Problem 11.13 in his The Collossal Book of Short Puzzles and Problems (W.W. Norton & Co., New York, 2006). The Nash equilibrium solution would be to write "1," "2," "3," "4," or "5" with probabilities 1/16, 5/16, 1/4, 5/16, and 1/16, respectively. (Gardner did not provide a proof, but it is not difficult to show this is a Nash equilibrium strategy and, with a little more work, the only one.) The highest number either player should consider writing is thus "5."

3. Swedish lottery.

This game, which I included in my book Mathematical Puzzles: A Conoisseur’s Collection (A K Peters Ltd., Natick, MA, 2001) as "Swedish Lottery," has the surprising property that the equilibrium strategy calls for playing every positive integer with positive probability. There is no largest integer you should consider playing. To see this, imagine for the sake of reaching a contradiction that there is a highest number you (and the other players) should ever play; call it number k. When would you win playing k? Only when the other players choose the same lower number. But if you played k+1, you would win all those times plus the times the other two players both play k. k+1 is thus a better choice than k, contradicting the assumption that the strategy is a Nash equilibrium. There is, in fact, a common Nash equilibrium strategy for Alice, Bob, and Charlie—calling for the number j to be selected with probability (1–r)r j−1 where r is the root of a certain cubic equation and approximately 0.543689. The probabilities for choosing 1, 2, 3, and 4 are about 0.456311, 0.248091, 0.134884, and 0.073335, respectively; the probability of choosing a number greater than 100 is teeny. As an experiment in 2010, I ran a Swedish Lottery among 40 graduate students in Dartmouth’s Computer Science Department. The winning number was 6. A much larger version—actually a game a day for 47 straight days—was run in Sweden in 2007 under the name "Limbo." The number of players each day averaged 53,785; the lowest winning number was 162, the highest 4,465. For more, see http://swopec.hhs.se/hastef/papers/hastef0671.pdf.

Back to Top

Back to Top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More