Notes for a Course in Game Theory

Maxwell B. Stinchcombe
Fall Semester, 2002. Unique #29775

Contents

0 Organizational Stuff 7
1 Choice Under Uncertainty 9
1.1 The basics model of choice under uncertainty . . . . . . . . . . . . . . . . . . 9
1.1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.2 The basic model of choice under uncertainty . . . . . . . . . . . . . . 10
1.1.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 The bridge crossing and rescaling Lemmas . . . . . . . . . . . . . . . . . . . 13
1.3 Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Correlated Equilibria in Static Games 19
2.1 Generalities about static games . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Dominant Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Two classic games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Signals and Rationalizability . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5 Two classic coordination games . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.6 Signals and Correlated Equilibria . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6.1 The common prior assumption . . . . . . . . . . . . . . . . . . . . . . 24
2.6.2 The optimization assumption . . . . . . . . . . . . . . . . . . . . . . 25
2.6.3 Correlated equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.6.4 Existence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.7 Rescaling and equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.8 How correlated equilibria might arise . . . . . . . . . . . . . . . . . . . . . . 28
2.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Nash Equilibria in Static Games 33
3.1 Nash equilibria are uncorrelated equilibria . . . . . . . . . . . . . . . . . . . 33
3.2 2x2 games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.1 Three more stories . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.2 Rescaling and the strategic equivalence of games . . . . . . . . . . . . 39
3.3 The gap between equilibrium and Pareto rankings . . . . . . . . . . . . . . . 41
3.3.1 Stag Hunt reconsidered . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Prisoners' Dilemma reconsidered . . . . . . . . . . . . . . . . . . . . 42
3.3.3 Conclusions about Equilibrium and Pareto rankings . . . . . . . . . . 42
3.3.4 Risk dominance and Pareto rankings . . . . . . . . . . . . . . . . . . 43
3.4 Other static games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4.1 In nite games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4.2 Finite Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5 Harsanyi's interpretation of mixed strategies . . . . . . . . . . . . . . . . . . 52
3.6 Problems on static games . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4 Extensive Form Games: The Basics and Dominance Arguments 55
4.1 Examples of extensive formgame trees . . . . . . . . . . . . . . . . . . . . . 55
4.1.1 Simultaneous move games as extensive formgames . . . . . . . . . . 56
4.1.2 Some games with \incredible" threats . . . . . . . . . . . . . . . . . . 57
4.1.3 Handling probability 0 events . . . . . . . . . . . . . . . . . . . . . . 58
4.1.4 Signaling games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.1.5 Spying games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.1.6 Other extensive formgames that I like . . . . . . . . . . . . . . . . . 70
4.2 Formalities of extensive formgames . . . . . . . . . . . . . . . . . . . . . . . 74
4.3 Extensive formgames and weak dominance arguments . . . . . . . . . . . . 79
4.3.1 Atomic Handgrenades . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.2 A detour through subgame perfection . . . . . . . . . . . . . . . . . . 80
4.3.3 A rst step toward de ning equivalence for games . . . . . . . . . . . 83
4.4 Weak dominance arguments, plain and iterated . . . . . . . . . . . . . . . . 84
4.5 Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.5.1 Hiring amanager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.5.2 Funding a public good . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.5.3 Monopolist selling to di erent types . . . . . . . . . . . . . . . . . . . 92
4.5.4 Efficiency in sales and the revelation principle . . . . . . . . . . . . . 94
4.5.5 Shrinkage of the equilibrium set . . . . . . . . . . . . . . . . . . . . . 95
4.6 Weak dominance with respect to sets . . . . . . . . . . . . . . . . . . . . . . 95
4.6.1 Variants on iterated deletion of dominated sets . . . . . . . . . . . . . 95
4.6.2 Self-referential tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.6.3 A horse game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.6.4 Generalities about signaling games (redux) . . . . . . . . . . . . . . . 99
4.6.5 Revisiting a speci c entry-deterrence signaling game . . . . . . . . . . 100
4.7 Kuhn's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.8 Equivalence of games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.9 Some other problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5 Mathematics for Game Theory 113
5.1 Rational numbers, sequences, real numbers . . . . . . . . . . . . . . . . . . . 113
5.2 Limits, completeness, glb's and lub's . . . . . . . . . . . . . . . . . . . . . . 116
5.2.1 Limits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.2.2 Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.2.3 Greatest lower bounds and least upper bounds . . . . . . . . . . . . . 117
5.3 The contraction mapping theorem and applications . . . . . . . . . . . . . . 118
5.3.1 StationaryMarkov chains . . . . . . . . . . . . . . . . . . . . . . . . 119
5.3.2 Some evolutionary arguments about equilibria . . . . . . . . . . . . . 122
5.3.3 The existence and uniqueness of value functions . . . . . . . . . . . . 123
5.4 Limits and closed sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.5 Limits and continuity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.6 Limits and compactness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.7 Correspondences and xed point theorem . . . . . . . . . . . . . . . . . . . . 127
5.8 Kakutani's xed point theorem and equilibrium existence results . . . . . . . 128
5.9 Perturbation based theories of equilibrium re nement . . . . . . . . . . . . . 129
5.9.1 Overview of perturbations . . . . . . . . . . . . . . . . . . . . . . . . 129
5.9.2 Perfection by Selten . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.9.3 Properness byMyerson . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.9.4 Sequential equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
5.9.5 Strict perfection and stability by Kohlberg and Mertens . . . . . . . . 135
5.9.6 Stability by Hillas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.10 Signaling game exercises in re nement . . . . . . . . . . . . . . . . . . . . . 137
6 Repeated Games 143
6.1 The Basic Set-Up and a Preliminary Result . . . . . . . . . . . . . . . . . . 143
6.2 Prisoners' Dilemma nitely and in nitely . . . . . . . . . . . . . . . . . . . . 145
6.3 Some results on nite repetition . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.4 Threats in nitely repeated games . . . . . . . . . . . . . . . . . . . . . . . . 148
6.5 Threats in in nitely repeated games . . . . . . . . . . . . . . . . . . . . . . . 150
6.6 Rubinstein-Stahl bargaining . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.7 Optimal simple penal codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
6.8 Abreu's example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
6.9 Harris' formulation of optimal simple penal codes . . . . . . . . . . . . . . . 152
6.10 \Shunning," market-place racism, and other examples . . . . . . . . . . . . . 154
7 Evolutionary Game Theory 157
7.1 An overview of evolutionary arguments . . . . . . . . . . . . . . . . . . . . . 157
7.2 The basic `large' population modeling . . . . . . . . . . . . . . . . . . . . . . 162
7.2.1 General continuous time dynamics . . . . . . . . . . . . . . . . . . . 163
7.2.2 The replicator dynamics in continuous time . . . . . . . . . . . . . . 164
7.3 Some discrete time stochastic dynamics . . . . . . . . . . . . . . . . . . . . . 166
7.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167