algorithmic mechanism design
   HOME

TheInfoList



OR:

Algorithmic mechanism design (AMD) lies at the intersection of economic
game theory Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
,
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
, and
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
. The prototypical problem in
mechanism design Mechanism design is a field in economics and game theory that takes an objectives-first approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally. Because it starts a ...
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 Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...
, such as
worst case analysis Worst case analysis was, from 1978 until 1986, a doctrine under which mandated that an environmental impact statement include such an analysis: It led to a 1989 SCOTUS decision, written by John Paul Stevens and reported in ''Robertson v. Methow ...
and
approximation ratio An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...
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 A Vickrey–Clarke–Groves (VCG) auction is a type of sealed-bid auction of multiple items. Bidders submit bids that report their valuations for the items, without knowing the bids of the other bidders. The auction system assigns the items in a ...
.


History

Noam Nisan Noam Nisan ( he, נעם ניסן; born June 20, 1961) is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game th ...
and Amir Ronen, from the
Hebrew University of Jerusalem The Hebrew University of Jerusalem (HUJI; he, הַאוּנִיבֶרְסִיטָה הַעִבְרִית בִּירוּשָׁלַיִם) is a public research university based in Jerusalem, Israel. Co-founded by Albert Einstein and Dr. Chaim Weiz ...
, first coined "Algorithmic mechanism design" in a research paper published in 1999..


See also

*
Algorithmic game theory Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments. Typically, in Algorithmic Game Theory problems, the input t ...
*
Computational social choice Computational social choice is a field at the intersection of social choice theory, theoretical computer science, and the analysis of multi-agent systems. It consists of the analysis of problems arising from the aggregation of preferences of a gr ...
*
Metagame Metagame, Hypergame, or game about the game, is an approach to a game that transcends or operates outside of the prescribed rules of the game, uses external factors to affect the game, or goes beyond the supposed limits or environment set by th ...
*
Incentive compatible A mechanism is called incentive-compatible (IC) if every participant can achieve the best outcome to themselves just by acting according to their true preferences. There are several different degrees of incentive-compatibility: * The stronger ...
*
Vickrey–Clarke–Groves mechanism In mechanism design, a Vickrey–Clarke–Groves (VCG) mechanism is a generic truthful mechanism for achieving a socially-optimal solution. It is a generalization of a Vickrey–Clarke–Groves auction. A VCG auction performs a specific task: divid ...


References and notes


Further reading

* *{{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 . Game theory Mechanism design Algorithms