Algorithmic game theory: Difference between revisions

Revision as of 15:39, 6 April 2021

Revision as of 17:28, 20 April 2021

Line 1:

{{essay-like|date=August 2013}}

'''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 [[Strategy (game theory)|strategic]] environments.

Typically, in Algorithmic Game Theory problems, the input to a given algorithm is distributed among many players who have a personal interest in the output. In those situations, the [[agent (economics)|agent]]s might not report the input truthfully because of their own personal interests. We can see Algorithmic Game Theory from two perspectives:

* ''Analysis'': look atgiven the currentcurrently implemented algorithms and, analyze them using Game Theory tools: (e.g., calculate and prove properties on their [[Nash equilibria]], [[price of anarchy]], and best-response dynamics ...)

* ''Design'': design games that have both good game-theoretical and algorithmic properties. This area is called [[algorithmic mechanism design]].

On top of the usual requirements in classical algorithm design (e.g., say ''polynomial-time running time'', ''good approximation ratio),'', ... the designer must also care about incentive constraints.

==History==

Line 39:

{{main|Price of Anarchy}}

The other two papers cited in the 2012 Gödel Prize for fundamental contributions to Algorithmic Game Theory introduced and developed the concept of "Price of Anarchy".

In their 1999 paper "Worst-case Equilibria",<ref name = "kp">{{Cite journal|title=Worst-case Equilibria|first1=Elias|last1=Koutsoupias|first2=Christos|last2=Papadimitriou|journal=Computer Science Review|volume=3|issue=2|date=May 2009|pages=65–69|url=http://www.cs.berkeley.edu/~christos/nash.ps|doi=10.1016/j.cosrev.2009.04.003|access-date=2018-01-08|archive-url=https://web.archive.org/web/20160313023635/http://www.cs.berkeley.edu/~christos/nash.ps|archive-date=2016-03-13|url-status=dead}}</ref> Koutsoupias and [[Christos Papadimitriou|Papadimitriou]] proposed a new measure of the degradation of system efficiency due to the selfish behavior of its agents: the ratio of between system efficiency at an optimal configuration, and its efficiency at the worst Nash equilibrium. (The term "Price of Anarchy" only appeared a couple of years later.<ref>{{citation

(The term "Price of Anarchy" only appeared a couple of years later.<ref>{{citation

| last = Papadimitriou | first = Christos | author-link = Christos Papadimitriou

| contribution = Algorithms, games, and the Internet