The complexity of uniform Nash equilibria and related regular subgraph problems (Q935157)

The complexity of finding uniform Nash equilibria is investigated. A Nash equilibrium is uniform if, for each player, all the strategies played with non-zero probability are assigned the same probability. It is shown that, even for a restricted class of win-lose bimatrix games, deciding the existence of such uniform equilibria is an NP-complete problem. The proof is graph-theoretical. As a related result it is shown that it is NP-complete to decide if a graph has an induced regular subgraph of large size or regularity.