MA3662 Lecture 5
Definition 2.12
A game is called finite if each player has a finite number of possible pure strategies.
Clearly any bimatrix game is finite, as there are only finitely many rows and columns.
The following fundamental result is known as the Nash existence theorem, and will be relied upon henceforth.
Theorem 2.13
Every finite game has a Nash equilibrium.
Thus every finite game has at least one stable pair of strategies from which neither player would deviate if they believed that the other was following it.
The proof of this theorem relies on a deep result known as Brouwer’s Fixed-Point Theorem. Full details can be found in Chapters 6 and 7 of Game Theory Basics by von Stengel.
Let us now return to the classic example of the Prisoner’s Dilemma.
Example 2.14
Consider the Prisoners’ Dilemma
| Confess | Deny | |
|---|---|---|
| Confess | \((-5,-5)\) | \((0,-10)\) |
| Deny | \((-10,0)\) | \((-1,-1)\) |
Example completed by hand in the lecture
In this game the best outcome for the pair of players would be if both did not confess. But this solution is unstable as each of the pair could benefit by defecting.
A Nash equilibrium occurs when they both confess. This is a stable solution as neither benefits by defecting from this pair of strategies, but they end up with a worse outcome!
We saw that dominance could be used to simplify a game. But how does this relate to finding Nash equilibria? Removing dominated strategies may seem obvious, but do we loose potential Nash equilibria, or gain ones that do not exist in the original game?
The following discussion is based on Section 3.5 of von Stengel, where further details (and proofs) can be found.
Example 2.15
Consider the game given by the bimatrix
| C | D | |
|---|---|---|
| C | \((1,3)\) | \((1,3)\) |
| D | \((0,0)\) | \((2,2)\) |
Example completed by hand in the lecture
In the last example we saw that weak dominance for player 2 removed a Nash equilibrium (and indeed, the one with a higher payoff for them than in the remaining Nash equilibrium).
Example 2.16
Consider the game
| L | M | R | |
|---|---|---|---|
| U | \((1,0)\) | \((3,1)\) | \((1,1)\) |
| M | \((1,1)\) | \((3,0)\) | \((0,1)\) |
| D | \((2,2)\) | \((3,3)\) | \((0,2)\) |
Example completed by hand in the lecture
Fortunately no more serious problems can arise, by the following basic result.
Theorem 2.17
Suppose that we use weak dominance to simplify a game \(G\) to a new game \(H\). Then any Nash equilibrium of \(H\) is a Nash equilibrium of \(G\).
Suppose that we use strict dominance to simplify a game \(G\) to a new game \(H\). Then the Nash equilibria of \(H\) are precisely the same as the Nash equilibria of \(G\).
The above theorem justifies the dominance principle that we stated earlier, and explains why we restricted to strict dominance when stating the principle.
The first part of the theorem shows that using weak dominance is fine if we only want to find some solutions of the original game.
To finish this Chapter we will introduce a fundamental result that will be very useful when we are looking for Nash equilibria.
As usual we will denote the payoff matrices for players 1 and 2 by \(A\) and \(B\) respectively.
We will sometimes denote by \(i\) the \(i\)th pure strategy for either player. So, for example, instead of writing \[\underline{x}= (0,0,1,0)\] we may just denote this strategy by the number \(3\).
We can now state our basic result, which is sometimes referred to as the best response condition or the equilibrium theorem but which we will refer to as the equality of payoffs theorem.
Theorem 2.18: (The Equality of Payoffs Theorem)
Consider a bimatrix game with \(p\times q\) payoff matrices \(A\) and \(B\), and let \[u = \text{max}\{\mathbb E_1(i,\underline{y}): 1 \leq i\leq p\}\quad\text{and}\quad v = \text{max}\{\mathbb E_2(\underline{x},j): 1\leq j\leq q\}.\] Then
- \(\underline{x}\) is a best response to \(\underline{y}\) if and only if \(x_i=0\) whenever \[\mathbb E_1(i,\underline{y})<u.\]
- \(\underline{y}\) is a best response to \(\underline{x}\) if and only if \(y_j=0\) whenever \[\mathbb E_2(\underline{x},j)<v.\]
A proof of this result can be found in Section 6.4 of von Stengel.
Example 2.19
We revisit 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)\) |
and 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
In this example the maximum value \(u\) was only attained for a single choice of \(i\), and so the best response was a pure strategy.
In general there may be multiple components where the maximum value is attained, and in such cases we will have infinitely many choices of \(\underline{x}\).
Thus if we are only looking for a best response to a given strategy then we now have an elementary method for finding them.
For a Nash equilibrium life is not so straightforward, as both strategies are initially unknown, and each of them has to satisfy the conditions of the Equality of Payoffs Theorem with respect to the other.
However, we will see that this theorem is still a valuable tool in finding such equilibria.