← 研踪 PaperTrailarXiv:2501.10884 · v2
Smoothed Analysis of Nash Equilibrium and Fixed Point Computation, and Efficiency of the Homotopy Method
首次提交 2025-01-19 05:32
版本更新 2026-11-10 01:20
雷达观测 2026-11-10 15:22
摘要
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^{Ω(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$.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-10 01:20 · 最新观测版本
Smoothed Analysis of Nash Equilibrium and Fixed Point Computation, and Efficiency of the Homotopy Method
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^{Ω(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$.
查看此版本解读 →查看此版本原文 ↗