The complexity of finding game theory optima, as seen in cooperation, mechanism design, adversarial training, Newcomb decision problems and so on.
The complexity class PPAD.
How long until we approach Nash equilibiruim, also includes a note on Aumann’s correlated equilibrium which i would like to know about.
- Ye08: Yinyu Ye (2008) A path to the Arrow–Debreu competitive market equilibrium. Mathematical Programming, 111(1–2), 315–348. DOI
- DaPa11: C. Daskalakis, C. Papadimitriou (2011) Continuous Local Search. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 790–804). Society for Industrial and Applied Mathematics DOI
- ChDe06: X. Chen, X. Deng (2006) Settling the Complexity of Two-Player Nash Equilibrium. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) (pp. 261–272). DOI
- DaGP09: C. Daskalakis, P. Goldberg, C. Papadimitriou (2009) The Complexity of Computing a Nash Equilibrium. SIAM Journal on Computing, 39, 195–259. DOI
- Axte05: Robert Axtell (2005) The Complexity of Exchange. The Economic Journal, 115(504), F193–F210. DOI
- ScVa09: Grant R Schoenebeck, Salil P Vadhan (2009) The Computational Complexity of Nash Equilibria in Concisely Represented Games. , 61.
- Aaro11: Scott Aaronson (2011) Why Philosophers Should Care About Computational Complexity., 59.