Game Theory Explained A Mathematical Introduction with Optimization (Christopher Griffin) (Z-Library)

Game Theory A Mathematical Introduction with Optimization Explained

This page intentionally left blank

Christopher Griffin Pennsylvania State University, USA Game Theory A Mathematical Introduction with Optimization Explained NEW JERSEY • LONDON • SINGAPORE • GENEVA • BEIJING • SHANGHAI • TAIPEI • CHENNAI

Published by World Scientific Publishing Co. Pte. Ltd. 5 Toh Tuck Link, Singapore 596224 USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601 UK office: 57 Shelton Street, Covent Garden, London WC2H 9HE Library of Congress Cataloging-in-Publication Data Names: Griffin, Christopher, 1979- author. Title: Game theory explained : a mathematical introduction with optimization / Christopher Griffin, Pennsylvania State University, USA. Description: New Jersey : World Scientific, [2025] | Includes bibliographical references and index. Identifiers: LCCN 2024035441 | ISBN 9789811297212 (hardcover) | ISBN 9789819812875 (paperback) | ISBN 9789811297229 (ebook for institutions) | ISBN 9789811297236 (ebook for individuals) Subjects: LCSH: Game theory. | Mathematical optimization. Classification: LCC QA269 .G75 2025 | DDC 519.3--dc23/eng/20241226 LC record available at https://lccn.loc.gov/2024035441 British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library. Copyright © 2025 by World Scientific Publishing Co. Pte. Ltd. All rights reserved. This book, or parts thereof, may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the publisher. For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher. For any available supplementary material, please visit https://www.worldscientific.com/worldscibooks/10.1142/13962#t=suppl Desk Editors: Nambirajan Karuppiah/Rosie Williamson Typeset by Stallion Press Email: enquiries@stallionpress.com Printed in Singapore

This book is dedicated to Beverly Leech (Kate Monday), Joe Howard (George Frankly), and Toni DiBuono (Pat Tuesday) of Mathnet and every person who made Square One TV possible when I was a kid. Without you, this book would not exist.

This page intentionally left blank

Preface Why did I write this book? This book started in 2010 as a series of lecture notes called “Game Theory: Penn State Math 486 Lecture Notes.” Game theory was the second course I ever taught, and I wrote the notes during a cold State College winter. People always ask me, “Why do you write such detailed lecture notes?” And I always tell them, “Sheer terror!” As a young faculty member, one is always worried about something, and I figured if I had a well-prepared set of typed lecture notes, the chances of me making a bone-headed mistake in class would be minimized. When I started the class, I had intended to use Luce and Raiffa’s book [1], with elements of Morris’ book [2] added for good measure. But the further I got into the class, the more I realized I wanted to cover the material in a way that emphasized the connection to other parts of mathematics, especially optimization. Nisan, Roughgarden, Tardos, and Vazirani had published their book, Algorithmic Game Theory [3], a few years earlier, and there was a sudden emphasis on finding equilibria in games algorithmically. I was aware of the work from the 1960s on using optimization methods to find Nash equilibria; consequently, a rather unique course was born that emphasized both classical results from game theory and interesting results from optimization theory. The material was aimed squarely at undergraduates and (in my opinion) provided a deep but not impenetrable introduction to the mathematics of games that is often missing at the undergraduate level. When I taught at the United States Naval Academy for a few years, I developed a course on “Computational Game Theory,” vii

viii Game Theory Explained: A Mathematical Introduction with Optimization where I continued to polish and refine the lecture notes. Finally, during the COVID-19 pandemic, a very nice editor named Rochelle from World Scientific contacted me and asked if I’d be willing to turn some of my notes into a book. I started with my notes on graph the- ory, and the result was my first book, Applied Graph Theory. With that project finished, I was finally ready to turn my notes on game theory into a book, and the result is this text. Between you and me, I’m glad I wrote this one second. The graph theory notes were more mature and easier to convert; I had found my voice (for the most part). Writing this book has been a bit like taking a trip down mem- ory lane to a time when I was less confident in myself as a teacher and had not yet found my voice as a writer. Frankly, parts of the process were painful, but I’m reasonably pleased with the outcome. I will give you a fair warning: There are parts of this book that are dense. I don’t like the “fluffy” approach to game theory, and I feel that such an approach hides too much of the beautiful intricacies of the subject and its deeper connections to the mathematical world. That being said, I’ve included plenty of examples and worked prob- lems so that the density is broken up by practical applications of game theory, along with some mathematical interludes that I hope you enjoy. How could you use this book? This book can be used entirely for self-study or in a classroom. I’ve had e-mails from all around the world saying that people have used the lecture note form for self- study, so it is possible. The book is really designed for a one-semester course and is geared toward undergraduates who have familiarity with differential vector calculus and matrices. The book emphasizes the proofs. However, many of these can be skipped on a first reading, though you will lose something if you skip too many of them. Almost all the proofs are derivations, though a few are by contradiction. So, while a “proofs class” is not needed, it won’t hurt. The book is organized into three parts and written in a “theorem- proof-example” style. There are remarks throughout and chapter notes that try to emphasize some history or other examples. Part 1 covers classical game theory, including games against the house (casino games) and utility theory. Part 2 covers the relationship between game theory and optimization. Part 3 covers cooperative game theory. There is an appendix that introduces evolutionary

Preface ix game theory by way of replicator dynamics. I used this material just after the pandemic, when we were running a week ahead of schedule in the course. In general, I favor a separate class on evolu- tionary games rather than wedging it into a course on game theory. Of course, part of my research focuses on evolutionary game theory, so I would say that. Each part emphasizes not only the results but also the proofs along with examples. A nice feature of the book is the relationship between Nash bargaining theory and multi-criteria optimization, which (as far as I know) is not covered in any other book. Sample curriculum paths are shown in the following figure. 1 2 3 4 5 6 7 8 9 10 A B Replicator Dynamics C Classical Game Theory Game Theory & Optimization Cooperative Game Theory Prerequisite Appendices Extra Material Appendix Classic route: The first time I taught this course, I went from Chapter 1 to Chapter 10, with limited information coming from the appendices. This is by far the easiest way to teach the course and gives a thorough understanding of classical game theory and its rela- tionship to optimization. The material on optimization and probabil- ity is self-contained, so there is no need to use an external resource, unless so desired. It has been my experience that students like the material on games against the house in Chapter 1, which helps offset the formal introduction to probability that it provides. Skip utility theory: When I taught game theory in 2021, I decided to skip Chapter 2. I like the material in it, but the students often find it a little dry. It is perfectly fine to skip Chapter 2 and go from Chapter 1 to Chapter 3. In this case, one could proceed at a slower pace and really emphasize all the proofs in the book or include Appendix C on evolutionary game theory, which is self-contained enough that students don’t need to have seen differential equa- tions (though it would help). In 2021, we covered the material in Appendix C and did most of the proofs.

x Game Theory Explained: A Mathematical Introduction with Optimization Skip Chapters 1, 2 and (parts of) 3: I’ve never done this because the students like the games in Chapter 1, but it is possi- ble to skip Chapters 1 and 2, assuming that the students are familiar enough with probability theory. In that case, Chapter 3 could be con- densed to just the material on game trees that do not include games of chance. (Essentially, you’re skipping poker.) It’s also possible to skip all of Chapter 3 and start immediately at Chapter 4 with normal form games. I would only do this if I wanted to really emphasize the proofs or review the material on calculus and matrices thoroughly. You would probably have to include Appendix C to make a 15-week course, though this could work in a 10-week term. How do you handle optimization? The book is sensitive to the fact that optimization can be a niche interest in some math departments. Consequently, all the material on optimization is self- contained, including the coverage of the Karush–Kuhn–Tucker con- ditions. Penn State has no math course that covers these as a prereq- uisite for the game theory class, and students had no problems with them. Appendices A and B can also be used to help bring students up to speed on elements of matrix arithmetic and calculus that they may have forgotten or missed. My favorite aspect of the book is the connection between games and optimization, especially the connection between optimization and cooperative games, which, I think, is wholly underemphasized. The quadratic programming method for finding Nash equilibria in general-sum bimatrix games is not the most “modern” way to solve such problems, but it is both understandable to undergraduates and can be performed on a computer algebra system. Moreover, it pro- vides critical mathematical foundations for more advanced study in game theory, using, for example, the book by González-Dı́az, Garćıa- Jurado, and Fiestras-Janeiro [4]. What isn’t in this book? Since this is geared toward a one- semester class, there are several omissions. There is no mention of dynamic or differential games, unless you consider multi-layered game trees to be a form of dynamic game, which I do not. Likewise, iterated games are not covered because they could form an entire text on their own. Cooperative game theory of the kind studied deeply in economics is only introduced in Chapter 10. It is not a feature of the book. Evolutionary game theory is covered in Appendix C.

Preface xi As this is one of my main areas of research, I would prefer a separate treatment of the subject. However, the material on the replicator is both exciting and produces nice pictures, so it is worth putting into an appendix as “bonus material” to be used as needed. Formal treat- ment of evolutionarily stable strategies (ESS) is explicitly omitted. ESS are subtle, and in my experience, the students hate it. When presented poorly, it is literally a way to turn students off from evo- lutionary games. Explicit optimization algorithms such as the simplex algorithm are not presented. Instead, I show how to solve optimization problems with a computer. For those readers interested in understanding the methods used by the computer for solving the optimization problems that arise in this book, there are ample references.

This page intentionally left blank

Acknowledgements This book was created with LATEX2e using Overleaf, TeXShop, BibDesk, and the grammar checker LanguageTool. Figures were cre- ated using MathematicaTM and OmnigraffleTM, unless otherwise noted. In acknowledging those people who helped make this work possible, first let me say thank you to all the other scholars who have worked in game theory. Without your pioneering work, there would be nothing to write about. Also, I must thank individuals who found typos in my original lecture notes and wrote to tell me about them: James Fan, George Kesidis, Nicolas Aumar, Arlan Stutler, and Sarthak Shah. I would also like to thank Volmir Eugênio Wilhelm, who selflessly translated a version of my game theory lecture notes into Spanish. If there is anyone else I have forgotten, I apologize, but your contributions are appreciated. I would very much like to thank Andrew Belmonte, at Penn State, for encouraging me to turn my notes into a book, even though I ignored him for 14 years. Finally, I owe a debt to Rochelle Kronzek Miller of World Scientific, who gave me the final push to write this, and to my desk editor, Rosie Williamson, and her editorial staff, who dealt with the mechanics of getting this published. Thank you all. xiii

This page intentionally left blank

About the Author Christopher Griffin is a Research Professor at the Applied Research Laboratory (ARL), where he holds a courtesy appointment as Professor of Mathematics at Penn State. He was a Eugene Wigner Fellow in the Computational Science and Engineering Division of the Oak Ridge National Laboratory and has also taught in the Mathematics Department at the United States Naval Academy. His favorite part of teaching is connecting complex mathematical concepts to their applications. He finds most students are excited by math when they know how much of our modern world depends on it. When he is not teaching (which is most of the time), Dr. Griffin’s research interests are in applied mathematics, where he focuses on applied dynamical systems (especially on graphs), game theory, and optimization. His research has been funded by the National Science Foundation, the Office of Naval Research, the Army Research Office, the Intelligence Advanced Research Projects Agency, and the Defense Advanced Research Projects Agency. He has published over 100 peer- reviewed research papers in various forms of applied mathematics. His book, Applied Graph Theory: An Introduction with Graph Opti- mization and Algebraic Graph Theory, was also published by World Scientific in 2023. xv

This page intentionally left blank

Contents Preface vii Acknowledgements xiii About the Author xv Part 1: Classical Game Theory 1 1. Games Against the House with an Introduction to Probability Theory 3 1.1 Probability . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Random Variables and Expected Values . . . . . . 8 1.3 Some Specialized Results on Probability . . . . . . 12 1.4 Conditional Probability . . . . . . . . . . . . . . . . 15 1.5 Independence . . . . . . . . . . . . . . . . . . . . . 18 1.6 Blackjack: A Game of Conditional Probability . . . 19 1.7 The Monty Hall Problem and Decision Trees . . . . 22 1.8 Bayes’ Theorem . . . . . . . . . . . . . . . . . . . . 25 1.9 Chapter Notes . . . . . . . . . . . . . . . . . . . . . 27 1.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . 29 2. Elementary Utility Theory 33 2.1 Decision-Making Under Certainty . . . . . . . . . . 33 2.2 Preference and the von Neumann–Morgenstern Assumptions . . . . . . . . . . . . . . . . . . . . . . 35 2.3 Expected Utility Theorem . . . . . . . . . . . . . . 40 2.4 Chapter Notes . . . . . . . . . . . . . . . . . . . . . 46 2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . 48 xvii

xviii Game Theory Explained: A Mathematical Introduction with Optimization 3. Game Trees and Extensive Form 51 3.1 Graphs and Trees . . . . . . . . . . . . . . . . . . . 51 3.2 Game Trees with Complete Information and No Chance . . . . . . . . . . . . . . . . . . . . 56 3.3 Game Trees with Incomplete Information . . . . . . 61 3.4 Games of Chance . . . . . . . . . . . . . . . . . . . 65 3.5 Payoff Functions and Equilibria . . . . . . . . . . . 66 3.6 Chapter Notes . . . . . . . . . . . . . . . . . . . . . 81 3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . 82 4. Games and Matrices: Normal and Strategic Forms 87 4.1 Normal and Strategic Forms . . . . . . . . . . . . . 87 4.2 Strategic-Form Games . . . . . . . . . . . . . . . . 89 4.3 Strategy Vectors and Matrix Games . . . . . . . . . 93 4.4 Chapter Notes . . . . . . . . . . . . . . . . . . . . . 95 4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . 96 5. Saddle Points, Mixed Strategies, and Nash Equilibria 97 5.1 Equilibria in Zero-Sum Games: Saddle Points . . . 98 5.2 Zero-Sum Games without Saddle Points . . . . . . 103 5.3 Mixed Strategies . . . . . . . . . . . . . . . . . . . . 105 5.4 Dominated Strategies and Nash Equilibria . . . . . 111 5.5 The Indifference Theorem . . . . . . . . . . . . . . 117 5.6 The Minimax Theorem . . . . . . . . . . . . . . . . 120 5.7 Existence of Nash Equilibria . . . . . . . . . . . . . 125 5.8 Finding Nash Equilibria in Simple Games . . . . . 127 5.9 Nash Equilibria in General-Sum Games . . . . . . . 131 5.10 Chapter Notes . . . . . . . . . . . . . . . . . . . . . 134 5.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . 135 Part 2: Optimization and Game Theory 137 6. An Introduction to Optimization and the Karush–Kuhn–Tucker Conditions 139 6.1 Motivating Example . . . . . . . . . . . . . . . . . 139 6.2 A General Maximization Formulation . . . . . . . . 141

Contents xix 6.3 Gradients, Constraints, and Optimization . . . . . 143 6.4 Convex Sets and Combinations . . . . . . . . . . . 145 6.5 Convex and Concave Functions . . . . . . . . . . . 147 6.6 Karush–Kuhn–Tucker Conditions . . . . . . . . . . 149 6.7 Relating Back to Game Theory . . . . . . . . . . . 154 6.8 Chapter Notes . . . . . . . . . . . . . . . . . . . . . 156 6.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . 157 7. Linear Programming and Zero-Sum Games 159 7.1 Linear Programs . . . . . . . . . . . . . . . . . . . . 160 7.2 Intuition on the Solution of Linear Programs . . . . 162 7.3 A Linear Program for Zero-Sum Game Players . . . 168 7.4 Solving Linear Programs Using a Computer . . . . 171 7.5 Standard Form, Slack and Surplus Variables . . . . 173 7.6 Optimality Conditions for Zero-Sum Games and Duality . . . . . . . . . . . . . . . . . . . . . . 175 7.7 Chapter Notes . . . . . . . . . . . . . . . . . . . . . 183 7.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . 184 8. Quadratic Programs and General-Sum Games 187 8.1 Introduction to Quadratic Programming . . . . . . 187 8.2 Solving Quadratic Programming Problems Using Computers . . . . . . . . . . . . . . . . . . . 188 8.3 General-Sum Games and Quadratic Programming . 189 8.4 Chapter Notes . . . . . . . . . . . . . . . . . . . . . 202 8.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . 204 Part 3: Cooperation in Game Theory 205 9. Nash’s Bargaining Problem and Cooperative Games 207 9.1 Payoff Regions in Two-Player Games . . . . . . . . 208 9.2 Collaboration and Multi-Criteria Optimization . . . 213 9.3 Nash’s Bargaining Axioms . . . . . . . . . . . . . . 217 9.4 Nash’s Bargaining Theorem . . . . . . . . . . . . . 219 9.5 Chapter Notes . . . . . . . . . . . . . . . . . . . . . 227 9.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . 228