Monotone Near-Zero-Sum Games: A Generalization of Convex-Concave Minimax
Authors: Ruichen Luo
Sebastian U Stich
Krishnendu Chatterjee
Venue: ICLR 2026 Poster (2026)
Keywords: Non-zero-sum games; monotone games
Primary area: optimization

Abstract: Zero-sum and non-zero-sum (aka general-sum) games are relevant in a wide range of applications. 
While general non-zero-sum games are computationally hard, researchers focus
on the special class of monotone games for gradient-based algorithms.
However, there is a substantial gap between the gradient complexity of monotone zero-sum and monotone general-sum games. 
Moreover, in many practical scenarios of games the zero-sum assumption needs to be relaxed.
To address these issues, we define a new intermediate class of monotone near-zero-sum games that contains monotone zero-sum games as a special case. Then, we present a novel algorithm that transforms the near-zero-sum games into a sequence of zero-sum subproblems, improving the gradient-based complexity for the class. Finally, we demonstrate the applicability of this new
class to model practical scenarios of games motivated from the literature.

Published as a conference paper at ICLR 2026
MONOTONE NEAR- NERR-ZERO-SUM GAMES: A GENERALIZATION OF CONVEX-CONCAVE MINIMAX
Ruichen Luo"
Sebastian U. Stich CISPA Helmholtz Center 66386 St. Ingbert, Germany
Krishnendu Chatterjee
IST Austria 3400 Klosterneuburg, Austria
IST Austria
3400 Klosterneuburg, Austria
ABSTRACT
Zero-sum and non-zero-sum (aka general-sum) games are relevant in a wide range of applications. While general non-zero-sum games are computationally hard, researchers focus on the special class of monotone games for gradient-base algorithms. However, there a substantial gap between the gradient complexity of monotone zero-sum and monotone general-sum games. Moreover, in many practical scenarios of games the zero-sum assumption needs to be relaxed. To address these issues, we define new intermediate class of monotone neur-zero-sum games that contains monotone zero-sum games as a special case. Then, we present novel algorithm that transforms the near-zero-sum games into sequence of zero- sum subproblems, improving the gradient- based complexity for the class. Finally, demonstrate the applicability of this class model practical scenarios of games motivated from the literature.
INTRODUCTION
Two-player zero-sum games (also known as strictly competitive games) and their generalization to non-zero-sum games (Nash] 1951 Rosen 1965) are crucial in domains like economics (von Neumann & Morgenstern) 1947). artificial intelligence Yannakakis & Togelius 2018). and biology in the form of evolutionary game theory (Weibull 1997; Smith, 1982). As initiated in Rosen (1965); Tseng
(1995); Nemirovski (2004), this paper focues the computationally tractable class of monotone games with compact convex strategy spaces.
Early work studies the restrictive classes of games where the two players have equal conditioning: the seminal paper of Nesterov (2005) established the complexity for bilinearly- zero-sum games, which was later extended by Nemirovski (2004) to general-sum classes. Later on, the field explores the broader concept of general conditioning, which allows for more detailed portrayal of the two players (Chambolle & Pock 2011 Lin et al., (020). Early explorations of Chambolle & (ock((00T)) (20TT): (Chen et (2014) focus on the bilinearly-com couullee cases; starting from Lin et al. (2020). Aanerall-coonditione
Pock
there has been extensive research into the generally-coupled,
and zero-sum
games (Yang et al., 2020; Wang & Li 2020 Kovalev & Gasnikov [022] Lan & Li 2023 Boj al.) 2023). However, it has been an interesting open question whether these recent developments can be further generalized to the broader classes of generally-coupled, innerally-conditioned and
non-zero-sum games.
On the theory side, there is substantial gap between the gradient complexity of monotone zero-sum games and that of monotone general-sum games. The recent developments minimax optimiza-
tion (Lin et al. 2020: Kovalev & Gasnikov 2022 Lan & Li 2023) establish much better complexity results for the zero-sum cases compared to the long-standing bounds of general-sum games (Rock)
afellar 1976 Tseng 1995).
On the application side, strictly competitive scenarios, modeled by monotone zero-sum games, are often insufficient. Real-world game settings frequently involve factors such as transaction fees or semi-cooperation (Kalai & Kalai 2013 Halpern & Rong 2013). ) necessitating a relaxation of the zero-sum assumption in the modeling.
"This work partially done during RL's stay at CISPA.

---

Published as a conference paper at ICLR 2026
Our contributions Our work makes the first step towards bridging the gap between the monotone zero-sum and general-sum classes. For this purpose, we introduce a new intermediate class of monotone games, present a novel algorithm for this class, and show the applicability of this new class. In detail:
Theoretical motivation. Our work extends the recent studies of monotone zero-sum games to the more general non-zero-sum settings. Specifically, we define new intermediate class of games called monotone near-gero-sum games, characterized by smoothness parameter 8 describing the game's proximity zero-sum game. This new class of games presents natural interpolation between monotone zero-sum games and a class of monotone general-sum games based on the near-zero-sum parameter ö, and thus, partially bridges the gap of the monotone zero-sum and general-sum classes.
Main theoretical result. We propose a novel algorithm, Iterative Coupling Linearization (ICL), that provides a black box reduction from monotone near-zero-sum games to zero-sum games. It con- log"
verges to an e-Nash equilibrium within
(( (Vir + min[a.y min V
6 1+v
gradient queries where L is the smoothness parameter, and и/ are the strong concavity parame- ters of the two players, 8 is the near-zero-sun parameter, and D is the diameter. When is small, our results improve the long-standing complexity results of TfTse (1995); Nemirovski (2004) for the first time non-zero-sum classes.
Practical applications. Besides the theoretical motivation. we demonstrate the practical relevance of this new class of games. We consider regularized matrix games and competitive games with small additional incentives. These games are not zero-sum but naturally have a near-zero-sum structure, where our methods are applied to achieve provably faster rates.
2
DEFINITIONS, PREVIOUS RESULTS, AND THE NEW PROBLEM CLASS
2.1 BASIC DEFINITIONS
This paper studies the Nash Equilibrium Problem (NEP) for two-person general-sum games, in which Player wants to maximize its utility function uj (x.y) over E and Player wants to maximize its utility function u2 u2(x, (x,y) y) over y E Y. Here, X and Y are compact and convex sets, and u1 (..-)): :: X Y - R and : : X Y - R are smooth functions. A pair of decisions (x", "r,y") E X x Y is a Nash equilibrium if
"1( .y yx,, for all x E X, and u2(x", ,y" 2 u2(x", .y), for all Y.
pair of decisions (x E x x Y is an e-accurate Nash equilibriumm if there exists Nash equilibrium (x", such that ||x - x" is an c-approximate Nash equilibrium, if (8. 2 1 (x) u2(x, y) - for all y Y. The relation between accurate and approximate Nash equilibria is discussed in Appendix B The goal of this paper is to find e-accurate (or an s-approximate) Nash equilibrium by iterative algorithms which subsequently query the gradients of the utility functions.
+ x 12
-"11 < E. pair of decisions (x. y) E X Y for all x E X and ( y) >
Notations Let X' and y be Euclidean spaces. In the space X' x Y, for all z (x,y) X x y
and z' = (x'.y') E X' x V, define (z', z) = (x'xx + (y', y). For all these spaces, the norms are those induced by inner products. Assume that the diameter of X C X' bounded by Dx and the diameter of Y C y is bounded by Dy. Let D VD + DE. Assume that un (.. and u2(;)) are L-smooth, that is,
[Vu, (z') - Vu, (z)ll < L Iz' - 2/1, (z') [uz(z)) < L L z||, for all z e xxX.
To facilitate analysis, adopt the following formulation that decomposes the game into coupling part and zero-sum part. Denote
= -
2 (4r + u2).
h = 2 ( 41 + u2). H. = -yyh), F= - (VxU1, Vyuz)
In the 5(.) notations, the poly-logarithm terms are omitted.
2

---

Published as a conference paper at ICLR 2026
where g is the coupling part, h is the zero-sum part, 7 is the operator corresponding to the zero-sum part h, and F is the operator corresponding to the game. Then, we have
"1 = -9 h, U2 9 h, F= Vg H.
Since the utilities un and u2 are both L-smooth, have the functions g and h are both L-smooth, and the operators H and F are both I--Lipschitz continuous. While similar decompositions can be found in the literature of variational inequalities and game theory (Nemirovski 1995 Halpern & Rong, 2013) Chen et al., 20177 Hwang & Rey-Bellet 2020). we emphasize that this notation particularly suited to characterize our near-zero-sum games (to be defined later) for explicitly separating the non-zero-sum coupling part.
2.2 PROBLEM CLASSES
Monotone general-sum games The seminal work of Nash (1951); Rosen (1965) establishes the existence of Nash equilibrium for concave games. But to obtain tractable class of NEPs, further restrictions need to be considered (Rosen 1965). Specifically, we make the following assumptions:
Assumption (Convex-concave zero-sum part). There exists (p, v) E [0, LJ x [0, L] such that the function h(x,y) y) concave in y for any fixed X.
||x is convex in for any fixed E Y, and the function y) + - ||yl|2 is
Assumption 2 (jointly convex coupling part). The function 9(())) ) is jointly comvex
The operator 71 = (Vxh,- vyy h is monotone with modulus min // under Assumption | and the operator Vg is monotone under Assumption [ Hence, under Assumptions and [ the game (or the operator J = y + H) is monotone with modulus min ) (Rosen 1965; Nemirovski 1995
that is, (F(z') F F(z), z' z) min(u, ||z' =1|² for all z, EXXY.
In this paper, we refer to a game as a monotone (general-sung sum) game if satisfies Assumptions and and refer to game strongly monotone game if it is monotone game with modulus μr, v/ > 0. It is known that there exists a unique Nash equilibrium for strongly monotone games [ooenn 1965).
Monotone zero-sum games (convex-concave minimax optimization) We now consider subelass: monotone zero-sum games. A two-person game is zero-sum if = O. A game is said to be a monotone zero-sum game if it is zero-sum and satisfies Assumption [ Note that monotone zero-sum games trivially satisfy Assumption 2 (since O is convex), and therefore form a subclass of monotone general-sum games. By Sion's minimax theorem (Sion, T958), the NEP for monotone zero-sum games is equivalent to convex-concave minimax optimization, that is, finding or approaching a saddle point of the function -..,)).
2.3 PREVIOUS RESULTS
We begin with historical overview of the related study of NEPs for monotone games. Many prior studies focus on restrictive cases. Early seminal work by Nesterov and Nemirovski in the early 2000s primarily addressed the restrictive classes of games with equal conditioning (μ v). Nesterov] (2005) initially studied the allinearly-cupple which Nemirovski (2004) later generalized cover generally-coupled and general-sum settings. Subsequently, research has shifted towards the broader concept of general conditioning (μ + v). This shift is motivated by the need for more fiexible modeling of player behaviors in realistic problems and can lead to substantially faster convergence rates, particularly when one of the player has better conditioning (Chambolle & Pock 2011: Lin et al. 2020). Early explorations focus on the bilinearly-coupled and zero-sum cases, developing various primal-dual algorithms in different oracle settings (Chambolle & Pock 2011 Chen et al. 2014 Kolmogorov & Pock 2021 [Thekumparampi] et al. 2022). More recently, the seminal work of Lin et al. (2020) spurred extensive research into generally-coupled, ceneraaly-condiiionn (2020); Zhang al. (2022): Kovalev & Gasnikov (2022) ; Bot al. (2023) Lan & Li (2023 Lin
gqually-conditioned and zero-sum cases,
and zero-sum games (see Yang et al. (2020): Wang & Li
et al. (2025). among others).
Despite these advancements, are not aware of any study addressing the more general settings of generally-coupler generally-condiiionen and non-zero-sume games. For this particularly challenging
class, the only established results are the long-standing bounds from Tseng (1995); Nemirovski
3

---

Published as a conference paper at ICLR 2026
2004
These bounds, however, remain huge gap from the optimal rates achieved for the zero-sum
cases
Lin et al. 2020 Kovalev & Gasnikov 2022
Lan & Li, 2023).
Now, we formally outline the state-of-the-ar gradient complexity results of monotone general-sum and zero-sum games within the general settings of general couplings and general conditioning. To simplify the presentation,
assume strong monotonicity for now in the Section 2.3) while the results for non-strongly monotone games are indeed similar (as we will discuss later). For general-sum games, the NEPs can be solved using variational inequality methods for the operator F, leading to the following long-standing gradient complexity:
Proposition Tseng (1995)). For strongly monotone general-she games, an E-accurate Nash equilibrium can be found with the number of gradient queries bounded by O mmn (in()) .log
For the zero-sum cases, the gradient complexity can be significantly improved due to recent advances in minimax optimization.
Proposition (Lin al. (2020): Kovalev & Gasnikov (2022); Zhang et al. (022): Lan & (203
For strongly monotone zero-sum games, E-accurule Nash equilibrium can be found with the number of gradient queries bounded by
VTo L. .log (D²) This rate is minimax optimal, as
a
L Vue
log
gradient queries are required in general.
2.4 THE NEW PROBLEM CLASS
Theoretical motivation As shown in Propositions T and huge gap exists in the gradient complexities for solving NEPs for monotone general-sum games versus zero-sum games. This motivates the exploration of an intermediate problem class that partially bridges this gap.
Monotone near-zero-sum games We introduce the class of monotone ô-near-zero-sum games, which naturally interpolates between monotone zero-sum = 0f and general-sum (ō = L) games.
Assumption Near-zero-sum) Let E [0, L] such that the function g(.-)) is 8-smooth.
Definition (MONOTONE NEAR SERR--ERO-SUR GAMES). If two-person general-sum game satisfies Assumptions we call monotone 8 5-near-zero-sum game.
3
ALGORITHM AND CONVERGENCE ANALYSIS
We first focus the algorithm for strongly monotone near-zero-sum games in Sections and 3.2
Then, in Section 3.3 we present the results for (non-strongly) monotone near-zero-sum games.
3.1 ALGORITHM
For the zero-sum classes, Lin (2020); Kovalev Gasnikov (2022); Carmon al. 2022 Lan
Li (2023) obtained the optimal convergence rate by the Catalyst method (Lin et al.) 2018). However, the more general classes of non-zero-sum games, the application of Catalyst complicated by the fact that the regularized minimization transforms the problem into Stackelberg game, whose solution deviates significantly from Nash equilibrium (see Appendix [oor more details). Thus, we are not aware of how the similar smoothing techniques can be applied directly to non-zero-sum games.
This raises the challenge: can we leverage the off-the-shelf algorithms designed for zero-sum games to solve the non-zero-sum problems of interest? Now, we introduce our novel algorithm, lterative Coupling Linearization (ICL), which overcomes the aforementioned challenge and presents a clean black-box framework to solve near-zero-sum games by using zero-sum algorithms as an oracle.
II O-near-zero-sum game, let Player I maximize aj b y h(x.y) and Player maximize a x bJ y + f((x, y). respectively. The Nash equilibrium in the above game is the same as that the following zero-sum game: Player maximizes a bby yoly-1a h(x,y) and Player 2 maximizes -aj by y h(x,y).
4

---

Published as a conference paper at ICLR 2026
Algorithm Iterative Coupling Linearization (ICL)
Require: 2o = (Xo,yo
E
X
x Y.
1: for == 0, 1, T
do
Let (x)
def
Vt).(x).y)..a. + |xx - x+ll" 1(x, y) Yt).
277 lly - y=ll" (1)
2771
3: Find an inexact solution Ze+1 = (Xet1. C X Y to minxex maxyer (x such that
(2xP(( - x) -V-VVVpp(ee)): y) S Es, for X, yeY.
(2)
4: end for
Potential function Our algorithm leverages a natural potential function A: X Y + IR defined as:
A(z)
max XXY)XX
g(z) - (
-xx,,)
for all z = (x, y) X x Y.
Jointly convex coupling
CouNex-coneave zcro-sum
This potential function decomposes into a jointly convex coupling part and a convex-concat zero- sum part. We show below in Propositions 3 and 4 that minimizing this potential function 4(-) is sufficient for finding Nash equilibrium (with detailed proofs in Appendix D.II:
Proposition 3. For any yx, X Y, have A(z) 0 and
2A(z)
max (xxXx)
(x, U1 yx + u2(xx,
u2(
Proposition 4. Letz' E X x Y. In monotone games, z" is the Nash equilibrium iff A(z") 0.
Algorithm description Our ICL algorithm solves the strongly monotone near-zero-sum game by iteratively linearizing the coupling part, therehy transforming the non-zero-sum game into sequence of strongly monotone zero-sum subproblems. The pseudocode is presented in Algorithm
Specifically, at every iteration we linearize the coupling part in the potential function at ze:
min A(z) min max zEXxY
ZEXxY xEXXY (Vg(z.), 2- 2)+ (1 1|2 - 2 2.11²) (xx,))
1
21j
and note that this minimax optimization can fully decomposed into two separate problems:
min max (Vg(2e), (x, (x, -5) + y)
1
(Ix x 11 - -vll =x 3), and
xEX
27).
min max (Vg(z,), (-x, 1( MM( yEY sex
1
(- ||
x,I12 lly yall - (X,,
27).
Moreover, by Sion's minimax theorem Sion 1958 (after simple substitutions) these two separate problems unify into a single saddle point problem of minxex maxyey (e(xx,) where y is defined in Equation [p. The update 1 (x++1, 1x++))+++1 is then computed by inexactly solving this unifted saddle point problem, where the inexactness condition is specified in Equation (2). Our algorithm, thus, provides a clean and black-box reduction from near-zero-sum games to zero-sum games.
3.2 CONVERGENCE ANALYSIS
Throughout Section 3.2 let z (x",y") be the (unique) Nash equilibrium for the game. We only present the main proof ideas this section, and the detailed proofs can found Appendix [D.2] The core of our convergence analysis is to the properties of the potential function and derive the following descent lemma, based on which we have the outer loop convergence.
Lemma (Descent lemma). In monotone S-near-zero-sum games, for 1 S 1. Algorithm ensures
1
min
||
2011 S 2mp
||z - 20 + et-
2m
2
5

---

Published as a conference paper at ICLR 2026
Lemma 6 (Outer loop convergence). Let 7p. 77 (0, Rl for all t - Denote
0 +mmiiipp.ry Let EG I #s
min(a.))
Inj for all E [0, - For strongly monotone ô-near-zero-sum
games, if the outer loop iterate equilibrium, that is, ||z: - z E.
log 2D then Algorithm converges to e-uccurate Nash
For the inner loop, any optimal gradient method for zero-sum games can be used:
Lemma (Inner loop complexity (Kovalev & Gasnikov 2022 Carmon et al. 2022, Thekumparampil
et al.
2022 Lan & Li, 2023)). UUnder Assumption with modulus μ.v.
each iteration
t E
2 for 1p 2 L. the inexact solution (X++1. in Equation of Algorithm 7 can
be found with the number of gradient queries bounded by O +v) +2)
1.
log LDa
Combining the outer loop convergence result (Lemma 6) with the inner loop complexity (Lemma 7 obtain the main theoretical result of this paper, the overall gradient complexity of Algorithm
min(p.r) Theorem (Main theoretical result). Denote rj = min { mintuwy } and . +min Let
0c = and & Anj for all L E [ --,T-10 1] nz. For strongly monotone ō-near-zero-sum games, for T > 1 log 2D the outer loop iterates of Algorithm converge to an s-accurate Nash equilibrium with the number of gradient queries bounded by
o
VIN ((+ min =
L
)) -log
LD²
D2 E
min
(
1.
min w) log
v}
Finally, we highlight the conditions under which Algorithm Jacieves faster convergence rate compared to variational inequality methods (Tseng 1995).
REMARK 1 (Acceleration in strongly monotone near-zero-sum games). Consider strongly monotone near-zero-sum games where min (J,, v) +8 (max v²). The gradient complexity of Algorithm 7
log? (D which (ignoring logarithms) improves upon the
mingpuy
k+v
minturyy log
(22)) rate of variational inequality methods as stated in Proposition 1 recovers the optimal
also remark that for the special case of zero-sum games (ō 0), rate as stated in Proposition to a logarithm term.
loog
D2
3.3 ACCELERATION IN NON-STRONGLY MONOTONE ZERO-SUM GAMES
We first state the known results for non-strongly monotone games in literature. Proposition 8 (Nemirovski (2004)). In monotone general-sum games where μ = 0 or 0, an e-upproximate Nash equilibrium can be found within O
LD²
grudient queries.
Then, provide result, which is obtained by a similar reduction in Lin al. Li (2000;)): Thekumparampil et al. (2022). The proof can be found in Appendix D.3
2020): Wang &
Corollary 9. In monotone 5-mear-zero-sum games with modulus and v:
(a) For 4
> 0 and v LDD. min 1, (1) log" (LD²), gradient queries;
0, an e-approximate Nash equilibrium can be obtained within
δ LDy VIue
+
(b) For
= 0 and u > 0, an e-approximate Nash equilibrium can be obtained within
5
LDx Vive
LDR min
log" (DD2) gradient queries; and
+
(c) For = 0 and v = 0, an e-approximate Nash equilibrium can be obtained within
δ LD + LD² min 7 log" LD22) gradient queries.

---

Published as a conference paper at ICLR 2026
REMARK 2 (Acceleration in non-strongly monotone near-zero- games). For non-strongly monotone general-sue sum games, our rate of finding an E-approximate Nash equilibrium (ignoring logarithms) is faster than the O LD" rate in literature: (a) when ô o(p) and 0; (b) when f 0 and o(v); : (c) when j === == and s/D² ó o (s/D3 +//))) We also remark that for the special case of zero-sum games (8 = 0), our rates recover the optimal rates oi et al. 2020); Wang & Li (2020) up to logarithm terms.
Technical novelty Our technical contributions include novel coupling linearization technique and the derivation of a descent lemma (Lemma These elements combine to form a clean, general, and powerful black-box reduction. This reduction's 's key advantage is its ability solve monotone non-zero-sum problems by treating any off-the-shelf zero-sum algorithm as an oracle. Moreover, the inherent black-box nature of our method also allows for deriving complexity results for other oracle settings. For instance, we present some additional results with proximal oracles in Appendix
4 APPLICATION EXAMPLES
In this section, we present practical examples of monotone near-zero-sum games. We focus on the application of our approach, while the proof details are presented Appendix D.4
4.1 OUR APPROACH FOR REGULARIZED MATRIX GAMES
Regularized matrix games We demonstrate the applicability of Iterative Coupling Linearization to
regularized matrix games. Let X C R" and Y C R" be compact convex sets, and let A, B E m=** with || || S T., |B]|| s L., and 2 S 3. Let R. X Y + R be an [--sooohh regularizer that
is ju-strongly concave-u-stronggy convex. Let Player 1 maximize
"n (x, (Ax,y) y) + R(x,y)
over X E X and Player 2 maximize
(2 y) = (Bx, -((x,y)
over y E Y. Assume that B s V/u, then the game is min 5 5 -strongly monotone, so classic variational incquality methods yield an e-accurate Nash equilibrium within O min gradient queries (Tseng) 1995).
D2
logg
Now, we show that our ICL algorithm can be applied to get faster rate by leveraging the near-zero- sum structure. Since - [u, + u.)) :) is not jointly convex, violating Assumption 2 a "convex reformulation" technique.
we first apply
Convex reformulation technique Specifically, we choose the parameters 83 and Bg based on the
relationship between 2,3, μr, and w: (i) If 2/3 < and 2 & v, let 31 = BB2 ;9; (ii) if / < 23 <
let 31 P and B3 2.3 and (iii) if v < 23 < μ. let 31 2 and B3 2 With these choices.
we always have $1 S 2. B2 S 2. and 1 = B.
We then reformulate the problem as follows: Player maximizes ūn (x, y) un (xx B2 ||yl| over x E X, and Player 2 maximizes (2 y) = U2 (x,y) y) - B1 ||x|| over y E Y. This reformulated NEP has the same Nash equilibrium as the original. Let
A B
B 2
B2 |1yl13
o(x.y)
x,y
+
|x||
2
and
T((x,) (
A B
(R(x. +
Br
||x||
B2
|r
x.y
2
2
2
Then, ū, = - h and ū2 - + h. Since 8 < 1 2uV, by Cauchy-Schware inequality, g(.-) is jointly convex. Further, by the choices of 31 and B2, we have g(,, is (B + max(B1, (2),))))-m0 -smoohh,,h and h((,)) is stroonngyy convex- -strongly concave.
7

---

Published as a conference paper at ICLR 2026
Our approach applied to reformulated games Now applying Algorithm NEP, by Theorem we obtain an E-accurate Nash equilibrium with the number of gradient queries bounded by
| to the reformulated
((
L V
3 VPv
D2
log
min
When min (u, v) + o (WV) this rate surpasses the best-known O
(u.n( log D2
gradient complexity of variational inequality methods (T'segg) 1995]. This acceleration leveraging the near-zero-sum structure seems to be new result even in the well-studied context of matrix games. EXAMPLE (Matrix games with transaction fees). Consider regularized matrix games with transaction fees. Let X = Pn
{x E Rz | +... I, =1 and Y = Pm del {y Im y1 +.... V/m. = 1 Let M E Ruxx be the payoff matrix of Player 1 without trans- action fee, with -M as the payoff matrix of Player without transaction fee. Assume |[M]] L.
Denote M+ (M abs (M)) and M_ 2/( (-M++ abs (M))
def
Now, suppose there a transaction fee of p E [0,1] charged by some third party on every payment. Then, the payoff matrices of Player and Player 2 with transaction fees
= = (1 p)M - M and = M, + (1 p)M
Let R: X X - R be L-smooth regularizer that is p-strongly concave-u-stronge convex. Assume that p llabs (M)] = (VHD).
Let Player maximize u1 (x. (Ax,y) + R(x,y) over x X, and Player 2 maximize yz yxx,))R((s y) over E Y. Applying the convex reformulation and then Algorithm we obtain an E-accurate Nash equilibrium with the number of gradient queries bounded by
L
labs (M)l)
(D² (-r)
min 1 m}
-logg
VPv
Matrix games with transaction fees are analogous to many practical scenarios, for instance, (a) betting sites often set odds such that there overall no loss loss-gain (zero-sum game) but charge a small transaction fee; or (b) negotiation between two clients via trusted-third party that charges brokerage fee is another example of a case with small transaction fee.
4.2 OUR APPROACH FOR COMPETITIVE GAMES WITH SMALL ADDITIONAL INCENTIVES
We show the applicability of Iterative Coupling Linearization competitive games with small addi- tional incentives. Let X and be compact convex sets in Euclidean spaces. Let h: X x Y + R be the competition payoff function, which T-smooth and j-strroglly convex-u-strongly concave. Let g: X x Y + R be the additional incentive function, which is 3-smooth with 3 < L. Let Player maximize #1 - g over X, and Player maximize ug = -9 h over y Y.
We explore two scenarios where the games are min 4, -stroongyy monotone, to which our ICL algorithm as well as the classic variational inequalities (Tsseg 1995) be applied:
1. If ) is jointly convex and 3 = (max (1,, v)), applying Algorithm directly yields an e-accurate Nash equilibrium with the number of gradient queries bounded by
o ((1e min(u, ) V
(22
log?
+ )
2. If 1 = min(u, (u,K), w)), we first apply the "convex reformulation" technique. We reformulate the problem as follows: Player maximizes ü, (x, y) = un (xxx,)) y) - ||y|| over x E X, and Player maximizes (2(x,)) y) - 3 |x|| over E Y. This reformulated NEP has the same Nash equilibrium the original. Let - | (ū, ū2) and h --strongly convex- Maavex---strongeee concave, and ((.,) is jointly convex and 2,3-smooth.
ū u2) Then, h(.:)) is
abs (M) represents matrix of the same dimensions as M where each element is the absolute value of the corresponding element in M. concrete illustration is given in Appendix F
8

---

Published as a conference paper at ICLR 2026
Applying A to the reformulated NEP, obtain E-accurate Nash equilibrium with the number of gradient queries bounded by
L pM
Dc
①
log"
In both scenarios I and our gradient queries are fewer than the O min(muy log (0²))
(o)) gradient
queries of the classic variational inequality methods (T'sngg 1995).
EXAMPLE 2 (Competitive games with small cooperation incentives). Consider the games where cooperation coexists with competition. Let X C X, x Xn and Y S Y, x Yb be compact convex sets Euclidean spaces. For x = (Xa, Xb) X, x, X, represents Player I's effort in cooperation. and Xb Xb represents Player I's effort in competition (and similarly for y (Ya. E Y). Let fa: Xa x + be the cooperation incentive function given by
fa
R1(xx) + I(Xa: Ya) + R2(ys),
where the regularizer R1: X, - is p-stronnly convex and L-smooth, the function 9: X, Y, is jointly convex and B-smooth, and the regularizer RR: Y, -> R. is u-strongly convex and L-smooth. Let fo: Xb x Yo - R. be the competition v-sttrogly concave. Assume that 3
function, which is L-smooth and p-strongly convex-
Let Player 1 maximize 11 (x, = -a(aa Ya) - fo((x, yb) over x E X, and Player 2 maximize y) = - fa(Ka, Na) + (o). over E Y. Denoting h(x,y) = R2(xxs) + fo fo(X,,
Ry)).). the NEP can be reformulated Player maximizing ū1 (x. = -9 Ya) h(x,y)
over X X, and Player 2 maximizing ūz( y) -(x Yv) + h(x,y) over y E Y. Applying
Algorithmaaas detailed above, we obtain an e-accurate Nash equilibrium with the number of gradient queries bounded by
δ ( min(u, v
log" (D²)
D2
1 1
As final remark, the modeling of the coexistence of competition and cooperation has been well- researched (for instance, see the studies of Nash ( (9500 (953); Selten 1960); Raiffa (952); Kalai & Rosenthal (1978); ; Kalai & Kalai (2133; Halpern & Rong
(ongg(0013 (2013) on semi-cooperative games). Indeed, the scenarios where cooperation dominates, and optimization
these theories are often applied techniques have been used to accelerate the dominant cooperation part (Chen et al. 2017). Our work contributes to this line of research on cooiecoopeeative games where competition dominates, yet there is small cooperation incentive. For example, repeated Prisoners' dilemma with stochastic number of rounds with small cenefit-t--con ratio is an example of competition with small cooperation incentive (as benefit-loccost ratio b/c. is small) (Nowak) 2006a b Sigmund 2010). We give a more concrete illustration of donation games in Appendix
5 BASIC NUMERICAL EXPERIMENTS
We conducted basic numerical experiments to validate our theoretical results, focusing on ma- trix games with transaction fees in Example [ We set m 10000, μ 10 = 1, and & = 10-7. A sparse, random matrix M E mRx such that |[M]| = 1 was gen- erated. The regularizer was defined as R(x.y) = - || + ||yl We varied the transac- tion fee p from {0.00%, 0.03%, ... ...18%))...... Our implementation of ICL (Algorithm IT. detailed in Section 4.1 used the Lifted Primal-Dual method (Thekumparampil et al.) (022) for the in- ner loop. We compared ICL against the Optimistic Gradient Descent Ascent (OGDA) (Popov) 1980) and Exxra-Grraden (EG) (Korpelevich) 1976) methods for variational inequalities. More details and additional experiments are provided Appendix G and our code can be found here: https://qi htt.:g/hhu.cooooome http://cwmrreeeeellloo/o Mwwone/Mooooooooooooo Near Zero Www.SSummmmaa....
The numerical results, summarized in Table I demonstrate that: (i) our ICL algorithm converges faster when the game is closer to a zero-sum one; (ii) the classic variational inequality methods (EG or OGDA) do not benefit from the near-zero-se zero-sum structure; and (iii) our ICL algorithm is faster than the classic variational inequality methods when the game is sufficiently near-zero-sum. In particular,

---

Published as a conference paper at ICLR 2026
Table 1: Gradient query counts (in thousands) converge e-accurate Nash equilibrium under
various transaction fees, Error bars indicate 2-sigma variations across 10 independent runs.
Transaction Fee p
0.00%
0.03%
0.06%
0.09%
0.12%
0.13%
0.18%
Methods
ICL (Algorithm 1
9.1 4: 0.0
22.6 0.4
42.2 4 0.3
65.0 + 0.3
75.7 4 0.3
113.7 0.7
123.8 +: 0.6
OGDA (Popov
1980
93.9 0.5
93.9
+ 0.5
93.9 : 0.5
93.9 + 0.5
03.9 + 0.5
94.0 = 0.6
94.0 + 0.6
EG (Korpelevich 1976
132.9 - 0.8
132.9 0.8
132.9
=
0.
132.9 =.8
132.9
in the experiments, ICL requires fewer gradient queries converge to an e-accurate Nash equilibrium when the transaction fee S 0.12%. This empirical observation aligns with our theoretical prediction Example which suggests that ICL converges faster when p ||abs (M)ll < /pv 1%.
CONCLUSIONS, LIMITATIONS, AND FUTURE WORK
In this work we consider the class of monotone games and present a condition that naturally inter- polates between the zero-sum and non-zero-sum class. We develop an efficient gradient-base approach and show its applicability with several examples motivated from the literature.
There are some limitations our work: (a) our complexity there is log? (2)) dependency rather than single logarithm dependency, and whether this double logarithm dependency can be removed is an interesting question; and (b) whether lower-bound results can be obtained for the new class also remains challenging question and may involve difficult construction of non-quarn non-quadratic functions, especially given that the lower bound for the general-sum classes remains widely open relative to the long-standing upper bound established in Tseng 1995); Nemirovsk] (2004).
The current work focuses two-player monotone non-zero-sum games, which constitutes a cru- cial first step generalizing two-player monotone zero-sum games with general conditioning. natural, though highly non-trivial, extension involves generalizing our fast convergence rates to the multiplayer gear-zero-sum setting. We notice that, as a preliminary step, the fast rate in zero-sum games (Proposition 2 have not yet been extended multiplayer settings. Indeed, this preliminary step is conceptually challenging, as the zero-sum condition in multiplayer games does not imply the strict competition found in two-player games. Furthermore, classic reductions in von Neumann & Morgenstern 1947) show that an n-player general-sun game can be reduced to an (n + 1)-player zero-sum game by letting the (n+ 1)th player take the negative of the summation of the first players. This implies that three-player zero-sum games are inherently no easier than two-player general-sum games. These results suggest that achieving fast convergence rate in the multiplayer setting will likely require significantly stronger structural assumptions than the simple summation of utilities to zero. Hence, leave the full generalization to the multiplayer setting for future research.
In addition to the above theoretical aspects, there are several other interesting directions as well: for example, (a) exploring other applications of regularized matrix games with near-zero-sun payoff matrices is an interesting direction; and (b) in the research of semi-cooperative games where competition dominates, applying our methods more practical examples another fruitful direction for future research.
ACKNOWLEDGMENTS
The authors thank for the helpful discussion with Anton Rodomanov during the initial preparation of this project.
RL and KC acknowledge the support of ERC CoG 863818 (ForM-SMArt) and Austrian Science Fund (FWF) 10.55776/COE12.
Ethics statement
This is theoretical research without any ethics concern. All the experiments based randomly generated data. The only LLM usage is to aid or polish writing.
Reproducibility statement
10

---

Published as a conference paper at ICLR 2026
We include the detailed proofs of all the results in the Appendix. We include the source codes of all the experiments, including the scripts for the generation of random data. The codes are based on standard Python libraries (like numpy or scipy) and are easy run.
REFERENCES
Bharat Adsul, Jugal Garg, Ruta Mehta, Milind Sohoni, and Bernhard von Stengel. Fast algorithms for rank-1 1 bimatrix games. Operations Research, 69(2):613-63) 2021.
Radu Ioan Bot, Eruö Robert Csetnek, and Michael Sedlmayer. An accelerated minimax algorithm for convex-concave saddle point problems with nonsmooth coupling function. Computational Optimization and Applications, 86(3):925 966, 2023.
Ozan Candogan, Asuman Ozdaglar, and Pablo A Parrilo. Dynamics in near- near-potential games. Games and Economic Behavior, 82:66-90 90066-90,000 2013.
Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Recapp: Crafting more efficient catalyst for convex optimization. In International Conference Machine Learning, pp. 2658-2685. PMLR, 2022.
Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 4001):1 2011.
Yunmei Chen, Guanghui Lan, and Yuyuan Ouyang. Optimal primal-dual methods for class of saddle point problems. SIAM Journal on Optimization, 24(4): 2014.
Yunmei Chen, Guanghui Lan, and Yuyuan Ouyang. Accelerated schemes for class of variational inequalities. Mathematical Programming, 165: 165:113-149, 2017.
Joseph Halpern and Nan Rong. Cooperative equilibrium: A solution predicting cooperative play. In International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013), pp. 319-326, 2013.
Aamal Hussain, Francesco Belardinelli, and Georgios Piliouras. Beyond strict competition: ap- proximate convergence of multi-agent q-learning dynamics. In Proceedings of the Second International Joint Conference on Artificial Intelligence, IJCAI 23, 2023. ISBN 978-1-956792- /ta.e//3//aaaaa2223....
03-4. doi: 10. http3////caa..2231166
Sung- Ha Hwang and Luc Rey-Bellet. Strategic decompositions of normal form games: Zero-sum games and potential games. Games and Economic Behavior, 122:370-390, 2020.
Adam Kalai and Ehud Kalai. Cooperation in strategic games revisited. The Quarterly Journal of Economics, 128(2)9177-666. 2013.
Ehud Kalai and Robert W Rosenthal. Arbitration of two-party disputes under ignorance. International Journal of Game Theory, 7:65-72, 1978.
Ravi Kamnan and Thorsten Theobald. Games of fixed rank: A hierarchy of bimatrix games. Economic Theory, 42: 1733,, 2010.
Vladimir Kolmogorov and Thomas Pock. One-sided frank-wolfe algorithms for saddle problems. In International Conference on Machine Learning, pp. 5665-5675, PMLR, 2021.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Dmitry Kovalev and Alexander Gasnikov. The first optimal algorithm for smooth and strongly- convex-strongly-concaee minimax optimization. Advances in Neural Information Processing Systems, 35:14691 2022.
Guanghui Lan and Yan Li. A novel catalyst scheme for stochastic minimax optimization. arXiv preprint (XXx:2311.002// 2023.
11

---

Published as a conference paper at ICLR 2026
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. Catalyst acceleration for first-order convex optimization: from theory to practice. Journal of Machine Learning Research, 18(212):1-54, 2018.
Tinyi Lin, Chi Jin, and Michael Jordan. Near-optimal algorithms for minimax optimization. In Conference Learning Theory, pp. 3738-2779. PMLR, 2020.
Tianyi Lin, Chi Jin, and Michael Jordan. Two-timescale gradient descent ascent algorithms for nonconvex minimax optimization. Journal of Machine Learning Research, 26(11):1 (e:11):::45,, 2025.
Ruta Mehta. Constant rank two-player games are ppad-hard. SIAM Journal on Computing, 47(5): 1858-1887, 2018.
Aryan Mokhtari, Asuman E Ozdaglar, and Sarath Pattathil. Convergence rate of o1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, 30(4):323033211, 2020.
John Nash. The bargaining problem. Econometrica, 18(2):155-62,, 1950.
John Nash. Non-cooperative games. Annals Mathematics, 54(2), 1951.
John Nash. Two-person cooperative games. Econometrica: Journal of the Econometric Society, pp. 128-140, 1953.
Arkadi Nemirovski. Information-base complexity of convex programming. Lecture notes, 834, 1995.
Arkadi Nemirovski. Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-coneave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004.
A. S. Nemirovsky and D. B. Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience, 1983.
Yurüi Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 103: 127-152, 2005.
Yurü E. Nesterov. Introductory Lectures on Convex Optimization A Basic Course, volume 87 of Applied Optimization. Springer, 2004, ISBN 9781-44331111 doi:
9. wtt.:/tpp.//ooo..e////..00000000
Martin A Nowak. Evolutionary dynamics: exploring the equations of life. Harvard university press,
2006a.
Martin A Nowak. Five rules for the evolution of cooperation. science, (5650)))1160-11555 2006b.
Leonid Denisovich Popov. A modification of the Arrow-Hurwig method of search for saddle points. Mat. Zamerki, 28(5):777-784 1980.
Howard Raiffa. Arbitration schemes for generalized two-person games. 1952.
University of Michigan,
R Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5):877-898, 1976.
J Ben Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econo- metrica: Journal of the Econometric Society, pp. 520-534, 1965.
Reinhard Selten. Bewertung strategischer spiele. Zeitschrifi für die gesamte Staatswis- senschaft/Journal of Institutional and Theoretical Economies, H(2):221-282, 1960.
Karl Sigmund. The Calculus of Selfishness. Princeton University Press, Princeton, NJ, 2010. ISBN 978-0-691-14277-5.
12

---

Published as a conference paper at ICLR 2026
Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171-176 03 1958. ISSN 0030-8730. doi: 10.2140/pjm. 10211440pmmm19888... 1958.8.171. URLhtttps://ci..ii.... crid/ 0tl.///122225992209122222
John Maynard Smith. Evolution and the Theory of Games. Cambridge University Press, 1982.
Kiran Thekumparampil, Niao He, and Sewoong Oh. Lifted primal-dual method for bilinearly coupled smooth minimax optimization. In Gustau Camps- Gamps-Valls, Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 4281-4308. PMLR. 28-30 Mar 2022.
Paul Tseng. On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1-2):237-25,, 1995.
John von Neumann and Oskar Morgenstern. Theory of games and economic behavior. Princeton university press, 1947.
Yuanhao Wang and Jian Li. Improved algorithms for convex-concave minimax optimization. Ad- vances Neural Information Processing Systems, 33:4800 2020.
Jörgen W Weibull, Evolutionary game theory. MIT press, 1997.
Junchi Yang, Siqi Zhang, Negar Kiyavash, and Niao He. A catalyst framework for minimax optimization. Advances in Neural Information Processing Systems, 33:5667-5678, 2020.
Georgios N Yannakakis and Julian Togelius. Artificial intelligence and games, volume Springer, 2018.
Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194(1):901-935, 2022.
13

---

Published as a conference paper at ICLR 2026
A
RELATED WORK
We discuss other classes of games in the literature that bridge the gap between zero-sum and general- sum games.
Near network zero-sum games Near network zero-sum games (Hussain et al. (023) define class of games that is close to network zero-sum games in terms of maximum pairwise difference (Candogan) al. 2013 Hussain et al. 2023). Limited to the setting of two-person games, monotone near-zero- sum games considered in this paper differ in three aspects: (i) The utility functions in this paper can be general functions, rather than bilinear functions; (ii) the difference between near-zero-sum games and zero-sum games in this paper is characterized by (higher-order) smoothness parameter, rather than by function values; and (iii) the solution of near network zero-sum games is taken directly from the zero-sum case, which only guarantees convergence to neighborhood of the Nash equilibrium.
Rank-k games In the setting of matrix games, one of the most significant attempts on bridging the gap between zero-sum and non-zero-sum games is the class of Rank-k games introduced in Kannan & Theobald (2010). As a generalization of zero-sum matrix games, Kannan & Theobald (2010) study matrix games where rank(A (A + B) k, where A and B are the payoff matrices of the two players. To find an approximate Nash equilibrium, an FPTAS exists when & is small (Kannan & find exact Nash equilibrium, Rank-1 games can be solved in polynomial
Theobald 2010);; time (Adsul et al. 2021), while Rank-3 games are already PPAD-hard (Mehta 2018). It is crucial emphasize that monotone near-zero-sum games, considered in this paper, are fundamentally distinct from Rank-k games. Specifically: (i) The utility functions in this paper can be general functions, rather than bilinear functions; (ii) matrix games can be sufficiently near-zero-sum but still have full rank; and (ii) the focus of this paper is on gradient- the Nemirovsky- Yudin optimization model (Nemirovsky & Yudin 1983), while the study of Rank-k games focuses on algorithms and complexity on Turing machines.
algorithms and complexity within
B RELATIONS TO APPROXIMATE NASH EQUILIBRIUM
Indeed, approximate Nash equilibrium can be obtained from accurate Nash equilibrium Ne- mirovski] 2004). Below, we include this result for ceff-consiteenc.
Proposition 10 Nemirovski (2044). ) In monotone general-sum game, let z" (x', y") ) be the Nash equilibrium. Let z (x, X Y and y E (0, /21. We have
max xEX, JEY
in u1 - U1 (8. 8) + u2 (2 (2
max xeX, yEY
(F(x, (x, (x,
2
/
D& + D3 1z z"ll
where & def IIx (x + + (I 7 (x) and def IIy ( + u2
Proof. Denote x Ixx (x +
y+ Il (5 + U2 and z def
(x+, v+).
Consider any E X and y Y. By the assignment of x, we have
1
(Vzu
|
x||² (X.,
||x - x1|²
+
||x, - -x12. (3)
27
27
27
By the assignment of x,, we have
1
1
1
(V (X, x+)
|x4
x|| (Vxu (2,
||x
x||
+
||x x12 (4)
27
24
27
'In Euclidean space Q, for non-empty, closed, and convex set Q C Q and vertex u E Q, let IQ((u) del
denote the projection of onto Q, that is, TT( argmin ||u vll.
14

---

Published as a conference paper at ICLR 2026
In view of
(x, x- - x)
(Vxu x4 x} + (VxU1 (x. x x+)
1
x+ - x) (Vxu1(X,))
(Vxin {),
27 |x+ - x| + 27
||x x||²
|| |x+ - =
27
1
(x,1(8,3),88 - x) + (Vxu (X,
x)
|| x||
27
1
1
||x x|
|x+ x||
+ 24
24
3
(Vx (x, 8) - Vx (x, 8), x+ - 8)
||x - x||
x - x|1
(5)
27
27
1
1
+ 2yy
||x - x1
||+ x||
2n
1
1
L ||( 8) - 2|1 |||+ - x||
1|x x1
x1
27
27
1
||x - x||
1
| - x11
+ 2n
2y
L
(xx
2||²
1
||x x1|
+
1
||x
X
2
||x - x
2
2y
2
27
(where we have used 7
1
in the last inequality), and similarly,
V2L
(Vyu2(R, 9). - 8) 5
L
[x 3) 2
1 y
118
2-
1
18
- -
1
lly - -112 (6)
2
27
2-
27
we have
(F(2, 8), (8, - -(,
5
1 ||(x. 8) - E||² +
1
|| (x,
1
1|2 - (X1
V2
27
27
27
1
1
< 27
2 - 5112
| - 3)1
27
where we have used 7 < 1 in the last inequality.
/2l.
Taking (x) == (x", y") in Equation 7 for the moment, we get
|z+ zz I z" 1 2n (). - 5/
(8)
Finally, in view of
(F(X $), (x, {3)
1
1
|z 2)
2x ||+ - (x,5)11
27
||x x||² ||x - x11 + || 51 - I|y+ 812))
27
<
(|x
x + x+ xx| ||x x+ ll + Ily 5 + y+ -11 1ly ylll)
2y
1
(9)
<
(Dx ||x - x+ |1 + Dr 118 - l+
D& D3. / x+ 12 + ||y y++ 1|
<
D& + DE- // Iz - 1- 2 | 1
2
D& + D2. 1 z² ||
15

---

Published as a conference paper at ICLR 2026
have
un (x, x) - (x, + (2( - "2(x, S (F(x, (x, (x,
2 -VD + Dr 2 z
and the desired bound follows because X and y can take arbitrary points in X and Y, respectively.
We also state the following sufficient condition for the accurate Nash equilibrium, which can be used stopping criterion for the optimization algorithms. Similar results can be found, for instance, in Nemirovski (2004): Yang et al. 2220)).
Proposition 11 (Stopping criterion Nemirovski (2004); Yang et al. sum game, let z = (x', yy) be the Nash equilibrium. Let Z (1, v.. We have
2020 ). In a monotone general- (x
X N, (0, I and
4
2
1| z²11² 1
+ 16
||+
z|1² =zl?
1222
jry
where 2, II -F(()), in which & II (z - FF())).
Proof. We have
M7 (1
1|z =1"
(22 -1) ||z zl²
Ny
12 2²12
Iz 1 27 (F(2), z²)
< x 1/ 27 (F(2) F(x"), - -2-)
< 7 x-| 2112 - 2py 2 - -2"1' 1²1
< | 2112 - M7 1- 121 2 12 2||
(1 (7) 2/ - 2 247 22 2 2 + 4uz 12 - 2||
< (1 (7) 2 2-222 2
2n7
12
2 + 8,y 1Z 2 Spr ||, - -//²
$ (1 - μ4) z - z" 2² 2
22 z| 2 + 8uy
1z_ - & + +pp7 ||z - 7F(2) - - F
< (1 μ7) 2 x 2 2n07
2/ 2 + 8uyy Iz_ ž SpLi2'² 12 2|1
$ (1 n7) 2 2 + Suy
|z z||²
where in the second last inequality rearrangement.
7 21
1 Finally, the desired bound follows from
C DISCUSSIONS ON THE CATALYST METHODS
In this section, present the intuition of most existing algorithms for convex-coneave minimax optimization considering general conditioning, and explain why similar idea may not work directly when generalized to monotone near-zero-sum games.
Most of existing algorithms for minimax optimization with general conditioning are based on Catalyst (Lin al. 2018). In minimax optimization, have u u2 Assume without loss of generality that S v. The function f(x) del -u (x)) is p-strongly convex over x E X, in which (x) del' arg maxyey u2(x, At the core of these algorithms, they build a function and get inexact solution 8441 each iteration t:
x A3 arg min [f((x) del f(x) + 2 ||x - xx x1]
(10)
xeX
16

---

Published as a conference paper at ICLR 2026
The outer loop is an inexact accelerated proximal point algorithm with Ō ( log (t) it-
erations (Nesterov, 2005 Lin et al. 2018 Caammon et al., 2022), and the inner loop of solv- ing the smoothed Equation (10) can be any method with the number of gradient queries O log (t)) Tseng 1995). So, the total gradient complexity is
()) δ (
L log (
)
L L
)
!
log
=
=Ō
log
V
p
However, we try to apply the above Catalyst method to monotone non-zero-sum games, the algorithm may only converge Stackelberg solution, which can be very different from the Nash cquilibrium in non-zero-sum games.
EXAMPLE 3 (Stackelberg solution). Consider the case where X [0, 1] x [1,2] S R2 and
Y = 1-,,0 R. Let Player I maximize
u1 "1 9) (21 - 122 1
2 (x2 1)² 21y
over x E X. and Player 2 maximize
1
u2(x, v) 2 T2y (y + 1)2
over y E Y. Then, the Catalyst minimization of f(x) uu
i (x, v(x)) will lead to the Stackelberg
solution (x =
40 68
46 which is different from the Nash equilibrium (x (8 1) y
63
63
63
Therefore, are not aware of how the Catalyst methods for convex-concave minimax optimization can be applied in NEPs for non-zero-sum games.
D PROOF DETAILS
D.I PROOFS FOR THE RESULTS IN SECTION
Proof of Proposition For any z (x,y) XY,
A(z) 2 g(z) g(z) + h)x,,))
- ((x,)) =
and for all 7
y) X Y, have
1 2 [g(z) g(x f) + h(xx h(xx y)] + [g(z) g v) + k(x,)) ((x,
1
A(z)
1
[2g(z) + (2, 3) + un y)]
2
2 un (x, (x) [x,
un
Proof of Proposition The (if) part follows directly from Proposition 3 Now we prove the (only if)
part. Suppose z y is the Nash equilibrium. For all z (x E x Y,
g(z") (z) + h(x", y lxx,yy)) < (Vg(z"), = - 2) + (H z" 2) < 0,
where in the first inequality
Assumptions and Then, have A(z') 0.
'The double logarithm term may be avoided by combining this algorithmic idea with some complicated
techniques (Kovalev & Gasnikov 2022 Carmon et al. 2022). which we omit here for the simplicity of presentation.
17

---

Published as a conference paper at ICLR 2026
D.2 PROOFS FOR THE RESULTS SECTION 3.2
The main technical work in the convergence analysis is to use the properties of our potential function and prove the descent lemma (Lemma
Proof of Lemma 5 By Assumption ! we can upper bound the convex zero-sum part
h(x++1,8") - h(xx, ye+1) = h(x(41, - h(x", Ye+1) + h(xx+1,y") - ((+x(+1)
S (xt1(
x*) # 1x++1-x111
(Vyh(x+11 Yt+1 y²) - 1 2
2 |lyc+1 - y²11
(H((++1), Ze+1 z²)
||x - x" 1|2 1ly++1 - y²11²
2
(11)
By Assumptions and 3. we can upper bound the jointly convex coupling part
g(((+1) g(z") = g(((+1) g(z,) + +(()) - g(z")
5
S (Vg(ze), 2 - -z1) +
|z(+1 - ztll + (Vg(z)), 21 z²)
2
(12)
8
= (Vg(ze), Zc+1 x²) + 2
|,+11 2rl1
In view of
(2t+1 Ze, 21+1 - 2²) = || - 2²" 2²112-
1
1|z - x- 221 + || - 2, 2:12, (13)
and
Vg((z)) + 71(z(+1) 1
(2(+1 21): 21+1 z²'
1)t
(Vxx) X|++1 -x") (Vygr(z++1) Ye+1 -y")
(14)
Et.
we have
0 -zz") S g(((+1) ) + ((xx+1,)y) -
xx11| - 1 (Vg(z)) + Hl(z+ 1), 20+1-11 -x") " ||x411-x111
|ly++1 - -y"1 |||2+1 - -zll2
-
Vo(zi) + 71(((41)+ + 17
(2141 21), Z++1 - zz"
(z++1 Ze. Zt+1 =²)
171
/
||x+1 x=
Ilye41 - -y112
2 1 - zell
2
2
Et.
+ 21/
||: - 112
+
||x++1 - 11
2t/
2
2T ly 11 - 277
1
1
+
v/
Ily++1 - 1²1
5
|z111 - -zz12
2
2m
2
where the first equality follows from Proposition 4 and the first inequality follows from the definition of A(-. Finally, the desired bound follows from 7) S J.
With Lemma 5 we are ready to prove the complexity of the outer loop (Lemma 6
Proof of Lemma 0 For monotone 5-nearly-zero-sum games and v S 1 3. by Lemma 5 for any E [0,t
1] n Z, we have
|z
22122 s - 0) 2|ze 2" 2²12 27Ex.
18

---

Published as a conference paper at ICLR 2026
Then, unrolling this recursion (from is f - 1, - .,,
to 0) yields
12 -22-2"11 51 120-- -2"1 27y
(1
k=
5 (1- 0) + +D3) + 27
max
Ek
ke|0,t-1ln2
$ +
E,
where the last inequality follows from log + and E S de 4nj
e
Below, we also include the proof of the gradient complexity of the inner loops for completeness. This result of the inner loops is heavily based the previous results of optimal gradient methods in minimax optimization (see, for instance, Kovalev & Gasnikov (2022); Carmon et al. (2022):
Thekumparampil al. (2022): Lan & Li 2023)).
Proof of Lemmal 7 Let 2 (144))441) E X x Y denote the saddle point of (p()))). Denote
& SL2 8L2 (D) + D2)
By Proposition 10 an inexact solution in Equation 22) of Algorithm 1 can be obtained from pair of decisions Zt+1 &8+1. E X x Y that satisfies [ 2, E
The function -)((-.) (n,- p1) sttongly convex- (1 + v) strongly concave and 2L-smooth,
where the 27--mmothhesss follows from 7) 2 +. Hence, by Kovalev & Gasnikov (2022); Carmon
al. (2022); Thekumparampil et al. (2022) Lan & Li (202)), the atorementioned pair of decisions
Z141 can be found within
L
D3 + D2 +
)
O
log
(ne"
+ 14) (ne + tv)
gradient queries. Finally, after substituting the E,, the desired bound follows.
Finally, we prove Theorem our main theoretical result.
Proof of Theorem The overall gradient complexity is given by the multiplication of outer loop iterations (Lemma 6 and inner loop gradient complexity (Lemma 7
+ min(u,
2(D3 + +D²))
L
log T(D3 + D3.
0
log
min(w,
E
Vin (n
Er
+ min(H,e) v) min(u,e)
D& + Dē E
L(D + DE
log
log
V + 1J) v)
min( .
I. min(u, v}
8 min v3
T. + D&)
D3 + DJ.
V
8 maxi m
log
mintur v/
log
E
=o
V
min
1,
log
L ( D&
log
D + D3
min(p,v)
min(u.)) u)
where the first relation follows from min min(a.y
19

---

Published as a conference paper at ICLR 2026
D.3 PROOFS FOR THE RESULT IN SECTION 3.3
We state a more general formulation of Corollary
9
Corollary 12. For monotone d-near-zero-sum games where μt 0 or = 0, an E-approximate Nash equilibrium be found within
o (1
+
L
min (1.V i - m+=e))
1) log
L2DD2
LD
log
min
min(U, DJ.
gradient queries, where j pe min
2 1i] and - min
2D2 L
Proof of Corollary 12
We consider the reduced game where Player maximizes
ú1 min
E
L
||x|| 2 +
min
E 4D3 2 |yyl
4D3
2
over x E X and Player 2 maximizes
L 2
L |y|l
ú2 + min
|
min
4
4D2.
over y E Y. Any 5-approximate Nash equilibrium of the reduced game is e-approximate Nash equilibrium in the original game. This reduction is similar to the ones used in Lin et al. (2020); Wang
Li (2020).
Denote 9 - (ā + i2) and & (- + u2). Then, we have h = h + 4D3 2 |xx|| c IDz
2 || which is 2L-smooth and j-stroogly convex-ü-strongly concave. We also have (1 ú2)) - ) (u1 + u2) g. which is jointly convex and d-smooth. By Theorem
2² obtain the number of gradient queries for an 321"1" accurate Nash equilibrium in the reduced game:
o (
L min 1, ( mi
L2D2 ) log min 0) -
LD
log
Finally, following from Proposition 10 we obtain the desired 5-approximate Nash equilibrium of the reduced game by taking an extragradient step from the 32 Terpr-accurate accurate Nash equilibrium.
D.4 PROOFS FOR THE RESULTS IN SECTION
Proposition 13 (Convex reformulation bilinear coupling). For 31, 32 and E Rmxx such that v B3,32 2 [M]] the function o(,,)) Te x Imm IR. defined as
81 |x|| + (Mx,)) +
B2 2
g(x. y)
|yl
jointly convex.
Proof. The quadratic function g(..)) is bounded below: for all x
E R², E RT.
B2
y(x,y)
|||| - ||Mx|| ||y || +
|2
2
B2
IV 0,
|||||
8, x
||yl|
+
|1
2
where the first inequality we used the Cauchy-Schware Schwarz incquality. Therefore, 7(..) is jointly convex.
20

---

Published as a conference paper at ICLR 2026
Proposition 14 (Convex reformulation in general coupling). For B 2 0 and g: :X x Y R such that .): B-smooth, the function g(:.-) X + R defined as
B ||*| +gxx + 8 yy|
g(x.y)
2
jointly convex.
Proof. For all z = (x. E X x Y and z' = y') E X x Y, we have
(ozzz)-VV(11) z) 3 ||z
z|| (Vg(z') Vg(z), -2)
2 8 || z _ B ||z - 2||
0,
where the first inequality follows from the 8-smoothness of g-:-). Therefore, the function g(.-) is jointly convex (Nesterov 2004 Theorem 2.1.3).
E ADDITIONAL RESULTS FOR OTHER ORACLE AND FUNCTION CLASSES
In this section, we consider different class of Nash equilibrium problem and demonstrate the applicability of our ICL framework. In Bot et al. (2023), they considered zero-sum (or strictly competitive) game where the two players have proximal oracle and gradient oracle, respectively. We now consider the generalization where an additional incentive added. To prevent ambiguity, we will define the problem class in a self-contained way.
In this section, we are interested in the Nash equilibrium problem, or equivalently, the variational inequality problem given by operator F defined on X x Y:
F(x,y) = Vg(x. y) + Vxh(x,y) VVh(xxy) + Vv(y)), (x.y)
where
1. The sets X and Y are compact convex sets in Euclidean spaces. The diameter of X is bounded by Dx, and the diameter of Y bounded by Dy.
The function g: X Y + R is 6-smooth and convex.
3. The function vb: Y - R (= is proper, lower semicontinuous, u-strongly convex, and with domain dom
(y
(yy) t00).
For all y dom v the function k(-.)): + R (RU(+))) proper, lower semi-continuous, and μ--ttronlyy convex.
For all x E xdom h) & (ueX Ev E Y such that (u, v) E dom h), we have that dom h(x, .) = Y and the function h(x, :): Y R is concave and continuously differentiable. Moreover, x (dom h) is closed.
6. There exists Lyz Lyy 2 such that for all (x, y), (a', v/= E 1Ix (dom h) x dom v
[V,,(x, - Vyl(x', y')ll < Lyz ||x - x' Lyg Ily - y'll
We assume the players can query the gradient Vg. the proximal operator of fi(-y) for any fixed y Y. the partial gradient vyh((,)), and the proximal oracle of (b.). The problem studied in Bog et al. (2023) corresponds to special case of the additional incentive = O, while we generalize their results to o 0.
We will use the complexity results in Bot et al. (2023) as a black box. We cite their results below. Lemma (Bot et al. (2023). Theorem 14). For 8= and μ > O, there exists an algorithu which returns an e-accurate Nash equilibrium with the number of partial gradient queries to Vyl(-) and the number of proximal oracle queries to prox and prox, bounded by
o
((1+
Lyz Vuu
Lug
D22 (2²))
+
log
v
By applying our ICL algorithm (Algorithm T). obtain the following complexity result:
21

---

Published as a conference paper at ICLR 2026
Theorem 2. Assume h is L-smooth over IIx (dom h) X dom v. and vb is L-smooth over dom sb For μ >> O, there exists an algorithm which returns an E-accurate Nash equilibrium with the number of partial gradient queries V y-h(()) and the number of proximal oracle queries proxa(-y) (:) and p-)x,(-) bounded by
(1+minttu and with the number of gradient queries to Vg(()) bounded by
(1+
Lye
Ly 8
LD minn( u).8
112
log
log
V(6 (1)
o ((1+ min(uur}
D2 E (e))
log
Proof. The result follows from multiplying the outer loop iterations in Lemma and the inner loop complexity in Lemma T3
F ILLUSTRATION OF THE APPLICATION EXAMPLES
Matrix games with transaction fees We give concrete illustration for matrix games with transaction fees. Let payoff matrices Player and Player without transaction fees be
300
-200
-300
200
M
and
MM
100
400
100
-400
respectively. Then,
300
200
300
0
0
200
abs (M)
M
and
M_
100
400
0
400
100
Let 1% of transaction fees imposed on every payment. Then, the payoff matrices of Player and Player 2 with transaction fees
297
200
-30
198
A
and B
100
396
99
-400
respectively. We also draw the Table 2 for easier comparisons.
Table 2: An illustration of matrix games with transaction fee p 0.01.
300/-300 -200/200
297/-300 -200/198
-100/100
400/-400
-100/99
396/-400
Competitive games with small cooperation incentives We give a concrete illustration for com- petitive games with small cooperation incentives. The donation games are canonical model in evolutionary game theory for studying the altruistic collaboration (Nowak) 2006a (Sigmund 2010).
Let us consider simplified version of donation games played for one round, as shown in Table 3 In this game, player can choose to incur a personal cost, c, to provide larger benefit, b, another player. Consider concrete example where the cost to donate only slightly higher at = 51.
50 and the benefit conferred is
In this scenario, if both players cooperate, they each pay cost of 50 and receive benefit of 51, resulting a modest net payoff of However, the temptation to defect is substantial: by withholding their own donation while still receiving the benefit from the other player, defector payoff of 51. Conversely, the cooperating player who is defected upon is left with a "sucker's payoff" of -0. This low benefit-to-cost ratio (b/c 1.02) creates very small incentive for cooperation.
achieve
22

---

Published as a conference paper at ICLR 2026
Table 3: An illustration of donation games.
Player 2: Cooperate
Player 2: Defect
Player Cooperate
(1, I)
(-50, 51)
Player 1: Defect
-50)
(0, 0)
G MORE EXPERIMENTAL DETAILS
G.1 IMPLEMENTATION DETAILS
We generate the sparse matrix M following the procedures outlined in Nemirovski (2004); Nesterov (2005): (i) The random seeds set from 111, 222, ... and 999; (ii) 100000 coordinates of M chosen uniformly at random; (iii) each chosen coordinate is assigned random value independently drawn from a uniform distribution between [-1, 1]; (iv) all remaining coordinates are set O.
The classic OGDA and classic EG methods are implemented as outlined in Popov 1980) and Korpelevich (176)), respectively, All solvers are initialized at (Xo. Vo) = -11,, n, m m., where 1 E I denotes the vector of size k where every element in the vector is equal 1. The setup for ICL is detailed in Theorem [ The stepsize for OGDA is set to 5T. following Popov 1980); Mokhtari et al. (2020), and for EG is set to
We implement our ICL method as described in Algorithm
v2L following Korpelevich 1976); Nemirovski (2004). For the inner loop, the Lifted Primal Dual method (Thekumparmmpl et 2022) is used, with the theoretical setup maintained as specified in
(Thekumprrampil et al. 2022 Theorem 2).
G.2 MORE DETAILS OF THE EXPERIMENT RUNS
We conducted our experiments on e2 e2-highopp vCPUs within the Google Cloud environment. The memory requirement of our experiments is quite modest, requiring only sufficient RAM for few 10000 x 10000 sparse matrices (that is, about 60 MB). Each independent run completes within about 3 minutes.
We plot the convergence behaviors in Figure Note that for ICL, only iterates within the outer loop are plotted. Figure I shows results for single seed (seed 0), as plotting all seeds in a single figure would introduce excessive visual complexity due to the unaligned æ--axis representing the counts of gradient queries in the outer loop. Nonetheless, we observed consistent convergence patterns across different seeds: (i) Transaction fee changes have little impact the convergence of OGDA and EG, but significantly accelerate the convergence of ICL as p decreases; (ii) ICL converges fastest when p 0. 12%; and (iii) OGDA converges fastest when p 2 0.15%.
[shows
We should clarify that all 21 entries (7 entries for each of the three algorithms) are indeed plotted in Figure ! The perceived "lack of distinct lines" is actually a crucial empirical result supporting our theoretical claims:
For OGDA (Red) and EG (Green): The seven lines corresponding to different parameter settings for OGDA and EG almost completely merge and overlap. This empirical observation is fully consistent with our theory, which states that the convergence rate of classical variational inequality methods does not benefit from the near-zero-sum structure. Their rates determined solely by L min(a.e} regardless the 8 parameter.
For the proposed ICL algorithm (Blue): The seven lines are clearly separated, showing distinct dependency on the 8 parameter. This separation empirically validates our key claim that our algorithm successfully harnesses the near-zero-sum structure to achieve faster convergence rate.
Finally, we report CPU times of experiment runs to converge to an e-accurate Nash equilibrium in Table 4 with error bars indicating 2- 2-sigma variations across 10 independent runs using randomly generated matrices. Table shows
shows that ICL achieves the shortest CPU time when p < 0.12%, while OGDA achieves the shortest CPU time when p 2 0.15%.
23

---

Fublished as a conference paper at ICLR 2026
100000
EG (p=0.000 (p=0.0%) 0.0%)
EG (p=0.033%
(p=0.005 0..6%
(p=000000) (000.99%)
(p=0.12%)
EG (p=0.15%%
EG (p=0.18%
Figure 1: Comparisons of the convergence of the ICL. OGDA, and EG methods with respect the gradient query counts.
OGDA (p=0 0.0)
OGDA (p=0 0.0%%)
OGDA (p=0 0.06%)
OGDA (p=0 0.0%)
OGDA (p=0.12%)
OGDA (p=0.15%)
OGDA (p=0.18%)
80000
ICL (p=0.0%)
ICL (p=0.03%)
ICL (p=0.06%)
ICL (p=0.09%)
ICL (p=0.12%)
ICL (p=0.115)
ICL (p=0.18%)
60000
# Gradient queries
40000
20000
10.3.
10
10-7
ell y -ll
+ zll x
24

---

Published as a conference paper at ICLR 2026
Table 4: The CPU times (in seconds) of the algorithms converge e-accurate Nash equilibrium under various transaction fees. The error bars indicate 2-sigma variations across the independent runs with 10 randomly generated matrices.
Transaction fee
0.00%
0.03%
0.06%
0.09%
0.12%
0.15%
0.18%
Methods
ICL (Algorithm
+ 185 +
93
167
247 +
264
OGDA (Popov 1980
186 +
185
185 =
185 +
185 +
186 1 257 =
EG KKrpelevich
1976
258 +
256
+ 2
258 : 2
257 =
257
257 :
G.3 ADDITIONAL RUNS UNDER DIFFERENT PARAMETER SETTING
In this section, we run additional numerical experiments under different parameter setting. We change the parameter 0.01, and vary the transaction fee ē from {0.0%, 0.3%, .... 1.8%). We keep the other parameter settings unchanged.
The results, summarized in Table55, demonstrate that ICL requires fewer gradient queries to converge an e-accurate Nash equilibrium when the transaction fee is below 1.2%. This empirical observation aligns with our theoretical prediction in Example which suggests that ICL converges faster when abs (M) < vpv 10%.
Table 5: Gradient query counts to converge to e-accurate Nash equilibrium under various trans- action fees. Error bars indicate 2-sigma variations across the independent runs with 10 randomly generated matrices.
Transaction fee p
0.0%
0.3%
0.6%
0.9%
1.2%
1.5%
1.8%
Methods
ICL (Algorithm
924
924
824 0
1030 0
1236 +
1648 0
2060 0
OGDA (Popov 1980
1364 0
1364
1361
1359 =
1353
1350 =
Korpelevich 1976
1848 0
1848
1848 0
1848 =
1848 +
1848
0
We also observe that the CPU times in this setting within 5 seconds for all independent runs.
25


Reviews:
[{"review_id": "7ZGStaIDPH", "reviewer": "Reviewer_eGdp", "summary": "The paper examines a new class of games that interpolates between zero-sum monotone games and general-sum monotone games. It is motivated by a gap between solving monotone zero-sum games and monotone general-sum games. The main contribution is an algorithm that improves the iteration complexity for that class. It finally provides some motivating examples together with some numerical results.", "questions": "- In the experiments, can the authors also report the gap of the average iterate of OGDA instead of its last iterate? In theory that should converge faster. It would also be interesting to see whether alternating instead of simultaneous updates make a difference in that experiment. \n- Can the authors provide more experiments using the class of competitive games with small cooperation incentives? Is there some specific setting in economics that naturally satisfies this assumption?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well written and examines a concrete problem. To my knowledge, the gap in the number of gradients needed between monotone zero-sum and monotone general-sum has been unexplored. This gap can be substantial, which motivates the main contribution of the paper. The paper also does a good job at explaining the technical steps and highlighting the technical contribution compared to existing techniques. The proposed algorithm is quite natural and clean; I didn't find any notable issues in the technical steps.", "weaknesses": "Overall, I believe the paper is lacking in motivating the significance of the new class of problems and providing good applications of it. Some of the examples discussed in Section 4 look pretty artificial. For example, this setting of matrix games with transaction fees hasn't been studied before, to my knowledge, and its significance is unclear. Concerning Example 2, combing competition with cooperation is, of course, very interesting. But the precise way it is formulated in that example appears to be again artificial. The paper would benefit a lot from having a good application that has been studied in the past and the community would appreciate. Otherwise, it is hard to see the significance of the paper.\n\nThe experimental section also doesn't go far enough. The only experiment is run on this setting of matrix games with transaction fees, and the improvement compared to OGDA only manifests itself for a narrow range of the parameter. The paper would benefit from expanding the set of experiments to include other domains where the method has an advantage.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iTty2X0Pqw", "reviewer": "Reviewer_F4W2", "summary": "In this paper, the authors targets on the gap between gradient complexity of monotone general game ($\\mathcal{O}(\\frac{L}{\\min\\{\\mu, \\nu\\}}\\cdot \\log(D^2/\\varepsilon)$) and monotone zero-sum game  ($\\mathcal{O}(\\frac{L}{\\sqrt{\\mu \\nu}}\\cdot \\log(D^2/\\varepsilon)$). To bridge this gap, the authors propose monotone near-zero-sum games , characterized by a smoothness paraemeter $\\delta$ describing the game's proximity to a zero-sum game. Then, the author present Iterative Coupling Linearization (ICL) algorithm that provide black-box reduction from monotone near-zero sum game to  zero-sum games and derive gradient complexity in-between the known ones of zero-sum and general-sum games.", "questions": "Would you expect a similar analysis and complexity improvement to extend to the multi-player setting? If not, could you elaborate on the main technical barriers that prevent such an extension? In particular, are there specific steps in the convergence proof or properties of the two-player potential function that fail to generalize when the number of players exceeds two?\n\nMoreover, could you provide additional examples or intuitions for practical game settings where the coupling part $g$ is expected to have a small smoothness parameter $\\delta$? In other words, in what types of real-world or commonly studied games would the near-zero-sum assumption $(\\delta<<L)$ naturally hold?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. The problem is theoretically well-motivated. The authors clearly identify a gap between the gradient complexities of monotone zero-sum and monotone general-sum games, and take a principled step toward bridging this gap through the introduction of a new intermediate class of monotone near-zero-sum games.\n2. The presentation is clear and well-structured. The decomposition of the potential function into a jointly convex coupling part and a convex–concave zero-sum part provides strong intuition that connects the problem formulation, algorithm design, and convergence analysis in a coherent way.\n3. The proposed Iterative Coupling Linearization (ICL) algorithm is conceptually novel and algorithmically elegant, and the the convergence analysis is technically rigorous.", "weaknesses": "My main concern is generalizability of the method presented in the paper and the overall contribution of the paper. \n1. The main theoretical results hinge on the near-zero-sum smoothness parameter $\\delta$ that measures how strongly coupled the game is. However, it remains unclear in which practical settings the $\\delta$-smoothness assumption naturally holds or how to estimate it empirically. Although it is formally bounded by the overall smoothness $L$, it is uncertain how often $\\delta$ would be sufficiently small in realistic problems to yield the claimed acceleration in convergence.\n2. In addition, the presented results are developed specifically for two-player games, whereas the classical gradient complexity results for monotone general-sum games (e.g., Tseng, 1995; Nemirovski, 2004) extend to arbitrary numbers of players. It would strengthen the contribution to discuss whether the proposed framework and analysis can be generalized to multi-player settings, or to explain the technical barriers that currently prevent such an extension.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RLwOwjXsFg", "reviewer": "Reviewer_AbM8", "summary": "The paper introduces a new class of two player games, termed “Monotone Near-Zero-Sum Games”, in between the classes of zero sum and general sum games. The class consists of games where averaging the utilities of the two players results in a smooth function, with the smoothness parameter $\\delta$ indicating the interpolation between the classes. One of the motivations of the paper for defining the class lies in the gap of gradient complexity, which is the theoretical focus of the paper, between zero and general sum games. The authors propose a novel algorithm whose complexity depends on $\\delta$ and matches, up to logarithmic terms, the state of the art results for both classes. Finally, they present some experimentation comparing their algorithm with previous methods in some families of games.", "questions": "Could you provide some additional examples of games that can be solved with your approach? Or some more illustrations, especially for the competitive games with small additional incentives? Also, could you include some references about the transaction fee games, even outside the literature of gradient complexity, as well as comparisons with different approaches to solve them? \n\nI will also add two minor comments:\nEquation (13) is incorrect. It should be 2 instead of $1/2$. (The substitution later on is correct)\nFigure 1 is somewhat confusing. Based on the text, I think that the best out of the 3 methods are depicted but that it is not clear from the figure itself. The legend is also confusing, with 21 entries but much fewer lines depicted. Also, it is not easy to tell some colors apart.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "On a conceptual level, the paper does take a step in filling the gap between zero sum and general sum games, introducing an interesting class. Moreover, from the technical side, the proofs require technical work. On the application side, the transaction fee games are interesting as a class so I appreciate a method that solves them efficiently.", "weaknesses": "I think that the weaker aspect of the paper lies in its applications. Aside from the example mentioned above, I am not sure about the practical relevance of the classes that can be captured within the presented framework.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9dzphqeP7M", "reviewer": "Reviewer_BPVS", "summary": "This paper studies the problem of computing NE in monotone games beyond the zero-sum regime. In particular, the authors define the class of monotone $\\delta$-near-zero-sum games, where the $\\delta$ parameter denotes that the coupled component of the game $g(\\cdot, \\cdot)$ is $\\delta$-smooth. This class interpolates between zero-sum ($\\delta=0$) and general-sum ($\\delta=L$) monotone games. While the zero-sum case has been well studied and admits minimax optimal algorithms, the general-case complexity from Tseng (1995) remains less well-studied. The paper describes a new algorithm called Iterative Coupling Linearization (ICL), which is shown to converge faster than existing methods when $\\delta$ is small enough, in both strongly and non-strongly monotone games. The algorithm relies on a linearization of the coupling part $g$, leading to a sequence of zero-sum subproblems. Finally, the paper exhibits several applications including regularized matrix games and competitive games with small cooperation incentives. The experiments are run on randomized examples of the former class, showing corroboration for the theoretical result.", "questions": "- Is it correct to say that recognizing that a game is $\\delta$-near-zero-sum is not a trivial task, since Assumption 3 is an existence statement? Are there other effective notions of closeness that are easier to verify?\n- No-regret algorithms have seen some success in converging to NE in multiplayer zero-sum monotone games, can a similar result potentially be established for ICL? Specifically, ICL's design relies heavily on the minimax (i.e. two player) formulation -- is there an extension that can work for games with more players?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well written and clear. The research question studied is of clear interest to the community, and is well-motivated in the introduction.\n- The use of the potential function and linearization in the design of ICL is a nice idea, and leads to improved/optimal convergence rates in certain game classes.\n- The applications given are nicely motivated and meaningfully extend the class of games for which we can guarantee fast convergence to Nash equilibria. The subsequent study of other similarly computationally 'easy' games seems to be a fruitful direction.\n- The technical components of the paper are clean and easy to digest.", "weaknesses": "- The presence of the quadratic log factor naturally brings up the question of whether this is an artifact of the algorithm proposed or a fundamental separation between zero-sum and non-zero-sum games. The paper contains only one 'main' theoretical result, which is itself not a weakness, but I would have liked to see more discussion or even some preliminary results towards establishing lower bounds. This is briefly mentioned in the concluding remarks, but I believe this should be given more focus by the authors. Can the authors comment on this?\n- The experiments given only pertain to Example 1. The ICL algorithm would be more compelling if some results can be shown in other examples or game classes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)