Expected Variational Inequalities

Expected Variational Inequalities

Speakers: Brian Zhang, Ioannis Anagnostides, Emanuel Tewolde, Ratip Emin Berker, Gabriele Farina, Vincent Conitzer, Tuomas Sandholm

Conference: ICML 2025

YouTube: https://slideslive.com/39044058

Overview

Variational Inequalities (VIs) represent a fundamental and highly expressive framework in mathematics and computer science, capable of modeling a vast array of problems from optimization to game theory. At its core, a VI seeks a point x within a set X such that the inner product of an operator F(x) and any deviation x' - x is non-negative. This general formulation elegantly captures first-order optimality conditions for convex optimization problems and, notably, Nash equilibria in game theory. However, the very generality that makes VIs so powerful also renders them notoriously difficult to solve in practice, often being PPAD-hard even in seemingly simple settings like multilinear games.

In this illuminating talk presented by Brian Zhang at ICML 2025, a novel relaxation of the classic VI problem is introduced: the Expected Variational Inequality (EVI). This framework aims to address the computational intractability of VIs by relaxing the solution concept from a single point to a distribution over points, and by allowing deviations to be arbitrary functions of the current point, rather than just other points. The central contribution of this work is demonstrating that, under specific and practically relevant conditions—namely, when the set of allowed deviation functions (phi) is restricted to linear maps—EVI problems become efficiently solvable, offering a significant breakthrough for a class of problems previously considered intractable.

The work by Zhang and his collaborators (Ioannis Anagnostides, Emanuel Tewolde, Ratip Emin Berker, Gabriele Farina, Vincent Conitzer, and Tuomas Sandholm) proposes a polynomial-time algorithm for finding approximate EVI solutions, thereby opening new avenues for tackling complex equilibrium and optimization problems. While primarily theoretical, the implications are profound, extending existing results in game theory for correlated equilibria and providing the first efficient algorithm for a broad class of quasi-convex optimization problems. This research not only provides a powerful new tool for analyzing equilibrium concepts but also refines our understanding of the boundary between tractability and intractability in the vast landscape of variational problems.

Background

▶ Watch: Introduction and Variational Inequality (VI) definition (0:00)

The concept of a Variational Inequality (VI) serves as a cornerstone for many problems across diverse fields. Formally, a VI is defined by a set X and an operator F. The objective is to find a point x* in X such that for all x' in X, the inner product ⟨F(x*), x' - x*⟩ ≥ 0. This seemingly abstract definition encapsulates a remarkable variety of specific problems.

Perhaps the most intuitive example is first-order optimization. If the operator F is the gradient ∇f of a convex function f, then the VI condition ⟨∇f(x*), x' - x*⟩ ≥ 0 for all x' in X is precisely the first-order optimality condition for x* to be a local (and for convex f, global) minimum of f over the set X. This connection immediately highlights the importance of VIs in the design and analysis of optimization algorithms.

Another critical application, and one that heavily informs the intuition behind the EVI framework, comes from game theory. In a game, if F represents the aggregate "incentive to deviate" for players, then the solutions to the corresponding VI problem are precisely the Nash equilibria of the game. A Nash equilibrium is a set of strategies where no player can improve their outcome by unilaterally changing their strategy, assuming other players' strategies remain fixed. The wide applicability of VIs to model strategic interactions, economic equilibria, and various engineering problems underscores their foundational significance.

Despite their expressive power, VIs are notoriously difficult to solve in general. The computational hardness stems directly from their ability to capture complex fixed-point problems. As highlighted in the talk, even when the operator F is multilinear—a common structure found in many game-theoretic settings—finding a solution to a VI is PPAD-hard. The complexity class PPAD (Polynomial Parity Argument on Directed graphs) is known for problems that are believed to be computationally intractable, meaning no polynomial-time algorithm is expected to exist. This inherent hardness motivates the search for meaningful relaxations that can still be solved efficiently, while retaining enough of the original problem's structure to be useful. The EVI framework emerges precisely from this need to find a balance between expressiveness and computational tractability.

Key Findings

▶ Watch: EVI relationship to correlated equilibria in games (4:00)

The central innovation presented in this talk is the introduction of Expected Variational Inequalities (EVIs) as a tractable relaxation of the generally intractable VI problem. The core idea behind EVI is to generalize the solution concept in two fundamental ways, moving beyond the limitations of finding a single deterministic point x.

First, instead of seeking a single point x, an EVI solution is a distribution over points mu. This means the solution is not a specific action or strategy, but rather a probability distribution over possible actions or strategies. This relaxation is akin to moving from pure strategy Nash equilibria to mixed strategy Nash equilibria, or more broadly, to correlated equilibria in game theory, where randomness plays a key role.

Second, the condition for deviation is generalized. In a standard VI, the condition ⟨F(x), x' - x⟩ ≥ 0 must hold for all points x' in the set X. In an EVI, this x' is replaced by an arbitrary function phi(x) from a predefined set Phi. The EVI condition becomes E_{x~mu}[⟨F(x), phi(x) - x⟩] ≥ -epsilon for all phi in Phi. This modification allows for more complex "deviations" where the alternative action phi(x) can depend on the current state x. The speaker notes that if Phi were restricted to constant functions (i.e., phi(x) = x' for some constant x'), the EVI problem would reduce to the classic VI problem, albeit with an expectation over x. By varying the richness of the set Phi, one can control the tightness of the relaxation; a larger Phi yields a tighter, potentially harder, problem.

A crucial finding is that EVIs indeed relax VIs: if x is a VI solution, then the point distribution concentrated on x is a valid EVI solution. Conversely, if Phi is sufficiently rich (e.g., containing all possible functions), EVIs can recover VIs. This establishes EVI as a legitimate generalization that encompasses the original problem.

Regarding the existence of solutions, the talk highlights that approximate EVI solutions are guaranteed to exist for any positive epsilon, provided that every function in the set Phi is Lipschitz continuous. This is a significant theoretical guarantee, ensuring that the problem is well-posed under reasonable conditions.

The most impactful finding, however, concerns the efficient computability of EVI solutions. While EVIs can still capture fixed-point problems and are thus hard in their most general form, the main result is that they become efficiently computable under a specific, yet powerful, restriction: when the set Phi contains only linear maps. Under this condition, the authors demonstrate a polynomial-time algorithm (in the dimension and log(1/epsilon)) that can compute an epsilon-EVI solution. This algorithm relies on a separation oracle for X and an evaluation oracle for F.

The practical implications of this result are manifold:

1. Game Theory Generalizations: The algorithm can recover known polynomial-time results for first-order linear correlated equilibria and zero-sum polymatrix games. It also introduces the concept of anonymous correlated equilibrium, a slightly tighter solution concept than standard correlated equilibrium, where players can deviate based on linear functions of other players' recommended actions.
2. Quasi-convex Optimization: For the first time, an efficient algorithm is provided for quasi-convex optimization when F is the gradient of a quasi-convex function. In this specific setting, EVI solutions correspond precisely to distributions over global minima of the quasi-convex function. This offers a novel approach to a class of optimization problems that are more general than convex optimization but still possess useful structure.

In essence, the key findings establish EVIs as a powerful new framework that strikes a balance between the expressiveness of VIs and the computational tractability required for practical applications, particularly when linear function mappings are applicable.

Technical Deep Dive

▶ Watch: Main result: Efficient EVI computation for linear maps (5:30)

The technical core of the talk revolves around proving the efficient computability of EVI solutions when the set of deviation functions Phi is restricted to linear maps. This proof builds upon and generalizes existing techniques from game theory, specifically the ellipsoid-against-hope algorithm used for computing correlated equilibria.

Let's first formalize the EVI problem with linear maps. We are looking for a distribution mu over X such that for all linear maps K (where phi(x) = Kx), we have E_{x~mu}[⟨F(x), Kx - x⟩] ≥ -epsilon. The speaker simplifies the linear map phi to Kx, where K is a matrix.

The intuition for the proof strategy is to transform the EVI problem into a dual problem. Instead of directly searching for mu, the algorithm tries to find a linear map K that "proves" that no EVI solution exists. If such a K could be found, it would mean the EVI problem is infeasible. However, the authors have already proven that EVI solutions exist under the Lipschitz condition (and specifically for linear Phi). Therefore, the dual problem must be infeasible. The crucial insight is that a certificate of infeasibility for the dual problem will precisely yield an EVI solution.

The dual problem can be formulated as finding a linear map K such that:

1. Kx ∈ X for all x ∈ X (the linear map must map points within the set X back into X).
2. ⟨F(x), Kx - x⟩ < -epsilon for all x ∈ X (this condition, if satisfied, would mean that for any x, there's a profitable deviation Kx that makes the inner product strongly negative, implying no EVI solution could exist).

Since the EVI problem is known to be feasible, this dual problem is infeasible. To find a certificate of its infeasibility, the authors propose using the ellipsoid algorithm. The ellipsoid algorithm is a general method for convex optimization (or feasibility problems) that, given a convex set, can either find a point within it or prove that the set is empty. For the ellipsoid algorithm to work, a separation oracle is required. A separation oracle, when given a point, must either confirm that the point is within the feasible set or provide a hyperplane that separates the point from the set.

The core of the proof then lies in constructing such a separation oracle for the dual problem, which involves checking the two conditions mentioned above:

1. Separation Oracle for Kx ∈ X for all x ∈ X:

This condition checks if a given linear map K maps X to X. The speaker simplifies this for the case where X is a polytope. If X is a polytope defined by a finite set of linear constraints, then checking Kx ∈ X for all x ∈ X reduces to checking a finite number of linear constraints on K. This can be done directly and efficiently. The paper generalizes this to cases where X is defined by a more general separation or optimization oracle.

2. Separation Oracle for ⟨F(x), Kx - x⟩ < -epsilon:

This condition is equivalent to finding if there exists an x such that ⟨F(x), Kx - x⟩ < -epsilon. The trick here is to consider a special case: if K admits a fixed point, i.e., an x such that Kx = x.

• Since K is a linear map and X is compact and convex (implied by X being a polytope), Kakutani's fixed-point theorem (or Brouwer's for continuous maps on convex, compact sets) implies that such a fixed point x must exist if K maps X to X.
• Furthermore, because K is linear, finding such a fixed point x (i.e., solving Kx = x subject to x ∈ X) can be achieved by solving a linear program.
• If such a fixed point x exists, then Kx - x = 0, which means ⟨F(x), Kx - x⟩ = 0. Since 0 ≥ -epsilon (for epsilon > 0), this x does not violate the ⟨F(x), Kx - x⟩ < -epsilon condition. Therefore, if K maps X to X and has a fixed point, it does not satisfy the second dual condition. This means that finding such a fixed point serves as a valid "non-violation" certificate for the second constraint of the dual problem. If no such fixed point can be found within X, or if K does not map X to X, then a violation is detected.

By combining these two separation oracles, the ellipsoid algorithm can be run on the dual problem. Because the dual problem is infeasible, the ellipsoid algorithm will eventually terminate by declaring it so, and in the process, it will provide a certificate of infeasibility. This certificate, as previously established, is precisely an epsilon-EVI solution. The polynomial-time complexity (in dimension and log(1/epsilon)) arises from the properties of the ellipsoid algorithm.

This technical approach elegantly links the problem of finding EVI solutions to the well-understood framework of convex optimization and fixed-point theory, leveraging known algorithms to establish tractability for a significant class of problems.

Experimental Setup & Results

▶ Watch: Solving EVI via a dual problem and infeasibility (7:00)

The talk explicitly clarifies the nature of this research by stating, "Okay so this is a primarily theoretical paper. Ellipsoid yeah yeah yeah. So these yeah Ellipsoid is not very practical in in the real world. Like I I understand this these results are mostly Okay theoretical. Thank you."

This statement confirms that the work presented focuses on the theoretical existence and complexity bounds of algorithms for solving Expected Variational Inequalities, rather than empirical performance or practical implementation details. Therefore, there are no experimental results, benchmarks, dataset comparisons, or hardware specifications to report. The paper does not delve into specific model architectures, training/inference techniques, or systems design in the context of empirical evaluation.

The "results" in this context are primarily theoretical guarantees:

• Existence Proofs: Demonstrating that approximate EVI solutions exist under reasonable conditions (Lipschitz continuity of phi).
• Tractability Proofs: Establishing that EVI problems are solvable in polynomial time when phi consists of linear maps, given access to appropriate oracles. This includes the log(1/epsilon) dependence for approximation accuracy.
• Recovery of Known Results: Showing that the EVI framework generalizes and recovers known polynomial-time algorithms for specific game-theoretic equilibria (e.g., first-order linear correlated equilibria, zero-sum polymatrix games).
• Novel Algorithm for Quasi-convex Optimization: Providing the first known efficient algorithm for finding distributions over global minima in quasi-convex optimization.

While the ellipsoid algorithm is theoretically polynomial-time, it is well-known for its slow convergence in practice and is rarely used for real-world optimization compared to methods like interior-point methods or first-order gradient-based techniques. The authors acknowledge this practical limitation, emphasizing that their contribution is primarily in establishing a theoretical upper bound on complexity and demonstrating a new class of problems that are, in principle, tractable. Future work would likely involve developing more practically efficient algorithms that leverage the insights from this theoretical foundation.

Practical Implications

▶ Watch: Separation oracle for ellipsoid algorithm on the dual (8:00)

The introduction of Expected Variational Inequalities (EVIs) and the proof of their efficient computability for linear maps have several significant practical implications, despite the theoretical nature of the underlying algorithm.

For Practitioners and Model Builders:

• Expanded Solution Space: EVIs offer a more flexible solution concept than traditional VIs, allowing for distributions over strategies or points rather than single deterministic choices. This is particularly relevant in domains like game theory, where mixed strategies and correlated equilibria are essential for modeling realistic behavior.
• New Tools for Hard Problems: For problems that are classically PPAD-hard (like finding Nash equilibria or solving general VIs), EVIs provide a path to efficient approximate solutions under specific, yet meaningful, relaxations. This means practitioners might now have a computationally feasible way to analyze or design systems that previously faced intractable equilibrium challenges, provided the "linear map" assumption holds.
• Quasi-convex Optimization: The most direct practical utility might be in quasi-convex optimization. Many real-world problems exhibit quasi-convexity (e.g., utility functions in economics, certain performance metrics in engineering) but are not necessarily convex. The ability to efficiently compute distributions over global minima for these problems is a significant advance, offering a new optimization paradigm for a broader class of functions.
• Understanding Equilibrium Concepts: The work introduces the concept of anonymous correlated equilibrium, which is slightly tighter than standard correlated equilibria. This provides a new lens through which to analyze strategic interactions and could inspire new mechanisms or solution concepts in game theory and multi-agent systems.

For Infra Teams and Deployers:

• Theoretical Foundation for Future Algorithms: While the ellipsoid algorithm itself is not practical for large-scale deployment, this work lays the theoretical groundwork. It demonstrates that a polynomial-time algorithm exists, which can motivate the development of more practically efficient algorithms (e.g., first-order methods tailored to the EVI structure) that leverage these theoretical insights. Infra teams may eventually benefit from optimized solvers for EVI-like problems.
• Tradeoffs and Limitations: The talk explicitly highlights a crucial limitation: the efficient computability rapidly breaks down when moving beyond linear maps for the set Phi. As the speaker notes, allowing even piecewise linear maps quickly reintroduces fixed-point hardness. This means that for problems where non-linear deviations are essential, the EVI framework, as currently presented for tractability, may not apply. Practitioners must carefully assess whether the "linear map" assumption is a reasonable approximation for their specific problem domain.
• Approximation vs. Exactness: The algorithm computes an epsilon-EVI solution, meaning it finds an approximate solution. For many real-world applications, an epsilon-approximation is sufficient, but the specific epsilon tolerance and its impact on system behavior must be considered.

Future Directions and Connections:

The talk briefly mentions future research, including exploring other settings where the EVI problem might be useful and highlighting a connection to the Minty condition. The Minty condition is a well-known concept in variational inequalities, and the EVI problem is shown to be the dual to the Minty condition. This relationship has already yielded the first polynomial-time algorithm for solving VIs under the Minty condition in a subsequent preprint. This cross-pollination of ideas between EVI and established VI theory suggests a rich area for further theoretical and algorithmic development.

In summary, while the immediate practical deployment of the ellipsoid-based EVI solver is limited, the theoretical breakthrough fundamentally changes our understanding of the tractability of variational problems. It provides a principled way to relax hard problems and offers new algorithmic avenues for specific, important classes of optimization and game-theoretic challenges.

Key Takeaways

• Expected Variational Inequalities (EVIs) as a Tractable Relaxation: EVIs generalize classic Variational Inequalities (VIs) by seeking a distribution over points and allowing deviations based on functions, providing a computationally feasible alternative to generally PPAD-hard VI problems.
• Efficient Solvability for Linear Maps: The core contribution is a polynomial-time algorithm (in dimension and log(1/epsilon)) for finding approximate EVI solutions when the set of deviation functions (Phi) is restricted to linear maps.
• Ellipsoid Algorithm and Dual Problem: The algorithm works by generalizing the ellipsoid-against-hope method from game theory, solving a dual problem to find a certificate of infeasibility, which in turn yields an EVI solution, relying on a separation oracle built upon fixed-point computation.
• Generalization of Game Theory Concepts: The EVI framework recovers and generalizes known polynomial-time algorithms for correlated equilibria in game theory, and introduces "anonymous correlated equilibria" as a tighter solution concept.
• First Efficient Algorithm for Quasi-convex Optimization: This work provides the first efficient algorithm for finding distributions over global minima in quasi-convex optimization, significantly expanding the scope of efficiently solvable optimization problems.
• Theoretical Nature with Practical Limitations: While a theoretical breakthrough, the reliance on the ellipsoid algorithm means the proposed method is not practically efficient for real-world deployment, serving primarily as a proof of concept for tractability. Hardness quickly returns for non-linear deviation functions.

About the Speaker(s)

The talk was presented by Brian Zhang, who is one of the lead authors on this joint work. The extensive list of co-authors includes Ioannis Anagnostides, Emanuel Tewolde, Ratip Emin Berker, Gabriele Farina, Vincent Conitzer, and Tuomas Sandholm. While specific affiliations were not detailed in the transcript, the caliber of the co-authors, particularly Vincent Conitzer and Tuomas Sandholm (both highly distinguished researchers in AI, game theory, and economics), suggests that this research originates from a leading academic institution, likely Carnegie Mellon University where Tuomas Sandholm is a professor, or other prominent research labs given the collaborative nature of the work. The team brings together expertise in theoretical computer science, game theory, and optimization, which is evident in the sophisticated mathematical and algorithmic foundations of the EVI framework.