# Simple game-theoretical problem

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?

-

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

-
Thanks for the elaboration. Do you mean, that I may not be able to "improve" $(\frac13,\frac13,\frac13)$ to an equilibrium strategy? That is, there may not be any equilibrium strategy with an expected payoff of at least $8/27$? – Ilya Sep 22 '13 at 8:02
Exactly, there might not be an equilibrium with payoff of at least $8/27$. Just because there is a strategy profile where everyone is better off in expectation than in your equilibrium does not mean that there is no incentive for an individual player to deviate from that profile to be even better off. – Nameless Sep 22 '13 at 12:39
Just because there is a strategy profile where everyone is better off in expectation than in your equilibrium does not mean that there is no incentive for an individual player to deviate from that profile to be even better off. Do you mean that $(\frac13,\frac13,\frac13)$ is not the best response in case others play that as well? – Ilya Sep 22 '13 at 13:20
Yes, that is what I wrote above. If players 2 and 3 play the uniform strategy, then player 1 would deviate and play "1" with probability 1, and not mix uniformly as would be required for equilibrium. – Nameless Sep 22 '13 at 13:33

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.

-
I guess you meant: every finite symmetric game has a symmetric equilibrium. – memo Sep 22 '13 at 9:41
@memo What it means is that every finite game has an equilibrium invariant under all symmetries of the game. – Michael Greinecker Sep 22 '13 at 9:42
Sorry but I didn't quite get it :).. certainly there are finite games with only asymmetric equilibria (e.g. just construct a 2by2 game with strictly dominant actions). therefore, the first sentence is not true in this sense. – memo Sep 22 '13 at 9:51
@memo Such a game may have no proper symmetries, so that every strategyprofile will be invariant under the symmetries. A symmetry may for example exchange two players, the strategies of a player etc. when they are "essentially the same". This symmetries are formally defined in Nash's paper linked above. The more symmetric a game is, the more symmetries it will have. A symmetric equilibrium is one that preserves these symmetries and such an equilibrium always exists. Indeed, Theorem 2 of the paper says "Any finite game has a symmetric equilibrium point". – Michael Greinecker Sep 22 '13 at 10:01
i just say that your claim is not valid under the modern game theory terminology. it can be misinterpreted by many people, e.g. me:) – memo Sep 22 '13 at 10:25