We are interested in the complexity of finding Nash equilibria with one uniformly mixed strategy (that is, equilibria in which at least one of the players plays a uniform probability distribution over some set of pure strategies). We show that, even in imitation bimatrix games, where one player has a positive payoff if he plays the same pure strategy as the opponent, deciding the existence of such an equilibrium is an NP-complete problem. We derive this result from the NP-completeness of graph-theoretical problems strictly related to this class of equilibria. © Springer-Verlag Berlin Heidelberg 2005.
Bonifaci, V., Di Iorio, U., & Laura, L. (2005). New results on the complexity of uniformly mixed Nash equilibria. In Proc. 1st Int. Workshop on Internet and Network Economics (pp.1023-1032). Berlin : Springer.
Titolo: | New results on the complexity of uniformly mixed Nash equilibria |
Autori: | |
Data di pubblicazione: | 2005 |
Serie: | |
Citazione: | Bonifaci, V., Di Iorio, U., & Laura, L. (2005). New results on the complexity of uniformly mixed Nash equilibria. In Proc. 1st Int. Workshop on Internet and Network Economics (pp.1023-1032). Berlin : Springer. |
Handle: | http://hdl.handle.net/11590/379750 |
ISBN: | 978-3-540-30900-0 |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |