We investigate the complexity of finding uniformly mixed Nash equilibria (that is, equilibria in which all played strategies are played with the same probability). We show that, even in very simple win/lose bimatrix games, deciding the existence of uniformly mixed equilibria in which the support of one (or both) of the players is at most or at least a given size is an NP-complete problem. Motivated by these results, we also give NP-completeness results for problems related to finding a regular induced subgraph of a certain size or regularity in a given graph, which can be of independent interest. © Springer-Verlag Berlin Heidelberg 2005.
Bonifaci, V., Di Iorio, U., & Laura, L. (2005). On the complexity of uniformly mixed nash equilibria and related regular subgraph problems. In Proc. 15th Int. Symp. on Fundamentals of Computation Theory (pp.197-208). Berlin : Springer Verlag [10.1007/11537311_18].
On the complexity of uniformly mixed nash equilibria and related regular subgraph problems
Bonifaci V.;
2005
Abstract
We investigate the complexity of finding uniformly mixed Nash equilibria (that is, equilibria in which all played strategies are played with the same probability). We show that, even in very simple win/lose bimatrix games, deciding the existence of uniformly mixed equilibria in which the support of one (or both) of the players is at most or at least a given size is an NP-complete problem. Motivated by these results, we also give NP-completeness results for problems related to finding a regular induced subgraph of a certain size or regularity in a given graph, which can be of independent interest. © Springer-Verlag Berlin Heidelberg 2005.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
