On the Role of Geometry in Solving Variational Inequalities
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 = ∞. 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∈[1,∞]. First, for any p≠ 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.
Related
- Solving Quasi-Variational Inequalities Using the Progressive Decoupling of Linkages
- Optimal High-Order Methods for Solving Monotone Variational Inequalities
- Energetic Variational Deep Learning for Solving High-Dimensional Stationary Fokker-Planck Equations
- Optimal Recovery for Solving Variational Problems
- Sharp logarithmic Sobolev inequalities on free groups by variational comparison
BibTeX
@misc{anagnostides2026role,
title = {{On the Role of Geometry in Solving Variational Inequalities}},
author = {Ioannis Anagnostides and Ioannis Panageas and Jingming Yan},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04151},
eprint = {2611.04151},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04151},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Role of Geometry in Solving Variational Inequalities
AU - Ioannis Anagnostides
AU - Ioannis Panageas
AU - Jingming Yan
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04151
UR - https://arxiv.org/abs/2611.04151
AB - 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 = ∞. 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∈[1,∞]. First, for any p≠ 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.
ER -