First consider only pure strategies (no randomization or mixed strategies). A strategy profile constitutes a Nash Equilibrium if for every for all . Which strategy profile constitutes a Nash Equilibrium in the following game?
y_{1} | y_{2} | y_{3} | |
x_{1} | 1,4 | 2,2 | 2,3 |
x_{2} | 3,1 | 1,5 | 4,1 |
x_{3} | 2,0 | 3,4 | 1,2 |
If Player 2 plays y_{2}, then the best response of player 1 is x_{3}. If player 1 plays x_{3}, then the best response of player 2 is y_{2}. This implies that strategy profile (x_{3},y_{2}) is a Nash Equilibrium. What if player 2 plays y_{1}, then player 1's best response is x_{2}, but for x_{2}, player 2's best response is y_{2}. Similarly if player 2 plays y_{3}, then player 1's best response is x_{2}, but for x_{2}, player 2's best response is y_{2}. Therefore is the only Nash Equilibrium strategy profile.
Consider the game of Matching Pennies.
Heads | Tails | |
Heads | -1, 1 | 1, -1 |
Tails | 1, -1 | -1, 1 |
Observe that there is no pure strategy equilibrium in the Matching Pennies.
When does (pure strategy) Nash Equilibrium exists?
(We are following the treatment in the book [#!OR94!#].)
First we need a few definitions and Kakutani's fixed point theorem.
For any player i, define the best response correspondence
such that for each
,
the set
A correspondence , where , the set is closed, has a closed graph if for any two converging sequences, and , where and for all k, then . The correspondence , where B is closed, is upper hemicontinuous if it has a closed graph and the images of the compact sets are bounded. A function defined on a convex set is quasi-concave if its upper contour set , for some value t is convex.
Here is the fixed point theorem due to Kakutani, and fir Illustration in one dimension see Figure 3.
Of course this theorem applies when the sets S_{i} are convex, but in our examples like Matching Pennies etc., the sets S_{i} are finite! OOPS! Before we do the proofs for this scenario - lets introduce mixed strategy Nash Equilibrium.
A mixed strategy profile constitutes a Nash Equilibrium if for every , , for all . For example, consider the Matching Pennies game again. This game has a mixed strategy equilibrium if each player chooses Heads or Tails with equal probability. Although this game didn't have a pure strategy Nash Equilibrium, but has a mixed strategy Nash Equilibrium! Here is the celebrated Nash Theorem!
Proof:
Let player i, has M pure strategies in the set S_{i}, i.e.,
|S_{i}|=M. Recall the simplex
,
representing the
probability vectors
In the following lemma we state an important property of mixed strategy Nash Equilibrium. It means that each player, given the distribution of strategies played by all his opponents, is indifferent among all pure strategies that (s)he plays. This lemma can be used to find the mixed strategy equilibrium.
Proof:
Necessary: Suppose that there is a strategy
in support of
,
but is not a best response to
.
Then by the
linearity of the utility function u_{i}, player i can increase
h(is/er) utility by transferring the probability from s_{i} to a
strategy, say s'_{i} that is a best response (i.e. player i would
have played s'_{i} in place of s_{i} and increased h(is/er) utility).
Sufficiency: Suppose that
is not a Nash Equilibrium. Then
there is a player who has a strategy
with
.
This implies
that there is a pure strategy
such that
.
But by assumption
for all
which are played with positive probabilities.
What are Nash Equilibriums for the following game?
Col-1 | Col-2 | |
Row-1 | 2,2 | 3,4 |
Row-2 | 1,3 | 5,1 |
Suppose Player 1 selects Row-1 and Row-2 with probability 1-p and
p respectively, i.e.
.
Then the utility of
Player 2, under strategy Col-1 and Col-2 should be the same, i.e.,
Similarly, if Player 2 selects Col-1 and Col-2 with probability
,
then
Therefore Nash Equilibrium is .
Here is a graphical way of computing Nash Equilibrium of games. In general let the game be given as follows:
1-q | q | |
1-p | a_{1},b_{1} | a_{2},b_{2} |
p | a_{3},b_{3} | a_{4},b_{4} |
Expected utility of the row player (Player 1) will be
First consider Player 1 (the row player). We can rewrite the utility
function u_{1} as a function of p, representing the equation of a
line
,
as follows.
The aim of the Player 1 is to maximize u_{1}. In our example
Similarly aim of the Player 2 is to maximize u_{2}. In our example
The plots are shown in Figure 4, and the intersection of the two graphs, where p=1/2 and q=1/3 is the Nash Equilibrium in this case. These graphs can be viewed as ``no regrets graphs'' of the two players. Given the strategy of a player, the best strategy of the other player is the corresponding point on the graph. For example, if Player 1 chooses p=.2, then the best strategy for player 2 is to choose q=1 (or Player 2 has no regrets in choosing q=1).