Research map / Learning theory and algorithms / Submodular and game algorithms

Expected Variational Inequalities

ICML 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Equilibrium solvers for adversarial games

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces expected variational inequalities (EVIs), a distributional relaxation of VIs parameterized by a deviation set Φ, and shows linear-Φ EVIs are poly-time solvable via ellipsoid-against-hope and regret minimization.

Problem

Variational inequalities are computationally intractable in general (PPAD-hard even for linear F), so the paper asks whether a meaningful relaxation of the VI solution concept can always be solved efficiently.

Approach

Relax the VI to a distribution over points that satisfies the VI constraint only in expectation (EVI); with deviation set restricted to linear maps, the problem becomes solvable in polynomial time via ellipsoid-against-hope, and it generalizes correlated equilibria, refining CEs in normal-form games.

Key results

• Linear-Phi EVIs can be solved in poly(d, log(B/epsilon)) time given a membership oracle for the constraint set, via ellipsoid against hope.
• Phi-EVIs with all nonlinear (even quadratic) deviation maps are PPAD-hard for absolute constant epsilon, showing the linearity restriction is needed.
• Existence of epsilon-approximate EVI solutions holds for measurable F and Lipschitz deviations, even when the VI itself has no solution (e.g., sign function example).

Surprising findings

• Linear-Phi EVI solutions can be a strict subset of linear correlated equilibria even in normal-form games, and their marginal set can be non-polyhedral.
• Exact EVI solutions need not exist for discontinuous F, and there exist EVI instances with no approximate solution when deviations are continuous but F is piecewise constant.

Limitations

• Algorithms rely on the ellipsoid method, which is slow in practice; the regret-based alternative has poly(1/epsilon) complexity.
• Exact solutions are not guaranteed; only epsilon-approximate solutions are obtained, and exact solutions may require irrational points.
• Open question whether the framework extends to deviations decomposable across players when epsilon is small.

Experimental setup

Baselines: variational inequalities coarse correlated equilibria correlated equilibria linear correlated equilibria

Builds on: ellipsoid against hope correlated equilibrium Phi-regret minimization smoothness framework

Closest papers by meaning

• Robust Equilibria in Continuous Games: From Strategic to Dynamic Robustness (NeurIPS 2025 · similarity 0.86)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.85)
• Last-Iterate Convergence for Generalized Frank-Wolfe in Monotone Variational Inequalities (NeurIPS 2024 · similarity 0.85)
• Generalized Smooth Stochastic Variational Inequalities: Almost Sure Convergence and Convergence Rates (NeurIPS 2026 · similarity 0.85)
• No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.85)
• Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.85)