# Strong Nash equilibria and mixed strategies

arXiv: https://arxiv.org/abs/1502.05629 · HTML: https://mlsanity.com/paper/1502.05629/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2015.

## Built on by (most cited first, 1 of 1)

- [Best of Both Worlds: Regret Minimization versus Minimax Play](https://mlsanity.com/paper/2502.11673/) (2025)

## Abstract (arXiv)

In this paper we consider strong Nash equilibria, in mixed strategies, for finite games. Any strong Nash equilibrium outcome is Pareto efficient for each coalition. First, we analyze the two--player setting. Our main result, in its simplest form, states that if a game has a strong Nash equilibrium with full support (that is, both players randomize among all pure strategies), then the game is strictly competitive. In order to get our result we use the indifference principle fulfilled by any Nash equilibrium, and the classical KKT conditions (in the vector setting), that are necessary conditions for Pareto efficiency. Our characterization enables us to design a strong-Nash-equilibrium-finding algorithm with complexity in Smoothed-P. So, this problem---that Conitzer and Sandholm [Conitzer, V., Sandholm, T., 2008. New complexity results about Nash equilibria. Games Econ. Behav. 63, 621--641] proved to be computationally hard in the worst case---is generically easy. Hence, although the worst case complexity of finding a strong Nash equilibrium is harder than that of finding a Nash equilibrium, once small perturbations are applied, finding a strong Nash is easier than finding a Nash equilibrium. Next we switch to the setting with more than two players. We demonstrate that a strong Nash equilibrium can exist in which an outcome that is strictly Pareto dominated by a Nash equilibrium occurs with positive probability. Finally, we prove that games that have a strong Nash equilibrium where at least one player puts positive probability on at least two pure strategies are extremely rare: they are of zero measure.