betaFeedback

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 ε\varepsilon-approximate coarse correlated equilibria, constant approximation is possible with support O(log⁡N/ε2)O(\log N/\varepsilon^2) in N×NN\times N games. For correlated equilibria, the best known upper bound was O(log⁡2N/ε4)O(\log^2 N/\varepsilon^4) [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 1≤k≤N1/21\leq k\leq N^{1/2} the worst-case correlated-equilibrium gap achievable by a distribution supported on at most kk pure profiles is Θ(min⁡{1,log⁡Nk1/4}), Θ\left( \min\left\{1,\frac{\sqrt{\log N}}{k^{1/4}}\right\} \right), which implies a Θ(log⁡2N/ε4)Θ(\log^2 N/\varepsilon^4) 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 ε\varepsilon-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 ε\varepsilon-optimal minimax strategy with support O(log⁡N/ε2)O(\log N/\varepsilon^2). 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 ε\varepsilon-Nash equilibrium in which each player has support O(log⁡N/ε2)O(\log N/\varepsilon^2). 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 xx and yy each have support size at most ss, then their independent product x⊗yx \otimes y is a joint distribution supported on at most s2s^2 action profiles. In contrast, a correlated equilibrium is itself a joint distribution μ\mu, and its support size is the number of action profiles (i,j)(i,j) with μij>0\mu_{ij} > 0. 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 O(log⁡N/ε2)O(\log N/\varepsilon^2) in every two-player NN-action game. More generally, if an equilibrium notion is specified by a finite deviation class D\mathcal{D}, the standard sampling argument gives support O(log⁡∣D∣/ε2)O(\log|\mathcal{D}|/\varepsilon^2). For CCE in a two-player NN-action game, there are only 2N2N 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”, f:[N]→[N]f : [N] \to[N] and g:[N]→[N]g : [N] \to[N]. There are NNN^N such mappings for each player, so the direct sampling argument only gives log⁡∣D∣=Θ(Nlog⁡N)\log|\mathcal{D}| = \Theta(N \log N). 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 NN-action game admits an ε\varepsilon-correlated equilibrium with support O(log⁡2N/ε4)O(\log^2 N/\varepsilon^4). Before our work, the best known lower bound was Ω(log⁡N/ε2)\Omega(\log N/\varepsilon^2), inherited from support lower bounds for approximate minimax strategies in zero-sum games [14]. Indeed, the marginals of an ε\varepsilon-correlated equilibrium in a zero-sum game are O(ε)O(\varepsilon)-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 O(log⁡N/ε2)O(\log N/\varepsilon^2), give an ε\varepsilon-correlated equilibrium with joint support O(log⁡2N/ε4)O(\log^2 N/\varepsilon^4) by taking their product. The previously known lower bound with explicit dependence on ε\varepsilon, however, was Ω(log⁡N/ε2)\Omega(\log N/\varepsilon^2) 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 1≤k≤N1/21 \leq k \leq N^{1/2}, there exists a zero-sum N×NN \times N game in which every distribution supported on at most kk profiles has correlated-equilibrium gap

Ω(min⁡{1,log⁡Nk1/4}).\Omega\left(\min\left\{1,\frac{\sqrt{\log N}}{k^{1/4}}\right\}\right).

This settles the support-size gap highlighted by Ko and Schvartzman [ [3]. In particular, the worst-case support complexity of approximate correlated equilibrium is Θ(log⁡2N/ε4)\Theta(\log^2 N/\varepsilon^4). 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 G=(U,V)G=(U,V) with U,V∈RN×NU,V\in\mathbb{R}^{N\times N} and a joint distribution μ∈Δ([N]2)\mu\in\Delta([N]^2), we define its correlated-equilibrium gap Gap⁡G(μ)\operatorname{Gap}_G(\mu) as the largest expected gain that either player can obtain from a recommendation-dependent deviation,

Gap⁡G(μ):=max⁡{max⁡f:[N]→[N]∑i,jμij(Uf(i),j−Uij),max⁡g:[N]→[N]∑i,jμij(Vi,g(j)−Vij)}.\operatorname{Gap}_G(\mu):=\max\left\{\max_{f:[N]\to[N]}\sum_{i,j}\mu_{ij}(U_{f(i),j}-U_{ij}),\max_{g:[N]\to[N]}\sum_{i,j}\mu_{ij}(V_{i,g(j)}-V_{ij})\right\}.

Thus, μ\mu is an ε\varepsilon-correlated equilibrium if Gap⁡G(μ)≤ε\operatorname{Gap}_G(\mu)\le\varepsilon.

Our main result gives a tight lower bound on the CE gap achievable by distributions with small joint support.

Theorem 1.1. Let ZNZ_N denote the set of bimatrix games with matrices U,V∈[0,1]N×NU,V\in[0,1]^{N\times N}. There exists a universal constant c>0c>0 and N0∈NN_0\in\mathbb{N} such that, for every N≥N0N\ge N_0 and every integer 1≤k≤N1/21\le k\le N^{1/2},

sup⁡G∈ZN inf⁡μ∈Δ([N]2)∣supp⁡(μ)∣≤kGap⁡G(μ)≥cmin⁡{1,log⁡Nk1/4}.\sup_{G\in Z_N}\ \inf_{\substack{\mu\in\Delta([N]^2)\\|\operatorname{supp}(\mu)|\le k}}\operatorname{Gap}_G(\mu)\ge c\min\left\{1,\frac{\sqrt{\log N}}{k^{1/4}}\right\}.

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 1≤k≤N1/21\le k\le N^{1/2},

sup⁡G∈ZN inf⁡μ∈Δ([N]2)∣supp⁡(μ)∣≤kGap⁡G(μ)=Θ(min⁡{1,log⁡Nk1/4}).\sup_{G\in Z_N}\ \inf_{\substack{\mu\in\Delta([N]^2)\\|\operatorname{supp}(\mu)|\le k}}\operatorname{Gap}_G(\mu)=\Theta\left(\min\left\{1,\frac{\sqrt{\log N}}{k^{1/4}}\right\}\right).

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 SN(ε)S_N(\varepsilon) denote the minimum support size of an ε\varepsilon-approximate correlated equilibrium in the worst-case N×NN\times N game,

SN(ε):=sup⁡G∈ZNmin⁡{∣supp⁡(μ)∣:μ∈Δ([N]2), Gap⁡G(μ)≤ε}.S_N(\varepsilon):=\sup_{G\in Z_N}\min\{|\operatorname{supp}(\mu)|:\mu\in\Delta([N]^2),\ \operatorname{Gap}_G(\mu)\le\varepsilon\}.

There exist universal constants c0,C0,c1,C1>0c_0,C_0,c_1,C_1>0 such that, whenever NN is sufficiently large and

C0log⁡N N−1/8≤ε≤c0,(1)C_0\sqrt{\log N}\,N^{-1/8}\le\varepsilon\le c_0, \tag*{(1)}

we have

c1log⁡2Nε4≤SN(ε)≤C1log⁡2Nε4.c_1\frac{\log^2 N}{\varepsilon^4}\le S_N(\varepsilon)\le C_1\frac{\log^2 N}{\varepsilon^4}.

In particular, for every sufficiently small fixed constant ε>0\varepsilon>0, we have SN(ε)=Θε(log⁡2N)S_N(\varepsilon)=\Theta_\varepsilon(\log^2 N).

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 Θ(log⁡N/ε2)\Theta(\log N/\varepsilon^2) joint support in the worst case, whereas approximate CE requires Θ(log⁡2N/ε4)\Theta(\log^2 N/\varepsilon^4). 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 NN, let [N]={1,…,N}[N] = \{1, \ldots, N\}. We identify a joint distribution on [N]2[N]^2 with a nonnegative matrix μ∈R+N×N\mu\in\mathbb{R}_{+}^{N \times N} satisfying ∑i,jμij=1\sum_{i,j} \mu_{ij} = 1. Its support is

supp⁡(μ):={(i,j):μij>0}.\operatorname{supp}(\mu) := \{(i,j) : \mu_{ij} > 0\}.

We write μi,∗\mu_{i,*} for the ii-th row vector and μ∗,j\mu_{*,j} for the jj-th column vector. Thus, μi,∗\mu_{i,*} records the probability mass on profiles whose row recommendation is ii, and μ∗,j\mu_{*,j} records the analogous mass for column recommendation jj. 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 U,V∈[0,1]N×NU,V \in[0,1]^{N \times N}. A row swap function is a map f:[N]→[N]f : [N] \to[N]; after being recommended row ii, the row player plays f(i)f(i). A column swap function is a map g:[N]→[N]g : [N] \to[N] defined similarly.

Definition 2.1. For a game G=(U,V)G = (U,V) and a joint distribution μ∈Δ([N]2)\mu\in\Delta([N]^2), define its swap regrets and CE gap as

Reg⁡RG(μ):=max⁡f:[N]→[N]∑i,jμij(Uf(i),j−Uij),\operatorname{Reg}_{R}^{G}(\mu) := \max_{f:[N]\to[N]} \sum_{i,j} \mu_{ij}(U_{f(i),j} - U_{ij}),
Reg⁡CG(μ):=max⁡g:[N]→[N]∑i,jμij(Vi,g(j)−Vij),\operatorname{Reg}_{C}^{G}(\mu) := \max_{g:[N]\to[N]} \sum_{i,j} \mu_{ij}(V_{i,g(j)} - V_{ij}),
Gap⁡G(μ):=max⁡{Reg⁡RG(μ),Reg⁡CG(μ)}.\operatorname{Gap}_{G}(\mu) := \max\{\operatorname{Reg}_{R}^{G}(\mu), \operatorname{Reg}_{C}^{G}(\mu)\}.

The distribution μ\mu is a swap-function ε\varepsilon-correlated equilibrium if Gap⁡G(μ)≤ε\operatorname{Gap}_{G}(\mu) \le\varepsilon.

The identity swap function is available, so both regrets are nonnegative. For ε=0\varepsilon= 0, this is the standard correlated equilibrium condition. For ε>0\varepsilon> 0, 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 ε\varepsilon.

Zero-Sum and Constant-Sum Games. Let ZN\mathcal{Z}_{N} be the set of bimatrix games with payoff matrix U∈[0,1]N×NU \in[0,1]^{N \times N} for the row player and payoff matrix V∈[0,1]N×NV \in[0,1]^{N \times N} for the column player. For our lower bounds, we focus on the constant-sum subclass in which V=11T−UV = \mathbf{1}\mathbf{1}^{\mathsf{T}} - U. 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 A∈{−1,+1}N×NA \in\{-1,+1\}^{N \times N} by defining the normalized constant-sum game

U=11T+A2,V=11T−A2.(2)U = \frac{\mathbf{1}\mathbf{1}^{\mathsf{T}} + A}{2}, \qquad V = \frac{\mathbf{1}\mathbf{1}^{\mathsf{T}} - A}{2}. \tag*{(2)}

Let Reg⁡RA\operatorname{Reg}_{R}^{A} and Reg⁡CA\operatorname{Reg}_{C}^{A} denote swap regrets in the sign zero-sum game with row payoff AA and column payoff −A-A. This normalization divides regrets by two.

Reg⁡RG(μ)=12Reg⁡RA(μ),Reg⁡CG(μ)=12Reg⁡CA(μ).(3)\operatorname{Reg}_{R}^{G}(\mu) = \frac{1}{2}\operatorname{Reg}_{R}^{A}(\mu), \qquad\operatorname{Reg}_{C}^{G}(\mu) = \frac{1}{2}\operatorname{Reg}_{C}^{A}(\mu). \tag*{(3)}

Finally, we use the symbol GN(k)G_N(k) to denote the worst-case CE approximation of a distribution with support kk across the bimatrix games in ZN\mathcal{Z}_N. Specifically, for 1≤k≤N21 \le k \le N^2, we define

GN(k):=sup⁡G∈ZN inf⁡μ∈Δ([N2])∣supp⁡(μ)∣≤kGap⁡G(μ).G_N(k) := \sup_{G \in\mathcal{Z}_N}\ \inf_{\substack{\mu\in\Delta([N^2])\\ |\operatorname{supp}(\mu)| \le k}} \operatorname{Gap}_G(\mu).

Proof Sketch and Technical Overview

In a zero-sum game (A,−A)(A,-A), the ±∑ijAijμij\pm\sum_{ij} A_{ij}\mu_{ij} terms in the definition of swap regret cancel out when summing the row and column regret, leading to

Reg⁡RA(μ)+Reg⁡CA(μ)=∑imax⁡r⟨Ar,∗,μi,∗⟩+∑jmax⁡c⟨−A∗,c,μ∗,j⟩.(4)\operatorname{Reg}^{A}_{R}(\mu) + \operatorname{Reg}^{A}_{C}(\mu) = \sum_i \max_r \langle A_{r,*}, \mu_{i,*}\rangle+ \sum_j \max_c \langle-A_{*,c}, \mu_{*,j}\rangle. \tag*{(4)}

Since Reg⁡RA(μ),Reg⁡CA(μ)\operatorname{Reg}^{A}_{R}(\mu), \operatorname{Reg}^{A}_{C}(\mu) 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 AA that ensures that the maxima must be large with high probability whenever μ\mu is too sparse. The hard instance AA is obtained by drawing a matrix with independent Rademacher entries and then normalizing it to a constant-sum game with payoffs in [0,1][0,1].

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 zz and an integer parameter 1≤p≤N1 \le p \le N, it will be crucial to determine the scale at which a Rademacher sum ∑iεizi\sum_i \varepsilon_i z_i is positive with probability at least exp⁡(−Θ(p))\exp(-\Theta(p)). This scale falls somewhat between ∥z∥1\|z\|_1 and p ∥z∥2\sqrt{p}\,\|z\|_2 where large coordinates in zz must be penalized individually, while the remaining spread-out mass is penalized via its Euclidean norm.

For z∈R+Nz \in\mathbb{R}_+^N, let z1∗≥z2∗≥⋯≥zN∗≥0z_1^* \ge z_2^* \ge\cdots\ge z_N^* \ge0 be the nonincreasing rearrangement of (zi)i=1N(z_i)_{i=1}^N. For an integer 1≤p≤N1 \le p \le N, define the interpolation scale

κp(z):=∑ℓ≤pzℓ∗+p(∑ℓ>p(zℓ∗)2)1/2.(5)\kappa_p(z) := \sum_{\ell\le p} z_\ell^* + \sqrt{p}\left(\sum_{\ell> p}(z_\ell^*)^2\right)^{1/2}. \tag*{(5)}

We also write

τp(z):=∑ℓ≤pzℓ∗,σp(z):=(∑ℓ>p(zℓ∗)2)1/2,(6)\tau_p(z) := \sum_{\ell\le p} z_\ell^*, \qquad\sigma_p(z) := \left(\sum_{\ell> p}(z_\ell^*)^2\right)^{1/2}, \tag*{(6)}

so that κp(z)=τp(z)+p σp(z)\kappa_p(z) = \tau_p(z) + \sqrt{p}\,\sigma_p(z).

The first term, τp(z)\tau_p(z), accounts for the pp largest coordinates of zz. Their contributions can be aligned by forcing the corresponding Rademacher signs to be +1+1, an event of probability exp⁡(−Θ(p))\exp(-\Theta(p)). The second term, p σp(z)\sqrt{p}\,\sigma_p(z), accounts for the remaining tail. A Rademacher sum over the tail has standard deviation σp(z)\sigma_p(z), and an upward fluctuation at p\sqrt{p} standard deviations again has probability exp⁡(−Θ(p))\exp(-\Theta(p)). Thus κp\kappa_p 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 κp\kappa_p, in the spirit of Montgomery-Smith [ [16]. The following technical lemma is proved in Section 4.1.

Lemma 3.2. There exist universal constants c∗,C∗>0c_\ast,C_\ast>0 and an integer p0p_0 such that, for every p≥p0p\ge p_0, every z∈R+Nz\in\mathbb{R}_+^N, and independent Rademacher signs ε1,…,εN\varepsilon_1,\ldots,\varepsilon_N,

P[∑i=1Nεizi≥c∗κp(z)]≥e−C∗p.\mathbb{P}\left[\sum_{i=1}^{N}\varepsilon_i z_i \ge c_\ast\kappa_p(z)\right]\ge e^{-C_\ast p}.

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 κp\kappa_p. The theorem below proves precisely this property for random sign matrices.

Theorem 3.3 (Sparse Rademacher norming). There exist universal constants a,c,c′>0a,c,c'>0 and N0∈NN_0\in\mathbb{N} such that for all N>N0N>N_0 the following holds. Let

p:=⌊alog⁡N⌋,K:=⌊N1/2⌋.p:=\lfloor a\log N\rfloor,\qquad K:=\lfloor N^{1/2}\rfloor.

If A∈{−1,+1}N×NA\in\{-1,+1\}^{N\times N} has independent uniform entries, then with probability at least 1−2exp⁡(−c′N3/4)1-2\exp(-c'N^{3/4}), simultaneously for every nonnegative z∈R+Nz\in\mathbb{R}_+^N with ∣supp⁡(z)∣≤K|\operatorname{supp}(z)|\le K,

max⁡r∈[N]⟨Ar,∗,z⟩≥cκp(z),\max_{r\in[N]}\langle A_{r,*},z\rangle\ge c\kappa_p(z),
max⁡c∈[N]⟨−A∗,c,z⟩≥cκp(z).\max_{c\in[N]}\langle-A_{*,c},z\rangle\ge c\kappa_p(z).

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 κp\kappa_p. 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 kk-supported probability matrix has nontrivial total κp\kappa_p-mass across its row and column vectors. We remark the exponent 1/41/4 in the result, which then propagates to the main theorem.

Lemma 3.4 (Interpolation lower bound). Let μ∈R+N×N\mu\in\mathbb{R}_+^{N\times N} satisfy ∥μ∥1=1\|\mu\|_1=1 and ∣supp⁡(μ)∣≤k|\operatorname{supp}(\mu)|\le k. For any integer p≥1p\ge1, set

SR:=∑iκp(μi,∗),SC:=∑jκp(μ∗,j),S:=SR+SC.S_R:=\sum_i\kappa_p(\mu_{i,*}),\qquad S_C:=\sum_j\kappa_p(\mu_{*,j}),\qquad S:=S_R+S_C.

Then

S≥min⁡{12,pk1/4}.S \ge\min\left\{\frac{1}{2},\frac{\sqrt{p}}{k^{1/4}}\right\}.

The proof, in § 4.2, is fundamentally a pruning argument over rows and columns. Recall that κp=τp+p σp\kappa_p=\tau_p+\sqrt{p}\,\sigma_p, where the τp\tau_p-part measures the largest entries and the σp\sigma_p-part measures the residual ℓ2\ell_2-mass. Suppose the total κp\kappa_p-mass SS is small. The τp\tau_p-parts then imply that deleting the pp largest entries in every row and in every column removes only small total mass, so a constant amount of ℓ1\ell_1-mass remains. On the remaining matrix, the σp\sigma_p-parts imply that both the sum of row ℓ2\ell_2-norms and the sum of column ℓ2\ell_2-norms are small. Blei’s mixed 4/34/3 inequality converts these two-sided ℓ2\ell_2 bounds into a small ℓ4/3\ell_{4/3}-norm [17]. Finally, kk-sparsity converts ℓ4/3\ell_{4/3} back to ℓ1\ell_1 with loss k1/4k^{1/4}. Since the remaining matrix still has constant ℓ1\ell_1-mass, this is impossible unless S≳p/k1/4S\gtrsim\sqrt{p}/k^{1/4}, 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 κp\kappa_p-mass so that no kk-supported candidate with gap below the desired bound can exist.

Theorem 3.5. There exist universal constants c,c′>0c,c'>0 such that the following holds for all sufficiently large NN. Let A∈{−1,+1}N×NA\in\{-1,+1\}^{N\times N} be a random sign matrix and let GAG_A be the normalized constant-sum game (2). With probability at least 1−2exp⁡(−c′N3/4)1-2\exp(-c'N^{3/4}), every joint distribution μ\mu with support size k≤N1/2k\le N^{1/2} satisfies

Gap⁡GA(μ)≥cmin⁡{1,log⁡Nk1/4}.(7)\operatorname{Gap}_{G_A}(\mu)\ge c\min\left\{1,\frac{\sqrt{\log N}}{k^{1/4}}\right\}. \tag*{(7)}

Proof. Condition on the event in Theorem 3.3. Let p=⌊alog⁡N⌋p=\lfloor a\log N\rfloor, and let μ\mu be supported on at most k≤N1/2k\le N^{1/2} pure profiles. Every row vector μi,∗\mu_{i,*} and every column vector μ∗,j\mu_{*,j} is nonnegative and has support at most k≤Kk\le K. Applying Theorem 3.3 to all these vectors and using the cancellation identity (4) gives

Reg⁡RA(μ)+Reg⁡CA(μ)≥c0∑iκp(μi,∗)+c0∑jκp(μ∗,j)=c0S.\begin{aligned} \operatorname{Reg}^{A}_{R}(\mu)+\operatorname{Reg}^{A}_{C}(\mu)\ge c_0\sum_i\kappa_p(\mu_{i,*})+c_0\sum_j\kappa_p(\mu_{*,j}) \\ &=c_0S. \end{aligned}

This simultaneous application is justified because, on the event from Theorem 3.3, both norming inequalities hold for every nonnegative vector z∈R+Nz\in\mathbb{R}^{N}_{+} with ∣supp⁡(z)∣≤K|\operatorname{supp}(z)|\le K. Since each row vector μi,∗\mu_{i,*} and each column vector μ∗,j\mu_{*,j} has support at most k≤Kk\le K, the corresponding inequalities apply to all of these vectors on the same event.

By Lemma 3.4,

S≥min⁡{12,pk1/4}.S\ge\min\left\{\frac{1}{2},\frac{\sqrt{p}}{k^{1/4}}\right\}.

Since both swap regrets are nonnegative,

max⁡{Reg⁡RA(μ),Reg⁡CA(μ)}≥c02min⁡{12,pk1/4}.\max\left\{\operatorname{Reg}^{A}_{R}(\mu),\operatorname{Reg}^{A}_{C}(\mu)\right\}\ge\frac{c_0}{2}\min\left\{\frac{1}{2},\frac{\sqrt{p}}{k^{1/4}}\right\}.

Finally, p=Θ(log⁡N)p=\Theta(\log N) and the normalization (3) divides regrets by two. Absorbing constants c:=c0a/4c:=c_0\sqrt{a}/4 proves (7). ∎

We therefore arrive at the main result of the paper.

Theorem 1.1 (Extended version). There exists a universal constant c>0c > 0 and N0∈NN_0 \in\mathbb{N} such that, for every N≥N0N \ge N_0 and every integer 1≤k≤N1/21 \le k \le N^{1/2},

GN(k)≥cmin⁡{1,log⁡Nk1/4}.G_N(k) \ge c \min\left\{1,\frac{\sqrt{\log N}}{k^{1/4}}\right\}.

Moreover, the lower-bound instance may be obtained by sampling a random sign matrix A∈{−1,+1}N×NA \in\{-1,+1\}^{N \times N} with independent entries and applying the normalization (2). With probability at least 1−2exp⁡(−c′N3/4)1 - 2\exp(-c'N^{3/4}), the resulting game satisfies the displayed lower bound simultaneously for all 1≤k≤N1/21 \le k \le N^{1/2}.

Proof. Theorem 3.5 shows that, with probability at least 1−2exp⁡(−c′N3/4)1 - 2\exp(-c'N^{3/4}), a random sign matrix produces a normalized constant-sum game for which every distribution supported on at most k≤N1/2k \le N^{1/2} profiles has gap at least the right-hand side of (7). Since this probability is positive for all sufficiently large NN, such a game exists by the probabilistic method. This proves the lower bound in the definition of GN(k)G_N(k).

Detailed Proofs

We begin with the statements and proofs of the auxiliary lemmas used in our derivations.

Lemma 4.1 (Paley–Zygmund). If Y≥0Y \ge0 has finite second moment and 0<θ<10 < \theta< 1, then

P[Y≥θE[Y]]≥(1−θ)2E[Y]2E[Y2].\mathbb{P}[Y \ge\theta\mathbb{E}[Y]] \ge(1-\theta)^2 \frac{\mathbb{E}[Y]^2}{\mathbb{E}[Y^2]}.

Lemma 4.2. For every d≥1d \ge1 and 0<δ≤10 < \delta\le1, the Euclidean unit sphere in Rd\mathbb{R}^d, and hence its intersection with the nonnegative orthant, has a δ\delta-net of cardinality at most (1+2/δ)d(1+2/\delta)^d.

Lemma 4.3. For every real uu with ∣u∣≤1/2|u| \le1/2,

u23≤log⁡cosh⁡u≤u22.\frac{u^2}{3} \le\log\cosh u \le\frac{u^2}{2}.

Proof. For the upper bound, let h(u)=u2/2−log⁡cosh⁡uh(u) = u^2/2 - \log\cosh u. The function is even, h(0)=h′(0)=0h(0) = h'(0) = 0, and

h′′(u)=1−sech⁡2u=tanh⁡2u≥0.h''(u) = 1 - \operatorname{sech}^2 u = \tanh^2 u \ge0.

Thus h(u)≥0h(u) \ge0. For the lower bound, let g(u)=log⁡cosh⁡u−u2/3g(u) = \log\cosh u - u^2/3. Again gg is even and g(0)=g′(0)=0g(0) = g'(0) = 0. On ∣u∣≤1/2|u| \le1/2,

g′′(u)=sech⁡2u−23≥sech⁡2(1/2)−23>0.g''(u) = \operatorname{sech}^2 u - \frac{2}{3} \ge\operatorname{sech}^2(1/2) - \frac{2}{3} > 0.

Hence gg 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 κp\kappa_p that become useful in the covering argument.

Lemma 4.4. For all z,w∈RNz,w \in\mathbb{R}^{N} and all p≥1p \ge1,

κp(z)≥∥z∥2,∣κp(z)−κp(w)∣≤2p ∥z−w∥2.\kappa_p(z) \ge\lVert z\rVert_2,\qquad\lvert\kappa_p(z)-\kappa_p(w)\rvert\le2\sqrt{p}\,\lVert z-w\rVert_2.

Proof. Let ztopz^{\mathrm{top}} retain the pp largest coordinates of zz in magnitude and let ztail=z−ztopz^{\mathrm{tail}}=z-z^{\mathrm{top}}. Then

τp(z)=∥ztop∥1≥∥ztop∥2,pσp(z)=p ∥ztail∥2≥∥ztail∥2.\tau_p(z)=\lVert z^{\mathrm{top}}\rVert_1\ge\lVert z^{\mathrm{top}}\rVert_2,\qquad\sqrt{p}\sigma_p(z)=\sqrt{p}\,\lVert z^{\mathrm{tail}}\rVert_2\ge\lVert z^{\mathrm{tail}}\rVert_2.

Thus κp(z)≥∥ztop∥2+∥ztail∥2≥∥z∥2\kappa_p(z)\ge\lVert z^{\mathrm{top}}\rVert_2+\lVert z^{\mathrm{tail}}\rVert_2\ge\lVert z\rVert_2.

For the Lipschitz bound, observe that

τp(z)=max⁡∣S∣≤p∥zS∥1.\tau_p(z)=\max_{\lvert S\rvert\le p}\lVert z_S\rVert_1.

Therefore, since τp\tau_p is subadditive,

∣τp(z)−τp(w)∣≤τp(z−w)≤p ∥z−w∥2.\lvert\tau_p(z)-\tau_p(w)\rvert\le\tau_p(z-w)\le\sqrt{p}\,\lVert z-w\rVert_2.

Also,

σp(z)=inf⁡v:∣supp⁡(v)∣≤p∥z−v∥2,\sigma_p(z)=\inf_{v:\lvert\operatorname{supp}(v)\rvert\le p}\lVert z-v\rVert_2,

because the best pp-sparse approximation in Euclidean norm is obtained by retaining the pp largest coordinates. Distance to a fixed set is 1-Lipschitz, so

∣σp(z)−σp(w)∣≤∥z−w∥2.\lvert\sigma_p(z)-\sigma_p(w)\rvert\le\lVert z-w\rVert_2.

Adding the two estimates proves the claim. Since κp=τp+pσp\kappa_p=\tau_p+\sqrt{p}\sigma_p, by the triangle inequality and the two estimates above, ∣κp(z)−κp(w)∣≤∣τp(z)−τp(w)∣+p∣σp(z)−σp(w)∣≤p∥z−w∥2+p⋅∥z−w∥2=2p∥z−w∥2\lvert\kappa_p(z)-\kappa_p(w)\rvert\le\lvert\tau_p(z)-\tau_p(w)\rvert+\sqrt{p}\lvert\sigma_p(z)-\sigma_p(w)\rvert\le\sqrt{p}\lVert z-w\rVert_2+\sqrt{p}\cdot\lVert z-w\rVert_2=2\sqrt{p}\lVert z-w\rVert_2.

We now prove a one-sided lower bound on the upper-tail probability of an i.i.d. Rademacher vector at the interpolation scale κp\kappa_p, in the spirit of Montgomery-Smith [ [16].

Lemma 3.2. There exist universal constants c∗,C∗>0c_\ast,C_\ast>0 and an integer p0p_0 such that, for every p≥p0p\ge p_0, every z∈R+Nz\in\mathbb{R}_+^N, and independent Rademacher signs ε1,…,εN\varepsilon_1,\ldots,\varepsilon_N,

P[∑i=1Nεizi≥c∗κp(z)]≥e−C∗p.\mathbb{P}\left[\sum_{i=1}^{N}\varepsilon_i z_i\ge c_\ast\kappa_p(z)\right]\ge e^{-C_\ast p}.

Proof. By homogeneity, no normalization is needed. Reorder the coordinates so that z1≥⋯≥zN≥0z_1\ge\cdots\ge z_N\ge0. Put

A0:=∑i≤pzi,B0:=(∑i>pzi2)1/2.A_0:=\sum_{i\le p}z_i,\qquad B_0:=\left(\sum_{i>p}z_i^2\right)^{1/2}.

Note that A0=τp(z)A_0=\tau_p(z) and B0=σp(z)B_0=\sigma_p(z), so κp(z)=A0+pB0\kappa_p(z)=A_0+\sqrt{p}B_0. If fewer than pp coordinates are nonzero, then the event that all nonzero signs are +1+1 has probability at least 2−p2^{-p} and yields the full sum κp(z)\kappa_p(z). We may therefore assume that at least pp coordinates are nonzero.

Case 1: A0≥pB0A_0\ge\sqrt{p}B_0. Require the first pp signs to be +1+1. The tail sum T:=∑i>pεiziT:=\sum_{i>p}\varepsilon_i z_i is symmetric, so P[T≥0]≥1/2\mathbb{P}[T\ge0]\ge1/2. The two events are independent and hence have joint probability at least 2−p−12^{-p-1}. On their intersection,

∑iεizi≥A0≥12(A0+pB0).\sum_i \varepsilon_i z_i\ge A_0\ge\frac{1}{2}(A_0+\sqrt{p}B_0).

Case 2: A0<pB0A_0<\sqrt{p}B_0. In this case B0>0B_0>0, and the largest tail coefficient satisfies

max⁡i>pzi≤zp≤A0p<B0p.\max_{i>p}z_i\le z_p\le\frac{A_0}{p}<\frac{B_0}{\sqrt{p}}.

Set

λ:=p4B0.\lambda:=\frac{\sqrt{p}}{4B_0}.

Then ∣λzi∣<1/4|\lambda z_i|<1/4 and ∣2λzi∣<1/2|2\lambda z_i|<1/2 for every i>pi>p. Let Y=eλTY=e^{\lambda T}. By Lemma 4.3,

E[Y]=∏i>pcosh⁡(λzi)≥exp⁡(λ2B023),\mathbb{E}[Y]=\prod_{i>p}\cosh(\lambda z_i)\ge\exp\left(\frac{\lambda^2B_0^2}{3}\right),

and

E[Y2]=∏i>pcosh⁡(2λzi)≤exp⁡(2λ2B02).\mathbb{E}[Y^2]=\prod_{i>p}\cosh(2\lambda z_i)\le\exp\left(2\lambda^2B_0^2\right).

Applying Lemma 4.1 with θ=1/2\theta=1/2 gives

P[Y≥12E[Y]]≥14(E[Y])2E[Y2]≥14exp⁡(−43λ2B02)=14e−p/12≥e−C1p,\mathbb{P}\left[Y\ge\frac{1}{2}\mathbb{E}[Y]\right]\ge\frac{1}{4}\frac{(\mathbb{E}[Y])^2}{\mathbb{E}[Y^2]}\ge\frac{1}{4}\exp\left(-\frac{4}{3}\lambda^2B_0^2\right)=\frac{1}{4}e^{-p/12}\ge e^{-C_1p},

where C1:=log⁡4+1/12C_1:=\log4+1/12 is universal. On this event,

T≥log⁡E[Y]−log⁡2λ≥λB023−log⁡2λ=(112−4log⁡2p)pB0.\begin{aligned} T\ge\frac{\log\mathbb{E}[Y]-\log2}{\lambda} \\ &\ge\frac{\lambda B_0^2}{3}-\frac{\log2}{\lambda} \\ &=\left(\frac{1}{12}-\frac{4\log2}{p}\right)\sqrt{p}B_0. \end{aligned}

After increasing p0p_0 so that p0≥96log⁡2p_0\ge96\log2, this implies

T≥124pB0.T\ge\frac{1}{24}\sqrt{p}B_0.

Now also require ε1=⋯=εp=+1\varepsilon_1=\cdots=\varepsilon_p=+1. This event is independent of the preceding event, since TT depends only on the signs (εi)i>p(\varepsilon_i)_{i>p}. Therefore, the joint event has probability at least

2−pe−C1p=e−C2p,C2:=C1+log⁡2.2^{-p}e^{-C_1p}=e^{-C_2p},\qquad C_2:=C_1+\log2.

On this event,

∑iεizi≥A0+124pB0≥124(A0+pB0).\sum_i\varepsilon_i z_i\ge A_0+\frac{1}{24}\sqrt{p}B_0\ge\frac{1}{24}(A_0+\sqrt{p}B_0).

Thus, in both cases,

P[∑iεizi≥c∗κp(z)]≥e−C∗p\mathbb{P}\left[\sum_i \varepsilon_i z_i \ge c_* \kappa_p(z)\right] \ge e^{-C_*p}

for universal constants c∗>0c_* > 0 and C∗>0C_* > 0, for example c∗=1/24c_* = 1/24 and C∗=max⁡{2log⁡2,C2}C_* = \max\{2\log2,C_2\}.

We are ready to restate and prove Theorem 3.3.

Theorem 3.3 (Sparse Rademacher norming). There exist universal constants a,c,c′>0a,c,c' > 0 and N0∈NN_0 \in\mathbb{N} such that for all N>N0N > N_0 the following holds. Let

p:=⌊alog⁡N⌋,K:=⌊N1/2⌋.p := \lfloor a\log N\rfloor,\qquad K := \lfloor N^{1/2}\rfloor.

If A∈{−1,+1}N×NA \in\{-1,+1\}^{N\times N} has independent uniform entries, then with probability at least 1−2exp⁡(−c′N3/4)1-2\exp(-c'N^{3/4}), simultaneously for every nonnegative z∈R+Nz\in\mathbb{R}_+^N with ∣supp⁡(z)∣≤K|\operatorname{supp}(z)|\le K,

max⁡r∈[N]⟨Ar,∗,z⟩≥cκp(z),(8)\max_{r\in[N]}\langle A_{r,*},z\rangle\ge c\kappa_p(z), \tag*{(8)}
max⁡c∈[N]⟨−A∗,c,z⟩≥cκp(z).(9)\max_{c\in[N]}\langle-A_{*,c},z\rangle\ge c\kappa_p(z). \tag*{(9)}

Proof. We first establish the row statement (8). Fix a nonnegative unit vector zz with support size at most KK. By Lemma 3.2, each random row Ar,∗A_{r,*} independently satisfies

⟨Ar,∗,z⟩≥c∗κp(z)\langle A_{r,*},z\rangle\ge c_*\kappa_p(z)

with probability at least q:=e−C∗pq:=e^{-C_*p}. Choose the universal constant a>0a>0 small enough that q≥N−1/4q\ge N^{-1/4} for all sufficiently large NN. Hence

P[max⁡r⟨Ar,∗,z⟩<c∗κp(z)]≤(1−q)N≤e−N3/4.(10)\mathbb{P}\left[\max_r\langle A_{r,*},z\rangle<c_*\kappa_p(z)\right]\le(1-q)^N\le e^{-N^{3/4}}. \tag*{(10)}

We now make the estimate uniform. Fix a support S⊆[N]S\subseteq[N] with ∣S∣=d≤K|S|=d\le K. Let SS,+S_{S,+} be the nonnegative part of the Euclidean unit sphere supported on SS. Put

δd:=c∗4(d+2c∗p).\delta_d:=\frac{c_*}{4(\sqrt{d}+2c_*\sqrt{p})}.

By Lemma 4.2, SS,+S_{S,+} has a δd\delta_d-net NSN_S with

∣NS∣≤(1+2δd)d.|N_S|\le\left(1+\frac{2}{\delta_d}\right)^d.

Taking the union over all supports of cardinality at most KK, the total number of net points is at most

∣N∣≤∑d=1K(Nd)(1+2δd)d≤exp⁡(CKlog⁡N)(11)|\mathcal{N}|\le\sum_{d=1}^{K}\binom{N}{d}\left(1+\frac{2}{\delta_d}\right)^d\le\exp(CK\log N) \tag*{(11)}

for a universal CC and all sufficiently large NN. Indeed, (Nd)≤(eN/d)d\binom{N}{d}\le(eN/d)^d, while δd−1=O(d+p)≤O(N)\delta_d^{-1}=O(\sqrt{d}+\sqrt{p})\le O(\sqrt{N}).

Applying (10) to every net point and taking a union bound, the probability that some net point fails is at most

exp⁡(CKlog⁡N−N3/4)≤exp⁡(−N3/4/2)\exp(CK\log N-N^{3/4})\le\exp(-N^{3/4}/2)

for all sufficiently large NN, since K=N1/2+O(1)K = N^{1/2} + O(1).

Assume now that every net point succeeds. Let z∈SS,+z \in S_{S,+} and choose z0∈NSz_0 \in\mathcal{N}_S with ∥z−z0∥2≤δd\lVert z-z_0\rVert_2 \le\delta_d. The function

FA(w):=max⁡r⟨Ar,∗,w⟩F_A(w) := \max_r \langle A_{r,*},w\rangle

is d\sqrt{d}-Lipschitz on vectors supported on SS, because every row restricted to SS has Euclidean norm d\sqrt{d}. By Lemma 4.44.4, κp\kappa_p is 2p2\sqrt{p}-Lipschitz. Therefore

FA(z)≥FA(z0)−d δd≥c∗κp(z0)−d δd≥c∗κp(z)−(2c∗p+d)δd≥c∗κp(z)−c∗4.\begin{aligned} F_A(z) &\ge F_A(z_0)-\sqrt{d}\,\delta_d\\ &\ge c_*\kappa_p(z_0)-\sqrt{d}\,\delta_d\\ &\ge c_*\kappa_p(z)-(2c_*\sqrt{p}+\sqrt{d})\delta_d\\ &\ge c_*\kappa_p(z)-\frac{c_*}{4}. \end{aligned}

Since κp(z)≥∥z∥2=1\kappa_p(z)\ge\lVert z\rVert_2=1, this is at least (3c∗/4)κp(z)(3c_*/4)\kappa_p(z). Homogeneity extends the conclusion to all nonnegative sparse zz.

The proof of the column statement (9) is identical. The columns of −A-A 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 3.43.4. For a matrix B=[bij]i,j=1NB=[b_{ij}]_{i,j=1}^N, write

∥B∥4/3:=(∑i,j∣bij∣4/3)3/4.\lVert B\rVert_{4/3}:=\left(\sum_{i,j}|b_{ij}|^{4/3}\right)^{3/4}.

We start with a two-dimensional form of Blei’s inequality [17].

Lemma 4.5 (Blei’s mixed 4/34/3 inequality). For every nonnegative matrix B=[bij]i,j=1NB=[b_{ij}]_{i,j=1}^N,

∥B∥4/3≤(∑i∥Bi,∗∥2)1/2(∑j∥B∗,j∥2)1/2.\lVert B\rVert_{4/3}\le\left(\sum_i\lVert B_{i,*}\rVert_2\right)^{1/2}\left(\sum_j\lVert B_{*,j}\rVert_2\right)^{1/2}.

Proof. Set ri:=∥Bi,∗∥2r_i:=\lVert B_{i,*}\rVert_2 and cj:=∥B∗,j∥2c_j:=\lVert B_{*,j}\rVert_2. Zero rows or columns may be omitted. For every remaining entry,

bij4/3=(bij2ri)1/3(bij2cj)1/3(ricj)1/3.b_{ij}^{4/3}=\left(\frac{b_{ij}^2}{r_i}\right)^{1/3}\left(\frac{b_{ij}^2}{c_j}\right)^{1/3}(r_ic_j)^{1/3}.

Hölder’s inequality with exponents (3,3,3)(3,3,3) gives

∑i,jbij4/3≤(∑i,jbij2ri)1/3(∑i,jbij2cj)1/3(∑i,jricj)1/3=(∑iri)2/3(∑jcj)2/3.\begin{aligned} \sum_{i,j}b_{ij}^{4/3} &\le\left(\sum_{i,j}\frac{b_{ij}^2}{r_i}\right)^{1/3} \left(\sum_{i,j}\frac{b_{ij}^2}{c_j}\right)^{1/3} \left(\sum_{i,j}r_ic_j\right)^{1/3}\\ &=\left(\sum_i r_i\right)^{2/3}\left(\sum_j c_j\right)^{2/3}. \end{aligned}

Raising both sides to the power 3/43/4 proves the claim.

Lemma 4.6. If a finite vector or matrix ww has at most kk nonzero entries, then

∥w∥1≤k1/4∥w∥4/3.\lVert w\rVert_1 \le k^{1/4}\lVert w\rVert_{4/3}.

Proof. Let S=supp⁡(w)S = \operatorname{supp}(w). By Hölder’s inequality with conjugate exponents 4/34/3 and 44,

∥w∥1=∑a∈S∣wa∣≤(∑a∈S∣wa∣4/3)3/4∣S∣1/4=∥w∥4/3∣S∣1/4≤k1/4∥w∥4/3.\lVert w\rVert_1 = \sum_{a\in S}|w_a| \le\left(\sum_{a\in S}|w_a|^{4/3}\right)^{3/4}|S|^{1/4} = \lVert w\rVert_{4/3}|S|^{1/4} \le k^{1/4}\lVert w\rVert_{4/3}.

Lemma 3.4 (Interpolation lower bound). Let μ∈R+N×N\mu\in\mathbb{R}_{+}^{N\times N} satisfy ∥μ∥1=1\lVert\mu\rVert_1 = 1 and ∣supp⁡(μ)∣≤k|\operatorname{supp}(\mu)| \le k. For any integer p≥1p \ge1, set

SR:=∑iκp(μi,∗),SC:=∑jκp(μ∗,j),S:=SR+SC.S_R := \sum_i \kappa_p(\mu_{i,*}), \qquad S_C := \sum_j \kappa_p(\mu_{*,j}), \qquad S := S_R + S_C.

Then

S≥min⁡{12,pk1/4}.S \ge\min\left\{\frac{1}{2},\frac{\sqrt{p}}{k^{1/4}}\right\}.

Proof. If S≥1/2S \ge1/2, the claim is immediate. Assume S<1/2S < 1/2.

For every row ii, select the positions of its pp largest entries, or all its nonzero entries if there are fewer than pp. Do the same for every column. Let ν\nu be the matrix obtained from μ\mu by retaining only entries that were selected by neither their row nor their column.

The total mass deleted by row selections is at most ∑iτp(μi,∗)≤SR\sum_i \tau_p(\mu_{i,*}) \le S_R. The additional mass deleted by column selections is at most ∑jτp(μ∗,j)≤SC\sum_j \tau_p(\mu_{*,j}) \le S_C. Hence

∥ν∥1≥1−S>12.(12)\lVert\nu\rVert_1 \ge1-S > \frac{1}{2}. \tag*{(12)}

In each row, ν\nu is supported in the tail remaining after the pp largest row entries are removed. Therefore

∥νi,∗∥2≤σp(μi,∗)≤κp(μi,∗)p,\lVert\nu_{i,*}\rVert_2 \le\sigma_p(\mu_{i,*}) \le\frac{\kappa_p(\mu_{i,*})}{\sqrt{p}},

and summing over rows gives

∑i∥νi,∗∥2≤SRp.\sum_i\lVert\nu_{i,*}\rVert_2 \le\frac{S_R}{\sqrt{p}}.

Similarly,

∑j∥ν∗,j∥2≤SCp.\sum_j\lVert\nu_{*,j}\rVert_2 \le\frac{S_C}{\sqrt{p}}.

By Lemma 4.5,

∥ν∥4/3≤SRSCp≤S2p.(13)\lVert\nu\rVert_{4/3} \le\frac{\sqrt{S_RS_C}}{\sqrt{p}} \le\frac{S}{2\sqrt{p}}. \tag*{(13)}

Finally, ν\nu has at most kk nonzero entries, so Lemma 4.6 yields

∥ν∥1≤k1/4∥ν∥4/3.(14)\lVert\nu\rVert_1 \le k^{1/4}\lVert\nu\rVert_{4/3}. \tag*{(14)}

Combining (4.5), (4.6), and (4.7),

12<∥ν∥1≤k1/4S2p.\frac{1}{2} < \lVert\nu\rVert_1 \le k^{1/4}\frac{S}{2\sqrt{p}}.

Thus S>p/k1/4S > \sqrt{p}/k^{1/4}, as required.

Acknowledgement

We thank an anonymous reviewer for observing that symmetrizing the construction of Althöfer [1994] yields an Ω(log⁡2N)\Omega(\log^2 N) support lower bound for sufficiently small constant ε\varepsilon. Our result additionally establishes the tight ε−4\varepsilon^{-4} 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. [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. [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. [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. [4]Robert J Aumann. Subjectivity and correlation in randomized strategies. Journal of mathematical Economics, 1(1):67–96, 1974.
  5. [5]Robert J Aumann. Correlated equilibrium as an expression of bayesian rationality. Econometrica: Journal of the Econometric Society, pages 1–18, 1987.
  6. [6]Sergiu Hart and David Schmeidler. Existence of correlated equilibria. Mathematics of Operations Research, 14(1):18–25, 1989.
  7. [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. [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. [9]Ingo Althöfer. On sparse approximations to randomized strategies and convex combinations. Linear Algebra and its Applications, 199:339–355, 1994.DOI
  10. [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. [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. [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. [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. [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. [15]Yaron Azrieli and Eran Shmaya. Lipschitz games. Mathematics of Operations Research, 38(2):350–357, 2013.DOI
  16. [16]Stephen J Montgomery-Smith. The distribution of rademacher sums. Proceedings of the American Mathematical Society, 109(2):517–522, 1990.
  17. [17]Dumitru Popa and Gord Sinnamon. Blei’s inequality and coordinatewise multiple summing operators. Publicacions Matemàtiques, 57(2):455–475, 2013.

Paper details

vlnc:W_pxmpdyj5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents