Read the original document by opening this link in a new tab.
Table of Contents
Acknowledgements ix
Preface 1
An overview of the book 1
Part I: Analyzing games: Strategies and equilibria 1
Part II: Designing games and mechanisms 5
For the reader and instructor 8
Prerequisites 8
Courses 8
Notes 9
Part I: Analyzing games: Strategies and equilibria 11
Chapter 1. Combinatorial games 12
Chapter 2. Two-person zero-sum games 34
Chapter 3. Zero-sum games on graphs 55
Chapter 4. General-sum games 74
Chapter 5. Existence of Nash equilibria and fixed points 99
Chapter 6. Games in extensive form 114
Chapter 7. Evolutionary and correlated equilibria 137
Chapter 8. The price of anarchy 148
Chapter 9. Random-turn games 171
Part II: Designing games and mechanisms 179
Chapter 10. Stable matching and allocation 180
Chapter 11. Fair division 193
Chapter 12. Cooperative games 204
Chapter 13. Social choice and voting 216
Chapter 14. Auctions 233
Chapter 15. Truthful auctions in win/lose settings 267
Chapter 16. VCG and scoring rules 288
Chapter 17. Matching markets 299
Chapter 18. Adaptive decision making 312
Appendix A. Linear programming 333
Appendix B. Some useful probability tools 342
Appendix C. Convex functions 344
Appendix D. Solution sketches for selected exercises 348
Bibliography 359
Index 376
Summary
We live in a highly connected world, with multiple self-interested agents interacting, leading to myriad opportunities for conflict and cooperation. Understanding these is the goal of game theory. It finds application in fields such as economics, business, political science, biology, psychology, sociology, computer science, and engineering. In this book, we present an introduction to this field. We will see applications from a variety of disciplines and delve into some of the fascinating mathematics that underlies game theory. The book covers topics such as combinatorial games, two-person zero-sum games, general-sum games, existence of Nash equilibria, games in extensive form, evolutionary and correlated equilibria, the price of anarchy, random-turn games, stable matching and allocation, fair division, cooperative games, social choice and voting, auctions, truthful auctions in win/lose settings, VCG and scoring rules, matching markets, adaptive decision making, as well as appendices on linear programming, probability tools, convex functions, and solution sketches for selected exercises.