A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition

Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm +1

Solving (Stampacchia) variational inequalities (SVIs) is a foundational problem at the heart of optimization. However, this expressivity comes at the cost of computational hardness…