A Course in Game Theory - Enrique A. Bour

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).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.

2 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 : 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 Disagree?

3 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 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.

4 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 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.

5 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. 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.

6 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). We regret any errors and encourage you to draw our attentionto of the BookThe book consists of four parts; in each part we study a group of relatedmodels. The chart on the next page summarizes the interactions amongthe chapters. A basic Course could consist of Chapters 2, 3, 6, 11, 12,and : Nash equilibrium3: Mixed equilibrium4: Rationalizability5: Knowledge6: Extensive, perfect : Bargaining8: Repeated games9: Complexity10: Implementation11: Extensive, imperfect : Sequential equilibrium13: Core14: Stable sets, barg. set15: Nash barg. solutionPart I: Strategic gamesPart II: Extensive games with perfect informationPart III: Extensive games with imperfect informationPart IV: Coalitional *.

7 > :..~?.. :The main interactions between the chapters. The areas of the boxes in which thenames of the chapters appear are proportional to the lengths of the chapters. Asolid arrow connecting two boxes indicates that one chapter depends on the other; adotted arrow indicates that only the main ideas of one chapter are used in the basic Course could consist of the six chapters in heavy of the exercises are challenging; we often use exercises to statesubsidiary results. Instructors will probably want to assign additionalstraightforward problems and adjust (by giving hints) the level of our ex-ercises to make it appropriate for their students. Solutions are availableto instructors on the web site for the book (see page xv).Disagreements Between the AuthorsWe see no reason why a jointly authored book should reflect a uniformview. At several points, as in the following note, we briefly discuss issuesabout which we Note on Personal PronounsWe disagree about how to handle English third-person singular that we should use a neutral pronoun and agrees to theuse of he , with the understanding that this refers to both men andwomen.

8 Continuous reminders of the he/she issue simply divert thereader s attention from the main issues. Language is extremely impor-tant in shaping our thinking, but in academic material it is not usefulto wave it as a flag, as is common in some that no language is neutral . In particular, there is awealth of evidence, both from experiments and from analyses of lan-guage use, that he is not generally perceived to encompass both fe-males and males. To quote theAmerican Heritage Dictionary(thirdedition, page 831), Thusheis not really a gender-neutral pronoun;rather it refers to a male who is to be taken as the representative mem-ber of the group referred to by its antecedent. The traditional usage,then, is not simply a grammatical convention; it also suggests a par-ticular pattern of thought. Further, the use of he to refer to anindividual of unspecified sex did not even arise naturally, but was im-posed as a rule by (male) prescriptive grammarians in the eighteenth andnineteenth centuries who were upset by the widespread use of they asa singular pronoun and decided that, since in their opinion men weremore important than women, he should be used.

9 The use of he torefer to a generic individual thus both has its origins in sexist attitudesand promotes such attitudes. There is no neat solution to the problem,especially in a book such as this in which there are so many referencesxivPrefaceto generic individuals. They has many merits as a singular pronoun,although its use can lead to ambiguities (and complaints from editors).My preference is to use she for all individuals. Obviously this us-age is not gender-neutral, but its use for a few decades, after a coupleof centuries in which he has dominated, seems likely only to help toeliminate sexist ways of thought. If such usage diverts some readers attentions from the subjects discussed in this book and leads them tocontemplate sexism in the use of language, which is surely an issue atleast as significant as the minutiae of sequential equilibrium, then anincrease in social welfare will have been achieved. (Whether or not thisbook qualifies as academic material , I see no reason why its readersshould be treated differently from those of any other material.)

10 To conclude, we both feel strongly on this issue; we both regard thecompromise that we have reached as highly unsatisfactory. When re-ferring to specific individuals, we sometimes use he and sometimes she . For example, in two-player games we treat player 1 as femaleand player 2 as male. We use he for generic book is an outgrowth of courses we have taught and discussionswe have had with many friends and colleagues. Some of the material inChapters 5, 8, and 9 is based on parts of a draft of a book on models ofbounded rationality had the privilege of being educated in game Theory by RobertAumann, Sergiu Hart, Mordecai Kurz, and Robert Wilson at StanfordUniversity. It is a great pleasure to acknowledge my debt to over the years with Jean-Pierre Beno t, Haruo Imai, VijayKrishna, and Carolyn Pitchik have improved my understanding of manytopics. I completed my work on the book during a visit to the Depart-ment of Economics at the University of Canterbury, New Zealand; I amgrateful to the members of the department for their generous hospital-ity.