Abstract
Computer science and economics have engaged in a lively interaction over the past fifteen years, resulting in the new field of algorithmic game theory. Many problems that are central to modern computer science, ranging from resource allocation in large networks to online advertising, involve interactions between multiple self-interested parties. Economics and game theory offer a host of useful models and definitions to reason about such problems. The flow of ideas also travels in the other direction, and concepts from computer science are increasingly important in economics. This book grew out of the author's Stanford University course on algorithmic game theory, and aims to give students and other newcomers a quick and accessible introduction to many of the most important concepts in the field. The book also includes case studies on online advertising, wireless spectrum auctions, kidney exchange, and network management.
Introduction: The Bridge Between Economics and Computation
Algorithmic Game Theory (AGT) serves as the essential bridge between economic incentives and computational systems. In any complex system with "strategic participants"—whether they are drivers on a highway, bidders in an ad auction, or athletes in a tournament—individuals will act to maximize their own utility. This reality presents a fundamental challenge: how can we ensure that individual self-interest aligns with collective efficiency?
This field addresses three core challenges. First, Mechanism Design focuses on engineering the "rules of the game" to prevent participants from gaming the system. Second, the Price of Anarchy (POA) quantifies the performance loss incurred when we allow selfish behavior instead of imposing a central, optimal plan. Finally, Computational Complexity questions whether mathematically stable states, or equilibria, are even reachable by real-world participants in a reasonable amount of time.
Mechanism Design and the 2012 Olympic Scandal
A primary goal of AGT is to design systems where the "honest" or "optimal" behavior is also the most beneficial for the individual. The 2012 Olympic badminton tournament serves as a cautionary tale of a mechanism design failure. Due to a flawed tournament structure—a round-robin stage followed by specific knockout pairings—several teams realized that losing their final group match would actually secure them a more favorable opponent in the next round.
As shown in the bracket above, the path for a "loser" could lead to a different quadrant of the tournament. This created a perverse incentive where athletes actively tried to lose, leading to disqualifications and a public relations disaster. This was not a failure of athlete ethics, but a failure of rule-making. If a system allows a participant to benefit by acting "badly," the burden of failure lies with the designer.
Selfish Routing and Braess’s Paradox
The tension between individual choice and system efficiency is perhaps most visible in network routing. A common assumption is that adding capacity to a network—such as building a new road—will always improve travel times. However, Braess’s Paradox demonstrates that this is not always the case.
Consider the networks illustrated above. In the initial network (a), flow is split between the upper and lower paths, resulting in a travel time of 1.5 hours. In the augmented network (b), a "superfast" link with zero cost is added between nodes $v$ and $w$. Because every individual driver acts selfishly to minimize their own time, they all converge on the path $o \to v \to w \to d$. This collective behavior increases the total travel time to 2 hours for everyone.
This result allows us to quantify the Price of Anarchy (POA). In this specific example, the POA is $2 / 1.5 = 1.33$, meaning selfish routing is 33% slower than a centrally dictated optimal route. While this paradox is counter-intuitive, it is a universal phenomenon that can even be observed in physical systems, such as mechanical networks of strings and springs.
The Computational Complexity of Equilibria
While Nash’s Theorem guarantees that a stable equilibrium exists for any finite game, AGT introduces a critical computational caveat. If an equilibrium is too difficult to compute (falling into complex classes like PPAD), it loses its power as a credible prediction of real-world behavior. Real-world participants cannot be expected to reach a state that even the most powerful algorithms cannot find efficiently.
This "computational crisis" suggests that we must look beyond standard Nash equilibria toward more tractable alternatives, such as correlated and coarse correlated equilibria. In many practical domains, such as network routing with modest over-provisioning, the Price of Anarchy remains close to 1, suggesting that selfish behavior can be largely benign if the system is designed correctly.
Conclusion
Algorithmic Game Theory shifts the focus from judging participant behavior to evaluating system rules. By understanding the Price of Anarchy and the limits of computational tractability, designers can build more robust systems that harmonize individual incentives with the social good. Future work in the field continues to bridge the gap between mathematical equilibrium and the bounded rationality of human psychology.
Summary updated