  A fundamental shortcoming of the concept of Nash equilibrium is its
computational intractability: approximating Nash equilibria in normal-form
games is PPAD-hard. In this paper, inspired by the ideas of smoothed analysis,
we introduce a relaxed variant of Nash equilibrium called $\sigma$-smooth Nash
equilibrium, for a smoothness parameter $\sigma$. In a $\sigma$-smooth Nash
equilibrium, players only need to achieve utility at least as high as their
best deviation to a $\sigma$-smooth strategy, which is a distribution that does
not put too much mass (as parametrized by $\sigma$) on any fixed action. We
distinguish two variants of $\sigma$-smooth Nash equilibria: strong
$\sigma$-smooth Nash equilibria, in which players are required to play
$\sigma$-smooth strategies under equilibrium play, and weak $\sigma$-smooth
Nash equilibria, where there is no such requirement.
  We show that both weak and strong $\sigma$-smooth Nash equilibria have
superior computational properties to Nash equilibria: when $\sigma$ as well as
an approximation parameter $\epsilon$ and the number of players are all
constants, there is a constant-time randomized algorithm to find a weak
$\epsilon$-approximate $\sigma$-smooth Nash equilibrium in normal-form games.
In the same parameter regime, there is a polynomial-time deterministic
algorithm to find a strong $\epsilon$-approximate $\sigma$-smooth Nash
equilibrium in a normal-form game. These results stand in contrast to the
optimal algorithm for computing $\epsilon$-approximate Nash equilibria, which
cannot run in faster than quasipolynomial-time. We complement our upper bounds
by showing that when either $\sigma$ or $\epsilon$ is an inverse polynomial,
finding a weak $\epsilon$-approximate $\sigma$-smooth Nash equilibria becomes
computationally intractable.
