2024-09-12-irfan24a.md

title	abstract	openreview	section	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Equilibrium Computation in Multidimensional Congestion Games: CSP and Learning Dynamics Approaches	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.	9Sw5gGPzQ1	Papers	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	irfan24a	0	Equilibrium Computation in Multidimensional Congestion Games: CSP and Learning Dynamics Approaches	1751	1779	1751-1779	1751	false	Irfan, Mohammad T. and Chan, Hau and Soundy, Jared	given family Mohammad T. Irfan given family Hau Chan given family Jared Soundy	2024-09-12		Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence	244	inproceedings	date-parts 2024 9 12	https://raw.githubusercontent.com/mlresearch/v244/main/assets/irfan24a/irfan24a.pdf