Communications of the ACM
Last byte
Puzzled: Solutions and Sources
Credit: Shutterstock.com
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.
Footnotes
All readers are encouraged to submit prospective puzzles for future columns to [email protected].
©2014 ACM 0001-0782/14/03
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2014 ACM, Inc.
No entries found