Game theory

Basic process for finding Nash equilibria

The easiest way to find Nash equilibria in a 2×2 game is to cover each column and row in turn and ask: “If player 1 knows that player 2 will choose X, what is player 1’s best choice?” over and over again. Mark player 1’s choice with a circle and mark player 2’s choice with a dot. Any cells that have both a circle and a dot are equilibria.

Here’s what that looks like in an invisible hand game. Anil and Bala need to choose what they’re going to grow. Their payoffs (measured in utils) for each of their choices are listed in this matrix:

Bala
Rice Cassava
Anil Rice 1, 3 2, 2
Cassava 4, 4 3, 1

To start, cover up the column where Bala chooses to grow cassava. If Anil assumes that Bala chooses to grow rice, what’s his best option? Anil would get 1 util from growing rice, and 4 from growing cassava. Cassava is best, so put a circle there.

Bala
Rice Cassava
Anil Rice 1, 3
Cassava ⭕ 4, 4

Next, cover the column where Bala chooses to grow rice. If Anil assumes that Bala chooses to grow cassava, what’s his best option? Anil would get 2 utils from growing rice, and 3 from growing cassava. Cassava is the best again, so put a circle there.

Bala
Rice Cassava
Anil Rice 2, 2
Cassava ⭕ 3, 1

Regardless of what Bala chooses to do, Anil’s best choice is always to grow cassava, so he’ll do that. That’s a pure, dominant strategy.

Let’s go through the same process for Bala. Cover up the row where Anil chooses to grow cassava. If Bala assumes that Anil chooses to grow rice, what’s his best option? Bala would get 3 utils from growing rice, and 2 from growing cassava. Rice is the best option, so put a dot there.

Bala
Rice Cassava
Anil Rice 🔵 1, 3 2, 2
Cassava

Next cover up the row where Anil chooses to grow rice If Bala assumes that Anil chooses to grow cassava, what’s his best option? Bala would get 4 utils from growing rice, and only 1 from growing cassava. Rice is again his best option, so put a dot there.

Bala
Rice Cassava
Anil Rice 🔵
Cassava ⭕ 🔵 4, 4 ⭕ 3, 1

Bala’s best option—regardless of what Anil chooses to do—is to grow rice, so that’s what he’ll do.

Phew. Finally we can look at it all together. Here’s a summary of the different possible choices and responses:

  • Best response for Anil if Bala chooses Rice = Cassava
  • Best response for Anil if Bala chooses Cassava = Cassava
  • Best response for Bala if Anil chooses Rice = Rice
  • Best response for Bala if Anil chooses Cassava = Rice

There’s a circle and a dot in the (4, 4) / (Cassava, Rice) square, which means that’s the Nash equilibrium. That’s the situation that both players will naturally settle on without any outside communication, given the structure of the payoffs in the game.

Bala
Rice Cassava
Anil Rice 🔵 1, 3 2, 2
Cassava ⭕ 🔵 4, 4 ⭕ 3, 1

Mixed strategies

When there is no single Nash equilibrium in a game, players have to engage in a mixed strategy and attempt to predict what the other players will do. The choices they make are determined by the payoffs in the game, since it is generally more likely that players will choose strategies that maximize their payoffs. You need to calculate two things to do this:

  1. Calculate the expected utility for each choice for each player and find the probability cutoff for each choice.
  2. Calculate the expected payoff for each player.

These calculations involve actual math, unlike the more simpler approach of covering rows and columns and drawing circles and dots.

There are a bunch of helpful external resources and examples of how to do this, including these. You should check these out if you’re interested in this game theory stuff:

Let’s do this with the Bach or Stravinksy game that we used in session 3:

Friend 2
Chinese Italian
Friend 1 Chinese 2, 1 0, 0
Italian 0, 0 1, 2

Step 1: Find the equilibria

  • Best response for Friend 1 if Friend 2 chooses Chinese = Chinese
  • Best response for Friend 1 if Friend 2 chooses Italian = Italian
  • Best response for Friend 2 if Friend 1 chooses Chinese = Chinese
  • Best response for Friend 2 if Friend 1 chooses Italian = Italian

The game has two Nash equilibria, so it has a mixed strategy.

Step 2: Calculate the expected utility for each choice for each player

We calculating the expected utility for each choice by assuming some probability for Friend 1’s choices (\(p\), \(1 - p\)) and for Friend 2’s choices (\(q\), \(1 - q\)):

Friend 2
Chinese Italian
\(q\) \(1 - q\)
Friend 1 Chinese \(p\) 2, 1 0, 0
Italian \(1 - p\) 0, 0 1, 2

To find the expected utility for a choice, add the utility × probability for each choice in the row (or column, for Player 2). Thus,

\[ \begin{aligned} EU_{\text{Friend 1, Chinese}} &= 2q + 0(1-q) =& 2q \\ EU_{\text{Friend 1, Italian}} &= 0q + 1(1-q) =& 1 - q \\ EU_{\text{Friend 2, Chinese}} &= 1p + 0(1-p) =& p \\ EU_{\text{Friend 2, Italian}} &= 0p + 2(1-p) =& 2 - 2p \end{aligned} \]

With these formulas, you can then determine \(q\) and \(p\) by setting the expected utilities for each player equal to each other and solving for the variable:

\[ \begin{aligned} 2q &= 1 - q & p &= 2 - 2p \\ 3q &= 1 & 3p &= 2 \\ q &= \frac{1}{3} & p &= \frac{2}{3} \end{aligned} \]

Friend 1’s best response is determined by what Friend 2’s \(q\) is in real life:

\[ \text{Best response}_{\text{Friend 1}} = \left \{ \begin{aligned} &\text{Chinese } & \text{if } q < \frac{1}{3} \\ &\text{Italian } & \text{if } q > \frac{1}{3} \\ &\text{indifferent } & \text{if } q = \frac{1}{3} \\ \end{aligned} \right \} \]

Similarly, Friend 2’s best response is determined by what Friend 1’s \(p\) is in real life:

\[ \text{Best response}_{\text{Friend 2}} = \left \{ \begin{aligned} &\text{Chinese } & \text{if } p > \frac{2}{3} \\ &\text{Italian } & \text{if } p < \frac{2}{3} \\ &\text{indifferent } & \text{if } p = \frac{1}{3} \\ \end{aligned} \right \} \]

Step 3: Calculate the expected payoff for each player when playing the mixed strategy

The expected payoff is the utility × probability for each cell, added together. First, calculate the joint probabilities for each cell by multiplying the row and column probabilities:

Friend 2
Chinese Italian
\(q = \frac{1}{3}\) \(1 - q = \frac{2}{3}\)
Friend 1 Chinese \(p = \frac{2}{3}\) \(\frac{2}{3} \times \frac{1}{3} = \frac{2}{9}\) \(\frac{2}{3} \times \frac{2}{3} = \frac{4}{9}\)
Italian \(1 - p = \frac{1}{3}\) \(\frac{1}{3} \times \frac{1}{3} = \frac{1}{9}\) \(\frac{1}{3} \times \frac{2}{3} = \frac{2}{9}\)

Then multiply each probability by the payoff and add all the cells together:

\[ \begin{aligned} EP_{\text{Friend 1}} &= (2 \times \frac{2}{9}) + (0 \times \frac{4}{9}) + (0 \times \frac{1}{9}) + (1 \times \frac{2}{9}) =& \frac{2}{3} \\ EP_{\text{Friend 2}} &= (1 \times \frac{2}{9}) + (0 \times \frac{4}{9}) + (0 \times \frac{1}{9}) + (2 \times \frac{2}{9}) =& \frac{2}{3} \end{aligned} \]

The expected payoff for each player in the mixed strategy is \(\frac{2}{3}\), which is less than what either player would make if they coordinated on their least preferred outcome. That is, it’s better for Friend 1 to compromise and eat Italian and get 1 unit of utility rather than gamble on the mixed strategy.