Games strategies and decision making by joseph harrington

Strategy, Decision Making

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.

We refer to the decision node at the top of the tree as the initial node (that is where the game starts) and to a node corresponding to an end to the game as a terminal node (which we have not bothered to represent as a dot in the figure). There are five terminal nodes in this game, since there are five possi- ble outcomes. Terminal nodes are distinct from decision nodes, as no player acts at a terminal node. It is at a terminal node that we list players’ payoffs,

2.2 Extensive Form Games: Perfect Information 21

Orioles' manager

Yankees' manager

MR

1

3

3

1

2 Orioles' manager

2 Yankees' manager

JG

RJ

JL

where a payoff describes how a player evaluates an outcome of the game, with a higher number indicating that the player is better off.

� SITUATION: BASEBALL, I

Good pitching will always stop good hitting and vice-versa. —CASEY STENGEL

One of the well-known facts in baseball is that right-handed batters generally perform better against left-handed pitch- ers and left-handed batters generally perform better against right-handed pitchers. TABLE 2.2 documents this claim.1 If you’re not familiar with baseball, batting average is the percentage of official at bats for which a batter gets a hit (in other words, a batter’s success rate). Right-handed batters got a hit in 25.5% of their attempts against a right- handed pitcher, or, as it is normally stated in baseball, their batting average was .255. However, against left-handed pitchers, their batting average was significantly higher, namely, .274. There is an analogous pattern for left-handed batters, who hit .266 against left-handed pitchers but an impressive .291 against right-handed pitching. Let’s explore the role that this simple fact plays in a commonly occurring strategic situation in baseball.

It is the bottom of the ninth inning and the game is tied between the Orioles and the Yankees. The pitcher on the mound for the Yankees is Mariano Rivera, who is a right-hander, and the batter due up for the Orioles is Javy Lopez, who is also a right-hander. The Orioles’ manager is thinking about whether to sub- stitute Jay Gibbons, who is a left-handed batter, for Lopez. He would prefer to have Gibbons face Rivera in order to have a lefty–righty matchup and thus a better chance of getting a hit. However, the Yankees’ manager could respond to Gibbons pinch-hitting by substituting the left-handed pitcher Randy Johnson for Rivera. The Orioles’ manager would rather have Lopez face Rivera than have Gibbons face Johnson. Of course, the Yankees’ manager has the exact opposite preferences.

The extensive form of this situation is shown in FIGURE 2.2. The Orioles’ manager moves first by deciding whether to substitute Gibbons for Lopez. If he does make the substi- tution, then the Yankees’ manager decides whether to substitute Johnson for Rivera. Encompassing these preferences, the Orioles’ manager assigns the highest payoff (which is 3) to when Gibbons bats against Rivera and the lowest payoff (1) to when Gibbons bats against Johnson. Because each manager is presumed to care only about winning, what makes the Orioles better off must make the Yankees worse off. Thus, the best outcome for the Yankees’ manager is when Gibbons bats against Johnson, and the worst is when Gibbons bats against Rivera.

TABLE 2.2

Batter Pitcher Batting Average

Right Right .255

Right Left .274

Left Right .291

Left Left .266

FIGURE 2.2 Baseball

22 CHAPTER 2: BUILDING A MODEL OF A STRATEGIC SITUATION

� SITUATION: GALILEO GALILEI AND THE INQUISITION, I

In 1633, the great astronomer and scientist Galileo Galilei was under consid- eration for interrogation by the Inquisition. The Catholic Church contends that in 1616 Galileo was ordered not to teach and support the Copernican theory, which is that the earth revolves around the sun, and furthermore that he violated this order with his latest book, The Dialogue Concerning the Two Chief World Systems. The situation to be modeled is the decision of the Catholic Church regarding whether to bring Galileo before the Inquisition and, if it does so, the decisions of Galileo and the Inquisitor regarding what to say and do.

The players are Pope Urban VIII, Galileo, and the Inquisitor. (Although there was actually a committee of Inquisitors, we’ll roll them all into one player.) The extensive form game is depicted in FIGURE 2.3. Urban VIII ini- tially decides whether to refer Galileo’s case to the Inquisition. If he declines to do so, then the game is over. If he does refer the case, then Galileo is brought before the Inquisition, at which time he must decide whether to con- fess that he did indeed support the Copernican case too strongly in his recent book. If he confesses, then he is punished and the game is over. If he does not confess, then the Inquisitor decides whether to torture Galileo. If he chooses

FIGURE 2.3 Galileo Galilei and the Inquisition

Urban VIII

Urban VIII 3

Galileo 5

Inquisitor 3

Galileo

Galileo

Do not confess

Do not confess

Do not torture

Confess

Confess

Inquisitor 5

3

4

2

4

2

4

1

5

1

2

1

Do not refer

Refer

Torture

2.2 Extensive Form Games: Perfect Information 23

To complete the extensive form game, payoff numbers are required. There are five outcomes to the game: (1) Urban VIII does not refer the case; (2) Urban VIII refers the case and Galileo initially confesses; (3) Urban VIII refers the case, Galileo does not initially confess, he is tortured, and then he con- fesses; (4) Urban VIII refers the case, Galileo does not initially confess, he is tortured, and he does not confess; and (5) Urban VIII refers the case, Galileo does not initially confess, and he is not tortured.

In specifying payoffs, we don’t want arbitrary numbers, but rather ones that accurately reflect the preferences of Urban VIII, Galileo, and the Inquisitor. Galileo is probably the easiest. His most preferred outcome is that Urban VIII does not refer the case. We’ll presume that if the case is referred, then Galileo’s preference ordering is as follows: (1) He does not confess and is not tortured; (2) he confesses; (3) he does not confess, is tortured, and does not confess; and (4) he does not confess, is tortured, and confesses. Galileo was a 69-year-old man, and evidence suggests that he was not prepared to be tortured for the sake of principle. Urban VIII is a bit more complicated, be- cause although he wants Galileo to confess, he does not relish the idea of this great man being tortured. We’ll presume that Urban VIII most desires a con- fession (preferably without torture) and prefers not to refer the case if it does not bring a confession. The Inquisitor’s preferences are similar to those of Urban VIII, but he has the sadistic twist that he prefers to extract confessions through torture.

So, what happened to Galileo? Let’s wait until we learn how to solve such a game; once having solved it, I’ll fill you in on a bit of history.

not to torture him, then, in a sense, Galileo has won, and we’ll consider the game ended. If the Inquisitor tortures poor Galileo, then he must decide whether to confess.

Galileo before the Inquisitor

H U

LT O

N A

R C H

IV E/

G ET

TY IM

A G

ES

24 CHAPTER 2: BUILDING A MODEL OF A STRATEGIC SITUATION

� SITUATION: HAGGLING AT AN AUTO DEALERSHIP, I

Donna shows up at her local Lexus dealership looking to buy a car. Coming into the showroom and sauntering around a taupe sedan, a salesperson, Marcus, appears beside her. After chatting a bit, he leads the way to his cu- bicle to negotiate. To simplify the modeling of the negotiation process, sup- pose the car can be sold for three possible prices, denoted pL, pM, and pH, and suppose pH > pM > pL. (H is for “high,” M is for “moderate,” and L is for “low.”)

The extensive form game is depicted in FIGURE 2.4. Marcus initially decides which of these three prices to offer Donna. In response, Donna can either ac- cept the offer—in which case the transaction is made at that price—or reject it. If it is rejected, Donna can either get up and leave the dealership (thereby end- ing the negotiations) or make a counteroffer. In the latter case, Donna can re- spond with a higher price, but that doesn’t make much sense, so it is assumed

Accept Reject A R

A R A R A R

A R

A R

Leave

DonnaDonna Donna

Donna

Donna

Donna

Marcus

Marcus

Donna

0

Marcus Marcus Marcus

Marcus 0

0

0

0

0

0

0

0 0

2(pM � pL)

0

0 0

2(pM � pL)

0

00

2(pM � pL)

2(pH � pL)

pM � pL

0

pM � pL pM � pL 0

pM � pH

pL pM

pLLeavepL pM

pM

pH

FIGURE 2.4 Haggling at an Auto Dealership

2.2 Extensive Form Games: Perfect Information 25

that she selects among those prices which are lower than what she was ini- tially offered (and turned down). For example, if Marcus offers a price of pH, then Donna can respond by asking for a price of either pM or pL. If Donna has decided to counteroffer, then Marcus can either accept or reject her counterof- fer. If he rejects it, then he can counteroffer with a higher price (though it must be lower than his initial offer). This haggling continues until either Donna leaves, or an offer is accepted by either Donna or Marcus, or they run out of prices to offer.

In terms of payoffs, assume that both Marcus and Donna get a zero payoff if the game ends with no sale. (There is nothing special about zero, by the way. What is important is its relationship to the other payoffs.) If there is a trans- action, Marcus’s payoff is assumed to be higher when the sale price is higher, while Donna’s payoff is assumed to be lower. More specifically, in the event of a sale at a price p, Donna is assumed to receive a payoff of pM � p and Marcus gets a payoff of 2(p � pL). (Why multiply by 2? For no particular reason.)

Think about what this is saying. If Marcus sells the car for a price of pL, then his payoff is zero because 2(pL � pL) � 0. He is then indifferent between selling it for a price of pL and not selling the car. At a price of pM, his payoff is positive, which means that he’s better off selling it at that price than not selling it; and his payoff is yet higher when he sells it for pH. For Donna, she is indifferent between buying the car at a price of pM, and not buying it, since both give the same payoff (of zero). She prefers to buy the car at a price of pL, as that price gives her a payoff of pM � pL > 0; she is worse off (relative to not buying the car) when she buys it at a price of pH, since that gives her a payoff of pM � pH < 0. (Yes, payoffs can be negative. Once again, what is important is the ordering of the payoffs.) These payoffs are shown in Figure 2.4.

To be clear about how to interpret this extensive form game, consider what can happen when Marcus initially offers a price of pH. Donna can either accept—in which case Marcus gets a payoff of 2(pH � pL) and Donna gets a payoff of pM � pH—or reject. With the latter, she can leave or counteroffer with either pL or pM. (Recall that we are allowing her to counteroffer only with a price that is lower than what she has been offered.) If Donna chooses the counteroffer of pL, then Marcus can accept—resulting in payoffs of zero for Marcus and pM � pL for Donna—or reject, in which case Marcus has only one option, which is to counteroffer with pM, in response to which Donna can ei- ther accept or reject (after which there is nothing left to do). If she instead chooses the counteroffer pM, then Marcus can accept or reject it. If he rejects, he has no counteroffer and the game ends.

It is worth noting that this extensive form game can be represented alter- natively by FIGURE 2.5. Rather than have the same player move twice in a row, the two decision nodes are combined into one decision node with all of the available options. For example, in Figure 2.4, Donna chooses between accept and reject in response to an initial offer of pM from Marcus, and then, if she chooses reject, she makes another decision about whether to counteroffer with pL or leave. Alternatively, we can think about Donna having three options (branches) when Marcus makes an initial offer of pM: (1) accept; (2) reject and counteroffer with pL; and (3) reject and leave. Figure 2.5 is a representation equivalent to that in Figure 2.4 in the sense that when we end up solving these games, the same answer will emerge.

26 CHAPTER 2: BUILDING A MODEL OF A STRATEGIC SITUATION

FIGURE 2.5 Simplifying the Extensive Form of the Haggling Game

Accept Reject

A Leave

A

A

R

DonnaDonna Donna

A R

Marcus

Marcus

Donna

0

Marcus Marcus Marcus 0

0

0

0pM � pH

0

0

A R

Donna

pM � pL

pL pM

pM

pL A LeavepL pM

pH

0

2(pM � pL) 2(pH � pL)

0

00

00

0pM � pL

0

pM � pL

2(pM � pL)

0

00

2(pM � pL)

Consider a two-player game in which a father chooses between actions yes, no, and maybe. His daughter moves second and chooses between stay home and go to the mall. The payoffs are as follows:

Outcome Father’s Payoff Daughter’s Payoff

yes and stay home 8 3

yes and go to the mall 5 9

no and stay home 4 1

no and go to the mall 1 5

maybe and stay home 7 2

maybe and go to the mall 2 7

2.1 CHECK YOUR UNDERSTANDING*

Write down the extensive form game for this strategic situation.

*All answers to Check Your Understanding are in the back of the book.

2.3 Extensive Form Games: Imperfect Information 27

2.3 Extensive Form Games: Imperfect Information RETURNING TO THE KIDNAPPING SCENARIO, suppose we want to model Guy (the kid- napper) and Vivica (the victim’s kin) as making their decisions without knowl- edge of what the other has done. The extensive form game in Figure 2.1 as- sumes that Guy learns whether ransom has been paid prior to deciding what to do with Orlando (the victim). An alternative specification is that Guy de- cides what to do with Orlando at the same time that Vivica decides about the ransom. You could imagine Guy deciding whether to release Orlando some- where in the city while Vivica is deciding whether to leave the ransom at an agreed-upon location. How do you set up an extensive form game with that feature?

The essential difference between these scenarios is information. In Figure 2.1, Guy knew what Vivica had done when it was time for him to make his decision, whereas Vivica did not know what was to happen to Orlando when she had to decide about paying the ransom. Vivica’s lack of knowledge was represented by having Vivica move before Guy. Now we want to suppose that at the time he has to decide about killing or releasing Orlando, Guy is also lacking knowledge about what Vivica is to do or has done. Well, we can’t make a decision tree in which Vivica moves after Guy and Guy moves after Vivica.

To be able to represent such a situation, the concept of an information set was created. An information set is made up of all of the decision nodes that a player is incapable of distinguishing among. Every decision node belongs to one and only one information set. A player is assumed to know which in- formation set he is at, but nothing more. Thus, if the information set has more than one node, then the player is un- certain as to where exactly he is in the game. All this should be clearer with an example.

FIGURE 2.6 is a reformulation of the Kid- napping game with the new assumption that Guy doesn’t get to learn whether Vivica has paid the ransom when he decides what to do with Orlando. In terms of nodes and branches, the trees in Figures 2.1 and 2.6 are identical. The distinctive element is the box drawn around the two decision nodes associ- ated with Guy choosing whether to release or kill Orlando (which are denoted III and IV). The nodes in that box make up Guy’s infor- mation set at the time he has to decide what to do with Orlando. Guy is assumed to know that the game is at either node III or node IV, but that’s it; he doesn’t know which of the two it is. Think about what this means. Not to know whether the game is at node III or node IV means that Guy doesn’t know whether the sequence of play has been “kid- nap and ransom is paid” or “kidnap and ran- som is not paid.” Well, this is exactly what we wanted to model; Guy doesn’t know whether

FIGURE 2.6 Kidnapping Game When the Exchange Is Simultaneous. The Box Around Nodes III and IV Represents the Information Set at the Point That Guy Has to Decide What to Do with Orlando

Guy

II

I II I

I I II I I IVIV

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

28 CHAPTER 2: BUILDING A MODEL OF A STRATEGIC SITUATION

the ransom is to be paid when he must decide whether to release or kill Orlando. The way this situation is represented is that Guy doesn’t know ex- actly where he is in the game: Is he at node III or node IV?

In any extensive form game, a player who is to act always has an informa- tion set representing what he knows. So what about when Vivica moves? What is her information set? It is just node II; in other words, she knows exactly where she is in the game. If we want to be consistent, we would then put a box around node II to represent Vivica’s information set. So as to avoid unneces- sary cluster, however, singleton information sets (i.e., an information set with a single node) are left unboxed. In Figure 2.6, then, Guy has two information sets; one is the singleton composed of the initial node (denoted I), and the other comprises nodes III and IV.

Returning to Vivica, since she is modeled as moving before Guy decides about Orlando, she makes her decision without knowing what has hap- pened or will happen to Orlando. Do you notice how I’m unclear about the timing? Does Vivica move chronologically before, after, or at the same time as Guy? I’ve been intentionally unclear because it doesn’t matter. What mat- ters is information, not the time of day at which someone makes a decision. What is essential is that Vivica does not know whether Guy has released or killed Orlando when she decides whether to pay ransom and that Guy does not know whether Vivica has paid the ransom when he decides whether to release or kill Orlando. In fact, FIGURE 2.7 is an extensive form game equiv- alent to that in Figure 2.6. It flips the order of decision making between Vivica and Guy, and the reason it is equivalent is that we haven’t changed the information that the players have when they move. In both games, we’ll say that Vivica and Guy move simultaneously (with respect to the ransom and release-or-kill decisions), which is meant to convey the fact that their

FIGURE 2.7 Extensive Form Equivalent to Figure 2.6

Guy

Guy 3

Vivica 5 Kill

Guy

4

1

2

2

5

3

1

4

Do not kidnap

Release

Kidnap

Vivica

Pay ransom

Do not pay ransom

Pay ransom

Do not pay ransom

2.3 Extensive Form Games: Imperfect Information 29

information is the same as when they make their decisions at the exact same time.

An extensive form game in which all information sets are singletons— such as the games in Figures 2.1–2.5—is referred to as a game of perfect information, since players always know where they are in the game when they must decide. A game in which one or more information sets are not singletons, such as the game in Figure 2.6, is known as a game of imper- fect information.

� SITUATION: MUGGING

Notorious for being cheap, the comedian Jack Benny would tell the fol- lowing story: “I was walking down a dark alleyway when someone came from behind me and said, ‘Your money or your life.’ I stood there frozen. The mugger said again, ‘Your money or your life.’ I replied, ‘I’m thinking, . . . I’m thinking.’”

Simon is walking home late at night when suddenly he realizes that there is someone behind him. Before he has a chance to do anything, he hears, “I have a gun, so keep your mouth shut and give me your wallet, cell phone, and iPod.” Simon doesn’t see a gun, but does notice that the mugger has his hand in his coat pocket, and it looks like there may be a gun in there. If there is no gun, Simon thinks he could give the mugger a hard shove and make a run for it. But if there is a gun, there is a chance that trying to escape will result in him being shot. He would prefer to hand over his wallet, cell phone, and even his iPod than risk serious injury. Earlier that evening, the mugger was engag- ing in his own decision making as he debated whether to use a gun. Because the prison sentence is longer when a crime involves a gun, he’d really like to conduct the theft without it.

The mugging situation just described is depicted as the extensive form game in FIGURE 2.8. The mugger moves first in deciding between three options: not to use a gun; bring a gun, but not show it to the victim; and bring a gun

FIGURE 2.8 Mugging

Mugger

Mugger

Simon

3

2

5

4

2

6

6

3

Gun & show Gun &

hide

No gun

SimonSimon

Resist Do not resist Resist Do not resist

3

2

4

5

Resist Do not resist

30 CHAPTER 2: BUILDING A MODEL OF A STRATEGIC SITUATION

and show it to the victim. In response to each of these actions, Simon has to decide whether to resist the mugger by doing the “shove and run” (resist) or by complying with the mugger’s instructions (do not resist). Simon has two in- formation sets. One is a singleton and is associated with the mugger’s having and showing a gun. The other information set comprises two nodes, one cor- responding to the mugger’s having a gun, but not showing it, and the other to the mugger’s not having a gun. With the latter information set, Simon isn’t sure whether the mugger’s pocket contains a gun.

In specifying the payoffs, the best outcome for Simon is that the mugger does not use a gun and Simon resists; the worst outcome is that the mugger has a gun and Simon resists. For the mugger, the best outcome is that Simon does not resist and the mugger doesn’t use a gun in the robbery. The worst out- come is that he doesn’t use the gun and Simon resists, as then the mugger comes away empty handed.

� SITUATION: U.S. COURT OF APPEALS FOR THE FEDERAL CIRCUIT

When the U.S. Court of Appeals for the Federal Circuit hears a case, a panel of 3 judges is randomly selected from the 12 judges on the court. After a case is filed, the parties submit written briefs stating their argu- ment. If the court decides to hear oral arguments, each party’s lawyer is given between 15 and 30 minutes. The panel of 3 judges then decides the case. Let us model a simplified version of this judicial setting when there is no oral argument.

One side of the case is represented by attorney Elizabeth Hasenpfeffer, while attorney Joseph Fargullio represents the other party. Prior to their ap- pearance, each attorney decides on a legal strategy and writes a brief based on it. For Ms. Hasenpfeffer, let us denote the strategies as A and B; for Mr. Fargullio, they’ll be denoted I and II. The briefs are submitted simultaneously, in the sense that each attorney writes a brief not knowing what the other has writ- ten. This situation is reflected in FIGURE 2.9, in which Ms. Hasenpfeffer moves first and Mr. Fargullio moves second, but with an information set that en- compasses both the node in which Ms. Hasenpfeffer chose A and the one in which she chose B.

After reading the two briefs, the three members of the court then vote either in favor of Ms. Hasenpfeffer’s argument or in favor of Mr. Fargullio’s argu- ment. This vote is cast simultaneously in that each judge writes down a deci- sion on a piece of paper. For brevity, the judges are denoted X, Y, and Z. As depicted, each judge has four information sets, where an information set cor- responds to the pair of legal strategies selected by the attorneys. Judge X moves first and thus doesn’t know how judges Y and Z have voted. Judge Y moves second and thus doesn’t know how Judge Z has voted (since Z is de- scribed as moving after him), but she also doesn’t know how Judge X has voted because of the structure of the information sets. Each of Judge Y’s in- formation sets includes two decision nodes: one for Judge X voting in favor of Ms. Hasenpfeffer and one for Judge X in favor of Mr. Fargullio. Turning to Judge Z, we see that each of her information sets comprises the four nodes that correspond to the four possible ways that Judges X and Y could have

FIGURE 2.9 U.S. Court of Appeals

EH

JF

X

Y

Z

1

0

2

2

2

1

0

2

2

1

H F

1

0

2

1

2

0

1

2

1

1

H F

1

0

1

2

2

0

1

1

2

1

H

Z

F

0

1

1

1

2

0

1

1

1

1

H F

H F

Y

X

H F

H F

JF

EH

I I II I

A B

I I II I

1

0

1

1

1

1

0

1

1

2

H F

1

0

1

2

1

0

1

1

2

2

H F

1

0

2

1

1

0

1

2

1

2

H

Z

F

0

1

2

2

1

0

1

2

2

2

H F

H F

Y

X

H F

H F

1

0

1

1

1

1

0

1

1

2

H F

1

0

1

2

1

0

1

1

2

2

H F

1

0

2

1

1

0

1

2

1

2

H

Z

F

0

1

2

2

1

0

1

2

2

2

H F

H F

Y

X

H F

H F

1

0

2

2

2

1

0

2

2

1

H F

1

0

2

1

2

0

1

2

1

1

H F

1

0

1

2

2

0

1

1

2

1

H

Z

F

0

1

1

1

2

0

1

1

1

1

H F

H F

Y

X

H F

H F

31

32 CHAPTER 2: BUILDING A MODEL OF A STRATEGIC SITUATION

voted. Although the judges are depicted as moving sequentially, in fact each votes without knowledge of how the other two have voted; in other words, the judges vote simultaneously.

� SITUATION: THE IRAQ WAR AND WEAPONS OF MASS DESTRUCTION

Now let’s take on some recent history: the situation faced by Iraq, the United Nations, and the United States that culminated in the U.S. invasion of Iraq on March 20, 2003. At issue is whether Sadaam Hussein has weapons of mass destruction (WMD). As shown in FIGURE 2.10, Iraq is modeled as hav- ing a choice of possessing or not possessing WMD. Without knowledge of Iraq’s choice, the United Nations decides whether to request inspections of Iraq. The United Nations then has one information set, which includes both of Iraq’s feasible actions: the one when it has WMD and the other when it does not. If the United Nations chooses not to request inspections, then the United States decides whether or not to invade Iraq, at which point we’ll consider the game done. If the United Nations does request inspections, then the move goes back to Iraq. If Iraq does not have WMD, then it can choose to deny inspections or allow them. If, instead, Iraq has WMD, then it can deny inspections, allow inspections, or allow inspections and hide the WMD. With the last option, suppose Iraq succeeds in preventing inspectors from finding WMD. Assume that when Iraq does have WMD and does not hide them from the inspectors, the WMD are found. After Iraq moves in response to the request for inspections by the United Nations, and the outcome of the inspections is revealed, the United States moves again regarding whether to attack Iraq.

The United States has four information sets. The information set de- noted I includes the two nodes associated with (1) Iraq having WMD and the United Nations not choosing inspections, and (2) Iraq not having WMD and the United Nations not choosing inspections. Although the United States doesn’t get to observe Iraq’s choice, it does get to observe the UN de-

cision. Information set II corresponds to the scenario in which inspections are requested by the United Nations and allowed by Iraq, but WMD are not found, either be- cause Iraq does not have them or because it does have them but has successfully hidden them from the in- spectors. Information set III denotes the situation in which the United Nations requests inspections, but they are refused by Iraq; once again, the United States doesn’t know whether Iraq has WMD. The lone single- ton information set for the United States is node IV,

which is associated with Iraq’s having WMD, the United Nation’s having re- quested inspections, and Iraq’s having allowing unobstructed inspections, in which case WMD are found. A similar exercise can be conducted to describe the one information set of the United Nations and the three in- formation sets of Iraq (all of which are singletons, as Iraq is the only one hiding something).

Now let us return to the Mugging game and suppose that the mugger not only chooses whether to use a gun and whether to show it, but also whether to load the gun with bullets. If Simon sees the gun, he doesn’t know whether it is loaded. Write down the extensive form of this strategic situation. (You can ignore payoffs.)

2.2 CHECK YOUR UNDERSTANDING

FIGURE 2.10 Iraq War and WMD. The Abbreviations W and NW Represent War and No War, Respectively

II

I II I

IVIVI I II I I

Iraq

Iraq Iraq

Iraq

UN

UN

1

10

11

11

14 5US

US

War No war No war

2

6

10

13

13 6

War No war No warDeny

NO WMD WMD

Allow

Inspect Inspect Do not inspect

Do not inspect

Deny Allow Allow & hide

7

1

12

7

9 1

War

3

5

9

14

12 7

War

5

2

13

8

8 2

W NW

6

3

14

9

10 3

W NW

4

4

8

12

4 11

W NW

US

US

US

33

34 CHAPTER 2: BUILDING A MODEL OF A STRATEGIC SITUATION

2.4 What Is a Strategy? Victorious warriors win first and then go to war, while defeated warriors go to war first and then seek to win. —SUN TZU2

WHAT DO YOU THINK the preceding quote from Sun Tzu means? One interpreta- tion is that, to be victorious, you should develop a detailed plan prior to going to battle and then, once in battle, execute that plan. Rather than trying to fig- ure out a plan over the course of the battle, perform all of your thinking be- fore one arrow is flung or one cannon is fired.

The notion of a strategy is central to game theory, and its definition is ex- actly what Sun Tzu had in mind. A strategy is a fully specified decision rule for how to play a game. It is so detailed and well specified that it accounts for every contingency. It is not a sequence of actions, but rather a catalog of con- tingency plans: what to do, depending on the situation. As was well expressed by J. D. Williams in an early book on game theory, a strategy is “a plan so com- plete that it cannot be upset by enemy action or Nature; for everything that the enemy or Nature may choose to do, together with a set of possible actions for yourself, is just part of a description of the strategy.”3

As a conceptual device, we imagine a player choosing a strategy before the game begins. This strategy could, in principle, be written down as a set of in- structions and given to another person to play. In other words, having a strat- egy means doing all of the hard thinking (utilizing intelligence, judgment, cleverness, etc.) prior to playing the game. The actual play is nothing more than following the instructions provided by the strategy selected. Of course, this description of a strategy is an abstraction, since, in practice, surely judg- ment and acumen are applied in the midst of a strategic situation. However, you’ll need to accept this definition of strategy if you are to make headway into gaining insight into strategic situations. It is one of those basic postulates that is valuable in practice because of its purity in form.

To be more concrete as to the nature of a strategy in game theory, let us re- turn to the Kidnapping game in Figure 2.1. What is a strategy for the kidnap- per? As we’ve just said, a strategy is a complete decision rule—one that pre- scribes an action for every situation that a player can find himself in. Guy (the kidnapper) can find himself in three situations: (1) contemplating whether to kidnap Orlando (i.e., the initial node); (2) having kidnapped Orlando, with ran- som having been paid by Vivica, and deciding whether to kill or release Orlando; and (3) having kidnapped Orlando, with ransom not having been paid by Vivica, and deciding whether to kill or release Orlando. It is not coinciden- tal that Guy can find himself in three scenarios and he has three information sets: A “situation” for a player is defined as finding himself at an information set; hence, a strategy assigns one action to each of a player’s information sets.

A template for Guy’s strategy is, then,

At the initial node, _____ [ fill in kidnap or do not kidnap].

If a kidnapping occurred and ransom was paid, then _____ [ fill in kill or release].

If a kidnapping occurred and ransom was not paid, then _____ [ fill in kill or release].

There are as many strategies as ways in which to fill in those three blanks. Exhausting the possibilities, we have eight feasible strategies:

2.4 What Is a Strategy? 35

1. At the initial node, kidnap. If a kidnapping occurred and ransom was paid, then release. If a kidnapping occurred and ransom was not paid, then kill.

2. At the initial node, kidnap. If a kidnapping occurred and ransom was paid, then release. If a kidnapping occurred and ransom was not paid, then release.

3. At the initial node, kidnap. If a kidnapping occurred and ransom was paid, then kill. If a kidnapping occurred and ransom was not paid, then release.

4. At the initial node, kidnap. If a kidnapping occurred and ransom was paid, then kill. If a kidnapping occurred and ransom was not paid, then kill.

5. At the initial node, do not kidnap. If a kidnapping occurred and ransom was paid, then release. If a kidnapping occurred and ransom was not paid, then kill.

6. At the initial node, do not kidnap. If a kidnapping occurred and ransom was paid, then release. If a kidnapping occurred and ransom was not paid, then release.

7. At the initial node, do not kidnap. If a kidnapping occurred and ransom was paid, then kill. If a kidnapping occurred and ransom was not paid, then release.

8. At the initial node, do not kidnap. If a kidnapping occurred and ransom was paid, then kill. If a kidnapping occurred and ransom was not paid, then kill.

Analogously, we can define a strategy template for Vivica:

If a kidnapping occurred, then _____ [fill in pay ransom or do not pay ransom].

Since Vivica has just one information set, her strategy is just a single action. With only two feasible actions and one information set, she then has two fea- sible strategies:

1. If a kidnapping occurred, then pay ransom.

2. If a kidnapping occurred, then do not pay ransom.

The strategy set for a player is defined to be the collection of all feasible strategies for that player. In this example, the strategy set for Guy comprises the eight strategies just listed for him, and the strategy set for Vivica is made up of two strategies. There are then 16 possible strategy pairs for this game.

As previously mentioned, all of the hard thinking goes into choosing a strat- egy, and once one is chosen, play arises from the implementation of that strat- egy. To see this point more clearly, suppose Guy chooses the following strategy:

At the initial node, kidnap.

If a kidnapping occurred and ransom was paid, then release.

If a kidnapping occurred and ransom was not paid, then kill.

Suppose also that Vivica chooses the following strategy:

If a kidnapping occurred, then pay ransom.

So what will happen? According to Guy’s strategy, he kidnaps Orlando. Vivica then pays the ransom (as instructed by her strategy), and in response to the

36 CHAPTER 2: BUILDING A MODEL OF A STRATEGIC SITUATION

ransom being paid, Guy releases Orlando (reading from his strategy). Similarly, you can consider any of the 16 possible strategy pairs and figure out what the ensuing sequence of actions is. It’s just a matter of following instructions.

Before moving on, notice a peculiar feature about some of Guy’s strategies, namely, that strategies 5 through 8 prescribe do not kidnap and then tell Guy what to do if he chose kidnap. In other words, it tells him to do one thing, but also what to do if he doesn’t do what he should have done. In spite of how

strange that might sound, we’ll allow for this possibility in a player’s strategy set, for three reasons. First, it’s simpler to define a strategy as any way in which to assign feasible actions to information sets than to try to come up with a more complicated definition that rules out these “silly” strategies. Second, inclusion of the silly strategies is, at

worst, some harmless detritus that won’t affect the conclusions that we draw. And the third reason, which is the most important, I can’t tell you now. It’s not that I don’t want to, but you’ll need to know a bit about solving games before you can understand what I want to say. I’ll clue you in come Chapter 4.

2.5 Strategic Form Games THE EXTENSIVE FORM IS one type of scaffolding around which a game can be con- structed. Its appeal is that it describes (1) a concrete sequence with which players act, (2) what actions they have available and what they know, and (3) how they evaluate the outcomes, where an outcome is a path through the de- cision tree. In this section, we introduce an alternative scaffolding that, though more abstract, is easier to work with than the extensive form. In the next section, we’ll show how you can move back and forth between these two game forms so that you may work with either one.

A strategic form game (which, in the olden days of game theory, was referred to as the normal form) is defined by three elements that address the following questions: (1) Who is making decisions? (2) Over what are they making deci- sions? and (3) How do they evaluate different decisions? The answer to the first question is the set of players, the answer to the second question is the players’ strategy sets, and the answer to the third question is players’ payoff functions.

The set of players refers to the collection of individuals who have decisions to make. The decision is with regard to a strategy, which is defined exactly as in the previous section. A player’s strategy set is the collection of strategies from which he can choose. Finally, a player’s payoff function tells us how the player evaluates a strategy profile, which is a collection of strategies, one for each of the players. A higher payoff means that a player is better off, and when we get to solving a game, the presumption will be that each player tries to maximize his or her payoff.

Although a player does not intrinsically value strategies—for they are just decision rules, and you can’t eat, wear, caress, or live in a decision rule—a strategy profile determines the outcome of the game (e.g., whether there is a kidnapping), and a player does care about the outcome. One final piece of jar- gon before we move on: The term n-tuple refers to n of something—for ex- ample, an n-tuple of strategies in a game with n players. Two of something is a pair, three of something is a triple, and n of something is an n-tuple. With all of this jargon, you can now talk like a game theorist!

For the revised Kidnapping game in Figure 2.6, write down the strategy sets for Guy and Vivica.

2.3 CHECK YOUR UNDERSTANDING

2.5 Strategic Form Games 37

� SITUATION: TOSCA

The force of my desire has two aims, and the rebel’s head is not the more pre- cious. Ah, to see the flames of those victorious eyes smoulder, aching with love! Caught in my arms, smouldering with love. One to the gallows, the other in my arms! —BARON SCARPIA FROM THE OPERA TOSCA

Giacomo Puccini was arguably the last great operatic composer. He died in 1924 after a career that produced such spectacular successes as La Bohème (the plot of which was recycled for the Broadway musical Rent), Madame Butterfly, and Turandot. Puccini’s music is the type that leads you to hum or whistle it after you leave the theater. It clearly runs counter to the popular def- inition of opera as two heavy-set people 6 inches apart screaming at the top of their lungs.

One of his most popular operas is Tosca, which is a story of love, devotion, corruption, lechery, and murder—in other words, perfect fodder for learning game theory!4 The main characters are Baron Vitellio Scarpia, the local chief of police; an attractive woman named Floria Tosca; and Mario Cavaradossi, her lover. Scarpia has lustful designs on Tosca and has devised a diabolical plot to act on them. He first has Cavaradossi arrested. He then tells Tosca that Cavaradossi is to go before the firing squad in the morning and he (Scarpia) can order the squad to use real bullets—and Cavaradossi will surely die—or blanks—in which case Cavaradossi will survive. After then hearing Scarpia’s sexual demands, Tosca must decide whether or not to concede to them.

Scarpia and Tosca meet that evening after Scarpia has already given his or- ders to the firing squad. Tosca faces Scarpia and—knowing that Scarpia has decided, but not knowing what he has decided—chooses between consenting to his lustful desires or thrusting the knife she has hidden in her garments into the heart of this heartless man.

In writing down the strategic form game, we have our two players, Scarpia and Tosca. The strategy set for Scarpia has two strategies—use real bullets or use blanks—while Tosca can either consent or stab Scarpia. As de- picted in FIGURE 2.11, the two strategies for Tosca correspond to the two rows, while the two strategies for Scarpia correspond to the two columns. Thus, Tosca’s choosing a strategy is equivalent to her choosing a row.

The final element to the strategic form game are the payoffs. The first number in a cell is Tosca’s payoff and the second num- ber is Scarpia’s payoff. (We will use the convention that the row player’s payoff is the first number in a cell.) For example, if Tosca chooses stab and Scarpia chooses blanks, then Tosca’s payoff is 4 and Scarpia’s payoff is 1. We have chosen the payoffs so that Tosca ranks the four possible strategy pairs as follows (going from best to worst): stab and blanks, consent and blanks, stab and real, and consent and real. Due to her love for Cavaradossi, the most important thing to her is that Scarpia use blanks, but it is also the case that she’d rather kill him than con- sent to his lascivious libido. From the information in the opening quote, Scarpia’s payoffs are such that his most preferred strategy pair is consent and real, as he then gets what he wants from Tosca and eliminates Cavaradossi as a future rival for Tosca. His least preferred outcome is, not surprisingly, stab and blanks.

FIGURE 2.11 Tosca

2,2 4,1

1,4 3,3 Tosca

Scarpia

Stab

Consent

Real Blanks

38 CHAPTER 2: BUILDING A MODEL OF A STRATEGIC SITUATION

Figure 2.11 is known as a payoff matrix and succinctly contains all of the elements of the strategic form game. Tosca is a reinterpretation of the Prisoners’ Dilemma, which is the most famous game in the entire kingdom of game theory. I’ll provide the original description of the Prisoners’ Dilemma in Chapter 4.

� SITUATION: COMPETITION FOR ELECTED OFFICE

The word ‘politics’ is derived from the word “poly,” meaning “many,” and the word “ticks,” meaning “blood sucking parasites. —LARRY HARDIMAN

Consider the path to the U.S. presidency. The Republican and Democratic can- didates are deciding where to place their campaign platforms along the polit- ical spectrum that runs from liberal to conservative. Let’s suppose that the Democratic candidate has three feasible platforms: liberal, moderately liberal, and moderate. Let’s suppose that the Republican candidate has three as well: moderate, moderately conservative, and conservative.

A candidate’s payoffs are assumed to depend implicitly on the candidate’s ideological preferences—what platform he would like to see implemented— and what it’ll take to have a shot at getting elected. Assume that most voters are moderate. The Democratic candidate is presumed to be liberal (i.e., his most preferred policies to implement are liberal), but he realizes that he may need to choose a more moderate platform in order to have a realistic chance of winning. Analogously, the Republican candidate is presumed to be conser- vative, and she, too, knows that she may need to moderate her platform. The payoff matrix is shown in FIGURE 2.12.

FIGURE 2.12 Competition for Elected Office

4,4 6,3 8,2

3,6 5,5 9,4

2,8 4,9 7,7

Republican candidate

Democratic candidate

Moderately liberal

Liberal

Moderate

Moderately conservativeModerate Conservative

The payoffs reflect these two forces: a preference to be elected with a plat- form closer to one’s ideal, but also a desire to be elected. Note that a candidate’s payoff is higher when his or her rival is more extreme, as this makes it easier to get elected. For example, if the Democratic candidate supports a moderately liberal platform, then his payoff rises from 3 to 5 to 9 as the Republican can- didate’s platform becomes progressively more conservative. Note also that as one goes from (moderate, moderate) to (moderately liberal, moderately conserva- tive) to (liberal, conservative), each candidate’s payoff rises, since, for all three strategy pairs, the candidate has an equal chance of winning (the candidates are presumed equally distant from what moderate voters want) and prefers to be elected with a platform closer to his or her own ideology.

2.6 Moving from the Extensive Form and Strategic Form 39

� SITUATION: THE SCIENCE 84 GAME

The magazine Science 84 came up with the idea of running the following con- test for its readership: Anyone could submit a request for either $20 or $100. If no more than 20% of the submissions requested $100, then everybody would receive the amount he or she requested. If more than 20% of the sub- missions asked for $100, then everybody would get nothing.

The set of players is the set of people who are aware of the contest. The strategy set for a player is made up of three elements: do not send in a request, send in a request for $20, and send in a request for $100. Let us suppose that each player’s payoff is the amount of money received, less the cost of submit- ting a request, which we’ll assume is $1 (due to postage and the time it takes to write and mail a submission).

In writing down player i’s payoff function, let x denote the number of play- ers (excluding player i) who chose the strategy send in a request for $20 and y denote the number of players (excluding player i) who chose send in a request for $100. Then player i’s payoff function is:

0 if i chooses do not send in a request

19 if i chooses send in a request for $20 and � .2 y

x � y � 1

99 if i chooses send in a request for $100 and � .2 y � 1

x � y � 1

�1 if i chooses send in a request for $20 and .2 � y

x � y � 1

�1 if i chooses send in a request for $100 and .2 � y � 1

x � y � 1

For example, if player i requested $20, and no more than 20% of the submis-

sions requested $100 (i.e., � .2), then she receives $20 from Science 84,

from which we need to subtract the $1 cost of the submission. Although it would be great to know what happened, Science 84 never ran

the contest, because Lloyd’s of London, the insurer, was unwilling to provide insurance for the publisher against any losses from the contest.

2.6 Moving from the Extensive Form and Strategic Form FOR EVERY EXTENSIVE FORM GAME, there is a unique strategic form representation of that game. Here, we’ll go through some of the preceding examples and show how you can derive the set of players (that one’s pretty easy), the strategy sets, and the payoff functions in order to get the corresponding strategic form game.

� SITUATION: BASEBALL, II

Consider the Baseball game in Figure 2.2. The strategy set of the Orioles’ man- ager includes two elements: (1) Substitute Gibbons for Lopez and (2) retain Lopez. As written down, there is a single information set for the Yankees’ man- ager, so his strategy is also a single action. His strategy set comprises (1) sub- stitute Johnson for Rivera and (2) retain Rivera. To construct the payoff ma- trix, you just need to consider each of the four possible strategy profiles and determine to which terminal node each of them leads.

y x � y � 1

⎞ ⎪ ⎪ ⎪ ⎬ ⎟ ⎪⎪ ⎠

40 CHAPTER 2: BUILDING A MODEL OF A STRATEGIC SITUATION

If the strategy profile is (retain Lopez, retain Rivera), then the payoff is 2 for the Orioles’ manager and 2 for the Yankees’ manager, since Lopez bats against Rivera. The path of play, and thus the payoffs, are the same if the profile is in- stead (retain Lopez, substitute Johnson), because substitute Johnson means “Put in Johnson if Gibbons substitutes for Lopez”. Since the latter event doesn’t occur when the Orioles’ manager chooses retain Lopez, Johnson is not substi- tuted. When the strategy profile is (substitute Gibbons, retain Rivera), Gibbons bats against Rivera and the payoff pair is (3,1), with the first number being the payoff for the Orioles’ manager. Finally, if the strategy profile is (substitute Gibbons, substitute Johnson), Gibbons bats against Johnson and the payoff pair is (1,3). The payoff matrix is then as depicted in FIGURE 2.13.