Expected Variational Inequalities

Brian Hu Zhang, Ioannis Anagnostides, Emanuel Tewolde, Ratip Emin Berker, Gabriele Farina, Vincent Conitzer, Tuomas Sandholm
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:74422-74446, 2025.

Abstract

Variational inequalities (VIs) encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning. However, their considerable expressivity comes at the cost of computational intractability. In this paper, we introduce and analyze a natural relaxation—which we refer to as expected variational inequalities (EVIs)—where the goal is to find a distribution that satisfies the VI constraint in expectation. By adapting recent techniques from game theory, we show that, unlike VIs, EVIs can be solved in polynomial time under general (nonmonotone) operators. EVIs capture the seminal notion of correlated equilibria, but enjoy a greater reach beyond games. We also employ our framework to capture and generalize several existing disparate results, including from settings such as smooth games, and games with coupled constraints or nonconcave utilities.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-zhang25a, title = {Expected Variational Inequalities}, author = {Zhang, Brian Hu and Anagnostides, Ioannis and Tewolde, Emanuel and Berker, Ratip Emin and Farina, Gabriele and Conitzer, Vincent and Sandholm, Tuomas}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {74422--74446}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/zhang25a/zhang25a.pdf}, url = {https://proceedings.mlr.press/v267/zhang25a.html}, abstract = {Variational inequalities (VIs) encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning. However, their considerable expressivity comes at the cost of computational intractability. In this paper, we introduce and analyze a natural relaxation—which we refer to as expected variational inequalities (EVIs)—where the goal is to find a distribution that satisfies the VI constraint in expectation. By adapting recent techniques from game theory, we show that, unlike VIs, EVIs can be solved in polynomial time under general (nonmonotone) operators. EVIs capture the seminal notion of correlated equilibria, but enjoy a greater reach beyond games. We also employ our framework to capture and generalize several existing disparate results, including from settings such as smooth games, and games with coupled constraints or nonconcave utilities.} }
Endnote
%0 Conference Paper %T Expected Variational Inequalities %A Brian Hu Zhang %A Ioannis Anagnostides %A Emanuel Tewolde %A Ratip Emin Berker %A Gabriele Farina %A Vincent Conitzer %A Tuomas Sandholm %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-zhang25a %I PMLR %P 74422--74446 %U https://proceedings.mlr.press/v267/zhang25a.html %V 267 %X Variational inequalities (VIs) encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning. However, their considerable expressivity comes at the cost of computational intractability. In this paper, we introduce and analyze a natural relaxation—which we refer to as expected variational inequalities (EVIs)—where the goal is to find a distribution that satisfies the VI constraint in expectation. By adapting recent techniques from game theory, we show that, unlike VIs, EVIs can be solved in polynomial time under general (nonmonotone) operators. EVIs capture the seminal notion of correlated equilibria, but enjoy a greater reach beyond games. We also employ our framework to capture and generalize several existing disparate results, including from settings such as smooth games, and games with coupled constraints or nonconcave utilities.
APA
Zhang, B.H., Anagnostides, I., Tewolde, E., Berker, R.E., Farina, G., Conitzer, V. & Sandholm, T.. (2025). Expected Variational Inequalities. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:74422-74446 Available from https://proceedings.mlr.press/v267/zhang25a.html.

Related Material