Game Theory Basics

Game theory is the science of interaction. This textbook, derived from courses taught by the author and developed over several years, is a comprehensive, straightforward introduction to the mathematics of non-cooperative games. It teaches what every game theorist should know: the important ideas and results on strategies, game trees, utility theory, imperfect information, and Nash equilibrium. The proofs of these results, in particular existence of an equilibrium via fixed points, and an elegant direct proof of the minimax theorem for zero-sum games, are presented in a self-contained, accessible way. This is complemented by chapters on combinatorial games like Go; and, it has introductions to algorithmic game theory, traffic games, and the geometry of two-player games. This detailed and lively text requires minimal mathematical background and includes many examples, exercises, and pictures. It is suitable for self-study or introductory courses in mathematics, computer science, or economics departments. Cover Half-title Page Title Page Copyright Page Contents Preface Aims and Contents Mathematical and Scholarly Level Acknowledgments 1 Nim and Combinatorial Games 1.1 Prerequisites and Learning Outcomes 1.2 Nim 1.3 Top-down Induction 1.4 Game Sums and Equivalence of Games 1.5 Nim, Poker Nim, and the Mex Rule 1.6 Sums of Nim Heaps 1.7 Finding Nim Values 1.8 A Glimpse of Partizan Games 1.9 Further Reading 1.10 Exercises for Chapter 1 2 Congestion Games 2.1 Prerequisites and Learning Outcomes 2.2 Introduction: The Pigou Network 2.3 The Braess Paradox 2.4 Definition of Congestion Games 2.5 Existence of Equilibrium in a Congestion Game 2.6 Atomic and Splittable Flow, Price of Anarchy 2.7 Further Reading 2.8 Exercises for Chapter 2 3 Games in Strategic Form 3.1 Prerequisites and Learning Outcomes 3.2 Games in Strategic Form 3.3 Best Responses and Equilibrium 3.4 Games with Multiple Equilibria 3.5 Dominated Strategies 3.6 The Cournot Duopoly of Quantity Competition 3.7 Games without a Pure-Strategy Equilibrium 3.8 Symmetric Games with Two Strategies per Player 3.9 Further Reading 3.10 Exercises for Chapter 3 4 Game Trees with Perfect Information 4.1 Prerequisites and Learning Outcomes 4.2 Definition of Game Trees 4.3 Backward Induction 4.4 Strategies in Game Trees 4.5 Reduced Strategies 4.6 Subgame-Perfect Equilibrium (SPE) 4.7 Commitment Games 4.8 Further Reading 4.9 Exercises for Chapter 4 5 Expected Utility 5.1 Prerequisites and Learning Outcomes 5.2 Summary 5.3 Decisions Under Risk 5.4 Preferences for Lotteries 5.5 Ordinal Preferences for Decisions Under Certainty 5.6 Cardinal Utility Functions and Simple Lotteries 5.7 Consistency Axioms 5.8 Existence of an Expected-Utility Function 5.9 Risk Aversion 5.10 Discussion and Further Reading 5.11 Exercises for Chapter 5 6 Mixed Equilibrium 6.1 Prerequisites and Learning Objectives 6.2 Compliance Inspections 6.3 Bimatrix Games 6.4 The Best-Response Condition 6.5 Existence of Mixed Equilibria 6.6 Finding Mixed Equilibria in Small Games 6.7 The Upper-Envelope Method 6.8 Degenerate Games 6.9 Further Reading 6.10 Exercises for Chapter 6 7 Brouwer’s Fixed-Point Theorem 7.1 Prerequisites and Learning Outcomes 7.2 Labels 7.3 Simplices and Triangulations 7.4 Sperner’s Lemma 7.5 The Knaster–Kuratowski–Mazurkiewicz Lemma 7.6 Brouwer’s Fixed-Point Theorem on a General Compact Convex Set 7.7 The Freudenthal Triangulation 7.8 Further Reading 7.9 Exercises for Chapter 7 8 Zero-Sum Games 8.1 Prerequisites and Learning Outcomes 8.2 Example: Soccer Penalty 8.3 Max-Min and Min-Max Strategies 8.4 A Short Proof of the Minimax Theorem 8.5 Further Notes on Zero-Sum Games 8.6 Further Reading 8.7 Exercises for Chapter 8 9 Geometry of Equilibria in Bimatrix Games 9.1 Prerequisites and Learning Outcomes 9.2 Labeled Best-Response Regions 9.3 The Lemke–Howson Algorithm 9.4 Using Best-Response Diagrams 9.5 Strategic Equivalence 9.6 Best-Response Polyhedra and Polytopes 9.7 Complementary Pivoting 9.8 Degeneracy Resolution 9.9 Further Reading 9.10 Exercises for Chapter 9 10 Game Trees with Imperfect Information 10.1 Prerequisites and Learning Outcomes 10.2 Information Sets 10.3 Extensive Games 10.4 Strategies for Extensive Games and the Strategic Form 10.5 Reduced Strategies 10.6 Perfect Recall 10.7 Behavior Strategies 10.8 Kuhn’s Theorem: Behavior Strategies Suffice 10.9 Behavior Strategies in the Monty Hall Problem 10.10 Subgames and Subgame-Perfect Equilibria 10.11 Further Reading 10.12 Exercises for Chapter 10 11 Bargaining 11.1 Prerequisites and Learning Outcomes 11.2 Bargaining Sets 11.3 Bargaining Axioms 11.4 The Nash Bargaining Solution 11.5 Geometry of the Bargaining Solution 11.6 Splitting a Unit Pie 11.7 The Ultimatum Game 11.8 Alternating Offers Over Two Rounds 11.9 Alternating Offers Over Several Rounds 11.10 Stationary Strategies 11.11 The Nash Bargaining Solution Via Alternating Offers 11.12 Further Reading 11.13 Exercises for Chapter 11 12 Correlated Equilibrium 12.1 Prerequisites and Learning Outcomes 12.2 Examples of Correlated Equilibria 12.3 Incentive Constraints 12.4 Coarse Correlated Equilibrium 12.5 Existence of a Correlated Equilibrium 12.6 Further Reading 12.7 Exercises for Chapter 12 References Index "This book is an introduction to the mathematics of non-cooperative game theory. Each concept is explained in detail, starting from a main example, with a slowpaced proof of each theorem. The book has been designed and tested for self-study, and as an undergraduate course text with core chapters and optional chapters for different audiences. It has been developed over 15 years for a one-semester course on game theory at the London School of Economics and the distance learning program of the University of London, attended each year by about 200 third-year students in mathematics, economics, management, and other degrees. After studying this book, a student who started from first-year mathematics (the basics of linear algebra, analysis, and probability) will have a solid understanding of the most important concepts and theorems of non-cooperative game theory"-- Provided by publisher Game theory analyzes interaction - of internet users, competing firms, or cancer cells. This text explains the mathematical basics of game theory from the ground up, and introduces all-important results on non-cooperative games. With detailed explanations, examples, exercises, and pictures, it is designed for self-study or course accompaniment.