Interview Questions V: The Lowest Unique Positive Integer Game

Today’s post will be quite an extended one, about an interesting game theory problem I’ve been thinking about recently. The game is a lottery that works as follows. Each of N players chooses a positive integer, and the player who picks the lowest integer that no-one else has selected wins. There are two variants of the game discussed in the literature, one in which the integers must be between 1 and N, and one in which they have no limit. Except in the specific case of only 3 players, this restriction seems to make no difference to the solution […unless I’ve got my algebra wrong, which is by no means impossible!].

Note that throughout this post, I’ll assume a basic familiarity with probability and knowledge of the formulae for infinite sums (given here, for example), particularly the sum to infinity of a geometric progression:

    \[\forall \; 0 \; \textless \; x \; \textless \; 1 \; : \; \sum^{\infty}_0 Ax^n = {A \over 1-x}\]

3-Player Case

I start with the N=3 case to illustrate the principles of the problem. Because going in to the problem we have exactly the same information as the other two players, there is no deterministic solution, and in order to maximise our chances of victory we need to adopt a ‘mixed strategy’ which involves selecting a random distribution that assigns a probability to the selection of each integer. This is explained a bit further at this website, although unfortunately the solution that they present is incorrect!

In the case that players are limited to selecting 1-N (so 1, 2 or 3), the problem is analysed in a paper on arXiv (although there’s also a mistake in this paper – this time the N=4 solution presented is incorrect, as I’ll show later), and my solution will follow the author’s.

We are trying to select a set of probabilities \{ p_1, p_2, p_3 \} such that when all players play this strategy, no player increases her chances of victory by adjusting her strategy (such a solution is called a Nash Equilibrium in game theory, as seen in A Beautiful Mind). Let’s assume player 2 and player 3 are both using these probabilities, and player 1 tries to increase her chance of victory by playing instead the strategy \{ q_1, q_2, q_3 \}.

If she chooses 1, she wins if the other players both play either 2 or 3; if she chooses 2 she wins only if the other players both play 1 or both play 3, and if she chooses 3 she wins only if both other players play 1 or both play 2. So, we can express her total probability of victory as the sum of these three terms

    \[p({\rm victory}) = q_1\cdot(p_2 + p_3)^2 + q_2\cdot(p_1^2 + p_3^2) + q_3\cdot(p_1^2 + p_2^2)\]

And subject to the normalisation condition

    \[\sum_1^3 p_n = \sum_1^3 q_n = 1\]

Maximising the victory probability is a natural problem for the method of Lagrange Multipliers. The Lagrange equation

    \[{\partial \over \partial q_n} \Big( p({\rm victory}) -\lambda \sum_1^3 q_n \Big) = 0\]

gives us the following three equations

    \[(p_2 + p_3)^2 = \lambda\]

    \[p_1^2 + p_3^2 = \lambda\]

    \[p_1^2 + p_2^2 = \lambda\]

And as in the paper above, we can solve these simultaneously along with the normalisation condition to give the probabilities

    \[p_1 = {2 \sqrt{3} - 3} = 0.46410\]

    \[p_2 = {2 -\sqrt{3}} = 0.26795\]

    \[p_3 = {2 -\sqrt{3}} = 0.26795\]

Her chances of victory are now 0.28719, regardless of her strategy – the equations above say that as long as two players play this solution, the other player can’t change her probability of winning by choosing ANY strategy. For example, if she switches her strategy to ALWAYS choosing 1, she will now win whenever the other two players play either 2 or 3, the chance of which is given by (1 - 0.46410)^2 – and this is still 0.28719.

Now what if we relax the restriction that bids be between 1 and 3?

We can see immediately that the solution presented in the first link above, p(x) = 0.5^x, is incorrect – in this case, if the third player plays always 1, she wins ¼ times (when both other players play more than 1), while if she plays always 1000, she wins almost a third of the times (whenever the other two players play the same number). But we said her victory probability should be independent of strategy for the Nash Equilibrium, so this can’t be correct. But it is along the right lines – the actual solution does decay rapidly as x increases.

Her chance of victory is now

    \[p({\rm victory}) = \sum_{i=1}^{\infty} q_i\cdot \Big\{ \sum_{j=1}^{i-1} p_j^2 + \Big(\sum_{j=i+1}^{\infty} p_j\Big)^2 \Big\}\]

And differentiating this with respect to each q_i in turn gives an infinite set of coupled equations

    \[\forall i:\quad\sum_{j=1}^{i-1} p_j^2 + \Big(\sum_{j=i+1}^{\infty} p_j\Big)^2 = \lambda\]

This turns out to be solvable, but difficult – a sketch of the solution is given at the bottom of the post. The solution is p(x) = A e^{-\alpha (x-1)}, A is given by the normalisation condition

    \[\sum_{n=1}^{\infty} A e^{-\alpha(n-1)} = 1\]

    \[A = (1-e^{-\alpha})\]

and we can use a trick to find the parameter \alpha. We’ve said that the third player’s odds of victory are independent of her strategy. Consider two strategies, one in which she plays the same as the other players, and another in which she always plays the same, very large number (say 10^{500}). In the first case, chances of victory are equal for all three players, so they must be equal to 1/3 times one minus the chances of NO-ONE winning (which happens when they all choose the same number)

    \[p({\rm victory}) = {1 \over 3}\Big( 1 - \sum_{i=1}^{\infty} p_i^3 \Big)\]

And in the second case, she wins whenever the other two players play the same number

    \[p({\rm victory}) = \sum_{i=1}^{\infty} p_i^2\]

We can combine these and substitute in the solution p_i = A e^{-\alpha (i-1)} with A = (1-e^{-\alpha}), and solve for \alpha:

    \[\sum_{i=1}^{\infty} p_i^2 = {1 \over 3}\Big( 1 - \sum_{i=1}^{\infty} p_i^3 \Big)\]

and using the summation formula

    \[{A^2 \over 1 - e^{-2\alpha}} = {1 \over 3}\Big( 1 - {A^3 \over 1 - e^{-3\alpha}} \Big)\]

    \[3(1 - e^{-3\alpha})A^2 = (1 - e^{-3\alpha})(1 - e^{-2\alpha}) - A^3 (1 - e^{-2\alpha})\]

    \[3(1 - e^{-3\alpha})(1 - e^{-\alpha})^2 = (1 - e^{-3\alpha})(1 - e^{-2\alpha}) - (1 - e^{-\alpha})^3 (1 - e^{-2\alpha})\]

Expanding out and cancelling terms where possible, then taking out factors:

(1)   \begin{eqnarray*} 3 - 6e^{-\alpha} + 3e^{-2\alpha} - 3e^{-3\alpha} + 6e^{-4\alpha} -3e^{-5\alpha} \\ \quad = 3e^{-\alpha} - 3e^{-2\alpha} - 3e^{-3\alpha} + 3e^{-4\alpha} \end{eqnarray*}

    \[1 - 3e^{-\alpha} + 2e^{-2\alpha} + e^{-4\alpha} -e^{-5\alpha}= 0\]

    \[(1 - e^{-\alpha})^2 \cdot (e^{-3\alpha} + e^{-2\alpha} + e^{-\alpha} - 1) = 0\]

So e^{-\alpha} is the real root of the equation x^3 + x^2 + x = 1, which is given by x = 0.543689. A quick wikipedia search reveals that this is the reciprocal of something called the tribonacci constant, vital in the construction of the Snub Cube. I don’t know if this has some deeper resonance, but I’d love to hear from anyone who thinks it does! So, the full symmetric Nash Equilibrium in the 3-player, no upper bid limit case is

    \[p_i = (1 - e^{-\alpha})\cdot e^{-\alpha (i-1)}\]

with \alpha = 0.609378. Note that the (incorrect) form given in the linked-to website can also be expressed in the same form, but with \alpha = 0.693147.

 

4-Player Case

In the case of 4 players and above, the maximisation equation is

    \[p({\rm victory}) = \sum_{i=1}^{\rm UL} q_i\cdot \Big\{ \sum_{j=1}^{i-1} p_j^3 + 3\Big(\sum_{j=i}^{i-1} p_j^2\ \cdot \sum_{j=i+1}^{\infty} p_j \Big)+ \Big(\sum_{j=i+1}^{\infty} p_j\Big)^3 \Big\}\]

where the new term in the middle of the expression comes from the victory scenario in which two players both choose the same lower integer than our player and so are not unique, while the third player chooses one that is larger. This is the term that is missing in the paper linked to above that leads to the incorrect solution.

In the case that UL = 4, we have four equations and the normalisation condition to solve. The equations feature cubic equations, so the solution for these is required. It’s uncommon enough for me to have had to refer to wikipedia, the solution can be found here – we are saved some hassle because the relevant cubic equations don’t have a quadratic term.

Once again, a sketch of the solution in the unrestricted scenario is presented at the bottom of the post, but it seems to make very little difference whether the upper limit UL is set to 4 or infinity. In both cases, I find that

    \[p_1 = 0.447737\]

    \[p_2 = 0.424873\]

    \[p_3 = 0.125655\]

    \[p_4 = 0.001736\]

    \[p_n \simeq 0.0 \quad \forall n \textgreater 4\]

Why does the upper limit no longer make any difference? We only want to choose a higher number if there is a significant chance of the lower numbers being ‘crowded out’ by the other players. That is, we sometimes choose 4 because there is a small chance that the other three players will all select either 1, 2 or 3. Similarly, we would only choose 5 if there was a significant chance that 4 wasn’t high enough, because there was also a significant chance of all of the other three playing 4 – but from looking at the values, we see that p_4 is very small already, and (p_4)^3 is truly tiny. Consequently, in the general case p_n for n \textgreater 4 is going to be negligibly small.

 

N-player Case

The problem rapidly becomes hard to compute for large N, but there is a body of literature on the subject, in particular this 2010 paper points out the mistake in the paper I linked to before, and presents a general solution for N players. Note from their graphs that the probability of choosing a number greater than N is essentially 0 for higher numbers of players, so whether or not we impose this restriction doesn’t change the equilibrium materially.

Derivations

I hope you’ve enjoyed my take on this problem, the sketches of my method of solution for the 3- and 4-player cases are given below but can probably be skipped on a first reading.

In the three-player case, the Lagrange equations are

    \[\forall i:\quad\sum_{j=1}^{i-1} p_j^2 + \Big(\sum_{j=i+1}^{\infty} p_j\Big)^2 = \lambda\]

For i=1, and using normalisation, this gives

    \[\Big(\sum_{j=2}^{\infty} p_j\Big)^2 = (1-p_1)^2 = \lambda\]

Which means for i greater than 1 we have

    \[i \; \textgreater \; 1 : \quad \sum_{j=1}^{i-1} p_j^2 + \Big(1 - \sum_{j=0}^{i} p_j\Big)^2 = (1 - p_1)^2\]

and with a little re-arrangement

    \[\sum_{j=0}^{i} p_j = 1 - \sqrt{(1 - p_1)^2 - \sum_{j=1}^{i-1} p_j^2}\]

    \[p_i = 1 - \sum_{j=0}^{i-1} p_j - \sqrt{1 - 2p_1 - \sum_{j=2}^{i-1} p_j^2}\]

This gives a ‘step-up’ formula for the construction of later terms from the sum of earlier terms. An engineering-style solution is to write a script (or an excel spreadsheet) that calculates p_2 to p_{n} from an initial guess of p_1, and then varying the initial guess to satisfy the normalisation condition. Alternatively, we can show by induction that the expression above is satisfied for our solution p_i = A e^{-\alpha (i-1)}. First of all, assuming the relationship holds for p_i, lets see what it implies for p_{i+1} (for notational simplicity, I’m going to write e^{-\alpha} below as x

    \[{p_{i+1}\over p_i} = x = {1 - \sum_{j=0}^{i} p_j - \sqrt{1 - 2p_1 - \sum_{j=2}^{i} p_j^2} \over Ax^{i-1} }\]

    \[Ax^i = 1 - A {1-x^i \over 1-x} - \sqrt{1 - 2A - A^2 x^2 {1-x^{-2(i-1)}\over 1-x^2}}\]

and remembering that from our normalisation condition A = 1-x

    \[(1-x)x^i = x^i - \sqrt{1 - 2(1-x) - (1-x) x^2 {1-x^{-2(i-1)}\over 1+x}}\]

    \[x^{2(i+1)}(1+x) = (2x - 1)(1+x) - (1-x) x^2 (1-x^{-2(i-1)})\]

    \[x^{2i+2}+x^{2i+3} + x^{2i+1} - x^{2i} = 2x^2 + x - 1 - x^2 +x^3\]

    \[(x^{2i} - 1) (x^3+x^2+x - 1) = 0\]

so we see that the ratio demonstrated above satisfies the step-up equation for every p_i. The first term is a special case, so I show this separately

    \[{p_2 \over p_1} = x = {1 - p_1 - \sqrt{1 - 2p_1} \over p_1}\]

And now setting p_1 = A:

    \[x = {x - \sqrt{2x - 1} \over 1-x}\]

    \[x(1-x) - x = \sqrt{2x - 1}\]

    \[x^4 - 2x + 1 = 0\]

    \[(x-1)(x^3 + x^2 + x - 1) = 0\]

so we see that the first term is satisfied by the expression.

A similar expression for 4 players is given by the solution to

    \[\Big(1-\sum_{j=0}^{i} p_j\Big)^3 + 3p_1^2\cdot\Big(1-\sum_{j=0}^{i} p_j\Big) = (1-p_1)^3 - p_1^3\]

which gives

    \[p_i = 1 - \sum_{j=0}^{i-1} p_j - \sqrt[3]{-{q\over 2} + \sqrt{{q^2 \over 4} + p_1^6}} - \sqrt[3]{-{q\over 2} - \sqrt{{q^2 \over 4} + p_1^6}}\]

with

    \[q = (1-p_1)^3 - p_1^3 = 1 - 3p_1 + 3p_1^2 - 2p_1^3\]

I’ve not found an analytical solution for general p_n to this yet, and had to proceed by the variational technique discussed above, giving the answers in the body of the post. If you can solve this exactly for me I’d be very interested to hear!