← All setups

Near-Zero-Sum Games

Descriptions may be stale. Consult the linked Lean sources.

Near-Zero-Sum Games

We study a two-player game on nonempty compact convex sets X⊂E and Y⊂F, where E,F are finite-dimensional real inner product spaces. The players minimize h+g and g−h, respectively, where h,g:E×F→R. The function h is strongly convex in the first variable and strongly concave in the second; g is jointly convex. Their within-domain gradients satisfy Lipschitz bounds, and an equilibrium exists. The oracle returns the players’ own-variable gradients or a Euclidean projection. For ε>0, the goal is a feasible output z¯ with ∥z¯−z⋆∥2≤ε almost surely for one fixed equilibrium z⋆, using the product Euclidean norm.

Write Z=X×Y and equip E×F with the inner product and norm ⟨(x,y),(u,v)⟩=⟨x,u⟩E+⟨y,v⟩F,∥(x,y)∥2=∥x∥E2+∥y∥F2. Define the players’ costs by c1=h+g and c2=g−h. Their respective problems, with the other player’s action fixed, are minx∈Xc1(x,y),miny∈Yc2(x,y). The algorithm receives E,F,X,Y, a feasible starting point z0=(x0,y0), and the parameters L,μ,ν,δ,D,ε, whose ranges are 0<μ≤L,0<ν≤L,0≤δ≤L,D>0,ε>0. The functions h and g are accessed through the oracle described below.

Our assumptions:

Assumption 1 (Feasible geometry). The sets X and Y are compact and convex, x0∈X, y0∈Y, and ∥z−w∥≤D,z,w∈Z.

Assumption 2 (Game structure). For every t∈[0,1], x,x′∈X, and y,y′∈Y, h((1−t)x+tx′,y)≤(1−t)h(x,y)+th(x′,y)≤−μ2t(1−t)∥x−x′∥E2,h(x,(1−t)y+ty′)≥(1−t)h(x,y)+th(x,y′)≥+ν2t(1−t)∥y−y′∥F2. Moreover, g is jointly convex on Z: for z,w∈Z and t∈[0,1], g((1−t)z+tw)≤(1−t)g(z)+tg(w).

Assumption 3 (Within-domain smoothness). There exist gradient selections H,G:Z→E×F such that, for every z∈Z, as w→z within Z, h(w)−h(z)−⟨H(z),w−z⟩=o(∥w−z∥),g(w)−g(z)−⟨G(z),w−z⟩=o(∥w−z∥). These selections satisfy, for all z,w∈Z, ∥(H+G)(z)−(H+G)(w)∥≤L∥z−w∥,∥(H−G)(z)−(H−G)(w)∥≤L∥z−w∥,∥G(z)−G(w)∥≤δ∥z−w∥.

Assumption 4 (Equilibrium existence). There exists z⋆=(x⋆,y⋆)∈Z such that c1(x⋆,y⋆)≤c1(x,y⋆)for every x∈X,c2(x⋆,y⋆)≤c2(x⋆,y)for every y∈Y. Such a point is a Nash equilibrium.

Write H=(Hx,Hy) and G=(Gx,Gy). At a feasible query z∈Z, the exact game-gradient oracle returns V(z)=(Hx(z)+Gx(z),−Hy(z)+Gy(z)). A projection query may instead be made at any u∈E×F and returns ΠZ(u), characterized by ΠZ(u)∈Z,⟨u−ΠZ(u),w−ΠZ(u)⟩≤0for every w∈Z. Both types of query count toward the same total oracle-call budget.

After the allotted calls, the output must satisfy, for some fixed Nash equilibrium z⋆, z¯∈Z,∥z¯−z⋆∥2≤εP-a.s., where P is the law of the algorithm’s randomness and z⋆ is independent of its realization.

Results

Compact convex X⊂E, Y⊂F in finite-dimensional real inner-product spaces; feasible initial point; diam(X×Y)≤D. Player costs are h+g and g−h: h is μ-strongly convex in x and ν-strongly concave in y; g is jointly convex. Gradients within the domain exist, ∇(h±g) are L-Lipschitz, and ∇g is δ-Lipschitz. Here 0<μ,ν≤L, 0≤δ≤L, and D,ε>0. An equilibrium exists. Access: own gradients and exact Euclidean projection. Target: feasible zout with ∥zout−z⋆∥2≤ε for an equilibrium z⋆.

Near-zero-sum games: NearZeroSumGames.
Result Oracle complexity Novelty Limitations
(1) NearZeroSumOwnGradients (Ours) (⋆⋆⋆) (review) O(Lmm+δM+δℓ0ℓ1) own-gradient and projection calls, counted together.
(2) ICL (Luo et al. 2025, Thm. 1) O(Lmm+δM+δℓ0ℓ1) full-utility-gradient queries, ε≤D2. Projections not quantified. (1): Matches rate for ε≤D2 using own gradients instead of full utility gradients; no separate ∇g. Includes projection costs.
(3) Extragradient (Luo et al. 2025, Prop. 1) O(Lmℓ0) own-gradient and projection calls. (1): Faster when m+δM+δℓ12≪1. For δ=m, L=M=κm: O(κℓ0ℓ1) instead of O(κℓ0). (1): Extra factor ℓ1 when M≍m or δ≳M; needs separate curvature and coupling parameters and the decomposition structure.
(4) Zero-sum guarantee (Luo et al. 2025, Prop. 2) O(Lμνℓ0) gradient queries; δ=0 (affine g absorbed into the saddle objective). (1): Scope extends to δ>0. (1): Extra factor ℓ1 on the δ=0 overlap.

Abbr: m=min{μ,ν}, M=max{μ,ν}; log+⁡t=max{0,log⁡t}; ℓ0=1+log+⁡(D2/ε), ℓ1=1+log+⁡(L2D2/(m2ε)). Own-gradient query: (∇x(h+g),∇y(g−h)). Full-utility-gradient query: ∇(h+g) and ∇(g−h).

Luo, Ruichen, Sebastian U. Stich, and Krishnendu Chatterjee. 2025. Monotone Near-Zero-Sum Games: A Generalization of Convex-Concave Minimax. https://doi.org/10.48550/arXiv.2512.02690.

Lean setup