Algorithmic game theory: Difference between revisions

Revision as of 22:29, 30 June 2019

Latest revision as of 17:09, 9 August 2025

(31 intermediate revisions by 27 users not shown)

Line 1:

{{Short description|Study of algorithms in strategic environments}}

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

'''Algorithmic game theory''' ('''AGT''') is an areainterdisciplinary field inat the intersection of [[game theory]] and [[computer science]], withfocused the objective ofon understanding and design ofdesigning algorithms infor [[Strategyenvironments (gamewhere multiple theory)|strategic]] environmentsagents interact. This research area combines computational thinking with economic principles to address challenges that emerge when algorithmic inputs come from self-interested participants.

In traditional [[algorithm design]], inputs are assumed to be fixed and reliable. However, in many real-world applications—such as [[Electronic auction|online auctions]], [[internet routing]], [[digital advertising]], and [[resource allocation]] systems—inputs are provided by multiple independent agents who may strategically misreport information to manipulate outcomes in their favor. AGT provides frameworks to analyze and design systems that remain effective despite such strategic behavior.

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:

The field can be approached from two complementary 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]].

* ''Analysis'': Evaluating existing algorithms and systems through game-theoretic tools to understand their strategic properties. This includes calculating and proving properties of [[Nash equilibria]] (stable states where no participant can benefit by changing only their own strategy), measuring [[price of anarchy]] (efficiency loss due to selfish behavior), and analyzing best-response dynamics (how systems evolve when players sequentially optimize their strategies).

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.

* ''Design'': Creating mechanisms and algorithms with both desirable computational properties and game-theoretic robustness. This sub-field, known as [[algorithmic mechanism design]], develops systems that incentivize truthful behavior while maintaining computational efficiency.

Algorithm designers in this ___domain must satisfy traditional algorithmic requirements (such as ''[[polynomial-time]] running time'' and ''good approximation ratio'') while simultaneously addressing incentive constraints that ensure participants act according to the system's intended design.

==History==

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

In 1999, the seminal paper of [[Noam Nisan|Nisan]] and Ronen[[Amir Ronen]]<ref name="nr">{{citation

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

| last2 = Ronen | first2 = Amir | author2-link = Amir Ronen

| contribution = Algorithmic mechanism design

| doi = 10.1145/301250.301287

| pages = 129–140

| title = Proceedings of the 31st ACM Symposium on Theory of Computing (STOC '99)

| year = 1999| isbn = 978-1581130676 | s2cid = 8316937 | doi-access = free}}</ref> drew the attention of the Theoretical Computer Science community to designing algorithms for selfish (strategic) users. As they claim in the abstract:

{{QuoteBlockquote|We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are capable of manipulating the algorithm, the algorithm designer should ensure in advance that the agents’ interests are best served by behaving correctly.

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.}}

Line 32 ⟶ 34:

|___location= New York

|agency=Association for Computing Machinery

|archive-date=20122013-0507-2618

|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|firstfirst1=Elias|lastlast1=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

Line 46 ⟶ 47:

| pages = 749–753

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

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

===The Internet as a catalyst===

Line 63:

===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 |author1=Tim authorsRoughgarden |author-link=[[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|s2cid=2839399}}.</ref> These concepts are counterparts to the notion of [[approximation ratio]] in algorithm design.

===Complexity of finding equilibria===

The existence of an equilibrium in a game is typically established using non-constructive [[fixed point theorem]]s. There are no efficient algorithms known for computing [[Nash equilibrium|Nash equilibria]]. The problem is complete for the [[complexity class]] [[PPAD]] even in 2-player games.<ref name="chen2005">*{{Cite conference|first1=Xi|last1=Chen|first2=Xiaotie|last2=Deng|title=Settling the complexity of two-player Nash equilibrium|conference=Proc. 47th Symp. Foundations of Computer Science|year=2006|pages=261–271|doi=10.1109/FOCS.2006.69|id={{ECCC|2005|05|140}}|postscript=<!--None-->}}.</ref> In contrast, [[correlated equilibrium|correlated equilibria]] can be computed efficiently using linear programming,<ref>{{cite journal |firstfirst1=Christos H. |lastlast1=Papadimitriou |first2=Tim |last2=Roughgarden |title=Computing correlated equilibria in multi-player games |journal=J. ACM |volume=55 |issue=3 |pages=14:1–14:29 |year=2008 |doi=10.1145/1379759.1379762|citeseerx=10.1.1.335.2634 |s2cid=53224027 }}</ref> as well as learned via no-regret strategies.<ref>{{cite journal |lastlast1=Foster |firstfirst1=Dean P. |first2=Rakesh V. |last2=Vohra |title=Calibrated Learning and Correlated Equilibrium |journal=Games and Economic Behavior |year=1996 |url=https://repository.upenn.edu/cgi/viewcontent.cgi?article=1008&context=statistics_papers}}</ref>

=== [[Computational social choice]]===

{{Main|Computational social choice}}

Computational social choice studies computational aspects of ''social choice'', the aggregation of individual agents' preferences. Examples include algorithms and computational complexity of voting rules and coalition formation.<ref>{{citation

Line 79:

| year = 2016

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

Other topics include:

Line 87 ⟶ 86:

* [[Multi-agent systems]]

And the area counts with diverse practical applications:<ref>{{cite book |author1=Tim authorsRoughgarden |author-link=[[Tim Roughgarden]] |title=Twenty lectures on algorithmic game theory |publisher=[[Cambridge University Press]] |year=2016 |isbn=9781316624791}}</ref><ref>{{Citecite web | url=http://www.sigecom.org/ec19/callforpapers.html |title = EC'19 &#124;&#124; 20th ACM Conference on Economics and Computation}}</ref>

* [[Sponsored search auction]]s

Line 98 ⟶ 97:

* [[Crowdsourcing]] and peer grading

* [[Economics of the cloud]]

== 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 | author1-link = Shuchi Chawla

| last2 = Fleischer | first2 = Lisa

| last3 = Hartline | first3 = Jason

Line 123 ⟶ 115:

| 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==

*[[Auction Theory]]

*[[Computational social choice]]

*[[Gamification]]

*[[Load balancing (computing)]]

*[[Mechanism design]]

Line 134 ⟶ 127:

==References==

{{Reflist}}

<references />

* [[John von Neumann]], [[Oskar Morgenstern]] (1944) ''[[Theory of Games and Economic Behavior]]''. Princeton Univ. Press. 2007 edition: {{ISBN|978-0-691-13061-3}}

*{{citation

Line 149 ⟶ 142:

==External links==

*[httphttps://gambit.sourceforge.net/ gambit.sourceforge.net] - a library of game theory software and tools for the construction and analysis of finite extensive and strategic games.

*[http://gamut.stanford.edu/ gamut.stanford.edu] - a suite of game generators designated for testing game-theoretic algorithms.

{{Authority control}}

{{DEFAULTSORT:Algorithmic Game Theory}}

[[Category:Game theory|+]]

[[Category:Theory of computation]]

[[Category:Algorithms]]