Twenty Lectures on Algorithmic Game Theory

The extensive growth of computer networks over the past few decades has generated some fascinating puzzles to solve, such as the efficient routing of traffic over the Internet and the effective design of online auctions. What these and similar problems have in common is the existence of multiple interacting parties, each motivated by self-interest. Addressing these challenges involves economic issues of resource allocation and the creation of incentives for desirable outcomes, and this has has led to a fruitful interplay between the disciplines of economics, game theory, and computer science over the past few decades.

Tim Roughgarden’s Twenty Lectures on Algorithmic Game Theory is an ideal point of entry to the subject. As the title suggests, the book consists of twenty well-written, accessible chapters that introduce the key ideas of the field. It leads off with some motivating examples: in particular, Braess’s Paradox, which offers the counterintuitive result that adding a new road to a network of existing roads can actually result in an increase in the overall expected arrival time for drivers. Traffic flow on the network could be improved by an altruistic dictator making routing choices for all the drivers — the difference is referred to as the “price of anarchy” (POA).

This opening chapter serves as introduction to a series of lectures discussing the relatively new discipline of “mechanism design”. Whereas traditional game theory is about the analysis of an existing strategic interaction, mechanism design is its dual: what are the rules and incentives that need to be in place between multiple parties to achieve a particular desirable outcome? The design of effective auctions are treated in some detail. For instance, ideally, we’d like auctions to be “dominant-strategy incentive compatible” (DSIC), which means that bidders have an incentive to offer up truthful bids. Can this ideal be achieved, even in complex auction scenarios?

We’re then treated to a handful of lectures that more deeply explore the concepts of equilibria in so-called “selfish routing” games in which a POA exists — among other results, we learn that over-provisioning in a network can be more effective than dictatorial control. Finally, the computation of equilibria in real-world games is not a trivial consideration, and the last lectures are devoted to the challenges associated with being able to do this in a tractable fashion — the well-known “Nash equilibrium” solution concept, for instance, can be computationally intractable for selfish routing games.

There are several features of this book that make it very well suited both for the classroom and for self-study. Each chapter has a section titled “The Upshot”, which reviews the key concepts presented, as well as exercises and problems (harder) for the reader. There are hints at the back of the book for many of these. And for those readers who want to see how all the pieces fit together, the author offers a “Top 10” list at the back of the book that highlights the key results over the twenty lectures. No background in game theory or economics is assumed, but the author suggests that mathematical maturity is a prerequisite, making this book more suitable for upper-division and beginning graduate courses.

There is no shortage of good books on the subject of game theory in general, but if your interest is in understanding how game theory, economics and computer science are cross-pollinating to address challenges of the design of online strategic interactions, this is the book to start with. It is clear, well-organized and makes a compelling introduction to a vibrant field.

David Burke leads the machine cognition research program at Galois, Inc., which investigates techniques for integrating human decision-making with machine intelligence (and vice versa). His research interests include techniques for reasoning under conditions of extreme uncertainty, game theory, and bio-inspired AI.