Unformatted text preview:

STANFORD UNIVERSITY Winter 2001DEPT. OF MANAGEMENT SCIENCE MS&E 241AND ENGINEERING ECONOMIC ANALYSISPRINCIPLES OF GAME THEORYLECTURE 3 MIXED STRATEGIESThe strategies {si ∈ Si} are referred to as Player i's pure strategies, i.e., a particular si is playedwith probability one. A mixed strategy for Player i is a probability distribution over (some or allof) the strategies in Si. See, e.g., Luenberger, p. 268, Varian, p. 264.[3.1] ExampleIn the Matching Pennies game, for instance, Si consists of the two pure strategies,Heads and Tails. A mixed strategy for Player i is the probability distribution (q, 1-q), where q isthe probability of playing Heads, 1-q the probability of playing Tails, and 0 ≤ q ≤ 1. The mixedstrategy (0, 1) is simply the pure strategy Tails; likewise, the mixed strategy (1, 0) is the purestrategy Heads.There is no Nash Equilibrium in this game if we restrict players to pure strategies.[3.2] ExampleIn the following game (payoff diagram on next page), Player 2 has pure strategies,L, M, and R. Here a mixed strategy for Player 2 is the probability distribution (q, r, 1-q-r), whereq is the probability of playing L, r the probability of playing M, and 1-q-r the probability ofplaying R. We require 0 ≤ q ≤ 1; 0 ≤ r ≤ 1; and 0 ≤ q+r ≤ 1. The mixed strategy (1/3, 1/3, 1/3), forinstance, puts equal probability on L, M and R.The pure strategies are simply the limiting cases of the players' mixed strategies. Player2's pure strategy, L, for instance, is the mixed strategy (1, 0, 0).Player i may in reality follow a pure strategy, but it may be modelled as a mixed strategyto reflect uncertainty in the mind of Player j about which element of Si Player i will actuallyplay. Player i's strategy may not really be random but appear to be random to Player j. Evenexplicitly random actions are not uncommon. The IRS randomly selects which tax returns toaudit, and telephone companies randomly monitor their operators' conversations to make surethey are polite to customers.Player 2LeftMiddleRightPlayer 1UpDown1, 01, 20, 10, 30, 12, 0[3.3] Definition A mixed strategy for Player i is a probability distribution over (some or allof) the strategies in Si. We refer to the strategies in Si as Player i's pure strategies. In thestrategic-form game, G = {S1, ..., Sn; U1, ..., Un}, suppose Si = (si1, si2, ..., siK). Then a mixedstrategy for Player i is a probability distribution pi = (pi1, pi2, ..., piK), where pik is the probabilitythat Player i will play strategy sik, for k = 1, 2, ..., K; 0 ≤ pik ≤ 1 for k = 1, ..., K; and pi1 + pi2,+ ... + piK = 1.[3.4] Calculating a Mixed-Strategy Nash Equilibrium [Varian, pp. 267, 268]Player 2Player 12, 10, 00, 01, 2TBLRLet (pT, pB) be the probabilities with which Player 1 plays Top and Bottom, respectively, anddefine (pL, pR) similarly. Then Player 1's problem is:Max pT[2pL + 0pR] + pB[0pL + 1pR]Subject to pT + pB = 1pT ≥ 0pB ≥ 0The expected payoff to Player 1 can be written: π1 = 2pTpL + (1 - pL)(1 - pT)= pT(3pL - 1) + (1 - pL)⇒ pT* = \B\LC\{(\A\HS5\AL( 0\, if pL < 1/3, 1\, if pL > 1/3, any ∈ [0\, 1]\, if pL = 1/3))Likewise, the expected payoff to Player 2 can be written, π2 = pL(3pT - 2) + 2(1 - pT)⇒ pL* = \B\LC\{(\A\HS5\AL( 0\, if pT < 2/3, 1\, if pT > 2/3, any ∈ [0\, 1]\, if pT = 2/3))These are the Best response Functions for Players 1 and 2, respectively, namely p*T(pL) andp*L(pT). The Nash Equilibria are determined by their intersection, as demonstrated in the figurebelow.PT12/301/31PLBold line: p*L(pT)Dotted line: p*T(pL) From the figure it follows that there are three Nash Equilibria:1. Two pure strategy equilibria, (B, R), and (T, L), corresponding to the points (pT = 0, pL = 0) and (pT = 1, pL = 1), respectively.2. One mixed strategy equilibrium, namely (pT = 2/3, pL = 1/3).This game has several economic interpretations. One example is the choice of anindustry-wide standard when two firms have different preferences but both want a commonstandard so as to encourage consumers to buy the product. A second is the choice of language ina contract when two firms want to formalize a sales agreement even though they prefer differentterms. Each prefers its own terms above its opponent's, but nevertheless prefers an agreement onits opponent's terms to failing to reach an agreement.[3.5] Dominance, Mixed Strategies, and Nash EquilibriumWe have defined Si as the set of strategies available to Player i, and the combination of strategies(s*1, ..., s*n) as the Nash equilibrium if, for each player i, s*i is Player i's best response to thestrategies of the n-1 other players:Ui(s*1, ... s*i-1,s*i, ,s*i+1 ... s*n) ≥ Ui(s*1, ... s*i-1, si, s*i+1, ... , s*n) ∀ si ∈ Si.By this definition, there is no Nash Equilibrium in the following (Matching Pennies) game if werestrict ourselves to pure strategies:Player 2HTHTPlayer 1-1, 11, -11, -1-1, 1Recall1. If a strategy si is strictly dominated, then there is no belief that player i could hold about thestrategies the other players will choose such that it would be optimal to play si.The converse is also true, if we allow for mixed strategies:2. If there is no belief that player i could hold about the strategies the other players will choosesuch that it would be optimal to play si, then there exists another strategy that strictly dominatessi. [3.6] Example The following examples show that statement (2) would be false if werestricted attention to pure strategies. In the game below, a given pure strategy may be strictlydominated by a mixed strategy, even if the pure strategy is not strictly dominated by any otherpure strategy. Suppose only pure strategies were allowed. Then B would never be chosen by Player 1,regardless of her beliefs of Player 2's strategy. If she believed Player 2 would play L, then T isher optimal response, while M is the optimal response to R. B would never be chosen, yet it isnot dominated by any pure strategy.Player 2Player 1TMBLR3, -0, -0, -3, -1, -1, -If we allow mixed strategies, then (i) B is never optimal, and (ii) B is dominated. (i) B is never optimal because whatever belief (q, 1-q) Player 1 may hold about Player 2'splay, 1's best response is either T (if q ≥ 1/2) or M (if q ≤ 1/2), but never B [verify]. (ii) B is dominated by one of Player 1's mixed strategies. If, for instance, Player 1 plays Twith probability 1/2 and M with probability 1/2, then 1's expected payoff is 3/2, no matter what(pure


View Full Document

Stanford MS&E 275 - Principles of Game Theory

Download Principles of Game Theory
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Principles of Game Theory and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Principles of Game Theory 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?