Smoothed Analysis of Nash Equilibrium and Fixed Point Computation, and Efficiency of the Homotopy Method
Organizations: Institute for Data, Econometrics, Algorithms, and Learning UIC and TTIC · School of Computer Science Tel Aviv University · EECS Department MIT · Department of Computer Science Yale University
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 strategies per player, a recursive cover-based algorithm computes an -Nash equilibrium using expected payoff-vector computations, compared to the worst-case runtime tradeoffs of , , , and . For fixed points and variational inequalities of bounded and Lipschitz maps on the -dimensional unit ball, the same approach runs in expected time , compared to the worst-case ; the 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 , so that the method finds an -approximate solution in time with probability at least .
Figures & tables
Nash Equilibrium Computation
Nash equilibrium computation develops algorithms for finding stable strategies in strategic, stochastic, and imperfect-information games.
See all 75 papers