AXIOMATIC EQUILIBRIUM SELECTION FOR GENERIC TWO-PLAYER GAMES

AXIOMATIC EQUILIBRIUM SELECTION FOR GENERIC TWO-PLAYER GAMES SRIHARI GOVINDAN AND ROBERT WILSON Abstract. We apply three axioms adapted from decision theory to refinements of the Nash equilibria of games with perfect recall that select connected closed subsets called solutions. Undominated Strategies: No player uses a weakly dominated strategy in an equilibrium in a solution. Backward Induction: Each solution contains a quasi-perfect equilibrium and thus a sequential equilibrium in strategies that provide conditionally admissible optimal continuations from information sets. Small Worlds: A refinement is immune to embedding a game in a larger game with additional players provided the original players’ strategies and payoffs are preserved, i.e. solutions of a game are the same as those induced by the solutions of any larger game in which it is embedded. For games with two players and generic payoffs, we prove that these axioms characterize each solution as an essential component of equilibria in undominated strategies, and thus a stable set as defined by Mertens (1989). Date: 28 May 2009. Key words and phrases. game, equilibrium, refinement, axiom, admissibility, backward induction, small worlds, stability. JEL subject classification: C72. This work was funded in part by a grant from the National Science Foundation of the United States. 1 2 SRIHARI GOVINDAN AND ROBERT WILSON Contents List of Figures 1. Introduction 2. Notation 3. The Axioms 3.1. Undominated Strategies 3.2. Backward Induction 3.3. Small Worlds 3.4. Summary of the Axioms 4. Additional Notation and Properties 4.1. Payoffs 4.2. Notation for the Extensive Form 4.3. Enabling Strategies 4.4. Stable Sets of Equilibria 4.5. The Associated Pseudomanifold 5. Statement and Proof of the Theorem 5.1. Preliminaries 5.2. A Game with Redundant Strategies 5.3. Extensive Form of the Metagames 5.4. Outsiders’ Payoffs in the Metagames 5.5. Outsiders’ Strategies in a Quasi-Perfect Equilibrium 5.6. Limits of the Quasi-Perfect Equilibria of the Metagames 5.7. Insiders’ Strategies in a Quasi-Perfect Equilibrium 5.8. The Induced Lexicographic Probability System 5.9. Limit of the Lexicographic Probability System 5.10. Final Step of the Proof 6. Concluding Remarks Appendix A. Enabling Strategies Appendix B. Proofs of Propositions B.1. Proof of Proposition 3.3 B.2. Proof of Proposition 3.4 Appendix C. Proof of Theorem 4.1 Appendix D. The Genericity Assumption References 2 3 5 6 6 6 7 9 10 10 10 11 12 13 13 14 15 16 17 17 19 20 21 22 24 25 27 28 28 29 30 45 46 List of Figures 1 2 A game tree and its pure reduced normal form in which each pure strategy is identified by the terminal nodes it does not exclude. 27 The game tree of a signaling game and its pure reduced normal form in which each pure strategy is identified by the terminal nodes it does not exclude. 28 AXIOMATIC EQUILIBRIUM SELECTION 3 1. Introduction Nash’s [22, 23] definition of equilibrium is insufficient when applied to a game in extensive form. Even for games with perfect information, some equilibria use weakly dominated strategies and yield outcomes different from the outcome predicted by backward induction; see [11, §4.2] for an example. The literature on refinements aims to sharpen Nash’s definition to exclude such equilibria; recent surveys include [8, 12, 31]. Kohlberg and Mertens [14] suggest that a refinement should be characterized by axioms adapted from decision theory. They also specify properties that axioms should imply. Subsequently, Mertens [19, 20, 21] defines the set-valued refinement called stability and shows that it has these and other properties, including the following.1 1. Admissibility and Perfection. All equilibria in a stable set are perfect (hence admissible) so each player’s strategy in each equilibrium is undominated. 2. Backward Induction and Forward Induction. A stable set includes a proper equilibrium that induces a quasi-perfect (hence sequential) equilibrium in every extensiveform game with perfect recall that has the same normal form. A subset of a stable set survives iterative elimination of weakly dominated strategies and strategies that are inferior replies at every equilibrium in the set. 3. Invariance, Small Worlds and Decomposition. The stable sets of a game are the projections of the stable sets of any larger game in which it is embedded. The stable sets of the product of two independent games are the products of their stable sets. For games in extensive form with perfect recall, we propose three axioms that are versions of these properties. We assume that for each game a refinement selects a nonempty collection of nonempty connected closed subsets of equilibria, called solutions.2 The axioms are the following: A. Undominated Strategies: No player uses a weakly dominated strategy in any equilibrium in a solution. 1 Mertens considers the graph of equilibria over the space of perturbed games obtained by perturbing players’ strategies toward mixed strategies, and then defines a connected closed set of equilibria as stable if the projection from a neighborhood in this graph is an essential map, i.e. has nonzero degree. See Mertens [19] for further topological aspects of the definition, and Govindan and Mertens [3] for an equivalent definition in terms of players’ best-reply correspondences. 2 Solutions are assumed to be sets because Kohlberg and Mertens [14, pp. 1015, 1019, 1029] show that there need not exist a single equilibrium satisfying weaker properties than the axioms invoked here. The technical requirement that a solution is connected excludes the trivial refinement that selects all equilibria. If only a single (possibly unconnected) subset is selected then only the trivial refinement satisfies the conditions invoked by Norde, Potters, Reijnierse, and Vermeulen [24]. Kreps and Wilson [16, Theorem 2] show that if payoffs are generic then all equilibria in a connected set yield the same probability distribution over terminal nodes, and thus the same paths of equilibrium play in the extensive form. 4 SRIHARI GOVINDAN AND ROBERT WILSON B. Backward Induction: A solution contains a quasi-perfect equilibrium. S. Small Worlds: A solution is immune to embedding the game within larger games that preserve players’ strategies and payoffs. In Axiom A we invoke only the implication of admissibility that no player uses a weakly dominated strategy. Axiom A is equivalent to admissibility in two-player games. Axiom B insists on inclusion of a quasi-perfect equilibrium because it induces a sequential equilibrium in strategies that provide admissible optimal continuations from players’ information sets.3 Axiom S ensures that a refinement is not vulnerable to framing effects depending on how the game is presented within wider contexts called metagames. A metagame can include additional players and additional pure strategies, provided these additional features do not alter optimal decisions in the original game. Our version of small worlds is stronger than Mertens’ [21] version because our definition of embedding allows a more general class of metagames. We prove that these three axioms characterize refinements that select some or all of the stable sets of a game in extensive form with perfect recall, two players, and generic payoffs. Our characterization is cast in terms of the ‘enabling form’ of a game in which two pure strategies of a player are considered equivalent if they exclude the same terminal nodes of the game tree, and thus enable the same sets of terminal nodes to occur as outcomes of the game. The enabling form is defined in Section 4.3 and explained further in Appendix A. Our main theorem establishes that the axioms imply that each solution is an essential component of admissible equilibria. For the enabling form of a game this is the defining property of a stable set.4 When payoffs are generic, all equilibria in a component yield the same probability distribution over outcomes. Therefore, for economic modeling and econometric studies the axioms’ chief implication is that a predicted outcome distribution should result from an essential component of the game’s admissible equilibria. A secondary implication is that a solution must include all equilibria in the component. This is germane for predicting players’ behaviors only after deviations from equilibrium play, but it addresses the issue of whether sequential rationality is a relevant decision-theoretic criterion after deviations (Reny [26]). We show that each equilibrium in a solution is induced by a quasi-perfect equilibrium in a 3 We intend that a revised version will weaken Axiom B to only require inclusion of a sequential equilibrium for which each player’s strategy is conditionally admissible from each of his information sets. 4 A component is a maximal closed connected set, and it is essential if it has the property described in footnote 1. For the usual normal form of the game, a solution can be a subset of a component that maps to a component of the enabling form of the game. AXIOMATIC EQUILIBRIUM SELECTION 5 solution of some metagame; therefore, it is sequentially rational when viewed in the wider context of this metagame. See [7, Section 2.3] for an example. Section 2 establishes notation for Section 3, which specifies Axioms A (undominated strategies), B (backward induction), and S (small worlds), including a precise definition of embedding a game in a larger game. Appendix B verifies that Nash equilibria satisfy this definition of embedding. Section 4 establishes further notation and states a key technical property proved in Appendix C. Section 5 states and proves the main theorem, Theorem 5.1. The proof is constructive in that each equilibrium in a stable set is shown to be induced by a quasi-perfect equilibrium in a solution of a particular metagame with perfect recall that embeds the given game. Section 6 interprets this result and provides concluding remarks. 2. Notation This section provides sufficient notation for statements of the axioms in Section 3. Section 4 introduces additional notation for the theorems in Section 5 and Appendix C. A typical game in extensive form is denoted Γ. Its specification includes a set N of players, a game tree with perfect recall for each player, and an assignment of players’ payoffs at each terminal node of the tree. Let Hn be player n’s collection of information sets, and let An (h) be his set of feasible actions at information set h ∈ Hn . The specification of the tree can include a completely mixed strategy of Nature. A player’s pure strategy chooses an action at each of his information sets. Denote n’s simplex of mixed strategies by Σn and interpret its vertices as his set Sn of pure strategies. Q Q The sets of profiles of players’ pure and mixed strategies are S = n Sn and Σ = n Σn . The normal form of Γ assigns to each profile of players’ pure strategies the profile of their expected payoffs; equivalently, it is the multilinear function G : Σ → RN that assigns to each profile of their mixed strategies the profile of their expected payoffs. A player’s behavioral strategy specifies a mixture over his actions at each of his information Q sets. Let Bn be n’s set of behavioral strategies, and B = n Bn the set of profiles of players’ behavioral strategies. Each mixed strategy σn induces a behavioral strategy bn . Because the game has perfect recall, for each behavioral profile there are profiles of mixed strategies that induce it and yield the same distribution of outcomes (Kuhn [17]). As defined by Nash [22, 23], an equilibrium is a profile of players’ strategies such that each player’s strategy is an optimal reply to other players’ strategies. That is, if BRn (σ) ≡ arg maxσn′ ∈Σn Gn (σn′ , σ−n ) is player n’s best-reply correspondence, then σ ∈ Σ is an equilibrium iff σn ∈ BRn (σ) for every player n. The analogous definition of equilibrium in behavioral strategies is equivalent for games with perfect recall. 6 SRIHARI GOVINDAN AND ROBERT WILSON A refinement is a correspondence that assigns to each game a nonempty collection of nonempty connected closed subsets of its equilibria. Each selected subset is called a solution. According to the above definitions, a mixed or behavioral strategy makes choices even at information sets that its previous choices exclude from being reached. In Section 4 we consider pure strategies to be equivalent if they make the same choices at information sets they do not exclude. And, we further simplify mixed and behavioral strategies by considering only their induced probability distributions on non-excluded terminal nodes. The definitions of an equilibrium and a refinement have equivalent statements in terms of these strategy spaces. Each equilibrium in a reduced strategy space corresponds to a set of equilibria as defined above, and analogously for solutions selected by a refinement. The axioms in Section 3 are stated in terms of mixed and behavioral strategies as defined above. One reason for this is that Axiom S implies invariance to redundant strategies, and thus justifies our later use of equivalence classes of strategies. 3. The Axioms 3.1. Undominated Strategies. The first axiom requires that no player uses a weakly dominated strategy. Say that a profile of players’ strategies is undominated if each player’s strategy is undominated. Axiom A (Undominated Strategies): Each equilibrium in a solution is undominated. 3.2. Backward Induction. We interpret sequential equilibrium as the generalization to games with perfect recall of backward induction in games with perfect information, and to be consistent with Axiom A we insist on conditionally admissible optimal continuations from information sets. Here we obtain these properties from a quasi-perfect equilibrium, which requires a consistency property of beliefs that is stronger than required by Kreps and Wilson’s [16] definition of sequential equilibrium. Van Damme [30, p. 8] defines a quasiperfect equilibrium in terms of players’ behavioral strategies. Definition 3.1 (Quasi-Perfect Equilibrium). A profile b ∈ B of behavioral strategies is a quasi-perfect equilibrium if it is the limit of a sequence of profiles of completely mixed behavioral strategies for which, for each player n, from each of his information sets, continuation of his strategy bn is an optimal reply to every profile in the sequence. That is, if BRn (·|h) is n’s best-reply correspondence in terms of behavioral strategies that continue from his information set h ∈ Hn , and bn (h) is the continuation of his behavioral AXIOMATIC EQUILIBRIUM SELECTION 7 strategy bn from this information set, then the profile b ∈ B is quasi-perfect if (∀ k) (∀ n ∈ N, h ∈ Hn ) bn (h) ∈ BRn (b̂k |h) for some sequence b̂k ∈ B \ ∂B for which b̂k → b. If the mixed-strategy profile σ ∈ Σ induces a behavioral profile b ∈ B that is a quasi-perfect equilibrium then we say that σ too is quasi-perfect. Similarly, the justifying sequence b̂k can be represented by a sequence σ̂ k in Σ \ ∂Σ for which σ̂ k → σ. Van Damme shows that a quasi-perfect equilibrium induces a perfect equilibrium of the normal form, and a sequential equilibrium of the extensive form in which all players’ beliefs are induced by the same justifying sequence. Moreover, by construction a quasi-perfect equilibrium provides for each player an admissible optimal continuation from each of his information sets. It can be shown that if payoffs are generic then every sequential equilibrium is quasi-perfect and extensive-form perfect. The second axiom requires that some equilibrium in a solution is quasi-perfect. Axiom B (Backward Induction): Each solution contains a quasi-perfect equilibrium. If payoffs are generic then Axioms A and B imply that each solution lies in a component of undominated equilibria, each of which yields the same distribution over outcomes as a sequential equilibrium in the solution. 3.3. Small Worlds. The third axiom requires that a refinement is not affected by extraneous features of wider contexts in which a game is embedded, provided such contexts do not alter players’ feasible strategies and payoffs. An embedding allows the presence of additional players whose actions might provide the original players with additional pure strategies equivalent to mixed strategies in the original game, and thus redundant. For simplicity, to define an embedding we use the normal form G : Σ → RN of the extensive-form game Γ. An embedding is described by a ‘larger’ game G̃ : Σ̃ × Σo → RN ∪ o in which game G is ‘embedded,’ subject to certain restrictions specified below. The larger game G̃ has outsiders in a set o, in addition to insiders who are the players in N , and there can be additional moves by Nature. An insider n can have additional pure strategies in Σ̃n that are not pure strategies in Sn but are equivalent to mixed strategies in Σn . The basic requirement is that an embedding should preserve the game among insiders, conditional on actions by outsiders. These restrictions have a technical formulation. There should exist a multilinear map f : Σ̃ × Σo → Σ that is surjective and such that G̃n = Gn ◦ f for each insider n. Moreover, to exclude an embedding from introducing correlation among insiders’ strategies, f should factor into separate multilinear maps (fn )n∈N , where each component is a map fn : Σ̃n ×Σo → 8 SRIHARI GOVINDAN AND ROBERT WILSON Σn such that fn (·, σo ) maps Σ̃n surjectively onto Σn for each profile σo ∈ Σo of outsiders’ strategies. Admittedly, a statement of the axiom that uses this technical language could contain unsuspected implications. However, after stating the formal definition, we provide in Proposition 3.3 an equivalent formulation that is more detailed and more transparent, and that verifies the requisite properties. Also, Proposition 3.4 applies a precise test of whether the axiom is correctly stated, namely, a refinement that satisfies the axiom should be immune to the same embeddings that equilibria are. Definition 3.2 (Embedding). A game G̃ : Σ̃ × Σo → RN ∪ o and a collection of multilinear maps fn : Σ̃n × Σo → Σn , one for each player n ∈ N , embed a game G : Σ → RN if (a) for each σo ∈ Σo , fn (·, σo ) maps Σ̃n surjectively onto Σn , and (b) G̃n = Gn ◦ f , where f = (fn )n∈N . Condition (a) ensures that embedding has no net effect on an insider’s set of mixed strategies, conditional on outsiders’ strategies, and condition (b) ensures that there is no net effect on any insider’s payoffs. Hereafter, if G̃ embeds G via maps f = (fn ) then we say that (G̃, f ) embeds G and that G̃ is a metagame for G. We omit description of f for metagames in extensive form that embed a game in extensive or strategic form. An elaborate example of a metagame in extensive form that embeds a game in extensive form is constructed in proving Theorem 5.1. Note that the property that G̃ is a metagame for G does not depend on specifying payoffs for the outsiders; in particular, it depends only on their extensive forms and the insiders’ payoffs in the two games. A multilinear map fn : Σ̃n × Σo → Σn is completely specified by its values at profiles of pure strategies. Let fˆn be the restriction of fn to the set S̃n × So of profiles of pure strategies of player n and the outsiders in o. The following Proposition, proved in Appendix B, provides an alternative definition of embedding in terms of pure strategies. Proposition 3.3. G̃ embeds G via a collection of multilinear maps f = (fn )n∈N if and only if for each player n there exists T̃n ⊆ S̃n and a bijection πn : T̃n → Sn such that for each (s̃, so ) ∈ S̃ × So and t̃n ∈ T̃n : (1) fˆn (t̃n , so ) = πn (t̃n ), (2) G̃n (s̃, so ) = Gn (fˆ(s̃, so )), where fˆ = (fˆn )n∈N . AXIOMATIC EQUILIBRIUM SELECTION 9 Property (2) assures that players’ payoffs from pure strategies of G are preserved by the metagame G̃. Hence property (1) assures that each pure strategy sn ∈ Sn is equivalent to some pure strategy t̃n = π −1 (sn ) ∈ T̃n , independently of the outsiders’ profile so . Q Pure strategies in S̃n \ T̃n are redundant because payoffs from profiles in n T̃n exactly Q replicate payoffs from corresponding profiles in n Sn for the embedded game G. In particular, if fˆn (s̃n , so ) = σn ∈ / Sn then conditional on so the pure strategy s̃n is equivalent for insiders to the mixed strategy σn ∈ Σn . The next Proposition, proved in Appendix B, verifies that equilibria are not affected by embedding in a metagame. Proposition 3.4. If (G̃, f ) embeds G then the equilibria of G are the f -images of the equilibria of G̃. A corollary of Proposition 3.4 is that embedding does not introduce correlation among insiders’ strategies. Using Definition 3.2 of embedding, the small worlds axiom is the following. Axiom S (Small Worlds): If (G̃, f ) embeds G then the f -images of the solutions that a refinement selects for G̃ are the solutions selected for G. In view of Proposition 3.4, this axiom is an instance of the general principle that a refinement should inherit invariance properties of equilibria. Two special cases of Axiom S are the following. Invariance: Suppose Σo and o are singletons and insiders’ payoffs and strategies in Σ̃ differ from Σ only by treating some mixed strategies in Σ as additional pure strategies in S̃. Then Axiom S implies that solutions depend only on a game’s reduced normal form obtained by deleting such redundant pure strategies. Mertens’ Small Worlds Axiom [21]: Suppose Σ̃ = Σ. Then Axiom S implies that a solution does not depend on the presence of outsiders, i.e. solutions of the original game are the projections of the solutions of metagames obtained by adding dummy players. 3.4. Summary of the Axioms. We study refinements that are independent of embeddings in metagames that, for each profile of outsiders’ strategies, preserve the strategies and payoffs of the game among insiders. And, we require that each of their solutions is a closed connected set of undominated equilibria, including one that is quasi-perfect. In particular, a solution of a metagame must contain a quasi-perfect equilibrium whose image is in the corresponding solution of the embedded game. 10 SRIHARI GOVINDAN AND ROBERT WILSON 4. Additional Notation and Properties In the sequel we consider only a game Γ in extensive form with perfect recall, two players, and generic payoffs. In this section we prepare for the statement and proof of the main theorem in Section 5. 4.1. Payoffs. Let Z be the set of terminal nodes of the game tree. Players’ payoffs are given by a point u in U = RN ×Z , where un (z) is the payoff to player n ∈ N at terminal node z ∈ Z. We assume that payoffs are generic in that there exists a lower dimensional subset U◦ of U such that our results are true for all games in U \ U◦ . The set U◦ includes the nongeneric set described in [4]. Therefore, each game outside U◦ has finitely many equilibrium outcome distributions, and in particular all equilibria in a component yield the same distribution over outcomes. However, the proofs in Section 5 and Appendix C require some genericity properties that are not necessarily implied by the construction in [4]. To avoid disrupting the main exposition, we defer to Appendix D the description of the exact set of genericity properties required for the proofs, and an explanation of why the resulting set U◦ of excluded payoffs has lower dimension. 4.2. Notation for the Extensive Form. The set of players is N = {1, 2}, typically represented as a player n and the other player m 6= n. Let X be the set of nodes in the game tree. Let Xn be the set of nodes where player n moves, partitioned into his information sets h ∈ Hn . For a node x ∈ Xn we write h(x) for the unique information set h ∈ Hn that contains x. For each n and h ∈ Hn , let An (h) be the set of actions available to player n at h. Assume that actions at all information sets are labeled differently, and let An be the set of all actions for player n. Node x precedes another node y, written x ≺ y, if x is on the unique path from the root of the tree to y. For a node x ∈ Xn and a ∈ An (h(x)) write (x, a) ≺ y if x ≺ y and the path from the root of the tree to y requires player n to choose a at h(x). If (x, a) ≺ y and x and y belong to n’s information sets h and h′ , respectively, then every node in h′ follows some node in h by the choice of a, so we write (h, a) ≺ h′ . The set of pure strategies of player n is the set Sn of functions sn : Hn → An such that sn (h) ∈ An (h) for all h ∈ Hn . For each n, sn ∈ Sn and y ∈ X, let βn (y, sn ) be the probability that sn does not exclude y, i.e. βn (y, sn ) = 1 if for each (x, a) ≺ y with x ∈ Xn , sn (h(x)) = a, and otherwise βn (y, sn ) = 0. By perfect recall, if y ∈ Xn then βn (y ′ , sn ) = βn (y, sn ) for all y ′ ∈ h(y) and we write βn (h(y), sn ) for this probability. Likewise, for any node y we write β0 (y) for the probability that Nature does not exclude y. Then for a profile s ∈ S the probability that node y is reached is β(y, s) ≡ β0 (y)β1 (y, s1 )β2 (y, s2 ). AXIOMATIC EQUILIBRIUM SELECTION 11 Recall that Σn is the set of mixed strategies of player n. For each node y the function P βn (y, ·) extends to a function over Σn via βn (y, σn ) = sn ∈Sn βn (y, sn )σn (sn ) for σn ∈ Σn . Recall also that Bn is the set of behavioral strategies of player n. For each bn ∈ Bn , βn (y, bn ) is the product of bn ’s probabilities of n’s actions on the path to y. Similarly extend β to profiles of mixed or behavioral strategies. Given a mixed-strategy profile σ ∈ Σ, the probability that outcome z results is β(z, σ) = β0 (z)β1 (z, σ1 )β2 (z, σ2 ). 4.3. Enabling Strategies. For each player n define ρn : Σn → [0, 1]Z by the formula ρn (σn ) = (βn (z, σn ))z∈Z , and let ρ = (ρn )n∈N . Similarly, if bn ∈ Bn is the behavioral strategy Q induced by σn then ρn (σn ) = (βn (z, bn ))z∈Z . Let Pn be the image of ρn , and P = n Pn the image of ρ. Then Pn is a compact convex polyhedron, called the space of n’s enabling strategies in [5]. Each vertex of Pn corresponds to an equivalence class of n’s pure strategies that exclude the same outcomes.5 If σ ∈ Σ and p = ρ(σ) then the probability of outcome z is γz (p) = β0 (z)p1 (z)p2 (z). Thus the function γ : P → ∆(Z) summarizes the extensive form. The analog of the game Γ’s normal form G : Σ → RN is the enabling form G : P → RN that assigns to each profile P of enabling strategies the profile of players’ expected payoffs, where Gn (p) = z γz (p)un (z). Note that γ and G are multilinear functions. From players’ best-reply correspondences in terms of enabling strategies one obtains the definition of equilibrium in enabling strategies. To each equilibrium in enabling strategies there correspond families of outcome-equivalent equilibria in behavioral and mixed strategies. Axioms A and S have direct analogs in terms of enabling strategies, as shown in [11]. For games in extensive form with perfect recall, enabling strategies are minimal representations. For example, using perfect recall, by working backward in the induced tree of a player’s information sets, from his enabling strategy one can construct the corresponding behavioral strategy at his information sets that his prior actions do not exclude. Because Axiom S implies Invariance, it is immaterial whether solutions are characterized in terms of mixed, behavioral, or enabling strategies. We use enabling strategies here because induced distributions over outcomes are multilinear functions of enabling strategies, like they are for mixed strategies but unlike the nonlinear dependence on behavioral strategies. Also, the dimensions of the spaces of enabling and behavioral strategies are the same, which is important for the technical property established in Theorem 4.1 below. Using these features, Section 5 derives the implications of the axioms in terms of enabling strategies. 5In [5], enabling strategies are defined in terms of terminal actions rather than terminal nodes. The present definition is equivalent because a player’s probability of enabling a terminal action is the probability of enabling each terminal node that follows it. The vertices of Pn are n’s pure strategies in the ‘pure reduced normal form’ defined by Mailath, Samuelson, and Swinkels [18]. See Appendix A for illustrations. 12 SRIHARI GOVINDAN AND ROBERT WILSON 4.4. Stable Sets of Equilibria. Now let Σ̄∗ be a component of the equilibria of Γ in terms of mixed strategies, and let Σ̄∗n be the projection of Σ̄∗ in Σn . By genericity, all equilibria in Σ̄∗ induce the same distribution over outcomes. Therefore, for each node x, β(x, σ) is the same for all σ ∈ Σ̄∗ ; in particular, if x belongs to information set h ∈ Hn and h is on an equilibrium path then βn (h, σn ) is the same for every equilibrium strategy σn of player n in Σ̄∗ . We therefore denote these probabilities by βn∗ (x) and βn∗ (h). Let Hn∗ be the collection of information sets h ∈ Hn of player n such that βn∗ (h) > 0 and let A∗n be the set of actions at information sets in Hn∗ that are chosen with positive probability by the equilibria in B̄ ∗ , where B̄ ∗ is the set of profiles of behavioral strategies induced by equilibria in Σ̄∗ . Let Sn0 ⊂ Sn be the set of pure strategies s0n with the property that, at each information set h ∈ Hn∗ that s0n does not exclude, s0n prescribes an action in A∗n . Let Sn1 = Sn \ Sn0 , i.e. each pure strategy sn in Sn1 chooses a non-equilibrium action at some information set h ∈ Hn∗ that it does not exclude. For i = 0, 1, let Σin be the set of mixed strategies whose support is contained in Sni . Observe that the support of n’s strategy in every equilibrium in Σ̄∗ is contained in Sn0 and that every strategy in Sn0 is a best reply against every equilibrium in Σ̄∗ . Thus Σ̄∗n is contained in Σ0n and Σ̄∗ = Σ̄∗1 × Σ̄∗2 . If Sn1 is empty for each n, then each equilibrium in B̄ ∗ is completely mixed; by genericity, B̄ ∗ is a singleton and its equivalent mixed strategy is stable. The only interesting case, therefore, is one where Sn1 is nonempty for at least one of the players. In order to avoid dealing with different cases, we assume that Sn1 is nonempty for each n. (Along the way, we will indicate how the proof changes when Sn1 is empty for exactly one player.) Let Pn0 be the image of Σ0n under ρn . Let Zn1 ⊂ Z be the set of terminal nodes z such that (h, a) ≺ z for some h ∈ Hn∗ and a ∈ / A∗n . Let Zn0 = Zn \ Zn1 . Then Pn0 is the set of pn ∈ Pn such that pn (z) = 0 for all z ∈ Zn1 and thus Pn0 is a face of Pn . However, the image Pn1 of Σ1n under ρn need not be a face of Pn . For i = 0, 1, let P i = P1i × P2i and define P = P 0 × P 1 . Z1 For each pn ∈ Pn , let ψZn1 (pn ) be the projection of pn to R+n ; then ψZn1 (pn ) = 0 iff pn ∈ Pn0 . Fix a point p̄m in the interior of Pm and define ηn : Pn → R by η(pn ) = P 0 1 p0 (z)p̄m (z)pn (z), where p0 is Nature’s enabling strategy. Then η(pn ) = 0 iff pn ∈ Pn . z∈Zn 1 Choose ε > 0 such that ηn (pn ) > ε for all pn ∈ Pn1 . Let Hn be the hyperplane in RZn with normal (p0 (z)p̄m (z))z∈Zn1 and constant ε. Hn separates the origin from ψZn1 (Pn1 ). Let Π1n be the intersection of Hn with ψZn1 (Pn1 ). Then there is a function π̄n1 from Pn \ Pn0 to Π1n that maps each pn ∈ / Pn0 to the point ε(ηn (pn ))−1 ψZn1 (pn ). AXIOMATIC EQUILIBRIUM SELECTION 13 Now let Σ∗ be a component of the undominated equilibria of the game Γ that is contained in Σ̄∗ . Since Σ̄∗ = Σ̄∗1 × Σ̄∗2 , Σ∗ is expressible as a product Σ∗1 × Σ∗2 , where Σ∗n is a component of the intersection of Σ̄∗n with the set of undominated strategies. For each n, let Q∗n be the image of Σ∗n under ρn , and Q∗ the image of Σ∗ under ρ, i.e. represented in enabling strategies. Hereafter we say that Q∗ is stable if Σ∗ is a stable set of equilibria.6 4.5. The Associated Pseudomanifold. Given Q∗ , let Q be the set of (q ∗ , (p0 , p1 ), π 1 ) ∈ Q∗ × P × Π1 such that there exist r0 , p̃0n ∈ Pn0 , r1 ∈ Pn1 , and for each n scalars λ0n , λ1n , µ1n in the interval (0, 1] such that, if qn0 = λ0n p0n + (1 − λ0n )rn0 and qn1 = (1 − λ1n )p̃0n + λ1n (µ1n p1n + (1 − µ1n )rn1 ) , then for each n:7 (i) π̄n1 (qn1 ) = πn1 . ∗ 0 1 (ii) qn0 , and rn0 if λ0n < 1, are lexicographic best replies against (qm , qm , qm ). (iii) If µ1n < 1 then rn1 is a best reply against qn∗ and lexicographically as good a reply ∗ 0 1 against (qm , qm , qm ) as other strategies in Pn1 . Let ψ : Q → P be the natural projection, i.e. ψ(q ∗ , (p0 , p1 ), π 1 ) = (p0 , p1 ). Let ∂Q = ψ −1 (∂P). The following technical property is proved in Appendix C. Theorem 4.1. (Q, ∂Q) is a pseudomanifold of the same dimension as (P, ∂P). Moreover, the projection map ψ : (Q, ∂Q) → (P, ∂P) is essential iff Q∗ is stable. 1 In case Sn1 is empty (and Sm is not), then the set Π1n is empty. We set P = P 0 × Pm1 . 1 Points in Q are of the form (q 0 , p0 , πm ) and we drop the optimality requirement (iii) for n. 5. Statement and Proof of the Theorem We now state and prove the main theorem. We assume that a solution is represented in terms of enabling strategies, i.e. Q∗ ⊂ P is a solution iff it is the image under ρ of a solution Σ∗ ⊂ Σ. Theorem 5.1. Axioms A, B, S imply that each solution is an essential component of the game’s undominated equilibria. 6Alternatively, as noted by Mertens [21], one can apply the definition of stability directly to Q∗ as a component of equilibria, represented in terms of enabling strategies, over the space of perturbations of players’ enabling strategies. 7Lexicographically optimal replies are defined by Blume, Brandenburger, and Dekel [1] and Govindan and Klumpp [2]. 14 SRIHARI GOVINDAN AND ROBERT WILSON Proof. Let Q∗ ⊂ P be a solution. Let deg(ψ) be the degree of the projection map ψ : (Q, ∂P ) → (P, ∂P) defined in Section 4.5 above. Let q 0,∗ be an arbitrary point in Q∗ . For 0,∗ 0 is a best reply. Such a each m, choose a point p0,∗ m in the interior of Pm against which q choice is possible by genericity of payoffs: the interior of the projection of Σ̄∗m belongs to the interior of Pm0 and all strategies in Pn1 are inferior replies against every such point. Since qn0,∗ belongs to Q∗n , which consists only of undominated (hence admissible) strategies, there exists a point pm in the interior of Pm against which qn0,∗ is a best reply. pm is equivalent 0 to a completely mixed strategy σm in Σm . Express σm as a convex combination of σm and 1 i i 0 1,∗ σm , where for i = 0, 1, σm belongs to the interior of Σm . Let pm and pm be the enabling 0 1 strategies that are equivalent to σm and σm , respectively. Then p0m and p1,∗ m are in the relative 0 1 0 interiors of Pm and Pm respectively, and pm is a convex combination of pm and p1,∗ m . It follows ∗ 0,∗ 0,∗ 1,∗ 1,∗ 1,∗ 1 1 that x ≡ (q , (p , p ), π ) belongs to Q \ ∂Q, where for each n, πn = π̄n (pn ), and in 1 1 the definition of Q, qn0 is p0,∗ n and qn is pn . For any neighborhood U (q 0,∗ ) of q 0,∗ we can choose a neighborhood U (x∗ ) of x∗ that is homeomorphic to a simplex, is contained in Q \ ∂Q and such that the projection onto the first factor is contained in the neighborhood U (q 0,∗ ), i.e. if (q 0 , (p0 , p1 ), π 1 ) ∈ U (x∗ ) then q 0 ∈ U (q 0,∗ ). For the proof we construct a metagame such that: (i) if deg(ψ) is zero then there is no quasi-perfect equilibrium of the metagame projecting to an equilibrium in Q∗ ; and (ii) if deg(ψ) is nonzero then all its quasi-perfect equilibria that project to points in Q∗ , project to points in U (q 0,∗ ). Since U (q 0,∗ ) is an arbitrary neighborhood of the arbitrary point q 0,∗ in Q∗ , this proves the theorem. 5.1. Preliminaries. Fix some p̄ in the interior of P and define ι : ∂P → ∂P as follows: ι(p) is the unique point in the boundary of the form λp + (1 − λ)p̄ for λ < 0. Then ι has no fixed point. Let g∂Q : ∂Q → P be the function ι ◦ ψ∂Q , where ψ∂Q is the restriction of ψ to ∂Q. Then g∂Q has no point of coincidence with ψ, i.e., for each x ∈ ∂Q, g∂Q (x) 6= ψ(x). Let d be the dimension of P and let α be the degree of ψ. If α = 0 then, since ι is a homeomorphism, ∗ (1) = 0 in H δ (Q, ∂Q), where i : ∂Q → Q is the inclusion map, 1 is the generator δ ∗ i∗ g∂Q of H d−1 (P) ≈ Z, and δ ∗ is the coboundary operator. By the Hopf Extension Theorem [29, Corollary 8.1.18], g∂Q can be extended to a map g : Q → ∂P. Obviously g has no point of coincidence with ψ. If α 6= 0 then construct a map g∂U (x∗ ) from ∂U (x∗ ) to ∂P of degree ∗ δ ∗ ∗ ∗ α such that δ ∗ i∗ g∂Q∪∂U (x∗ ) (1) = 0 in H (Q \ (U (x ) \ ∂U (x )), ∂Q ∪ ∂U (x )), where now i : (∂Q ∪ ∂U (x∗ )) → Q \ (U (x∗ ) \ ∂U (x∗ )) is the inclusion map and δ ∗ is the coboundary operator. Using again the Hopf Extension Theorem, there exists a map g∂U (x∗ ) such that the two maps g∂Q and g∂U (x∗ ) can be extended to a map from Q \ (U (x∗ ) \ ∂U (x∗ )) to P; AXIOMATIC EQUILIBRIUM SELECTION 15 furthermore, by mapping points in U (x∗ ) to P in a way that extends g∂U (X ∗ ) , we obtain a map g : Q → P such that all its points of coincidence with ψ, of which there is at least one, are contained in U (x∗ ) \ ∂U (x∗ ). By construction there exists α > 0 such that for all x ∈ Q, kg(x)−ψ(x)k 6 α iff α 6= 0 and x ∈ U (x∗ ). Choose a triangulation Kni of Pni for each n and i = 0, 1 such that the diameter of each simplex is no more than α/2. For each n there exists for each i a triangulation Lin of Pni 1 and a triangulation LΠ n of Πn such that, letting L be the resulting multisimplicial subdivision of P 0 ×P×Π1 , g has a multisimplicial approximation g̃ [9, Appendix B] with the triangulation Q of the range given by K = n,i Kni . Observe that if for some x = (q 0 , p0 , p1 , π 1 ) there exists a multisimplex K that contains ψ(x) and g̃(x) then, since g̃ is a multisimplicial approximation of g, that multisimplex is a face of one that contains g(x) and thus kg(x) − ψ(x)k 6 α; in particular, if x also belongs to Q, then x ∈ U (x∗ ), and thus q 0 ∈ U (q 0,∗ ). As in [9, Theorem B.2], now take a further polyhedral subdivision T of L and let γ be the convex function generated by T , i.e. γ is piecewise linear and linear precisely on each full-dimensional polyhedron of the subdivision. Hereafter, unless explicitly stated, we represent players’ pure and mixed strategies in terms of the induced enabling strategies; thus, pure strategies in Sn are represented as vertices of Pn and mixed strategies are mixtures of these vertices. 5.2. A Game with Redundant Strategies. We first construct a game with redundant pure strategies that is the basis for the metagame specified later. For each fixed p̂ = (p0 , p1 ) ∈ P and δ ∈ (0, 1), consider the following game Γ(δ, p̂). Each player n chooses a strategy in the following manner (and unaware of his opponent’s choices). Initially, player n provisionally chooses a pure strategy s0n ∈ Sn0 , or he rejects all strategies in Sn0 . • If initially he chooses a strategy s0n then at a subsequent second stage he can retain s0n or revise his choice. At this second stage the revisions available are ‘duplicate’ pure strategies in a set Tn0 (δ, p0n ), each of which is a mixed strategy of the form tn (δ, p0n ) ≡ (1 − δ)tn + δp0n for some tn ∈ Sn0 . • If he rejects all strategies in Sn0 then at a second stage he can choose among the strategies in Tn0 (δ, p0n ) or reject them all.8 If he rejects them all then at a third stage he chooses among the pure strategies in Sn1 ∪ Tn1 (δ, p1n ), where each strategy in Tn1 (δ, p1n ) is a duplicate of the form tn (δ, p1n ) ≡ (1 − δ)tn + δp1n for some tn ∈ Sn0 . 8It would have sufficed, at this stage, to give player n the option of playing just the strategy p0n instead of all the strategies in Tn0 (δ, p0n ), which we do only for economy in notation. 16 SRIHARI GOVINDAN AND ROBERT WILSON In Γ(δ, p̂) the set of n’s pure strategies is S̃n (δ, p̂n ) ≡ Sn ∪ Tn0 (δ, p0n ) ∪ Tn1 (δ, p1n ). Thus, game Γ(δ, p̂) has the same reduced normal form as Γ. 5.3. Extensive Form of the Metagames. Now we specify a family of similar metagames Γ̃δ , one for each δ > 0. Before the insiders play, thirteen outsiders, denoted players o0 and oin,j for n = 1, 2, i = 0, 1 and j = 1, 2, 3, move simultaneously. Outsider o0 chooses a full-dimensional polyhedron T of the polyhedral complex T . Outsider oin,j , for n = 1, 2, j = 1, 3 and i = 0, 1, chooses a point in the vertex set Vni of Kni . Outsider o0n,2 chooses a point in a finite subset Sn0,δ of Pn0 chosen such that every point in Pn0 is within δ of some point in Sn0,δ ; outsider o1n,2 chooses a point in a finite subset Sn1,δ of Π1n such that every point in Π1n is within δ of some point in Sn1,δ . For outsider oin,1 , each pure strategy vni corresponds to a point in Pni denoted pin (vni ). i i Therefore, each mixed strategy σn,1 corresponds to a point in Pni , denoted pin (σn,1 ), which is obtained by taking the appropriate average of the points induced by the pure strategies in i 0 0 the support of σn,1 . Likewise a mixed strategy σn,2 of o0n,2 corresponds to a point qn0 (σn,2 ) in 1 1 ) in Π1n . of o1n,2 corresponds to a point πn1 (σn,2 Pn0 , and a mixed strategy σn,2 A mixed-strategy profile σ̃o for the outsiders induces a point (q 0 (σ̃o ), (p0 (σ̃o ), p1 (σ̃o )), π 1 (σ̃o )) in P 0 × P × Π1 , where for each n and i, pin (σ̃o ) depends on the choice by oin,1 , and qn0 (σ̃o ) and π̄n1 (σ̃o ) depend on the choices by o0n,2 and o1n,2 respectively. After each pure-strategy profile s̃o of the outsiders there follows a copy of the game Γ(δ, p̂(s̃o )). That is, if in the profile s̃o outsiders oin,1 choose points vni , then there follows a copy of Γ(δ, p̂) after these choices, where for each n, p̂n = (p0n (vn0 ), p1n (vn1 )). However, the information sets in Γ̃δ are such that the insiders play without knowing which copy of Γ(δ, p̂) they are playing. The sets of duplicate strategies available are therefore now denoted by Tn0 (δ) and Tn1 (δ), omitting the reference to p0n and p1n , since the insiders are uninformed about which mixtures were implemented by outsiders. Put differently, for i = 0, 1 and tn ∈ Sn0 , the exact duplicate strategy implemented by choosing tin (δ) ∈ Tni (δ) depends on the choice by the outsider oin,1 that insiders do not observe. Thus in the metagame Γ̃δ , player n’s set of pure strategies, up to duplication of pure strategies, is S̃n (δ) ≡ Sn ∪ Tn0 (δ) ∪ Tn1 (δ). That the metagame Γ̃δ embeds Γ follows from Proposition 3.3. The strategies in Sn are available as pure strategies in S̃n (δ) and the other pure strategies, which belong to Tni (δ), for i = 0, 1, implement mixtures in Σn that depend on the choices of outsiders oin,1 . AXIOMATIC EQUILIBRIUM SELECTION 17 5.4. Outsiders’ Payoffs in the Metagames. Next we describe the outsiders’ payoffs in each metagame Γ̃δ . The payoffs to o0 depend on the choices of all outsiders except outsiders oin,3 for i = 0, 1 and n = 1, 2. Recall that the convex function γ is linear over each full-dimensional polyhedron T of T . This linear function extends uniquely to a linear function γT over P 0 × P × Π1 . Every mixed strategy profile of the other outsiders induces a unique point (q̃, p̂, π 1 ) ∈ P 0 × P × Π1 and o0 ’s payoff from choosing T is γT (q̃, p̂, π 1 ). Outsider oin,1 wants to mimic oin,3 . In particular, if he chooses vni and oin,3 chooses wni then his payoff is one if vni = wni and zero otherwise. Outsider o0n,2 wants to mimic the actual choice implemented by player n when this choice belongs to Pn0 . Similarly, outsider o1n,2 wants to mimic the πn1 implied by n’s choice when he i plays a strategy in Pn1 . Specifically, for i = 0, 1, let ϕin : RZn → R be the function given by P i ϕin (r) = z∈Zni rz2 . For each r ∈ RZn , let ξni (r, ·) be the affine approximation to ϕin at r, i.e. P i for each r′ ∈ RZn , ξni (r, r′ ) = z (rz2 + 2rz (rz′ − rz )). Suppose now that oin,2 chooses a pure 1 0 strategy si,δ n,2 and n chooses a pure strategy s̃n in S̃n (δ). If s̃n is in Tn (δ) or Tn (δ) then let qn be the actual strategy in Pn that is implemented based on p0n (vn0 ) or p1n (vn1 ) where for each i, vni is the choice of outsider oin,1 ; and otherwise let qn = s̃n . For outsider o0n,2 , his payoff is 0 1 zero if qn ∈ / Pn0 ; otherwise, it is ξn0 (s0,δ n,2 , qn ). For outsider on,2 , his payoff is zero if qn ∈ Pn ; 1 otherwise it is ξn1 (s1,δ n,2 , π̄n (qn )). The payoff to outsider oin,3 depends on the choices of all other outsiders. If o0 chooses a polyhedron T then there exists a unique multisimplex L of L that contains T . For each vertex wni of Vni , and each vertex ṽ of L, let uin,2 (T, ṽ, wni ) = 1 if wni is the image of ṽ under g̃ni and zero otherwise, where g̃ni is the (n, i)-th coordinate map of g̃. The function uin,2 extends multilinearly to L and, since L is full-dimensional, to the whole of P 0 × P × Π1 , denoted still by uin,2 (T, ·, wni ). Given an arbitrary mixed strategy of the other players, if o0 chooses T and oin,2 chooses wni then the payoff of oin,2 is uin,2 (T, (p, q), wni ), where (p, q) is the point in P 0 × P × Π1 induced by the mixed strategies of the other players. 5.5. Outsiders’ Strategies in a Quasi-Perfect Equilibrium. If Q∗ is a solution of Γ then, by Axioms B and S, in the metagame Γ̃δ there exists a quasi-perfect equilibrium b̃δ whose equivalent mixed-strategy profile σ̃ δ belongs to a solution and whose image under the map from the metagame Γ̃δ to Γ is a point in Q∗ . Each player n’s strategy in b̃δ necessarily has the following feature. He avoids going to his information set where his choices are among the strategies in Sn1 (δ) ∪ Tn1 (δ), since each of 18 SRIHARI GOVINDAN AND ROBERT WILSON these strategies chooses a non-equilibrium action at some information set on the equilibrium path. Let qn0,δ be n’s actual strategy in Pn0 that is implemented by n’s strategy in the profile b̃δ in the metagame Γ̃δ . By construction, qn0,δ belongs to Q∗n . Let x̃δ ≡ (q̃ 0,δ , p0,δ , π̃ 1,δ ) be the point in P 0 × P × Π1 that is induced by the profile σ̃oδ of the outsiders’ strategies in the equilibrium σ̃ δ . Under b̃δ , after n has rejected all strategies in Sn0 and Tn0 (δ), consider the strategy implemented by n. Let (1 − αn1,δ ) be the total probability of choosing a duplicate in Tn1 (δ) under b̃δ . Then n’s choice at this information set is equivalent to an enabling strategy in Pn of the form 1,δ 1,δ 1,δ q̌nδ ≡ (1 − αn1,δ )((1 − δ)p̌0,δ n + δpn ) + αn rn , where: (i) p̌0n (δ) is the mixture over strategies tn such that the strategy t1n (δ) is played i i with positive probability at this information set; (ii) p1,δ n = pn (σ̃n,1 ) is the enabling strategy i of outsider oin,1 ; (iii) rn1,δ is the enabling strategy in induced by the equilibrium strategy σ̃n,1 Pn1 that is obtained from n’s actual mixture over strategies in Sn1 if αn1,δ > 0, and is arbitrary otherwise. Let −1 1,δ 1,δ q 1,δ = (δ(1 − αn1,δ ) + αn1,δ ) (δ(1 − αn1,δ )p1,δ n + αn rn ) . Then π̄n1 (q̌nδ ) = π̄n1 (qn1,δ ) ≡ πn1,δ . The following lemma characterizes the important aspects of the outsiders’ equilibrium strategies. Lemma 5.2. The equilibrium strategies of the outsiders satisfy the following properties. (1) For each n, suppose the vertices in the support Vni,δ of oin,3 ’s equilibrium strategy span a simplex Kni,δ of Kni . Then pni,δ belongs to Kni,δ . (2) If every polyhedron in the support of o0 ’s strategy contains x̃δ then, for each n and i, the vertices in Vni,δ span a simplex Kni,δ , and g̃n,i (x̃δ ) belongs to the interior of a simplex K̄ni,δ that has Kni,δ as a face. (3) Every polyhedron in the support of o0 ’s strategy contains x̃δ . (4) q̃n0,δ is within δ of qn0,δ and π̃n1,δ is within δ of πn1,δ . Proof of Lemma. Outsider oin,1 wants to mimic outsider oin,3 . So, if the vertices of Vni,δ span a simplex Kni,δ then the payoff to oin,1 from choosing a vertex wni is positive if it belongs to Vni,δ, and zero otherwise. Point (1) follows. Let L̄ = L0 × (L̃0 × L1 ) × LΠ be the unique multisimplex of L that contains x̃δ in its interior. For each polyhedron T in the support of o0 ’s strategy, there exists a full-dimensional multisimplex L̂ of L that contains T . Obviously L̂ has L̄ as a face. oin,3 ’s payoff from choosing AXIOMATIC EQUILIBRIUM SELECTION 19 a strategy wni if o0 chooses such a T , and given the strategies of the other outsiders, is positive if it is the image of a vertex of L̄ under g̃ni and zero otherwise. Since the image of the vertices of L̄ under the coordinate function g̃ni span a simplex K̄ni,δ , g̃ni (x̃δ ) ∈ K̄ni,δ and the vertices of δ span a face of K̄ni,δ . Therefore, point (2) follows. Vn,i For each polyhedron T of T , o0 ’s payoff from T is γT (x̃δ ) and by construction, γT (x̃δ ) 6 γ(x̃δ ) with the inequality being strict iff x̃δ does not belong to T , which proves (3). It remains to prove (4). The actual strategy implemented by n is qn0,δ , which belongs to Pn0 . o0n,2 ’s payoff function is such that his best replies to qn0,δ are the points in Sn0,δ that are closest to qn0,δ . Thus q̃n0,δ is within δ of qn0,δ . Since qn0,δ belongs to Pn0 , all of o1n,2 ’s strategies yield a payoff of zero against qn0,δ . However, since the behavioral strategy b̃δ is a quasi-perfect equilibrium, there exists a sequence of completely mixed behavioral strategies b̃ε,δ converging δ is a best reply. Under the sequence b̃ε,δ , to b̃δ against which o1n,2 ’s equilibrium strategy σ̃n,2 there is a positive probability that player n moves into the third stage of his choice and δ makes a choice among strategies in Sn1 ∪ Tn1 (δ). The fact that σ̃n,2 is optimal against the sequence implies that it is optimal against the limiting choice q̌nδ there. Since π̄n1 (q̌nδ ) = πn1,δ , o1n,2 ’s best replies are within δ of πn1,δ and thus πn1,δ is within δ of πn1,δ as well. ¤ 5.6. Limits of the Quasi-Perfect Equilibria of the Metagames. Consider a sequence of δ’s converging to zero and a corresponding sequence b̃δ of quasi-perfect equilibria in solutions of the metagames Γ̃δ . Let σ̃ δ be an equivalent sequence of mixed strategies and let (q̃ 0,δ , (p0,δ , p1,δ ), π̃ 1,δ ) be the sequence in Q∗ × P × Π1 induced by the outsiders’ strategies. Let q̃ 0,0 , (p0,0 , p1,0 ), and π̃ 1,0 be the corresponding limits of q̃ 0,δ , (p0,δ , p1,δ ), and π̃ 1,δ . Let q 0,0 and π 1,0 be the limits of q 0,δ and π 1,δ . By properties (1)-(3) of the previous lemma, for each δ, n, i, there exists a simplex K̄ni,δ of Kni that contains both g̃n,i (q̃ 0,δ , (p0,δ , p1,δ ), π̃ 1,δ ) and pi,δ n , with the former belonging to its interior. By property (4) of the previous lemma, q̃ 0,0 = q 0,0 and π̃ 1,0 = π 1,0 . By passing to a subsequence, we can assume that there exist multisimplices L̄ of L and K̄ of K such that for all δ, (q̃ 0,δ , (p0,δ , p1,δ ), π̃ 1,δ ) belongs to the interior of L̄ and its image under g̃ belongs to the interior of K̄—hence K̄ also contains (p0,δ , p1,δ ). Going to the limit, (q 0,0 , (p0,0 , p1,0 ), π 1,0 ) belongs to L̄ and its image under g̃ belongs to K̄; also (p0,0 , p1,0 ) belongs to K̄. Since L̄ and K̄ are multisimplices and g̃ is a multisimplicial map, we have that for all δ, xδ ≡ (q 0,0 , (p0,δ , p1,0 ), π 1,0 ) belongs to L̄, and g̃(xδ ), (p0,δ , p1,0 ) ∈ K̄. If we show that for small δ, xδ belongs to Q, then by construction this implies that the degree of ψ is nonzero and xδ ∈ U (x∗ ), and therefore q 0,0 ∈ U (q 0,∗ ), which proves the theorem. The remainder of the proof establishes this fact. 20 SRIHARI GOVINDAN AND ROBERT WILSON 5.7. Insiders’ Strategies in a Quasi-Perfect Equilibrium. Let b̃ε,δ be a sequence of completely mixed behavioral strategies converging to b̃δ against which for each insider n and each information set of n in Γ̃δ , his continuation strategy is optimal. We now study the important features of both the sequence and its limit. If n chooses sn ∈ Sn0 in the first stage then in the second stage he has the option of revising this strategy to play something in Tn0 (δ). Therefore, quasi-perfection implies that player n will end up implementing sn with positive probability in b̃δn only if this strategy is at least as good a reply against the sequence b̃ε,δ as the strategies in Tn0 (δ). Likewise, player n has the option of playing a strategy in Tn0 (δ) before he decides to play a strategy in Sn1 and even when he makes a choice among these strategies, he has the option of choosing a strategy in Tn1 (δ). Therefore, at the information set that follows his choice of avoiding strategies in Sn0 , b̃δn assigns a positive probability to moving on to a third stage and then choosing a strategy in Tn1 (δ) ∪ Sn1 only if one of these strategies is at least as good a reply against the sequence b̃ε,δ as all the strategies in Tn0 (δ). Furthermore, at the information set obtained after n avoids strategies in Sn0 ∪ Tn0 (δ), b̃δn assigns a positive probability to a strategy sn in Sn1 only if sn is at least as good a reply against the sequence b̃ε,δ as all the strategies in Sn1 ∪ Tn1 (δ). Let σ̃ ε,δ be a sequence of mixed strategy profiles that is equivalent to the sequence b̃ε,δ of behavioral strategy profiles. For each player n, his strategy σ̃nε,δ in the sequence is a mixture over his pure strategy set S̃n = Sn ∪ Tn0 (δ) ∪ Tn1 (δ). However, the implications of n’s strategy (for m’s choices) depend on the choices of the outsiders through their implications for strategies in Tn0 (δ) and Tn1 (δ). Each strategy tin (δ) plays tn with probability (1 − δ) and with probability δ plays a strategy in Pni that is determined by oin,1 ’s strategy. In order to fully capture the impact that oin,1 has on tin (δ), let Wni be the vertex set of Kni . Let T̄ni (δ) be the union over all wni ∈ Wni of the sets Tni (δ, pin (wni )). Let S̄n = Sn ∪ T̄n0 (δ) ∪ T̄n1 (δ) and let Σ̄n be the set of mixtures over S̄n . Since Wni is the pure strategy set of outsider oin,1 , and σ̃ ε,δ is a sequence of completely mixed has Wni as its support for all ε in the sequence. The sequence σ̃ ε,δ induces strategies, σ̃oε,δ i n,1 a mixed strategy σ̄nε,δ in S̄n for each n as follows. For each sn ∈ Sn , the probability σ̄nε,δ (sn ) of sn is σ̃nε,δ (sn ). For each i = 0, 1, wni ∈ Wni and tn ∈ Sn0 , the probability σ̄nε,δ (tin (δ, pin (wni ))) i is σ̃nε,δ (tin (δ))σ̃oε,δ From player m’s perspective it is the sequence σ̄nε,δ , or rather its i (wn ). n,1 equivalent sequence in Pn , that matters for his choice. AXIOMATIC EQUILIBRIUM SELECTION 21 5.8. The Induced Lexicographic Probability System. By Blume, Brandenburger, and Dekel [1, Appendix Proposition 2], we can construct for each player n a lexicographic probl (δ),δ ability system (LPS) Λ̄δn = (σ̄n0,δ , . . . , σ̄nn a subsequence converging to zero, ) over his strategies in S̄n such that for each ε in σ̄nε,δ = (1 − ν0 (ε))(σ̄n0,δ + ν0 (e)((1 − ν1 (ε))σ̄n1,δ + ν1 (ε)((1 − ν2 (ε))σ̄n1,δ + · · · + νln (δ)−1 (ε)σ̄nln (δ),δ )) , l (δ) where (ν0 (ε), . . . , νln (δ)−1 (ε)) is a sequence in R+n converging to the origin. Quasi-perfection implies that σ̄n0,δ is equivalent to the enabling strategy qn0,δ in Γ and it is a lexicographic best reply to Λ̄δm . Let ln0,δ be the first level in Λ̄δn at which some strategy in T̄n0 (δ) appears with positive probability. Let ln1,δ be the first level of Λ̄δn at which some strategy in Sn1 ∪ T̄n1 (δ) appears with positive probability. From the LPS Λ̄δn construct an LPS Λδ = (qn0,δ , . . . , qnln ,δ ) for Γ where for each l, qnl,δ is an enabling strategy in Γ that is equivalent to σ̄nl,δ . qn0,δ is a lexicographic best reply against Λδm . i,δ For each wni ∈ Wni , the total probability under σ̄nln of the strategies in Tni (δ, pin (wni )) is the i,δ i i δ limit σ̃oδi (wni ) of the sequence σoε,δ i (wn ). Since pn (σ̃oi ) is, by definition, pn , we have that n,1 level lni,δ n,1 is expressible as a convex combination n,1 li ,δ λnn pi,δ n li ,δ li ,δ li ,δ + (1 − λnn )rnn with λnn > 0 and li ,δ l1 ,δ rnn ∈ Pn . Since ln1,δ is the first level of Λδ that does not have its support in Pn0 , π̄n1 (qnn ) equals πn1,δ , which recall was computed from n’s strategy under b̃δ in the third stage of his choice. 0,δ We claim that for each l 6 ln0,δ , qnl,δ induces the equilibrium outcome against qm . Indeed, 0,δ ∗ 0 since qm belongs to Q , and the strategies in Tn (δ) always implement some strategy in Pn0 0,δ regardless of the choice of outsider o0n,1 , all the strategies in Tn0 (δ) are optimal against qm . By quasi-perfection, this implies that every strategy in S̄n that appears at a level l 6 ln0,δ of 0,δ 0,δ 0,δ Λ̄δn must be a best reply to qm . Thus for all l 6 ln0,δ , qnl,δ is a best reply to qm . Since qm is δ 0,δ a lexicographic best reply to Λn , (q̃n (ε), qm ) is an equilibrium of the game Γ for all small ε, where 0,δ 0,δ q̃n (ε) = (1 − ε) qn0,δ + ε((1 − ε)qn1,δ + ε2 ((1 − ε)qn2,δ + ε3 (· · · + εln qnln ) . By genericity of payoffs, Γ has finitely many equilibrium outcomes, so each of these equilibria induces the same equilibrium outcome—hence the claim follows. Three implications of this l1 ,δ claim are: (i) ln1,δ > ln0,δ ; (ii) the enabling strategy rnn in the previous paragraph belongs to Pn0 ; (iii) all levels up to ln0,δ prescribe the same mixture at each information set on the equilibrium path and differ only at information sets excluded by (all of) m’s equilibrium strategies in Q̄∗m , which is the ρm -image of the component Σ̄∗m of equilibria. 22 SRIHARI GOVINDAN AND ROBERT WILSON 5.9. Limit of the Lexicographic Probability System. Take a subsequence of the δ’s such that the following properties hold for the associated LPSs Λδn for each n: (i) lni,δ is independent of δ for each i, call it lni ; (ii) for each l 6 ln1 , the face of Pn that contains qnl,δ in its interior, as well as the strategies for m that are best replies to qnl,δ , are independent of δ. l1 ,δ l1 ,δ Let σnn be a sequence of strategies in Σn that is equivalent to the sequence qnn . Again using Blume, Brandenburger, and Dekel [1, Appendix Proposition 2], there is now an LPS l1 ,0 l1 ,kn (σnn , . . . , σnn ) and a sequence (µ0 (δ), . . . , µkn −1 (δ)) ∈ Rkn converging to zero such that for l1 ,δ a subsequence of δ’s, σnn is expressible as the nested combination 1 1 1 1 1 σnln ,δ = (1 − µ0 (δ))(σnln ,0 + µ0 (δ)((1 − µ1 (δ))σnln ,1 + µ1 (δ)((1 − µ2 (δ))σnln ,2 + · · · + µkn −1 (δ)σnln ,kn )) l1 ,kn l1 ,0 This LPS induces an equivalent LPS (qnn , . . . , qnn Let kn1 be the first level k of this LPS where l1 ,δ previous section that qnn l1 ,k qnn ) in enabling strategies. does not belong to Pn0 . Recall from the l1 ,δ l1 ,δ l1 ,δ n n is expressible as a convex combination λnn p1,δ n + (1 − λn )rn l1 ,δ l1 ,δ and that π̄n1 (qnn ) = πn1,δ . Express rnn as a convex combination αn0,δ rn0,δ + αn1,δ rn1,δ , where for l1 ,δ l1 ,k l1 ,d i = 0, 1, rni,δ ∈ Pni . Then λnn + (1 − λnn )αn1,δ > 0 since qnn does not belong to Pn0 . Going to −1 l1 ,δ l1 ,δ l1 ,δ a subsequence, let λ1n be the limit of (λnn + (1 − λnn )αn1,δ ) λnn and let rn1,0 be the limit of l1 ,k1 1,0 n n is expressible as a convex combination rn1,δ . Since the limit of p1,δ n is pn , we have that qn 1 1,0 1 1,0 0 ζn (λn pn + (1 − λn )rn ) + (1 − ζn )p̌n for some ζn > 0 and p̌0n ∈ Pn0 . Moreover, since πn1,0 is 1 l1 ,kn the limit of πn1,δ , π̄n1 (qnn ) = πn1,0 . 1 +1,δ l1 +kn For each δ in the subsequence used above, define now an LPS Λ̂δn = (q̂n0,δ , . . . , q̂nn 1 ,l−l1 −1 ln n follows: q̂n0,δ = qn0,0 , q̂nl,δ = qnl−1,δ if 0 < l 6 ln1 , and q̂nl,δ = qn ) as otherwise. The strategy q̂nl,δ l0 +1,δ is independent of δ for l = 0 and l > ln1 . Each level l < ln1 + kn1 + 1 is a strategy in Pn0 . q̂nn l0 ,δ l0 ,δ l0 ,δ n n is a convex combination λnn p0,δ n + (1 − λn )rn 1 +1,δ l1 +kn while q̂nn 1 +k 1 ,δ ln n 1 1,0 0 1 ζn (λ1n p1,0 n + (1 − λn )rn ) + (1 − ζn )p̌n where ζn > 0 and π̄n (q̂n is a convex combination ) = πn1,0 . The next lemma sets out the key properties of Λ̂δn that lead to a conclusion of our proof. Lemma 5.3. For all small δ, the LPS Λ̂δn satisfies the following properties. (1) A strategy is at least as good a reply against Λδn as another only if it is at least as good a reply against Λ̂δn . 0,0 and is at least as good a reply (2) If λ1n < 1, then the strategy rn1,0 is a best reply to qm lexicographically against Λδm as every strategy in Sn1 . 0,0 . (3) λ1n > 0 and every level l < ln1 + kn1 + 1 induces the equilibrium outcome against qm AXIOMATIC EQUILIBRIUM SELECTION l0 ,δ 23 l0 ,δ (4) The strategy q̂nl,δ for l < ln0 and the strategy rnn if λnn < 1 are lexicographic best δ replies against q̂m . Proof of Lemma. Suppose sm is a better reply against Λ̂δn than another strategy tm . We show that sm is also a better reply against Λδn . Let l be the first level of Λ̂δn such that sm is l,δ than tm . If l = 0 then for all small δ, sm is a better reply against a better reply against q̂m 0,δ 0,δ qn since q̄n equals the limit qn0,0 of qn0,δ ; thus against Λδn , tm is a worse reply against the very first level. If 0 < l < ln1 + 1 then obviously sm is better reply against Λδn than tm since level l of Λ̄δn corresponds to level l − 1 of Λδn . Suppose then that ln1 + 1 6 l 6 ln1 + kn1 + 1. l1 ,δ l1 ,δ Then for all small δ, sm is a better reply against qnn since qnn is a nested combination of l1 ,0 l1 ,kn (qnn , . . . , qnn ). Thus, sm is a better reply against Λδn . This proves (1). In the game Γ̃δ player n, when finally making a choice among the strategies in Sn1 ∪ Tn1 (δ), would choose a strategy sn in Sn1 with positive probability only if it is at least as good a reply against Λδn as the other strategies in Sn1 . Therefore, such a strategy would show up with positive probability under level ln1 of Λ̃δn (and hence in Λ̄δn ) only if this is the case. This l1 ,δ implies that if (1 − µnn )αn1 is positive, then the strategy rn1,δ is at least as good a reply against Λδn as the strategies in Sn1 . Recall that rn1,0 is the limit of rn1,δ and λ1n is the limit l1 ,δ 1 −1 l1 ,δ of (µnn + (1 − µln ,δ )αn1,δ ) µnn . Therefore, by point (1) of this lemma, rn1,0 is at least as good a reply against Λ̂δn as strategies in Sn1 if λ1n < 1. To show that it is also a best reply 0,0 against qm , suppose to the contrary that it is not. Then every strategy in Tn1 (δ), regardless 0,δ of outsider o1n,1 ’s choice, is a better reply against qm for all small δ, since for δ = 0 these 0,0 strategies are in Pn0 , which are best replies to qm . Therefore, quasi-perfection implies that 1 n would prefer to play the strategies in Tn (δ) rather than implementing rn1,0 (or rn1,δ when δ 1 is small), which shows that (1 − µln ,δ )αnl,δ = 0 for all small δ and hence that λ1n = 1. This proves (2). We turn now to (3). Every strategy q̂nl,δ for l < ln1 +kn1 +1 belongs to Pn0 and is thus optimal 0,0 against qm , which belongs to Q∗m . The strategy p̌0n (which recall is part of the expression l1 ,k1 defining qnn n ) which is chosen with positive probability is also in Pn0 and hence optimal 0,0 against qm . As we saw in the previous paragraph, if λ1n < 1, the strategy rn1 must also be 0,0 0,0 0,δ optimal against qm . Obviously qm is optimal against Λ̂δn since it is the limit of qm , which 0,0 , qn (ε)) is an equilibrium by point (1) is optimal against Λ̂δn . Therefore, for all small ε, (qm 24 SRIHARI GOVINDAN AND ROBERT WILSON of Γ, where q̃n (ε) = 1 µ ln1X +kn l ε + (1 − 1λ1n >0 )ε 1 +k 1 +1 ln n l=0 1 ¶−1 µ ln1X +kn εl q̂nl,δ + (1 − 1 1 1 1 1λ1n >0 )εln +kn +1 q̂nln +kn +1 l=0 1 +1 l1 +kn where 1λ1n >0 is the indicator function. This is impossible if λ1n = 0, since q̂nn Pn0 Pn1 . ¶ is a λ1n convex combination of a strategy in and one in Thus > 0. Moreover, since this is a continuum of equilibria, genericity implies that all of them induce the same outcome. Therefore, all strategies at levels preceding ln1 +kn1 +1 induce the equilibrium outcome against 0,0 qm . Lastly we prove (4). By the previous paragraph, all strategies in Pn0 are optimal against 1 1 k,δ q̂m for k 6 lm + km . Thus the optimality of a strategy in Pn0 depends on how it fares against 1 +1 l1 +km q̂mm . If a strategy sn ∈ Sn0 is not optimal against this strategy, then for all small δ, 1 l1 ,km some strategy in Tn0 (δ) is a superior reply to q̂mm regardless of what outsider o0n,1 ’s choice is. Thus, such a duplicate strategy is a better reply against Λδm than sn . Therefore, in the quasi-perfect equilibrium of Γδ , player n when given a choice of actually implementing sn will prefer this duplicate strategy in Tn0 (δ), i.e. the probability of sn is zero for all l 6 ln0 in Λδn . Point (4) now follows. ¤ 5.10. Final Step of the Proof. Fix a small δ that satisfies the properties enumerated in Lemma 5.3 of the previous subsection. Let µ X ¶−1 µ X ¶ 0 l l l,δ q̄n (ε) = ε ε q̂n 0 +1 l6ln 0 +1 l6ln 1 1 µ ln1 +k ¶−1 µ ln1 +k ¶ n +1 n +1 X X 1 l l l,δ q̄n (ε) = ε ε q̂n . 0 +2 l=ln 0 +2 l=ln Observe that q̄n0 (ε) belongs to Pn0 for all ε and it is a convex combination of p0,δ n and a subset Rn0 of strategies that are at least as good replies against Λ̂δm as other strategies in Sn0 . Likewise q̄n1 (ε) is a convex combination of p1n , rn1 and a point in Pn0 such that the strategy rn1 if it has a positive weight is at least as good a reply against Λ̂δm as other strategies in Pn1 . There exists a small ε such that a strategy sm is at least as good as a strategy tm against Λ̂δn iff it is lexicographically at least as good a reply against the LPS (q 0 , q̄n0 (ε), q̄n1 (ε)). Since π̄n1 (q̄n1 (ε)) = π̄n1 (qn1,0 ) = π 1,0 for all ε, it follows that (q 0 , (p0,δ , p1,0 ), π 1,0 ) belongs to Q. As we noted earlier, proving that this point belongs to Q shows that in fact it belongs to U (x∗ ) and hence that q 0 in U (q 0,∗ ), which completes the proof. ¤ AXIOMATIC EQUILIBRIUM SELECTION 25 Remark 5.4. In the case where Sn1 is empty for exactly one player n, as we said initially in the description of P and Q, we do not have the factor Pn1 or Π1n . In the family of games Γ(δ, p̂), player n decides provisionally in the first stage on the strategy in Sn to play and in the second stage gets to execute it or switch to playing a strategy in Tn (δ, p̂). In the metagame, we do not have outsiders o1n,j for j = 1, 2, 3. The rest of the analysis is essentially the same modulo these provisions. 6. Concluding Remarks Like our previous paper [10] on forward induction, the characterization in this paper is a step toward a theory of equilibrium refinement using axioms adapted from decision theory. Theorem 5.1 is confined to games in extensive form with perfect recall, two players, and generic payoffs, but it suggests that an extension to more general games might be possible. We hope also that Axiom B can be weakened to require only that a solution contains a sequential equilibrium for which each player’s strategy is conditionally admissible from each of his information sets—thus keeping the axioms entirely within standard decision theory. Previously, some proposed refinements selected equilibria with one or more desirable properties, like admissibility, subgame perfection, or sequential rationality. Other proposed refinements derived some properties from limits of equilibria of perturbed games, such as perfect, quasi-perfect, and proper equilibria. In the latter approach, a key step forward was Kohlberg and Mertens’ [14] argument that an axiomatic development requires set-valued refinements. Their program achieved remarkable success with Mertens’ [19] definition of a stable set, which has the desirable properties 1, 2, 3 listed in Section 1 and others too, such as ordinality and immunity to splitting players into agents. However, an axiomatic theory of refinement should be based on basic principles of rational behavior in the game at hand, as in decision theory. This precludes reliance on perturbed games obtained by perturbing players’ sets of feasible strategies. The challenge, therefore, has been to establish why consideration of perturbed games yields the requisite decisiontheoretic properties. Our answer here begins with Axiom S, which generalizes the invariance criterion of Kohlberg and Mertens’ [14] and the small worlds criterion of Mertens’ [21], as explained in Section 3.3. Absent a strong invariance property like Axiom S, a refinement is vulnerable to ‘framing effects’ depending on wider contexts in which the given game might be embedded. In decision theory, such effects were examined by Savage [28], and in cognitive psychology they play a prominent role in interpreting decisions by subjects in experiments, as for instance in Kahneman and Tversky [13]. For a theory of thoroughly rational behavior, however, an 26 SRIHARI GOVINDAN AND ROBERT WILSON axiom should exclude framing effects. Axiom S does this by requiring a solution of a game to be consistent with the solution of any metagame in which it is embedded. As shown in Proposition 3.4, it is already true of any equilibrium that it is consistent with an equilibrium of any metagame in which the game is embedded. Axiom S merely extends to refinements this fundamental invariance property of equilibria. Our answer continues with the proof of Theorem 4.1 in Appendix B. There it is shown that a set Q∗ of equilibria in enabling strategies is stable iff the corresponding projection map from the pseudomanifold Q to the space P of enabling strategies is essential. Using this key property, the proof of Theorem 5.1 shows that for each equilibrium in a component of undominated equilibria there exists a corresponding metagame for which the equilibrium is the image of a quasi-perfect equilibrium in the metagame if and only if the projection map is essential. Hence Axioms A, B, S imply that a solution is a stable set, and conversely due to Mertens’ previous proofs. The answer to the ‘why’ question above is thus that, given Axioms A and B, stability with respect to perturbed games is equivalent to an analogous ‘stability’ with respect to embeddings in metagames, as required by Axiom S. Because in practice every game is embedded in some wider context, we view Axiom S’s requirement that a refinement is immune to presentation effects as the relevant criterion from the perspective of decision theory. This view is reinforced by the facts that Nash equilibria satisfy Axiom S, and that together with Axioms A and B, the implied refinement agrees with stability based on perturbed games. For a refinement satisfying the axioms, Theorem 5.1 establishes that a solution of a game must be a component of its undominated equilibria, and that the component must be essential. Because payoffs are assumed to be generic, all equilibria in the component have the same paths of equilibrium play and thus the same distribution of outcomes. Therefore the main implication for equilibrium refinements is that a predicted outcome distribution should result from equilibria in an essential component of undominated equilibria, and in particular, from the sequential equilibria it necessarily contains. A secondary implication is that after deviations from equilibrium play, the continuations of all equilibria in the component remain admissible and sequentially rational, where those that are not sequential equilibria of the original game are justified by beliefs induced by quasiperfect equilibria of corresponding metagames that embed the given game. This provides one resolution of the conundrum posed by Reny [25, 26, 27]. AXIOMATIC EQUILIBRIUM SELECTION 27 1 2 1 a b 1 2 c e 1 — 2: ac aef bd bgh ab a a b b cdeg c e d g cdfh c f d h d f g h Figure 1. A game tree and its pure reduced normal form in which each pure strategy is identified by the terminal nodes it does not exclude. Appendix A. Enabling Strategies In the normal-form representation of a game in extensive form, a player’s pure strategy specifies the action chosen at each of his information sets in the game tree. However, outcomes are not affected by a strategy’s actions at information sets excluded by his previous actions. One therefore considers equivalence classes of pure strategies. Say that two pure strategies are outcome equivalent if the sets of terminal nodes they do not exclude are the same. For instance, the game in Figure 1 is shown on the left side in extensive form and on the right side in the ‘pure reduced normal form’ (PRNF) introduced by Mailath, Samuelson, and Swinkels [18]. In the PRNF, each outcome-equivalent class of player 1’s pure strategies is identified by the terminal nodes it does not exclude, as indicated by labels of rows along the left side; and each equivalence class of player 2’s pure strategies is identified by the terminal nodes it does not exclude, as indicated by labels of columns along the top. Because this game has no moves by Nature, each row and column determine a unique outcome that is the intersection of the row and column labels, shown as the corresponding entry in the matrix. A similar example is shown in Figure 2 for the game tree of a signaling game. In this case, each profile of pure strategies determines a pair of outcomes such that the first or second outcome occurs depending on whether Nature’s initial move is up or down. For instance, the outcome of 1’s strategy abcd and 2’s strategy aceg is a with probability p and c with probability 1 − p. Say that a terminal node that is not excluded is an enabled outcome. A pure strategy of a player enables outcome z if it chooses all his actions on the path to z. A player’s mixed strategy randomizes over his pure strategies, whereas a behavioral strategy randomizes over 28 SRIHARI GOVINDAN AND ROBERT WILSON a e 1 b f p 2 2 1−p c d 1 g 1—2: aceg acfh bdeg abcd ac ac bd abgh ag ah bg efcd ec fc ed efgh eg fh eg bdfh bd bh fd fh h Figure 2. The game tree of a signaling game and its pure reduced normal form in which each pure strategy is identified by the terminal nodes it does not exclude. actions at each of his information sets. A strategy of either kind induces a probability distribution over outcome-equivalent classes of his pure strategies, and thus a distribution over enabled outcomes. Such a distribution is called an enabling strategy. A point pn ∈ [0, 1]Z is an enabling strategy for player n if it is the distribution over enabled outcomes induced by some mixed or behavioral strategy, i.e. pn (z) is the mixed strategy’s probability of those pure strategies that enable outcome z. The vertices of the polyhedron Pn of n’s enabling strategies correspond to outcome-equivalent classes of n’s pure strategies in the PRNF, as in Figures 1 and 2. Enabling strategies are minimal representations of strategic behavior in games with perfect recall.9 Let p∗ (z) be the probability that Nature’s strategy enables outcome z, which is 1 if Nature Q has no moves. Then for each profile p ∈ P = n Pn of players’ enabling strategies, the Q probability that outcome z results is γz (p) = p∗ (z) n pn (z), because Nature and the players randomize independently. The extensive form is therefore summarized by the multilinear function γ : P → ∆(Z) ⊂ RZ that assigns to each profile of players’ enabling strategies a distribution over terminal nodes, including the effect of Nature’s enabling strategy. Player P n’s expected payoff is Gn (p) = z γz (p)un (z). The game Γ is therefore summarized by the multilinear function G : P → RN that assigns to each profile of players’ enabling strategies their expected payoffs. This summary specification is called the enabling form of the game. Appendix B. Proofs of Propositions B.1. Proof of Proposition 3.3. A multilinear map fn : Σ̃n × Σo → Σn is completely specified by its values at profiles of pure strategies. We use fˆn to denote the restriction of fn to the set S̃n × So of profiles of pure strategies. 9Mertens [21, p. 554] introduces the mapping of mixed strategies to induced distributions on terminal nodes. Koller and Megiddo [15] call them realization plans. AXIOMATIC EQUILIBRIUM SELECTION 29 Proposition B.1. G̃ embeds G via a collection of multilinear maps f = (fn )n∈N if and only if for each player n there exists T̃n ⊆ S̃n and a bijection πn : T̃n → Sn such that for each (s̃, so ) ∈ S̃ × So and t̃n ∈ T̃n : (1) fˆn (t̃n , so ) = πn (t̃n ), (2) G̃n (s̃, so ) = Gn (fˆ(s̃, so )), where fˆ = (fˆn )n∈N . Proof. Suppose we have a game G̃ : Σ̃ × Σo → RN ∪ o and a collection of multilinear maps fn : Σ̃n × Σo → Σn , one for each n ∈ N , such that conditions (1) and (2) of the proposition are satisfied. Then, by condition (1) and multilinearity of fn for each n, for each fixed σo , fn (·, σo ) is surjective because it maps the face spanned by T̃n homeomorphically onto Σn . Also, condition (2) and multilinearity of each fn imply that G̃ = G ◦ f . According to Definition 3.2, therefore, (G̃, f ) embeds G. Now suppose that (G̃, f ) embeds G. Let σo be a profile of completely mixed strategies for outsiders. Because fn is multilinear it induces a linear mapping fn (·, σo ) from Σ̃n to Σn that, by the definition of an embedding, is surjective. Hence, for each sn ∈ Sn there exists a pure strategy t̃n (sn ) in S̃n that is mapped to sn by this linear map. We claim that fn (t̃n (sn ), so ) = P sn for all so ∈ So . Indeed, observe that fn (t̃n (sn ), σo ) = so fn (t̃n (sn ), so )σo (so ), where for each so , σo (so ) is the probability of so under σo . Therefore, since σo is completely mixed, if fn (t̃n (sn ), so ) 6= sn for some so then fn (t̃n (sn ), σo ), which is an average of values at vertices of So , cannot be sn . Thus, fn (t̃n (sn ), so ) = sn for all so . Let T̃n ⊂ S̃n be a collection comprising a different pure strategy t̃n (sn ) for each sn ∈ Sn and let πn be the associated bijection. Define fˆn : S̃n × So → Σn by fˆn (s̃n , so ) = fn (s̃n , so ). Then conditions (1) and (2) of the proposition are satisfied. ¤ B.2. Proof of Proposition 3.4. Proposition B.2. If (G̃, f ) embeds G then the equilibria of G are the f -images of the equilibria of G̃. Proof. Suppose (σ̃, σo ) is an equilibrium of G̃ and let σ = f (σ̃, σo ). For any insider n and his strategy τn ∈ Σn there exists τ̃n ∈ Σ̃n such that fn (τ̃n , σo ) = τn because fn (·, σo ) is surjective by condition (a) of Definition 3.2 an embedding. Using condition (b), Gn (τn , σ−n ) = Gn (f (τ̃n , σ̃−n , σo )) = G̃n (τ̃n , σ̃−n , σo ) 6 G̃n (σ̃, σo ) = Gn (f (σ̃, σo )) = Gn (σ) , where the inequality obtains because (σ̃, σo ) is an equilibrium of G̃. Hence σ is an equilibrium of G. 30 SRIHARI GOVINDAN AND ROBERT WILSON Conversely, suppose σ is an equilibrium of G. For each n, let πn be the bijection given by Proposition 3.3. Let σ̃n be the strategy for insider n in G̃ defined by σ̃n (t̃n ) = σn (πn (t̃n )) for t̃n ∈ T̃n and σ̃n (s̃n ) = 0 for s̃n ∈ / T̃n . Since fn is multilinear, by condition (1) of Proposition 3.3, fn (σ̃n , ·) = σn and thus f (σ̃, ·) = σ. Hence, it suffices to show that there exists a strategy profile σo for outsiders such that (σ̃, σo ) is an equilibrium of G̃. By fixing the profile of insiders’ strategies to be σ̃ one induces a game among outsiders. Let σo be an equilibrium of this induced game among outsiders. To see that (σ̃, σo ) is an equilibrium of G̃, observe that for each pure strategy s̃n of an insider n: G̃n (s̃n , σ̃−n , σo ) = Gn (fn (s̃n , σo ), σ−n ) 6 Gn (σ) = Gn (f (σ̃, σo )) = G̃n (σ̃, σo ) , where the first and second equalities use the property f (σ̃, ·) = σ established above, and the inequality obtains because σ is an equilibrium of G. ¤ Appendix C. Proof of Theorem 4.1 Theorem C.1. (Q, ∂Q) is a pseudomanifold of the same dimension as (P, ∂P). Moreover, ψ : (Q, ∂Q) → (P, ∂P) is an essential map iff Q∗ is stable. Proof. The proof invokes genericity of payoffs by assuming that certain points and polyhedra, identified as they arise during the proof, are in general position. See Appendix D for elaboration of the character of these genericity requirements. For any set X, we write d(X) for its dimension. For any subset Tn of Sn , let Pn (Tn ) be the convex hull (in Pn ) of the strategies in Tn . For simplicity, we write d(Tn ) for d(Pn (Tn )). See Sections 4.4 and 4.5 for additional notation used below. For any vertex πn1 of Π1n , let Sn1 (πn1 ) be the set of pure strategies that map to πn1 . For any face Ψ1n of Π1n , let Sn1 (Ψ1n ) be the set of strategies s1n such that π̄n1 (s1n ) ∈ Ψ1n . Let Hn0 be the set of information sets hn ∈ Hn \ Hn∗ of player n such that at the last information set h′n ∈ Hn∗ that precedes hn , the action there leading to hn belongs to A∗n , which is the set of his equilibrium actions. If a subset Tn0 of Sn0 is such that Pn (Tn0 ) contains an equilibrium in Q̄∗n , then for each first information set hn ∈ Hn0 there exists a strategy in Tn0 that enables hn . Let Hn1 = Hn \ (Hn∗ ∪ Hn0 ). Lemma C.2. Suppose Tn0 is a subset of strategies in Sn0 such that Pn (Tn0 ) contains an equilibrium qn∗ in Q̄∗n . If the strategies in Tn0 are at least as good replies against p0m ∈ Pm0 as other strategies in Sn0 , then all the strategies in Sn0 are equally good replies against p0m . ∗ Proof. Let Π∗n be the projection of Pn0 to RZ , where Z ∗ is the set of terminal nodes reached 0 . Consequently, the with positive probability under the equilibria in Q̄∗ . Then Z ∗ = Zn0 ∩ Zm AXIOMATIC EQUILIBRIUM SELECTION 31 payoff to a strategy s0n against p0m depends on s0n only through its projection to Π∗n . Since the projection of qn∗ —which is at least as good a reply as the other strategies in Sn0 against p0m —belongs to the relative interior of Π∗n , every strategy in Sn0 is a best reply against p0m . ¤ Lemma C.3. Suppose that Tn0 is a subset of Sn0 such that Pn (Tn0 ) is a face of Pn0 containing an equilibrium strategy in Q̄∗n . For each tn ∈ / Tn0 there exists an information set hn ∈ Hn0 that tn enables and where the action chosen by it is avoided by all t0n ∈ Tn0 that enable hn . Proof. Since Pn (Tn0 ) is a face of Pn0 , which is itself a face of Pn , there exists a linear function f : RZ → R that is zero on Pn (Tn0 ) and negative everywhere else on Pn . Fix pm in the interior of Pm and define a payoff function ũn for n by the equation: p0 (z)pm (z)ũn (z) = f (ez ) where ez is the z-th unit vector in RZ . Then when n’s payoff function is ũn , the strategies in Pn (Tn0 ) are the best replies against pm . Take tn ∈ / Tn0 . Since it is suboptimal against pm , there exists an information set hn where the action a chosen by tn is suboptimal. Then hn does not belong to Hn∗ : indeed, since tn belongs to Sn0 , a is an equilibrium action if hn ∈ Hn∗ ; and since Pn (Tn0 ) contains an equilibrium strategy, there exists a strategy in Tn0 that enables such an hn and chooses a. Let h′n be the last information set preceding hn that belongs to Hn∗ . Then obviously the action chosen by tn at h′n is an equilibrium action and thus hn belongs to Hn0 . Any strategy in Tn0 that enables hn avoids a, which proves the lemma. ¤ For the next lemma, it is worth recapitulating the exact definition of the set Π1n . Recall from Section 4.5 that we fix a completely mixed enabling strategy p̄m for player m and compute for each pn the total probability η(pn ) of reaching a terminal node in Zn1 under 1 1 (p̄m , pn ). Hn is a hyperplane in RZn that separates the projection ψZn1 (Pn1 ) of Pn1 to RZn 1 from the origin of RZn and that has (p0 (z)p̄m (z))z∈Zn1 as its normal and some ε > 0 as its constant. The function π̄n1 maps each point pn ∈ Pn \ Pn0 to ε(η(pn ))−1 ψZn1 (pn ) ∈ Hn . Lemma C.4. For a strategy sn of Sn1 , π̄n1 (sn ) is a vertex of Π1n iff there exists a unique information set hn ∈ Hn∗ with the property that sn enables hn and chooses a non-equilibrium action there. Proof. Let sn ∈ Sn1 be a pure strategy satisfying the condition of the lemma. We prove by contradiction that π̄n1 (sn ) is a vertex of Π1n . Therefore suppose to the contrary that π̄n1 (sn ), which equals ε(η(pn ))−1 ψZn1 (pn ), is not a vertex of Π1n . We can express π̄n1 (sn ) as a unique P convex combination Jj=1 λj πn1,j where J > 1 and for each 1 6 j 6 J, πn1,j is a vertex of −1 1,j 1 (s Π1n . For each j, since πn1,j is a vertex of Π1n , we can express πn1,j as ε(η(s1,j n ) for n )) ψZn ′ j 1,j 1 some s1,j n in Sn . Since λ > 0, sn cannot choose a non-equilibrium action at any hn 6= hn 32 SRIHARI GOVINDAN AND ROBERT WILSON in Hn∗ that it enables; since it belongs to Sn1,j it must therefore enable hn ; and it cannot choose a different non-equilibrium action from sn at hn . Observe now that the probability η(pn ) and η(s1,j n ) for all j are equal and exactly the probability that Nature and the strategy P 1,j 1,j p̄m do not exclude hn . Therefore, ψZn1 (pn ) = j λj ψZn1 (s1,j n ). Modify sn to a strategy tn so that at every information set other than the successors to hn , t1,j n agrees with sn , and at the successors to hn it agrees with s1,j n . It is now clear that when viewed as enabling P j 1,j strategies, sn = j λ tn and thus sn is a convex combination of the strategies t1,j n . But that is a contradiction since sn is a vertex of Pn and all the strategies t1,j n are different from one 1,j another and from sn as they induce the points πn that are different from one another and from π̄n1 (sn ) in Hn . To prove the other way around, suppose sn is a strategy that, at a collection hkn for k = 1, . . . , K of at least two information sets in Hn∗ , chooses a non-equilibrium action. For each k, k 1 choose a strategy s1,k n in Sn that enables hn , agrees with sn there and at all its successors, but P at other hn ∈ Hn∗ , chooses an equilibrium action. Then ψZn1 (sn ) = k ψZn1 (s1,k n ). Therefore, π̄n1 (sn ) cannot be a vertex of Π1n . ¤ For each Tn0 ⊆ Sn0 such that Pn (Tn0 ) is a face of Pn0 and contains an equilibrium strategy for n, let Sn1 (Tn0 ) be the subset of Sn1 consisting of strategies s1n such that for each first information set h0n in Hn0 that s1n does not exclude, s1n agrees with some t0n ∈ Tn0 at h0n and all its successors, where t0n has the property that it does not exclude h0n . For a face Ψ1n of Π1n , let Sn1 (Tn0 ; Ψ1n ) = Sn1 (Ψ1n ) ∩ Sn1 (Tn0 ) and Tn ≡ Tn0 ∪ Sn1 (Tn0 ; Ψ1n ). For notational simplicity, we refer to Sn1 (Tn0 ; Ψ1n ) as Tn1 . The following lemma provides an important feature of the set Tn . Lemma C.5. The strategies in Tn are the vertices of a face of Pn whose dimension is d(Tn ) ≡ d(Tn0 ) + d(Ψ1n ) + 1. Proof. Let T̂n1 be the set of strategies t1n in Tn1 such π̄n1 (t1n ) is a vertex of Ψ1n . We will first show that every tn ∈ Tn \ (Tn0 ∪ T̂n1 ) is affinely dependent on the strategies in Tn0 ∪ T̂n1 . Let ∗ t1n ∈ Tn \ (Tn0 ∪ T̂n1 ). By Lemma C.4, there exist information sets h1n , . . . hK n , K > 1, in Hn such that for each k, t1n chooses a non-equilibrium action ak at hkn , and at each other hn ∈ Hn∗ it chooses an equilibrium action. Fix t0n ∈ Tn0 that agrees with t1n everywhere except at the 1 information sets hkn for each k. For each k let t1,k n be the strategy that agrees with tn at 1 hkn and its successors, but everywhere else agrees with t0n . Each t1,k n belongs to T̂n and also, P 0 1 1 0 t1n = k t1,k n − (K − 1)tn . Thus, tn is an affine combination of the strategies in Tn ∪ T̂n . AXIOMATIC EQUILIBRIUM SELECTION 33 1 1,j 0 1 For each j = 0, . . . , d(Ψ1n ), pick a strategy t1,j n ∈ Sn (Tn ) such that π̄n (tn ) is a vertex of Ψ1n . Let T̃n1 be the collection of these strategies. We show that strategies in T̂n1 \ T̃n1 are now affinely dependent on the strategies in Tn0 ∪ T̃n1 . Fix t1n ∈ T̂n1 \ T̃n1 . By Lemma C.4 there exists a unique information set hn ∈ Hn∗ enabled by t1n and where it chooses a non-equilibrium action. J 1 1 1 By construction of T̃n1 , there exists a subset (t1,j n )j=1 of T̃n such that π̄n (tn ) is expressible P j 1,j as an affine combination j λj π̄(t1,j n ) with λ 6= 0 for all j. For each j, sn enables hn and chooses a at hn ; at all other information sets in Hn∗ it chooses an equilibrium action. Let t0n be a strategy that agrees with t1n everywhere except at hn and its successors. For each j, let 1,j t0,j n be a strategy that agrees with tn everywhere except at hn and its successors, where it P 0,j agrees with t0n . Then t1n = t0n + j λj (t1,j n − tn ) and is affinely dependent on the strategies in Tn0 ∪ T̃n1 . It follows now from the above arguments that the affine space A spanned by Tn0 ∪ T̃n1 contains Pn (Tn ) and that the dimension of Pn (Tn ) is as stated. To finish the proof of the lemma, we show that Pn (Tn ) is a face of Pn . Let Qn be the smallest face of Pn that contains Pn (Tn ). Suppose Qn 6= Pn (Tn ). Then there exists a point pn in the relative of interior of Pn (Tn ) and Qn . Therefore pn can be expressed as a convex combination of the vertices of P j 1,j P 0,i 0 1,j Qn in two different ways: (a) i λi t0,i n + j λ tn , where the tn ’s are in Tn and the tn ’s P j 1,j P k 2,k P 2,k are in Tn1 ; (b) i µi t0,i n + k µ tn , where now the tn ’s are the vertices of Qn j µ tn + 0 0 that are not in Tn . Consider one of the t2,k n ’s. If it belongs to Sn \ Tn then by Lemma C.3 there is an information set hn in Hn0 that is enabled by t2,k n where the action chosen by hn is avoided all strategies in Tn0 that enable it: that implies under the expression in (b) that the nodes following this action are assigned a positive probability, but not under (a), which 1 1 1 1 is impossible. If t2,k n belongs to Sn \ Tn then it must belong to Sn (Ψn ) since otherwise under / Tn1 there exists an information set hn ∈ Hn0 enabled by t2,k / Ψ1n . Since sn ∈ (b) π̄n1 (pn ) ∈ n 0 0 2,k where the continuation strategy of tn coincides with that of some tn ∈ Sn \ Tn but not for any sn ∈ Tn0 . As in the previous case, this too is impossible. ¤ One corollary of the above result obtains when we take Tn1 to be Sn1 and Ψ1n to be Π1n . The dimension of Pn is d(Pn0 ) + d(Π1n ) + 1. Observe that Pn1 is a face of Pn iff ψZn1 (Pn1 ) is a face of ψZn1 (Pn ), which is equivalent to saying that Π1n is homeomorphic to ψZn1 (Pn1 ). Thus, the dimension of Pn1 equals d(Π1n ) if Pn1 is a face of Pn and otherwise it equals the dimension of Pn . Fix T ≡ ((T10 , Ψ11 ), (T20 , Ψ12 )), where for each n, Pn (Tn )∩Q∗n nonempty and Ψ1n is a (possibly empty) face of Π1n . Let An (T ) be the set of points in Pn (Tn0 ) such that the strategies in Tm 34 SRIHARI GOVINDAN AND ROBERT WILSON are all best replies. Let T̃n0 be the unique subset of Tn0 such that the interior of An (T ) is contained in the interior of Pn (T̃ 0 ). Let d˜∗ (T ) be the dimension of An (T ). n n Lemma C.6. If Tm1 is nonempty then An (T ) is a proper face of Q̄∗n ∩ Pn (T̃n0 ). Proof. Since Q∗n ∩Pn (Tn ) is nonempty, the strategies in Tn0 are undominated. Hence, Pn (T̃n0 )∩ Q̄∗n = Pn (T̃n0 ) ∩ Q∗n ≡ A∗n (T ). An (T ) is thus a face of A∗n (T ). There remains to show that it is a proper face. This follows from the genericity of payoffs. Fix t1m ∈ Tm1 . There exists ∗ an information set hm ∈ Hm where it chooses a non-equilibrium action a. If the path from each (x, a), for x ∈ hm that is reached under the equilibrium outcome, does not pass through an information set hn ∈ Hn0 , then a would be suboptimal against every equilibrium Q̄∗n . ∗ Thus, there exists a first information set hn ∈ Hn0 and nodes x ∈ Hm and y ∈ hn such that (x, a) ≺ y and x is reached under the equilibrium outcome. Because A∗n (T ) is nonempty, there is a strategy t0n ∈ T̃n0 that enables hn . Clearly, there must be multiple such strategies, again by genericity. Perturbing the probabilities of the terminal nodes following y does not affect the payoffs to strategies in Tm0 but they affect the payoff to t1m . Hence An (T ) is a proper face of A∗n (T ). ¤ 1 (Tm0 ) \ Tm1 such that: (i) sm is an equally good Let T̂m1 be the set of strategies sm in Sm reply against every point in Pn0 to which the strategies in Tm are equally good replies. Let 1 T̄m1 be the set of strategies sm in Sm (Tm0 ) \ (T̂m1 ∪ Tm1 ) that are best replies against every point in An (T ). Let Bn∗ (T ) be the closure of the points in the interior of Pn0 against which the strategies in Tm are equally good replies and at least as good replies as strategies in T̄m1 . Let d∗n (T ) be the dimension of Bn∗ (T ). If Tm1 is empty, let Bn (T ) = Pn0 . Otherwise, let Bn (T ) be the set of points in Pn0 that are of the form λqn0 + (1 − λ)rn0 such that λ > 1, qn0 ∈ Bn∗ (T ), and rn0 ∈ Pn (Tn0 ). Lemma C.7. Suppose Tm1 is nonempty. Bn (T ) is a polyhedron of dimension d∗n (T )+dn (Tn0 )− d˜∗n (T ). Each maximal face Bn′ (T ) of Bn (T ) satisfies exactly one of the following: (1) The relative interior of Bn′ (T ) is contained in the relative interior of a maximal proper face of Pn0 . (2) There exists a strategy rm ∈ T̄m1 such that for each p0n ∈ Bn′ (T ), rm is an equally good ∗ (T ); moreover, in this reply against every point of the form λp0n + (1 − λ)rn0 in Bm 1 1 , if rm is a best reply against case, letting Řm be the set of such rm , for any rm ∈ R̄m 1 is also a best reply against this point. a point in Bn∗ (T ) then every point in Řm AXIOMATIC EQUILIBRIUM SELECTION 35 (3) There exists a maximal proper face of Pn (Tn0 ), say Pn (Rn0 ), such that for each qn ∈ Bn∗ (T ), rn ∈ Pn (Tn0 ) and λ > 1, if λqn + (1 − λ)rn belongs to Bn′ (T ), then rn belongs to Pn (Rn0 ); moreover, An (T ) is contained in Pn (Rn0 ). Proof. Let P̃n0 , P̃n (Tn0 ), and B̃n∗ (T ) be the convex cones spanned by Pn0 , Pn (Tn0 ), and Bn∗ (T ) respectively. Let ξ : Pn0 × P̃n (Tn0 ) → P̃n0 be the function ξ(p0n , r̃n0 ) = p0n + r̃n0 . Then for each p̃0n , ξ −1 (p̃0n ) is a set of dimension d(Tn0 ). Hence the dimension of B̂(T ) ≡ ξ −1 (B̃n∗ (T )) is d(Tn0 ) + d∗n (T ) + 1. Obviously B̂(T ) is a polyhedron. For each face B̂n′ (T ) of B̂n (T ) and for all points (p0n , r̃n0 ) ∈ B̂n′ (T ) at least one of the following holds: (i) p0n belongs to the boundary of Pn0 ; (ii) there exists a strategy tm ∈ T̄m1 such that ξ(p0n , r̃n0 ) belongs to the convex cone spanned by the face of Bn∗ (T ) where this strategy tm is an equally good reply; (iii) r̃n0 belongs to the boundary of P̃n (Tn0 ). Observe now that Bn (T ) is the projection of B̂n (T ) onto the first factor. Obviously it is a polyhedron. For each p0n ∈ Bn (T ) and each r̃n0 such that (p0n , r̃n0 ) ∈ B̂n (T ), (p0n , r̃n0 + λrn0 ) ∈ B̂n (T ) for all rn0 ∈ Bn∗ (T ) ∩ Pn (Tn0 ) and λ > 0. If the set Bn∗ (T ) is in generic position (i.e. if the payoffs are in generic position), then all points in B̂n (T ) that project to p0n are of this form. Since the set Bn∗ (T )∩Pn (Tn0 ) is the intersection of Pn (Tn0 ) with the affine space spanned by An (T ), the dimension of Bn (T ) is as asserted. The enumerated properties of Bn (T ) now follow directly from the corresponding points above; only the last part of property (iii) needs a proof. Suppose rn0 belongs to a proper face Pn (Rn0 ) of Pn (Tn0 ) and An (T ) is not contained in Pn (Rn0 ). If (p0n , λrn0 ) belongs to B̂n (T ), then so does (p0n , λrn0 + r̄n0 ) for r̄n0 ∈ An (T ) \ Pn (Rn0 ) and λrn0 + r̄n0 does not belong to the convex cone generated by Pn (Rn0 ). ¤ Let Cn∗ (T ) be the closure of the set of qn in the interior of Pn such that the strategies in Tm are all equally good replies and at least as good as strategies in T̂m1 and Sn0 \ Tn0 . By Lemma C.5, the dimension of the face spanned by Tm is d(Tm0 ) + d(Ψ1m ) + 1. By genericity of payoffs, the dimension of Cn∗ (T ) is therefore d(Pn ) − d(Tm0 ) − d(Ψ1m ) − 1. Let Cn (T ) be the set of (p1n , πn1 ) ∈ Pn1 × Π1n such that there exist p0n ∈ Pn0 , p2n ∈ Pn (Tn1 ), P P P qn ∈ Cn∗ (T ), and µ ∈ R3+ , such that i µi pin ∈ Cn∗ (T ), i µi = 1, µ1 > 0, and π̄n1 ( i µi pin ) = πn1 . Lemma C.8. The set Cn (T ) is a polyhedron of dimension d(Pn0 ) + d(Pn1 ) + dn (Ψ1n ) − d(Tm0 ) − d(Ψ1m ) − d∗n (T ). On each maximal proper face C ′ of Cn (T ), exactly one of the following holds P for all (p1n , πn1 ) in C ′ . If qn ∈ C ∗ (T ) is of the form i µi pin for some p0n ∈ Pn0 and p2n ∈ Pn (Tn1 ), P and π̄n1 ( i µi pin ) = πn1 , then: (1) p1n belongs to a maximal proper face of Pn1 ; 36 SRIHARI GOVINDAN AND ROBERT WILSON i \ Tmi , which actually belongs to (2) for i = 0 or i = 1, but not both, there exists sm ∈ Sm T̂mi if i = 1, that is as good a reply as points in Tm against qn ; moreover, in this case, if i = 0, Tm0 and sm span a face of Pm0 of which Pm (Tm0 ) is a maximal proper face; and if i = 1, Ψ1m and π̄n1 (sm ) span a face of Π1m of which Ψ1m is a maximal proper face. (3) there exists a maximal proper face Ψ′ of Ψn such that π̄n1 (p2n ) belongs to Ψ′ . Proof. We show that Cn (T ) is a polyhedron of the stated dimension. Since the construction is similar to that in the previous lemma, the enumerated properties can be proved just as before. Let Pn2 be the convex hull of Pn0 and Pn (Tn1 ). Using Lemma C.5, the dimension of Pn2 is d(Pn0 ) + d(Ψ1n ) + 1. Let P̃n2 and P̃n be the convex cones spanned by Pn2 and Pn , respectively. Define ξ : Pn1 × P̃n2 → P̃n by ξ(p1n , p̃2n ) = p1n + p̃2n . Then for each p̃n in the interior of P̃n , ξ −1 (p̃n ) is a set of dimension d(Pn1 )+d(Pn0 )+d(Ψ1n )+1. Letting C̃n∗ (T ) be the convex cone spanned by Cn∗ (T ), the dimension of Ĉn (T ) ≡ ξ −1 (C̃n∗ (T )) is d(Pn0 ) + d(Pn1 ) + d(Ψ1n ) + 1 − d(Tm0 ) − d(Ψ1m ). The function π̄n1 extends to P̃ \ { 0 }. Cn (T ) is the image of Ĉn (T ) under the function χ : Pn1 × P̃n2 given by χ(p1n , p̃2n ) = (p1n , π̄n1 (p1n + p̃2n )) and is thus a polyhedron. As will be shown in the course of the proof of the next lemma, Cn∗ (T ) ∩ Pn (Tn1 ) ⊂ Pn0 . Therefore, Cn∗ (T ) ∩ Pn2 is the intersection of Pn0 with the affine space spanned by Bn∗ (T ). For each (p1n , p̃2n ) ∈ Ĉn (T ), the point (p1n , p̃2n +µqn0 ) belongs to Ĉn (T ) for all µ > 0 and qn0 ∈ Cn∗ (T )∩Pn2 , and has the same image under χ as (p1n , p̃2n ). Moreover, if Cn∗ (T ) is in general position then for each (p1n , πn1 ) in Cn (T ) every point in its inverse image under χ is expressible in this form. Therefore, the dimension of Cn (T ) is as given. ¤ Let T be the collection of T ’s such that An (T ), Bn (T ) and Cn (T ) are nonempty for each n. For each T ∈ T , let Qn (T ) = An (T ) × Bn (T ) × Cn (T ) for each n and let Q(T ) = Q1 (T ) × Q2 (T ). Lemma C.9. (q ∗ , p0 , p1 , π 1 ) belongs to Q iff it belongs to Q(T ) for some T ∈ T . Proof. Suppose for each n that qn∗ ∈ An (T ), p0n ∈ Bn (T ), (p1n , πn1 ) ∈ Cn (T ) for some T . Choose rn0 ∈ Pn (Tn0 ) and λ0n such that qn0 ≡ (1 − λ0n )p0n + λ0n rn0 ∈ Bn∗ (T ). Also, fix p̃0n , rn2 ∈ Pn (Tn1 ), µ0n , µ1n , µ2n such that qn1 ≡ µ0n p̃0n + µ1n p1n + µ2n rn2 belongs to Cn∗ (T ). Fix points q̄n0 and q̄n1 in the interior of An (T ) and Bn (T ) for each n and consider for each 0 < ε < 1, the LPS (q ∗ , q̃ 0 (ε), q̃ 1 (ε)) where for each n, q̃n0 (ε) = (1−ε)q̄n0 +εqn0 ; and q̃n1 (ε) = (1−ε)q̄n0 +εq̄n1 (ε)+ε2 qn1 . ∗ 0 1 The strategies in Tn are equally good replies to qm , q̃m (ε), q̃m (ε) for all ε. We show that these strategies are lexicographic best replies to (q ∗ , q̃ 0 (ε), q̃ 1 (ε)) for all small ε, which proves that (q ∗ , p0 , p1 , π 1 ) belongs to Q. AXIOMATIC EQUILIBRIUM SELECTION 37 ∗ and Observe first that for all ε, a strategy in Sn0 \ Tn0 is an equally good reply against qm 1 0 (ε) by construction (ε) as strategies in Tn0 , by Lemma C.2, and no better a reply against q̃m q̃m 1 1 1 ∗ of Cn (T ). Now for a strategy sn in Sn , consider the strategy tn that agrees with s1n everywhere except that starting at each first information set hn ∈ Hn0 that s1n enables, t1n agrees with some t0n in Tn0 . Since strategies in Tn0 are at least as good as the other strategies in Sn0 , 0 ∗ (ε), q̃n1 (ε)). Observe now that t1n belongs to , q̃m clearly t1n is at least good a reply against (qm ∗ Sn1 (Tn0 ). If it belongs to T̂n1 , then it is an equally good reply as strategies in Tn against qm 1 0 (ε) by definition. If it belongs to T̄n1 then (ε) and no better reply a reply against q̃m and q̃m 0 ∗ (ε) for all ε, and a strictly worse , no better reply against q̃m it is an equally good reply to qm 1 reply against q̃m (ε) for all small ε, again by construction, since it is an inferior reply against q̄n1 which belongs to the interior of Bn∗ (T ). Finally, if it belongs to Sn1 (Tn1 ) \ (T̂n1 ∪ T̄n1 ) then 0 ∗ (ε) for all small ε, since it is and an inferior reply to q̃m it is no better a reply against qm 0 an inferior reply to q̄n by construction of An (T ). Thus the strategies in T are lexicographic best replies to (q ∗ , q̃ 0 (ε), q̃ 1 (ε)) for all small ε. Before proceeding to prove the converse, we use the above argument to show that the intersection of Cn∗ (T ) with the convex hull Pn2 of Pn0 is in fact the intersection F of Pn0 with the affine space spanned by Bn∗ (T ). Take a point qn1 in Cn∗ (T ) ∩ P 2 . If it belongs to Pn0 , then in fact it belongs to F by the definitions of Bn∗ (T ) and T̂m1 . If it does not belong to Pn0 , then it assigns a positive weight to some strategy s1n ∈ Tn1 . The above argument applied when using ∗ is a best reply to (qn∗ , q̃n0 (ε), q̃n1 (ε)) and the strategies in Tn and Sn0 are this qn1 shows that qm ∗ . Observe now that q̃n1 (ε) is a convex combination of strategies in Sn0 and best replies to qm ∗ ) is an equilibrium if ε is Tn1 . Therefore, for all small δ, ((1 − δ − δ 2 )qn∗ + δ q̃n0 (ε) + δ 2 q̃n1 (ε), qm 1 small as well. But these points induce different outcomes because q̃n (ε) has a non-equilibrium strategy, namely one in Tn1 , in its support, which is impossible. Thus, Cn∗ (T ) ∩ Pn2 = F as claimed. Returning to the proof of this lemma, suppose (q ∗ , (p0 , p1 ), π 1 ) belongs to Q. Let qn0 = (1 − λ0n )p0n + λ0n rn0 and let qn1 = µ0n p̃0n + µ1n p1n + µ2n rn2 where (1 − λ0n )qn∗ + λ0n rn0 is a best reply against (q ∗ , q 0 , q 1 ); and rn2 , if µ2n > 0, is a best reply against qn∗ and a weakly better reply against (q ∗ , q 0 , q 1 ) than all the strategies in Pn1 . Let Q0n be the face of Pn0 that contains (1 − λ0n )qn∗ + λ0n rn0 . Let Q1n be the face of Pn1 that contains rn2 in its interior if µ2n > 0. Let Tn0 be the set of strategies tn in Sn0 such that if tn enables a first information set hn ∈ Hn0 then the choices from there on prescribed by t0n coincide with the choices dictated by some vertex of Q0n or Q1n that enables hn . Observe that each t0n ∈ Tn0 is optimal against (q ∗ , q 0 , q 1 ). If µ2n > 0, let Ψ1n be the face of Π1n that contains π̄n1 (rn2 ) in its interior; otherwise let Ψ1n be the empty set. 38 SRIHARI GOVINDAN AND ROBERT WILSON We can now assume without loss of generality that the strategies in Q0n and Q1n are equally 1 0 ∗ ) and hence best replies. Indeed, if for i either 0 or 1, if the , qm , qm good replies against (qm 1 i i strategies in Qn do not yield the same payoff against qm as those in Q0n , modify qm as follows: 0 ∗ in the face Q̃0n of Q0n containing qm pick a point řm in its interior such that the strategies in 0 1 Qn are equally good replies, the strategies in Qn do strictly better than the strategies in Q0n i ∈ [0, 1] such that and at least as well as the other strategies in Sn1 . There exists a unique νm 0 1 i i i i the strategies in Qn and Qn are now equally good replies against (1 − νm )qm řm . Thus, + νm our assumption is without loss of generality. Since the strategies in Q0n and Q1n are best replies. There remains to show that every ∗ 0 1 strategy in Sn (Tn0 ; Ψ1n ) is a best reply against (qm , qm , qm ). Fix sn ∈ Sn (Tn0 ; Ψ1n ). To show that it is a best reply it is sufficient to show that an information set hn that is enabled by sn is enabled by some vertex of either Q0n or Q1n and that this vertex agrees with sn ’s choice an there. Suppose that this hn is in Hn∗ and an ∈ A∗n , or hn belongs to Hn0 ; then obviously some strategy in Q0n or Q1n enables hn and chooses an , by the definition of Tn0 . If hn ∈ Hn∗ and an ∈ / A∗n or hn follows some information set in Hn∗ by the choice of a non-equilibrium action, then some strategy in Q1n enables it and chooses this action, since otherwise sn enables a terminal node that is excluded by all strategies in Q1n , contradicting the assumption that π̄n1 (sn ) ∈ Ψ1n . Thus sn is a best reply and (q ∗ , q 0 , q 1 ) belongs to Q(T ). ¤ Lemma C.10. Q is a pseudomanifold of dimension dˆ ≡ d(P). ˆ By the previous lemma Q = ∪T ∈T Q(T ). Proof. Each Q(T ) is a polyhedron of dimension d. ˆ To show that Q is a pseudomanifold, we establish three Therefore, Q has dimension d. facts for each (q ∗ , (p0 , p1 ), π 1 ) that belongs to some Q(T ): (1) if (q ∗ , (p0 , p1 ), π 1 ) belongs to the interior of Q(T ), then it does not belong to the interior of Q(R) for R 6= T ; (2) if (q ∗ , (p0 , p1 ), π 1 ) is a generic point in a maximal proper face Q′ of Q(T ), then it does not belong to Q(R) for any R 6= T if (p0 , p1 ) ∈ ∂P, and it belongs to the boundary of Q(R) for exactly one other R 6= T if (p0 , p1 ) ∈ / ∂P; moreover in the latter case it belongs to the interior of a maximal proper face of this Q(R) as well; (3) given T, R ∈ T , there exists a finite chain T = T (0), . . . , T (k) = R such that for each 0 ≤ j ≤ k − 1, Q(T (j)) ∩ Q(T (j + 1)) is a subset of a maximal proper face of each and has a nonempty interior in this face. Fix T = (T 0 , Ψ1 ) and x = (q ∗ , (p0 , p1 ), π 1 ) ∈ Q(T ). For each n, choose qn0 ≡ (1 − λ0n )p0n + λ0n rn0 in Bn∗ (T ) and qn1 ≡ µ0n p̃0n + µ1n p1n + µ2n rn1 ∈ Cn∗ (T ). We start with (1). Suppose now that x belongs to the interior of Q(R) for some R. We show that R = T . Since x belongs to the interior of Q(T ), we can assume that every strategy 0 0 \ Tm0 . Since sm is an inferior reply \ Tm0 is inferior to qn1 . Let sm be a strategy in Sm in Sm AXIOMATIC EQUILIBRIUM SELECTION 39 1 compared to the strategies in Tn0 , by Lemma C.3 there exists an information set against qm hn ∈ Hn0 that is enabled by sn where the action chosen by sn is suboptimal and different from the action chosen by every tn ∈ Tn0 that enables hn . But the posterior belief over the 1 1 . This implies that can be computed from πm terminal nodes following hn computed from qm 1 1 ′ 1 ′ ) cannot for any qm such that π̄m (qm ) = πm , sn is an inferior strategy. Therefore, (p1m , πm 0 0 0 0 belong to Cm (R) unless Rm ⊆ Tm . Moreover, if Rm ( Tm , then it cannot belong to the 0 are also optimal. Thus, if x belongs to the interior of Cm (R), since strategies in Tm0 \ Rm 0 0 1 interior of Q(R), Rm = Tm for each m. If Ψm is empty, this implies that Rm = Tm . Suppose 1 1 now that Ψ1m is nonempty. Since x is in the interior we can assume that π̄m (p1m ) 6= πm and 1 1 ) can be computed uniquely from p1m that π̄n (rm ) is in the interior of Ψ1m . Observe that π̄n1 (rm 1 1 1 and computing the boundary and πm by taking the line segment from π̄m (p1m ) through πm point of this line. This implies that if x belongs to the interior of Q(R), then Rm = (Tm0 , Ψ1m ). Thus R = T . We turn to point (2). Suppose now x belongs to the relative interior of a maximal proper face of Q(T ) and that (p0 , p1 ) belongs to ∂P . Then if it belongs to another Q(R) it cannot be in the interior and must belong to the boundary. The arguments of the previous paragraph apply to show that x does not belong to the interior of a maximal face of Q(R). Indeed, 0 it relied on strategies in Sm \ Tm0 being inferior to qn1 , and qn0 (resp. qn1 ) not belonging to the boundary of Bn (T ) (resp. Cn (T )). Thus x must belong to a face of dimension at most dˆ − 2. The set of such points in this maximal proper face of Q(T ) then has dimension at most dˆ − 2, i.e. it is nongeneric. Suppose that x belongs to the relative interior of a maximal proper face of Q(T ) but that (p0 , p1 ) is in the interior in P. Then for exactly one n, just one of the following hold: (2a) qn∗ belongs to the boundary of A∗n (T ); (2b) p0n belongs to the boundary of Bn (T ); (2c) (p1n , πn1 ) belongs to the boundary of Cn (T ). We start with (2c). By the properties we proved for Cn (T ) in Lemma C.8, and since (p0 , p1 ) ∈ / ∂P, either property (ii) or property (iii) of that lemma holds. Under property (ii) x belongs to the boundary of Q(R) where 0 i R = ((Rm , Φ1m ), (Tn , Ψ1n )) is defined as follows. If the strategy rm identified there belongs 0 0 0 i to Sm , then Rm is the vertex set of the face spanned by rm and Tm , while Φ1m = Ψ1n ; if the i 0 strategy rm belongs to Sn1 (Tn0 ; Ψ1n ), then Rm = Tm0 and Φ1m is a face of Π1m that has Ψ1m as 1 1 a maximal face with πm (rm ) ∈ Φ1m \ Ψ1m . Under property (iii) x belongs to the boundary of Q(R) where R = ((Tn0 , Φ1n ), (Tm0 , Ψ1m )) where Φ1n is the maximal proper face of Ψ1n identified there. Suppose x satisfies (2b). Then by the properties we proved for Bn (T ) in Lemma C.7, 1 be the either property (ii) or property (iii) of that lemma holds. Under property (ii) let R̃m 40 SRIHARI GOVINDAN AND ROBERT WILSON set of strategies in T̃m1 that are now best replies against qn0 . Let Φ̃1m be the smallest face of 1 1 1 1 Π1m that contains Ψ1m and the vectors πm (r̃m ) for r̃m ∈ R̃m . Then the strategies in Tm0 and 1 Sm (Φ1m ) are equally good replies against qn0 . Moreover by the genericity of x, if one of these strategies is a best reply against a point in Bn∗ (T ) then all these points are best replies as well. For each face Φ1m of Φ̃1m that has Ψ1m a maximal proper face, choose a strategy rm (Φ1m ) that maps to a vertex of Φ1m that is not contained in Ψ1m . The set of points in Bn∗ (T ) against which the strategies in R̃m are as good replies as Tm has dimension d∗n (T ) − 1. However, the set of points in Cn∗ (T ) where two or more of these strategies rm (Φ1m ) are also best replies has dimension d(Pn ) − d(Tm0 ) − d(Ψ1m ) − 3 or less. Therefore, for R and R′ of the form ((Tn0 , Ψ1n ), (Tm0 , Φ1m )) the set of (p1n , πn1 ) that lies in the intersection Cn (T ) ∩ Cn (R) ∩ Cn (R′ ) is at most d0n + d1n + dn (Ψ1n ) − d∗n (T ) − 1 or less. This implies that generic (p1n , πn1 ) in Cn (T ) belongs to at most one of these sets. Moreover, if x belongs to Q(R), then it belongs to 1 is a convex combination of the boundary of Q(R): indeed the point φ1m in Φ1m such that πm 1 1 1 π̄m (pm ) and φm is uniquely determined, as we argued above; since this point belongs to Ψ1m , which is a face of Φ1m , x indeed belongs to the boundary of Q(R) if it belongs to Q(R). To 1 finish the proof of this case, we now show that x belongs to at least one Q(R). Take an r̃m 1 that yields the highest payoff against qn1 among the strategies in R̃m . If this payoff is higher than the payoff to the strategies in Tm0 , pick a point q̄n0 in the interior of Bn∗ (T ) and replace 1 qn1 with q̃n1 (ε) ≡ (1 − ε)qn1 + εq̄n0 where ε is the unique number where the strategies Tm0 and r̃m 1 1 are equally good replies; then x belongs to some Q(R) that has πm (r̃m ) as an extra vertex. 1 0 0 If the payoff to r̃m is lower, take a point q̄n in Pn against which the strategies in Tm0 are 1 equally good and worse than the strategies in R̃m and repeat the argument to show that x belongs to Q(R). Finally, suppose that x satisfies (2a). Let A′n be a maximal proper face of An (T ) that 1 1 contains qn∗ in its interior. Let Řm be the set of strategies řm in Sm (Tm0 ) \ (Tm1 ∪ T̂m1 ∪ T̄m1 )) 1 that are best replies against all the points in A′n . Observe that Řm is nonempty if qn∗ belongs to the interior of Pn (T̃n0 ). Indeed, in this case, the interior of A′n which is a face of An (T ) is 1 contained in the interior of Pn (T̃n0 ), which implies that some strategy in Sm is now optimal 0 0 0 against every point in this face. Let Rn be the set of subsets Rn of Tn such Pn (Rn0 ) is a maximal proper face of Pn (Tn0 ) and Pn (Rn0 ) ∩ Q∗n = A′n . Observe that R0n is nonempty if qn∗ belongs to the boundary of Pn (T̃n0 ). 1 1 1 (řm ) for řm ∈ Let Φ̌1m be the smallest face of Π1m that contains Ψ1m and the vectors πm 1 Řm . For each face Φ1m of Φ̌1m that has Ψ1m as a maximal proper face, choose a strategy 1 řm (Φ1m ) that maps to a vertex of Φ1m that is not contained in Ψ1m . Take R and R′ of AXIOMATIC EQUILIBRIUM SELECTION 41 the form ((Tn0 , Ψ1n ), (Tm0 , Φ1m )). Since A′n is a face of An (T ), d˜∗n (R) = d˜∗n (R′ ) = d˜∗n (T ) − 1. 1 are inferior replies to points in the interior of An (T ), Bn∗ (R) Since the strategies in Řm if nonempty has dimension d∗n (T ) − 1. Therefore, if Bn (R) 6= Bn (R′ ), their intersection with Bn (T ) has codimension 1 in Bn (T ) and x cannot belong to two of these sets at once. On the other hand, if Bn (R) = Bn (R′ ) then an argument similar to that in the previous paragraph shows that generic (p1n , πn1 ) ∈ Cn (T ) can belong to at most one of these sets, Cn (R) and Cn (R′ ). Hence a generic x belongs to at most one of these sets. Likewise, for R of the form ((Rn0 , Ψ1n ), (Tm0 , Ψ1m )) with Rn0 ∈ R0n and R′ of the form ((Rn′ 0 , Ψ1n ), (Tm0 , Ψ1m )) or ((Tn0 , Ψ1n ), (Tm0 , Φ1m )), the intersection of Bn (T ) with Bn (R) and Bn (R′ ) has codimension at least one. Thus x belongs to at most one set Q(R). To finish the proof of this part, we show that it belongs to at least one such set. 1 Let řm (Φ1m ) be a strategy that is a lexicographic best reply to (qn0 , qn1 ) among the strategies 1 in this class. If řm (Φ1m ) is a lexicographic (weakly) better reply against (qn0 , qn1 ) (or it is a worse reply and qn∗ belongs to the interior of Pn (T̃n0 )) we choose a point q̄n0 in the interior of 1 Pn (T̃n0 ) against which the strategy řm (Φ1m ) is at least as good as the other points in this class and inferior (resp. superior) to strategies in Tm0 . The strategies in Tm0 and Sm (Tm0 ; Φ1m ) are now equally good replies against some average of qn0 and q̄n0 , as well as some average of qn1 and q̄n0 . The point x then belongs to ((Tm0 , Φ1m ), (Tn0 , Ψ1n )). If qn∗ belongs to the boundary of 1 Pn (T̃n0 ), and řm (Φ1m ) is an inferior reply, then Řn0 is nonempty. There exists Rn0 such that qn0 is a convex combination of a point in Pn (Ťn0 ) and p0n . Then x belongs to ((Ťn0 , Ψ1n ), (Tm0 , Ψ1m )). This concludes the proof of (2). We turn now to (3). Given Q(T ) and Q(R) for T = (T 0 , Ψ0 ) 6= R = (R0 , Φ1 ), we will first construct a sequence T = T (1), . . . , T (k) = T̃ where T̃ = ((T̃n0 , ∅), (T̃m0 , ∅)). And, likewise one from R to R̃. Then we will show how to construct a sequence from T̃ to R̃. In case T̃n0 6= Tn0 for some n, let T = T (0), . . . , T (k) be a sequence where for each j > 0, T (j) = ((Tn0 (j), Ψ1n ), (Tm0 (j), Ψ1n )) with Pn (Tn0 (j))×Pm (Tm0 (j)) being a maximal proper face of Pn (Tn0 (j−1))×Pm (Tm0 (j−1)), and Tn (k) = T̃n0 for each n. This sequence generates a sequence of polyhedra Q(T ) = Q(T (0)), . . . , Q(T (k)) where for each j > 0, the intersection of Q(T (j)) with Q(T (j − 1)) is contained in a maximal proper face of each and has a nonempty interior. After this operation we have Q(T̃ (k)), where T̃ (k) = ((T̃n0 , Ψ1n ), (T̃m0 , Ψ1m )). In case Ψ1n is nonempty for some n, let Ψ1 = (Ψ1n (0), Ψ1m (0)), . . . , (Ψ1n (l), Ψ1m (l)) = (∅, ∅) be a sequence such that for each 1 6 j ≤ l, Ψ1m (j)×Ψ1m (j) is a maximal proper face of Ψ1n (j −1)×Ψ1m (j −1), and Ψ1 (l) = ∅. This way we can connect Q(T̃ (k)) with Q(T̃ ) where T̃ = ((T̃n0 , ∅), (T̃m0 , ∅)). Now we show how to connect T̃ with R̃ for two sets T, R in T . Because Q∗n is connected for 42 SRIHARI GOVINDAN AND ROBERT WILSON 0 0 each n, there exists a sequence T̃ 0 = (Sn0 (0), Sm (0)), . . . , (Sn0 (l), Sm (l)) = R̃n0 where for each 0 1 6 j 6 l, either Pn (Sn0 (j)) × Pn (Sm (j)) is either a maximal proper face of Pn (Sn0 (j + 1)) or vice versa and for each n, Q∗n intersects the interior of the set Pn (Sn0 (j)). This generates 0 a sequence Q0 , . . . Qj , where Qj = ((Sn0 (j), ∅), (Sm (j), ∅)). Thus we have constructed a sequence of sets in T that connect T and R. ¤ This concludes the proof of the first statement in the theorem. Now we prove the second part. Lemma C.11. ψ : (Q, ∂Q) → (P, ∂P) is essential iff Q∗ is stable. Proof. Let Y = [0, 1] × P . For each 0 < ε 6 1, let Yε = [0, ε] × P and let ∂Yε be the boundary of Yε . Each (ε, p) ∈ Y defines a strategic game G(ε, p) where the strategy set is P but where the payoff from an enabling strategy profile q is the payoff in G from the profile (1 − ε)q + εp. If q is an equilibrium of G(ε, p), we say that (1 − ε)q + εp is a perturbed equilibrium of G(ε, p). Let E be the closure of the set of (ε, p, q) such that (ε, p) ∈ Y1 \ ∂Y1 and q is a perturbed equilibrium of G(ε, p). Let θ be the projection map from E. For each subset E of E and each 0 < ε, let (Eε , ∂Eε ) be E ∩ θ−1 (Pε , ∂Pε ). In [9] we show that there exists 0 < ε̄ 6 1 and a finite number of subsets E 1 , . . . , E K of E such that for each 0 < ε 6 ε̄: (i) (Eεk , ∂Eεk ) is a pseudomanifold (in fact a homology manifold) of dimension d(P ) + 1 for each k; (ii) Eεk ∩ Eεj ⊂ ∂φ−1 (∂P1 ) for k 6= j; (iii) ∪k Eεk = Eε . In [6] we show that there exists a neighborhood of Σ∗ and an ε > 0 such that the set of ε-perfect equilibria in this neighborhood is connected. The image of this set of ε-perfect equilibria under ρ is therefore connected. Thus there exists some k such that E0k = { 0 }×Q∗ . Q∗ is stable iff the projection θ from E k to Yε̄ is essential (Mertens [19]). For simplicity in notation we refer to this E k as simply E. It is now sufficient to prove that ψ is essential iff the projection θ from E is essential. For each n, P̃n ≡ [0, 1] × Pn and define χn : P̃n → Pn by χn (λn , p0n , p1n ) = (1 − λn )p0n + λn p1n . Then we have that ((P̃n , ∂ P̃n ), (Pn , ∂Pn ), χn ) is a ball-bundle. Let χ be the product map χ1 × χ2 ; then ((P̃ , ∂ P̃ ), (P, ∂P ), χ) is a ball-bundle too. Let Ŷε = [0, ε] × P̃ . Then χ induces a map hY : Ŷ1 → Y1 by h(ε, λ, p0 , p1 ) = (ε, χ(λ, p0 , p1 )). Now ((Ŷε , ∂ Ŷε ), (Yε , ∂Yε ), hY ) is a ball-bundle. Let Ẽ be the set of all ((ε, λ, p0 , p1 ), q) ∈ Ŷ1 × P such that hE (ε, λ, p0 , p1 , q) ≡ (ε, f (λ, p0 , p1 ), q) ∈ E. Then also ((Ẽε , ∂ Ẽε ), (Eε , ∂Eε ), hE ) is a ball-bundle. Moreover, letting θ̃ be the projection from Ẽ to P, we have that hY ◦ θ̃ = θ ◦ hE . Therefore, by the Thom Isomorphism Theorem, θ is essential iff θ̃ is; cf. [20, Appendix IV.3]. AXIOMATIC EQUILIBRIUM SELECTION 43 Let Ê be the closure of the set of (ε, λ, p0 , p1 , q, π 1 (q)) such that (ε, λ, p0 , p1 , q) ∈ Ẽ and λ 6= 0. By the strong excision property, the natural projection φ̂ from Ê to Ẽ induces an isomorphism of their cohomology groups. Let θ̂ be the projection from Ê to Ŷε . Then θ̂ = θ̃ ◦ φ̂. Therefore, θ̃ is essential iff θ̂ is. Let η : Ê → R3+ be the projection map η(ε, λ, (p0 , p1 ), q, π 1 ) = (ε, λ). Let D = η(Ê). By the generic local triviality theorem, there exists a partition of D into a finite number of connected subsets D10 , . . . , Dl0 , and for each Di a semi-algebraic fibre pair (Fi , ∂Fi ), a homeomorphism hi : Di0 × (Fi , ∂Fi ) → (η −1 (Di0 ), η −1 (Di0 ) ∩ ∂ Ê) such that η ◦ hi is the projection from Di0 × Fi to Di0 . There now exists an i, say 1, such that the closure D1 of a subset of Di0 is homeomorphic to a 3-simplex and contains [0, ε̃] × { 0 } for some ε̃ < ε̄. Let (Ŷ (D1 ), ∂ Ŷ (D1 )) ≡ (D1 , ∂D1 ) × (P, ∂P) and let Ê(D1 ) be the closure of the inverse image of D1 × F1 under h1 . Let θ̂(D1 ) : (Ê(D1 ), ∂ Ê(D1 )) → (Ŷ (D1 ), ∂ Ŷ (D1 )) be the projection. We claim that (Ê(D1 ), ∂ Ê(D1 )) is a pseudomanifold. Since Ê is a pseudomanifold, this claim is proved if we show that Ê(D1 ) \ ∂ Ê(D1 ) is path-connected. There exist 0 < ε̂ < ε̃ and integers rn > 1 for each n such that (ε, λ) ∈ D1 if 0 < ε < ε̂ and 0 ≤ λn ≤ εrn −1 . Now given two points x(0) and x(1) in Êε̂ (D1 ) \ ∂ Êε̂ (D1 ), connect them by a curve x(t) = (ε(t), λ(t), p0 (t), p1 (t), q(t), π 1 (q(t))) in Êε̄ \ ∂ Êε̄ as t goes from 0 to 1. For each t, express q(t) as ε(t))(λ(t)p0 (t) + (1 − λ(t))p1 (t)) + (1 − ε(t))r(t) where r(t) is a best reply to q(t). For each t we can now find a point q ∗ (t) ∈ Q∗ such that r(t) is a best reply against q ∗ (t). Choose a positive ε such that ε + εrn < ε̂. For each n, modify xn (t) to the vector x̃n (t) = (ε + εrn ε(t), λ̃(t), p̃0 (t), p1 (t), q̃(t), π 1 (t)) where λ̃n (t) = p̃0n (t) = εrn ε(t) λn (t), ε + ε rn εq ∗ (t) + εrn ε(t)(1 − λ(t))p0 (t) , ε + εrn ε(t)(1 − λ(t)) q̃n (t) = (1 − εrn )q ∗ (t) + εrn (1 − ε(t))r(t) + εrn ε(t)((1 − λ(t))p0 (t) + λ(t)p1 (t)). Then x̃(t) belongs to Ê(D1 ) \ ∂ Ê(D1 ) for all t. Moreover, for t = 0, 1, x(t) and x̃(t) can now be connected by a path x̂(t; s) defined as follows. For s ∈ [0, 1], let kn (s) = min(1, 2s)rn and then: x̂n (t; s) = ((2s − 1)+ ε + εkn (s) ε(t), λ̂(t; s), p0 (t; s), p1 (t), q̂(t; s), π 1 (t)) 44 SRIHARI GOVINDAN AND ROBERT WILSON where λ̂n (t) = p̃0n (t; s) = εkn (s) ε(t)λn (t) , (2s − 1)+ ε + εkn (s) ε(t) (2s − 1)+ εqn∗ (t) + εrn ε(t)(1 − λn (t))p0n (t) , (2s − 1)+ ε + εkn (s) ε(t)(1 − λn (t)) q̃n (t; s) = (1 − εkn (s) )qn∗ (t) + εkn (s) (1 − ε(t))r(t) + εkn (s) ε(t)((1 − λn (t))p0n (t) + λn (t)p1 (t)). Thus Ê(D1 )\∂ Ê(D1 ) is connected and hence a pseudomanifold of dimension d(P)+3. Ŷ (D1 ) is a full-dimensional subset of Yε̄ . Therefore θ̂ is essential iff θ̂(D1 ) is essential. Since (Ê(D1 ), ∂ Ê(D1 )) is a pseudomanifold, (F1 , ∂F1 ) is a pseudomanifold of dimension d(P). Moreover, for each (ε, λ) ∈ D10 , letting (Êε,λ , ∂ Êε,λ ) ≡ h−1 1 ({ ε, λ } × (F1 , ∂F1 )) we have that θ̂ is essential iff θ̂ε,λ , the projection map (Êε,λ , ∂ Êε,λ ) → (P, ∂P ), is essential. Let L be the set of (ε, λ) ∈ D1 such that λn = εr for some r > rn for each n. Let Ê(L) be the closure of the inverse image of L \ { (0, 0) } under h1 . Let ∂ Ê(L) be the inverse image of ∂P under the projection map θ(L) from Ê(L). For each (ε, λ) ∈ L, (Eε,λ , ∂Eε,λ ) is (θ(L))−1 ({ (ε, λ) } × (P, ∂P)). Our next objective is to show that (Q, ∂Q) equals the set of (q ∗ , (p0 , p1 ), π 1 ) such that (0, 0, (p0 , p1 ), q ∗ , π 1 ) belongs to E0,0 (L). Given (0, 0, (p0 , p1 ), q ∗ , π 1 ) in Ê(L) there exists a sequence (ε(k), λ(k), (p0 , p1 )(k), q(k), π 1 (k)) in Ê(L) \ E0,0 converging to it. For each n and k, we can express qn (k) as (1 − ε(k))((1 − µ1n )qn0 (k) + µ1n rn1 (k)) + ε(k)(λ(k)p0n (k) + (1 − λ(k))p1n (k)), where µ1n and λ(k) converge to zero, qn0 (k) belongs to Pn0 and converges to qn∗ , and rn1 (k) belongs to Pn1 . Also qn0 (k) and rn1 (k) if µ1n > 0 are best replies to q(k) for all k. By going to a subsequence, the faces to which qn0 (k) and rn0 (k) belong are constant for all k. The sequence generates for each n an LPS Λn = (q̄n0 , . . . , q̄nl ) where q̄n0 = qn∗ . As in the proof of Theorem 5.1, there exists a level lni for each i = 0, 1 that is expressible as a convex combination of p0n and another strategy. Since λ(k) converges to zero, ln0 < ln1 . As in the proof of Theorem 5.1, we can prove that q̄nl belongs to Q̄∗n for each l < ln0 l0 and if we express q̄nn = νn0 p0n + (1 − νn0 )rn0 , then the strategies q̄nl for l < ln0 and rn0 if ν 0 < 1 l1 are lexicographic best replies against Λm . Likewise, if we express q̄nn as ν̄n0 p̃0n + ν̄n1 p1n + ν̄n2 rn2 , then the strategy rn2 if ν̄n2 > 0 is a lexicographic best reply against Λm . As in the proof of Theorem 5.1, Section 5.6, we can now write down an LPS (q ∗ , q̄ 0 (ε), q̄ 1 (ε)) to show that (q ∗ , (p0 , p1 ), π 1 ) belongs to Q. Given (q ∗ , (p0 , p1 ), π 1 ) in Q, it belongs to Q(T ) for some T . There exist qn0 = (1 − λ0n )p0n + λ0n rn0 and qn1 = µ0n p̃0n + µ1n p1n + µ2n rn2 such that the strategies in Tm are best replies against the r LPS (q ∗ , qn0 , qn1 ). For all small ε, choose α(ε) such that εr µ1 = (εr µ1 + εr µ0 + α(ε)(1 − λ0n )p0n ) , AXIOMATIC EQUILIBRIUM SELECTION 45 where r satisfies the property in the first line of the previous paragraph. Then for all small ε, (ε, λ(ε), (p0 , p1 )(ε), q(ε)) belongs to Ê(L), where: λ(ε) = εr µ1 , εr µ1 + εr µ0 + α(ε)(1 − λ0n ) and (p0 , p1 )(ε) = (p0 (ε), p1 ) with for each n, p0n (ε) = εr µ0 p̃0n + α(ε)(1 − λ0n )p0n εr µ0 + α(ε) and q̂(ε) = (1 − α(ε) − εr )q ∗ + α(ε)q 0 + εr q 1 . For each (ε, λ), (Eε,λ , ∂Eε,λ ) is a pseudomanifold. Indeed for (ε, λ) 6= (0, 0) this follows from the fact that this pair is homeomorphic to (F1 , ∂F1 ), which is a pseudomanifold; for (0, 0), this follows from the fact that (E0,0 , ∂E0,0 ) is homeomorphic to (Q, ∂Q). The inclusion map (Eε,λ , ∂Eε,λ ) induces an isomorphism of the d(P)-th cohomology groups. Thus θ̂0,0 is essential iff θ̂ε,λ is essential for some (and then all) (ε, λ) ∈ L. The projection map θ̂0,0 is just the map ψ. Hence Q∗ is stable iff ψ is essential. ¤ In case Sn1 is empty, the construction is modified as follows. We can omit the sets Cn (T ) and Bm (T ) from the description of Q(T ). In the last lemma above, the vector λ is now just a number, one for player m. The simplex D constructed there is 2-dimensional and contains a curve L of the form λ = εr . The rest of the proof is essentially the same. This concludes the proof of the Theorem. ¤ Appendix D. The Genericity Assumption The conclusions of this paper necessarily hold only when, fixing the game tree, the payoffs lie in a generic set. Here we outline the nature of the genericity that is invoked. First, we require that the game have finitely equilibrium outcomes: in [4] we show that outside a lower-dimensional set every game has finitely many outcomes. Second, the constructions in Appendix C rely on certain polyhedra being in general position. Each of these polyhedra— there are finitely many of them—is a set of enabling strategies for a player n against which, in a certain class of strategies for player m, a subclass is optimal. Since these are defined by linear equations and inequalities in the payoffs of player m, the set of games where the arguments fail is a lower-dimensional set. Third, Lemma C.11 requires a characterization of stable sets that in [9] we show holds for all games outside a lower-dimensional set. 46 SRIHARI GOVINDAN AND ROBERT WILSON References [1] Blume, L., A. Brandenburger, and E. Dekel (1991): Lexicographic Probabilities and Equilibrium Refinements, Econometrica, 59, 81-98. [2] Govindan, S., and T. Klumpp (2002): Perfect Equilibrium and Lexicographic Beliefs, International Journal of Game Theory, 31, 229-243. [3] Govindan, S., and J.-F. Mertens (2003): An Equivalent Definition of Stable Equilibria, International Journal of Game Theory, 3, 339-357. [4] Govindan, S., and R. Wilson (2001): Direct Proofs of Generic Finiteness of Nash Equilibrium Outcomes, Econometrica, 69, 765-769. [5] Govindan, S., and R. Wilson (2002): Structure Theorems for Game Trees, Proceedings of the National Academy of Sciences USA, 99, 9077-9080. URL: www.pnas.org/cgi/reprint/99/13/9077.pdf [6] Govindan, S., and R. Wilson (2002): Maximal Stable Sets of Two-Player Games, International Journal of Game Theory, 30, 557-566. [7] Govindan, S., and R. Wilson (2006): Sufficient Conditions for Stable Equilibria, Theoretical Economics, 1, 167-206. [8] Govindan, S., and R. Wilson (2008): “Nash Equilibrium, refinements of,” in S. Durlauf and L. Blume (eds.), The New Palgrave Dictionary of Economics, 2nd Edition. New York: Palgrave Macmillan. [9] Govindan, S., and R. Wilson (2008): Metastable Equilibria, Mathematics of Operations Research, 33, 787-820. [10] Govindan, S., and R. Wilson (2009): On Forward Induction, Econometrica, 77, 1-28. [11] Govindan, S., and R. Wilson (2009): Axiomatic Theory of Equilibrium Selection in Games with Games with Two Players, Perfect Information, and Generic Payoffs, Research Paper 2008, Stanford Business School, Stanford CA. [12] Hillas, J., and E. Kohlberg (2002): Conceptual Foundations of Strategic Equilibrium, in R. Aumann and S. Hart (eds.), Handbook of Game Theory, III, 1597-1663. New York: Elsevier. [13] Kahneman, D., and A. Tversky, editors (2000): Choices, Values, and Frames. Cambridge, UK: Cambridge University Press. [14] Kohlberg, E., and J.-F. Mertens (1986): On the Strategic Stability of Equilibria, Econometrica, 54, 1003-1037. [15] Koller, D., and N. Megiddo (1992): The Complexity of Two-Person Zero-Sum Games in Extensive Form, Games and Economic Behavior, 4, 528-552. [16] Kreps, D., and R. Wilson (1982): Sequential Equilibria, Econometrica, 50, 863-894. [17] Kuhn, H. (1953): Extensive Games and the Problem of Information, in H. Kuhn and A. Tucker (eds.), Contributions to the Theory of Games, II, 193-216. Princeton: Princeton University Press. Reprinted in H. Kuhn (ed.), Classics in Game Theory, Princeton University Press, Princeton, New Jersey, 1997. [18] Mailath, G., L. Samuelson, and J. Swinkels (1993): Extensive Form Reasoning in Normal Form Games, Econometrica, 61, 273-302. [19] Mertens, J.-F. (1989): Stable Equilibria–A Reformulation, Part I: Definition and Basic Properties, Mathematics of Operations Research, 14, 575-625. [20] Mertens, J.-F. (1991): Stable Equilibria–A Reformulation, Part II: Discussion of the Definition and Further Results, Mathematics of Operations Research, 16, 694-753. [21] Mertens, J.-F. (1992): The Small Worlds Axiom for Stable Equilibria, Games and Economic Behavior, 4, 553-564. AXIOMATIC EQUILIBRIUM SELECTION 47 [22] Nash, J. (1950): Equilibrium Points in N-Person Games, Proceedings of the National Academy of Sciences USA, 36, 48-49. [23] Nash, J. (1951): Non-Cooperative Games, Annals of Mathematics, 54, 286-295. [24] Norde, H., J. Potters, H. Reijnierse, D. Vermeulen (1996): Equilibrium Selection and Consistency, Games and Economic Behavior, 12, 219-225. [25] Reny, P. (1992): Backward Induction, Normal Form Perfection and Explicable Equilibria, Econometrica, 60, 627-649. [26] Reny, P. (1992): Rationality in Extensive-Form Games, Journal of Economic Perspectives, 6, 103-118. [27] Reny, P. (1993): Common Belief and the Theory of Games with Perfect Information, Journal of Economic Theory, 59, 257-274. [28] Savage, L.J. (1954): Foundations of Statistics, New York: John Wiley & Sons. [29] Spanier, E.H. (1966): Algebraic Topology, New York: McGraw-Hill. [30] van Damme, E. (1984): A Relation between Perfect Equilibria in Extensive Form Games and Proper Equilibria in Normal Form Games, International Journal of Game Theory, 13, 1-13. [31] van Damme, E. (2002): Strategic Equilibrium, in R. Aumann and S. Hart (eds.), Handbook of Game Theory, III, 1523-1596. New York: Elsevier. Department of Economics, University of Iowa, Iowa City IA 52242, USA. E-mail address: srihari-govindan@uiowa.edu Stanford Business School, Stanford, CA 94305-5015, USA. E-mail address: rwilson@stanford.edu