Strategies Pure and mixed strategies in general extensive games are easily defined Definition 3 Fix an extensive game r and a player E N. a pure strategy for Player i is a map s:→ A such that, for all Ii∈,s(1)∈A(l1) Denote by Si, S-i and s the sets of strategies of Player i, the set of strategy profiles of i's opponents, and the set of complete strategy profiles respectively. A mixed strategy for Player i is a probability distribution O E A(Si) The notion of randomization captured in Definition is as follows: at the beginning of the game, players spin a roulette wheel to choose a pure strategy, and stick to that strategy thereafter However, players could also randomize at each information set. This gives rise to a different notion: Definition 4 Fix an extensive game r and a player i E N. a behavioral strategy for Player i is a map 62:→△(A) such that, for all I∈,A1(1)(A(h)=1 Denote by Bi, B-i and B the sets of i's behavioral strategies, of her opponents'behavioral strategy profiles, and of complete behavioral strategy profiles If this reminds you of our definition of chance moves, it should: the function fc is simply Chances behavioral strategy It is natural to ask whether the two notions of randomization are related. The answer is that, of course, they are. To be precise about this, we first define(with some abuse of notation) the outcome functions O:B→△(Z)andO:IieN△(S)→△(Z) to be the maps which associate with each profile of behavioral or mixed strategies a distribution over terminal nodes(you should provide a formal definition) We then ask two distinct questions. First, given a behavioral strategy profile B E B,can we find an outcome-equivalent mixed strategy profile, i.e. some o E IleN A(Si)such that O(a)=O(6)? The answer is affirmative for all games which satisfy the following condition: for every player i E N, information set Ii E Ii, and histories h, h'E Ii, it is never the case that h is a subhistory of h or vice-versa. Hence, in particular, the answer is affirmative for all games with perfect recall. OR provides an example(p. 214)where this condition fails Second, given a mixed strategy profile o, can we find an outcome-equivalent behavioral strategy profile B? The answer is again affirmative, if we restrict ourselves to games with erfect recall. This is Proposition 214.1 in OR, also known as Kuhn,s Theorem I conclude by noting that a Nash equilibrium of an extensive game is simply a Nash luilibrium of (the mixed extension of) its normal form; you can think of a formal definition using outcome functionsStrategies Pure and mixed strategies in general extensive games are easily defined: Definition 3 Fix an extensive game Γ and a player i ∈ N. A pure strategy for Player i is a map si : Ii → A such that, for all Ii ∈ Ii , si(Ii) ∈ A(Ii). Denote by Si , S−i and S the sets of strategies of Player i, the set of strategy profiles of i’s opponents, and the set of complete strategy profiles respectively. A mixed strategy for Player i is a probability distribution σi ∈ ∆(Si). The notion of randomization captured in Definition is as follows: at the beginning of the game, players spin a roulette wheel to choose a pure strategy, and stick to that strategy thereafter. However, players could also randomize at each information set. This gives rise to a different notion: Definition 4 Fix an extensive game Γ and a player i ∈ N. A behavioral strategy for Player i is a map βi : Ii → ∆(A) such that, for all Ii ∈ Ii , βi(Ii)(A(h)) = 1. Denote by Bi , B−i and B the sets of i’s behavioral strategies, of her opponents’ behavioral strategy profiles, and of complete behavioral strategy profiles. If this reminds you of our definition of chance moves, it should: the function fc is simply Chance’s behavioral strategy! It is natural to ask whether the two notions of randomization are related. The answer is that, of course, they are. To be precise about this, we first define (with some abuse of notation) the outcome functions O : B → ∆(Z) and O : Q i∈N ∆(Si) → ∆(Z) to be the maps which associate with each profile of behavioral or mixed strategies a distribution over terminal nodes (you should provide a formal definition). We then ask two distinct questions. First, given a behavioral strategy profile β ∈ B, can we find an outcome-equivalent mixed strategy profile, i.e. some σ ∈ Q i∈N ∆(Si) such that O(σ) = O(β)? The answer is affirmative for all games which satisfy the following condition: for every player i ∈ N, information set Ii ∈ Ii , and histories h, h0 ∈ Ii , it is never the case that h is a subhistory of h 0 or vice-versa. Hence, in particular, the answer is affirmative for all games with perfect recall. OR provides an example (p. 214) where this condition fails. Second, given a mixed strategy profile σ, can we find an outcome-equivalent behavioral strategy profile β? The answer is again affirmative, if we restrict ourselves to games with perfect recall. This is Proposition 214.1 in OR, also known as Kuhn’s Theorem. I conclude by noting that a Nash equilibrium of an extensive game is simply a Nash equilibrium of (the mixed extension of) its normal form; you can think of a formal definition, using outcome functions. 5