WorksComputer Science
Settling the Support Complexity of Correlated Equilibria
Abstract
We study the support complexity of approximate correlated equilibria (CE) in two-player games, that is, the minimum number of pure action profiles that must be assigned positive probability to approximate a correlated equilibrium of a two-player matrix game. For -approximate coarse correlated equilibria, constant approximation is possible with support in games. For correlated equilibria, the best known upper bound was [Babichenko et al., 2014, 2017], but whether this bound was tight remained open. We establish a matching lower bound, resolving the open question of Ko and Schvartzman [2017]. Specifically, we show that, already for two-player zero-sum games, for every the worst-case correlated-equilibrium gap achievable by a distribution supported on at most pure profiles is which implies a worst-case support bound. The proof builds on a probabilistic-method construction based on random sign matrices.
Introduction
A correlated equilibrium, introduced by Aumann [ [4, 5], is a joint distribution over action profiles from which no player can improve by applying a recommendation-dependent deviation function. Exact correlated equilibria exist by the theorem of Hart and Schmeidler [ [6]. Unlike a Nash equilibrium, which requires players to randomize independently, a correlated equilibrium may use arbitrary correlation between the players’ actions. This additional freedom leads to a major computational difference. In an explicitly represented normal-form game, an exact correlated equilibrium can be found in polynomial time by linear programming, whereas computing a Nash equilibrium in a two-player bimatrix game is PPAD-complete [7, 8]. In this work, we analyze the difference between correlated and Nash equilibria from a different angle: whether correlation also leads to substantially sparser equilibrium representations. More precisely, how many pure action profiles are necessary and sufficient to support an -correlated equilibrium in the worst case?
This question is part of a long line of work on sparse equilibrium representations. In zero-sum games, Althöfer [ [9] and Lipton and Young [ [10] showed that each player has an -optimal minimax strategy with support . This small-support approach was extended from zero-sum games to general bimatrix games by Lipton et al. [ [11], who showed that every such game admits an -Nash equilibrium in which each player has support . Approximate Carathéodory theorems provide more general tools for obtaining sparse convex representations, with applications to sparse approximate equilibria in games [12, 13].
It is important here to distinguish the support of a mixed strategy from the support of a correlated distribution. For Nash equilibrium and minimax strategies, support is measured separately for each player. If two mixed strategies and each have support size at most , then their independent product is a joint distribution supported on at most action profiles. In contrast, a correlated equilibrium is itself a joint distribution , and its support size is the number of action profiles with . Correlation can in principle couple two large-support marginals using far fewer than the product of their support sizes. Thus, lower bounds on the support of each player’s mixed strategy do not directly give corresponding quadratic lower bounds on the joint support of a correlated equilibrium.
For coarse correlated equilibrium, where deviations must be chosen independently of the recommendation, standard sampling gives joint support in every two-player -action game. More generally, if an equilibrium notion is specified by a finite deviation class , the standard sampling argument gives support . For CCE in a two-player -action game, there are only relevant constant deviations. For CE, however, a player may choose a different deviation for each recommendation. These deviations are described by mappings, also called “swap functions”, and . There are such mappings for each player, so the direct sampling argument only gives . A different argument is therefore needed to obtain polylogarithmic support. Despite this obstacle, polylogarithmic support is in fact achievable.
For correlated equilibrium, Babichenko et al. [ [1, 2] showed that every two-player -action game admits an -correlated equilibrium with support . Before our work, the best known lower bound was , inherited from support lower bounds for approximate minimax strategies in zero-sum games [14]. Indeed, the marginals of an -correlated equilibrium in a zero-sum game are -optimal minimax strategies, and the support of either marginal cannot exceed the joint support.
This left a quadratic gap between the known upper and lower bounds. In particular, it remained possible that correlation could substantially reduce the joint support needed for approximate equilibrium. Two approximate minimax strategies, each with support , give an -correlated equilibrium with joint support by taking their product. The previously known lower bound with explicit dependence on , however, was joint support.
We close this gap and show that correlation cannot provide such a reduction of support size in the worst case. The upper bound of Babichenko et al. [ [1, 2] is tight already for zero-sum games. For every , there exists a zero-sum game in which every distribution supported on at most profiles has correlated-equilibrium gap
This settles the support-size gap highlighted by Ko and Schvartzman [ [3]. In particular, the worst-case support complexity of approximate correlated equilibrium is . Thus, in zero-sum games, the product of two low-support approximate minimax strategies already achieves the optimal worst-case joint support up to constant factors.
More precisely, given a bimatrix game with and a joint distribution , we define its correlated-equilibrium gap as the largest expected gain that either player can obtain from a recommendation-dependent deviation,
Thus, is an -correlated equilibrium if .
Our main result gives a tight lower bound on the CE gap achievable by distributions with small joint support.
Theorem 1.1. Let denote the set of bimatrix games with matrices . There exists a universal constant and such that, for every and every integer ,
Combined with the upper bound of Babichenko et al. [ [2], Theorem 1.1 determines the worst-case CE gap up to universal constant factors. In particular, for ,
Moreover, our lower bound already holds for the subclass of constant-sum games, which are equivalent to zero-sum games for our purposes. We provide a technical overview and proof sketch in § 3, and the full proof in § 4.
Equivalently, Theorem 1.1 determines the worst-case support complexity of approximate correlated equilibrium.
Corollary 1.2. Let denote the minimum support size of an -approximate correlated equilibrium in the worst-case game,
There exist universal constants such that, whenever is sufficiently large and
we have
In particular, for every sufficiently small fixed constant , we have .
This shows that correlation does not reduce the worst-case joint support below the quadratic scale obtained by taking the product of two low-support approximate minimax strategies. It also separates CE from CCE in terms of joint support. In the regime of Corollary 1.2, approximate CCE requires only joint support in the worst case, whereas approximate CE requires . The result also has a direct implication for learning. For example, this rules out bandit learning algorithms that use a sparse empirical distribution of realized play as a certificate of convergence to an approximate CE.
Preliminaries and Notation
For a positive integer , let . We identify a joint distribution on with a nonnegative matrix satisfying . Its support is
We write for the -th row vector and for the -th column vector. Thus, records the probability mass on profiles whose row recommendation is , and records the analogous mass for column recommendation . All logarithms are natural and universal constants may change from line to line.
Approximate Correlated Equilibrium. A two-player normal-form game has row-player and column-player payoff matrices . A row swap function is a map ; after being recommended row , the row player plays . A column swap function is a map defined similarly.
Definition 2.1. For a game and a joint distribution , define its swap regrets and CE gap as
The distribution is a swap-function -correlated equilibrium if .
The identity swap function is available, so both regrets are nonnegative. For , this is the standard correlated equilibrium condition. For , it is the “global” swap-function definition used in Babichenko et al. [ [1, 2], which is stronger than bounding each individual recommendation-to-action gain separately by .
Zero-Sum and Constant-Sum Games. Let be the set of bimatrix games with payoff matrix for the row player and payoff matrix for the column player. For our lower bounds, we focus on the constant-sum subclass in which . Subtracting constants from payoffs does not affect deviations, so this subclass is equivalent, for our purposes, to zero-sum games.
For our lower bounds, we focus on games constructed from a sign matrix by defining the normalized constant-sum game
Let and denote swap regrets in the sign zero-sum game with row payoff and column payoff . This normalization divides regrets by two.
Finally, we use the symbol to denote the worst-case CE approximation of a distribution with support across the bimatrix games in . Specifically, for , we define
Proof Sketch and Technical Overview
In a zero-sum game , the terms in the definition of swap regret cancel out when summing the row and column regret, leading to
Since are nonnegative, showing that right-hand side is large is sufficient to conclude that the CE gap is large.
The cancellation (4) reduces showing that the CE gap is large to controlling the maxima on the right-hand side. In particular, we will seek a randomized matrix that ensures that the maxima must be large with high probability whenever is too sparse. The hard instance is obtained by drawing a matrix with independent Rademacher entries and then normalizing it to a constant-sum game with payoffs in .
Remark 3.1. A related random-sign construction appears in Azrieli and Shmaya [ [15] to rule out pure approximate Nash equilibria in many-player Lipschitz games. Their argument needs the random matrix to control the finite set of pure sign profiles, whereas our setting requires a substantially stronger uniform property. We must simultaneously control all sparse nonnegative vectors with arbitrary weights, since the rows and columns of a sparse correlated distribution can be any such vectors. This continuous family cannot be handled by a direct union bound over pure profiles and leads to the sparse norming and interpolation arguments developed below.
The Effect of Rademacher Sign Matrices on the CE Gap
For a fixed vector and an integer parameter , it will be crucial to determine the scale at which a Rademacher sum is positive with probability at least . This scale falls somewhat between and where large coordinates in must be penalized individually, while the remaining spread-out mass is penalized via its Euclidean norm.
For , let be the nonincreasing rearrangement of . For an integer , define the interpolation scale
We also write
so that .
The first term, , accounts for the largest coordinates of . Their contributions can be aligned by forcing the corresponding Rademacher signs to be , an event of probability . The second term, , accounts for the remaining tail. A Rademacher sum over the tail has standard deviation , and an upward fluctuation at standard deviations again has probability . Thus determines the scale at which a sparse nonnegative vector can be detected by one of exponentially many sign tests. More specifically, we show a one-sided lower bound on the upper-tail probability of an i.i.d. Rademacher vector at the interpolation scale , in the spirit of Montgomery-Smith [ [16]. The following technical lemma is proved in Section 4.1.
Lemma 3.2. There exist universal constants and an integer such that, for every , every , and independent Rademacher signs ,
Armed with the one-sided Rademacher tail bound, we can now show that a random sign matrix detects every sparse nonnegative vector at the interpolation scale . The theorem below proves precisely this property for random sign matrices.
Theorem 3.3 (Sparse Rademacher norming). There exist universal constants and such that for all the following holds. Let
If has independent uniform entries, then with probability at least , simultaneously for every nonnegative with ,
We defer the proof of the theorem to Section 4.1. The proof uses a covering argument, which is handled by a combination of the Paley-Zygmund inequality and a union bound over the largest coordinates.
Mixed-Norm Interpolation Bound
The random norming result in Theorem 3.3 shows that the payoff matrix detects each sparse row or column of a candidate distribution, at least at the scale of . To turn this into a regret lower bound, we need a deterministic statement saying that a sparse joint distribution cannot make all of its row and column vectors small at this scale. This is the point where swap-function correlated equilibrium differs from one-sided or coarse notions as the same probability matrix is simultaneously conditioned by all rows and columns.
The next lemma ensures that every -supported probability matrix has nontrivial total -mass across its row and column vectors. We remark the exponent in the result, which then propagates to the main theorem.
Lemma 3.4 (Interpolation lower bound). Let satisfy and . For any integer , set
Then
The proof, in § 4.2, is fundamentally a pruning argument over rows and columns. Recall that , where the -part measures the largest entries and the -part measures the residual -mass. Suppose the total -mass is small. The -parts then imply that deleting the largest entries in every row and in every column removes only small total mass, so a constant amount of -mass remains. On the remaining matrix, the -parts imply that both the sum of row -norms and the sum of column -norms are small. Blei’s mixed inequality converts these two-sided bounds into a small -norm [17]. Finally, -sparsity converts back to with loss . Since the remaining matrix still has constant -mass, this is impossible unless , up to the trivial constant lower bound.
Connecting the Pieces
We now show that in a random sign game, every sparse probability matrix has enough total -mass so that no -supported candidate with gap below the desired bound can exist.
Theorem 3.5. There exist universal constants such that the following holds for all sufficiently large . Let be a random sign matrix and let be the normalized constant-sum game (2). With probability at least , every joint distribution with support size satisfies
Proof. Condition on the event in Theorem 3.3. Let , and let be supported on at most pure profiles. Every row vector and every column vector is nonnegative and has support at most . Applying Theorem 3.3 to all these vectors and using the cancellation identity (4) gives
This simultaneous application is justified because, on the event from Theorem 3.3, both norming inequalities hold for every nonnegative vector with . Since each row vector and each column vector has support at most , the corresponding inequalities apply to all of these vectors on the same event.
By Lemma 3.4,
Since both swap regrets are nonnegative,
Finally, and the normalization (3) divides regrets by two. Absorbing constants proves (7). ∎
We therefore arrive at the main result of the paper.
Theorem 1.1 (Extended version). There exists a universal constant and such that, for every and every integer ,
Moreover, the lower-bound instance may be obtained by sampling a random sign matrix with independent entries and applying the normalization (2). With probability at least , the resulting game satisfies the displayed lower bound simultaneously for all .
Proof. Theorem 3.5 shows that, with probability at least , a random sign matrix produces a normalized constant-sum game for which every distribution supported on at most profiles has gap at least the right-hand side of (7). Since this probability is positive for all sufficiently large , such a game exists by the probabilistic method. This proves the lower bound in the definition of .
Detailed Proofs
We begin with the statements and proofs of the auxiliary lemmas used in our derivations.
Lemma 4.1 (Paley–Zygmund). If has finite second moment and , then
Lemma 4.2. For every and , the Euclidean unit sphere in , and hence its intersection with the nonnegative orthant, has a -net of cardinality at most .
Lemma 4.3. For every real with ,
Proof. For the upper bound, let . The function is even, , and
Thus . For the lower bound, let . Again is even and . On ,
Hence is convex on this interval and minimized at zero.
Proofs for sec:radenorming
In this section we prove Theorem 3.3. We start with elementary properties of that become useful in the covering argument.
Lemma 4.4. For all and all ,
Proof. Let retain the largest coordinates of in magnitude and let . Then
Thus .
For the Lipschitz bound, observe that
Therefore, since is subadditive,
Also,
because the best -sparse approximation in Euclidean norm is obtained by retaining the largest coordinates. Distance to a fixed set is 1-Lipschitz, so
Adding the two estimates proves the claim. Since , by the triangle inequality and the two estimates above, .
We now prove a one-sided lower bound on the upper-tail probability of an i.i.d. Rademacher vector at the interpolation scale , in the spirit of Montgomery-Smith [ [16].
Lemma 3.2. There exist universal constants and an integer such that, for every , every , and independent Rademacher signs ,
Proof. By homogeneity, no normalization is needed. Reorder the coordinates so that . Put
Note that and , so . If fewer than coordinates are nonzero, then the event that all nonzero signs are has probability at least and yields the full sum . We may therefore assume that at least coordinates are nonzero.
Case 1: . Require the first signs to be . The tail sum is symmetric, so . The two events are independent and hence have joint probability at least . On their intersection,
Case 2: . In this case , and the largest tail coefficient satisfies
Set
Then and for every . Let . By Lemma 4.3,
and
Applying Lemma 4.1 with gives
where is universal. On this event,
After increasing so that , this implies
Now also require . This event is independent of the preceding event, since depends only on the signs . Therefore, the joint event has probability at least
On this event,
Thus, in both cases,
for universal constants and , for example and .
We are ready to restate and prove Theorem 3.3.
Theorem 3.3 (Sparse Rademacher norming). There exist universal constants and such that for all the following holds. Let
If has independent uniform entries, then with probability at least , simultaneously for every nonnegative with ,
Proof. We first establish the row statement (8). Fix a nonnegative unit vector with support size at most . By Lemma 3.2, each random row independently satisfies
with probability at least . Choose the universal constant small enough that for all sufficiently large . Hence
We now make the estimate uniform. Fix a support with . Let be the nonnegative part of the Euclidean unit sphere supported on . Put
By Lemma 4.2, has a -net with
Taking the union over all supports of cardinality at most , the total number of net points is at most
for a universal and all sufficiently large . Indeed, , while .
Applying (10) to every net point and taking a union bound, the probability that some net point fails is at most
for all sufficiently large , since .
Assume now that every net point succeeds. Let and choose with . The function
is -Lipschitz on vectors supported on , because every row restricted to has Euclidean norm . By Lemma , is -Lipschitz. Therefore
Since , this is at least . Homogeneity extends the conclusion to all nonnegative sparse .
The proof of the column statement (9) is identical. The columns of are independent uniform sign vectors. A final union bound over the row and column events proves the theorem, after adjusting constants.
Proofs for sec:mixednorm
In this section, we formally prove Lemma . For a matrix , write
We start with a two-dimensional form of Blei’s inequality [17].
Lemma 4.5 (Blei’s mixed inequality). For every nonnegative matrix ,
Proof. Set and . Zero rows or columns may be omitted. For every remaining entry,
Hölder’s inequality with exponents gives
Raising both sides to the power proves the claim.
Lemma 4.6. If a finite vector or matrix has at most nonzero entries, then
Proof. Let . By Hölder’s inequality with conjugate exponents and ,
Lemma 3.4 (Interpolation lower bound). Let satisfy and . For any integer , set
Then
Proof. If , the claim is immediate. Assume .
For every row , select the positions of its largest entries, or all its nonzero entries if there are fewer than . Do the same for every column. Let be the matrix obtained from by retaining only entries that were selected by neither their row nor their column.
The total mass deleted by row selections is at most . The additional mass deleted by column selections is at most . Hence
In each row, is supported in the tail remaining after the largest row entries are removed. Therefore
and summing over rows gives
Similarly,
By Lemma 4.5,
Finally, has at most nonzero entries, so Lemma 4.6 yields
Combining (4.5), (4.6), and (4.7),
Thus , as required.
Acknowledgement
We thank an anonymous reviewer for observing that symmetrizing the construction of Althöfer [1994] yields an support lower bound for sufficiently small constant . Our result additionally establishes the tight dependence and shows that the lower bound holds with high probability for random sign games.
A.S. and P.J. were partially supported by the ONR grant N00014-24-1-2470. G.F. was supported in part by the National Science Foundation awards CCF-2443068 and IIS-2552046, the Office of Naval Research grant N000142512296, and an AI2050 Early Career Fellowship.
References
- [1]Yakov Babichenko, Siddharth Barman, and Ron Peretz. Simple approximate equilibria in large games. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 753–770, 2014.DOI
- [2]Yakov Babichenko, Siddharth Barman, and Ron Peretz. Empirical distribution of equilibrium play and its testing application. Mathematics of Operations Research, 42(1):15–29, 2017.arxiv.org/abs/1310.7654
- [3]Young Kun Ko and Ariel Schvartzman. Bounds for the communication complexity of two-player approximate correlated equilibria. In Electronic Colloquium on Computational Complexity (ECCC), 2017.
- [4]Robert J Aumann. Subjectivity and correlation in randomized strategies. Journal of mathematical Economics, 1(1):67–96, 1974.
- [7]Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player nash equilibria. Journal of the ACM (JACM), 56(3):1–57, 2009.arxiv.org/abs/0704.1678
- [8]Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. Communications of the ACM, 52(2):89–97, 2009.
- [9]Ingo Althöfer. On sparse approximations to randomized strategies and convex combinations. Linear Algebra and its Applications, 199:339–355, 1994.DOI
- [10]Richard J Lipton and Neal E Young. Simple strategies for large zero-sum games with applications to complexity theory. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 734–740, 1994.
- [11]Richard J Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In Proceedings of the 4th ACM Conference on Electronic Commerce, pages 36–41, 2003.DOI
- [12]Siddharth Barman. Approximating nash equilibria and dense bipartite subgraphs via an approximate version of caratheodory’s theorem. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 361–369, 2015.
- [13]Vahab Mirrokni, Renato Paes Leme, Adrian Vladu, and Sam Chiu-wai Wong. Tight bounds for approximate carathéodory and beyond. In International Conference on Machine Learning, pages 2440–2448. PMLR, 2017.
- [14]Philip Klein and Neal E Young. On the number of iterations for dantzig–wolfe optimization and packing-covering approximation algorithms. SIAM Journal on Computing, 44(4):1154–1172, 2015.
- [15]Yaron Azrieli and Eran Shmaya. Lipschitz games. Mathematics of Operations Research, 38(2):350–357, 2013.DOI
- [16]Stephen J Montgomery-Smith. The distribution of rademacher sums. Proceedings of the American Mathematical Society, 109(2):517–522, 1990.
- [17]Dumitru Popa and Gord Sinnamon. Blei’s inequality and coordinatewise multiple summing operators. Publicacions Matemàtiques, 57(2):455–475, 2013.