Game Theory - Unsure how to proceed with this 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.).

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

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