Expected Variational Inequalities

We thank the reviewer for their feedback and service.

"To the best of my understanding, if $\Phi$ contains all functions [...] EVIs would correspond to VIs if $\mu$ is restricted to Dirac measures."

We clarify that this equivalence holds without any restriction on $\mu$; it doesn’t have to be a Dirac measure.

"Thus I am not yet convinced of the relevance of the solution concept"

Our main positive result captures the setting where $\Phi$ contains all linear functions, which we argue is a strong solution concept. Even in the special case of normal-form games, it is tighter (that is, closer to Nash equilibria) than the usual notion of a correlated equilibrium (see Figure 1). Moreover, our hardness results preclude efficient computation when $\Phi$ contains even quadratic functions; as a result, there is a fundamental sense in which our solution concept is the best one can hope for using efficient algorithms.

"In the setting of games: Is there a clear relation to the $\Phi$-equilibria considered in Cai et al.?"

In the special case of nonconcave games, our solution captures the one considered by Cai et al., as we show and discuss in Appendix G. In fact, when $\Phi$ contains all linear functions, our solution concept is tighter (see Figure 1). We also argue that our definition is more natural and simple, while also applying to any variational inequality problem. Besides those points, we provide significant algorithmic improvements compared to Cai et al., as we point out in Appendix G.

"Is there a similar solution concept in optimization to which you can relate?"

To the best of our knowledge, there is no existing solution concept in optimization that directly relates to $\Phi$-EVIs, except in more specific classes of problems (see Section 6). Given how natural this concept is, we believe that introducing it to the optimization community is an important contribution.

We thank the reviewer for their feedback and service.

We are happy to adjust the writing style and follow any other suggestions for the revision. Regarding the bibliography, we follow the convention that page numbers are omitted for conference publications, which explains why some references have page numbers and others don’t. We are happy to change that if the reviewer finds it inconsistent.

We thank the reviewer for their feedback and service.

“It would be helpful if the authors could compare the strength of VI to EVI in terms of modeling power. For example, are there still many VI problems for which EVI suffices? Furthermore, are there any problems where EVI is actually more natural of a model than VI?”

This is a great question. If we look at the special case of games, $\Phi$-EVIs (which subsume correlated equilibria) are in many ways more natural than VIs (that is, Nash equilibria). Indeed, they often lead to better outcomes in terms of welfare as they enable correlation between the players, which in many applications is more reasonable than assuming that players are acting independently (a traffic light is a common example of a correlation device). This shows that there are problems in which EVIs are, in many ways, more natural than VIs. Furthermore, given how expressive games are from an optimization standpoint, we argue that this already makes a compelling case for EVIs compared to VIs. That being said, we believe that further understanding the power of EVIs and how they compare against VIs is an important question for follow-up work.