Algorithmic game theory: Difference between revisions

Revision as of 12:30, 23 July 2019

Revision as of 23:30, 27 August 2019

Line 1:

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

'''Algorithmic game theory''' 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 (grammar)|agent]]s might not report the input truthfully because of their own personal interests. We can see Algorithmic Game Theory from two perspectives:

Line 7:

* ''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, say ''polynomial-time running time'', ''good approximation ratio'', ... the designer must also care about incentive constraints.

==History==

Line 37:

===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|doi=10.1016/j.cosrev.2009.04.003}}</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.

Line 47:

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

| year = 2001| isbn = 978-1581133493 | citeseerx = 10.1.1.70.8836 }}</ref>)

===The Internet as a catalyst===

Line 63 ⟶ 62:

===Inefficiency of equilibria===

The concepts of [[price of anarchy]] and [[price of stability]] were introduced to capture the loss in performance of a system due to the selfish behavior of its participants. The [[price of anarchy]] captures the worst -case performance of the system at equilibrium relative to the optimal performance possible.<ref>{{cite book | authors=[[Tim Roughgarden]] |title=Selfish routing and the price of anarchy |publisher=[[MIT Press]] |year=2005 |isbn=0-262-18243-2 }}</ref> The [[price of stability]], on the other hand, captures the relative performance of the best equilibrium of the system.<ref>*{{Cite journal|first1=Elliot|last1=Anshelevich|first2=Anirban|last2=Dasgupta|first3=Jon|last3=Kleinberg|first4=Éva|last4=Tardos|first5=Tom|last5=Wexler|first6=Tim|last6=Roughgarden|title=The Price of Stability for Network Design with Fair Cost Allocation|journal=SIAM J. Comput.|volume=38|issue=4|year=2008|pages=1602–1623|doi=10.1137/070680096}}</ref> These concepts are counterparts to the notion of [[approximation ratio]] in algorithm design.

===Complexity of finding equilibria===

Line 79 ⟶ 78:

| year = 2016

| url = http://procaccia.info/papers/comsoc.pdf}}</ref>

Other topics include:

Line 100 ⟶ 98:

== Conferences ==

* [[Association for Computing Machinery|ACM]] Conference on Economics and Computation (EC) <ref name="EC"> [http://www.sigecom.org/ec19/ EC 2019]</ref>

* Conference on Web and Internet Economics (WINE) <ref name="WINE"> [https://www.cs.ox.ac.uk/conferences/wine2018/ WINE 2018]</ref>

* International Symposium on Algorithmic Game Theory (SAGT) <ref name="SAGT"> [http://corelab.ntua.gr/sagt2019/ SAGT 2019]</ref>

Algorithmic Game Theory papers also often appear in general [[Theoretical Computer Science]] conferences such as [[Symposium on Theory of Computing|STOC]]<ref>[http://acm-stoc.org/stoc2019/call-for-papers.html STOC 2019 call for papers]</ref> and [[Symposium on Foundations of Computer Science|FOCS]],<ref>[http://focs2019.cs.jhu.edu/cfp/ FOCS 2019 call for papers]</ref> or [[Artificial Intelligence]] conferences such as [[Association for the Advancement of Artificial Intelligence #Conferences and publications|AAAI]]<ref> [https://aaai.org/Conferences/AAAI-19/wp-content/uploads/2018/11/AAAI-19_Accepted_Papers.pdf AAAI 2019 accepted papers]</ref> and [[International Joint Conference on Artificial Intelligence|IJCAI]].<ref> [https://www.ijcai19.org/accepted-papers.html IJCAI 2019 accepted papers]</ref>

== Journals and newsletters ==

* [[Association for Computing Machinery|ACM]] Transactions on Economics and Computation (TEAC) <ref name="TEAC"> [https://teac.acm.org/ TEAC]</ref>

* SIGEcom Exchanges <ref>[http://www.sigecom.org/exchanges/ SIGEcom Exchanges]</ref>

Algorithmic Game Theory papers are often also published in Game Theory journals such as [[Games and Economic Behavior| GEB]],<ref>

{{citation

| last1 = Chawla | first1 = Shuchi

Line 123 ⟶ 121:

| author4-link = Tim Roughgarden

| doi = 10.1016/j.geb.2015.02.011

}}</ref> Economics journals such as [[Econometrica]], and Computer Science journals such as [[SIAM Journal on Computing|SICOMP]].<ref> [https://www-siam-org.stanford.idm.oclc.org/Publications/Journals/SIAM-Journal-on-Computing-SICOMP SICOMP]</ref>

==See also==