View source for Algorithmic Mechanism Design

'''Algorithmic mechanism design''' is the intersection of [[Mechanism Design|mechanism design]] and [[Computational Complexity Theory|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|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.

See also: [[Mechanism Design|mechanism design]], [[Revelation Principle|revelation principle]], [[Computational Complexity Theory|computational complexity]], [[Auction Theory|auction theory]], [[Combinatorial Auction|combinatorial auction]]

[[Category:Economics]]
[[Category:Computer Science]]
[[Category:Systems]]