Algorithmic mechanism design: Difference between revisions

Revision as of 00:46, 5 June 2018

Latest revision as of 00:56, 15 July 2025

(18 intermediate revisions by 15 users not shown)

Line 1:

'''Algorithmic mechanism design''' ('''AMD''') lies at the intersection of economic [[game theory]], [[optimization]], and [[computer science]]. The prototypical problem in [[mechanism design]] is to design a system for multiple self-interested participants, such that the participants' self-interested actions at equilibrium lead to good system performance. Typical objectives studied include revenue maximization and social [[welfare maximization]]. 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 [[Time complexity|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]].

'''Algorithmic mechanism design (AMD)''' lies at the intersection of economic [[game theory]] and [[computer science]].

==History==

[[Noam Nisan]] and Amir Ronen, from the [[Hebrew University of Jerusalem]], first coined "Algorithmic mechanism design" in a research paper published in 1999.<ref name="nisan">{{citation

[[Noam Nisan]] and Amir Ronen, from the [[Hebrew University of Jerusalem]], first coined "Algorithmic mechanism design" in a research paper published in 1999.<ref name="nisan">{{citation

| last1 = Nisan | first1 = Noam | author1-link = Noam Nisan

| last2 = Ronen | first2 = Amir

| journaltitle = Proceedings of the thirty-first annual ACM symposium on Theory of computingComputing | chapter = Algorithmic mechanism design (Extended abstract) | pages = 129–140

| year = 1999| doi = 10.1145/301250.301287 | isbn = 978-1581130676 | doi-access = free}}.</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=166166–196|year=2001|last1=Nisan|first1=Noam|last2=Ronen|first2=Amir|citeseerx=10.1.1.16.7473}}</ref>

| pages = 129–140

| title = Algorithmic mechanism design

| url = http://dl.acm.org/citation.cfm?id=301287

| year = 1999}}.</ref><ref name=journal_version>{{Cite journal|doi=10.1006/game.1999.0790|title=Algorithmic Mechanism Design|journal=Games and Economic Behavior|volume=35|pages=166|year=2001|last1=Nisan|first1=Noam|last2=Ronen|first2=Amir}}</ref>

==See also==

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 game theory]]

*[[Computational social choice]]

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]].

*[[Metagame]]

*[[Incentive compatible]]

*[[Vickrey–Clarke–Groves mechanism]]

==References and notes==

Line 20 ⟶ 22:

*{{Cite Algorithmic Game Theory 2007}}

*{{citation

| last1 = Dütting
| first1 = Paul

| last2 = Geiger
| first2 = Andreas

| date = May 9, 2007

| publisher = University of Karlsruhe, Fakultät für Informatik

| series = Seminar Report

| title = Algorithmic Mechanism Design

| url = http://www.cs.uu.nl/docs/vakken/msagi/mech_design.pdf}}.

| access-date = June 11, 2015

| archive-url = https://web.archive.org/web/20150613164748/http://www.cs.uu.nl/docs/vakken/msagi/mech_design.pdf

==See also==

| archive-date = June 13, 2015

*[[Algorithmic game theory]]

| url-status = dead

*[[Computational social choice]]

}}.

*[[Game theory]]

*[[Mechanism design]]

*[[Metagame]]

*[[Incentive compatible]]

*[[Vickrey–Clarke–Groves mechanism]]

[[Category:Game theory]]

[[Category:Mechanism design]]

[[Category:Game theoryAlgorithms]]