Algorithmic game theory: Difference between revisions

Revision as of 18:24, 13 June 2024

Latest revision as of 17:09, 9 August 2025

(4 intermediate revisions by 4 users not shown)

Line 1:

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

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

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 (economics)|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'': given the currently implemented algorithms, 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]].

* ''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 (e.g., ''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==

Line 67 ⟶ 68:

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}}}}.</ref> In contrast, [[correlated equilibrium|correlated equilibria]] can be computed efficiently using linear programming,<ref>{{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 }}</ref> as well as learned via no-regret strategies.<ref>{{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}}</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 141 ⟶ 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.