《The introduction of game theory(lecture notes 8)》由会员分享，可在线阅读，更多相关《The introduction of game theory(lecture notes 8)（22页珍藏版）》请在金锄头文库上搜索。
1、Mixed Strategy Nash EquilibriumMixed Strategy Nash Equilibrium A mixed strategy is one in which a player plays his available pure strategies with certain probabilities. Mixed strategies are best understood in the context of repeated games, where each players aim is to keep the other player(s) guessi
2、ng, for example: Rock, Scissors Paper. If each player in an n-player game has a finite number of pure strategies, then there exists at least one equilibrium in (possibly) mixed strategies. (Nash proved this). If there are no pure strategy equilibria, there must be a unique mixed strategy equilibrium
3、. However, it is possible for pure strategy and mixed strategy Nash equilibria to coexist, as in the Chicken game. Mixed Strategies: An ExampleConsider the matching pennies game:There is no (pure strategy) Nash equilibrium in this game. If we play this game, we should be “unpredictable.” That is, we
4、 should randomize (or mix) between strategies so that we do not get exploited.Mixed Strategies: An ExampleBut not any randomness will do: Suppose Player 1 plays .75 Heads and .25 Tails (that is, Heads with 75% chance and Tails with 25% chance). Then Player 2 by choosing Tails (with 100% chance) can
5、get an expected payoff of 0.751 + 0.25(-1) =0.5. But that cannot happen at equilibrium since Player 1 then wants to play Tails (with 100% chance) deviating from the original mixed strategy.Since this game is completely symmetric it is easy to see that at mixed strategy Nash equilibrium both players
6、will choose Heads with 50% chance and Tails with 50% chance.In this case the expected payoff. to both players is 0.51 +0.5(-1) = 0 and neither can do better by deviating to another strategy (regardless it is a mixed strategy or not).In general there is no guarantee that mixing will be 50-50 at equil
7、ibrium.Mixed StrategiesTennis MatchHere the payoffs to the Receiver is the probability of saving and the payoffs to the Server is the probability of scoring.Lets consider the potential strategies for the Server:If the Server always aims Forehands then the Receiver (anticipating the Forehand serve) w
8、ill always move Forehands and the payoffs will be (90,10) to Receiver and Server respectively.If the Server always aims Backhands then the Receiver (anticipating the Backhand serve) will always move Backhands and the payoffs will be (60,40).Mixed StrategiesHow can the Server do better than that? The
9、 Server can increase his performance by mixing Forehands and Backhands.For example suppose the Server aims Forehand with 50% chance and Backhands with 50% chance (or simply mixes 50-50). Then the Receivers payoff is* 0.590 + 0.520 = 55 if she moves Forehands and* 0.530 + 0.560 = 45 if she moves Back
10、hands.Since it is better to move Forehands, she will do that and her payoff will be 55. Therefore if the Server mixes 50-50 his payoff will be 45. (Note that the payoffs add up to 100). This is already an improvement for the Servers performance.Mixed StrategiesThe next step is searching for the best
11、 mix for the Server. How can he get the best performance?Suppose the Server aims Forehands with q probability and Backhands with 1-q probability. Then the Receivers payoff is q90 + (1-q)20 = 20 + 70q if she moves Forehands and q30 + (1-q)60 = 60 - 30q if she moves Backhands.The Receiver will move to
12、wards the side that maximizes her payoff. Therefore she will moveForehands if 20 + 70q 60 - 30q,Backhands if 20 + 70q 100q = 40 = q = 0.4.In order to maximize his payoff. the Server should aim Forehands 40% of the time and Backhands 60% of the time. In this case the Receivers payoff will be 20 + 700
13、.4 = 60 -300.4 = 48.In other words if the Server mixes 40-60 then the Receivers payoff will be 48 whether she moves Forehands or Backhands (or mixes between them). Therefore the Servers payoff will be 100-48 = 52.Mixed StrategiesMixed StrategiesNext lets carry out a similar analysis for the Receiver
14、.If the Receiver does not mix, then the Server will aim the other side.Suppose the Receiver moves Forehands with p probability. Then her payoff isp90 + (1-p)30 = 30 + 60p if the Server aims Forehands andp20 + (1-p)60 = 60 - 40p if the Server aims Backhands.The Server will aim towards the side that m
15、inimizes the Receivers payoff. Therefore he will aimForehands if 30 + 60p 60 - 40p, andeither one if 30 + 60p = 60 - 40p.Mixed StrategiesThat is, the Receivers payoff is the smaller of 30+60p and 60-40p. The Receiver should equate 30+60p and 60-40p so as to maximize her payoff:30 + 60p = 60-40p = 10
16、0p = 30 = p = 0.3.In order to maximize her payoff the Receiver should move Forehands 30% of the time and Backhands 70% of the time. In this case the Receivers her payoff will be 30 + 600.3 = 60 -400.3 = 48. Therefore the Servers payoff will be 100-48 = 52.Therefore the mixed strategy:Receiver: 0.3F
17、+ 0.7B, andServer: 0.4F + 0.6B is the only one that cannot be “exploited” by either player. Hence it is a mixed strategy Nash equilibrium.Mixed StrategiesMixed Strategies Important Observation: If a player is using a mixed strategy at equilibrium, then he/she should have the same expected payoff fro
18、m the strategies he/she is mixing. We can easily find the mixed strategy Nash equilibrium in 2 2 games using this observation.Mixed StrategiesMixed StrategiesMixed StrategiesMixed StrategiesMixed StrategiesMixed StrategiesMixed StrategiesReferencesEquilibrium points in N-Person Games, 1950, Proceedings of NAS. The Bargaining Problem, 1950, Econometrica. A Simple Three-Person Poker Game, with L.S. Shapley, 1950, Annals of Mathematical Statistics. Non-Cooperative Games, 1951, Annals of Mathematics. Two-Person Cooperative Games, 1953, Econometrica.
