This page intentionally left blank
Games, Strategies, and Decision Making
Joseph E. Harrington, Jr. Johns Hopkins University
Worth Publishers
Senior Publisher: Craig Bleyer
Acquisitions Editor: Sarah Dorger
Senior Marketing Manager: Scott Guile
Market Research and Development: Steven Rigolosi
Developmental Editor: Carol Pritchard-Martinez
Consulting Editor: Paul Shensa
Associate Editor: Matthew Driskill
Photo Editor: Bianca Moscatelli
Art Director: Babs Reingold
Photo Researcher: Julie Tesser
Senior Designer, Cover Designer: Kevin Kall
Interior Designer: Lissi Sigillo
Associate Managing Editor: Tracey Kuehn
Project Editors: Dana Kasowitz
Dennis Free, Aptara®, Inc.
Production Manager: Barbara Anne Seixas
Composition: Aptara®, Inc.
Printing and Binding: RR Donnelley
Library of Congress Control Number: 2008925817
ISBN-13: 978-0-7167-6630-8
ISBN-10: 0-7167-6630-2
© 2009 by Worth Publishers
All rights reserved
Printed in the United States of America
First printing
Worth Publishers
41 Madison Avenue
New York, NY 10010
www.worthpublishers.com
www.worthpublishers.com
Games, Strategies, and Decision Making
To Colleen and Grace, who as children taught me love,
and who as teenagers taught me strategy.
This page intentionally left blank
vi
Joseph E. Harrington, Jr., is Professor of Economics at Johns Hopkins University. He has served on various editorial boards, including those of the RAND Journal of Economics, Foundations and Trends in Microeconomics, and the Southern Economic Journal. His research has appeared in top journals in a variety of disciplines, including economics (e.g., the American Economic Review, Journal of Political Economy, and Games and Economic Behavior), po- litical science (Economics and Politics, Public Choice), sociology (American Journal of Sociology), management science (Management Science), and psy- chology (Journal of Mathematical Psychology). He is a coauthor of Economics of Regulation and Antitrust, which is in its fourth edition.
Brief Contents
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv
C H A P T E R 1
Introduction to Strategic Reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
C H A P T E R 2
Building a Model of a Strategic Situation . . . . . . . . . . . . . . . . . . . 17
C H A P T E R 3
Eliminating the Impossible: Solving a Game when Rationality Is Common Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
C H A P T E R 4
Stable Play: Nash Equilibria in Discrete Games with Two or Three Players . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
C H A P T E R 5
Stable Play: Nash Equilibria in Discrete n-Player Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
C H A P T E R 6
Stable Play: Nash Equilibria in Continuous Games . . . 147
C H A P T E R 7
Keep ’Em Guessing: Randomized Strategies . . . . . . . . . . . . . . 181
C H A P T E R 8
Taking Turns: Sequential Games with Perfect Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
C H A P T E R 9
Taking Turns in the Dark: Sequential Games with Imperfect Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
vii
BRIEF CONTENTS viii
C H A P T E R 1 0
I Know Something You Don’t Know: Games with Private Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
C H A P T E R 1 1
What You Do Tells Me Who You Are: Signaling Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
C H A P T E R 1 2
Lies and the Lying Liars That Tell Them: Cheap Talk Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
C H A P T E R 1 3
Playing Forever: Repeated Interaction with Infinitely Lived Players . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
C H A P T E R 1 4
Cooperation and Reputation: Applications of Repeated Interaction with Infinitely Lived Players . . . . . . . . . . . . . . . . . . . . 423
C H A P T E R 1 5
Interaction in Infinitely Lived Institutions . . . . . . . . . . . . . . . . . 451
C H A P T E R 1 6
Evolutionary Game Theory and Biology: Evolutionarily Stable Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
C H A P T E R 1 7
Evolutionary Game Theory and Biology: Replicator Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
Answers to “Check Your Understanding” Questions . . . . . . . . . . . . . . . . . . . . . . S-1
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G-1
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I-1
ix
Competition for Elected Office . . . . . . . . . . . . . . . . . . . . . 38 The Science 84 Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.6 Moving from the Extensive Form and Strategic Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Baseball, II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Galileo Galilei and the Inquisition, II . . . . . . . . . . . . . . . . 40 Haggling at an Auto Dealership, II . . . . . . . . . . . . . . . . . 41
2.7 Going from the Strategic Form to the Extensive Form . . . . . . . . . . . . . . . . . . . . . . . . 42 2.8 Common Knowledge . . . . . . . . . . . . . . . . . . . . . 43 2.9 A Few More Issues in Modeling Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
C H A P T E R 3
Eliminating the Impossible: Solving a Game when
Rationality Is Common Knowledge 55
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2 Solving a Game when Players Are Rational . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.1 Strict Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
White Flight and Racial Segregation in Housing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Banning Cigarette Advertising on Television . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2.2 Weak Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Bidding at an Auction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 The Proxy Bid Paradox at eBay . . . . . . . . . . . . . . . . . . . . 66
3.3 Solving a Game when Players Are Rational and Players Know that Players Are Rational . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Team-Project Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv
C H A P T E R 1
Introduction to Strategic Reasoning 1
1.1 Who Wants to Be a Game Theorist? . . . 1 1.2 A Sampling of Strategic Situations . . . . . 3 1.3 Whetting Your Appetite: The Game of Concentration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Psychological Profile of a Player . . . . . . . 8 1.4.1 Preferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.2 Beliefs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.3 How Do Players Differ? . . . . . . . . . . . . . . . . . . . 12
1.5 Playing the Gender Pronoun Game . . . 13 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
C H A P T E R 2
Building a Model of a Strategic Situation 17
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Extensive Form Games: Perfect Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Baseball, I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Galileo Galilei and the Inquisition, I . . . . . . . . . . . . . . . . 22 Haggling at an Auto Dealership, I . . . . . . . . . . . . . . . . . 24
2.3 Extensive Form Games: Imperfect Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Mugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 U.S. Court of Appeals for the Federal Circuit . . . . . . . 30 The Iraq War and Weapons of Mass Destruction . . . 32
2.4 What Is a Strategy? . . . . . . . . . . . . . . . . . . . . . . . 34 2.5 Strategic Form Games . . . . . . . . . . . . . . . . . . . 36
Tosca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Contents
Existence-of-God Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 Boxed-Pigs Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.4 Solving a Game when Rationality Is Common Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.4.1 The Doping Game: Is It Rational for Athletes to Use Steroids? . . . . . . . . . . . . . . . . . . . . . . . . 73
3.4.2 Iterative Deletion of Strictly Dominated Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.5 Appendix: Strict and Weak Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 3.6 Appendix: Rationalizability (Advanced) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
C H A P T E R 4
Stable Play: Nash Equilibria in Discrete Games with Two
or Three Players 89
4.1 Defining Nash Equilibrium . . . . . . . . . . . . . . 89 4.2 Classic Two-Player Games . . . . . . . . . . . . . . 92
Prisoners’ Dilemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 A Coordination Game—Driving Conventions . . . . . . . 95 A Game of Coordination and Conflict—Telephone . . 95 An Outguessing Game—Rock–Paper–Scissors . . . . . 97 Conflict and Mutual Interest in Games . . . . . . . . . . . . . 99
4.3 The Best-Reply Method . . . . . . . . . . . . . . . . . 99 4.4 Three-Player Games . . . . . . . . . . . . . . . . . . . . 101
American Idol Fandom . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Voting, Sincere or Devious? . . . . . . . . . . . . . . . . . . . . . . 102 Promotion and Sabotage . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.5 Foundations of Nash Equilibrium . . . 109 4.5.1 Relationship to Rationality Is Common Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.5.2 The Definition of a Strategy, Revisited . 110
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.6 Appendix: Formal Definition of Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . 116 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
C H A P T E R 5
Stable Play: Nash Equilibria in Discrete n-Player
Games 117
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.2 Symmetric Games . . . . . . . . . . . . . . . . . . . . . . . 118
The Sneetches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Airline Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Operating Systems: Mac or Windows? . . . . . . . . . . . . 125 Applying for an Internship . . . . . . . . . . . . . . . . . . . . . . . . 128
5.3 Asymmetric Games . . . . . . . . . . . . . . . . . . . . . 130 Entry into a Market . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Civil Unrest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
5.4 Selecting among Nash Equilibria . . . 137 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
C H A P T E R 6
Stable Play: Nash Equilibria in Continuous Games 147
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 6.2 Solving for Nash Equilibria without Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Price Competition with Identical Products . . . . . . . . . 149 Neutralizing Price Competition with
Price-Matching Guarantees . . . . . . . . . . . . . . . . . . . . . 152 Competing for Elected Office . . . . . . . . . . . . . . . . . . . . . 154
6.3 Solving for Nash Equilibria with Calculus (Optional) . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
Price Competition with Differentiated Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .160
Tragedy of the Commons— The Extinction of the Woolly Mammoth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Charitable Giving and the Power of Matching Grants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
x CONTENTS
C H A P T E R 7
Keep ’Em Guessing: Randomized Strategies 181
7.1 Police Patrols and the Drug Trade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 7.2 Making Decisions under Uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 7.2.1 Probability and Expectation . . . . . . . . . 182
7.2.2 Preferences over Uncertain Options . . . 185
7.2.3 Ordinal vs. Cardinal Payoffs . . . . . . . . . 186
7.3 Mixed Strategies and Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 7.3.1 Back on the Beat . . . . . . . . . . . . . . . . . 187
7.3.2 Some General Properties of a Nash Equilibrium in Mixed Strategies . . . . . 191
7.4 Examples . . . . . . . . . . . . . . . . . . . .192 Avranches Gap in World War II . . . . . . . . . . . . . . . 193 Entry into a Market . . . . . . . . . . . . . . . . . . . . . . . 197
7.5 Advanced Examples . . . . . . . . . . . . 198 Penalty Kick in Soccer . . . . . . . . . . . . . . . . . . . . . 198 Slash ’em Up: Friday the 13th . . . . . . . . . . . . . . . 201 Bystander Effect . . . . . . . . . . . . . . . . . . . . . . . . . . 204
7.6 Games of Pure Conflict and Cautious Behavior . . . . . . . . . . . . . 207 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
7.7 Appendix: Formal Definition of Nash Equilibrium in Mixed Strategies . . . . . . . . . . . . . . . . . . . . . . .215 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
C H A P T E R 8
Taking Turns: Sequential Games with Perfect
Information 219
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 8.2 Backward Induction and Subgame Perfect Nash Equilibrium . . . . . . . . . . . . . . . . . . . 221
8.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 Cuban Missile Crisis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 Enron and Prosecutorial
Prerogative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 Racial Discrimination and Sports . . . . . . . . . . . . . . . . . 229
8.4 Waiting Games: Preemption and Attrition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 8.4.1 Preemption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
8.4.2 War of Attrition . . . . . . . . . . . . . . . . . . . . . . . . . . 238
8.5 Do People Reason Using Backward Induction? . . . . . . . . . . . . . . . . . . . . . . . . 239 8.5.1 Experimental Evidence and Backward Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
8.5.2 A Logical Paradox with Backward Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .242
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
C H A P T E R 9
Taking Turns in the Dark: Sequential
Games with Imperfect Information 255
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 9.2 Subgame Perfect Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
British Intelligence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
9.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 OS/2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 Agenda Control in the Senate . . . . . . . . . . . . . . . . . . . . 268
9.4 Commitment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 9.4.1 Deterrence of Entry . . . . . . . . . . . . . . . . . . . . . . 270
9.4.2 Managerial Contracts and Competition: East India Trade in the Seventeenth Century . . . . . . . . . . . . . . . . . . . . . . . . 277
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
CONTENTS xi
C H A P T E R 1 0
I Know Something You Don’t Know: Games with Private
Information 291
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 10.2 A Game of Incomplete Information: The Munich Agreement . . . . 291 10.3 Bayesian Games and Bayes–Nash Equilibrium . . . . . . . . . . . . . . . . . . . . 296
Gunfight in the Wild West . . . . . . . . . . . . . . . . . . . . . . . . 298
10.4 When All Players Have Private Information: Auctions . . . . . . . . . . . . . . . . . . . . . . . . 301
Independent Private Values and Shading Your Bid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
Common Value and the Winner’s Curse . . . . . . . . . . . 304
10.5 Voting on Committees and Juries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 10.5.1 Strategic Abstention . . . . . . . . . . . . . . . . . . . . 307
10.5.2 Sequential Voting in the Jury Room . . . 309
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
10.6 Appendix: Formal Definition of Bayes–Nash Equilibrium . . . . . . . . . . . . . . . . 318 10.7 Appendix: First-Price, Sealed-Bid Auction with a Continuum of Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 10.7.1 Independent Private Values . . . . . . . . . . . . 319
10.7.2 Common Value . . . . . . . . . . . . . . . . . . . . . . . . . 321
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
C H A P T E R 1 1
What You Do Tells Me Who You Are: Signaling Games 325
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 11.2 Perfect Bayes–Nash Equilibrium . . . .326
Management Trainee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
11.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 Lemons and the Market for Used Cars . . . . . . . . . . . 333
Courtship . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 Brinkmanship . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
11.4 Appendix: Bayes’s Rule and Updating Beliefs . . . . . . . . . . . . . . . . . . . . . . . . 354 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
C H A P T E R 1 2
Lies and the Lying Liars That Tell Them: Cheap
Talk Games 359
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 12.2 Communication in a Game-Theoretic World . . . . . . . . . . . . . . . . . . . . . . 360 12.3 Signaling Information . . . . . . . . . . . . . . . . 363
Defensive Medicine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363 Stock Recommendations . . . . . . . . . . . . . . . . . . . . . . . . . 367
12.4 Signaling Intentions . . . . . . . . . . . . . . . . . . 374 12.4.1 Preplay Communication in Theory . . . . . 374
12.4.2 Preplay Communication in Practice . . . . 379
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
C H A P T E R 1 3
Playing Forever: Repeated Interaction with Infinitely
Lived Players 391
13.1 Trench Warfare in World War I . . . . . 391 13.2 Constructing a Repeated Game . . . 393 13.3 Trench Warfare: Finite Horizon . . . . 398 13.4 Trench Warfare: Infinite Horizon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401 13.5 Some Experimental Evidence for the Repeated Prisoners’ Dilemma . . . 406 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
xii CONTENTS
13.6 Appendix: Present Value of a Payoff Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . 416 13.7 Appendix: Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
C H A P T E R 1 4
Cooperation and Reputation: Applications of Repeated
Interaction with Infinitely Lived
Players 423
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 14.2 A Menu of Punishments . . . . . . . . . . . . . 424 14.2.1 Price-Fixing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
14.2.2 Temporary Reversion to Moderate Rates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
14.2.3 Price Wars: Temporary Reversion to Low Rates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
14.2.4 A More Equitable Punishment . . . . . . . . . 430
14.3 Quid-Pro-Quo . . . . . . . . . . . . . . . . . . . . . . . . . . 431 U.S. Congress and Pork-Barrel Spending . . . . . . . . . 431 Vampire Bats and Reciprocal Altruism . . . . . . . . . . . . 434
14.4 Reputation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437 Lending to Kings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437 Henry Ford and the $5 Workday . . . . . . . . . . . . . . . . . 439
14.5 Imperfect Monitoring and Antiballistic Missiles . . . . . . . . . . . . . . . . . . . . . . . . . 441 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
C H A P T E R 1 5
Interaction in Infinitely Lived Institutions 451
15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451 15.2 Cooperation with Overlapping Generations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452
Tribal Defense . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453 Taking Care of Your Elderly Parents . . . . . . . . . . . . . 456 Political Parties and Lame-Duck Presidents . . . . . . 458
15.3 Cooperation in a Large Population . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
eBay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464 Medieval Law Merchant . . . . . . . . . . . . . . . . . . . . . . . . . . 469
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
C H A P T E R 1 6
Evolutionary Game Theory and Biology: Evolutionarily
Stable Strategies 479
16.1 Introducing Evolutionary Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 16.2 Hawk–Dove Conflict . . . . . . . . . . . . . . . . . . 481 16.3 Evolutionarily Stable Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
“Stayin’ Alive” on a Cowpat . . . . . . . . . . . . . . . . . . . . . 488
16.4 Properties of an ESS . . . . . . . . . . . . . . . . . 491 Side-Blotched Lizards . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493
16.5 Multipopulation Games . . . . . . . . . . . . . . 496 Parental Care . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
16.6 Evolution of Spite . . . . . . . . . . . . . . . . . . . . 499 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
C H A P T E R 1 7
Evolutionary Game Theory and Biology: Replicator
Dynamics 507
17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507 17.2 Replicator Dynamics and the Hawk–Dove Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508 17.3 General Definition of the Replicator Dynamic . . . . . . . . . . . . . . . . . . . . . 512
CONTENTS xiii
17.4 ESS and Attractors of the Replicator Dynamic . . . . . . . . . . . . . . . . . . . . . . . . . . 513 17.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
Stag Hunt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515 Handedness in Baseball . . . . . . . . . . . . . . . . . . . . . . . . . . 517 Evolution of Cooperation . . . . . . . . . . . . . . . . . . . . . . . . 521
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532
Answers to “Check Your Understanding” Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . S-1
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G-1
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I-1
xiv CONTENTS
xv
Preface
For Whom Is This Book Intended? When I originally decided to offer an undergraduate course on game theory, the first item on my to-do list was figuring out the target audience. As a pro- fessor of economics, I clearly wanted the course to provide the tools and ap- plications valuable to economics and business majors. It was also the case that my research interests had recently expanded beyond economics to include is- sues in electoral competition and legislative bargaining, which led me to think, “Wouldn’t it be fun to apply game theory to politics, too?” So, the target audience expanded to include political science and international relations ma- jors. Then I thought about the many fascinating applications of game theory to history, literature, sports, crime, theology, war, biology, and everyday life. Even budding entrepreneurs and policy wonks have interests that extend beyond their majors. As I contemplated the diversity of these applications, it became more and more apparent that game theory would be of interest to a broad spectrum of college students. Game theory is a mode of reasoning that applies to all encounters between humans (and even some other members of the animal kingdom) and deserves a place in a general liberal arts education.
After all of this internal wrangling, I set about constructing a course (and now a book) that would meet the needs of majors in economics, business, po- litical science, and international relations—the traditional disciplines to which game theory has been applied—but that would also be suitable for the general college population. After 15 years of teaching this class, the course remains as fresh and stimulating to me as when I taught it the first time. Bringing together such an eclectic student body while applying game theory to a varied terrain of social environments has made for lively and insightful intellectual discourse. And the enthusiasm that students bring to the subject continues to amaze me. This zeal is perhaps best reflected in a class project that has students scour real, historical, and fictional worlds for strategic settings and then analyze them using game theory. Student projects have dealt with a great range of subjects, such as the Peloponnesian War, patent races among drug companies, the tele- vision show Survivor, accounting scandals, and dating dilemmas. The quality and breadth of these projects is testimony to the depth and diversity of stu- dents’ interest in game theory. This is a subject that can get students fired up!
Having taught a collegewide game theory course for 15 years, I’ve learned what is comprehensible and what is befuddling, what excites students and what allows them to catch up on their sleep. These experiences—though hum- bling at times—provided the fodder for the book you now hold in your hands.
How Does This Book Teach Game Theory? Teaching a game theory course intended for the general college population raises the challenge of dealing with a diversity of academic backgrounds. Although many students have a common desire to learn about strategic reasoning, they dif- fer tremendously in their mathematics comfort zone. The material has to be
presented so that it works for students who have avoided math since high school, while at the same time not compromising on the concepts, lest one cheat the better prepared students. A book then needs to both appeal to those who can effortlessly swim in an ocean of mathematical equations and those who would drown most ungracefully. A second challenge is to convey these concepts while maintaining enthusiasm for the subject. Most students are not intrinsically enamored with game-theoretic concepts, but it is a rare student who is not en- tranced by the power of game theory when it is applied to understanding human behavior. Let me describe how these challenges have been addressed in this book.
Concepts Are Developed Incrementally with a Minimum of Mathematics A chapter typically begins with a specific strategic situation that draws in the reader and motivates the concept to be developed. The concept is first intro- duced informally to solve a particular situation. Systematic analysis of the concept follows, introducing its key components in turn and gradually build- ing up to the concept in its entirety or generality. Finally, a series of examples serve to solidify, enhance, and stimulate students’ understanding. Although the mathematics used is simple (nothing more than high school algebra), the content is not compromised. This book is no Game Theory for Dummies or The Complete Idiot’s Guide to Strategy; included are extensive treatments of games of imperfect information, games of incomplete information with signaling (in- cluding cheap-talk games), and repeated games that go well beyond simple grim punishments. By gradually building structure, even quite sophisticated settings and concepts are conveyed with a minimum of fuss and frustration.
The Presentation Is Driven by a Diverse Collection of Strategic Scenarios Many students are likely to be majors from economics, business, political sci- ence, and international relations, so examples from these disciplines are the most common ones used. (A complete list of all the strategic scenarios and ex- amples used in the text can be found on the inside cover.) Still, they make up only about one-third of the examples, because the interests of students (even economics majors) typically go well beyond these traditional game-theoretic set- tings. Students are very interested in examples from history, fiction, sports, and everyday life (as reflected in the examples that they choose to pursue in a class project). A wide-ranging array of examples will hopefully provide something for everyone—a feature that is crucial to maintaining enthusiasm for the sub- ject. To further charge up enthusiasm, examples typically come with rich con- text, which can be in the form of anecdotes (some serious, some amusing), intriguing asides, empirical evidence, or experimental findings. Interesting context establishes the relevance of the theoretical exercise and adds real-world meat to the skeleton of theory. In this book, students do not just learn a clever answer to a puzzle, but will acquire genuine insights into human behavior.
To assist students in the learning process, several pedagogical devices are deployed throughout the book.
■ Check Your Understanding exercises help ensure that students are clear on the concepts. Following discussion of an important concept, students are given the opportunity to test their understanding by solving
xvi PREFACE
a short Check Your Understanding exercise. Answers are provided at the end of the book.
■ Boxed Insights succinctly convey key conceptual points. Although we explore game theory within the context of specific strategic scenar- ios, often the goal is to derive a lesson of general relevance. Such lessons are denoted as Insights. We also use this category to state general results pertinent to the use of game theory.
■ Boxed Conundrums are yet-to-be-solved puzzles. In spite of the con- siderable insight into human behavior that game theory has delivered, there is still much that we do not understand. To remind myself of this fact and to highlight it to students, peppered throughout the book are challenging situations that currently defy easy resolution. These are ap- propriately denoted Conundrums.
■ Chapter Summaries synthesize the key lessons of each chapter. Students will find that end-of-chapter summaries not only review the key concepts and terms of the chapter, but offer new insights into the big pic- ture.
■ Exercises give students a chance to apply concepts and methods in a variety of interesting contexts. While some exercises revisit examples introduced earlier in the book, others introduce new and interesting sce- narios, many based on real-life situations. (See the inside cover of the text for a list of examples explored in chapter exercises.)
How Is This Book Organized? Let me now provide a tour of the book and describe the logic behind its struc- ture. After an introduction to game theory in Chapter 1, Chapter 2 is about constructing a game by using the extensive and strategic forms. My experience is that students are more comfortable with the extensive form because it maps more readily to the real world with its description of the sequence of deci- sions. Accordingly, I start by working with the extensive form—initiating our journey with a kidnapping scenario—and follow it up with the strategic form, along with a discussion of how to move back and forth between them. A virtue of this presentation is that a student quickly learns not only that a strategic form game can represent a sequence of decisions, but, more generally, how the extensive and strategic forms are related.
Although the extensive form is more natural as a model of a strategic situ- ation, the strategic form is generally easier to solve. This is hardly surprising, since the strategic form was introduced as a more concise and manageable mathematical representation. We then begin by solving strategic form games in Part 2 and turn to solving extensive form games in Part 3.
The approach taken to solving strategic form games in Part 2 begins by lay- ing the foundations of rational behavior and the construction of beliefs based upon players being rational. Not only is this logically appealing, but it makes for a more gradual progression as students move from easier to more difficult con- cepts. Chapter 3 begins with the assumption of rational players and applies it to solving a game. Although only special games can be solved solely with the as- sumption of rational players, it serves to introduce students to the simplest method available for getting a solution. We then move on to assuming that each player is rational and that each player believes that other players are rational.
PREFACE xvii
These slightly stronger assumptions allow us to consider games that cannot be solved solely by assuming that players are rational. Our next step is to assume that each player is rational, that each player believes that all other players are rational, and that each player believes that all other players believe that all other players are rational. Finally, we consider when rationality is common knowl- edge and the method of the iterative deletion of strictly dominated strategies (IDSDS). In an appendix to Chapter 3, the more advanced concept of rational- izable strategies is covered. Although some books cover it much later, this is clearly its logical home, since, having learned the IDSDS, students have the right mind-set to grasp rationalizability (if you choose to cover it).
Nash equilibrium is generally a more challenging solution concept for stu- dents because it involves simultaneously solving all players’ problems. With Chapter 4, we start slowly with some simple 2 � 2 games and move on to games allowing for two players with three strategies and then three players with two strategies. Games with n players are explored in Chapter 5. Section 5.4 examines the issue of equilibrium selection and is designed to be self- contained; a reader need only be familiar with Nash equilibrium (as described in Chapter 4) and need not have read the remainder of Chapter 5. Games with a continuum of strategies are covered in Chapter 6 and include those that can be solved without calculus (Section 6.2) and, for a more advanced course, with calculus (Section 6.3).
The final topic in Part 2 is mixed strategies, which is always a daunting sub- ject for students. Chapter 7 begins with an introductory treatment of proba- bility, expectation, and expected utility theory. Given the complexity of working with mixed strategies, the chapter is compartmentalized so that an instructor can choose how deeply to go into the subject. Sections 7.1–7.4 cover the basic material. More complex games, involving more than two players or when there are more than two strategies, are in Section 7.5, while the maximin strat- egy for zero-sum games is covered in Section 7.6.
Part 3 tackles extensive form games. (Students are recommended to re- view the structure of these games described in Sections 2.2–2.4; repetition of the important stuff never hurts.) Starting with games of perfect information, Chapter 8 introduces the solution concept of subgame perfect Nash equilibrium and the algorithm of backward induction. The definition of subgame perfect Nash equilibrium is tailored specifically to games of perfect information. That way, students can become comfortable with this simpler notion prior to facing the more complex definition in Chapter 9 that applies as well to games of im- perfect information. Several examples are provided, with particular attention to waiting games and games of attrition. Section 8.5 looks at some logical and ex- perimental sources of controversy with backward induction, topics lending themselves to spirited in-class discussion. Games of imperfect information are examined in Chapter 9. After introducing the idea of a “game within a game” and how to properly analyze it, a general definition of subgame perfect Nash equilibrium is provided. The concept of commitment is examined in Section 9.4.