On the Role of Geometry in Solving Variational Inequalities
cs.CC, cs.GT, math.OC
Submitted: 2026-11-03
Updated: 2026-11-03
License: http://creativecommons.org/licenses/by/4.0/
The gist: The geometry of constraints in variational inequalities (VIs) plays a central role in applications ranging from resource allocation and equilibrium computation to constrained optimization.
Abstract
The geometry of constraints in variational inequalities (VIs) plays a central role in applications ranging from resource allocation and equilibrium computation to constrained optimization. Yet, its effect on computational complexity has received surprisingly little attention beyond special cases. We examine this question when the constraint set is an p ball. This family of problems encompasses two of the most extensively studied classes of problems in algorithmic game theory: symmetric bimatrix games for p = 1 and multi-player polymatrix games for p = infinity. Both of these problems are known to be PPAD-complete even for affine operators. We establish a comprehensive complexity landscape for VIs over p balls across the full range p in[1, infinity]. First, for any p not equal to 2, we show that finding an inverse-polynomial approximate VI solution is PPAD-complete even for affine operators. In contrast, for p=2, we give a polynomial-time algorithm for affine VIs, extending a classic result of Ye (1992) beyond symmetric operators. On the other hand, once the operator becomes quadratic, we establish PPAD-completeness even at inverse polynomial precision. From a technical standpoint, we develop a new toolkit for exploiting the geometry of the constraint set and the structure of the operator to characterize the complexity of equilibrium and optimization problems, which is of independent interest.
Sources
- Smoothed Analysis of Nash Equilibrium and Fixed Point Computation, and Efficiency of the Homotopy Method
- Improving neural networks by preventing co-adaptation of feature detectors
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?