Algorithmic mechanism design: Difference between revisions

Revision as of 05:29, 5 January 2010

Latest revision as of 00:56, 15 July 2025

(39 intermediate revisions by 29 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 2001.<ref name="nisan">{{cite journal|url=http://iew3.technion.ac.il/~amirr/AMDJ.pdf|title=Algorithmic mechanism design|first=Noam|last=Nisan|coauthors=Amir Ronen|journal=Games and Economic Behavior|year=2001|issue=35|pages=166–196}}</ref>

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

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.

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

| last2 = Ronen | first2 = Amir

| title = Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 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=166–196|year=2001|last1=Nisan|first1=Noam|last2=Ronen|first2=Amir|citeseerx=10.1.1.16.7473}}</ref>

==See also==

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

*[[GameAlgorithmic game theory]]

*[[Computational social choice]]

*[[Metagame]]

*[[Incentive compatible]]

*[[Vickrey–Clarke–Groves mechanism]]

==References and notes==

Line 11 ⟶ 20:

==Further reading==

*{{Cite Algorithmic Game Theory 2007}}

*{{cite book |author=Vijay V. Vazirani; Nisan, Noam; Tim Roughgarden; Éva Tardos |title=Algorithmic Game Theory |publisher=Cambridge University Press |___location=Cambridge, UK |year= 2007|pages= |isbn=0-521-87282-0}} Available for [http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf download (PDF)]

*{{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

| archive-date = June 13, 2015

| url-status = dead

}}.

==External links==

*[http://iew3.technion.ac.il/~amirr/AMDJ.pdf] Algorithmic mechanism design

*[http://www.rainsoft.de/publications/mech_design.pdf] Algorithmic Mechanism Design

*[http://video.google.com/videoplay?docid=6121409064231775355] Noam Nisan discussing algorithmic mechanism design

==See also==

*[[Game theory]]

*[[Mechanism design]]

*[[Metagame]]

*[[Incentive compatible]]

[[Category:Game theory]]

[[Category:Mechanism design]]

[[Category:Game theoryAlgorithms]]

[[de:Algorithmische Spieltheorie]]