Finding any nontrivial coarse correlated equilibrium is hard

One of the most appealing aspects of correlated equilibria and coarse correlated equilibria 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 correlated and coarse correlated equilibria. However, in general these dynamics and algorithms do not provide a guarantee on the quality (say, in terms of social welfare) of the resulting equilibrium. In light of these results, a natural question is how good are the correlated and coarse correlated equilibria---in terms natural objectives such as social welfare or Pareto optimality---that can arise from any efficient algorithm or dynamics. 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. 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.

相关均衡和粗糙相关均衡最吸引人的特点之一是，即使在有众多参与者的博弈中，自然动态过程也能迅速趋近于这类均衡。此外，存在多项式时间算法来计算精确的相关均衡和粗糙相关均衡。然而，一般来说，这些动态过程和算法并不能保证所得均衡的质量（比如从社会福利的角度）。鉴于这些结果，一个自然的问题是，通过任何高效算法或动态过程所能得到的相关均衡和粗糙相关均衡，从社会福利或帕累托最优等自然目标来看，到底能有多好。 我们探讨了这个问题，并得出了有力的否定性结论。具体而言，我们表明，在具有简洁表示的多人博弈中，要计算出任何福利严格优于最差可能情况的粗糙相关均衡（或近似粗糙相关均衡）是NP难问题。关注简洁博弈能确保潜在的复杂性问题具有研究价值；实际上，许多令人关注的多人博弈都是简洁的。我们证明了类似的难解性结果也适用于相关均衡，并且在平等主义目标或帕累托最优条件下依然成立。 为了补充这些难解性结果，我们开发了一个算法框架，用于确定在哪些情形下我们能够高效计算出具有接近最优福利的近似相关均衡。我们利用这个框架，为聚合博弈开发出一种高效算法，用于计算具有接近最优福利的近似相关均衡。