Alicia gametree co kr english

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.

Part 4 covers games of incomplete information, which is arguably the most challenging topic in an introductory game theory class. My approach is to slow down the rate at which new concepts are introduced. Three chapters are devoted to the topic, which allows both the implementation of this incre- mental approach and extensive coverage of the many rich applications involv- ing private information.

xviii PREFACE

Chapter 10 begins with an example based on the 1938 Munich Agreement and shows how a game of imperfect information can be created from a game of incomplete information. With a Bayesian game thus defined, the solution con- cept of Bayes–Nash equilibrium is introduced. Chapter 10 focuses exclusively on when players move simultaneously and thereby extracts away from the more subtle issue of signaling. Chapter 10 begins with two-player games in which only one player has private information and then takes on the case of both players possessing private information. Given the considerable interest in auctions among instructors and students alike, both independent private-value auctions and common-value, first-price, sealed-bid auctions are covered, and an optional chapter appendix covers a continuum of types. The latter requires calculus and is a nice complement to the optional calculus-based section in Chapter 6. (In ad- dition, the second-price, sealed-bid auction is covered in Chapter 3.)

Chapter 11 assumes that players move sequentially, with the first player to move having private information. Signaling then emerges, which means that, in response to the first player’s action, the player who moves second Bayesian updates her beliefs as to the first player’s type. An appendix introduces Bayes’s rule and how to use it. After the concepts of sequential rationality and consis- tent beliefs are defined, perfect Bayes–Nash equilibrium is introduced. This line of analysis continues into Chapter 12, where the focus is on cheap talk games. In Section 12.4, we also take the opportunity to explore signaling one’s intentions, as opposed to signaling information. Although not involving a game of incomplete information, the issue of signaling one’s intentions natu- rally fits in with the chapter’s focus on communication. The material on sig- naling intentions is a useful complement to Chapter 9—as well as to Chapter 7—as it is a game of imperfect information in that it uses mixed strate- gies, and could be covered without otherwise using material from Part 4.

Part 5 is devoted to repeated games, and again, the length of the treat- ment allows us to approach the subject gradually and delve into a diverse col- lection of applications. In the context of trench warfare in World War I, Chapter 13 focuses on conveying the basic mechanism by which cooperation is sustained through repetition. We show how to construct a repeated game and begin by examining finitely repeated games, in which we find that coop- eration is not achieved. The game is then extended to have an indefinite or in- finite horizon, a feature which ensures that cooperation can emerge. Crucial to the chapter is providing an operational method for determining whether a strategy profile is a subgame perfect Nash equilibrium in an extensive form game with an infinite number of moves. The method is based on dynamic pro- gramming and is presented in a user-friendly manner, with an accompanying appendix to further explain the underlying idea. Section 13.5 presents empir- ical evidence—both experimental and in the marketplace—pertaining to coop- eration in repeated Prisoners’ Dilemmas. Finally, an appendix motivates and describes how to calculate the present value of a payoff stream.

Chapters 14 and 15 explore the richness of repeated games through a series of examples. Each example introduces the student to a new strategic scenario, with the objective of drawing a new general lesson about the mechanism by which cooperation is sustained. Chapter 14 examines different types of pun- ishment (such as short, intense punishments and asymmetric punishments), cooperation that involves taking turns helping each other (reciprocal altruism), and cooperation when the monitoring of behavior is imperfect. Chapter 15

PREFACE xix

considers environments poorly suited to sustaining cooperation—environ- ments in which players are finitely lived or players interact infrequently. Nevertheless, in practice, cooperation has been observed in such inhospitable settings, and Chapter 15 shows how it can be done. With finitely lived players, cooperation can be sustained with overlapping generations. Cooperation can also be sustained with infrequent interactions if they occur in the context of a population of players who share information.

The book concludes with coverage of evolutionary game theory in Part 6. Chapter 16 is built around the concept of an evolutionarily stable strat- egy (ESS)—an approach based upon finding rest points (and thus analogous to one based on finding Nash equilibria)—and relies on Chapter 7’s coverage of mixed strategies as a prerequisite. Chapter 17 takes an explicitly dynamic approach, using the replicator dynamic (and avoids the use of mixed strate- gies). Part 6 is designed so that an instructor can cover either ESS or the repli- cator dynamic or both. For coverage of ESS, Chapter 16 should be used. If coverage is to be exclusively of the replicator dynamic, then students should read Section 16.1—which provides a general introduction to evolutionary game theory—and Chapter 17, except for Section 17.4 (which relates stable outcomes under the replicator dynamic to those which are an ESS).

How Can This Book Be Tailored to Your Course? The Course Guideline (see the accompanying table) is designed to provide some general assistance in choosing chapters to suit your course. The Core treatment includes those chapters which every game theory course should cover. The Broad Social Science treatment covers all of the primary areas of game theory that are applicable to the social sciences. In particular, it goes beyond the Core treatment by including select chapters on games of incomplete information and repeated games. Recommended chapters are also provided in the Course Guideline for an instructor who wants to emphasize Private Information or Repeated Interaction.

If the class is focused on a particular major, such as economics or political science, an instructor can augment either the Core or Broad Social Science treatment with the concepts he or she wants to include and then focus on the pertinent set of applications. A list of applications, broken down by disci- pline or topic, is provided on the inside cover. The Biology treatment recog- nizes the unique elements of a course that focuses on the use of game theory to understand the animal kingdom.

Another design dimension to any course is the level of analysis. Although this book is written with all college students in mind, instructors can still vary the depth of treatment. The Simple treatment avoids any use of probability, calculus (which is only in Chapter 6 and the Appendix to Chapter 10), and the most challenging concepts (in particular, mixed strategies and games of incom- plete information). An instructor who anticipates having students prepared for a more demanding course has the option of offering the Advanced treatment, which uses calculus. Most instructors opting for the Advanced treatment will elect to cover various chapters, depending on their interests. For an upper-level economics course with calculus as a prerequisite, for example, an instructor can augment the Advanced treatment with Chapters 10 (including the Appendices), 11, and 13 and with selections from Chapters 14 and 15.

xx PREFACE

COURSE GUIDELINE

Broad Social Private Repeated

Chapter Core Science Information Interaction Biology Simple Advanced

1: Introduction to Strategic Reasoning ✔ ✔ ✔ ✔ ✔ ✔ ✔

2: Building a Model of a Strategic Situation ✔ ✔ ✔ ✔ ✔ ✔ ✔

3: Eliminating the Impossible: Solving a Game when Rationality Is Common Knowledge ✔ ✔ ✔ ✔ ✔ ✔ ✔

4: Stable Play: Nash Equilibria in Discrete Games with Two or Three Players ✔ ✔ ✔ ✔ ✔ ✔ ✔

5: Stable Play: Nash Equilibria in Discrete n-Player Games ✔ ✔

6: Stable Play: Nash Equilibria in Continuous Games ✔

7: Keep ’Em Guessing: Randomized Strategies ✔ ✔ ✔ ✔

8: Taking Turns: Sequential Games with Perfect Information ✔ ✔ ✔ ✔ ✔ ✔ ✔

9: Taking Turns in the Dark: Sequential Games with Imperfect Information ✔ ✔ ✔ ✔ ✔ ✔ ✔

10: I Know Something You Don’t Know: Games with Private Information ✔ ✔

11: What You Do Tells Me Who You Are: Signaling Games ✔ ✔

12: Lies and the Lying Liars That Tell Them: Cheap Talk Games ✔

13: Playing Forever: Repeated Interaction with Infinitely Lived Players ✔ ✔ ✔ ✔

14: Cooperation and Reputation: Applications of Repeated Interaction with Infinitely Lived Players ✔ ✔ 14.3 ✔

15: Interaction in Infinitely Lived Institutions ✔

16: Evolutionary Game Theory and Biology: Evolutionarily Stable Strategies ✔

17: Evolutionary Game Theory and Biology: Replicator Dynamics ✔ ✔

PREFACE xxi

Resources for Instructors To date, supplementary materials have been relatively minimal to the instruc- tion of game theory courses, a product of the niche nature of the course and the ever-present desire of instructors to personalize the teaching of the course to their own tastes. With that in mind, Worth has developed a variety of products that, when taken together, facilitate the creation of individualized resources for the instructor.

Instructor’s Resources CD-ROM This CD-ROM includes

■ All figures and images from the textbook (in JPEG and MS PPT for- mats)

■ Brief chapter outlines for aid in preparing class lectures (MS Word)

■ Notes to the Instructor providing additional examples and ways to engage students in the study of text material (Adobe PDF)

■ Solutions to all end-of-chapter problems (Adobe PDF)

Thus, instructors can build personalized classroom presentations or enhance online courses using the basic template of materials found on the Instructor’s Resource CD-ROM.

Companion Web Site for Instructors The companion site http://www.worthpublishers.com/harrington is another excellent resource for instructors, containing all the materials found on the IRCD. For each chapter in the textbook, the tools on the site include

■ All figures and images from the textbook (in JPEG and MS PPT for- mats)

■ Brief chapter outlines for aid in preparing class lectures (MS Word)

■ Notes to the Instructor providing additional examples and ways to en- gage students in the study of text material (Adobe PDF)

■ Solutions to all end-of-chapter problems (Adobe PDF)

As with the Instructor’s Resource CD-ROM, these materials can be used by in- structors to build personalized classroom presentations or enhance online courses.

Acknowledgments Because talented and enthusiastic students are surely the inspiration for any teacher, let me begin by acknowledging some of my favorite game theory stu- dents over the years: Darin Arita, Jonathan Cheponis, Manish Gala, Igor Klebanov, Philip London, and Sasha Zakharin. Coincidentally, Darin and Igor were roommates, and on the midterm exam Igor scored in the mid-90s while Darin nailed a perfect score. Coming by during office hours, Igor told me in his flawless English tinged with a Russian accent, “Darin really kicked ass on that exam.” I couldn’t agree more, but you also “kicked ass,” Igor, and so did the many other fine students I’ve had over the years.

When I was in graduate school in the early 1980s, game theory was in the early stages of a resurgence, but wasn’t yet part of the standard curriculum.

xxii PREFACE

http://www.worthpublishers.com/harrington
Professor Dan Graham was kind enough to run a readings course in game the- ory for myself and fellow classmate Barry Seldon. That extra effort on Dan’s part helped spur my interest in the subject—which soon became a passion— and for that I am grateful.

I would like to express my appreciation to a superb set of reviewers who made highly constructive and thoughtful comments that noticeably improved the book. In addition to a few who chose to remain anonymous, the reviewers were Shomu Bannerjee (Emory University), Klaus Becker (Texas Tech University), Giacomo Bonanno (University of California, Davis), Nicholas J. Feltovich (University of Houston), Philip Heap (James Madison University), Tom Jeitschko (Michigan State University), J. Anne van den Nouweland (University of Oregon and University of Melbourne), Kali Rath (University of Notre Dame), Matthew R. Roelofs (Western Washington University), Jesse Schwartz (Kennesaw State University), Piotr Swistak (University of Maryland), Theodore Turocy (Texas A&M University), and Young Ro Yoon (Indiana University, Bloomington).

My research assistants Rui Ota and Tsogbadral (Bagi) Galaabaatar did a splendid job in delivering what I needed when I needed it.

The people at Worth Publishers were simply terrific. I want to thank Charlie Van Wagner for convincing me to sign with Worth (and my colleague Larry Ball for suggesting it). My development editor, Carol Pritchard-Martinez, was a paragon of patience and a fount of constructive ideas. Sarah Dorger guided me through the publication process with expertise and warmth, often pushing me along without me knowing that I was being pushed along. Matt Driskill stepped in at a key juncture and exhibited considerable grit and determination to make the project succeed. Dana Kasowitz, Paul Shensa, and Steve Rigolosi helped at various stages to make the book authoritative and attractive. The copy editor, Brian Baker, was meticulous in improving the exposition and, amidst repairing my grammatical faux pas, genuinely seemed to enjoy the book! While I dedicated my doctoral thesis to my wife and best friend, Diana, my first textbook to my two wonderful parents, and this book to my two lovely and inspiring daughters, I can’t help but mention again—24 years after saying so in my thesis—that I couldn’t have done this without you. Thanks, Di.

PREFACE xxiii

This page intentionally left blank

Games, Strategies, and Decision Making

This page intentionally left blank

Man’s mind, once stretched by a new idea, never regains its original dimensions. —OLIVER WENDELL HOLMES

1.1 Who Wants to Be a Game Theorist? April 14, 2007: What’s this goo I’m floating in? It’s borrrriiiing being here by myself.

May 26, 2007: Finally, I get out of this place. Why is that woman smiling at me? I look like crud. And who’s that twisted paparazzo with a camera?

June 1, 2007: Oh, I get it. I cry and then they feed me. I wonder what else I can get them to do. Let’s see what happens when I spit up. Whoa, lots of at- tention. Cool!

September 24, 2019: Okay, this penalty kick can win it for us. Will the goalie go left or right? I think I’ll send it to the right.

January 20, 2022: I have got to have the latest MP5 player! sugardaddy37 has the high bid on eBay, but how high will the bidding go? Should I bid now or wait? If I could only get around eBay’s new antisniping software!

December 15, 2027: This game theory instructor thinks he’s so smart. I know exactly what he’s asking for with this question. Wait, is this a trick? Did he think I would think that? Maybe he’s not so dumb, though he sure looks it; what a geek.

May 7, 2035: If I want that promotion to sales manager, I’ve got to top the charts in next quarter’s sales. But to do that, I can’t just do what everyone else does and focus on the same old customers. Perhaps I should take a chance by aggressively going after some new large accounts.

August 6, 2056: If my son keeps getting lousy grades, he’ll never get into a good college. How do I motivate him? Threaten to ground him? Pay for grades? Bribe him with a car?

February 17, 2071: This transfer to the middle of nowhere is just a way to get me to quit. Maybe I can negotiate a sweet retirement deal with my boss. I wonder how badly she wants me out of here.

October 17, 2089: That guy in room 17 always gets to the commons room first and puts on that stupid talk show. Since when did he own this nursing home? Tomorrow, I’ll wake up early from my nap and beat him there!

FROM WOMB TO TOMB, life is a series of social encounters with parents, siblings, classmates, friends, teammates, teachers, children, neighbors, colleagues, bosses, baristas, and on and on. In this book, we explore a myriad collection of such

1

1

Introduction to Strategic Reasoning

2 CHAPTER 1: INTRODUCTION TO STRATEGIC REASONING

interactions and do so with two objectives. One objective is to understand the manner in which people behave—why they do what they do. If you’re a social scientist—such as a psychologist or an economist—this is your job, but many more people do it as part of everyday life. Homo sapiens is a naturally curious species, especially when it comes to each other; just ask the editors of People and National Enquirer. Our second objective is motivated not by curiosity, but by ne- cessity. You may be trying to resolve a conflict with a sibling, engaging in a sporting contest, competing in the marketplace, or conspiring on a reality TV show. It would be useful to have some guidance on what to do when interacting with other people.

In the ensuing chapters, we’ll explore many different kinds of human en- counters, all of which illustrate a situation of strategic interdependence. What is strategic interdependence? First, consider a situation in which what one person does affects the well-being of others. For example, if you score the win- ning goal in a soccer game, not only will you feel great, but so will your team- mates, while the members of the other team will feel lousy. This situation il- lustrates an interdependence across people, but strategic interdependence is something more. Strategic interdependence is present in a social situation when what is best for someone depends on what someone else does. For ex- ample, whether you kick the ball to the right or left depends on whether you think the goalkeeper will go to the right or left.

The presence of strategic interdependence can create a formidable chal- lenge to figuring out what to do. Suppose Greg and Marcia arrive at a museum together, but are later separated. Because Greg’s cell phone battery is dead, each must independently decide where to meet. Since Greg wants to go where he thinks Marcia will go, he needs to think like Marcia. “Where would I go if I were Marcia?” Greg asks himself. But as soon as he begins thinking that way, he realizes that Marcia will go where she thinks Greg will go, which means that Marcia is asking herself, “Where would I go if I were Greg?” So Greg doesn’t need to think about what Marcia will do; he needs to think about what Marcia thinks Greg will do. And it doesn’t stop there. As portrayed in FIGURE 1.1, each person is thinking about what the other person is thinking about what the other person is thinking about what the other person is thinking. . . . This prob- lem is nasty enough to warrant its own name: infinite regress.

Infinite regress is a daunting property that is exclusively the domain of the social sciences; it does not arise in physics or chemistry or any of the other physical sciences. In their pioneering book Theory of Games and Economic Behavior, John von Neumann and Oskar Morgenstern recognized the singu- larity of strategic situations and that new tools would be needed to conquer them:

The importance of the social phenomena, the wealth and multiplicity of their manifestations, and the complexity of their structure, are at least equal to those in physics. It is therefore to be expected—or feared—that mathemati- cal discoveries of a stature comparable to that of calculus will be needed in order to produce decisive success in this field.1

Game theory provides a method to break the chain of infinite regress so that we can stop banging our heads against the wall and say something useful (assuming that we haven’t banged our heads for so long that we’ve lost any ca- pacity for intelligent thought). Showing how game theory can be used to ex- plore and understand social phenomena is the task this book takes on.

1.2 A Sampling of Strategic Situations 3

1.2 A Sampling of Strategic Situations SINCE ITS DISCOVERY, game theory has repeatedly shown its value by shedding insight on situations in economics, business, politics, and international rela- tions. Many of those success stories will be described in this book. Equally ex- citing has been the expansion of the domain of game theory to nontraditional areas such as history, literature, sports, crime, medicine, theology, biology, and simply everyday life (as exemplified by the chapter’s opening monologue). To appreciate the broad applicability of game theory, the book draws examples from an expansive universe of strategic situations. Here is a sampling to give you a taste of what is in store for you:

Price-matching guarantees Surf on over to the website of Best Buy, and you’ll see the following statement: “If you’re about to buy at a Best Buy store and discover a lower price than ours, let us know and we’ll match that price on the spot.” A trip to Circuit City’s website reveals a similar policy: “If you’ve seen a lower advertised price from another local

FIGURE 1.1 Infinite Regress in Action

4 CHAPTER 1: INTRODUCTION TO STRATEGIC REASONING

store with the same item in stock, we want to know about it. Bring it to our attention, and we’ll gladly beat their price by 10% of the difference.” Although these policies would seem to represent fierce competition, such price-matching guarantees can actually raise prices! How can that be?

Ford and the $5-a-day wage In 1914, Henry Ford offered the unheard-of wage of $5 a day to workers in his automobile factories, more than double the going wage. Although we might conclude that Henry Ford was just being generous with his workers, his strategy may actually have increased the prof- its of the Ford Motor Company. How can higher labor costs increase profits?

Nuclear standoff Brinkmanship is said to be the ability to get to the verge of war without actually getting into a war. This skill was pertinent to a recent episode in which the United States sought to persuade North Korea to discontinue its nuclear weapons program. Even if Kim Jong-Il has no desire to go to war, could it be best for him to take actions which suggest that he is willing to use nuclear weapons on South Korea? And if that is the case, should President Bush take an aggressive stance and thereby call a sane Kim Jong-Il’s bluff, but at the risk of inducing a crazy Kim Jong-Il to fire off nuclear weapons?

Jury room After the completion of a trial, the 12 jurors retire to the jury room. On the basis of their initial assessment, only 2 of them believe that the defendant is guilty. They start their deliberations by taking a vote. In turn, each and every juror announces a vote of guilty! How can this hap- pen? And is there an alternative voting procedure that would have avoided such an unrepresentative outcome?

Galileo and the Inquisition In 1633, the great astronomer and scientist Galileo Galilei was under consideration for interrogation by the Inquisition. The Catholic Church contended that Galileo violated an order not to teach that the earth revolves around the sun. Why did Pope Urban I refer Galileo’s case to the Inquisitors? Should Galileo confess?

Waiting at an airport gate Some airlines have an open seating policy, which means that those first in line get a better selection of seats. If the passengers are comfortably seated at the gate, when does a line start forming and when should you join it?

Helping a stranger Studies by psychologists show that a person is less likely to offer assistance to someone in need when there are several other people nearby who could help. Some studies even find that the more peo- ple there are who could help, the less likely is any help to be offered! How is it that when there are more people to help out, the person in need is more likely to be neglected?

Trench warfare in World War I During World War I, the Allied and German forces would engage in sustained periods of combat, regularly launching offensives from their dirt fortifications. In the midst of this bloodletting, soldiers in opposing trenches would occasionally achieve a truce of sorts. They would shoot at predictable intervals so that the other side could take cover, not shoot during meals, and not fire artillery at the enemy’s supply lines. How was this truce achieved and sustained?

Doping in sports Whether it is the Olympics, Major League Baseball, or the Tour de France, the use of illegal performance-enhancing drugs such

1.3 Whetting Your Appetite: The Game of Concentration 5

as steroids is a serious and challenging problem. Why is doping so ubiqui- tous? Is doping inevitable, or can it be stopped?

Extinction of the wooly mammoth A mass extinction around the end of the Pleistocene era wiped out more than half of the large mammal species in the Americas, including the wooly mammoth. This event coin- cided with the arrival of humans. Must it be that humans always have such an impact on nature? And how does the answer to that question pro- vide clues to solving the problem of global climate change?

1.3 Whetting Your Appetite: The Game of Concentration THE VALUE OF GAME THEORY in exploring strategic situations is its delivery of a better understanding of human behavior. When a question is posed, the tools of game theory are wielded to address it. If we apply these tools appropriately, we’ll learn something new and insightful. It’ll take time to develop the tools so that you can see how that insight is derived—and, more importantly, so that you can derive it yourself—but you are certain to catch on before this course is over. Here, I simply offer a glimpse of the kind of insight game theory has to offer.

Game theory can uncover subtly clever forms of strategic behavior. To see what I mean, let’s consider the common card game of Concentration that many of you undoubtedly have played. Through your own experience, you may already have stumbled across the strategic insight we’ll soon describe. The beauty of game theory is that it can provide insight into a situation before you’ve ever faced it.

The rules of Concentration are simple. All 52 cards are laid face down on a table. Each player takes turns selecting 2 cards. If they match (e.g., if both are Kings), then the player keeps the pair and continues with her turn. If they do not match, then the cards are returned face down and the turn goes to the next player. The game is played until all the cards are off the table— 26 matched pairs have been collected—and the player with the most pairs wins.

What does it take to win at Concentration? A bit of luck helps. Early in the game, players have little choice but to choose randomly. Of course, the first player to move is totally in the dark and, in fact, has less than a 6% chance of making a match. But once the game gets rolling, luck is trumped by a good memory. As cards fail to be matched and are turned back over, remembering where those cards are will lead to future matches. So memory and luck are two valuable traits to possess (to the extent that one can possess luck). And then there is, of course, strategy. Strategy, I say? Where is the role for strategy in Concentration?

To focus on the strategic dimension to Concentration, we’ll neutralize the role of memory by assuming that players have perfect memory.2 For those of you who, like me, lack anything approaching such an enviable trait, consider instead the following modification to the game: When two cards are turned up and don’t match, leave them on the table turned up. So as not to confuse our- selves, we’ll now speak of a player “choosing” a card, and that card may al- ready be turned up (so that all know what card it is), or it may be turned down (in which case the card is yet to be revealed).

6 CHAPTER 1: INTRODUCTION TO STRATEGIC REASONING

Suppose two players—Angela and Zack—are playing Concentration and face the following array of cards on the board:

Board 1

There are six remaining cards, of which one is known to be a queen. Of the five unknown cards, one is another queen; assume that the others are two kings and two 10’s.

It’s Angela’s turn, and suppose she chooses one of the unknown cards, which proves to be a king. The board now looks as follows, with the selected card noted.

Board 2

What many people are inclined to do at this point is choose one of the four unknown cards with the hope of getting another king, rather than select the card known to be a queen. But let’s not be so hasty and instead explore the pos- sible ramifications of that move. If Angela flips over one of the other four un- known cards, there is a one-in-four chance that it is the other king, because, of those four cards, one is a king, one is a queen, and two are 10’s. Similarly, there is a one-in-four chance that the card is a queen and a one-in-two chance that it is a 10.

What happens if it is a king? Then Angela gets a match and gets to choose again. If it is instead a queen, then Angela doesn’t get a match, in which case it is Zack’s turn and he faces this board:

Board 3

1.3 Whetting Your Appetite: The Game of Concentration 7

Notice that Zack is sure to acquire one pair by choosing the two Queens; he could get more if he’s lucky. Finally, suppose the second card Angela selects turns out to be a 10. Then Zack inherits this board:

Now Zack gets all three remaining pairs! If he chooses any of the three re- maining unknown cards, he’ll know which other card to select to make a match. For example, if he chooses the first card and it is a king, then he just needs to choose the fourth card to have a pair of kings. Continuing in this manner, he’ll obtain all three pairs.

TABLE 1.1 summarizes the possibilities when Angela has Board 2—having just gotten a king—and chooses one of the four remaining unknown cards as her second card. She has a 25% chance of getting a pair (by getting a king), a 25% chance of Zack getting at least one pair (by Angela’s getting a queen), and a 50% chance of Zack getting all three remaining pairs (by Angela’s getting a 10).

Board 4

TABLE 1.1 OUTCOMES WHEN ANGELA CHOOSES AN UNKNOWN CARD AFTER GETTING A KING

Identity of Second Number of Pairs for Number of Pairs for Card Chosen Chances Angela on This Round Zack on Next Round

King 25% 1 (maybe more) 0 (maybe more)

Queen 25% 0 (for sure) 1 (maybe more)

10 50% 0 (for sure) 3 (for sure)

Having randomly chosen her first card and found it to be a king, what, then, should Angela select as her second card? Game theory has proven that the best move is not for her to choose one of the four remaining unknown cards, but instead to choose the card that is known to be a queen! It will take us too far afield for me to prove to you why that is the best move, but it is easy to explain how it could be the best move. Although selecting the queen means that Angela doesn’t get a pair (because she’ll have a king and a queen), it also means that she doesn’t deliver as attractive a board to Zack. Instead, Zack would receive the following board:

Board 5

8 CHAPTER 1: INTRODUCTION TO STRATEGIC REASONING

Notice that Zack is no longer assured of getting a pair. If, instead, Angela had chosen one of the four unknown cards, there is a 25% chance that she’d have gotten a pair, but a 75% chance that Zack would have gotten at least one pair.

What this analysis highlights is that choosing an unknown card has bene- fits and costs. The benefit is that it may allow a player to make a match— something that is, obviously, well known. The cost is that, when a player chooses a card that does not make a match (so that the revealed card remains on the board), valuable information is delivered to the opponent. Contrary to accepted wisdom, under certain circumstances it is optimal to choose a card that will knowingly not produce a match in order to strategically restrict the information your opponent will have and thereby reduce his chances of col- lecting pairs in the next round.

Generally, the value of game theory is in delivering insights of that sort. Even when we analyze a decidedly unrealistic model—as we just did with players who have perfect memory—a general lesson can be derived. In the game of Concentration, the insight is that you should think not only about trying to make a match, but also about the information that your play might reveal to the other player—a useful tip even if players’ memories are imperfect.

1.4 Psychological Profile of a Player I think that God in creating Man somewhat overestimated his ability. —OSCAR WILDE

A STRATEGIC SITUATION IS described by an environment and the people who inter- act in that environment. Before going any further, it is worth discussing what defines a person for the purposes of our analysis. If you are asked to describe someone you know, many details would come to your mind, including the per- son’s personality, intelligence, knowledge, hair color, gender, ethnicity, family history, political affiliation, health, hygiene, musical tastes, and so on. In game theory, however, we can ignore almost all of those details because, in most sit- uations, understanding or predicting behavior requires knowing just two characteristics: preferences and beliefs.

1.4.1 Preferences With her current phone contract expired, Grace is evaluating two cell phone providers: Verizon and AT&T. The companies differ in terms of their pricing plans and the phones that they offer. (Especially enticing is AT&T’s support for the iPhone.) A key assumption in this book is that a person can always de- cide; that is, when faced with two alternatives, someone is able to say which she likes more or whether she finds them equally appealing. In the context of cell phone providers, this assumption just means that Grace either prefers Verizon to AT&T, prefers AT&T to Verizon, or is indifferent between the two plans. Such a person is said to have complete preferences. (Thus, we are ruling out people with particular forms of brain damage that cause abulia, which is an inability to decide; they will be covered in Volume II of this book—yeah, right.)

A second assumption is that a person’s preferences have a certain type of consistency. For example, if Grace prefers AT&T to Verizon and Verizon to Sprint, then it follows that she prefers AT&T to Sprint. Let’s suppose, however,

1.4 Psychological Profile of a Player 9

that were not the case and that she instead prefers Sprint to AT&T; her prefer- ences would then be as follows:

AT&T is better than Verizon.

Verizon is better than Sprint.

Sprint is better than AT&T.

Let’s see what trouble emerges for a person with such preferences. If Grace started by examining Verizon and comparing it with AT&T, she

would decide that AT&T is better. Putting the AT&T plan alongside the one from Sprint, she thinks, “Sprint has a better deal.” But just as she’s about to buy the Sprint plan, Grace decides to compare Sprint with Verizon, and lo and behold, she decides that Verizon is better. So she goes back and compares Verizon and AT&T and decides, yet again, that AT&T is better. And if she were to compare AT&T and Sprint, she’d go for Sprint again. Her process of com- parison would keep cycling, and Grace would never decide! To rule out such troublesome cases, it is assumed that preferences are transitive. Preferences are transitive if, whenever option A is preferred to B and B is preferred to C, it follows that A is preferred to C.

The problem with intransitive preferences goes well beyond the possibility of vacillating ad nauseam: you could end up broke! Suppose Jack has intran- sitive preferences in that he prefers A to B, B to C, and C to A. Suppose also that you possess item A and Jack has items B and C. Consider the series of transactions listed in TABLE 1.2: You propose to Jack that you give him A in ex- change for B and, say, a dollar. Now, assume that Jack prefers A enough to B that he would give up B and a dollar in order to obtain A. So now you have B and a dollar, while Jack has A and C (and is a dollar poorer). You then propose to give him B in exchange for C and a dollar. Because Jack prefers B to C (say,

TABLE 1.2 PUMPING JACK FOR MONEY

What You Have What Jack Has Transaction

A and $0 B, C, and $99

A for B and $1

B and $1 A, C, and $98

B for C and $1

C and $2 A, B, and $97

C for A and $1

A and $3 B, C, and $96

A for B and $1

B and $4 A, C, and $95

B for C and $1

C and $5 A, B, and $94

� � �

A and $99 B, C, and $0

10 CHAPTER 1: INTRODUCTION TO STRATEGIC REASONING

by more than a dollar), Jack will make the trade. Now you possess C and two dollars. The next step is to offer C in exchange for A and a dollar. Since Jack prefers A to C (say, by at least a dollar), he’ll make the trade. Now you have A and three dollars, whereas if you recall, you started with A and no money. Trading with Jack is a money pump! It gets even better: you can continue to execute this sequence of trades while accumulating three dollars in each round. Eventually, you’ll have taken all of Jack’s money. Such is the sad life of someone whose preferences are not transitive, so take this cautionary tale to heart and always have your preferences be transitive!

If a person’s preferences are complete and transitive, then there is a way in which to assign numbers to all of the feasible items—where the associated number is referred to as an item’s utility—so that a person’s preferences can be represented as choosing the item that yields the highest utility. To be more concrete, suppose there are four cell phone providers available to Grace: AT&T, Verizon, Sprint, and T-Mobile. Her preferences are as follows: