[2501.10884] Smoothed Analysis of Nash Equilibrium and Fixed Point Computation, and Efficiency of the Homotopy Method

View a PDF of the paper titled Smoothed Analysis of Nash Equilibrium and Fixed Point Computation, and Efficiency of the Homotopy Method, by Idan Attias and 4 other authors

View PDF
HTML (experimental)

Abstract:We study, under a smoothed analysis perspective, the complexity of three PPAD-complete problems: computing Nash equilibria, computing fixed points, and solving variational inequalities. We consider a general perturbation model that bounds the probability density of the quantities evaluated by our algorithms. As special cases, it captures worst-case games perturbed by small random per-action costs, and worst-case maps perturbed by a small random affine function.

Under these models, we show that classical algorithmic paradigms, cover-based search and homotopy path-following provably outperform the worst-case state-of-the-art. For games with a constant number of players and $n$ strategies per player, a recursive cover-based algorithm computes an $\varepsilon$-Nash equilibrium using $\log(1/\varepsilon)\cdot 2^{O(n)}$ expected payoff-vector computations, compared to the worst-case runtime tradeoffs of $\log(1/\varepsilon)\cdot n^{O(n)}$, $(1/\varepsilon)^{O(n)}$, $2^{O(\log^2 n/\varepsilon^2)}$, and $2^{O(n)}\mathrm{poly}(\log(1/\varepsilon))$. For fixed points and variational inequalities of bounded and Lipschitz maps on the $n$-dimensional $\ell_2$ unit ball, the same approach runs in expected time $\log(1/\varepsilon)\cdot 2^{O(n)}$, compared to the worst-case $(1/\varepsilon)^{O(n)}$; the $2^{\Omega(n)}$ factor is necessary by prior work [Rubinstein, 2017]. For general smooth maps, we further analyze the classical predictor–corrector homotopy method, for which only qualitative convergence guarantees were previously known, showing that under perturbations the homotopy path is well conditioned and has length $2^{O(n)}$, so that the method finds an $\varepsilon$-approximate solution in time $2^{O(n)}\cdot\mathrm{poly}(1/p)/\varepsilon$ with probability at least $1-p$.