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. © 2008 Elsevier B.V. All rights reserved.

Bonifaci, V., Di Iorio, U., Laura, L. (2008). The complexity of uniform Nash equilibria and related regular subgraph problems. THEORETICAL COMPUTER SCIENCE, 401(1-3), 144-152 [10.1016/j.tcs.2008.03.036].

The complexity of uniform Nash equilibria and related regular subgraph problems

Bonifaci V.;
2008-01-01

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. © 2008 Elsevier B.V. All rights reserved.
2008
Bonifaci, V., Di Iorio, U., Laura, L. (2008). The complexity of uniform Nash equilibria and related regular subgraph problems. THEORETICAL COMPUTER SCIENCE, 401(1-3), 144-152 [10.1016/j.tcs.2008.03.036].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/379881
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 11
social impact