The Theory of Extensive Form Games (Springer Series in Game Theory)

This book treats extensive form game theory in full generality. It provides a framework that does not rely on any finiteness assumptions at all, yet covers the finite case. The presentation starts by identifying the appropriate concept of a game tree. This concept represents a synthesis of earlier approaches, including the graph-theoretical and the decision-theoretical ones. It then provides a general model of sequential, interpersonal decision making, called extensive decision problems. Extensive forms are a special case thereof, which is such that all strategy profiles induce outcomes and do so uniquely. Requiring the existence of immediate predecessors yields discrete extensive forms, which are still general enough to cover almost all applications. The treatment culminates in a characterization of the topologies on the plays of the game tree that admit equilibrium analysis. Preface 8 References 9 Contents 10 List of Figures 14 List of Symbols 16 1 Introduction 17 1.1 The Starting Point 18 1.1.1 Historical Notes 18 1.1.2 Extensive Form Games 19 1.2 How to Model Games 21 1.2.1 Kuhn's Graph Approach 22 1.2.2 Von Neumann and Morgenstern's Refined-Partitions Approach 23 1.2.3 The Synthesis 24 1.2.4 The Sequence Approach 26 1.2.5 Some Illustrative Examples 27 1.2.6 Plan of the Book 30 References 31 2 Game Trees 32 2.1 Preview 34 2.2 Set Representations 35 2.2.1 Trees and Subtrees 36 2.2.2 Motivating Examples 40 2.2.2.1 Osborne-Rubinstein Trees 40 2.2.2.2 Long Cheap Talk 40 2.2.2.3 Bilateral Bargaining 41 2.2.2.4 Repeated Games 42 2.2.2.5 Stochastic Games 42 2.2.2.6 Differential Games 43 2.2.3 Decision Trees 44 2.2.4 Representation by Plays 47 2.3 Set Trees 50 2.3.1 Reduced Form and Plays 53 2.3.2 Irreducible Set Trees 54 2.3.3 Proper Order Isomorphism 56 2.3.4 Bounded Set Trees 58 2.4 Game Trees 62 2.4.1 Complete Game Trees 64 2.5 Summary 68 References 70 3 Pseudotrees and Order Theory 71 3.1 Pseudotrees 72 3.2 Directed Sets and Pseudotrees 73 3.3 Pseudotrees as (Semi)Lattices 75 3.4 Representation of Pseudotrees 77 3.5 Summary 80 References 80 4 Extensive Decision Problems 81 4.1 Preview 82 4.2 Definition of Extensive Decision Problems 82 4.2.1 Information Sets 85 4.2.2 Simultaneous Decisions 87 4.2.3 Absent Mindedness 89 4.2.4 Independence of the Conditions 92 4.2.5 EDP2 When Chains Have Lower Bounds 93 4.3 Choices and Strategies 94 4.3.1 Plays and Choices 94 4.3.2 Strategies 94 4.4 Game Trees Revisited 95 4.4.1 Examples 96 4.4.2 A Classification of Nodes 100 4.4.3 Removing Singletons 103 4.5 Available Choices 105 4.5.1 Perfect Information Choices 105 4.5.2 Existence of EDPs 108 4.6 Summary 109 References 110 5 Extensive Forms 112 5.1 Preview 113 5.2 Strategies and the Desiderata 114 5.2.1 Randomized Strategies 115 5.3 Plays Reached by Strategies 116 5.4 When Do Strategies Induce Outcomes? 117 5.4.1 Examples for Non-existence 117 5.4.2 Undiscarded Nodes 118 5.4.3 Perfect Information and Playability 120 5.4.4 Everywhere Playable EDPs 121 5.4.5 Up-Discrete Trees 125 5.5 Uniqueness 129 5.5.1 Examples with Multiple Outcomes 129 5.5.2 Extensive Forms 131 5.5.3 A Uniqueness Result 136 5.6 A Joint Characterization 137 5.7 Note: Games in Continuous Time 138 5.8 Summary 141 References 143 6 Discrete Extensive Forms 144 6.1 Preview 145 6.2 Discrete Extensive Forms 146 6.2.1 Up-Discrete Trees Revisited 146 6.2.2 Discrete Trees 148 6.2.3 Discrete Extensive Forms 151 6.3 Discrete Games when Nodes are Primitives 156 6.3.1 Simple Trees 156 6.3.2 Simple Extensive Forms 158 6.4 Perfect Recall 163 6.4.1 Definition and Characterization 164 6.4.2 A Choice-Based Definition 167 6.4.3 Some Implications 168 6.5 Summary 172 References 173 7 Equilibrium 175 7.1 Preview 176 7.2 Motivating Examples: Nodes as Sets Versus Plays as Sequences 179 7.3 Perfect Information and Backwards Induction 183 7.3.1 Perfect Information Games 184 7.3.2 Backwards Induction 188 7.3.3 Games Where Players Move Finitely Often 196 7.3.4 Continuity at Infinity 197 7.3.5 Well-Behaved Perfect Information Games 200 7.4 A Characterization 203 7.5 Necessary Conditions 206 7.5.1 Proof of Theorem 7.3 207 7.5.1.1 Necessity of (CN) 208 7.5.1.2 Necessity of Closed Terminal Slices 208 7.5.1.3 Necessity of (OP) 209 7.6 Sufficient Conditions 211 7.6.1 Topology on Nodes 212 7.6.2 The Algorithm 213 7.6.3 Proof of Theorem 7.4 216 7.6.3.1 The Limit Correspondence 219 7.6.3.2 Forward Induction 221 7.7 Discussion 222 7.7.1 On Generality 222 7.7.1.1 Topologies on Slices May Not Be Separated 224 7.7.1.2 The Successor Correspondence May Not Be Upper Hemi-Continuous 225 7.7.1.3 Topologies on Plays Allow Additional Flexibility 225 7.7.2 The Fort Example 226 7.7.3 Is Compactness Necessary? 228 7.7.4 Topologies on Strategies 229 7.7.5 Continuous Game Trees 229 7.7.5.1 Proof of Proposition 7.4 231 7.8 Summary 232 References 233 A Mathematical Appendix 235 A.1 Sets, Relations, and Functions 235 A.1.1 Sets 235 A.1.2 Binary Relations 236 A.1.2.1 Partial Orders 237 A.1.2.2 Lattices and Directed Sets 238 A.1.2.3 Equivalence Relations 238 A.1.3 Functions and Correspondences 238 A.2 Topology 239 A.2.1 Separation Properties 241 A.2.2 Sequences and Nets 241 A.2.3 Compactness 242 A.2.4 Continuity 243 A.2.5 Separation by Continuous Functions 244 Bibliography 245 Index 249 Front Matter....Pages i-xv Introduction....Pages 1-15 Game Trees....Pages 17-55 Pseudotrees and Order Theory....Pages 57-66 Extensive Decision Problems....Pages 67-97 Extensive Forms....Pages 99-130 Discrete Extensive Forms....Pages 131-161 Equilibrium....Pages 163-222 Back Matter....Pages 223-239