Consistent beliefs in extensive form games

Barelli, Paulo Article Consistent beliefs in extensive form games Games Provided in Cooperation with: MDPI – Multidisciplinary Digital Publishing Institute, Basel Suggested Citation: Barelli, Paulo (2010) : Consistent beliefs in extensive form games, Games, ISSN 2073-4336, MDPI, Basel, Vol. 1, Iss. 4, pp. 415-421, https://doi.org/10.3390/g1040415 This Version is available at: https://hdl.handle.net/10419/98489 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/3.0/ Games 2010,1, 415-421; doi:10.3390/g1040415 OPEN ACCESS games ISSN 2073-4336 www.mdpi.com/journal/games Article Consistent Beliefs in Extensive Form Games Paulo Barelli 1,2 1Department of Economics, University of Rochester, 214 Harkness Hall, Rochester, NY 14627, USA; E-Mail: [email protected]; Tel.: 1-585-275-8075; Fax: 1-585-256-2309 2Insper Institute of Education and Research, Rua Quat´ a, 300 - Vila Ol´ ımpia 04546-042, S˜ ao Paulo, Brazil Received: 1 July 2010; in revised form: 26 September 2010 / Accepted: 15 October 2010 / Published: 20 October 2010 Abstract: We introduce consistency of beliefs in the space of hierarchies of conditional beliefs (Battigalli and Siniscalchi) and use it to provide epistemic conditions for equilibria in finite multi-stage games with observed actions. Keywords: hierarchies of conditional beliefs; epistemic conditions; common belief; correlated subgame perfect equilibrium 1. Introduction Battigalli and Sinischalchi [1] constructed the space of hierarchies of conditional beliefs and used it to provide epistemic foundations for solution concepts in dynamic games. We consider the question of consistency of beliefs in the space of hierarchies of conditional beliefs. In the space of hierarchies of beliefs, Aumann [2], Aumann and Brandenburger [3] and Barelli [4], among others, have used consistency of beliefs to provide epistemic foundations for solution concepts in games in normal form. Here we provide an analogous analysis for multi-stage games with observable actions, in the corresponding space of hierarchies of conditional beliefs. In particular, we show that consistency of beliefs and extensive form rationality provide epistemic foundations for correlated subgame perfect equilibrium (correlated SPE), and these two conditions, plus a notion of constancy of conjectures, provide epistemic foundations for subgame perfect equilibrium (SPE).1 1For simplicity we deal only with finite multi-stage games with with observed actions, so sequential rationality is well captured by subgame perfection; the analysis can be generalized to include incomplete information and/or more complex information structures, where sequential equilibrium is the relevant equilibrium concept to capture sequential rationality. Games 2010,1416 The following simple example helps understand the ideas involved. Consider the standard Battle of Sexes game, with the payoff matrix below, F O F2,1 0,0 O0,0 1,2 The story is that the players decide simultaneously where to meet (either at a football game, F, or an opera house, O), and each player would rather go to the same place as the other, but has a preference for one venue over the other. Let Ai={F, O}for i= 1,2and A=A1×A2. A correlated equilibrium for such a simultaneous move game is a Nash equilibrium of the game augmented by some payoff irrelevant state space, which is understood by both players. Consider, for instance, that each player chooses Fif the weather is good, and chooses Ootherwise (that is, they go to the outdoor event if the weather is good, and to the indoor event if the weather is not good). It is clear that such a strategy is a Nash equilibrium of the game augmented by the state space {good weather, weather not good}: if the other player uses the strategy, it is in the given player’s interest use it as well (if the weather is good (not good), a given player knows that the other will go to the football game (opera house), and will do well to go there too). Let pbe the probability of the weather being good. Then the pair of strategies above gives rise to the distribution of joint actions η∈∆(A)given by η(F, F) = pand η(O, O)=1−p, and it is without loss to focus directly on such distributions in describing a correlated equilibrium. It suffices that, for each ai∈Ai, the expected payoff of aigiven η(ai,·)∈∆(Aj),j6=i, is not smaller than the expected payoff of any other action a0 i, for i= 1,2. Now consider that the players play the game twice. That is, the players play the game once, observe its outcome, play it again, and get the sum of the payoffs obtained in each round. Let H={∅}∪Adenote the set of histories. The empty history represents the first round, and each of the four joint strategies in Arepresents a possible second round. Recall that a SPE is a Nash equilibrium of the entire game that induces Nash equilibria at each subgame. Analogously, a correlated SPE is a correlated equilibrium of the entire game that induces correlated equilibria at each subgame. It can be described as follows. Let η∈∆(A)be a correlated equilibrium of the original Battle of the Sexes game, like the ηdescribed above. A correlated SPE is a list of probability distributions (νh)h∈Hwith νh∈∆(A)for each h∈H, where νha correlated equilibrium for the continuation game at history h∈Aand ν∅a correlated equilibrium of the one shot game given by the first round outcome and the contingent second round outcome, given νhwith h∈A. That is, each of the four continuation games is simply the original Battle of the Sexes game played after the first round. So a correlated equilibrium for a continuation game is a probability distribution η∈∆(A). In the first round, on the other hand, each joint action gives rise to a (potentially) different continuation strategy. So it is not a simple stage game as the games in the second round. But it can be viewed as an one-shot game, with payoffs given by the sum of what is obtained in the first round and of the conditional payoffs in the second round, given the correlated equilibria of the four potential continuation games. Then, for instance, νh=ηfor all h∈His a correlated SPE, because νa(=η) is a correlated equilibrium of the continuation game after history h=afor each a∈A, and given the four continuation correlated moves (νa)a∈A,ν∅(=η) is a correlated equilibrium of the game with payoffs ui(a) + ui(η), where uiis player i’s stage game payoff and ui(η)is the expected payoff given η(so, in Games 2010,1417 particular, the expected payoff given ν∅is simply ui(η)+ui(η)). More complex correlated SPE involving different correlated continuation strategies can be constructed analogously. Likewise, let η∈∆(A1)×∆(A2)be a joint distribution associated with a Nash equilibrium of the stage game. For instance, η(F, F) = η(O, O) = 2 9,η(F, O) = 4 9and η(O, F) = 1 9, which is the joint distribution associated with the Nash equilibrium of the original Battle of the Sexes game in non degenerate mixed strategies. Then a list (νh)h∈Hwith νh=ηfor all h∈His a SPE of the game, for the same reason as above. More complex SPE with different Nash equilibria of the continuation games can be constructed analogously. Now let’s perform an epistemic analysis on the game, that is, an analysis of knowledge and beliefs of the players. In order to do so, we append a type structure (T1, T2, g1, g2)with gi,h ∈∆(S×Tj)for each h∈H, where S=S1×S2with Si={F, O}Hfor i= 1,2. The beliefs of a type ti,(gi,h(ti))h∈H form a conditional probability system (CPS), (the formal definitions are provided below). A “state” for a player is a strategy-type pair (si, ti), describing the player’s strategy choice and beliefs. Epistemic statements can now be stated in terms of the states of the players. For instance, let Si(h)be player i’s set of strategies consistent with history h∈H. Let η=η(·|Sj(h))h∈H, where η(·|Sj(h)) ∈∆(Sj(h)) for each h∈H. We say that siis a best response to η, written si∈ri(η), if simaximizes the expected utility with respect to η(·|Sj(h)) for every history hconsistent with si. And we say that the strategy-type pair (si, ti)∈Si×Tiis rational if si∈ri((margSjgi,h(ti))h∈H). Statements like “rationality is common knowledge among the players” can be described by a type structure where in each state (s, t)∈S1×S2×T1×T2both players are rational. Note that a type of a player determines the conditional beliefs at every history, and rationality captures sequentially rational choices, after every history (given the conditional beliefs). Assume that the beliefs of the players are consistent in the following sense. There is a CPS (µh)h∈H with µh∈∆(S(h)×T)for each h∈H, such that gi,h(ti)(E×Tj) = µh(E×T|ti)for all E⊂S, ti∈Tiand i= 1,2. The idea is analogous to action-consistency in Barelli [4], which is a generalization of the standard common prior assumption. Because strategies are in principle verifiable entities, we can conceive of an outside observer offering bets on S, conditional on each history, where the payouts of the bets are measured in utils. The two players will be in a no-bets situation if there does not exist a bet that yields a sure gain to an outsider. In Barelli [4] it is shown that this is equivalent to consistency of beliefs, as defined above. Now, if consistency and rationality obtain at every (s, t)∈S×T,2then we can identify a correlated SPE (νh)h∈Hfrom the CPS (µh)h∈Hby putting νh(a) = µh({s:sh=a} × T), for all a∈A. Indeed, if it is the case that beliefs are consistent and the CPS (µh)h∈Hsatisfies µh({s:sh= (F, F)}×T) = pand µh({s:sh= (O, O)} × T) = 1 −pfor every h∈H, then it is straightforward to verify that rationality is obtained at every state, and that we obtain the correlated SPE described above. Indeed, rationality implies that no player wants to deviate from the recommended action, as required in a correlated SPE, and (νh)h∈His exactly the correlated SPE above. Other correlated SPE are analogously obtained as we vary the consistent CPS (µh)h∈H. The key observation here is that, under consistency, rationality ensures that the system of inequalities defining a correlated SPE is met. 2More precisely, if throughout the support of the CPS (µh)h∈Hdefined above we have rational strategy-type pairs. Games 2010,1418 If instead µh({s:sh= (F, F)}×T) = µh({s:sh= (O, O)}×T) = 2 9,µh({s:sh= (F, O)}×T) = 4 9and µh({s:sh= (O, F)} × T) = 1 9for every h∈H, then we again have rationality at every state, and the SPE described above is obtained. As in Aumann and Brandenburger [3] and Barelli [4], the key observation is that constancy of conjectures in the support of the CPS (µh)h∈Hensures that (µh({s:sh=a} × T))a∈Ais the product of its marginals, just as above. So rationality, consistency and constancy of conjectures in the support of the CPS are sufficient conditions for a SPE. It is important to note that constancy of conjectures is implied by (but does not imply) conjectures being commonly known among the players. 2. Set Up The set up is as in Battigalli and Siniscalchi [1]. Let Xbe a Polish space, and let Abe its Borel sigma algebra. Let B ∈ A be a countable collection of clopen sets, with ∅/∈ B. The collection B represents the relevant hypotheses. A CPS on (X, A,B)is a mapping µ(·|·) : A × B → [0,1] satisfying: (i) µ(B|B) = 1 for all B∈ B, (ii) µ(·|B)∈∆(X), and (iii) for all A∈ A,B, C ∈ B, if A⊂B⊂C then µ(A|B)µ(B|C) = µ(A|C).3The set of CPSs on (X, A,B)is a closed subset of [∆(X)]B, and it denoted by ∆B(X). Consider a finite multi-stage game Gwith observable actions (Fudenberg and Tirole [5], Chap. 3). Let Hbe the set of histories and let Sibe the set of strategies si:H → Ai, where Aiis the set of all possible actions for player i∈I, and si(h)∈Ai(h)for each h∈ H, where Ai(h)is the set of actions available at h. Let ui:S→ R denote player i’s utility function, with S=×i∈ISi. As usual, we use A−i=×j6=iAjand A=×i∈IAi(likewise for other sets, like Ti,T−iand Tbelow.) A correlated equilibrium of a finite normal form game (Ai, ui)i∈Iis a probability distribution η∈∆(A)satisfying X a−i∈A−i [ui(ai, a−i)−ui(a0 i, a−i)]η(a)≥0 for all i∈Iand all ai, a0 i∈Ai. The interpretation is the one provided in the Introduction: the players use some external random device to peg their actions to, and assuming that the other players follow the recommended choices with the implied likelihoods, a given player has no incentive to deviate from his/her recommended choices. Because any such equilibrium generates a probability distribution over the joint actions, it is convenient to focus directly on such distributions (in the same way that a mixed strategy Nash equilibrium is defined directly on distributions, and not on the random variables that generate the distributions). A correlated SPE of a finite multi-stage game with observed actions is given by ν= (νh)h∈H, with νh∈∆(A(h)), which induces correlated equilibria at every subgame. That is, for each history hwe have a continuation game G(h)where the payoffs are defined for the histories that are consistent with h. Given h, we have a continuation correlated strategy ν|h, given by the restriction of νto histories consistent with h. Then a correlated SPE is νsuch that ν|his a correlated equilibrium of G(h)for every h∈ H. Standard dynamic programming arguments show that this is equivalent to the description provided in the Introduction. An SPE is a correlated SPE νwith νh∈ ×i∈I∆(Ai(h)) for each h∈ H. 3∆(X)denotes the space of probability measures on (X, A). Games 2010,1419 Let Si(h)be player i’s set of strategies consistent with history h∈ H, and let H(si)be the set of histories consistent with si. The relevant hypotheses for the players are thus the collection B={S(h) : h∈ H}. For a given player i, the hypotheses that are consistent with i’s strategies are Bi={Si(h) : h∈ H}. As in Battigalli and Siniscalchi [1], we simplify notation by writing ∆Bi(·) and ∆B(·)as ∆H(·). In order to perform an epistemic analysis, we append a type structure to the game, describing the beliefs of the players. A type space is a tuple T= (Ti, gi)i∈Iwith gi:Ti→∆H(S×T−i) for each i∈I. Again, to simplify notation we write (gi,h(ti))h∈H ∈∆H(S×T−i)instead of (gi,S(h)(ti))S(h)∈B ∈∆B(S×T−i). Let η=η(·|S−i(h))h∈H ∈∆H(S−i). We say that siis a best response to η, written si∈ri(η), if for all h∈ H(si)and s0 i∈Si(h), we have X s−i∈S−i(h) [ui(si, s−i)−ui(s0 i, s−i)]η(s−i|S−i(h)) ≥0 We then say that a strategy-type pair (si, ti)is rational if si∈ri((margS−igi,h(ti))h∈H), and if si∈Si(h) then gi,h(ti)({(si} × S−i×T−i) = 1. We say that player iis rational at state (s, t)∈S×Tif the strategy-type pair (si, ti)∈Si×Tiis rational. A CPS µ∈∆H(S×T)is called a consistent prior if µh(E×T) = ZTi gi,h(ti)(E×T−i)margTiµh(dti) for all i∈I, all h∈ H and all E⊂S. It then follows that gi,h(ti)(E×T−i) = µh(E×T|ti)for all i∈I, all h∈ H, all E⊂Sand margTiµh-a.e. ti. Let supp µ=Sh∈H supp µhdenote the support of the consistent prior. As advanced above, consistency is founded on players being in a no-bets situation, that is, a situation where an outside observer cannot make a sure gain on the group of players by offering bets on the strategy choices of the players. Proposition 5.3 in Barelli [4] establishes the equivalence between consistency and no-bets, and the reader is referred to that paper for further details. For the sake of comparison with the literature, consider a finite normal form game G= (Ai, ui)i∈I and a type space T= (Ti, λi)i∈I, with λi(ti)∈∆(A×T−i)capturing hierarchies of beliefs. Player iis rational at state (a, t)if aiis a best response to his conjecture margA−iλi(ti)and λi(ti)({ai} × A−i×T−i)=1. A common prior is a probability measure p∈∆(A×T)such that λi(ti) = p(·|ti) for margTip-a.e. ti. An action-consistent prior is a probability measure π∈∆(A×T)such that margAλi(ti) = margAπ(·|ti)for margTiπ-a.e. ti. Aumann [2] showed that, when there is a common prior, common knowledge of rationality implies that players play a correlated equilibrium. Aumann and Brandenbuger [3] showed that common knowledge of rationality and of conjectures and the existence of a common prior are sufficient conditions for players to play a Nash equilibrium. These results were extended in Barelli [4] with the use of action-consistency in the place of common prior, rationality in the support of the action-consistent prior in the place of common knowledge of rationality and constancy of conjectures in the support of the action-consistent prior in the place of common knowledge of conjectures. Note that the notion of consistency used here is much more demanding than using action-consistency in the normal form of the game. Consistency requires that players be at a no-bets situation after every Games 2010,1420 history h∈ H, whereas action-consistency allows for players to not be at a no-bets situation after histories that are not compatible with the strategy profiles in the support of the action-consistent prior. Players are required to be aware of a potential outsider at every counter factual that they envisage while choosing their strategies. 3. Results For a given consistent prior µ, let ν= (νh)h∈H be given by νh(a) = margSµh(s:sh=a)for each a∈A(h), so that νh∈∆(A(h)). We have: Proposition 1. Let Gbe a finite multi-stage game with observed actions, and let Tbe a type space associated with G. Assume that there exists a consistent prior µ∈∆H(S×T)such that player iis rational at all (s, t)∈supp µ, for every i∈I. Then νdefined above is a correlated SPE. Proof. By consistency, we have margS−igi,h(ti) = margS−iµh(·|ti)for every i∈I,h∈ H and ti∈supp margTiµh. By rationality we then have for each i∈Iand every h∈ H(si) X s−i∈S−i(h) [ui(si, s−i)−ui(s0 i, s−i)]margS−iµh(s−i|ti)≥0 for every (si, ti)and every s0 i∈Si(h). Let η= (ηh)h∈H with ηh∈∆(S(h)) be given by ηh(s) = ZTi(si)margS−iµh(s−i|ti)margTiµh(dti) where Ti(si) = {t0 i∈Ti: (si, t0 i)is rational}, so that X s−i∈S−i(h) [ui(si, s−i)−ui(s0 i, s−i)]ηh(s)≥0 for every i∈I,si, s0 iin Si(h)and h∈ H(si). Now notice that the restriction of νto a history h∈ H, ν|h, is the behavioral representation of ηh. By Kuhn’s Theorem, the distribution over final outcomes induced by ηhis the same as that induced by ν|h, so ν|his a correlated equilibrium of the continuation game G(h)for every history h∈ H, and we are done. Let φi,h(ti) = margS−igi,h(ti)denote the conjecture of type tiat h∈ H. We have: Proposition 2. Let Gbe a finite multi-stage game with observed actions, and let Tbe a type space associated with G. Assume that there exists a consistent prior µ∈∆H(S×T)such that (i) player i is rational at all (s, t)∈supp µfor every i∈Iand (ii) φi,h(ti) = φi,h(t0 i)for every i∈Ifor every ti, t0 i∈supp margTiµh, for each h∈ H. Then νdefined above is a SPE. Proof. Fix h∈Hand let φi,h be player i’s constant conjecture in the support of margTiµh. By consistency and rationality, we have for each s∈S(h) margSµh(s) = margTiµh(Ti(si))φi,h(s−i) where Ti(si)is as in Proposition 1. Hence margSµh=margSiµh⊗margS−iµh Now induction in the number of players shows that margSµh=⊗i∈ImargSiµh, and a fortiori νh∈ ×i∈I∆(Ai(h)), for all h∈ H. The result then follows from Proposition 1. Games 2010,1421 4. Conclusion The results in section 3 tell us the following: under consistency, rationality yields correlated SPE and adding constancy of conjectures to these two conditions yield SPE. These results are analogous to the results in Aumann [2], Aumann and Brandenburger [3] and Barelli [4]. As in the latter, beliefs are required to be consistent only at events that are potentially observable by an outsider, who could in principle force beliefs to be consistent by offering bets on the observable events. Rationality and constancy of conjectures have to hold in the support of the consistent prior. Because rationality and/or constancy of conjectures are implied by (but do not imply) rationality and/or conjectures being commonly known among the players, we have that rationality need not be common knowledge for players to play a correlated SPE, and neither do conjectures have to be common knowledge for players to play a SPE. References 1. Battigalli, P.; Sinischalchi, M. Hierarchies of Conditional Beliefs and Interactive Epistemology in Dynamic Games. J. Econ. Theory 1999,88, 188–230. 2. Aumann, R. Correlated Equilibrium as an Expression of Bayesian Rationality. Econometrica 1987, 55, 1–18. 3. Aumann, R.; Brandenburger, A. Epistemic Conditions for Nash Equilibrium. Econometrica 1995, 63, 1161–1180. 4. Barelli, P. Consistency of Beliefs and Epistemic Conditions for Nash and Correlated Equilibria. Game. Econ. Behav. 2009,67, 363–375. 5. Fudenberg, D.; Tirole, J. Game Theory; The MIT Press: Cambridge, MA, USA, 1992. c 2010 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license http://creativecommons.org/licenses/by/3.0/.