Mixed Strategies PDF

Mixed Strategies The strategies we have been studying so far have been pure strategies In some games, it might instead be better to play a random or mixed strategy: “a probability distribution over (some or all of) a player’s available Matching Pennies Consider the following game...

Mixed Strategies The strategies we have been studying so far have been pure strategies In some games, it might instead be better to play a random or mixed strategy: “a probability distribution over (some or all of) a player’s available Matching Pennies Consider the following game of Matching Pennies Bill and Ben simultaneously show one of the faces of a coin: if the faces are the same, Ben wins both coins if the faces are different, Bill wins both coins Matching Pennies None of the circled payoffs coincide – where is the Nash equilibrium? Nash’s Theorem says “in every finite game, there will be at least one Nash equilibrium” Matching Pennies The Nash equilibrium will be where both Bill and Ben choose their actions with a probability of one half how to get there? there are two pure strategies - to play Head or to play Tail the mixed strategy for a player is a probability distribution (p,1-p) [p=prob(Head), 1-p=prob(Tail)] An Illustration of a Mixed Strategy Matching Pennies examples: (0,1) is the pure strategy of playing Tail (1,0) is the pure strategy of playing Head Left-Centre-Right Game examples: the three pure strategies are played with a mixed strategy (p,q,1-p-q) (1/3,1/3,1/3) attaches equal Identifying a Mixed Strategy How is a mixed strategy equilibrium arrived at? players are interested in maximising their expected payoffs Expected Payoffs Outcome Y has a 50/50 chance of yielding a payoff of 10, and the other half of the time the payoff is only 5 what is the expected payoff? Expected Payoffs Outcome Y has a 50/50 chance of yielding a payoff of 10, and the other half of the time the payoff is only 5 Expected payoff = (10. 0.5) + (5. 0.5) = 5 + 2.5 = 7.5 Nash Equilibrium and Mixed Strategies As in Lecture 1: A Nash equilibrium is a combination of mixed strategies so that each player’s mixed strategy is a best response to the other players’ mixed strategies. Bill’s and Ben’s Beliefs in Matching Pennies Bill thinks Ben will play Heads with a probability of p Bill thinks Ben will play Tails with a probability of (1-p) Ben thinks Bill will play Heads with a probability of q Ben thinks Bill will play Tails with a probability of (1-q) Identifying the Nash Equilibrium in Mixed Strategies Expected payoffs for Bill Head: p(-1) + (1-p)1 = 1- 2p Tail: p1 + (1-p) (-1) = 2p - 1 Identifying the Nash Equilibrium in Mixed Strategies Expected payoffs for Ben Head: q1 + (1-q) (-1) = 2q - 1 Tail: q(-1) + (1-q)1 = 1 - 2q Identifying the Nash Equilibrium in Mixed Strategies To find Bill’s equilibrium strategy, equate expected payoffs from playing Heads and Tails 1 – 2p = 2p –1 p = 1/ 2 thus, Bill is indifferent between playing either Heads or Tails whenever Ben plays Heads with probability 1/2 Identifying the Nash Equilibrium in Mixed Strategies If p ≠ 1/2 Bill would NOT be indifferent between choosing Heads or Tails Remember: Bill wins both - if p < 1/2 Bill will play Heads coins if the for example, when p = 0 faces are different Head: 1 – 2p = 1 AND Tail: 2p – 1 = -1 - if p > 1/2 Bill will play Tails p is the probability that for example, when p = 1 Ben plays Heads Head: 1 – 2p = -1 Identifying the Nash Equilibrium in Mixed Strategies and for Ben... Remember: Ben wins both 2q – 1 = 1 – 2q coins if the faces are the q = 1/ 2 same AND if q < 1/2 Ben will play Tails q is the if q > 1/2 Ben will play Heads probability that Bill plays Heads Identifying the Nash Equilibrium in Mixed Strategies Bill’s best response function for every p for every q response function Ben’s best NE There is only one Nash equilibrium Bill (q,1-q) = (1/2,1/2) Ben (p,1-p) = (1/2,1/2) Mixed strategies in the real world Game of poker: it does not make sense to play honest all the time. At least sometimes, a bluff is necessary. Penalty shootouts: both the shooter and the goalie randomize their chosen corners  Mixed strategies make sense in zero-sum competition games Battle of the Sexes Revisited Mixed strategies also make sense to achieve a third “fair” Nash equilibrium in a coordination game with two pure strategy Nash equilibria Battle of the Sexes Revisited Expected payoffs for Woman Opera: q2 + (1-q)0 = 2q Fight: q0 + (1-q)1 = 1 – q Battle of the Sexes Revisited Expected payoffs for Man Opera: p1 + (1-p)0 = p Fight: p0 + (1-p)2 = 2 – 2p Battle of the Sexes Revisited The Woman is indifferent between Opera and Fight when: 2q = 1 – q q = 1/ 3 if q1/3 the Woman will go to the Opera Battle of the Sexes Revisited The Man is indifferent between Opera and Fight when: p = 2 – 2p p = 2/ 3 if p2/3 the Man will go to the Opera Battle of the Sexes Revisited Woman’s best response function for every p response function Man’s best for every q Battle of the Sexes Revisited In this game there are three Nash equilibria: both the Man and the Woman attend the Battle of the Sexes Revisited In this game there are three Nash equilibria: both the Man and the Woman attend the Battle of the Sexes Revisited In this game there are three Nash equilibria: the Woman plays the mixed strategy 2 1