Algorithmic game theory: Difference between revisions

Revision as of 17:02, 5 December 2017

Revision as of 23:04, 8 January 2018

Line 1:

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

'''Algorithmic game theory''' is an area in the intersection of [[game theory]] and [[algorithmcomputer designscience]], whose objective is to understand and design 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 agents might not report the input truthfully because of their own personal interests. On top of the usual requirements in classical algorithm design, say ''polynomial-time running time'', ''good approximation ratio'', ... the designer must also care about incentive constraints. We can see Algorithmic Game Theory from two perspectives:

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

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

==History==

The field was started when Nisan and Ronen in STOC'99 <ref name="nr">{{citation

===Nisan-Ronen: a new framework for studying algorithms===

TheIn field1999, wasthe startedseminal whenpaper of [[Noam Nisan|Nisan]] and Ronen in STOC'99 <ref name="nr">{{citation

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

| last2 = Ronen | first2 = Amir

Line 18 ⟶ 21:

Following notions from the field of mechanism design, we suggest a framework for studying such algorithms. In this model the algorithmic solution is adorned with payments to the participants and is termed a mechanism. The payments should be carefully chosen as to motivate all participants to act as the algorithm designer wishes. We apply the standard tools of mechanism design to algorithmic problems and in particular to the shortest path problem.}}

This paper coined the term [[algorithmic mechanism design]] and was recognized by the 2012 [[Gödel Prize]] committee as one of "three papers laying foundation of growth in Algorithmic Game Theory".<ref>{{cite press release

==The Internet as a catalyst==

|author=<!--Staff writer(s); no by-line.-->

|title= ACM SIGACT Presents Gödel Prize for Research that Illuminated Effects of Selfish Internet Use

|url=http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012

|archive-url=https://web.archive.org/web/20130718154540/http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012

|___location= New York

|agency=Association for Computing Machinery

|archive-date=2012-05-26

|date=2012-05-16

|access-date=2018-01-08}}</ref>

===Price of Anarchy===

{{main article|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|first=Elias|last=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}}</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

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

| contribution = Algorithms, games, and the Internet

| doi = 10.1145/380752.380883

| pages = 749--753

| title = Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC '01)

| year = 2001}}</ref>)

===The Internet as a catalyst===

The Internet created a new economy—both as a foundation for exchange and commerce, and in its own right. The computational nature of the Internet allowed for the use of computational tools in this new emerging economy. On the other hand, the Internet itself is the outcome of actions of many. This was new to the classic, ‘top-down’ approach to computation that held till then. Thus, game theory is a natural way to view the Internet and interactions within it, both human and mechanical.