# 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? –  Noah Stein Jun 4 '10 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). –  Ricky Demer Jun 4 '10 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. –  Noah Stein Jun 4 '10 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? –  Aaron Meyerowitz Feb 17 '12 at 7:51