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.
Titolo: | On the complexity of uniformly mixed nash equilibria and related regular subgraph problems |
Autori: | |
Data di pubblicazione: | 2005 |
Serie: | |
Citazione: | 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. |
Handle: | http://hdl.handle.net/11590/379655 |
ISBN: | 978-3-540-28193-1 |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |