Nash Equilibrium in Game Theory

Continuing on from last week’s post on the different strategies in game theory, I will talk about the most important equilibrium in game theory: the Nash Equilibrium. (I am still referencing Essentials of Game Theory). I must point out that the Nash Equilibrium only gives the most optimal solution profile in non-cooperative games. In cooperative games, the optimal payoff for all players may be greater than that predicted by the Nash Equilibrium. This is the case because the Nash Equilibrium finds the most optimal strategy profile for a player given that the player knows nothing about the other players’ strategies. In other words, the player has to be prepared for the worst possible outcome and be ready to pick a strategy (pure or mixed) that provides the best possible outcome in all scenarios.

  1. Nash Equilibrium definition:
    To make what I said in words clearer and more mathematically rigorous, let me define some variables. As with my previous posts, let’s define s_i to be player i‘s strategy. Then let s_{-i} to be the strategy profile s without s_i. In other words, s_{-i} = (s_1, ..., s_{i-1}, s_{i+1}, ..., s_n). A strategy profile s=(s_1^*, ..., s_n^*) is a Nash Equilibrium if for all players, i, their chosen strategy, s_i^{*}, allows them to each gain a utility, u_i where u_i(s_i^{*}, s_{-i}) \geq u_i(s_i, s_{-i}) for all s_i \epsilon S_i. Put simply, a strategy profile is a Nash Equilibrium if every player choses a strategy that puts them in the best position possible given a competitive game where every player is trying to obtain the most optimal utility. Note that a player’s strategy in a Nash Equilibrium may be either mixed or pure.
  2. Prisoner’s Dilemma:
    Let’s look at a couple of examples of Nash Equilibria in games. The book provides a neat example of pure and mixed strategy Nash Equilibria in a game called the Battle of the Sexes. However, I’ll talk about another example called the Prisoner’s Dilemma to distinguish between the two different kinds of equilibria more clearly. To see a description of the Prisoner’s Dilemma, look at its Wikipedia page, which provides a very good general overview. In the example of the Prisoner’s Dilemma below (Figure 1), the only pure Nash Equilibrium that exists is “Defect, Defect.” You may argue that the payoff is maximal for both player if they both cooperate. However, “Cooperate, Cooperate” is not a Nash Equilibrium because both players given that the other player chooses to “cooperate” can improve their payoff if they switch their strategy to “defect.” Thus, given s_i^*="cooperate" and s_i \epsilon S_i where S_i = \left\{cooperate, defect\right\}, u_i(s_i^*, s_{-i}) \not\geq u_i(s_i, s_{-i}) for all s_i \epsilon S_i. This is because if player i chooses to cooperate and the other player also chooses to cooperate, then u_i(s_i^*, s_{-i}) = 3. However, player i could easily improve her position if she chooses to defect u_i(s_{defect}, s_{-i}) = 5. Thus, u_i(s_i^*, s_{-i}) \not\geq u_i(s_i, s_{-i}) in the case that s_i^* = cooperate and s_{-i} = cooperate and s_i = defect. The only Nash Equilibria is “Defect, Defect” because neither player may improve his or her position when this is the case.
  3. Figure 1

    Figure 1: From Wikipedia, the only pure strategy Nash Equilibrium is “Defect, Defect.”

  4. Mixed Strategy Nash Equilibria:
    So far, we have only looked at an example of a pure strategy Nash Equilibrium. However, mixed strategy Nash Equilibria also exist in many games. In the Prisoner’s Dilemma, there is no other mixed strategy besides the “Defect, Defect” strategy previously mentioned. Take my word for now, and I will offer a more rigorous explanation at the end of this section. For now, let’s consider another game that does have a mixed strategy Nash Equilibrium. The game we will now look at is called the Matching Pennies game (Figure 2). Computing a mixed strategy equilibrium is generally a very complicated task (which I will attempt to explain in my next blog post). However, in this case, we know the strategy profiles of both players, and we know that there are only two players in the game. Let’s suppose player i randomizes her actions by turning the penny to heads with probability p and to tails with probability (1-p). Thus, given that player i turns the penny to either side randomly, player j must be indifferent between heads or tails given that he has no idea what player i will do. Given these two pieces of information, we know that to satisfy the Nash Equilibrium principle, the utility player j receives for either action must be the same. We, therefore, get the following equations and result:

    u_j(heads) = u_j(tails)

    p - (1-p) = -p + (1-p)
    p = 0.5.

    If player i plays heads with 50% probability, player j will be indifferent between playing either heads or tails. This logic also applies in reverse order where player j plays heads with probability 50%. If both players play heads with 50% probability, then both players will be indifferent between playing either heads or tails. This constitutes as a Nash Equilibrium because there is no other move that the players can make to maximize their utility given that they do not know the other player’s strategy.

    From Wikipedia, the mixed strategy that is a Nash Equilibrium is to play heads and tails with equal probability.

    Figure 2: From Wikipedia, the mixed strategy that is a Nash Equilibrium is to play heads and tails with equal probability.

    1. Explanation of the lack of a mixed strategy equilibrium in the Prisoner’s Dilemma:

      Going back to the assumption I proposed in the beginning of this section, the Prisoner’s Dilemma has no other Nash Equilibrium besides “Defect, Defect.” In other words, there is no mixed strategy equilibrium in the Prisoner’s Dilemma*. Using the same technique described above, assume prisoner i chooses to cooperate with probability p and defect with probability (1-p). Then, prisoner j would be indifferent between either cooperating or defecting. Thus, writing out the equations, we obtain:

      u_j(cooperate) = u_j(defect)

      3*p + 0*(1-p) = 5*p + 3*(1 - p)

      p = 3

      Wait a minute, probability can never be greater than one, but p = 3 > 1. This is an invalid result, so we conclude that there is no mixed strategy that will make player j indifferent between cooperating and defecting. Thus, the only valid Nash Equilibrium is “Defect, Defect” in the Prisoner’s Dilemma. (For extra practice, think about the Prisoner’s Dilemma in the general case without any numbers.)

      *Please note: I hesitate to use the phrase “no mixed strategy equilibrium” because a equilibrium where one strategy is played with 100% probability is still considered a mixed strategy. What I mean to say is that there are no pure mixed strategy equilibrium, but I didn’t say it at the risk of confusion with pure strategy equilibriums.

    At the end of this post, I leave you with this important theorem:

    (Nash, 1951): Every game with a finite number of players and action profiles has a Nash Equilibrium.

    Perhaps sometime this week or sometime next week, I’ll attempt to explain the proof for this theorem, as well as, how to find the mixed strategy of a game with more than two players (the general case). This might be the one post that breaks my promise of a simple and easy to understand applied math blog.

    Advertisements
This entry was posted in Game theory, Math and tagged , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s