Communications of the ACM
Puzzled: Lowest Number Wins
Credit: Shutterstock.com
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.
- 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?
- 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?
- 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?
Footnotes
Corrections to "Solutions and Sources" (Dec. 2013) to "Coin Flipping" (Nov. 2013). Three careful readers pointed out there are 12, not 10 (as we said in the solution to Problem 1) head-tail sequences of length 5 that take on average only 32 flips to occur. In addition, Joseph Skudlarek found a sequence (HTTHH or its complement THHTT) that gets the first player a better than 1/3 chance to win in Problem 2, 9/26, to be exact.
Readers are encouraged to submit prospective puzzles for future columns to [email protected].
The Digital Library is published by the Association for Computing Machinery. Copyright © 2014 ACM, Inc.