Equilibrium Computation in Multidimensional Congestion Games: CSP and Learning Dynamics Approaches

Mohammad T. Irfan, Hau Chan, Jared Soundy
Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, PMLR 244:1751-1779, 2024.

Abstract

We present algorithms of two flavors{—}one rooted in constraint satisfaction problems (CSPs) and the other in learning dynamics{—}to compute pure-strategy Nash equilibrium (PSNE) in k-dimensional congestion games (k-DCGs) and their variants. The two algorithmic approaches are driven by whether or not a PSNE is guaranteed to exist. We first show that deciding the existence of a PSNE in a k-DCG is NP-complete even when players have binary and unit demand vectors. For general cost functions (potentially non-monotonic), we devise a new CSP-inspired algorithmic framework for PSNE computation, leading to algorithms that run in polynomial time under certain assumptions while offering exponential savings over standard CSP algorithms. We further refine these algorithms for variants of k-DCGs. Our experiments demonstrate the effectiveness of this new CSP framework for hard, non-monotonic k-DCGs. We then provide learning dynamics-based PSNE computation algorithms for linear and exponential cost functions. These algorithms run in polynomial time under certain assumptions. For general cost, we give a learning dynamics algorithm for an (\ensuremath{(\alpha, \beta)})-approximate PSNE (for certain \ensuremath{\alpha} and \ensuremath{\beta}). Lastly, we also devise polynomial-time algorithms for structured demands and cost functions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v244-irfan24a, title = {Equilibrium Computation in Multidimensional Congestion Games: CSP and Learning Dynamics Approaches}, author = {Irfan, Mohammad T. and Chan, Hau and Soundy, Jared}, booktitle = {Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence}, pages = {1751--1779}, year = {2024}, editor = {Kiyavash, Negar and Mooij, Joris M.}, volume = {244}, series = {Proceedings of Machine Learning Research}, month = {15--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v244/main/assets/irfan24a/irfan24a.pdf}, url = {https://proceedings.mlr.press/v244/irfan24a.html}, abstract = {We present algorithms of two flavors{—}one rooted in constraint satisfaction problems (CSPs) and the other in learning dynamics{—}to compute pure-strategy Nash equilibrium (PSNE) in k-dimensional congestion games (k-DCGs) and their variants. The two algorithmic approaches are driven by whether or not a PSNE is guaranteed to exist. We first show that deciding the existence of a PSNE in a k-DCG is NP-complete even when players have binary and unit demand vectors. For general cost functions (potentially non-monotonic), we devise a new CSP-inspired algorithmic framework for PSNE computation, leading to algorithms that run in polynomial time under certain assumptions while offering exponential savings over standard CSP algorithms. We further refine these algorithms for variants of k-DCGs. Our experiments demonstrate the effectiveness of this new CSP framework for hard, non-monotonic k-DCGs. We then provide learning dynamics-based PSNE computation algorithms for linear and exponential cost functions. These algorithms run in polynomial time under certain assumptions. For general cost, we give a learning dynamics algorithm for an (\ensuremath{(\alpha, \beta)})-approximate PSNE (for certain \ensuremath{\alpha} and \ensuremath{\beta}). Lastly, we also devise polynomial-time algorithms for structured demands and cost functions.} }
Endnote
%0 Conference Paper %T Equilibrium Computation in Multidimensional Congestion Games: CSP and Learning Dynamics Approaches %A Mohammad T. Irfan %A Hau Chan %A Jared Soundy %B Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2024 %E Negar Kiyavash %E Joris M. Mooij %F pmlr-v244-irfan24a %I PMLR %P 1751--1779 %U https://proceedings.mlr.press/v244/irfan24a.html %V 244 %X We present algorithms of two flavors{—}one rooted in constraint satisfaction problems (CSPs) and the other in learning dynamics{—}to compute pure-strategy Nash equilibrium (PSNE) in k-dimensional congestion games (k-DCGs) and their variants. The two algorithmic approaches are driven by whether or not a PSNE is guaranteed to exist. We first show that deciding the existence of a PSNE in a k-DCG is NP-complete even when players have binary and unit demand vectors. For general cost functions (potentially non-monotonic), we devise a new CSP-inspired algorithmic framework for PSNE computation, leading to algorithms that run in polynomial time under certain assumptions while offering exponential savings over standard CSP algorithms. We further refine these algorithms for variants of k-DCGs. Our experiments demonstrate the effectiveness of this new CSP framework for hard, non-monotonic k-DCGs. We then provide learning dynamics-based PSNE computation algorithms for linear and exponential cost functions. These algorithms run in polynomial time under certain assumptions. For general cost, we give a learning dynamics algorithm for an (\ensuremath{(\alpha, \beta)})-approximate PSNE (for certain \ensuremath{\alpha} and \ensuremath{\beta}). Lastly, we also devise polynomial-time algorithms for structured demands and cost functions.
APA
Irfan, M.T., Chan, H. & Soundy, J.. (2024). Equilibrium Computation in Multidimensional Congestion Games: CSP and Learning Dynamics Approaches. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 244:1751-1779 Available from https://proceedings.mlr.press/v244/irfan24a.html.

Related Material