Content deleted Content added
→Areas of research: Added details for subareas along with references |
→Areas of research: Added a short blurb about computational social choice. |
||
Line 67:
===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 }}</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
| 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}}</ref>
Line 72 ⟶ 84:
* Algorithms for computing [[market equilibrium|Market equilibria]]
▲* [[Computational social choice]]
* [[Fair division]]
* [[Multi-agent systems]]
| |||