2015/05/30 by Ioannis Avramopoulos, Avramopoulos, Ioannis · 1 voice
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Economic theories and models #Experimental Behavioral Economics Studies #Game Theory and Applications #cs.CC #cs.GT
paper · pdf · doi:10.48550/arxiv.1506.00095
I am withdrawing the claim that NP = coNP. The community working on the hardness of nonlinear optimization problems uses the term "NP-hard" to mean hardness under Turing (rather than Karp) reductions and does not distinguish between "NP-hard" and "coNP-hard" problems. Therefore, my proof that NP = coNP has a flaw in its argument. The rest of the results are correct though
openalex publication_date 2015/05/30 · arxiv created 2015/06/15 · arxiv updated 2015/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is well-known that the problem of recognizing an ESS in a symmetric bimatrix game is coNP-complete. In this paper, we show that recognizing an ESS even in doubly symmetric bimatrix games is also coNP-complete. Our result further implies that recognizing asymptotically stable equilibria of the replicator dynamic in this class of games is also a coNP-complete problem.