Content deleted Content added
Adding local short description: "Study of algorithms in strategic environments", overriding Wikidata description "study of algorithms in strategic environments" |
m →Computational social choice: Do not link section header |
||
Line 67:
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>
===
{{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
| |||