Algorithmic mechanism design: Difference between revisions

Revision as of 23:56, 12 February 2019

Revision as of 14:09, 27 May 2019

Line 9:

| year = 1999| doi = 10.1145/301250.301287 | isbn = 978-1581130676 }}.</ref><ref name=journal_version>{{Cite journal|doi=10.1006/game.1999.0790|title=Algorithmic Mechanism Design|journal=Games and Economic Behavior|volume=35|issue=1–2|pages=166–196|year=2001|last1=Nisan|first1=Noam|last2=Ronen|first2=Amir}}</ref>

It combines ideas such as utility maximization and [[mechanism design]] from [[economics]], rationality and [[Nash equilibrium]] from game theory, with such concepts as [[complexity]] and algorithm design from [[discrete mathematics]] and theoretical [[computer science]]. Examples of topics include networking, [[peering]], online auctions and exchanges, online advertising, and search engine's page ranking.

Algorithmic mechanism design differs from classical economic mechanism design in several respects. It typically employs the analytic tools of [[theoretical computer science]], such as [[worst case analysis]] and [[approximation ratio]]s, in contrast to classical mechanism design in economics which often makes distributional assumptions about the agents. It also considers computational constraints to be of central importance: mechanisms that cannot be efficiently implemented in polynomial time are not considered to be viable solutions to a mechanism design problem. This often, for example, rules out the classic economic mechanism, the [[Vickrey–Clarke–Groves auction]].