# Guessing the smallest unique positive integer

Let us consider the following game: there are some players and a computer. Each player inputs one positive integer and his name (player doesn't know another's numbers, just his own). When all the players made their moves, computer outputs a name of winner – who submitted the lowest unique number.

How do you think, what is the best strategy for this game?

• There are a bunch of webpages for this problem with conflicting answers, but this one seems likely to have gotten it right. – Peter Shor Jul 3 '13 at 14:08
• @PeterShor or vortexxx192 - consider summarizing the information at the given link in an answer, as applicable. – Patrick87 Jul 3 '13 at 14:32
• This game was actually run for a Dutch newspaper by a popular mathematician. There were 1607 participants and the winner chose 35. Source (Dutch, paywall): volkskrant.nl/opinie/… – Albert Hendriks Apr 27 '18 at 0:04

There are a number of discussions of this game online, but you should be wary because some of them give incorrect solutions. This website gives an excellent exposition of how to solve this game. (Based in part on this paper.) You assume that all players use the same mixed strategy, and that when all players use this strategy, there is a Nash equilibrium. This gives equations which for three players have a closed form solution: you choose the integer $i$ with probability

$$0.839286 \cdot (0.543689)^{\textstyle i}$$

where 0.543689 is the solution of $x^3 + x^2 + x = 1$.

For $k$ players, if $k \geq 4$, the equations can still be derived, but they appear to have no closed form solution. However, in the optimal strategy the probability of playing a number larger than $k$ is very small, so an explicit nearly-optimal strategy can be found by solving the equations numerically.

Not enough reputation to comment, but, it is worth noting that if your opponents are playing by the Nash equilibrium strategy Peter Shor described for a 3 player game your chances of winning are around 29.6% irrespective of the number you choose. If you are only playing a single game (so no one can determine your strategy) and consider a draw between all players no better than a loss, a large number such as 89285829358008871 will give you the same chance of victory as a 1 or 2.

In this specific case, there's nothing to lose from trying a different strategy, just in case your opponents don't conform to your assumptions.

• Basically, what you're saying is that there are strategies that do well against the equilibrium strategy. This is essentially always the case and, really, all you're doing is violating the assumption that the players act rationally. Sure, you can beat the Nash equilibrium but if the other players know you're going to try to do that, they can play in a way that makes you (likely to) lose out. – David Richerby Apr 27 '18 at 13:13
• No, that was not what I was saying at all! I never stated that the Nash equilibrium would be beaten - if the other two players opt for that strategy then it will NOT be beaten. Rather, the third player's response is irrelevant as it has no impact on the final outcome (on average), so there is no cost in switching strategies (if an opponent elects a sub-optimal strategy, for instance - no assumption of rationality in OP). The response was more to highlight some particular properties of the Nash equilibrium, and discuss some of the practical implications. Does that address your concerns? – Matt Thompson May 1 '18 at 4:08