We investigate the complexity of finding Nash equilibria in which the strategy of each player is uniform on its support set. We show that, even for a restricted class of win-lose bimatrix games, deciding the existence of such uniform equilibria is an NP-complete problem. Our proof is graph-theoretical. Motivated by this result, we also give NP-completeness results for the problems of finding regular induced subgraphs of large size or regularity, which can be of independent interest. (c) 2008 Elsevier B.V. All rights reserved.
The complexity of uniform Nash equilibria and related regular subgraph problems / Bonifaci, Vincenzo; U., Di Iorio; Laura, Luigi. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 401:1-3(2008), pp. 144-152. (Intervento presentato al convegno 1st International Workshop on Internet and Network Economics tenutosi a Hong Kong, PEOPLES R CHINA nel DEC 15-17, 2005) [10.1016/j.tcs.2008.03.036].
The complexity of uniform Nash equilibria and related regular subgraph problems
BONIFACI, VINCENZO;LAURA, Luigi
2008
Abstract
We investigate the complexity of finding Nash equilibria in which the strategy of each player is uniform on its support set. We show that, even for a restricted class of win-lose bimatrix games, deciding the existence of such uniform equilibria is an NP-complete problem. Our proof is graph-theoretical. Motivated by this result, we also give NP-completeness results for the problems of finding regular induced subgraphs of large size or regularity, which can be of independent interest. (c) 2008 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
