Stiftung.at

Abstract
Markov Perfect Equilibrium as commonly used is not a solution concept defined solely on the extensive form of a game, but makes useof an externally given set of states. Using the idea that states shouldbe payoff-relevant and that payoff-relevance should be definable fromthe extensive form, Maskin and Tirole have provided a canonical defi-nition of the payoff relevant states for dynamic games with observableactions.
It is argued in this paper that their approach has to be extended in order to identify future strategic possibilities. Otherwise, differentstates may only differ in payoff-irrelevant ways. For a large class ofgames, one can apply their approach directly after modifying the ex-tensive form of a game in payoff-irrelevant ways.
A byproduct of the analysis is that the restriction to finite action spaces and nonstationary equilibria employed by Maskin and Tirole isnot necessary.
Keywords: Markov Perfect, Dynamic Game, RefinementJEL Classification: C72, C73 Introduction
We prefer simple models to complicated ones. In game theory, we deal withmodels in which the players possess models themselves. A player has to ∗Thanks to Guilherme Carmona, Venkataraman Bhaskar, Ehud Lehrer, Konrad Podczeck, Philip Reny, and Ariel Rubinstein for helpful discussions. Klaus Ritzberger has provided anextensive list of valuable comments and suggestions which are gratefully acknowledged.
Christina Pawlowitsch helped me in improving the exposition. The usual disclaimer applies.
†Institut für Wirtschaftswissenschaften, Universität Wien, Hohenstaufengasse 9, A-1010 Wien, Austria. E-mail: [email protected], Tel: ++43/1/4277-37412, Fax:++43/1/-4277-9374 have a model of the strategic environment she faces and that model hasto contain everything that is relevant to her decision making. Yet what isrelevant to her, will often depend on the models used by other players. Aseemingly irrelevant variable may become important to her because otherplayers make their behavior conditional on that variable and their behaviormatters.
The model of the strategic environment used when making a choice will usually depend on past play. Partially because past play influences whatplayers can do and want, partially because other players take history intoaccount themselves. We want to focus on the former aspect, so we have tolook at minimal models of the past and we have to look at the models ofplayers jointly. The models players will use in this paper are simply sets ofstates, with each state summarizing the part of the past that is still relevantto todays decisionmaking, states are what is payoff-relevant. Players employtheir models when making decisions, they choose strategies that depend onstates alone. We will look at how small such models can be in order to dropas much payoff-irrelevant knowledge of the past as possible.
Our starting point is the concept of a (stationary) Markov perfect equilib- rium, as defined by Maskin and Tirole in [9].1 When payoff-relevant stateswere still just a modelling choice made on a case by case basis, they under-took the important task of defining the payoff relevant states in terms of theextensive form alone. In the setting of dynamic games with observable ac-tions, they defined a Markov perfect equilibrium as a subgame-perfect equi-librium in which every players strategy is "measurable with respect to thecoarsest partition of histories for which, if all other players use measurablestrategies, each player’s decision-problem is also measurable." In order to show that such a partition actually exists, Maskin and Tirole had to make two restrictive assumptions: They had to assume that all play-ers can condition on calendar time and that players can choose only amongfinitely many actions when called to make a decision. The first assumptiongoes against the spirit of payoff-relevance, the second assumption rules outmany important applications of dynamic games. Both restrictions turn outto be superflous (Theorem 1).
The definition of payoff-relevant states by Maskin and Tirole is quite sensitive to what they view as decision problems. Two actions are treateddifferently, if they have different names. For this reason, in a Markov perfectequilibrium, players may make non-isomorphic choices in isomorphic sub-games. But names of actions are not payoff relevant, they merely decorate 1An accessible textbook treatment of their approach can be found in [8], section 5.6.
the game tree. In general, their notion of Markov Perfect Equilibrium maytell us very little about what the payoff-relevant states are. Actually, anysubgame-perfect equilibrium becomes a Markov perfect equilibrium after asimple relabeling of actions (Theorem 2). This is not just troubling on aconceptual basis, it also renders the concept inapplicable when one uses adefinition of the extensive form that does not identify different actions bynames. In the classical graph-theoretic definition of the extensive form ofKuhn ([6]), Markov Perfect Equilibrium cannot even be defined.
For a large class of dynamic games that are "sufficiently asymmetric", there exists a canonical labeling of actions that ensures that all Markov per-fect equilibria induce isomorphic choices in isomorphic subgames (Theorem3). Moreover, this labeling uses only information included in every rea-sonable definition of the extensive form (payoffs and the order structure ofmoves). For games outside this class of games, a relabeling of this kind maynot exist.
Major proofs are collected in an appendix.
Environment
We will focus exclusively on games with observable actions2 in discrete time.
In the usual definition of an extensive form game, dynamics are representedby a graph and information and choices are modelled by partitions. Forgames with observable actions, such a definition is unnecessarily cumber-some. Information sets coincide with histories and making an arbitrarytemporal ordering of moves when players move simultaneously adds onlyirrelevant information. For our analysis, we will take histories, which arenothing but sequences of action profiles, as the basic unit of analysis. Ourformal model has three ingredients: A set of players, a set of histories andfor each player, preferences over maximal histories.
We start with a set of players I. We merely require I to be nonempty, we do not rule out an infinity of players. Our second ingredient is a set Hof histories. The members of H are finite or infinite sequences of I-tuples.3Each term of the sequence is an action profile and each coordinate in an ac-tion profile is an action. We have to impose some consistency requirementson H: (i) The empty sequence ∅ belongs to H.
2Such games are also known as games of almost perfect information, games with perfect monitoring, or as simultaneous move games.
3Formally, an I-tuple is simply a function with domain I.
1 ∈ N ∪ {∞}) and T2 < T1 then (at)T2 (iv) Suppose h is not of maximal length. For each player i, let Ai(h) = ai : ∃a−i h, (ai, a−i) ∈ H . Then for all a ∈ The conditions (i) and (ii) ensure that H has a well defined tree structure.
Condition (iii) for infinite histories ensures that maximal histories exist evenwhen the time horizon is infinite. Finally, condition (iv) guarantees that theactions a player can play after a certain history, are independent of what theothers play after that history.
We call histories of maximal length plays and all other histories nonter- minal histories. We denote the set of nonterminal histories by H∗, theseare the histories where players can actually act. Clearly, they all have finitelength. The last ingredient in our definition of the extensive form is a re-flexive, complete and transitive preference ordering player i. So (I, H, ( i)i∈I) is a game. We may refer to H also as a gameform.
This framework is quite flexible. We can model situations in which only some players can choose after some history by allowing the other playersonly to "choose" one single action. This way, we can accommodate gamesof perfect information, games with overlapping generations of players as in[3], and games with long-and short run players as in [4]. Technically, wecould even work with histories indexed by large ordinals and accommodatetransfinite games such as long cheap talk ([2]).
A (pure) strategy for player i is a function si that maps each nonterminal history h to an action in Ai(h). We restrict ourselves to pure strategiesin order to avoid measurability problems when dealing with continua ofactions.
When we specify a strategy for each player, we get a strategy profile (si)i∈I. By recursion, every strategy profile determines a unique play. A con-tinuation c of a nonterminal history h is a sequence of action profiles thatmakes the sequence (h, c) a play.4 So a continuation is "what can happenafter h". At each nonterminal history, every player i has conditional prefer-ences h over continuations such that c h c if and only if (h, c) 4The notation (h, c) denotes the concatenation of the sequences h and c. The context should prevent confusion when the same notation is used for ordered pairs. What we callcontinuations, are futures in [9].
Given a nonterminal history h of length T , we can construct an h-subgame The set of histories consists of all con- tinuations and initial segments of continuations. The continuations are theplays and preferences for player i are simply i induces a uniques continuation strategy si|h in the h-subgame by settingsi|h(h ) = si (h, h ) . Since every strategy profile induces a unique play,every player has preferences over her strategies, for fixed strategies of theothers. By slight abuse of notation, we also write si equilibrium of the game (I, H, ( i)i∈I) is a strategy profile such that for ev-ery player i, every nonterminal history h, and every possible strategy s ofplayer i, the inequality s|h h s Finally, we will need some mathematical definitions related to partitions: A partition Π of a set X is a family of nonempty, pairwise disjoint subsets ofX such that P = X. We call the elements of a partition cells. If Π Π2 are partitions of X, we say that Π1 is coarser than Π2 if every cell in Π1is the union of cells in Π2. This is equivalent to every cell in Π2 being thesubset of a cell in Π1. Let Π be a partition of X and f be a function definedon X. We say that f is Π-measurable, if for every cell P ∈ Π and every twoelements x, y ∈ P, we have f(x) = f(y). When x and y are in the same cellof the partition Π, we will say that x and y are Π-equivalent.
Markov Perfect Equilibrium
A partition profile (Πi)i∈I lists for each player i, a partition Πi of H∗. Apartition profile should provide a model of the relevant past for every playerthat encompasses the current strategic environment. For this, we need thefollowing consistency conditions, taken from [9]. A partition profile (Πi)i∈Iis consistent if it satisfies the following two conditions: (i) If the histories h1 and h2 are Πi-equivalent for any player i, then h1 (ii) Suppose all players j = i employ Πj-measurable strategies. If h1 and Condition (i) formalizes the idea that all players can behave in the same wayin the future and condition (ii) that one can restrict oneself to measurablestrategies, provided everybode else does the same. Condition (ii) does not imply that the preferences over continuations are the same. Consider twohistories ending in the following one-shot games: Clearly, both players have different preferences over continuations. But dueto the special structure of this example, a players payoff depend in bothgames only on the action chosen by the other players. So both players areindifferent between their actions and hence continuation strategies. So (ii)holds trivially.
A partition profile (Πi)i∈I is dated if any two histories h1 and h2 that are Πi-equivalent for some player i are of the same length. In a dated partitionprofile, measurable strategies can be condition on calendar time.
What we are really after are minimal models. We say that the partition profile (Πi)i∈I is coarser than the partition profile (Π ) than Π for every player i. A coarser partition profile corresponds to players Theorem 1 There exists a coarsest consistent partition profile and a coarsest
consistent dated partition profile.
The maximally coarse consistent partition profile contains the payoff- relevant information for every player, they form the state space for theplayer. A special case of this result has been obtained by Maskin and Ti-role. They show that a coarsest consistent dated partition profile exists whenno player can choose among infinitely many actions after some history andwhen the set of players is finite. For finitely many players, they have alsoshown that maximally coarse consistent partition-profiles exist in general byemplying Zorn’s lemma. They did not rule out the possibility of different,incomparable, maximally coarse consistent partitions in that case.
In applied work, one usually assumes that there is a single state spaces shared by all players. Our formulation allows for different players to havedifferent partitions in the coarsest consistent partition profile. One couldeasily formulate everything in terms of a partition common to all players.
It is also possible to rule out a diversity of partitions by essentially requir-ing that everything some player does has an impact on every other playerat every time. This is the approach employed by Maskin and Tirole. Theassumption is satisfied in games in which everyones strategic possibilities depend on some aggregate stock, such as the stock of fish in the classicalfishwar model ([7]).
Finally, Maskin and Tirole define a Markov Perfect Equilibrium (MPE) as a subgame perfect strategy profile in which every player plays a strategymeasurable with respect to her partition in the coarsest consistent datedpartition profile. They define stationary Markov Perfect Equilibrium (SMPE)as a subgame perfect strategy profile in which every player plays a strategymeasurable with respect to her partition in the coarsest consistent partitionprofile. For expositional clarity, we focus on the latter. The discussion caneasily be adopted to the dated case.
Limitations of MPE and SMPE
When we defined consistent partition profiles, we required that two histo-ries are equivalent for any player only if they allow for the same continua-tions. But sequences of action profiles are a poor representation of a deci-sion problem. In a (S)MPE, players may face isomorphic subgames differingonly by the names of actions and behave differently in the two subgames.
So (S)MPE does not conform to reasonable notions of subgame consistency.
To make this precice, we need to formalize a notion of being essentially thesame.
An isomorphism between the games (I, H, ( i)i∈I) and (I, H , ( (i) For two histories h1 and h2, h1 is an initial segment of h2 if and only if f(h1) is an initial segment of f(h2).
(ii) For any nonterminal history h there exists a family (fh) fi : Ai(h) → A (f(h)) such that f h, (a (iii) For any two plays h1 and h2 and any player i, h1 Condition (i) guarantees that f is an order-isomorphism under the “is an initial segment of"-ordering. Condition (ii) makes it an order isomorphismon the terminal histories for the preferences of each player. Condition (ii) isrequired to preserve the internal product structure of histories.
Isomorphic games are the same in everything that is payoff relevant.
But by a mere relabeling of actions, we can change every subgame-perfectequilibrium into a stationary Markov perfect equilibrium.
Theorem 2 Given any game, there exists an isomorphic game in which every
subgame-perfect equilibrium is a stationary Markov perfect equilibrium.
If f is an isomorphism between the games (I, H, ( i)i∈I) and (I, H , ( i )i∈I) and (si)i∈I is a strategy profile for (I, H, ( i)i∈I), there is also aninduced strategy profile (sf) history in H of length T and h be the unique history of lenth T + 1 thatoccurs when all players follow the strategy profile (si)i∈I. Now sf f(h) is simply defined to be the ith coordinate of the last term of f(h ).
With this definition out of the way, we can define subgame consistency.
A strategy profile (si)i∈I in a game (I, H, ( i)i∈I) is subgame-consistent if,whenever there is an isomorphism f between two subgames, the strategyprofile induced by f in one subgame is the strategy profile in the othersubgame. Informally, in a subgame-consistent strategy profile, players fac-ing the same strategic situation behave in the same way.5 By our last re-sult, there clearly exists stationary Markov perfect equilibria that are notsubgame-consistent.
Suppose there are two different isomorphisms between subgames. Then some strategy profile in one subgame induces different strategy profiles un-der the different isomorphisms. Such a strategy profile cannot be subgame-consistent. To avoid this problem, we look at games in which two subgamescan be isomorphic in only one way. Formally, we say that a game is rigid ifthe only isomorphism of the game with itself is the identity mapping.
Remark 1 A game is rigid if and only if no two subgames are isomorphic to
each other in more than one way.
Proof: Since the whole game is a subgame, if two subgames are isomorphic
to each other in one way, the game must be rigid. Conversely, we observe
first that every isomorphism from a subgame to itself can be extended to
an isomorphism on the whole game that maps each history outside the sub-
game to itself. So in a rigid game, every subgame can be isomorphic to itself
only under the identity. Now, if f and f are different isomorphism from one
subgame to another, then f−1 ◦ f and f−1 ◦ f are different isomorphisms of
the first subgame to itself, whic cannot be in a rigid game.
For rigid games, we can relabel actions in a way that makes stationary Markov perfect equilibria subgame-consistent.
5The notion of subgame-consistency goes back to [12].
Theorem 3 Given any rigid game, there exists an isomorphic game such that
every stationary Markov perfect equilibrium is subgame-consistent.
For games that are not rigid, a mere relabeling will not suffice. Here is a The two proper subgames are clearly isomorphic, but no pure strategy can make all isomorphic choices at the same time. Any isomorphism re-produces the tree structure, including the payoff-irrelevant redundancies.
There is really no decision problem in this example. The example is non-generic, but this is natural in this context. The symmetries avoided by rigidgames stem from nongeneric payoff-ties.
Remark 2 If in game with only finitely many histories there exists a player
who is not indifferent between any two plays, then the game is rigid.
Proof: By assumption, there is a player i whose preferences
are a linear ordering. Isomorphisms are completely determined by whatthey do to plays. The identity on H is the only isomorphism to itsef thatdoesn’t change any plays. Now by (iii) in the definition of an isomor-phism, the restriction of every isomorphism to the set of plays is an order-isomorphism for i. The only order isomorphism of a finite, linearly ordered Discussion
The notion of subgame consistency used here is quite strong. In particular,we assume that all isomorphisms induce behavior in corresponding sub-games. This corresponds to the idea that an observer can hold any viewon how different subgames are related to each other. A different approachwould require that if two subgames are related by some isomorphism, thereexists some isomorphism that relates the behavior in one subgame to the be-havior in another subgame. For elementary games, these notions coincide.
For other games, requiring this form of subgame-consistency would meanthat players have a shared understanding of what subgames are consideredto be the same. This requires them to have a more complex model of theirenvironment that is not just based on the structure of the game.
Satisfying our notion of subgame-consistency would be easier if players could employ mixed strategies. Our notion does rule out certain pure equi-libria even in one-shot games, where symmetric equilibria always exist inmixed strategies ([10]). If one prefers to work with the mixed extension,one replaces actions by behavior strategies, interpreted as transition proba-bilities. To justify this, one appeals to a suitable extension of Kuhn’s theo-rem, such as [1]. This will require additional assumptions. The extensionis relatively straightforward when only finitely many players have nontrivialchoices each period and after each nonterminal history, a player can playat most countably many actions. In this case, H∗ will be at most countableand every consistent partition profile will only include partitions with atmost countably many cells. No special measurable or topological structurehas to be imposed on the state space. Also, if we start with a dynamic gamedefined in terms of a given countable state space, we are guaranteed thatour construction gives us less states (Proposition 5.6.2. in [8]), so for manyapplications, there is no problem in admitting mixed strategies.
Finally, it is worth pointing out that one could separate all results from specific solution concepts such as SPE. Effectively, we have shown that onecan represent future strategic possibilities by summary statistics, states, andthat for rigid games, one can do this in a way that preserves symmetriesin the strategic possibilities. If we look at purely forward-looking forms ofbehavior, states will contain all relevant information.
Appendix
The following proof builds on the original proof of Maskin and Tirole andwork of Ore on the lattice structure of partitions. The construction of thecoarsest consistent partition profile is based on a characterization of thefinest common coarsening of a family of partitions. Partitions of a set forma complete lattice with the "coarser than"-ordering and Ore laid the founda-tions for the theory in [11]. The reader interested in partition lattices willfind a comprehensive overview in [5], section IV.4.
Proof of Theorem 1
We show that a coarsest consistent partition profile exists. Essentially thesame proof works for dated partition profiles. For each player i, we definea relation ≡i on H∗ such that h ≡i h if there is a finite sequence of non-terminal histories h, h1, h2, . . . , hn, h such that consecutive histories in thesequence are equivalent for the partition of i in some consistent partitionprofile Πi. The relation ≡i is clearly an equivalence relation. Let Π∗ be the partition of H∗ into ≡i-equivalence classes.
i i∈I is the coarsest consistent partition pro- file. It is clearly a partition profile and by construction coarser than anyconsistent partition profile. It remains to verify that it is also consistent.Webegin with consistency condition (i). If h and h are Π∗-equivalent, they are also ≡i-equivalent and that means they are connected by a finite sequenceof nonterminal histories such that consecutive histories are equivalent un-der some partition in a consistent partition profile. But then consecutivehistories in the sequence must allow for the same continuations by (i) andby transitivity, h and h allow for the same continuations. This proves (i).
For consistency condition (ii), observe that the coarser a partition is, the less strategies are measurable. That means that whenever all playersj = i play Πj-measurable strategies, they play strategies measurable withrespect to their partition in every consistent partition profile. Now supposeall players j = i employ Π∗-measurable strategies. Let h and h be Π∗- there exists a finite sequence h1, . . . , hn+1 of nonterminal histories and afinite sequence of consistent partition profiles (Π1) h1 = h, hn+1 = h and hk, hk+1 are in the same cell of Πk for k = 1, . . . , n.
Now if all players j = i employ Π∗-measurable strategies, they also employ Πk-measurable strategies. Since all continuations are the same, we can hk s |hk for k = 1, . . . , n. By transitivity of ≡ Proof of Theorem 2
Proof: Let H, ( i)i∈I be a given game. We rename every action played at
a certain history so that actions played after different histories get different
names. Here is one way to do this: If a = (ai)i∈I is an action profile and
z some mathematical object, write a|z for (ai, z)
suppose f(h) is already defined when h has length T − 1. For a finite history is an infinite history, let f(h) be the unique sequence such that the initial segment of length T coincides with f (at)T H = f(H), which is a game form. Define ( ) is obvious that f is an isomorphism.
Since actions played after different histories are different, there are no two histories in H that have a common continuation. So the only stationaryconsistent partition consists of all singletons and every strategy is measur-able with respect to this partition. So every subgame perfect equilibriumuses strategies measurable with respect to this partition and is therefore aSMPE.
Proof of Theorem 3
Proof: Let G = (I, H, ( i)i∈I) be a rigid game. By transforming the game
as in the proof of Theorem 2, we can assume that no action can be played
after different histories. For each player i ∈ I we define a function gi on
Ai =
h∈H∗ Ai(h). By assumption, for each ai ∈ Ai there is a unique ∈ H. Now we let gi(ai) be the set of all ai such that there is some h-subgame isomorphic to the ha -subgame with isomorphism f : Hhai → Hh such that a is the ith coordinate of the last component of f h, (ai, a−i) . Effectively, gi(ai) is the set of actions thatserve the same role as ai in some subgame.
We now construct a function g on H recursively. We set g(∅) = ∅. Sup- pose g is already defined for all histories of length n−1 and h = h, (ai)i∈Iis a history of length n. Then we set g(h ) = g(h), (gi(ai))i∈I . If h =(at)∞ is an infinite history, let g(h) be the unique sequence such that the initial segment of length T coincides with g (at)T i i∈I) is a game isomorphic to G under the isomorphism g : H → g(H). Moreover, any isomorphic subgames of G actually coincideby construction, so every SMPE of G is necessarily subgame-consistent.
References
[1] R. J. AUMANN, Mixed and behavior strategies in infinite extensive games, in Advances in Game Theory, Princeton Univ. Press, Princeton, N.J.,1964, pp. 627–650.
[2] R. J. AUMANN AND S. HART, Long cheap talk, Econometrica, 71 [3] V. BHASKAR, Informational constraints and the overlapping generations model: Folk and anti-folk theorems, The Review of Economic Studies,65 (1998), pp. pp. 135–149.
[4] D. FUDENBERG AND D. K. LEVINE, Reputation and equilibrium selection in games with a patient player, Econometrica, 57 (1989), pp. pp. 759–778.
[5] G. GRÄTZER, General lattice theory, Birkhäuser Verlag, Basel, 2003.
With appendices by B. A. Davey, R. Freese, B. Ganter, M. Greferath,P. Jipsen, H. A. Priestley, H. Rose, E. T. Schmidt, S. E. Schmidt,F. Wehrung and R. Wille, Reprint of the 1998 second edition[MR1670580].
[6] H. W. KUHN, Extensive games and the problem of information, in Contri- butions to the theory of games, vol. 2, Annals of Mathematics Studies,no. 28, Princeton University Press, Princeton, N. J., 1953, pp. 193–216.
[7] D. LEVHARI AND L. J. MIRMAN, The great fish war: An example using a dynamic cournot-nash solution, The Bell Journal of Economics, 11(1980), pp. pp. 322–334.
[8] G. J. MAILATH AND L. SAMUELSON, Repeated Games and Reputations: Long-Run Relationships, Oxford University Press, USA, 9 2006.
[9] E. MASKIN AND J. TIROLE, Markov perfect equilibrium. I. Observable actions, J. Econom. Theory, 100 (2001), pp. 191–219.
[10] J. NASH, Non-cooperative games, Ann. of Math. (2), 54 (1951), [11] O. ORE, Theory of equivalence relations, Duke Math. J., 9 (1942), [12] R. SELTEN AND W. GÜTH, Game theoretical analysis of wage bargaining in a simple business cycle model, Journal of Mathematical Economics,10 (1982), pp. 177 – 195.

Source: http://www.stiftung.at/wp-content/uploads/2012/06/2012_Payoff-Relevance.pdf