Simple(?) game theory

Question

3 players are playing a game where they get to pick independently without knowing the other players picks one of 2 prizes (A,B) and the payout is (a,b) for the two prizes, divided by how many people picked the specific prize.

For example, if the prizes are (3,1) and 2 people picks A and 1 person picks B, the 2 people get 3/2 = 1.5 each and the third person gets 1 for himself.

In a zero-sum setting, if the prizes are (3,1), it would always be best to pick the first location, since you are guaranteed a prize of at least 1. If prizes are (2,1), this is also true, since no other player can beat that strategy. But, if prizes are (3,2), and two players use the strategy, the third player can do better by always picking the 2nd prize.

Is it possible to find an equilibrium for this particular problem, and does it generalize to further players and prizes? Does it fit into some standard theory?

Answer 1

This looks like a homework exercise on mixed strategy Nash equilibria.

My ASCII art skills are a little rusty, but let's write up a "nice" litte 2x2x2 cube:

              +--------------+-----------------+
C plays 3    /              /                / |
            +--------------+----------------+  | 
C plays 2  /              /                /|  / 
          +---------------+---------------+ | /| 
B plays 3 |  (3/2,3/2,2)  |    (1,3,1)    | |/ /
          +---------------+---------------+-/ /
B plays 2 |    (3,1,1)    | (2/3,2/3,2/3) | |/
          +---------------+---------------+-/
               A plays 3     A plays 2

Yes I know it's ugly as sin. Just sketch it on a piece of paper instead and fill it out with the payoffs. And leave a spot somewhere for the (A:3,B:2,C:3) corner.

Now let $p_X$ denote the propability that player $X$ plays $3$ and let $U_{X,y}$ denote the expeted payoff for player $X$ playing $y$

Because of the symmetries in this game, in a mixed strategy equilibrium $A$, $B$ and $C$ will all play the same mixed strategy, i.e. $p_A = p_B = p_C$.

$$ U_{C,3} = p_Ap_B\cdot 1 + p_A(1-p_B)\cdot\tfrac{3}{2} + (1-p_A)p_B\cdot\tfrac{3}{2} + (1-p_A)(1-p_B)\cdot 3 $$ $$ = p_A^2 + \tfrac{3}{2}p_A - \tfrac{3}{2}p_A^2 + \tfrac{3}{2}p_A - \tfrac{3}{2}p_A^2 + 3 -6p_A + 3p_A^2 = p_A^2 -3p_A + 3$$

$$ U_{C,2} = p_Ap_B \cdot 2 + p_A(1-p_B)\cdot 1 + (1-p_A)p_B\cdot 1 + (1-p_A)(1-p_B)\tfrac{2}{3} $$ $$ = \tfrac{2}{3}p_A^2 + \tfrac{2}{3}p_A + \tfrac{2}{3}$$

Then we just solve $U_{C,3} = U_{C,2}$ for $p_A$ and we get $\tfrac{1}{3}p_A^2 - \tfrac{11}{3}p_A + \tfrac{7}{3} = 0$ which has solutions $p_A = \frac{11 \pm \sqrt{93}}{2}$. Only the root corresponding to minus gives $p_A \in [0,1]$, so we conclude that the players should play $3$ with a probability of approximately $0.678$.

PS: I've given up on align. It just doesn't work. Ever.

PPS: There's almost certainly a mistake. This was a pretty quick and dirty computation.

Answer 2

The accepted answer correctly finds one equilibrium but overlooks three others: Any two players can choose $3$ while the other chooses $2$.

Answer 3

Is it possible to find an equilibrium for this particular problem, and does it generalize to further players and prizes? Does it fit into some standard theory?

Apologies for the late answer, but yes, it is a simple case of a congestion game.

In such games, we can show that best-response dynamics will always find a pure-strategy equilibrium using a potential function argument. For each prize $j$, let $B_j$ be the total prize awarded and $n_j$ be the number of agents who choose prize $j$, then the potential function is $$ \sum_j \sum_{i=1}^{n_j} \frac{B_j}{i} ~ = ~ \sum_j \left(B_j + \frac{B_j}{2} + \cdots + \frac{B_j}{n_j}\right). $$ We get this potential function by adding the players to the prizes one at a time, according to their strategies, and summing the prize that player would get if the game stopped there. (So the first person added to prize $j$ contributes $B_j$ to the potential, the next contributes $B_j/2$.)

Now one can see three properties:

• if any player is not best-responding, then if they switch to another prize that is a best-response (fixing all the other players), the potential increases. (We have subtracted off some $\frac{B_j}{n_j}$ and added on some $\frac{B_{j'}}{n_{j'}+1}$ to the potential; and by definition of a best-response, this has increased the potential.)

• there is a hard cap on the maximum value of the potential, for example, the number of players times the maximum prize.

• any switch from a non-best-response to a best-response increases the potential by more than some absolute constant, for example, the smallest difference between two prizes divided by the number of players.

So if we start with an arbitrary pure strategy profile and repeatedly pick any non-best-responding player and switch their strategy to a best response, we create a sequence of potential values each of which strictly increases by at least $\alpha$ and all of which lie below $\beta$, hence after a finite number of rounds the sequence stops and we have reached an equilibrium.