Preface for the Third Edition xi
Preface for the Second Edition xiii
Preface for the First Edition xvi
Acknowledgments xix
Introduction xxi
1 Matrix Two-Person Games 1
1.1 What Is Game Theory? 1
1.2 Motivating Examples 2
1.2.1 Three Card Poker 3
1.2.2 Simplified Baseball 6
1.2.3 2 × 2 NIM 9
1.3 Mathematical Setup 11
1.3.1 Definition of a Matrix Game 11
1.3.2 Saddle Points: What It Means to be Optimal 14
Problems 15
1.4 Mixed Strategies 17
1.4.1 Definition of Mixed Strategies 17
1.4.2 Optimal Mixed Strategies 18
1.4.3 Best Response Strategies 23
1.4.4 Dominated Strategies 27
Problems 30
1.5 The Indifference Principle and Completely Mixed Games 32
1.5.1 2 × 2 Games 35
1.5.2 Completely Mixed Games and Invertible Matrix Games 37
1.5.3 An Application: Optimal Target Choice and Defense 40
Problems 45
1.6 Finding Saddle Points in General 49
1.6.1 Graphical Methods 49
1.6.2 The n × m Case and Linear Programming 52
1.6.3 Using Calculus 58
1.6.4 Symmetric Games 59
Problems 62
1.7 Existence of Saddle Points: The Von Neumann Minimax Theorem 67
1.7.1 Statement of the Minimax Theorem 67
1.7.2 Von Neumann’s Theorem Guarantees Matrix Games Have Saddle Points 69
Problems 69
1.8 Review Problems 75
Problems 75
1.9 Appendix: A Proof of the von Neumann Minimax Theorem 76
2 Two-Person Nonzero Sum Games 81
2.1 The Basics 81
2.1.1 Prisoner’s Dilemma 83
Problems 88
2.2 2 × 2 Bimatrix Games, Best Response, Equality of Payoffs 90
Problems 96
2.3 Interior Mixed Nash Points by Calculus 98
2.3.1 Calculus Method for Interior Nash 98
Problems 105
2.3.2 Existence of a Nash Equilibrium for Bimatrix Games 107
2.4 Nonlinear Programming Method for Nonzero Sum Two-Person Games 108
Summary of Methods for Finding Mixed Nash Equilibria 111
Problems 112
2.5 Correlated Equilibria 114
2.5.1 Motivating Example 114
2.5.2 Definition of Correlated Equilibrium and Social Welfare 115
Problems 122
2.6 Choosing Among Several Nash Equilibria (Optional) 123
Problems 128
Bibliographic Notes 128
3 Games in Extensive Form: Sequential Decision Making 129
3.1 Introduction to Game Trees/Extensive form of Games 129
3.1.1 Gambit 129
Problems 140
3.2 Backward Induction and Subgame Perfect Equilibrium 143
Problems 147
3.2.1 Subgame Perfect Equilibrium 149
3.2.2 Examples of Extensive Games Using Gambit 154
3.3 Behavior Strategies in Extensive Games 157
Problems 159
3.4 Extensive Games with Imperfect Information 165
3.4.1 Bayesian Games and Bayesian Equilibria 170
3.4.1.1 Separating and Pooling PBEs 182
Problems 189
Bibliographic Notes 198
4 N-Person Nonzero Sum Games and Games with a Continuum of Strategies 199
4.1 Motivating Examples 199
4.2 The Basics 202
4.2.1 Do We Have Mixed Strategies in Continuous Games 206
4.2.2 Existence of Pure NE 214
Problems 227
4.3 Economics Applications of Nash Equilibria 234
Problems 248
4.4 Duels 252
Problems 259
4.5 Auctions 260
4.5.1 Complete Information 264
Problems 265
4.5.2 Symmetric Independent Private Value Auctions 265
Problems 272
4.6 Stable Matching, Marriage, and Residencies 272
4.6.1 Finding a Stable Marriage Using Mathematica 277
Problems 278
4.7 Selected Chapter Problems 280
Problems 280
Bibliographic Notes 283
5 Repeated Games 285
5.1 Games Repeated Until 288
5.2 Grim-Trigger in General 295
5.2.1 A Better Estimate for the Discount Factor 299
5.2.2 Folk Theorems 300
Problems 301
Bibliographic Notes 305
6 Cooperative Games 307
6.1 What Is a Cooperative Game? 307
6.2 Coalitions and Characteristic Functions 308
Problems 324
6.2.1 More on the Core and Least Core 327
Problems 333
6.3 The Nucleolus 334
6.3.1 An Exact Nucleolus for Three Player Games 341
Problems 346
6.4 The Shapley Value 348
Problems 359
Bibliographic Notes 364
7 Bargaining 367
7.1 Introduction 367
7.2 The Nash Model with Security Point 373
7.3 Threats 379
7.3.1 Finding the Threat Strategies 381
7.3.1.1 Summary Approach for Bargaining with Threat Strategies 383
7.3.1.2 Another Way to Derive the Threat Strategies Procedure 384
7.4 The Kalai–Smorodinsky Bargaining Solution 389
7.5 Sequential Bargaining 391
Problems 396
Bibliographic Notes 399
8 Evolutionary Stable Strategies and Population Games 401
8.1 Evolution 401
8.1.1 Properties of an ESS 407
Problems 412
8.2 Population Games 413
8.3 The Von Neumann Minimax Theorem from Replicator Dynamics 429
Problems 431
Bibliographic Notes 437
Appendix A The Essentials of Matrix Analysis 439
Appendix B The Essentials of Probability 443
Appendix C The Mathematica Commands 447
C.1 The Upper and Lower Values of a Game 447
C.2 The Value of an Invertible Matrix Game with Mixed Strategies 448
C.3 Solving Matrix Games 448
C.4 Interior Nash Points 449
C.5 Lemke–Howson Algorithm for Nash Equilibrium 450
C.6 Is the Core Empty? 450
C.7 Find and Plot the Least Core 451
C.8 Nucleolus Procedure and Shapley Value 453
C.9 Mathematica Code for Three-Person Nucleolus 454
C.10 Plotting the Payoff Pairs 456
C.11 Bargaining Solutions 457
C.12 Mathematica for Replicator Dynamics 459
Appendix D Biographies 461
D.1 John Von Neumann 461
D.2 John Forbes Nash 462
Selected Problem Solutions 463
References 545
Index 547
