Algorithmic game theory

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

Algorithmic game theory (AGT) is an interdisciplinary field at the intersection of game theory and computer science, focused on understanding and designing algorithms for environments where multiple strategic agents 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 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.

The field can be approached from two complementary perspectives:

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).
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 and Amir Ronen{{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}} drew the attention of the Theoretical Computer Science community to designing algorithms for selfish (strategic) users. As they claim in the abstract:

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

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".{{cite press release

|author=

|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=2013-07-18

|date=2012-05-16

|access-date=2018-01-08}}

=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",{{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}} Koutsoupias and 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.{{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| isbn = 978-1581133493 | citeseerx = 10.1.1.70.8836 | s2cid = 207594967 }})

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

Game theory studies equilibria (such as the Nash equilibrium). An equilibrium is generally defined as a state in which no player has an incentive to change their strategy. Equilibria are found in several fields related to the Internet, for instance financial interactions and communication load-balancing{{Citation needed|date=September 2010}}. Game theory provides tools to analyze equilibria, and a common approach is then to ‘find the game’—that is, to formalize specific Internet interactions as a game, and to derive the associated equilibria.

Rephrasing problems in terms of games allows the analysis of Internet-based interactions and the construction of mechanisms to meet specified demands. If equilibria can be shown to exist, a further question must be answered: can an equilibrium be found, and in reasonable time? This leads to the analysis of algorithms for finding equilibria. Of special importance is the complexity class PPAD, which includes many problems in algorithmic game theory.

Areas of research

=Algorithmic mechanism design=

Mechanism design is the subarea of economics that deals with optimization under incentive constraints. Algorithmic mechanism design considers the optimization of economic systems under computational efficiency requirements. Typical objectives studied include revenue maximization and social welfare maximization.

=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.{{cite book |author1=Tim Roughgarden |author-link=Tim Roughgarden |title=Selfish routing and the price of anarchy |publisher=MIT Press |year=2005 |isbn=0-262-18243-2 }} The price of stability, on the other hand, captures the relative performance of the best equilibrium of the system.*{{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}} 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 theorems. There are no efficient algorithms known for computing Nash equilibria. The problem is complete for the complexity class PPAD even in 2-player games.*{{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}}}}. In contrast, correlated equilibria can be computed efficiently using linear programming,{{cite journal |first1=Christos H. |last1=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 }} as well as learned via no-regret strategies.{{cite journal |last1=Foster |first1=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}}

=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.{{citation

| editor1 = Felix Brandt

| editor2 = Vincent Conitzer

| editor3 = Ulle Endriss

| editor4 = Jérôme Lang

| editor5 = Ariel D. Procaccia

| title = Handbook of Computational Social Choice

| year = 2016

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

Journals and newsletters

ACM Transactions on Economics and Computation (TEAC) [https://teac.acm.org/ TEAC]
SIGEcom Exchanges [http://www.sigecom.org/exchanges/ SIGEcom Exchanges]

Algorithmic Game Theory papers are often also published in Game Theory journals such as GEB,

{{citation

| last1 = Chawla | first1 = Shuchi | author1-link = Shuchi Chawla

| last2 = Fleischer | first2 = Lisa

| last3 = Hartline | first3 = Jason

| author4 = Tim Roughgarden

| title = Introduction to the Special Issue – Algorithmic Game Theory – STOC/FOCS/SODA 2011

| journal = Games and Economic Behavior

| volume = 92

| pages = 228–231

| year = 2015

| author4-link = Tim Roughgarden

| doi = 10.1016/j.geb.2015.02.011

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

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

| last1 = Vazirani | first1 = Vijay V. | author1-link = Vijay Vazirani

| last2 = Nisan | first2 = Noam | author2-link = Noam Nisan

| last3 = Roughgarden | first3 = Tim | author3-link = Tim Roughgarden

| last4 = Tardos | first4 = Éva | author4-link = Éva Tardos

| isbn = 978-0-521-87282-9

| location = Cambridge, UK

| publisher = Cambridge University Press

| title = Algorithmic Game Theory

| url = http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf

| year = 2007}}.

External links

[http://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.

+

Category:Theory of computation

Category:Algorithms