Game Theory, Alive

We live in a highly connected world with multiple self-interested agents interacting and myriad opportunities for conflict and cooperation. The goal of game theory is to understand these opportunities. This book presents a rigorous introduction to the mathematics of game theory without losing sight of the joy of the subject. This is done by focusing on theoretical highlights (e.g., at least six Nobel Prize winning results are developed from scratch) and by presenting exciting connections of game theory to other fields such as computer science (algorithmic game theory), economics (auctions and matching markets), social choice (voting theory), biology (signaling and evolutionary stability), and learning theory. Both classical topics, such as zero-sum games, and modern topics, such as sponsored search auctions, are covered. Along the way, beautiful mathematical tools used in game theory are introduced, including convexity, fixed-point theorems, and probabilistic arguments. The book is appropriate for a first course in game theory at either the undergraduate or graduate level, whether in mathematics, economics, computer science, engineering, or statistics. The importance of game-theoretic thinking transcends the academic setting-for every action we take, we must consider not only its direct effects, but also how it influences the incentives of others.

Table of Contents

Part I: Analyzing games: Strategies and equilibria

Chapter 1. Combinatorial games

Chapter 2. Two-person zero-sum games

Chapter 3. Zero-sum games on graphs

Chapter 4. General-sum games

Chapter 5. Existence of Nash equilibria and fixed points

Chapter 6. Games in extensive form

Chapter 7. Evolutionary and correlated equilibria

Chapter 8. The price of anarchy

Chapter 9. Random-turn games

Part II: Designing games and mechanisms

Chapter 10. Stable matching and allocation

Chapter 11. Fair division

Chapter 12. Cooperative games

Chapter 13. Social choice and voting

Chapter 14. Auctions

Chapter 15. Truthful auctions in win/lose settings

Chapter 16. VCG and scoring rules

Chapter 17. Matching markets

Chapter 18. Adaptive decision making

Appendix A. Linear programming

Appendix B. Some useful probability tools

Appendix C. Convex functions

Appendix D. Solution sketches for selected exercises

Review

Game theory’s influence is felt in a wide range of disciplines, and the authors deliver masterfully on the challenge of presenting both the breadth and coherence of its underlying world-view. The book achieves a remarkable synthesis, introducing the reader to the blend of economic insight, mathematical elegance, scientific impact, and counter-intuitive punch that characterizes game theory as a field. –Jon Kleinberg, Cornell University, 2006 Nevanlinna Prize winner

A game theory textbook by people who love … games! It covers many classic as well as recent topics of game theory. Its rigorous treatment, interspersed with illuminating examples, makes it a challenging pleasure to read. –Sergiu Hart, The Hebrew University of Jerusalem

This beautifully written book introduces the reader to the rich and flourishing subject of game theory. From an exhaustive account of basics of the classical theory to a wide range of modern themes including auctions, matching markets, sequential decision making the book presents a great variety of topics in a rigorous yet entertaining manner. The authors guide the reader through the intricacies of game theory with an exquisite mathematical elegance. For anyone interested in the topic, experts and beginners alike, this book is a must. –Gábor Lugosi, Pompeu Fabra University, Barcelona, Spain

About the Authors

Anna R. Karlin, University of Washington, Seattle, WA.

Yuval Peres, Microsoft Research, Redmond, WA.