On the Role of Geometry in Solving Variational Inequalities
Source: arxiv.org/abs/2611.04151
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.04151
curl -X POST /api/v1/records/arxiv/2611.04151/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.04151/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'