Communications of the ACM

Last byte

Puzzled: Lowest Number Wins

By Peter Winkler
Communications of the ACM, February 2014, Vol. 57 No. 2, Page 120
10.1145/2559597
Comments (2)

Each of these puzzles involves a symmetric game. You will be asked about your best strategy, but what does "best strategy" mean? Here, we want a strategy that is a "Nash equilibrium" for all players; that is, one with the property that if it is followed by all other players, you can do no better than follow it yourself. Often, such a strategy requires that players do some randomization; for example, in the familiar game "Rock, Paper, Scissors," the Nash equilibrium strategy requires each player to choose rock, paper, or scissors with equal probability. As in "Rock, Paper, Scissors," plays in the games here are done simultaneously, with no collaboration allowed, so every man/woman for him/herself. For solutions and sources, see next month's column.

1. Having found a dollar bill on the street, Alice and Bob each write down a positive integer. Lowest integer wins the dollar. If they each write the same number, the dollar is torn up. What is the highest integer you, as Alice, should consider writing down?
2. No dollar is found this time. Alice and Bob instead play a "zero-sum game" with their own money. Each again writes down a positive integer. Lowest integer wins $1 from the other player, unless it is lower by exactly 1; in that case, the player with the higher number wins $2 from the other player. If the players happen to choose the same number, no money changes hands. What is the highest integer you, as Alice, should consider writing down?
3. Three players this time, with a $10 prize to be given to the player who writes down the lowest number not written down by any other player. For example, if Alice and Bob each write "1" and Charlie writes "2," Charlie wins the $10. If Alice writes "2," Bob "3," and Charlie "5," Alice wins. If all three write the same number, the prize goes unclaimed. What is the highest integer you, as Alice, should consider writing down?

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2014 ACM, Inc.