Transcription
Chapter 11.‐ Mixed‐Strategy NashEquilibrium As we have seen, some games do not have a Nashequilibrium in pure strategies. However, existence of Nash equilibrium wouldfollow if we extend this notion to mixedstrategies. All we need is for each player’s mixed strategy tobe a best response to the mixed strategies of allother players.
Example: Matching pennies game.‐ We saw beforethat this game does not have a Nash equilibrium inpure strategies. Intuitively: Given the “pure conflict” nature of thematching pennies game, letting my opponent knowfor sure which strategy I will choose is neveroptimal, since this will give my opponent the abilityto hurt me for sure. This is why randomizing is optimal.
Consider the following profile of mixedstrategies:ଵଵ ଵଶ ଶଵଶandଶଵ ଵଶ ଶ Note thatଵଶ And therefore,ଵଵଶଵଶଵଶ
Since payoffs are symmetrical, we also haveଶଵଶ Note that: Each player is indifferent between his twostrategies (H or T) if the other player randomizesଵ ଵ(both H and T yield aaccording to ଶ ଶpayoff of zero). Both strategies are bestଵ ଵ.responses to ଶ ଶଵ ଵଶ ଶ Playing the mixed strategy alsoyields a payoff of zero and therefore is also aଵ ଵbest response to .ଶ ଶ
Therefore, if the other player chooses H or Twith probability ½ each, then each player isperfectly content with also randomizingbetween H and T with probability ½. This constitutes a Nash equilibrium in mixedstrategies.
Definition: Consider a (mixed) strategy profileଵଶ where is a mixed strategy for player . Theprofile is a mixed‐strategy Nash equilibrium ifand only if playing is a best response to ି .That is: ି ି for each Fact #1 about mixed‐strategy Nash Equilibrium: Amixed strategy is is a best response to ି onlyif assigns positive probability exclusively tostrategies that are best‐responses to ି .
Facts about mixed‐strategy Nash equilibria:1. In any mixed‐strategy Nash equilibriumଵ ଶ , players assign positiveprobability only to rationalizable strategies. Thatis, only if is rationalizable.2. In any mixed‐strategy Nash equilibriumଵ ଶ , the mixed strategy assignspositive probability exclusively to strategies that are best‐responses to ି . That is:If , then it must be that: ି ି for every .
3. In any mixed‐strategy Nash equilibriumଵ ଶ , each player is indifferent between allthe strategies that he can play with positiveprobability according to . That is, for each: for all ି such that ି and Using these facts, we can characterize a step‐by‐stepprocedure to find mixed‐strategy Nash equilibria in twoplayer games (things get a bit more complicated ingames with three or more players).
Procedure for finding mixed‐strategyequilibria in discrete, two‐player games:1. Step 1: Find the set of rationalizablestrategies in the game using iterateddominance.2. Step 2: Restricting attention to rationalizablestrategies, write equations for each player tocharacterize mixing distributions that makeeach player indifferent between the relevantpure strategies.3. Step 3: Solve these equations to determineequilibrium mixing distributions.
Example: A lobbying game.‐ Suppose two firmssimultaneously and independently decide whetherto lobby (L) or not lobby (N) the government inhopes of trying to generate favorable legislation.Suppose payoffs are:
This game has two pure‐strategy Nashequilibria: Question: Does it also have a mixed‐strategyNash equilibrium? Since this game has only two players and twostrategies, this question is easy to answer. Step 1: Note that both strategies arerationalizable for each player.
Step 2: With only two players and twostrategies, a profile of mixed strategies ଵ ଶ isa Nash equilibrium if and only if:I. Player 1 is indifferent between L and N whenplayer 2 uses ଶ .II. Player 2 is indifferent between L and N whenplayer 1 uses ଵ . That is, if and only if ଵ ଶ are such that:ଵଶଵଶandଶଵଶଵ
Since each player has only two strategies (L and N), anymixed strategy is fully described by ୧ ��ଵଵଶଶଵଵ
In any mixed‐strategy Nash equilibrium, wemust have ଵଶଵଶ . That is:ଶଶ This will be satisfied if:ଶ And we also must haveThat is:ଵଶଵଶଵ This will be satisfied if:ଵଵ.
Therefore, this game has a mixed‐strategyequilibrium ଵ ଶ , where:ଵandଶ This example also illustrates that some gamesmay have Nash equilibria in pure strategies ANDalso in mixed strategies.
Example: A tennis‐service game.‐ Considertwo tennis players. Player 1 (the server) must decide whether toserve to the opponent’s forehand (F), center(C) or backhand (B). Simultaneously, Player 2 (the receiver) mustdecide whether to favor the forehand, centerof backhand side.
Suppose payoffs are given by: We begin by noting that this game does nothave any pure‐strategy Nash equilibrium.
To see why, note that best‐responses are givenby: So there is no pair of mutual best‐responses inpure strategies.
Question: Find the mixed‐strategy Nashequilibria in this game. Step 1: Using iterated dominance, find the setof rationalizable strategies R.– To find the reduced game ଵ– Note first that all three strategiesarebest‐responses for player 2, so they will allsurvive.– For player 1,are best‐responses. And wecan show easily that is dominated by a mixedstrategy between. From here, we have:ଵ
(cont )– To find ଶ , we note that in the reduced game ଵ ,the only dominated strategy is , for player 2.Player 1 does not have any dominated strategy inଵ. Therefore,ଶ– It is easy to verify that there are no dominatedstrategies in ଶ . Therefore the game cannot bereduced any further and we have
The set of rationalizable strategies is:21CBC0, 53, 2B3, 22, 3 To find mixed‐strategy Nash equilibria, we needto look for mixing distributions:ଵଵଵଶଶଶ(where each player randomizes only between “C”and “B” and play “F” with zero probability) suchthat both players are indifferent between C and B.
That is, we must have:ଵଶଵଶandଶଵଶଵ Expected payoffs are given �ଵଵଵଵ
Therefore,andଵଶneed to satisfy:ଶଶandଵଵ This yields:ଶଵସandଵଵସ
Therefore, the mixed‐strategy Nash equilibriumin this game is given by the mixing distributions:ଵandଶ
Example: Find the set of Nash equilibria (pureand mixed) in this game:
We begin with the pure‐strategy equilibria:
Mixed‐strategy equilibria: first, using iterateddominance we look for the set of rationalizablestrategies R– Player 1: “M” is a best response to “X” and “Y”, while“U” is a best response to “Z”. The strategy “D” isdominated by “U”.– Player 2: “Z” is a best response to “U”, “X” is a bestresponse to “M” and “D”.– We need to check if “Y” is a dominated strategy. Sameprocedure we followed in Chapter 6 shows that it isNOT a dominated strategy.– Therefore:ଵ
Matrix form of the reduced gameଵis:– Player 1 has no dominated strategies in the reducedgame given by ଵ .– For Player 2, “Y” is dominated by “Z” in the reducedgame given by ଵ .– Therefore, ଶ.
ଶ. Reduced game:– Player 1 has no dominated strategies in the reducedgame given by ଶ .– Player 2 has no dominated strategies in the reducedgame given by ଶ .– Therefore, no further reduction can be done and we. Therefore,have ଶ
Focusing on the rationalizable strategies R, wenow need to find well‐defined mixingprobabilitiesଵଵଶଶଵଶsuch that both players are indifferent betweentheir actions (X and Z for player 2, and U andM for player 1). That is:ଵଶଵଶandଶଵଶଵ
The reduced game R looks like this:21XZU2, 04, 2M3, 42, 3 From here we have:ଵଶଶଶଶଵଶଶଶଶ And:ଶଵଵଵଵଶଵଵଵଵ
Both players will be indifferent between theirrelevant strategies if and only if:(for player 1)ଶଶ(for player 2)ଵଵ The first condition will hold if and only ifଶ And the second condition will hold if and onlyifଵ
Therefore, this game has one mixed‐strategyNash equilibrium where players randomizeaccording to the distributions:ଵଶ
Mixed‐strategy Nash Equilibrium in ContinuousGames: As in discrete games, the key feature isthat players must randomize in a way that makesother players indifferent between their relevantstrategies. Example: Bertrand competition with capacityconstraints. Consider a duopoly industry of a homogenousgood with two firms who compete in prices. Suppose the market consists of 10 consumers,each of which will purchase one unit of the good.Suppose that each consumer is willing to pay atmost 1 for the good.
For simplicity, suppose the production cost iszero for both firms. If this setup fully describes the model, then it isa very simple case of Bertrand competition. Aswe learned previously, the equilibrium priceswould be those that yield a profit of zero. Since production cost is zero, this mean that theNash equilibrium prices would be:and ଶଵas we learned previously, this would be theUNIQUE Nash equilibrium in the game.
Suppose now that both firms have a capacityconstraint. Specifically, suppose each firm canproduce at most eight units of the good. This will change the features of the modeldrastically: Now the firm with the cheapest pricecannot capture the entire market because of thecapacity constraint. Conversely, the firm with the highest price can stillcapture two consumers. As a result, the Nash equilibrium properties of thismodel will change. As we will see, it will no longerhave an equilibrium in pure strategies. Instead, itwill have a unique equilibrium in mixed strategies.
With capacity constraints, the game no longerhas an equilibrium in pure strategies: We beginby noting that by setting the highest possible, firm ensures itself a profit of atprice ( least 2 (since at the very least it will sell twounits due to the capacity constraint of theopponent). Can this be a Nash Suppose ଵଶequilibrium? No, because it would be better foreither firm to undercut the other firm’s price byan infinitesimal amount. This will always yield ahigher payoff than choosing the same price asthe opponent.
Suppose ଵ. Can this be a Nashଶequilibrium? It used to be the Nashequilibrium without capacity constraints, butnot any more. Why? Because if my opponentsets a price of zero, my best response now isto set a price of 1. This will ensure me aprofit of 2 instead of 0, which is what Iwould obtain if I set my price to zero. Therefore, combining the two cases above,there cannot be a Nash equilibrium in purestrategies where ଵଶ
Can there be a pure‐strategy Nash equilibrium inwhich ? First note that if one firm chooses a price higher than the other firm, thenthe only rational price to choose is the highestpossible price (since you would have two captivecostumers). That is, if in equilibrium, then it must bethe case that But if , it is notoptimal for firm to charge strictly less than 1.Firm would like to keep raising byinfinitesimal amounts to become closer andcloser to 1. So the best response by would notbe well‐defined.
Therefore since there is no pure‐strategy Nashequilibrium where ଵଶ and there is no pure‐strategy Nash equilibrium where , weconclude that this game does not possess a pure‐strategy Nash equilibrium. How about a mixed‐strategy Nash equilibrium? Notice that the strategy space is continuous,which makes the problem a bit “trickier”. Still, wecan describe the mixed‐strategy Nash equilibriumusing the same principle as in discrete games: Inequilibrium, both players must be indifferentbetween all their relevant strategies.
– To find 6, we note that in the reduced game 5, the only dominated strategy is , for player 2. Player 1 does not have any dominated strategy in 5. Therefore, 6 – It is easy to verify that there are no dominated strategies in 6. Therefore the
