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?
If Player 2 plays y2, then the best response of player 1 is x3. If player 1 plays x3, then the best response of player 2 is y2. This implies that strategy profile (x3,y2) is a Nash Equilibrium. What if player 2 plays y1, then player 1's best response is x2, but for x2, player 2's best response is y2. Similarly if player 2 plays y3, then player 1's best response is x2, but for x2, player 2's best response is y2. Therefore is the only Nash Equilibrium strategy profile.
Consider the game of Matching Pennies.
|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
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 Si are convex, but in our examples like Matching Pennies etc., the sets Si 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!
Let player i, has M pure strategies in the set Si, i.e.,
|Si|=M. Recall the simplex
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.
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 ui, player i can increase
h(is/er) utility by transferring the probability from si to a
strategy, say s'i that is a best response (i.e. player i would
have played s'i in place of si 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?
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
Therefore Nash Equilibrium is .
Here is a graphical way of computing Nash Equilibrium of games. In general let the game be given as follows:
Expected utility of the row player (Player 1) will be
First consider Player 1 (the row player). We can rewrite the utility
function u1 as a function of p, representing the equation of a
The aim of the Player 1 is to maximize u1. In our example
Similarly aim of the Player 2 is to maximize u2. 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).