Simple game-theoretical problem

Question

I have a confusion regarding the following problem:

Suppose there are three players, and each of them has to pick a number out of $1,2$ or $3$. If there is a player who picked a unique number (others picked different numbers), then the player with the smallest unique number wins. If there are no unique choices, nobody wins.

Clearly, the problem is symmetric. As a simple guess, each of the player can play a strategy of randomly (uniformly) picking any of the numbers, and win with the probability $\frac8{27}$. On the other hand, perhaps that is not the optimal choice of the strategy - I would expect the optimal probability of winning to be $\frac13$. However, when I am computing best responses I obtain that the optimal mixed strategy is $(\frac{\sqrt3}{2+\sqrt3},\frac1{2+\sqrt3},\frac1{2+\sqrt3})$ whose payoff is $\frac{4}{7+4\sqrt3}<\frac8{27}$, which clearly cannot be the case for the optimal strategy. While computing it I made an assumption that the optimal strategy is the same for all players due to the symmetry - is such assumption incorrect?

Answer 1

You have found a mixed strategy equilibrium, so your approach must have been correct. The following is elaboration.

Here's how you would usually proceed: postulate there is a symmetric mixed strategy equilibrium, find a candidate (e.g., yours) and show that playing this strategy is best response if both of the other players are playing this strategy.

Note that in a mixed strategy equilibrium, all players must be indifferent between choosing any of the pure strategies (this is why we can mix). If we weren't indifferent, the best response would be to play the pure strategy that gives highest expected payoff with probability 1.

We can show your candidate is a symmetric mixed strategy equilibrium. To show this, suppose the winner gets a payoff of 1, the rest 0. In case of draw, everyone gets 0. We are player 1, both of the others play your candidate. What is the expected payoff from playing "1"?

$$E_1=1\cdot\left[\underbrace{\frac{1}{(2+\sqrt{3})^2}}_{\text{both }3}+\underbrace{\frac{1}{(2+\sqrt{3})^2}}_{\text{both }2}+\underbrace{\frac{1}{(2+\sqrt{3})^2}}_{\text{one }2\text{, other }3}+\underbrace{\frac{1}{(2+\sqrt{3})^2}}_{\text{reversed}}\right]=\frac{4}{(2+\sqrt{3})^2}.$$ The expected payoff from playing "2" is $$E_2=1\cdot\left[\frac{1}{(2+\sqrt{3})^2} +\frac{3}{(2+\sqrt{3})^2}\right]=\frac{4}{(2+\sqrt{3})^2}.$$ Similarly, the expected payoff from playing "3" is also $$E_3=1\cdot\left[\frac{1}{(2+\sqrt{3})^2} +\frac{3}{(2+\sqrt{3})^2}\right]=\frac{4}{(2+\sqrt{3})^2}.$$ Thus, we as player 1 are indifferent between any of the three pure strategies and thus it is (one of the infinitely many) best responses to play your candidate as a response to the other 2's playing this candidate. Therefore, this is an equilibrium.

There are others, which might yield different payoffs. The interesting thing is indeed that the payoff is less than $1/3$. But this is very plausible if you think about it. There are realizations (e.g., when all play "1" or all play "3") where nobody gets a positive payoff. And if there is a positive payoff of 1, then only one player receives it by the rules of the game. Hence, in expectation everyone gets less than $1/3$.

Finally, I think you made a mistake in computing the payoff. In equilibrium, this is $\frac{4}{(2+\sqrt{3})^2}$, which is indeed smaller than $8/27$. So yes, every player would be better off if everyone played the uniform mixed strategy. But this is not an equilibrium. When you calculate the expected payoffs assuming both other players use the uniform strategy, you will get $E_1=4/9$, $E_2=2/9$, $E_3=2/9$. Hence, we would best respond by always playing "1"! Hence, this is not an equilibrium. I suppose this is one of the examples where strategic play rules out certain Pareto superior distributions (in expectation). The strategy that makes everyone better off does not rule out that an individual might be even better off by deviating from it.

(In fact, everyone would be even better off if they took turns playing "1", and never choose "1" together.)

Answer 2

Every finite game has a symmetric equilibrium in mixed strategies, as has already be shown by Nash.

Since this game is symmetric, in any symmetric equilibrium, every player must get the same expected payoff and win with the same probability. But this probability must be strictly smaller than $1/3$, since in a symmetric equilibrium, there is always a positive probability of there being no unique smallest number being chosen.

There are asymmetric equilibria too. For example, pick one of the players and make her always play $1$. Make the others play $2$, $3$, or any combination thereof. It is clear that nobody has an incentive to deviate. $1$ wins, so she likes it. The only way to keep her from winning is for another player to choose $1$ too, but that player will gain nothing from it.

Now in a symmetric stratgy profile, all players have the same payoff and the only thing that can lower the payoffs are full ties, in which case nobody wins ex post. So the socially optimal symmetric profile is the one where the chance of perfect tiees is the smallest. This is indeed everyone playing uniformly over $\{1,2,3\}$. But in an equilibrium, players care only about their own payoff. In the socially optimal symmetric strategy, it may happen that all players play different numbers and it is as likely in that case to be the player with the largest number as the player with the smallest number. Socially it does not matter, but individually, a player would much prefer to be the smallest player, so it should not be surprising that there exists an individually beneficial deviation.