← 研踪 PaperTrailarXiv:2611.04151 · v1
On the Role of Geometry in Solving Variational Inequalities
首次提交 2026-11-03 09:41
版本更新 2026-11-03 09:41
雷达观测 2026-11-04 23:40
摘要
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 $\ell_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 = \infty$. Both of these problems are known to be PPAD-complete even for affine operators. We establish a comprehensive complexity landscape for VIs over $\ell_p$ balls across the full range $p\in[1,\infty]$. First, for any $p\neq 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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-03 09:41 · 最新观测版本
On the Role of Geometry in Solving Variational Inequalities
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 $\ell_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 = \infty$. Both of these problems are known to be PPAD-complete even for affine operators. We establish a comprehensive complexity landscape for VIs over $\ell_p$ balls across the full range $p\in[1,\infty]$. First, for any $p\neq 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.
查看此版本解读 →查看此版本原文 ↗