Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 10, 2015 | public
Book Section - Chapter Open

Approximating Nash Equilibria in Tree Polymatrix Games


We develop a quasi-polynomial time Las Vegas algorithm for approximating Nash equilibria in polymatrix games over trees, under a mild renormalizing assumption. Our result, in particular, leads to an expected polynomial-time algorithm for computing approximate Nash equilibria of tree polymatrix games in which the number of actions per player is a fixed constant. Further, for trees with constant degree, the running time of the algorithm matches the best known upper bound for approximating Nash equilibria in bimatrix games (Lipton, Markakis, and Mehta 2003). Notably, this work closely complements the hardness result of Rubinstein (2015), which establishes the inapproximability of Nash equilibria in polymatrix games over constant-degree bipartite graphs with two actions per player.

Additional Information

© 2015 Springer-Verlag Berlin Heidelberg. This work was supported by NSF grants CNS-0846025, CCF-1101470, CNS-1254169, SUTD grant SRG ESD 2015 097, along with a Microsoft Research Faculty Fellowship, a Google Faculty Research Award, a Linde/SISL Postdoctoral Fellowship and a CMI Wally Baer and Jeri Weiss postdoctoral fellowship. Katrina Ligett gratefully acknowledges the support of the Charles Lee Powell Foundation. The bulk of the work was conducted while Georgios Piliouras was a postdoctoral scholar at Caltech.

Attached Files

Submitted - 1604.02676.pdf


Files (185.8 kB)
Name Size Download all
185.8 kB Preview Download

Additional details

August 20, 2023
August 20, 2023