Before I construct the strategy, I want to point out a somewhat neat theorem about the game and discuss an incorrect strategy. One idea is just to pick 1 with probability 1/2 and 2 with probability 1/2, since this is a zero sum game, every wins zero on average if they all do the same thing. Seems like a reasonable idea, but you can beat this by always picking 3. There is a 50% chance that the other players will pick the same number as eachother and you just win, the rest of the time, they pick different numbers and you lose. Thus your average winnings are 0.5x$2-0.5x$1, which is more than zero. This hints at an interesting idea, there is no number that is the largest number players can pick in a symmetric equilibrium. Suppose each player has a strategy S which is a series of probabilities P(n) for picking number n. Suppose there is a largest number K that S suggest you will ever pick (that is, P(n)=0 for n>K). Now, you generate your random number, and it says you should play K. I say you should play K+1. If K was going to win, so will K+1 (it would only win if the opponents were about to pick the same number). But it is possible K+1 will win and K will not (specifically if both other opponents pick K). Thus it is advantageous for you to change strategy S into a slightly different strategy, and so it is not an equilibrium.
Alright, to find the actual solution, let us assume that we are going to search for a symmetric Nash equilibrium. I think there is a theorem that symmetric games always have at least one symmetric equilibrium, but I cannot find any such theorem online. Anyway, we must find a list of P(n) that is the chance a player picks n, and we know there is no K such that P(n)=0 for n>K (that doesn't actually help us, but I think its neat).
OK, suppose we had P(n), what properties would it have? First of all, no player would do any better by deviating from the strategy. Let us also assume that they will do no worse (so we get equalities instead of inequalities). Second, we know that when everybody plays P(n) they have expected winnings of zero (just by symmetry and it being a zero sum game).
Suppose 2 of the players are playing the strategy suggested by P(n) and the third player decides to write down 1. What are his expected winnings? They are:
2(1-P(1))2-P(1)(1-P(1))-P(1)(1-P(1))
That is, he wins $2 if both opponents do not pick 1, and he loses $1 if one picks 1 while the other does not and this can happen two ways. In other cases he wins nothing and loses nothing. Setting this to zero (player 3 does no worse to unilaterally change his strategy), we see that P(1)=1/2.
What happens if he instead changes his strategy to just write down 2? His expected winnings are now given by
2P(1)2+2(1-P(1)-P(2)2)-2P(1)(1-P(1))-2P(2)(1-P(1)-P(2))
That is, he wins $2 if both opponents pick 1 or if they both pick numbers larger than 2. He loses $1 if one opponent picks 1 and the other does not (can happen in two ways) and he loses $1 if one opponent picks 2 and the other picks larger than 2 (can happen 2 ways). Setting this to zero and solving for P(2) we get P(2)=1/4.
This suggests P(n)=1/2n is the solution we are looking for. This can be confirmed by looking at what happens if the third player writes down A. His winnings are
2Σn to A-1 P(n)2+2(1-Σn to AP(n))2-2Σn to A P(n)(1-Σj to nP(j))
Σn to A means sum n from 1 to A. These terms can be explained the same as the A=2 case as before. Subbing in P(n)=1/2n we find that this equals zero for all A and so this strategy is a Nash equilibrium.
Actually, this strategy is quite easy to perform in real life, you simply flip a coin until it comes up heads and write down the number of flips it took, this gives the correct P(n).
For the case where ties result in everybody losing their dollar, the game is more difficult, since it is no longer zero sum, there is a chance of money exiting the system. You can try something similar where your expected winning each round is the sum of P(n)3 (which is a third of the total amount of money lost each round, on average), but then you cannot iteratively solve for each P(n) as we did, you just have infinitely many coupled equations.
The 4 player game (with friendly ties) also has this problem, since a player playing 1 wins if nobody else picked 1, but also does not lose if the other two players pick the same number, so the sum over P(n)2 shows up in your first equation. The 4 player game also has annoying Nash equilibria like two players pick 1 and the other two pick 2.
Anyway, enough about that game.
No comments:
Post a Comment