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 [10.1007/11600930_103].
New results on the complexity of uniformly mixed Nash equilibria
Bonifaci V.;
2005-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
