A Course In Game Theory

A Course in Game Theory

Electronic version of “A Course in Game Theory” by Martin J. Osborne and Ariel Rubinstein (ISBN 0-262-65040-1) Copyright c 1994 Massachusetts Institute of Technology. All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission inwriting from the publisher. This file is made freely available with permission of MIT Press. It is for your personal use only. You are not permitted to transfer it to anyone else, to copy it, to include any part of it in any other file, or to make it available on any website (whether or not password-protected). Version: 2006-9-24.

A Course in Game Theory

Martin J. Osborne Ariel RubinsteinThe MIT Press Cambridge, Massachusetts London, England

Copyright c 1994 Massachusetts Institute of Technology All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher. This book was typeset by the authors, who aregreatly indebted to Donald Knuth A (the creator of TEX), Leslie Lamport (the creator of L TEX), and Eberhard Mattes (the creator of emTEX) for generously putting superlative software in the public domain. Camera-ready copy was produced by Type 2000, Mill Valley, California, and the book was printed and bound by The Maple-Vail Book Manufacturing Group, Binghamton, New York. Osborne, Martin J. A coursein game theory/Martin J. Osborne, Ariel Rubinstein. p. cm. Includes bibliographical references and index. ISBN 0-262-15041-7.—ISBN 0-262-65040-1 (pbk.) 1. Game Theory. I. Rubinstein, Ariel. II. Title. HB144.O733 1994 658.4’0353–dc20

94-8308 CIP

Contents

Preface 1

xi

Introduction 1 1.1 Game Theory 1 1.2 Games and Solutions 2 1.3 Game Theory and the Theory of Competitive Equilibrium1.4 Rational Behavior 4 1.5 The Steady State and Deductive Interpretations 5 1.6 Bounded Rationality 6 1.7 Terminology and Notation 6 Notes 8

3

I
2

Strategic Games

9

Nash Equilibrium 11 2.1 Strategic Games 11 2.2 Nash Equilibrium 14 2.3 Examples 15 2.4 Existence of a Nash Equilibrium 19 2.5 Strictly Competitive Games 21 2.6 Bayesian Games: Strategic Games with Imperfect Information24 Notes 29

vi

Contents

3

Mixed, Correlated, and Evolutionary Equilibrium 3.1 Mixed Strategy Nash Equilibrium 31 3.2 Interpretations of Mixed Strategy Nash Equilibrium 3.3 Correlated Equilibrium 44 3.4 Evolutionary Equilibrium 48 Notes 51

31 37

4

Rationalizability and Iterated Elimination of Dominated Actions 53 4.1 Rationalizability 53 4.2 Iterated Elimination of StrictlyDominated Actions 58 4.3 Iterated Elimination of Weakly Dominated Actions 62 Notes 64 Knowledge and Equilibrium 67 5.1 A Model of Knowledge 67 5.2 Common Knowledge 73 5.3 Can People Agree to Disagree? 75 5.4 Knowledge and Solution Concepts 76 5.5 The Electronic Mail Game 81 Notes 84

5

II
6

Extensive Games with Perfect Information
Extensive Games with Perfect Information 89 6.1 ExtensiveGames with Perfect Information 89 6.2 Subgame Perfect Equilibrium 97 6.3 Two Extensions of the Definition of a Game 101 6.4 The Interpretation of a Strategy 103 6.5 Two Notable Finite Horizon Games 105 6.6 Iterated Elimination of Weakly Dominated Strategies Notes 114 Bargaining Games 117 7.1 Bargaining and Game Theory 117 7.2 A Bargaining Game of Alternating Offers 7.3 Subgame Perfect Equilibrium121 7.4 Variations and Extensions 127 Notes 131

87

108

7

118

Contents

vii

8

Repeated Games 133 8.1 The Basic Idea 133 8.2 Infinitely Repeated Games vs. Finitely Repeated Games 134 8.3 Infinitely Repeated Games: Definitions 136 8.4 Strategies as Machines 140 8.5 Trigger Strategies: Nash Folk Theorems 143 8.6 Punishing for a Limited Length of Time: A Perfect Folk Theorem for...