Algorithmic game theory: Difference between revisions

Revision as of 23:30, 27 August 2019

Revision as of 05:46, 15 March 2020

Line 65:

===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 |first=Christos H. |last=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 }}</ref> as well as learned via no-regret strategies.<ref>{{cite journal |last=Foster |first=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]]===