The Exact Computational Complexity of Evolutionarily Stable Strategies

References

• [1] Chen X, Deng X, Teng SH (2009) Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3):14:1–14:57.Crossref, Google Scholar
• [2] Conitzer V, Sandholm T (2008) New complexity results about Nash equilibria. Games Econom. Behav. 63(2):621–641.Crossref, Google Scholar
• [3] Daskalakis C, Goldberg P, Papadimitriou CH (2009) The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1):195–259.Crossref, Google Scholar
• [4] Etessami K, Lochbihler A (2008) The computational complexity of evolutionarily stable strategies. Internat. J. Game Theory 37(1):93–113.Crossref, Google Scholar
• [5] Etessami K, Yannakakis M (2010) On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6):2531–2597.Crossref, Google Scholar
• [6] Gilboa I, Zemel E (1989) Nash and correlated equilibria: Some complexity considerations. Games Econom. Behav. 1(1):80–93.Crossref, Google Scholar
• [7] Ko KI, Lin CL (1995) On the complexity of min-max optimization problems and their approximation. Du DZ, Pardalos PM, eds. Minimax and Applications (Kluwer Academic Publishers, Boston), 219–239.Crossref, Google Scholar
• [8] Lemke C, Howson J (1964) Equilibrium points of bimatrix games. J. Soc. Indust. Appl. Math. 12(4):413–423.Crossref, Google Scholar
• [9] Nash J (1950) Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA 36(1):48–49.Crossref, Google Scholar
• [10] Nisan N (2006) A note on the computational hardness of evolutionary stable strategies. Electronic Colloquium on Computational Complexity Report No. 76, https://eccc.weizmann.ac.il/report/2006/076/.Google Scholar
• [11] Papadimitriou CH (1994) On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci. 48(3):498–532.Crossref, Google Scholar
• [12] Papadimitriou CH (2001) Algorithms, games and the internet. Proc. 33rd Annual Sympos. Theory Comput. (ACM, New York), 749–753.Crossref, Google Scholar
• [13] Price G, Smith JM (1973) The logic of animal conflict. Nature 246(5499):15–18.Google Scholar
• [14] Savani R, von Stengel B (2006) Hard-to-solve bimatrix games. Econometrica 74(2):397–429.Crossref, Google Scholar
• [15] Schaefer M, Umans C (2008) Completeness in the polynomial-time hierarchy: A compendium. Working paper, DePaul University, Chicago.Google Scholar
• [16] Suri S (2007) Computational evolutionary game theory. Nisan N, Roughgarden T, Tardos E, Vazirani V, eds. Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 717–736.Crossref, Google Scholar