Strong Nash equilibrium is in smoothed P

The computational characterization of game–theoretic solution concepts is a prominent topic in artificial intel-ligence. The central solution concept is Nash equilib-rium (NE). However, it fails to capture the possibility that agents can form coalitions. Strong Nash equilib-rium (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 ex-istence of mixed–strategy SNEs, given that the problem of enumerating 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