Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-076 | 4th May 2006 00:00

A Note on the computational hardness of evolutionary stable strategies

RSS-Feed




TR06-076
Authors: Noam Nisan
Publication: 21st June 2006 09:12
Downloads: 1402
Keywords: 


Abstract:

We present a very simple reduction that when given a graph G and an integer k produces a game that has an evolutionary stable strategy if and only if the maximum clique size of G is not exactly k. Formally this shows that existence of evolutionary stable strategies is hard for a complexity class called co-Dp, slightly strengthening (and greatly simplifying) the known NP-hardness and co-NP-hardness. En route we show that even recognizing an evolutionary stable strategy is co-NP complete.



ISSN 1433-8092 | Imprint