Game complexity
June 7, 2019 — June 7, 2019
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 equilibrium, 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
1 References
Aaronson. 2011. “Why Philosophers Should Care About Computational Complexity.”
Axtell. 2005. “The Complexity of Exchange.” The Economic Journal.
Chen, and Deng. 2006. “Settling the Complexity of Two-Player Nash Equilibrium.” In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06).
Daskalakis, Goldberg, and Papadimitriou. 2009. “The Complexity of Computing a Nash Equilibrium.” SIAM Journal on Computing.
Daskalakis, and Papadimitriou. 2011. “Continuous Local Search.” In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings.
Kaznatcheev. 2020. “Evolution Is Exponentially More Powerful with Frequency-Dependent Selection.” bioRxiv.
Schoenebeck, and Vadhan. 2009. “The Computational Complexity of Nash Equilibria in Concisely Represented Games.”
Ye. 2008. “A Path to the Arrow–Debreu Competitive Market Equilibrium.” Mathematical Programming.