Game complexity

June 7, 2019 — June 7, 2019

compsci
economics
game theory
incentive mechanisms
markets
Figure 1

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.

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.