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
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 ε-Nash equilibrium using log(1/ε)⋅2O(n) expected payoff-vector computations, compared to the worst-case runtime tradeoffs of log(1/ε)⋅nO(n), (1/ε)O(n), 2O(log2n/ε2), and 2O(n)poly(log(1/ε)). For fixed points and variational inequalities of bounded and Lipschitz maps on the n-dimensional ℓ2 unit ball, the same approach runs in expected time log(1/ε)⋅2O(n), compared to the worst-case (1/ε)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 2O(n), so that the method finds an ε-approximate solution in time 2O(n)⋅poly(1/p)/ε with probability at least 1−p.
Figures & tables
Figure 1: The homotopy path for n=1 , drawn in the (t,x) plane. The path γ (blue) is the branch of the zero set {(x,t):K(x,t)=0} that starts at (0,0) ; it may turn back in t . (a) γ reaches ∣x∣=1 at some t<1 , where F(x)=λx with λ≥0 , giving a boundary solution. (b) γ reaches t=1 , where F(x)=0 . Other components of the zero set (gray) are not followed.
Figure 2: Two iterations of Algorithm 1 : each predictor step (solid) moves along the approximate tangent and leaves γ ; each corrector step (dashed) is a Newton step orthogonal to it that returns close to γ .
We show that computing an approximate correlated equilibrium of a polytope game is PPAD-complete, and thus polynomial-time equivalent to finding a Nash equilibrium. This challenges the conventional view in game theory that correlated equilibria are more tractable objects than Nash equilibria. From a conceptual standpoint, we connect correlated equilibria to a natural generalization of fixed points, which we call fixed sets. A fixed set of a continuous function f is a nonempty finite set S such that S⊆convf(S). Our main technical contribution is to prove that computing a fixed set is PPAD-hard even at inverse polynomial precision.
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina +3
Carnegie Mellon University. · Massachusetts Institute of Technology. · University of Texas, Austin. +1
Developing general-purpose algorithms with global asymptotic convergence guarantees for Nash equilibria of general-sum games remains a longstanding challenge. This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from simplex domains to product-of-simplex domains, enabling its direct application to Nash equilibrium computation. The resulting fixed-point bundle exhibits a composite fiber bundle structure. The key innovation is to construct an equivalent VI on a simplex and establish the equivalence between the two fixed-point bundle frameworks via a fiber bundle isomorphism. Exploiting this geometric equivalence, we show that the path-following algorithm for VIs on product-of-simplex domains inherits the global linear convergence guarantees of the simplex-domain framework. In numerical experiments, the algorithm attained a precision of 10−5 on all 5600 randomly generated game instances, with dimension ranging from 2-player 128-action to 128-player 2-action. Code and data are available at https://github.com/shb20tsinghua/FiberBundle_VI.
Many important games have more than two players and imperfect information. Existing approaches for computing Nash equilibrium, the central game-theoretic solution concept, in such games either lack scalability or obtain poor performance. In this paper we introduce a new algorithm called projected exploitability descent (PED) for approximating Nash equilibria in multiplayer games of imperfect information. The algorithm works by running projected subgradient descent minimizing a proxy for the multiplayer generalized exploitability function. The objective is nonconvex and nonsmooth, but can be represented as the sum of the maxima of linear functions, for which a subgradient can easily be computed and projected to the polytope of feasible sequence-form strategies. We explore performance of PED on a generalized version of the well-studied benchmark game three-player Kuhn poker. No prior exact algorithms scale to the version of the game with deck size larger than 4, and we compare performance to the popular algorithms of fictitious play (FP) and counterfactual regret minimization (CFR). We find that PED obtains a consistent near-monotonic improvement throughout all runs, though both FP and CFR perform significantly better in the initial iterations. This inspires a hybrid algorithm FP-PED that runs FP for an initial burn-in period before switching to PED for stable long-run refinement. We can alternatively view this as a multi-step algorithm that runs FP as a pre-processing step to obtain a strong initialization for PED.