A Course in Game Theory

1 A Course in Game TheoryElectronic version of A Course in Game Theory byMartin J. Osborne and Ariel Rubinstein (ISBN 0-262-65040-1)Copyrightc 1994 Massachusetts Institute of rights reserved. No part of this book may be reproduced in anyform by any electronic or mechanical means (including photocopying,recording, or information storage and retrieval) without permission inwriting from the file is made freely available with permission of MIT Press. It isfor your personal use only. You are not permitted to transfer it toanyone else, to copy it, to include any part of it in any other file, or tomake it available on any website (whether or not password-protected).

2 Version: Course in Game TheoryMartin J. OsborneAriel RubinsteinThe MIT PressCambridge, MassachusettsLondon, EnglandCopyrightc 1994 Massachusetts Institute of TechnologyAll rights reserved. No part of this book may be reproduced in any form by anyelectronic or mechanical means (including photocopying, recording, or informationstorage and retrieval) without permission in writing from the book was typeset by the authors, who are greatly indebted to Donald Knuth(the creator of TEX), Leslie Lamport (the creator of LATEX), and Eberhard Mattes(the creator of emTEX) for generously putting superlative software in the publicdomain.

3 Camera-ready copy was produced by Type 2000, Mill Valley, California,and the book was printed and bound by The Maple-Vail Book ManufacturingGroup, Binghamton, New , Martin Course in game Theory /Martin J. Osborne, Ariel bibliographical references and 0-262-15041-7. ISBN 0-262-65040-1 (pbk.)1. Game Theory . I. Rubinstein, Ariel. II. 0353 dc2094-8308 CIPC ontentsPreface xi1 Introduction Game Theory Games and Solutions Game Theory and the Theory of Competitive Equilibrium Rational Behavior The Steady State and Deductive Interpretations Bounded Rationality Terminology and Notation 6 Notes 8I Strategic Games 92 Nash Equilibrium Strategic Games Nash Equilibrium Examples Existence of a Nash Equilibrium Strictly Competitive Games Bayesian Games.

4 Strategic Games with ImperfectInformation 24 Notes 29viContents3 Mixed, Correlated, and Evolutionary Equilibrium Mixed Strategy Nash Equilibrium Interpretations of Mixed Strategy Nash Equilibrium Correlated Equilibrium Evolutionary Equilibrium 48 Notes 514 Rationalizability and Iterated Elimination of DominatedActions Rationalizability Iterated Elimination of Strictly Dominated Actions Iterated Elimination of Weakly Dominated Actions 62 Notes 645 Knowledge and Equilibrium A Model of Knowledge Common Knowledge Can People Agree to

5 Disagree? Knowledge and Solution Concepts The Electronic Mail Game 81 Notes 84II Extensive Games with Perfect Information 876 Extensive Games with Perfect Information Extensive Games with Perfect Information Subgame Perfect Equilibrium Two Extensions of the Definition of a Game The Interpretation of a Strategy Two Notable Finite Horizon Games Iterated Elimination of Weakly Dominated Strategies 108 Notes 1147 Bargaining Games Bargaining and Game Theory A

6 Bargaining Game of Alternating Offers Subgame Perfect Equilibrium Variations and Extensions 127 Notes 131 Contentsvii8 Repeated Games The Basic Idea Infinitely Repeated Games vs. Finitely Repeated Games Infinitely Repeated Games: Definitions Strategies as Machines Trigger Strategies: Nash Folk Theorems Punishing for a Limited Length of Time: A Perfect FolkTheorem for the Limit of Means Criterion Punishing the Punisher: A Perfect Folk Theorem for theOvertaking Criterion Rewarding Players Who Punish.

7 A Perfect Folk Theorem forthe Discounting Criterion The Structure of Subgame Perfect Equilibria Under theDiscounting Criterion Finitely Repeated Games 155 Notes 1609 Complexity Considerations in Repeated Games Introduction Complexity and the Machine Game The Structure of the Equilibria of a Machine Game The Case of Lexicographic Preferences 172 Notes 17510 Implementation Theory Introduction The Implementation Problem Implementation in Dominant Strategies Nash Implementation Subgame Perfect Equilibrium Implementation 191 Notes 195viiiContentsIII Extensive Games with ImperfectInformation 19711 Extensive Games with Imperfect Information Extensive Games with Imperfect Information Principles for the Equivalence of Extensive Games Framing Effects and the Equivalence of ExtensiveGames Mixed and Behavioral Strategies Nash Equilibrium 216 Notes 21712 Sequential Equilibrium Strategies and Beliefs Sequential Equilibrium Games

8 With Observable Actions: Perfect BayesianEquilibrium Refinements of Sequential Equilibrium Trembling Hand Perfect Equilibrium 246 Notes 254IV Coalitional Games 25513 The Core Coalitional Games with Transferable Payoff The Core Nonemptiness of the Core Markets with Transferable Payoff Coalitional Games without Transferable Payoff Exchange Economies 269 Notes 27414 Stable Sets, the Bargaining Set, and the ShapleyValue Two Approaches The Stable Sets of von Neumann and Morgenstern The Bargaining Set, Kernel, and Nucleolus The Shapley Value 289 Notes 297 Contentsix15 The Nash Solution Bargaining Problems The Nash Solution.

9 Definition and Characterization An Axiomatic Definition The Nash Solution and the Bargaining Game of AlternatingOffers An Exact Implementation of the Nash Solution 311 Notes 312 List of Results 313 References 321 Index 341 PrefaceThis book presents some of the main ideas of game Theory . It is designedto serve as a textbook for a one-semester graduate Course consisting ofabout 28 meetings each of 90 topics that we cover are those that we personally would includein such a one-semester Course . We do not pretend to provide a completereference book on game Theory and do not necessarily regard the topicsthat we exclude as unimportant.

10 Our selection inevitably reflects ourown preferences and interests. (Were we to start writing the book nowwe would probably add two chapters, one on experimental game theoryand one on learning and evolution.)We emphasize the foundations of the Theory and the interpretation ofthe main concepts. Our style is to give precise definitions and full proofsof results, sacrificing generality and limiting the scope of the materialwhen necessary to most easily achieve these have made a serious effort to give credit for all the concepts,results, examples, and exercises (see the Notes at the end of eachchapter).