  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-$\mathcal{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.
