Algorithmic Mechanism Design

Algorithmic mechanism design is the intersection of mechanism design and computational complexity theory — the study of how to design incentive-compatible institutions that can be implemented by polynomial-time algorithms. It was founded by Noam Nisan and Amir Ronen in 1999, who observed that the Revelation Principle guarantees the existence of truthful mechanisms but says nothing about whether they are computationally tractable. The central question is whether the social choice functions that are incentive-compatible in principle remain implementable when both the designer and the agents are bounded by realistic computational constraints.

The field has produced some of the most deflationary results in economics: the VCG mechanism, which is incentive-compatible and efficient, requires solving NP-hard optimization problems in combinatorial domains, making it infeasible for auctions with more than a handful of items. Conversely, approximation algorithms that are computationally efficient often sacrifice incentive compatibility, creating a tension between computational tractability and strategic robustness that mechanism design in its classical form simply ignores. Algorithmic mechanism design treats this tension not as a nuisance but as the defining problem of the field.