If player one knows (or has the prior belief) that player two is going to play a particular strategy \(\underline{y}\) (optimal or not) then what should player one do?

They should play the strategy \(\underline{x}\) that maximises the expected value \(\mathbb E_1(\underline{x},\underline{y})\). This is the best response strategy to \(\underline{y}\).

Similarly if player two believes that player one is going to play strategy \(\underline{x}\) then they should play the strategy \(\underline{y}\) the maximise the expected value \(\mathbb E_2(\underline{x},\underline{y})\). This is the best response strategy to \(\underline{x}\).

Note: The best response strategy may not be the one that player \(i\) would use if they assumed that player \(\bar{i}\) was playing optimally.

A mixed strategy \(\underline{x}^b\) for player \(1\) is a best response to the strategy \(\underline{y}=(y_1,\ldots,y_q)\) of player \(2\) if it satisfies \[\max_{\underline{x}\in \Delta S_1}\mathbb E_1(\underline{x},\underline{y})=\max_{\underline{x}\in \Delta S_1}\sum_{i=1}^{p}\sum_{j=1}^{q}x_ia_{ij}y_j=\mathbb E_1(\underline{x}^b,y).\]

Similarly, a mixed strategy \(\underline{y}^b\) for player \(2\) is a best response to the strategy \(\underline{x}=(x_1,\ldots,x_p)\) of player \(1\) if it satisfies \[\max_{\underline{y}\in\Delta S_2}\mathbb E_2(\underline{x},\underline{y})=\max_{\underline{y}\in\Delta S_2}\sum_{i=1}^{p}\sum_{j=1}^{q}x_ib_{ij}y_j=\mathbb E_2(\underline{x},\underline{y}^b).\]

Example 2.5

Consider the game

L M R
U \((1,-1)\) \((1,-1)\) \((1,-1)\)
M \((1,-1)\) \((2,-2)\) \((0,0)\)
D \((1,-1)\) \((0,0)\) \((2,-2)\)

Suppose that player 1 believes that player 2 will used the mixed strategy \((\frac{1}{4},\frac{1}{4},\frac{1}{2})\). What is their best response?

Example completed by hand in the lecture

We now introduce one of the best known concepts in game theory, which was introduced by the American mathematician John Nash (1928-2015; winner of the Nobel Prize for Economics).

We begin with the definition for pure strategies (for bimatrix games).

Definition 2.6

Suppose that the payoff matrices for a game for players 1 and 2 are \(A\) and \(B\) respectively. We call the pair of strategies \((i^*,j^*)\in S_1\times S_2\) a pure Nash equilibrium if \[a_{i^*j^*}\geq a_{ij^*}\] for all \(1\leq i\leq p\) and \[b_{i^*j^*}\geq b_{i^*j}\] for all \(1\leq j\leq q\).

In other words, \(i^*\) is a best response to \(j^*\) and \(j^*\) is a best response to \(i^*\).

Remark 2.7

  1. In a Nash equilibrium no player can gain any payoff if either one deviates from playing their part of the Nash equilibrium, assuming that the other player is playing their part of the equilibrium.

  2. A Nash equilibrium refers to a pair of strategies. It makes no sense to talk about a Nash equilibrium for a single player’s strategy.

  3. The term equilibrium is used because a player who knows that their opponent is playing the prescribed strategy will play optimally by following their part of the same strategy. Thus if each player believes that the other will play in the Nash equilibrium, there is no incentive for either player to deviate from this strategy.

To look for a Nash equilibrium in pure strategies is easy — we simply look for a payoff pair \((a_{ij},b_{ij})\) where \(a_{ij}\) is the largest number in its column of matrix \(A\) and \(b_{ij}\) is the largest number in its row of matrix \(B\).

Example 2.8

Consider the game

Strategy 1 Strategy 2 Strategy 3 Strategy 4
Strategy 1 \((5,6)\) \((8,3)\) \((7,5)\) \((3,5)\)
Strategy 2 \((3,7)\) \((3,1)\) \((4,4)\) \((7,8)\)
Strategy 3 \((0,4)\) \((5,2)\) \((5,6)\) \((3,3)\)

Example completed by hand in the lecture

As the last example showed, a game can have several Nash equilibria. We are not claiming that a Nash equilibria is necessarily the best pair of strategies that two players can pick, only that it is a stable pair of strategies.

There is no reason to assume that a game will always have a Nash equilibrium in pure strategies.

Example 2.9

Consider the game

Strategy 1 Strategy 2
Strategy 1 \((2,0)\) \((1,3)\)
Strategy 2 \((0,1)\) \((3,0)\)

This has no pure Nash equilibrium.

Definition 2.10

Suppose that the payoff matrices for a game for players 1 and 2 are \(A\) and \(B\) respectively. We call the pair of mixed strategies \((\underline{x}^*,\underline{y}^*)\in \Delta S_1\times \Delta S_2\) a mixed Nash equilibrium if \[\mathbb E_1(\underline{x}^*,\underline{y}^*)\geq \mathbb E_1(\underline{x},\underline{y}^*)\] for all \(\underline{x}\in\Delta S_1\) and \[\mathbb E_2(\underline{x}^*,\underline{y}^*)\geq \mathbb E_2(\underline{x}^*,\underline{y})\] for all \(\underline{y}\in\Delta S_2\).

Once again, if a player assumes that their opponent is playing in a Nash equilibrium, then a best response is also to play in the same equilibrium.

Example 2.11

Consider the game of Matching Pennies

Strategy 1 Strategy 2
Strategy 1 \((-1,1)\) \((1,-1)\)
Strategy 2 \((1,-1)\) \((-1,1)\)

Example completed by hand in the lecture

The last example is comforting, as the theory matches what we would expect from a common sense view of the game.