# Game Theory - Choosing the smallest number not chosen yet

A company has a competition to win a car. Each contestant needs to pick a positive integer. If there’s at least one unique choice, the person who made the smallest unique choice wins the car. If there are no unique choices, the company keeps the car and there’s no repeat of the competition. It turns out that there are only three contestants, and you’re one of them. Everyone knows before picking their numbers that there are only three contestants. How should you make your choice?

Thoughts: Since there's no strategy you can adopt that the others cant, you need to aim for the situation where the other 2 pick the same number so you need to avoid them, so perversely aim high. However the other 2 can do the same as well, so do you aim lower of the high numbers, or does it make no difference?

I understand the answer is not: pick 12, but once you've gone beyond the strategy of getting the other 2 to match, do you hedge your bets somewhat by keeping it low, or do you maximise your chances of your strategy working by going insanely high (utilising exponentials etc.).

• 1 seems to be the best choice, as you only lose if BOTH other people pick 1 (or, rather, if only one other person picks 1, you would lose no matter what). Pick 2 if you think both other people will pick 1. There is no reason to pick anything higher.
– Carl
Nov 10, 2011 at 2:19
• So what should you do??? (ps. posted by a 11 yr old)
– user133592
Mar 6, 2014 at 18:58

I assume there is no possibility of collusion between players. Consider mixed strategies $S$ where you choose positive integer $i$ with probability $S_i$. Thus all $S_i \ge 0$ and $\sum_{i=1}^\infty S_i = 1$. There appears to be a Nash equilibrium in which all three players (independently) use the same mixed strategy, which gives positive probabilities to all positive integers. The first 9 probabilities are approximately $S_1 = .4563110597, S_2 = .2480914427, S_3 = .1348849695, S_4 = 0.07333654926, S_5 = 0.03987532390$, $S_6 = 0.02168843374, S_7 = 0.01181641450, S_8 = 0.006495476489, S_9 = 0.003750165099$. I obtained these as follows.

Suppose the other two players both choose the mixed strategy $S$, and you choose number $j$. Then the probability you win (i.e. either both choose the same number $< j$ or both choose numbers $> j$) is $Q_j = \sum_{i=1}^{j-1} S_i^2 + (1 - \sum_{i=1}^j S_i)^2$. In order for $S$ with all $S_i > 0$ to be a Nash equilibrium, no player can have an incentive to "defect", so no $Q_j$ can be greater than the probability $Q_S$ of winning if you also choose mixed strategy $S$. But $Q_S = \sum_{j=1}^\infty Q_j S_j$, so $Q_S \le \max_j Q_j$. We conclude that all $Q_j$ must be equal. So $S$ should be a solution of the infinite set of nonlinear equations $\{ \sum_{j=1}^\infty S_j = 1, \ Q_1 = Q_2 = Q_3 = \ldots \}$. I doubt that there is a closed-form solution, but I used Maple's fsolve to get a numerical solution to a finite truncation of the system, with the result I quoted above.

• Hi @RobertIsrael, how did you go to the point of all $Q_i$'s being equal from the previous two-three lines?
– A. G
Jun 16 at 20:34
• @A.G $\max_j Q_j \le Q_S \le \max_j Q_j$ so they are equal. If the maximum is for $j = j^*$, $0 = Q_S - Q_{j^*} = \sum_j (Q_j - Q_{j^*}) S_j$, but since all terms $\le 0$ this can only be $0$ if all terms are $0$. Jun 18 at 19:01
• thanks a lot, sure makes sense, I was thinking of proving that using a kind of "convex combination" argument, but what you've written is a translated formal formulation. And the argument that all $S_j$ should be bigger than 0 for it to work can be done via induction/contradiction if not as in the comment from the next answer, right?
– A. G
Jun 28 at 20:34

If we restrict our search to the geometric distributions with some parameter $$p$$: $$S_k=(1-p)p^{k-1}$$ Then all the $$Q_n$$'s from Robert's answer will be equal to: $$Q_n = \sum_{i=1}^{n-1} S_i^2 + (1 - \sum_{i=1}^n S_i)^2=\frac{1-p}{1+p}+\frac{p^{2n-2}}{1+p}(p^3+p^2+p-1)$$ So they will all be equal when $$p$$ is the only real root of: $$x^3+x^2+x-1=0$$ Which is equal to $$s \approx .543689012692076$$. The first nine probabilities are therefore:

$$S_1 \approx .456310987307924$$
$$S_2 \approx .248091270169992$$
$$S_3 \approx .134884497736246$$
$$S_4 \approx .073335219401686$$
$$S_5 \approx .039871553032060$$
$$S_6 \approx .021677725302500$$
$$S_7 \approx .011785941067126$$
$$S_8 \approx .006407886662433$$
$$S_9 \approx .003483897572941$$

If all players play according to this strategy then the expected value of their payoff will be the common value of all $$Q_n$$'s i.e.: $$\frac{1-s}{1+s} \approx 0.295597742522085$$ Which is also the unique real root of $$x^3+x^2+3x-1=0$$. It is less than $$\frac{1}{3}$$ because there is a: $$\sum_{n=1}^{\infty}S_n^3=1-3\frac{1-s}{1+s}=\frac{4s-2}{s+1} \approx .113206772433746$$ Chance of all of them choosing the same number (it is the real root of $$x^3-6x^2+36x-4=0$$).

• Very nice answer! I think there is an argument showing that $S$ must necessarily be geometrically distributed: we have $\mathbb{P}(S=i+j | S > i) = \mathbb{P}(S=j)$ because the condition in the first term means that all players choose a number $>i$ and the whole problem is just translated. Thus $S$ is memoryless which is a defining property, so $S$ must be geometric. This explains why this answers gives (roughly) the same numbers as Robert who doesn't make any a priori assumption on the distribution. Dec 21, 2021 at 23:56

Shameless Advertisement: Game Theory proposal on Area 51 that you should follow!

This is the lowest unique positive integer (LUPI) game, which is relatively well studied or sparsely studied depending on who you ask, and in which year you've asked. There appear to be some nice answers; for example, if all numbers are allowed, one symmetric mixed strategy is:

$$\text{Each player chooses } m \text{ with probability } \frac{1}{2^m}$$

For a symmetric equilibrium among the first $n=3$ natural numbers, choose $1$ with probability $2\sqrt3-3\approx46.4\%$ and $2$ and $3$ each with probability $2-\sqrt3\approx26.8\%$, according to Comments on 'Reverse Auction: The Lowest Unique Positive Integer Game (2008)

If there is "Poisson-distributed uncertainty about the number of players", then you'll need a model like that in Testing Game Theory in the Field: Swedish LUPI Lottery Games (2010), which gives some experimental and actual results, should you be so inclined.

Other references, generally dealing with endogenous entry (anyone can enter) include:

Some of which are from this nearly identical MathOverflow post on Lowest Unique Bid

After spending considerable time on what I thought was a simple question (despite having been previously forewarned in a Behavioral Game Theory class two years ago), I can't actually validate these answers, but someone on a Game Theory StackExchange might!

• I'm curious what's wrong with the following thinking. Suppose there are 100 players, and we're all perfectly rational. What are my odds of winning? Not higher than 1%. For if I could choose a strategy with better odds, the other players would choose it too, and then each player's chance of winning would be > 1%. But that's impossible, since there are 100 players. A strategy with a 1% chance of winning is simply: pick a random positive integer. If we all use this strategy, each player's chance of winning is 1%. So this strategy must be the best. Jun 18, 2022 at 22:37
• The game considered in  Comments on 'Reverse Auction: The Lowest Unique Positive Integer Game (2008)' puts a restriction on the integers to be chosen. May 8 at 9:14

I don't know if assigning probabilities helps here because you play only ones.

My approach is as follows:

Let's say the other player's choices are a and b, and mine is c. Without loosing generality and for shortness of notation, let's assume that a is always the smaller of both a <= b.

Knowing a and b the best choice for c is:

If a = b = 1, I choose c > 1.

If only one of a = 1 and b > 1, I cannot win.

If both a, b > 1, I win as long as c < a, b.

Lets examine our choices:

c = 1: I win if a, b >1, I loose if a = 1.

c = 2: I win if a = b = 1 or if a > 2, I loose if a = 1 < b, or one of a and b = 2.

c = n > 2: I win if a = b or if a > n, I loose if a < n <= b or one of a and b = n.

It appears that every time c > 2 wins, c = would also win, except if one of a and b = c. I therefore deduce that the only sensible choices are c = 1 or 2 which win with equal probability.

Beyond that it's just chance and dependent on how smart the other players are. If both of them follow my reasoning and choose between 1 and 2, my chances of winning are 1/4 (because the dealer keeps the car if a = b = c), otherwise they are higher.

• Welcome to Math.SE! When posting an additional answer to an older Question, you may help your Readers by highlighting ideas presented in your Answer that are not already covered by previous answers. Math expressions can appear in your posts by using MathJax and $\LaTeX$. Jan 22, 2016 at 12:18

Let's say that n is the highest number any player can pick. Then if you choose n, you win anytime the two other players choose the same number except n.

Now consider to choose n+1, then you win anytime the two others pick the same numbers. We observe that n+1 is better than n`, and there can't be an equilibrium. Therefore, there'll be a lot high submissions by each contestant.