Algorithmic mechanism design: Difference between revisions

Revision as of 19:43, 1 May 2020

Latest revision as of 00:56, 15 July 2025

(11 intermediate revisions by 10 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]].

==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 41 ⟶ 37:

}}.

[[Category:Game theory]]

[[Category:Mechanism design]]

[[Category:Algorithms]]