Games strategies and decision making pdf

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.