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.

- Fortnow and Gasarch, The complexity of Nash equilibrium
- What is PPAD

## References

Aaronson, Scott. 2011. “Why Philosophers Should Care About Computational Complexity,” August, 59.

Axtell, Robert. 2005. “The Complexity of Exchange.”

*The Economic Journal*115 (504): F193–210.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.Daskalakis, C., P. Goldberg, and C. Papadimitriou. 2009. “The Complexity of Computing a Nash Equilibrium.”

*SIAM Journal on Computing*39 (January): 195–259.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.Kaznatcheev, Artem. 2020. “Evolution Is Exponentially More Powerful with Frequency-Dependent Selection.”

*bioRxiv*, May, 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.
## No comments yet. Why not leave one?