Eco514-Game Theory Lecture 14: General Extensive Games Marciano siniscalchi November 10. 1999 Introduction By and large, I will follow OR, Chapters 1l and 12, so I will keep these notes to a minimum. J Games with observed actions and payoff uncertainty Not all dynamic models of strategic interaction fit within the category of games with observed actions we have developed in the previous lectures. In particular, no allowance was made for payoff uncertainty On the other hand, it is very easy to augment the basic model to allow for it. I am going follow OR very closely here Definition 1 An extensive-form game with observed actions and incomplete information (OR: a Bayesian extensive game with observed actions)is a tupleT=(N, A, H, P, Z, (0i, Pi, UdieN) where N, is a set of players a is a set of actions: H is a collection of finite and countable sequences of vectors of elements of A, such that i)0∈H; (i)(a2,,.a)∈ H implies(a1,,a)∈ h for all e<k; i)fh=(a1,,a,)and(a1,…,a0)∈ h for all k≥1, then h∈H (al, ...,ak, a) H for all a E A. Also let X=H\Z. All infinite histories are terma nd Z is the set of terminal histories: that is,(a P: X=N is the player correspondence ei is a set of payoff types; write e=ilen ei Pi is a probability distribution over i; for i j, Pi and p; are independent U=(Ui)iEN: Z x Lien 0i-R is the payoff function, associating a vector of payoffs te every terminal history and every profile of payoff types
Eco514—Game Theory Lecture 14: General Extensive Games Marciano Siniscalchi November 10, 1999 Introduction [By and large, I will follow OR, Chapters 11 and 12, so I will keep these notes to a minimum.] Games with observed actions and payoff uncertainty Not all dynamic models of strategic interaction fit within the category of games with observed actions we have developed in the previous lectures. In particular, no allowance was made for payoff uncertainty. On the other hand, it is very easy to augment the basic model to allow for it. I am going to follow OR very closely here: Definition 1 An extensive-form game with observed actions and incomplete information (OR: a Bayesian extensive game with observed actions) is a tuple Γ = (N, A, H, P, Z,(Θi , pi , Ui)i∈N ) where: N, is a set of players; A is a set of actions; H is a collection of finite and countable sequences of vectors of elements of A, such that: (i) ∅ ∈ H; (ii) (a 1 , . . . , ak ) ∈ H implies (a 1 , . . . , a` ) ∈ H for all ` < k; (iii) If h = (a 1 , . . . , ak , . . .) and (a 1 , . . . , ak ) ∈ H for all k ≥ 1, then h ∈ H. Z is the set of terminal histories: that is, (a 1 , . . . , ak ) ∈ Z iff (a 1 , . . . , ak ) ∈ H and (a 1 , . . . , ak , a) 6∈ H for all a ∈ A. Also let X = H \ Z. All infinite histories are terminal. P : X ⇒ N is the player correspondence. Θi is a set of payoff types; write Θ = Q i∈N Θi . pi is a probability distribution over Θi ; for i 6= j, pi and pj are independent. U = (Ui)i∈N : Z × Q i∈N Θi → R is the payoff function, associating a vector of payoffs to every terminal history and every profile of payoff types. 1
hus, the key innovations are the sets e and the measures p;. The former enter as parameters in the payoff functions, and thus capture payoff uncertainty; note that Player j's payoffs may depend on Player i's payoff type (i.e. values may be interdependent, using our auction-theoretic terminology The probabilities Pi determine a common prior over e. This is not yet apparent, but it will be when we define a solution concept that applies to such games The implicit assumption one makes is that, before the game begins, payoff types are drawn according to the probabilities pi, .. PN; each player i E N learns her own payoff type Bi, and the product measure p_i E A(e-i) defined by (-)=I (63)≠i∈ j≠i serves as her prior belief about her opponents' payoff types Two important comments are in order. First of all, one might visualize the select of payoff types as a chance move. Clearly, to make things interesting, it must be the that this initial move by chance is not perfectly observed by all players. Hence, one needs a model of extensive games without observed actions; this is precisely the model we are going to develop in the next section Indeed, one might even say that games with incomplete information are the main reason why the theory has traditionally focused on extensive games without observable actions. My point here(shared by OR, as well as Fudenberg and Tirole) is that the general notion is perhaps more than is strictly required to model dynamic games of economic interest I should also add that reducing a situation with incomplete information/payoff uncer- tainty to one with imperfect information(in particular, unobserved actions)is not an entirely harmless assumption-chiefly because doing so requires imposing the common -prior assump- tion(can you see why?) Second. note that i am deviating somewhat from our basic framework for interactive decision making. First, I am incorporating probabilities in the description of the model, and I am making the players'priors over payoff type profiles common. This is why I am using the term "incomplete information"as opposed to "payoff uncertainty-in keeping with the literature Second, for simultaneous-move games, the setup does not immediately reduce to the one we adopt for static Bayesian games. However, to relate the two constructions, it is sufficient to note that 0 is the counterpart of @2 in our static Bayesian setting, and each e; defines a partition of e whose cells are of the form (0i x_i1 While the static Bayesian model is more general than this derived formulation(think about a setting in which all players'payoffs depend on a single random draw which no
Thus, the key innovations are the sets Θi and the measures pi . The former enter as parameters in the payoff functions, and thus capture payoff uncertainty; note that Player j’s payoffs may depend on Player i’s payoff type (i.e. values may be interdependent, using our auction-theoretic terminology). The probabilities pi determine a common prior over Θ. This is not yet apparent, but it will be when we define a solution concept that applies to such games. The implicit assumption one makes is that, before the game begins, payoff types are drawn according to the probabilities p1, . . . , pN ; each player i ∈ N learns her own payoff type θi , and the product measure p−i ∈ ∆(Θ−i) defined by p−i(θ−i) = Y j6=i pj (θj ) ∀θ−i = (θj )6=i ∈ Θ−i serves as her prior belief about her opponents’ payoff types. Two important comments are in order. First of all, one might visualize the selection of payoff types as a chance move. Clearly, to make things interesting, it must be the case that this initial move by chance is not perfectly observed by all players. Hence, one needs a model of extensive games without observed actions; this is precisely the model we are going to develop in the next section. Indeed, one might even say that games with incomplete information are the main reason why the theory has traditionally focused on extensive games without observable actions. My point here (shared by OR, as well as Fudenberg and Tirole) is that the general notion is perhaps more than is strictly required to model dynamic games of economic interest. I should also add that reducing a situation with incomplete information/payoff uncertainty to one with imperfect information (in particular, unobserved actions) is not an entirely harmless assumption—chiefly because doing so requires imposing the common-prior assumption (can you see why?) Second, note that I am deviating somewhat from our basic framework for interactive decision making. First, I am incorporating probabilities in the description of the model, and I am making the players’ priors over payoff type profiles common. This is why I am using the term “incomplete information” as opposed to “payoff uncertainty”—in keeping with the literature. Second, for simultaneous-move games, the setup does not immediately reduce to the one we adopt for static Bayesian games. However, to relate the two constructions, it is sufficient to note that Θ is the counterpart of Ω in our static Bayesian setting, and each Θi defines a partition of Θ whose cells are of the form {{θi} × Θ−i}. While the static Bayesian model is more general than this derived formulation (think about a setting in which all players’ payoffs depend on a single random draw which no 2
player observes), the two can be reconciled by introducing a dummy player in Definition 1 This is not a particularly clean solution, of course, but it works I will return to Bayesian extensive games with observed actions when I discuss Perfect Bayesian equilibrium, the"modal" solution concept for such games. For the time being let me point out that, while the model implicitly defines each player i's prior on e-i, it stands to reason that, as the game progresses, Player i will update her prior beliefs about her opponents' payoff types based on her observations(as well as the conjectured equilibrium) These updated beliefs must somehow be part of the description of the equilibrium; also they must be subject to some sort of consistency condition-Bayes'rule, for instance. We shall see that identifying such conditions is the key problem in the formulation of extensive- form solution concepts General Games with Incomplete Information With the above discussion as a motivation of sorts we are led to consider a notion of extensive ames which allows for partial observability of actions The basic idea is to start with a game with perfect information(i.e. without simultaneous moves) and enrich it with a description of what players actually"know "when a given history obtains layer i's knowledge is modelled via a partition Ii of the set of histories at which the are called upon to choose an action, i.e. P-(i). This is exactly as in our model of payoff uncertainty in static games: in the interim stage, Player i learns, hence knows, that the true state of the world w is an element of the cell ti(w)cQ, but need not know that it is exactly w. Similarly, at a history h, a player learns that the actual history belongs to some set Ii(h)CP-(i), but not necessarily that it is h Definition 2 An extensive-form game with chance moves is a tupleT=(N, A, H, P, Z, (Ui, Ii), fe) N is a set of players; Chance, denoted by c, is regarded as an additional player, socM a is a set of actions h is a set of sequences whose elements are elements of A, such that (i)0∈H; (i)(a1,,a)∈ H implies(al,,a)∈ h for all t<k; i)fh=(a1,,a,.)and(a1,,a^)∈ h for all k≥1, then h∈H; Z and x are the set of terminal and non-terminal histories P is the player function P: X-NUch U: Z-R is the payoff vector function; Li is a partition of P-(i)
player observes), the two can be reconciled by introducing a dummy player in Definition 1. This is not a particularly clean solution, of course, but it works. I will return to Bayesian extensive games with observed actions when I discuss Perfect Bayesian equilibrium, the “modal” solution concept for such games. For the time being, let me point out that, while the model implicitly defines each player i’s prior on Θ−i , it stands to reason that, as the game progresses, Player i will update her prior beliefs about her opponents’ payoff types based on her observations (as well as the conjectured equilibrium). These updated beliefs must somehow be part of the description of the equilibrium; also, they must be subject to some sort of consistency condition—Bayes’ rule, for instance. We shall see that identifying such conditions is the key problem in the formulation of extensiveform solution concepts. General Games with Incomplete Information With the above discussion as a motivation of sorts, we are led to consider a notion of extensive games which allows for partial observability of actions. The basic idea is to start with a game with perfect information (i.e. without simultaneous moves) and enrich it with a description of what players actually “know” when a given history obtains. Player i’s knowledge is modelled via a partition Ii of the set of histories at which they are called upon to choose an action, i.e. P −1 (i). This is exactly as in our model of payoff uncertainty in static games: in the interim stage, Player i learns, hence knows, that the true state of the world ω is an element of the cell ti(ω) ⊂ Ω, but need not know that it is exactly ω. Similarly, at a history h, a player learns that the actual history belongs to some set Ii(h) ⊂ P −1 (i), but not necessarily that it is h. Definition 2 An extensive-form game with chance moves is a tuple Γ = (N, A, H, P, Z,(Ui , Ii), fc) where: N is a set of players; Chance, denoted by c, is regarded as an additional player, so c 6∈ N. A is a set of actions H is a set of sequences whose elements are elements of A, such that (i) ∅ ∈ H; (ii) (a 1 , . . . , ak ) ∈ H implies (a 1 , . . . , a` ) ∈ H for all ` < k; (iii) If h = (a 1 , . . . , ak , . . .) and (a 1 , . . . , ak ) ∈ H for all k ≥ 1, then h ∈ H; Z and X are the set of terminal and non-terminal histories; P is the player function P : X → N ∪ {c} U : Z → R N is the payoff vector function; Ii is a partition of P −1 (i). 3
For every i∈NuU{e},letA(h)={a∈A:(h,a)∈H}. Then fc:{h:c∈P(h)}→△(4) indicates the probability of each chance move, and f(h)(Ai(h))=1 for all h such that c∈P(h Note that we are not allowing for simultaneous moves at a given history. Th easily fixed, but it is not necessary because simultaneous moves can be modelled exploiting the fact that moves may be unobservable The cells of each partition Ii are called information sets Perfect recall Note that, in general, it may be the case that, for some sequences of actions h, h', both h and(h, h)belong to the same information set. This represents a situation in which a player forgets her own previous choice More generally, a player may forget that her opponents have chosen certain actions in the past Definition 2 allows for both possibilities. However, it is conventional(and expedient) to assume that players have perfect recall: they forget neither their own actions, nor their previous observations o formulate this assumption rigorously, we first define, for each player i E N, a collection of sequences(Xi(h))hex such that, for every h E X, Xi (h) includes all the actions Player has chosen and all the information sets in Ii she has visited in the partial history h Formally, let X;(0)=0; next, assuming that Xi(h) has been defined for all histories of ength e, for every a E A(h), let Xi(,a)=Xi(hyufauIi(h, a) if P(h)=P(h, a)=i; Xi(h, a)=Xi(h)ua if P(h)=it p(h, a); Xi(h, a)=Xi(h)UIi(h, a) if P(h,a)=it P(h);and ·X(h,a)=X(h)ifP(h)≠ i and f(h,a)≠i Then we say that an extensive game r has perfect recall iff, for every player i N information set Ii E Ti, and histories h, h'E Ii, Xi(h)=Xi(h ). Observe that Xi is defined at every history, but the notion of perfect recall imposes direct restrictions only at histories where Player i moves Note that, in particular, perfect recall implies that it is never the case that, for some history h and sequence of actions h, both h and(h, h) belong to the same information set
For every i ∈ N∪{c}, let Ai(h) = {a ∈ A : (h, a) ∈ H}. Then fc : {h : c ∈ P(h)} → ∆(A) indicates the probability of each chance move, and fc(h)(Ai(h)) = 1 for all h such that c ∈ P(h). Note that we are not allowing for simultaneous moves at a given history. This can be easily fixed, but it is not necessary because simultaneous moves can be modelled exploiting the fact that moves may be unobservable. The cells of each partition Ii are called information sets. Perfect Recall Note that, in general, it may be the case that, for some sequences of actions h, h0 , both h and (h, h0 ) belong to the same information set. This represents a situation in which a player forgets her own previous choices. More generally, a player may forget that her opponents have chosen certain actions in the past. Definition 2 allows for both possibilities. However, it is conventional (and expedient) to assume that players have perfect recall: they forget neither their own actions, nor their previous observations. To formulate this assumption rigorously, we first define, for each player i ∈ N, a collection of sequences (Xi(h))h∈X such that, for every h ∈ X, Xi(h) includes all the actions Player i has chosen and all the information sets in Ii she has visited in the partial history h. Formally, let Xi(∅) = ∅; next, assuming that Xi(h) has been defined for all histories of length `, for every a ∈ A(h), let: • Xi(h, a) = Xi(h) ∪ {a} ∪ Ii(h, a) if P(h) = P(h, a) = i; • Xi(h, a) = Xi(h) ∪ {a} if P(h) = i 6= P(h, a); • Xi(h, a) = Xi(h) ∪ Ii(h, a) if P(h, a) = i 6= P(h); and • Xi(h, a) = Xi(h) if P(h) 6= i and P(h, a) 6= i. Then we say that an extensive game Γ has perfect recall iff, for every player i ∈ N, information set Ii ∈ Ii , and histories h, h0 ∈ Ii , Xi(h) = Xi(h 0 ). Observe that Xi is defined at every history, but the notion of perfect recall imposes direct restrictions only at histories where Player i moves. Note that, in particular, perfect recall implies that it is never the case that, for some history h and sequence of actions h 0 , both h and (h, h0 ) belong to the same information set. 4
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 functions
Strategies 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