Computing Exact Nash Equilibria in Graphical Games: A Geometric Approach to Paths, Stars, and Caterpillars

Evan Lucca, Mohammad T. Irfan, Luis E. Ortiz
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:4027-4066, 2026.

Abstract

Computing mixed-strategy {Nash} equilibria (MSNE) in graphical games being PPAD-complete, special types of graphical games have received a lot of attention over the years. We present a number of new results using a geometric approach to computing exact MSNE. We consider graphical games of several structures, such as paths, stars, and caterpillars. We also consider graphical polymatrix games on these structures. We provide a new tight upper bounding result for path-structured graphical games and a new quadratic-time algorithm for representing all MSNE and computing one for path-structured polymatrix games. For star graphical games, our algorithm is logarithmic time for non-degenerate cases (i.e., without symmetric players) and linear time for general cases with symmetric players. Interestingly, having more symmetric players makes the computation more expensive. For star polymatrix games, our algorithm is linear in the input size. For the open problems on caterpillar polymatrix and graphical games, our algorithms are polynomial time in the input size.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-lucca26a, title = {Computing Exact {Nash} Equilibria in Graphical Games: A Geometric Approach to Paths, Stars, and Caterpillars}, author = {Lucca, Evan and Irfan, Mohammad T. and Ortiz, Luis E.}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {4027--4066}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/lucca26a/lucca26a.pdf}, url = {https://proceedings.mlr.press/v337/lucca26a.html}, abstract = {Computing mixed-strategy {Nash} equilibria (MSNE) in graphical games being PPAD-complete, special types of graphical games have received a lot of attention over the years. We present a number of new results using a geometric approach to computing exact MSNE. We consider graphical games of several structures, such as paths, stars, and caterpillars. We also consider graphical polymatrix games on these structures. We provide a new tight upper bounding result for path-structured graphical games and a new quadratic-time algorithm for representing all MSNE and computing one for path-structured polymatrix games. For star graphical games, our algorithm is logarithmic time for non-degenerate cases (i.e., without symmetric players) and linear time for general cases with symmetric players. Interestingly, having more symmetric players makes the computation more expensive. For star polymatrix games, our algorithm is linear in the input size. For the open problems on caterpillar polymatrix and graphical games, our algorithms are polynomial time in the input size.} }
Endnote
%0 Conference Paper %T Computing Exact Nash Equilibria in Graphical Games: A Geometric Approach to Paths, Stars, and Caterpillars %A Evan Lucca %A Mohammad T. Irfan %A Luis E. Ortiz %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-lucca26a %I PMLR %P 4027--4066 %U https://proceedings.mlr.press/v337/lucca26a.html %V 337 %X Computing mixed-strategy {Nash} equilibria (MSNE) in graphical games being PPAD-complete, special types of graphical games have received a lot of attention over the years. We present a number of new results using a geometric approach to computing exact MSNE. We consider graphical games of several structures, such as paths, stars, and caterpillars. We also consider graphical polymatrix games on these structures. We provide a new tight upper bounding result for path-structured graphical games and a new quadratic-time algorithm for representing all MSNE and computing one for path-structured polymatrix games. For star graphical games, our algorithm is logarithmic time for non-degenerate cases (i.e., without symmetric players) and linear time for general cases with symmetric players. Interestingly, having more symmetric players makes the computation more expensive. For star polymatrix games, our algorithm is linear in the input size. For the open problems on caterpillar polymatrix and graphical games, our algorithms are polynomial time in the input size.
APA
Lucca, E., Irfan, M.T. & Ortiz, L.E.. (2026). Computing Exact Nash Equilibria in Graphical Games: A Geometric Approach to Paths, Stars, and Caterpillars. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:4027-4066 Available from https://proceedings.mlr.press/v337/lucca26a.html.

Related Material