Algorithmic mechanism design: Difference between revisions

Revision as of 06:18, 26 June 2019

Latest revision as of 00:56, 15 July 2025

(14 intermediate revisions by 12 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 selfishself-interested participants, such that the participants' selfishself-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]].

==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

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

| last2 = Ronen | first2 = Amir

| journaltitle = Proceedings of the Thirtythirty-first Annualannual ACM Symposiumsymposium 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>

| pages = 129–140

| title = Algorithmic mechanism design

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

==See also==

Line 26 ⟶ 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

| archive-date = June 13, 2015

| url-status = dead

}}.

[[Category:Game theory]]

[[Category:Mechanism design]]

[[Category:Game theoryAlgorithms]]