3 contestants choosing a smallest number to win a car

Question

Each of 3 contestants chooses a positive integer. The contestant who chooses the unique smallest positive integer number wins a car. If all of them chose the same number, then no body wins car. What is the optimal strategy?

I do not know how this is done, so I can only guess.

The players should play the same strategy, by the nature of the game. I started off assuming that it makes no sense choosing 4 or above (so I assumed one should choose 1,2 or 3).

After some algebra bashing, I arrived at the result.

maximise $x(1-x)^2 + y(x^2+(1-x-y)^2)+(1-x-y)(x^2+y^2)$ subject to the condition $x+y\leq 1$

Somewhat surprisingly, this expression in symmetric in x and y. I used the Language's multiplier and arrive at $x=y=4/3-\sqrt{40}/6$, which is about 0.28.

This suggest the contestants should choose 1 or 2 with probability 0.28 and choose 3 with probability 0.44. The chance of winning is about 0.29.

However, it is clear that this is not the optimal strategy. If players A and B uses such strategy, then C can choose 1 or 2 with probability 1/2, then he has about > 0.5 chance of winning.

I suspected that the optimal strategy is all players choose 1 or 2 with probability 1/2. I seem to find is no way of deviating from this strategy which would improve each player's pay off. Is this right? how do we prove this?

Answer 1

Okay, I'll try to formulate something that hopefully makes sense. This is long mainly because you're relatively unfamiliar with game theory, and I want to make sure that you get what is happening here. I get a bit hand-wavy at parts, sorry about that. Oh, also, the more usual, simple version of this is called the Competition Game, which is a good way to see how results can be weird when you're new to game theory. Check it out.

The assumptions are the following:

1. The players are not cooperating.
2. The players want to individually maximise their expected benefit, (which is $1$ when they get the car, and $0$ otherwise)

Suppose instead of all positive integers, we were looking at positive integers up to some $N$, and $A$ put some probability distribution $p_A$ on them: $A$ samples the space of possible moves with $p_A$ and plays the result. $A$ wants to choose the $p_A$ such that her chance of winning the car is maximised given that $B$ and $C$ are running their own strategies $p_B$ and $p_C$. But the symmetry of the problem - all three are in the identical situation- suggests that whatever $p_A$ she decides, $B$ and $C$ will also decide the same. So she can assume $p_A$, $p_B$, $p_C$ are identical, some $p$. The thing left to choose is the actual $p_k$ and cardinality $N$.

(I waved my hands a bit there, and if you want to learn a more precise and general version of this idea, pick up a good game theory text. Actually, even the wiki page isn't too bad. This essentially defines a mixed Nash Equilibirium, and Nash famously showed that this exists, so we're not in too much hot water)

So, from any one player's point of view, you have three i.i.d random variables $X_1, X_2, X_3 \sim p$, and we're interested in the optimisation problem

\begin{equation*} \begin{aligned} & \underset{p, N}{\text{max}} & & P(X_1 < X_2, X_1 < X_3) \\ & \text{subject to} & & p_k = 0, \; i \notin [1: N] \\ & & & \sum_1^N p_k = 1 \end{aligned} \end{equation*}

(Note that this is strictly less than $1/3$. Herein lies the difference with the cooperative case. $A$ could have just played a random over numbers of the form $3k$, $B$ over $3k+1$, $C$ over $3k+2$, and they'd have essentially made their chances of winning a car the same, which is anyway enforced, and maximum. The reason they can't do that here is obvious - even if they realised that this was the best way to go, there's no way to ensure that they'd pick the right parities.)

This may or may not be easy to solve. Intuitively, the optimal strategy seems to be that to find a very large $N$ and uniformly sample over $[1:N]$, so that the chance of collisions is small, and the individual probabilities of winning as close to $1/3$ as possible.

(There are technical issues with this, the main one being that distributions over the natural number don't really exists)

Note however, why the strategy you suggest is unstable: Suppose I have a strategy that mean I will win with probability $x$, and there exists a strategy that increases this chance, I will definitely switch to it. This would affect the chances of my opponents winning, and if they find that they can do better with something else, given that I'm now playing this new strategy, they will switch as well. This would either keep going on forever, or we'll hit some sort of fixed point, where changing is detrimental to all players, and stay there. Nash showed that at least one fixed point exists.

Answer 2

There is no optimal strategy of the form "everyone follows this given probability distribution: pick $i$ with probability $p_i$".

Indeed, everyone will follow the same strategy if there is an optimal one, so the probability that anyone wins is equal and is at most 1. That is, the four things that can happen are "I win", "Player 2 wins", "Player 3 wins", "no-one wins", and these cover the entire range of options. The first three have equal probability, so it turns out that an optimal strategy is characterised precisely by the need to minimise the probability that no-one wins.

The probability that no-one wins is $\sum_{i=1}^{\infty} p_i^3$, the probability that everyone picks the same number. We wish to minimise this while ensuring that $\sum_{i=1}^{\infty} p_i = 1$.

But we can pick $p_i$ so that this has arbitrarily small sum, as can be seen with Lagrange multipliers: there is no optimal strategy of this form. For any distribution you give me, I can give you a better one.

However, if everyone adopts the strategy "Pick one of the first $N$ integers at random", then there is probability $\frac{1}{3} - \frac{1}{3 n^3}$ of me (and hence of any given person) winning. That is, with collaboration, you can make the probability of someone winning arbitrarily close to 1.

Answer 3

If there is a Nash equilibrium, and the other two are playing it, then it doesn't matter what number the first player plays. So if the others play with probability distribution p(1)=a,p(2)=b,p(3)=c,
First player wins playing 1 with probability $(1-a)^2$
First player wins playing 2 with probability $a^2+c^2$
First player wins playing 3 with probability $a^2+b^2$
So $(1-a)^2=a^2+c^2=a^2+b^2,a+b+c=1$
which has solution $a=2\sqrt{3}-3,b=2-\sqrt{3},c=2-\sqrt{3}$ and first player wins with probability $28-16\sqrt{3}=0.287$
If they use four numbers, then $(1-a)^2=a^2+(1-a-b)^2=a^2+b^2+d^2=a^2+b^2+c^2$ and Wolfram says the chance of a win is 0.294
When more numbers are used, it seems that $a/b,b/c,c/d,...$ all approach the same ratio. That gives this solution for infinitely many:
$$(a_1,a_2,...)=a_1(1,x,x^2,x^3,x^4,...)\\a_1=1-x$$ Then, using $$(1-a_1)^2=a_1^2+(1-a_1-a_2)^2\\x^2=(1-x)^2+x^4\\x^3+x^2+x=1$$ we get the value of $x=0.5437$ for the Nash equilibrium, with a win probability of $(1-a_1)^2=0.2956$