What is the optimal strategy of guessing a number where closest without going over wins?

Question

When a group of people need to decide a winner or leader between them, one approach would be that a random hidden integer is chosen with uniform distribution on $\{0, 1, ..., n\}$ and all $p$ participants publicly choose a number.

Then, the number is revealed and the participant who was the closest wins.

---

A variant of this happens when we introduce what is informally known as the 'price is right' rule, where you only win when you aren't going over (so the one who is the closest from the bottom wins).

---

Now I am having trouble formalizing the optimal strategy for games like this in my head, and even more so for how the rules would change when the 'price is right' variant is introduced.

Answer 1

An interesting problem!

The case of $p = 2$ is fairly straightforward. For simplicity, suppose that each player must choose a real number in $[0, 1]$ (ignoring integer issues) and let $x_1 \in [0, 1]$ and $x_2 \in [0, 1]$ denote the choices of the first and second player. Now, for any number $x_1$ that the first player chooses, the second player will either choose $x_1 - \epsilon$ if $x_1 < 1/2$; otherwise, $x_1 + \epsilon$ if $x > 1/2$. Effectively, the first player is dividing an interval into two parts, and the second player is choosing the larger of the two sub-intervals. Knowing this, the first player will then choose $x_1 = 1/2$ and so both players have a $50\%$ chance of winning.

[Of course, this is analysis is not entirely rigorous since there is no optimal $\epsilon$. While this technical problem can be solved by discretising the choice set, I consider the continuous model to ease the analysis in the case of $p = 3$.]

The case of $p = 3$ is a bit more tricky. To solve it, begin by considering the decision of the third player and let $x_1$ and $x_2$ denote the choices of the first and second players. The choices $x_1$ and $x_2$ effectively cut the interval into three segments. Let $\Delta \equiv |x_1 - x_2|$ denote the distance between the first and second choices. The third player can then choose between one or two different strategies:

1. If $\Delta$ is large, then they will choose some $x_3 \in (x_1, x_2)$. That way, they will capture half of $\Delta$. To make the analysis tractable, I will assume (a little arbitrarily) that they will choose the midpoint, i.e. $x_3 = (x_1 + x_2)/2$.
2. If $\Delta$ is small, then they will go either side of $(x_1, x_2)$. For instance, if $x_1 < x_2$ (an assumption we will henceforth maintain without any real loss of generality), then they will either choose $x_2 + \epsilon$ (capturing all the interval to the right of $x_2$) or otherwise choose $x_1 - \epsilon$ (capturing all the interval to the left of $x_1$).

What do I mean by `large' and 'small'? Let $\text{M} = \text{max}\{x_1, |1 - x_2|\}$ denote the largest distance either $x_1$ or $x_2$ to the edge. (For example, if $x_1 = 0.2$ and $x_2 = 0.9$, then $x_2$ is closer to the edge and so $\text{M} = 1 - 0.9 = 0.1$). If the third player follows strategy $1$, then their payoff is $1/2 \Delta$. If they follow strategy $2$, then their payoff is $\text{M}$. Thus, they choose strategy $1$ if $1/2 \Delta \geq M$; and choose strategy $2$ otherwise. [Note that I am assuming that ties are broken in favour of strategy $1$.]

Given this, how will the second player choose? Given any $x_1$, the second player can either force the third player into the middle ($x_3 \in (x_1, x_2)$ or force them to choose strategy $2$. Which is better?

Key insight: It must be optimal for the second player to make the third player indifferent between these two strategies.

Heuristic Proof: If the third player strictly preferred one strategy, say strategy (1), then the second player could slightly change their strategy without inducing the third player to swap to strategy 3 in a way that improves the second player's payoff. [Draw a picture if you are not convinced!]

By indifference, we have $1/2 \Delta = M$. In other words, given any $x_1$, the second player chooses $2/3$ of the way between $x_1$ and the endpoint of $1$. [Again, a picture may help.] For example, if $x_1 = 0.1$, then $x_2 = 0.1 + (2/3)0.9 = 0.7$ so that $\Delta = 0.7 - 0.1 = 0.6$ and $\text{M} = 1 - 0.7 = 0.3 = 2\text{E}$.

Finally, let us consider the choice of the first player. They anticipate the subsequent players to choose fairly mechanically. For any $x_1 \leq 1/4$, the second player will choose $x_2 = x_1 + (2/3)(1-x_1)$ and the third player will choose the midpoint between $x_1$ and $x_2$. From this, it is easy to see that the first player should choose $x_1 = 1/4$. (Choosing $x_1 = 3/4$, thereby inducing the 'mirror image' scenario, would be equally good).

Bottom line: In the case of $p = 3$, equilibrium strategies induce the first player to choose $1/4$, the second to choose $3/4$ and the third to choose $1/2$. Clearly, the player who chooses last is at a disadvantage.

Answer 2

Just to make things a bit easier, assume the initial random number is a random real number between 0 and 1. If there are $p$ players, then I think one Nash Equilibrium strategy is for the $i$th player to choose the number $\frac1{2p} + \frac{i-1}p$ with $i=1,2,\ldots p$.

With "The Price is Right" rule, I think that one Nash Equilibrium strategy is for the $i$th player to choose the number $\frac{i-1}p$.

Answer 3

I tried to analyze the game, but, according to antkam’s guesses, the analysis became more and more technical, so I decided to stop it. My findings are below.

To make the game possible we assume that $n+1\ge p$.

To be involved we start from the case $p=2$. Suppose that the first player chose a number $n_1$. Cleary, then an optimal choice for the second player is to choose either $0$ or $n_1+1$ (if the respective choice is possible). Then he wins with a probability $\tfrac{n_1}{n+1}$ in the first case and $\tfrac{n-n_1}{n+1}$ in the second case. This observation makes his optimal choice clear.

Assume that the second player plays optimally. This is an essential assumption, because if the second player decide to minimize the winning probability of the first player (to $\tfrac 1{n+1}$) by all means, his strategy can be to choose $n_1+1$, if $n_1<n$, and $0$, otherwise.

Now we have that if the first player chooses a number $n_1<\tfrac n2$, he wins with a probability $\tfrac 1{n+1}$, that is only when his guess is exact. If he chooses $n_1>\tfrac n2$ then he wins with a probability $\tfrac{n-n_1}{n+1}$. If he chooses $n_1=\tfrac n2$ then he wins with a probability $\tfrac{1}{n+1}$, when the second player chooses $n_1+1$, and with a probability $\tfrac{n}{2n+2}$, when the second player chooses $0$.

Similarly we can try to consider the general case $p>2$. Assume first that all players but the last already chose their numbers $n_1<n_2<\dots n_{p-1}$. Then an optimal choice for the last player is to choose one of numbers $0,n_1+1,n_2+1,\dots, n_{p-1}+1$ (if the respective choice is possible). The respective winning probabilities are $$\tfrac {n_1}{n+1},\tfrac {n_2-n_1-1}{n+1},\dots \tfrac {n_{p-1}-n_{p-2}-1}{n+1}, \tfrac{n-n_{p-1}}{n+1}.$$ This observation makes his optimal choice clear.

Similarly to the case $p=2$, we assume that each player tries to win by all means and knows that all other players behave similarly. Assume that the first $p-2$ players already chose their numbers $n_1<n_2<\dots n_{p-2}$. Due to the optimality of the last player strategy, we have that if the $(p-1)$-th player chooses a number ....

Answer 4

Not a full solution. I am merely attempting to "fully solve" the $p=2, 3$ cases, just to highlight the general technique and also technical issues you can run into right away.

I will consider $8$ versions of this problem:

• $p = 2$ vs $p = 3$

• the range of choices (also the random number) is discrete $\{1, 2, \dots, n\}$ vs continuous $[0, 1]$.

• the Original Winning Rule "OWR" (closest wins) vs the Price-is-Right "PIR" variant winning rule (closest-and-not-exceeding wins).

  • In the discrete case, the OWR rule can have ties; in this case I assume the win is split.

  • Also, in the discrete case, the PIR rule can have a guess exactly equaling the random number; in this case I assume the guesser wins (i.e. disqualification only happens when the guess is strictly $>$ the random number).

Terminology:

• The first, second, third player will be called X, Y, Z respectively (and I will alternate pronouns).

• Their choices are $x,y,z$ respectively.

• Their payoffs (with a split win counting as half a win) are $p_x, p_y, p_z$ respectively.

---

p=2, continuous, OWR: $x$ divides the $[0,1]$ interval into two sides and clearly Y should choose the bigger side and be as close to $x$ as possible. I.e.:

• If $x > 1/2$, then $y = x - \delta$ for some tiny $\delta > 0$.

• If $x < 1/2$, then $y = x + \delta$ for some tiny $\delta > 0$.

• If $x = 1/2$, then either choice above is fine.

The technical issue is that this does not give an "optimal" strategy, since $\delta$ can be arbitrarily small. In other words, no matter how small $\delta$ Y chooses, there is a better strategy for Y with an even smaller $\delta$. If we hand-wave a bit, the game is "solved", but if we are nit-picky, there is technically no optimal solution (hence also no Nash equilibrium). All the continuous variants run into this technical issue, and I will not mention it again. I will also use $\delta$ to refer to any arbitrarily small positive number.

Anyway, given the above, and backtracking, X can see that $p_x = \min(x, 1-x)$, i.e. X always gets the smaller side in the end. So the optimal for X is $x^* = \arg \max_x p_x = 1/2$.

---

p=2, continuous, PIR: First lets visualize the PIR rule. Basically given any $x,y$, each player captures the range from their choice to the next higher choice (or to $1$ if there is no higher choice).

Again $x$ divides the interval, but this time X won't win at all for $r < x$. Y can capture the lower range by $y=0$ or can capture the upper range by $y = x + \delta$.

I will adopt the usual assumption that: Y's only aim is to maximize her payoff, and does not care one bit what happens to X. Then Y's strategy is:

• If $x > 1/2$, then $y = 0$.

• If $x < 1/2$, then $y = x + \delta$.

• If $x = 1/2$, then $y = 0$ -- note that in this case Y's payoff is $1/2$, whereas if Y chose $y= x+ \delta$ then her payoff is slightly smaller at $1/2 -\delta$.

X's payoff is a bit more complicated:

• If $x \ge 1/2$ then $p_x = 1 - x$.

• If $x < 1/2$ then $p_x = \delta$.

But this doesn't change the optimal $x^* = 1/2$.

---

p=2, discrete, OWR: Once we're in discrete-land, effectively we have $\delta = 1$ (the smallest positive value), but the exact integers might matter. Reminder: my range is $\{1, 2, \dots, n\}$ which I find to be more natural than the OP's $\{0, 1, \dots, n\}$.

• If $n$ is odd, then $x^* = (1+n)/2$ i.e. the median number. Y can choose either $y = x \pm 1$ and it doesn't matter to X. I.e. X's optimal is unique and Y's is not. Also $p_x = (n+1)/2n, p_y = (n-1)/2n$.

• If $n$ is even then $x^* =$ either of the two median numbers work just as well. Y will then choose the bigger side. I.e. X's optimal is not unique and Y's is. Also $p_x = p_y = 1/2$.

---

p=2, discrete, PIR: Here we run into another fun technical issue, and it only happens when $n$ is odd!

• If $n$ is even then $x^* = 1 + n/2$, i.e. the higher of the two median numbers. Y will choose the lower half with $y=0$. For the optimal we have $p_x = p_y = 1/2$. (Note that $x= n/2$ does not work for X, as Y will choose $y=x+1$ and leave X with almost nothing.)

• If $n$ is odd: this is the interesting case. One would think X simply chooses the median $(1+n)/2$, but in this case Y has two equal choices $y = x \pm 1$. It is widely accepted that Y will make an optimal choice without reference to X's payoff, but what if there are multiple optimal choices which pays the same for Y but differently for X, as is the case here?

  • If we further assume Y will pick either equally-optimal-for-her choices randomly, then suddenly X's payoff is much smaller, because there is a $1/2$ chance Y will pick $y=x+1$ and leave X with almost nothing. So X's optimal is now $x^* = 1 + (1+n)/2$, i.e. one above the median number, in order to incentivize Y to pick the lower range.

  • Alternatively, we can model a credible threat, which I informally define as Y promising that in case of equal choices she will pick the one that hurts X the most. Since Y is just maximizing for herself, the threat is indeed credible in a sense -- it doesn't hurt Y at all to hurt X. So again, X needs to choose $x = 1 + (1+n)/2$ so the threat does not come into play.

The technical issue is that either further assumptions above is just that: a further assumption. I am not a game theory expect but AFAIK there is no generally accepted further assumption in this case. Now in this specific example the two further assumptions result in the same optimum, but they can have different optima in other examples.

---

p=3, continuous, OWR: As usual we have to work backwards. Given $x,y$, let $a = \max(x,y), b= \min(x,y)$, so as far as Z is concerned there are three ranges: $[0,b), (b,a), (a,1]$. Z's choices are:

• capture the entire lower range with $z = b - \delta$,

• or, capture the entire upper range with $z = a + \delta$,

• or, capture half the middle range with any $z \in (b, a)$

  • Note that Z is capturing $(\frac{b+z}2, \frac{z+a}2)$ which has size $\frac{a-b}2$ for any $z \in (b,a)$. So again the optimal is not unique.

So e.g. if the ranges are of sizes $0.2, 0.5, 0.3$ in that order, then Z will capture the entire upper $0.3$ range. ...

---

Before I continue (probably tonight or tomorrow or even the weekend) -- is this kind of analysis interesting to people?