首个在 Minty 条件下求解变分不等式的多项式时间算法

View PDF HTML (experimental)

Abstract:Solving (Stampacchia) variational inequalities (SVIs) is a foundational problem at the heart of optimization. However, this expressivity comes at the cost of computational hardness. As a result, most research has focused on carving out specific subclasses that elude those intractability barriers. A classical property that goes back to the 1960s is the Minty condition, which postulates that the Minty VI (MVI) problem admits a solution.
In this paper, we establish the first polynomial-time algorithm -- with complexity growing polynomially in the dimension $d$ and $\log(1/\epsilon)$ -- for solving $\epsilon$-SVIs for Lipschitz continuous mappings under the Minty condition. Prior approaches either incurred an exponentially worse dependence on $1/\epsilon$ (and other natural parameters of the problem) or made more restrictive assumptions, such as monotonicity. To do so, we introduce a new variant of the ellipsoid algorithm whereby separating hyperplanes are obtained after taking a descent step from the center of the ellipsoid. It succeeds even though the set of SVIs can be nonconvex and not fully dimensional. Moreover, when our algorithm is applied to an instance with no MVI solution and fails to identify an SVI solution, it produces a succinct certificate of MVI infeasibility. We also show that deciding whether the Minty condition holds is $\mathsf{coNP}$-complete, thereby establishing that the disjunction of those two problems is polynomial-time solvable even though each problem is individually intractable.
We provide several extensions and new applications of our main results. Most notably, we obtain the first polynomial-time algorithms for computing Nash equilibria in multi-player harmonic games. Finally, in two-player general-sum concave games, we give the first polynomial-time algorithm that outputs either a Nash equilibrium or a strict coarse correlated equilibrium.

Comments:	To appear in FOCS 2026
Subjects:	Optimization and Control (math.OC); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)
Cite as:	arXiv:2504.03432 [math.OC]
	(or arXiv:2504.03432v4 [math.OC] for this version)
	https://doi.org/10.48550/arXiv.2504.03432 arXiv-issued DOI via DataCite

Submission history

From: Ioannis Anagnostides [view email]
[v1] Fri, 4 Apr 2025 13:24:41 UTC (368 KB)
[v2] Wed, 5 Nov 2025 16:50:41 UTC (475 KB)
[v3] Thu, 2 Apr 2026 07:43:51 UTC (476 KB)
[v4] Fri, 2 Oct 2026 02:25:02 UTC (476 KB)