← All setups

Near Zero Sum Own Gradients — Near-Zero-Sum Games

Descriptions may be stale. Consult the linked Lean sources.

Near-Zero-Sum Games · Lean proof

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.

Proved result

⌈16777216⋅Lmin{μ,ν}⋅min{μ,ν}+δμ+ν+δ⋅log⁡(2+D2ε)⋅log⁡(2+524288⋅L2⋅D2(min{μ,ν})2⋅ε)⌉+

OracleTemplate.Convergence LongTails.Setups.NearZeroSumGames.spec OracleTemplate.NearZeroSum.OwnGradients.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.