AAAI Publications, Workshops at the Twenty-Seventh AAAI Conference on Artificial Intelligence

Font Size: 
Strong Nash Equilibrium Is in Smoothed P
Nicola Gatti, Marco Rocco, Tuomas Sandholm

Last modified: 2013-06-29


The computational characterization of game–theoretic solution concepts is a prominent topic in computer sci- ence. The central solution concept is Nash equilibrium (NE). However, it fails to capture the possibility that agents can form coalitions. Strong Nash equilibrium (SNE) refines NE to this setting. It is known that finding an SNE is NP–complete when the number of agents is constant. This hardness is solely due to the existence of mixed–strategy SNEs, given that the problem of enu- merating all pure–strategy SNEs is trivially in P. Our central result is that, in order for an n–agent game to have at least one non–pure–strategy SNE, the agents’ payoffs restricted to the agents’ supports must lie on an (n − 1)-dimensional space. Small perturbations make the payoffs fall outside such a space and thus, unlike NE, finding an SNE is in smoothed polynomial time.

Full Text: PDF