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.
Titolo: | The complexity of uniform Nash equilibria and related regular subgraph problems | |
Autori: | ||
Data di pubblicazione: | 2008 | |
Rivista: | ||
Citazione: | 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. | |
Handle: | http://hdl.handle.net/11590/379881 | |
Appare nelle tipologie: | 1.1 Articolo in rivista |