# Lowest Unique Bid

Each of n players simultaneously choose a positive integer, and one of the players who chose [the least number of [the numbers chosen the fewest times of [the numbers chosen at least once]]] is selected at random and that player wins.

For n=3, the symmetric Nash equilibrium is the player chooses m with probability 1/(2^m).

What is the symmetric Nash equilibrium for n=4? Is it known for general n?

• Do you know that a symmetric Nash equilibrium exists? Since the strategy sets are $\mathbb{N}$ you don't automatically get this for free as you would if they were finite. Also, you imply that for three players the symmetric Nash equilibrium is unique and you expect this to be true for four players as well. Do you have a proof that this is true in general or were you just being loose with the wording? Jun 4, 2010 at 15:09
• It is unique for 3 players, and I was just being loose with the wording for more players (though I do expect it would be unique).
– user5810
Jun 4, 2010 at 15:58

There is some published literature on this problem. See for example the following papers and the references therein.

Baek and Bernhardsson, Equilibrium solution to the lowest unique positive integer game

Houba et al., The Unique-lowest Sealed-bid Auction

Apparently, in general, the Nash equilibria are intractable to describe.

• The game in the paper is slightly different from the one in the post. In the paper a player can only win by choosing a unique number. In the post if n=4 and two players choose 1 and the other two choose 2 then the players choosing 1 each have a 1/2 probability of winning. This difference may or may not have a significant effect on equilibrium strategies. Jun 4, 2010 at 18:09

There are non symmetric Nash equilibria. For example with 3 players: (1,1,2) is a silly solution.

• So the player with 2 is winning and happy. Neither player with 1 has anything to gain by switching to 2 or higher.... But if the first two players chose 1 or 2 with probabilities $\frac14$ and $\frac34$ then the third player would only win $\frac1{16}+\frac9{3\cdot16}=\frac14$ of the time. So is it really stable? Feb 17, 2012 at 7:51