Descriptions may be stale. Consult the linked Lean sources.
Near-Zero-Sum Games
We study a two-player game on nonempty compact convex sets and , where are finite-dimensional real inner
product spaces. The players minimize and , respectively, where . The function
is strongly convex in the first
variable and strongly concave in the second; 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 ,
the goal is a feasible output with almost surely for one fixed
equilibrium , using the
product Euclidean norm.
Write and equip
with the inner product
and norm Define the players’ costs by and . Their respective problems, with
the other player’s action fixed, are The algorithm receives , a feasible starting point , and the parameters , whose
ranges are The
functions and are accessed through the oracle
described below.
Our assumptions:
Assumption 1 (Feasible geometry). The sets and are compact and convex, , , and
Assumption 2 (Game structure). For every , , and , Moreover,
is jointly convex on : for and ,
Assumption 3 (Within-domain smoothness). There exist
gradient selections such that, for every , as within , These selections satisfy, for all ,
Assumption 4 (Equilibrium existence). There exists
such
that Such a point is a Nash equilibrium.
Write and . At a feasible query , the exact game-gradient oracle
returns
A projection query may instead be made at any and returns , characterized by 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 , where is the law of the algorithm’s
randomness and is
independent of its realization.