Constrained Phi-Equilibria

Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, Francesco Trovò, Nicola Gatti
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:2184-2205, 2023.

Abstract

The computational study of equilibria involving constraints on players’ strategies has been largely neglected. However, in real-world applications, players are usually subject to constraints ruling out the feasibility of some of their strategies, such as, e.g., safety requirements and budget caps. Computational studies on constrained versions of the Nash equilibrium have lead to some results under very stringent assumptions, while finding constrained versions of the correlated equilibrium (CE) is still unexplored. In this paper, we introduce and computationally characterize constrained Phi-equilibria—a more general notion than constrained CEs—in normal-form games. We show that computing such equilibria is in general computationally intractable, and also that the set of the equilibria may not be convex, providing a sharp divide with unconstrained CEs. Nevertheless, we provide a polynomial-time algorithm for computing a constrained (approximate) Phi-equilibrium maximizing a given linear function, when either the number of constraints or that of players’ actions is fixed. Moreover, in the special case in which a player’s constraints do not depend on other players’ strategies, we show that an exact, function-maximizing equilibrium can be computed in polynomial time, while one (approximate) equilibrium can be found with an efficient decentralized no-regret learning algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-bernasconi23b, title = {Constrained Phi-Equilibria}, author = {Bernasconi, Martino and Castiglioni, Matteo and Marchesi, Alberto and Trov\`{o}, Francesco and Gatti, Nicola}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {2184--2205}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/bernasconi23b/bernasconi23b.pdf}, url = {https://proceedings.mlr.press/v202/bernasconi23b.html}, abstract = {The computational study of equilibria involving constraints on players’ strategies has been largely neglected. However, in real-world applications, players are usually subject to constraints ruling out the feasibility of some of their strategies, such as, e.g., safety requirements and budget caps. Computational studies on constrained versions of the Nash equilibrium have lead to some results under very stringent assumptions, while finding constrained versions of the correlated equilibrium (CE) is still unexplored. In this paper, we introduce and computationally characterize constrained Phi-equilibria—a more general notion than constrained CEs—in normal-form games. We show that computing such equilibria is in general computationally intractable, and also that the set of the equilibria may not be convex, providing a sharp divide with unconstrained CEs. Nevertheless, we provide a polynomial-time algorithm for computing a constrained (approximate) Phi-equilibrium maximizing a given linear function, when either the number of constraints or that of players’ actions is fixed. Moreover, in the special case in which a player’s constraints do not depend on other players’ strategies, we show that an exact, function-maximizing equilibrium can be computed in polynomial time, while one (approximate) equilibrium can be found with an efficient decentralized no-regret learning algorithm.} }
Endnote
%0 Conference Paper %T Constrained Phi-Equilibria %A Martino Bernasconi %A Matteo Castiglioni %A Alberto Marchesi %A Francesco Trovò %A Nicola Gatti %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-bernasconi23b %I PMLR %P 2184--2205 %U https://proceedings.mlr.press/v202/bernasconi23b.html %V 202 %X The computational study of equilibria involving constraints on players’ strategies has been largely neglected. However, in real-world applications, players are usually subject to constraints ruling out the feasibility of some of their strategies, such as, e.g., safety requirements and budget caps. Computational studies on constrained versions of the Nash equilibrium have lead to some results under very stringent assumptions, while finding constrained versions of the correlated equilibrium (CE) is still unexplored. In this paper, we introduce and computationally characterize constrained Phi-equilibria—a more general notion than constrained CEs—in normal-form games. We show that computing such equilibria is in general computationally intractable, and also that the set of the equilibria may not be convex, providing a sharp divide with unconstrained CEs. Nevertheless, we provide a polynomial-time algorithm for computing a constrained (approximate) Phi-equilibrium maximizing a given linear function, when either the number of constraints or that of players’ actions is fixed. Moreover, in the special case in which a player’s constraints do not depend on other players’ strategies, we show that an exact, function-maximizing equilibrium can be computed in polynomial time, while one (approximate) equilibrium can be found with an efficient decentralized no-regret learning algorithm.
APA
Bernasconi, M., Castiglioni, M., Marchesi, A., Trovò, F. & Gatti, N.. (2023). Constrained Phi-Equilibria. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:2184-2205 Available from https://proceedings.mlr.press/v202/bernasconi23b.html.

Related Material