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 June 2015 | Submitted
Book Section - Chapter Open

Finding Any Nontrivial Coarse Correlated Equilibrium Is Hard

Abstract

One of the most appealing aspects of the (coarse) correlated equilibrium concept is that natural dynamics quickly arrive at approximations of such equilibria, even in games with many players. In addition, there exist polynomial-time algorithms that compute exact (coarse) correlated equilibria. In light of these results, a natural question is how good are the (coarse) correlated equilibria that can arise from any efficient algorithm or dynamics. In this paper we address this question, and establish strong negative results. In particular, we show that in multiplayer games that have a succinct representation, it is NP-hard to compute any coarse correlated equilibrium (or approximate coarse correlated equilibrium) with welfare strictly better than the worst possible. The focus on succinct games ensures that the underlying complexity question is interesting; many multiplayer games of interest are in fact succinct. Our results imply that, while one can efficiently compute a coarse correlated equilibrium, one cannot provide any nontrivial welfare guarantee for the resulting equilibrium, unless P=NP. We show that analogous hardness results hold for correlated equilibria, and persist under the egalitarian objective or Pareto optimality. To complement the hardness results, we develop an algorithmic framework that identifies settings in which we can efficiently compute an approximate correlated equilibrium with near-optimal welfare. We use this framework to develop an efficient algorithm for computing an approximate correlated equilibrium with near-optimal welfare in aggregative games.

Additional Information

© 2015 ACM. The authors thank Nikhil Bansal for helpful discussions. This work was supported by NSF grants CNS-0846025, CCF-1101470, and CNS-1254169, along with a Microsoft Research Faculty Fellowship, a Google Faculty Research Award, and a Linde/SISL Postdoctoral Fellowship. Katrina Ligett gratefully acknowledges the support of the Charles Lee Powell Foundation.

Attached Files

Submitted - 1504.06314v1.pdf

Files

1504.06314v1.pdf
Files (239.3 kB)
Name Size Download all
md5:f5830e16f7c47bdcf1ec9db2757d9460
239.3 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 23, 2023