Game complexity

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.

Aaronson, Scott. 2011. “Why Philosophers Should Care About Computational Complexity,” August, 59. https://arxiv.org/abs/1108.1791v3.

Axtell, Robert. 2005. “The Complexity of Exchange.” The Economic Journal 115 (504): F193–F210. https://doi.org/10.1111/j.1468-0297.2005.01001.x.

Chen, X., and X. Deng. 2006. “Settling the Complexity of Two-Player Nash Equilibrium.” In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), 261–72. https://doi.org/10.1109/FOCS.2006.69.

Daskalakis, C., P. Goldberg, and C. Papadimitriou. 2009. “The Complexity of Computing a Nash Equilibrium.” SIAM Journal on Computing 39 (January): 195–259. https://doi.org/10.1137/070699652.

Daskalakis, C., and C. Papadimitriou. 2011. “Continuous Local Search.” In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 790–804. Proceedings. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973082.62.

Kaznatcheev, Artem. 2020. “Evolution Is Exponentially More Powerful with Frequency-Dependent Selection.” bioRxiv, May, 2020.05.03.075069. https://doi.org/10.1101/2020.05.03.075069.

Schoenebeck, Grant R, and Salil P Vadhan. 2009. “The Computational Complexity of Nash Equilibria in Concisely Represented Games,” 61.

Ye, Yinyu. 2008. “A Path to the Arrow–Debreu Competitive Market Equilibrium.” Mathematical Programming 111 (1-2): 315–48. https://doi.org/10.1007/s10107-006-0065-5.