Advertisement
Published in:
2005 | OriginalPaper | Chapter
New Results on the Complexity of Uniformly Mixed Nash Equilibria
Authors : Vincenzo Bonifaci, Ugo Di Iorio, Luigi Laura
Published in: Internet and Network Economics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.