Games strategies and decision making

Strategy, Decision Making ( Harrington) Problem Chapter 11 Exercise 8

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:

AT&T is better than Verizon. Verizon is better than Sprint.

Sprint and T-Mobile are equally appealing.

This set of preferences implies the following ordering of plans: AT&T is best, Verizon is second best, and Sprint and T-Mobile are tied for third best. The next step is to as- sign a utility to each of these choices so that choosing the plan with the highest utility is equivalent to choosing the most preferred plan. Such an assignment of utilities is shown in TABLE 1.3.

We can now describe Grace’s behavior by saying that she makes the choice which yields the highest utility. If all four plans are available in her area, we know by her pref-

erences that she’ll choose AT&T. If we say that she chooses the plan with the highest utility, it means that she chooses AT&T, because the utility of choos- ing AT&T is 10, which is higher than 6 from Verizon and 2 from either Sprint or T-Mobile. Now suppose that AT&T is unavailable in her area, so she can choose only between Verizon, Sprint, and T-Mobile. Her preferences rank Verizon higher than the other two, so that is what she will buy. Choosing Verizon is also what maximizes her utility—it delivers utility of 6—when she can choose only between Verizon, Sprint, and T-Mobile.

To ensure that choosing the option with the highest utility is equivalent to choosing the most preferred option, numbers need to be assigned so that the utility of option A is greater than the utility of option B if and only if A is pre- ferred to B and the utility of A is equal to that of B if and only if the individ- ual choosing is indifferent between A and B. Note that there is no unique way to do that. Rather than assigning 10, 6, 2, and 2 to AT&T, Verizon, Sprint, and T-Mobile, respectively, it would have worked just as well to have used 14, 12, 11, and 11 or 4, 3, 0, and 0. As long as the utility is higher for more preferred items, we’ll be fine.

There is nothing deep about the concept of utility. The idea is that people are endowed with preferences which describe how they rank different alter- natives. If preferences are complete and transitive, then there is a way in which to assign a number to each alternative that allows a person’s behavior to be described as making the choice with the highest utility. A list of options

TABLE 1.3 GRACE’S UTILITY FUNCTION

Cell Phone Provider Utility

AT&T 10

Verizon 6

Sprint 2

T-Mobile 2

1.4 Psychological Profile of a Player 11

and their associated utilities—such as Table 1.3—is known as a utility func- tion. A person’s utility function captures all of the relevant information about the person’s preferences.

Writing down a person’s preferences begs the question of where they come from. Why does someone prefer rock and roll to opera? cats to dogs? stripes to solids? pizza to General Tso’s chicken? Preferences could be determined by genes, culture, chemicals, personal experience, and who knows what else. Where preferences come from will not concern us. We’ll be content to take preferences as given and explore what they imply about behavior.

1.4.2 Beliefs In many situations, the utility received by a person depends not just on the choices the person makes, but also on the choices of others. For example, many cell phone providers have designed their plans to create an interdependence be- tween the choices that people make. For most plans, the price charged per minute is lower if you are calling someone on the same network (i.e., someone who has chosen the same provider) than if you are calling someone on another network. What this means is that the best provider for someone may well de- pend on the providers used by the people whom they call.

With this in mind, consider Grace’s deciding on a cell phone plan, knowing that she spends most of her time calling her best friend Lisa. Although Grace really likes AT&T (because then she can have an iPhone), it is most critical to her that she choose the same network as Lisa. A utility function consistent with these preferences for Grace is shown in TABLE 1.4. Note that Grace’s most preferred provider is always the provider that Lisa chooses. If Lisa chooses Sprint, then Sprint yields the highest utility for Grace. (Compare 6 from Sprint, 5 from AT&T, and 3 from Verizon.) If Lisa chooses Verizon, then Verizon maximizes Grace’s utility. Given that Grace really likes AT&T, her highest utility comes when both she and Lisa choose AT&T.

To make the best choice, Grace will need to form beliefs as to which plan Lisa will choose. This condition leads us to the second key personal attribute

TABLE 1.4 GRACE’S UTILITY FUNCTION WHEN IT DEPENDS ON LISA’S PROVIDER

Grace’s Provider Lisa’s Provider Grace’s Utility

AT&T AT&T 10

AT&T Verizon 5

AT&T Sprint 5

Verizon AT&T 3

Verizon Verizon 8

Verizon Sprint 3

Sprint AT&T 2

Sprint Verizon 2

Sprint Sprint 6

12 CHAPTER 1: INTRODUCTION TO STRATEGIC REASONING

that is relevant to game theory: a person’s capacity to form beliefs as to what others will do. While we’ll assume that people are endowed with preferences, such as those described in Table 1.4, they are not endowed with beliefs. Indeed, a major function of game theory is to derive reasonable beliefs re- garding what other players will do.

There are two processes from which these beliefs might emerge, one smart and one dumb. The dumb process is simply experience, which is referred to as experiential learning. By interacting again and again, a person comes to expect—rightly or wrongly—that another person will do what he’s done in the past. This process has great universality, as it can be practiced by small kids and many species in the animal kingdom.

The smart process for forming beliefs is called simulated introspection. Introspection is the examination of one’s own thoughts and feelings, while in simulated introspection a person is simulating the introspective process of someone else in order to figure out what that individual will do. Simulated in- trospection is the default method of belief derivation in this book, although some of what we’ll say can be derived through experiential learning. Because simulated introspection is subtle and complex, let’s discuss what demands it puts on a person.

To have the capacity to simulate the reasoning of others, a person must have self-awareness, which means being aware of your own existence. It is not enough to think; a person must be capable of thinking about thinking. Thinking is, then not just a process, like digestion, but also a mental state. Of course, thinking about how you think doesn’t necessarily get you closer to fig- uring out what someone else is thinking; we also need what psychologists call a theory-of-mind mechanism (ToMM). Possession of a ToMM means that you attribute thinking to others and attribute a ToMM to others, which means that you attribute to them the possibility of thinking about you thinking, just as you can think about them thinking. A ToMM is essential to strategizing and is what produces the endlessly slippery slope of infinite regress.

A ToMM is a fascinating capacity and is the basis for all that underlies this book. It has been argued that a ToMM is so useful for social animals that it is natural to think of it as the product of evolution. Surviving and thriving in a community would surely have been enhanced by being able to predict what others would do.3 Given the advantage that a ToMM bestows, it is natural to ask whether other primates possess it. Although indirect tests have been con- ducted on apes and chimpanzees, the evidence is mixed. Interestingly, some scientists believe that the absence of a ToMM is a feature of autism, in which case it is possible to be an intelligent human, yet lack a ToMM.

1.4.3 How Do Players Differ? Thus far, we’ve discussed how people are similar: they have well-defined prefer- ences, self-awareness, and a theory-of-mind mechanism. But how do they differ? Three forms of individual heterogeneity are especially relevant to game theory. First, although each person is assumed to have complete and transitive preferences, those preferences can vary across people. For instance, Grace may prefer AT&T, while Lisa prefers Verizon. Tony may like the Red Sox and detest the Yankees, while Johnny is just the opposite. Second, people can have differ- ent options and opportunities. For example, a wealthy bidder at an auction has a different set of options than another bidder with lower net worth. Third, people

1.5 Playing the Gender Pronoun Game 13

can have different information. Thus, the bidder with less wealth may have a better evaluation of the item being auctioned off than the wealthier bidder.

One last trait that deserves mention is skill, which is required both in figuring out what to do in a strategic encounter and in then executing a plan. Skill em- bodies many elements, including originality, cleverness, composure, and, as described by Winston Churchill, that “element of legerdemain, an original and sinister touch, which leaves the enemy puzzled as well as beaten.”4 How skillful are players presumed to be, and how much are they allowed to vary in their skill?

FIGURE 1.2 depicts a range of intellects drawn from fiction. Players aren’t presumed to be brilliant like James Bond or Albert Einstein, nor are they going to be in the “dumb and dumber” category like Curly or Mr. Bean. We’re not out to explain how the Three Stooges would behave when faced with a nu- clear standoff. We will presume that players have at least a modicum of good sense and guile and, overall, that they are intelligent.

Are people presumed to be logical like Mr. Spock from Star Trek, or can they draw upon their emotions in decision making? While our analysis will be an exercise in logic, that does not preclude the possibility that people use emo- tions or “gut feelings” to arrive at a decision. In many cases, we will not be re- producing how people actually make decisions; rather, we will be describing what the end result of that process may be. A person may reach a decision through cold logic or on the basis of emotions rooted in past experiences.5

The more intriguing issue is whether we allow for variation in the skill of our players. Can we explore SpongeBob battling wits with Star Wars’ Senator Palpatine? Or have Mr. Bean and Voldemort exercise their “gray matter” in conflict? Although it would be exciting to explore such possibilities, they will not be considered here. A key assumption throughout this book is that people have comparable levels of skill. The strategic moves considered will take place on a level playing field. Although a player may have an advantage because she has more options or better information, no player will be able to “outsmart” an- other. (In principle, game theory can handle such possibilities, but that line of inquiry is largely undeveloped.)

1.5 Playing the Gender Pronoun Game BEFORE GOING ANY FURTHER in our quest to learn the logic of game theory, there is a sociopolitical–legal issue that my publisher, priest, and barista have urged me to raise with you: the use of gender pronouns. Any textbook that

FIGURE 1.2 A Range of Intellect

Dumb Smart

TH E

KO B A

L C O

LL EC

TI O

N

© U

N IV

ER SA

L/ C O

U RT

ES Y

EV ER

ET T

C O

LL EC

TI O

N

© S

O N

Y PI

C TU

R ES

/C O

U R TE

SY EV

ER ET

T C O

LL EC

TI O

N

© C

O R B IS

14 CHAPTER 1: INTRODUCTION TO STRATEGIC REASONING

discusses people in the abstract—such as a book on game theory—must ex- plain how it intends to use gender pronouns and provide the rationale for that usage. While this matter is typically discussed in a book’s preface, peo- ple don’t tend to read the preface (apparently, “preface” means “ignore” in lots of languages), and every reader needs to know where I stand on this con- tentious issue.

To the chagrin of “stupid white men”—as filmmaker Michael Moore de- scribes them—the people who live in this book are not all males. If they were, where would the next generation of players come from for my second edition? Yes, women do live in the abstract world of game theory and will live along- side men. But allowing cohabitation between the covers of this book still leaves a decision of how to allocate men and women across our many exam- ples. I remember a scholarly piece on crime in which the male pronoun was used to refer to criminals (because most criminals are men) while judges, ju- rors, attorneys, witnesses, and victims were female. (To be accurate, most criminals who are caught are men; perhaps women are better about getting away with it.) Such an approach is disturbing. Might not an impressionable boy be led to believe that he should turn to a life of crime because that is what males do? And should we really convey the impression to a girl that crime is too risky for the female half of the species? Contrary to that approach, this book will allow both men and women to be deviants, sociopaths, and your run-of-the-mill perverts.

An alternative strategy is to deploy tactics utilized in the Gender Pronoun Game. This is the conversational game by which a person seeks to hide the gender of his partner. Instead of using “he” or “she” and “him” or “her”, one either avoids the use of pronouns or uses plural pronouns such as “they” and “them”. In the heterosexual world, a gay person might strive to avoid reveal- ing that her partner is of the same gender, and analogously, someone in the gay community (who is perhaps bisexual) might hide a heterosexual relation- ship. But these gender-neutral plural pronouns can become awkward (and drive my editor crazy), which leads me to another strategy: invent some gender-neutral pronouns. There is no shortage of worthy attempts, including “shis”, “shim”, “shey”, “shem”, “sheir”, “hisorher”, “herorhis”, and—my per- sonal favorite—“h’orsh’it” (a colorful blend of “he”, “she”, and “it”).

After long hours of monklike contemplation with my subconscious in sync with the Fox Network, I have decided to deal with this issue by mimicking real life. Just as our species is made up of both men and women, so will the play- ers occupying the pages of this book. If there is a two-player game, then one player will be male and the other female. More generally, I’ll just mix them up—a male here, a female there, a hermaphrodite when I’m getting bored. Admittedly, I have not counted their respective numbers to ensure an even gender balance. You the reader are welcome to do so, and once having been informed of your findings, I would be glad to replace an X chromosome with a Y or a Y with an X as is needed. In the meantime, I will do my best to be gender neutral and avoid stepping in h’orsh’it.

REFERENCES 1. John von Neumann and Oskar Morgenstern, Theory of Games and

Economic Behavior (Princeton: Princeton University Press, 1944), p. 6.

References 15

2. This discussion is based on Uri Zwick and Michael S. Patterson, The Memory Game (Coventry, U.K.: Mathematics Institute, University of Warwick, March 1991). It was reported in Ian Stewart, “Mathematical Recreations”, Scientific American, October 1991, pp. 126–28.

3. Nicholas Humphrey, The Inner Eye (Oxford, U.K.: Oxford University Press, 2003).

4. Winston S. Churchill, The World Crisis (New York: Charles Scribner’s Sons, 1923) vol II, p. 5.

5. On the role of emotions in social decision making, the interested reader is referred to Antonio R. Damasio, Descartes’ Error: Emotion, Reason, and the Human Brain (New York: Avon Books, 1994).

This page intentionally left blank

If the human mind was simple enough to understand, we’d be too simple to understand it. —EMERSON PUGH

2.1 Introduction THEY SPEAK OF “DELIVERABLES” in the corporate world as the end product that is—well, delivered to a customer. So for those who are trying to understand social phenomena—such as economists, political scientists, and nosy neigh- bors—or those trying to determine how to behave—such as policymakers, business owners, and teenagers—game theory has two deliverables. First, it provides a framework for taking a complex social situation and boiling it down to a model that is manageable. Second, it provides methods for extract- ing insights from that model regarding how people do behave or how they should behave. This chapter focuses on using game theory to model a strate- gic situation; the next chapter begins our journey solving such models.

Human behavior typically occurs in an environment that is highly complex, and this complexity poses a challenge in modeling social phenomena. Deciding on what to put in a model is like trying to pack for college: there’s just no way to shove everything you want into that suitcase. In that light, it is useful to dis- tinguish between literal and metaphorical models. A literal model is a model that is descriptively accurate of the real-world setting it is intended to repre- sent. Other than for board games and a few other settings, a literal model of a social situation would be a bloody mess. In contrast, a metaphorical model is a vast simplification—a simplified analogy—of the real-world situation; it is not meant to be descriptively accurate. With a metaphorical model, we try to simulate the real world in essential ways, not replicate it. The “essential” ways are those factors thought to be critical to the problem of interest. Factors that are presumed to be secondary are willfully ignored. Most of the models in this book and most of the models constructed to understand social phenomena are metaphorical. Done right, a metaphorical model can yield insights into human behavior that are applicable to much richer and more realistic situations.

Whether literal or metaphorical, game theory offers a scaffolding around which a model can be constructed, and in this chapter we review the two pri- mary types of scaffolding. The extensive form is a description of the sequence of choices faced by those involved in a strategic situation, along with what they know when they choose. In Section 2.2, we consider extensive form games of perfect information, in which a person always knows what has thus far transpired in the game. Situations with imperfect information are de- scribed in Section 2.3, and these models allow a person to lack knowledge about what other people have chosen so far. The central concept of a strategy

2Building a Model of a Strategic Situation

17

is introduced in Section 2.3, and this concept provides the foundation for de- scribing the strategic form of a game in Section 2.4—the second type of scaf- folding. Though more abstract than the extensive form, the strategic form is more concise and easier to work with. Common knowledge is a concept perti- nent to both methods of modeling a strategic situation and is covered in Section 2.5. Common knowledge deals with what a person knows about what others know.

Before we move forward, let me remind you that this chapter is about building a game. Solving a game will begin with the next chapter, so be pre- pared for some delayed gratification.

2.2 Extensive Form Games: Perfect Information IN SPITE OF ITS NAME, game theory can deal with some fairly dire subjects, one of which is the criminal activity of kidnapping for ransom. This is a sufficiently serious and persistent problem in some countries—such as Colombia, Mexico, and Russia—that companies have taken out insurance against their executives being held for ransom. Building a model of kidnapping can involve factoring in a great many considerations. The focus of our task, however, is not so much on gaining insight into kidnapping, but on learning how to construct a game- theoretic model.

Because the objective of game theory is to derive implications about be- havior, a model should focus on those individuals who have decisions to make. Our attention will accordingly be on the kidnapper, whom we’ll call Guy, and the victim’s wife, Vivica, who has been contacted to pay ransom. Although the victim (whom we’ll name Orlando) is surely affected by what transpires, we are presuming that the victim has no options. In describing the situation, our model should address the following questions: When do Guy and Vivica get to act? What choices are available when they get to act? What do they know

when they get to act? More information will be needed to derive predictions about behav- ior, but the information obtained by answer- ing these questions is sufficient for starters.

The model is represented by what is known as a decision tree, such as that shown in FIGURE 2.1. A decision tree is read from top to bottom. (It can also be depicted to be read from left to right.) Each of the dots is called a decision node, which represents a point in the game at which someone has a decision to make. Coming out of a decision node is a series of branches, where each branch represents a different action avail- able to the decision maker. Choosing a branch is equivalent to choosing an action.

At the top of the decision tree, Guy is to make the initial decision, and his choices are kidnap (Orlando) and do not kidnap.* If he

18 CHAPTER 2: BUILDING A MODEL OF A STRATEGIC SITUATION

FIGURE 2.1 Extensive Form of the Kidnapping Game

Guy

Guy 3

Vivica 5 Pay ransom

Vivica

4

1

5

3

2

2

1

4

Do not kidnap

Do not pay ransom

Kidnap

Guy

Kill KillRelease Release

Guy

*The name of an action or strategy will typically be italicized in this book.

2.2 Extensive Form Games: Perfect Information 19

chooses the latter, then the tree comes to an end, which represents “game over.” If, instead, he chooses to kidnap Orlando, then Vivica is informed of the kidnapping and decides whether to pay the ransom. In response to Vivica’s de- cision, Guy decides whether to release Orlando or kill him. The assumption is that Guy observes whether ransom is paid prior to making this choice. (How to handle a simultaneous exchange will be discussed later in the chapter.)

There is a total of five outcomes to this game, each of which corresponds to a path through the decision tree or, equivalently, a sequence of actions. These outcomes are listed in TABLE 2.1. One outcome is for there not to be a kidnap- ping. If there is a kidnapping, there are four possible outcomes, depending on whether ransom is paid and whether Orlando is killed or released.

TABLE 2.1 KIDNAPPING GAME AND PAYOFFS

Outcome Guy (Violent) Guy Vivica

No kidnapping 3 3 5

Kidnapping, ransom is paid, Orlando is killed 4 5 1

Kidnapping, ransom is paid, Orlando is released 5 4 3

Kidnapping, ransom is not paid, Orlando is killed 2 2 2

Kidnapping, ransom is not paid, Orlando is released 1 1 4

The objective of our model is to make some predictions about how Guy and Vivica will behave. Although solving a game won’t be tackled until the next chapter, in fact we don’t have enough information to solve it even if we knew how. To describe how someone will behave, it’s not enough to know what they can do (e.g., kill or release) and what they know (e.g., whether ran- som has been paid); we also need to know what these people care about. What floats their boat? What rings their bell? What tickles their fancy? You get the idea.

A description of what a player cares about takes the form of a ranking of the five outcomes of the game. Suppose Guy is someone who really just wants the money and kills only out of revenge for the ransom not being paid. Then Guy’s best outcome is to perform the kidnapping, Vivica pays the ransom, and he releases Orlando. Because we assume that he is willing to kill in exchange for money, his second-best outcome is to perform the kidnapping, have the ransom paid, and kill Orlando. The third-best outcome is not to kidnap Orlando, since Guy prefers not to run the risk of kidnapping when ransom is not to be paid. Of the two remaining outcomes, suppose that if he kidnaps Orlando and ransom is not paid, then he prefers to kill Orlando (presumably out of spite for not receiving the ransom). The least preferred outcome is then that there is a kidnapping, ransom is not paid, and Orlando is released.

To concisely include Guy’s preferences in our description of the game, we’ll assign a number to each outcome, with a higher number indicating a more preferred outcome for a player. This ranking is done in Table 2.1 under the col- umn labeled “Guy.” These numbers are referred to as payoffs and are in- tended to measure the well-being (or utility, or welfare, or happiness index) of a player. For example, the highest payoff, 5, is assigned to the best outcome: the kidnapping takes place, ransom is paid, and Orlando is released. The worst

20 CHAPTER 2: BUILDING A MODEL OF A STRATEGIC SITUATION

outcome—the kidnapping takes place, ransom is not paid, and Orlando is re- leased—receives the lowest payoff, 1.

Suppose, contrary to what was just assumed, that Guy felt that his chances of getting caught would be less if Orlando were dead, so that he now always prefers killing Orlando to releasing him. Then Guy’s payoffs would be as shown in the column “(Violent) Guy.” The highest payoff is now assigned to the outcome in which Guy kidnaps and kills Orlando and the ransom is paid.

What about Vivica? If she cares about Orlando more than she cares about money, then her most preferred outcome is no kidnapping, and we’ll assign that the highest payoff of 5. Her least preferred outcome is that Orlando is kid- napped and killed and ransom is paid, so it receives the lowest payoff of 1. The payoffs for the other outcomes are shown in the table.

To ensure that the depiction in Figure 2.1 contains all of the relevant infor- mation, the payoffs have been included. Each terminal node corresponds to a particular outcome of the game, and listed below a terminal node are the pay- offs that Guy and Vivica assign to that outcome; the top number is Guy’s pay- off and the bottom number is Vivica’s payoff. While we could also list Orlando’s payoffs—he is surely not indifferent about what happens—that would be extraneous information. Because our objective is to say something about behavior, and this model of kidnapping allows only the kidnapper and the victim’s kin to act, only their payoffs matter.

This step of assigning a payoff to an outcome is analogous to what was done in Chapter 1. There we began with a person’s preferences for certain items (in our example, it was cell phone providers), and we summarized those preferences by assigning a number—known as utility—to each item. A per- son’s preferences were summarized by the resulting utility function, and her behavior was described as making the choice that yielded the highest utility. We’re performing the same step here, although game theory calls the number a payoff; still, it should be thought of as the same as utility.

The scenario depicted in Figure 2.1 is an example of an extensive form game. An extensive form game is depicted as a decision tree with decision nodes, branches, and terminal nodes. A decision node is a location in the tree at which one of the players has to act. Let us think about all of the informa- tion embodied in Figure 2.1. It tells us which players are making decisions (Guy and Vivica), the sequence in which they act (first Guy then, possibly, Vivica, and then Guy again), what choices are available to each player, and how they evaluate the various outcomes of the game. This extensive form game has four decision nodes: the initial node at which Guy decides whether to kidnap Orlando, the decision node at which Vivica decides whether to pay ransom, and Guy’s two decision nodes concerning whether to kill or release Orlando (one decision node for when Vivica pays ransom and one for when she does not). Extending out of each decision node are branches, where a branch represents an action available to the player who is to act at that deci- sion node. More branches mean more choices.