Bridging the Gap Between Nash Equilibria and Coarse-Correlated Equilibria

With the growing importance of computational methods in game theory, much recent work has been devoted to studying the computational complexity of various equilibrium concepts, with particular focus on the standard notions of Nash equilibrium and coarse-correlated equilibrium (CCE). In particular, it has been shown that finding Nash equilibria is computationally hard while CCEs can be efficiently computed. However, there exists a wide gap between these two equilibrium concepts, and the computational complexity of finding equilibria weaker than Nash equilibria but stronger than CCEs is still poorly understood.

In this paper, we investigate a class of equilibria called rank-k CCEs that lie in between Nash equilibria and CCEs. We first provide a graphical characterization of rank-2 CCEs in Rock Paper Scissors and show that the region is non-convex. Furthermore, we show that the unique Nash equilibrium occurs precisely at a singular point in the region of rank-2 CCEs. We then examine the close relationship between no-regret online learning algorithms and rank-k CCEs. We present the results of our experiment tracking the number of periods online learning takes to converge to a CCE as the number of strategies grows and provide evidence to support the conjecture that the T = Oupper bound is in fact tight. This result also suggests that finding rank-O(1) CCEs is likely computationally hard.

Finally, we present our initial attempt at proving that finding rank-2 CCEs is PPAD-hard. To that end, we try to follow the methods and ideas presented by Constantinos Daskalakis in his proof showing that finding Nash equilibria is PPAD-hard [Das08]. However, rank-2 CCEs introduce a series of complications that make it difficult to replicate the proof, and we conclude with a discussion of these challenges.