Game Theory - Choosing the smallest number not chosen yet

Question

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.).

Answer 1

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.

Answer 2

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$).

Answer 3

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:

• Least Unmatched Price Auctions (2007)
• Reverse Auction: The Lowest Unique Positive Integer Game (2007)
• The Unique-Lowest Sealed-Bid Auction (2008)
• Equilibrium Solution to the Lowest Unique Positive Integer Game (2009)
• Equilibrium Strategy and Population-Size Effects in Lowest Unique Bid Auction (2012)

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!

Answer 4

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.

Answer 5

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.