C73-15: A closed-certificate characterization for every fixed mirror-descent rule

C73-15: A closed-certificate characterization
for every fixed mirror-descent rule

Ji Ho Bae
LawAll AI

10 October 2026

The characterization is infinitary. No finite recognition algorithm, step-size-independent potential criterion, or familiar-game-class list is claimed. The construction retains the arbitrary specified regularizers and positive schedule, including allowed boundary iterates. The fixed mirror-descent family, schedule, and universal-interior-initialization target are the specialization C73-15 of the broader source agenda; the result does not classify every learning dynamic in that agenda.

Exact target and the form of the answer

Fix $d\ge1$ players and nonempty finite action sets $S_i$, $i=1,\ldots,d$, $X_i=\Delta(S_i)$, and $X=\prod_iX_i$. The fixed rule has proper lower-semicontinuous strictly convex regularizers $h_i:X_i\to\mathbb R\cup\{+\infty\}$, finite and differentiable on $\operatorname{relint} X_i$, and steps $\eta_t>0$. For a game's payoff array $U$, write $u_i^U$ for its multilinear extension and $v_i^U(x)_a=u_i^U(a,x_{-i})$. The exact simultaneous update is \begin{equation} x_i^{t+1}=\underset{p\in X_i}{\arg\max} \left\{\eta_t\langle v_i^U(x^t),p\rangle -h_i(p)+h_i(x_i^t) +\langle\nabla h_i(x_i^t),p-x_i^t\rangle\right\}. \label{wsref-0-65-71-3a-6d-64} \end{equation} We retain the canonical assumption that these updates are uniquely defined and remain in the declared gradient domain from every interior initialization. No assertion is made about a payoff array for which this assumed rule is undefined.

Our answer associates to $U$ countable trees $T_{a,b}(U)$, $a,b\in\mathbb N_{>0}$. Node validity is a finite closed feasibility problem: it uses fixed regularizer epigraphs, regularizer evaluations at interior probes and interpolated interior points, the specified steps, and explicit payoff polynomials. The interpolated points depend on the finite feasibility variables; the regularizers themselves remain fixed rule data. It contains no Nash set, convergence assertion, infinite trajectory, or gradient evaluation. The condition on the payoff array is \begin{equation} \boxed{\quad T_{a,b}(U)\text{ is well-founded for every }a,b\ge1.\quad} \label{wsref-0-65-71-3a-77-66} \end{equation} Equivalently each tree admits a strictly decreasing countable-ordinal ranking. The full definition is in Section 4. Sections 2--3 explain why its finite constraints encode interior-ray slopes and exact updates without imposing Fréchet differentiability or continuity of the boundary gradient.

Closed certificates for interior-ray slopes

For each $i$, fix an enumeration $(q_{i,\ell})_{\ell\ge1}$ of the rational points of $\operatorname{relint} X_i$. It is dense in $\operatorname{relint} X_i$, hence in $X_i$. All numbers $h_i(q_{i,\ell})$ are finite and fixed before testing $U$. For a singleton simplex repeat its unique point.

We normalize a declared gradient by choosing its representative $g$ with $\sum_{s\in S_i}g_s=0$. Adding a constant to all gradient coordinates has no effect on a Bregman divergence or on (eq:md). The proof uses only the defining directional property of a gradient on each interior ray: \begin{equation} \lim_{\theta\downarrow0} \frac{h_i(x+\theta(q-x))-h_i(x)}{\theta} =\langle\nabla h_i(x),q-x\rangle\qquad(q\in\operatorname{relint} X_i). \label{wsref-0-65-71-3a-64-70} \end{equation} This holds both for a Fréchet gradient and for a linear finite-domain Gâteaux gradient. We do not assert a uniform expansion at a boundary point, or finite regularizer values in a whole boundary neighborhood. A selected subgradient unrelated to these directional derivatives would be a different notion from the declared gradient.

\begin{samepage} For a fixed probe $q_\ell$, convexity makes its secant quotient \[
\phi_\ell(\theta)=\frac{h(x+\theta(q_\ell-x))-h(x)}{\theta},
\qquad 0<\theta\le1,
\] nondecreasing as a function of $\theta$. Its limit at zero is therefore its infimum, possibly an extended real number before the certificate is used. \end{samepage}

At a point where the original rule declares a gradient, (eq:dp) and (eq:d) identify the certificate vector with its normalized representative. Indeed their inner products with every $q_\ell-x$ agree. By density these vectors span the affine tangent space, and normalization removes the only ambiguity, an all-coordinate constant. We will use this identification only at points already identified as actual iterates of the declared rule.

These lemmas do not assume continuity of the boundary gradient. For a finite list of probes, (eq:g1) is closed. With an integer $N_{\ell,k}$ fixed, the interpolated point lies in the relative interior for every $x\in P$. Every coordinate of that point is at least the corresponding positive coordinate of $q_\ell/N_{\ell,k}$, so all such points belong to a compact subset of the relative interior. Thus $h(z_{\ell,k})$ is continuous in $x$, and both inequalities in (eq:g2) are closed. The epigraph condition $c\ge h(x)$ is closed by lower semicontinuity. These closure facts are the reason for retaining ray-specific denominators as integer node labels instead of assuming that finite mirror-descent trajectories depend continuously on their initialization.

Payoff polynomials and compact initial cores

Define pure-deviation regrets \begin{equation} R_{i,s}^U(x)=u_i^U(s,x_{-i})-u_i^U(x),\qquad R^U(x)=\max_{i,s}R_{i,s}^U(x). \label{wsref-0-65-71-3a-72} \end{equation} They are explicit polynomials in mixed-action probabilities, with coefficients from $U$. For example \begin{equation} u_i^U(x)=\sum_{z\in\prod_jS_j}U_i(z)\prod_jx_{j,z_j}, \qquad v_i^U(x)_s=\sum_{z_{-i}}U_i(s,z_{-i})\prod_{j\ne i}x_{j,z_j}. \label{wsref-0-65-71-3a-70} \end{equation} For an integer $a\ge1$, let \begin{equation} K_a=\{x\in X:x_{i,s}\ge1/a\text{ for every }i,s\}. \label{wsref-0-65-71-3a-6b} \end{equation} Each $K_a$ is compact, possibly empty, and $\bigcup_{a\ge1}K_a=\operatorname{relint} X$. Thus compact cores cover precisely all permitted initial profiles, even arbitrarily close to the boundary.

The finite node test and the payoff criterion

Fix $a,b\ge1$. A node of depth $r\ge1$ has only finite discrete labels:

• strictly increasing integer times $1\le T_1<\cdots<T_r$;
• player/action labels $(i_j,s_j)$, one for each marked time;
• positive integer bounds $B_t$, $1\le t\le T_r$;
• positive integer denominators $N_{i,t,\ell,k}$, $1\le i\le d$, $1\le t\le T_r$, $1\le\ell,k\le r$.

A depth-$r$ node is valid if the following finite system has a solution in variables $x^t\in X$, $c_{i,t}\in\mathbb R$, $g_{i,t}\in\mathbb R^{S_i}$, $1\le t\le T_r$:

1. Compact bounds and initial core: \begin{equation} x^1\in K_a,\qquad |c_{i,t}|\le B_t,\qquad |g_{i,t,s}|\le B_t,\qquad \sum_sg_{i,t,s}=0. \label{wsref-0-65-71-3a-66-31} \end{equation}
2. Epigraph and finite supporting probes: for every $i,t$, \begin{equation} c_{i,t}\ge h_i(x_i^t),\qquad E_{i,t,\ell}:=h_i(q_{i,\ell})-c_{i,t} -\langle g_{i,t},q_{i,\ell}-x_i^t\rangle\ge0 \quad(1\le\ell\le r). \label{wsref-0-65-71-3a-66-32} \end{equation}
3. Finite interior-ray secants: for every $i,t$ and $1\le\ell,k\le r$, put \[ z_{i,t,\ell,k}= \left(1-\frac1{N_{i,t,\ell,k}}\right)x_i^t +\frac{q_{i,\ell}}{N_{i,t,\ell,k}}. \] Require \begin{equation} 0\le h_i(z_{i,t,\ell,k})-c_{i,t} -\frac{\langle g_{i,t},q_{i,\ell}-x_i^t\rangle}{N_{i,t,\ell,k}} \le\frac{\|q_{i,\ell}-x_i^t\|}{kN_{i,t,\ell,k}}. \label{wsref-0-65-71-3a-66-33} \end{equation}
4. Finite update probes: for $1\le t<T_r$, every $i$, and $1\le\ell\le r$, \begin{equation} h_i(q_{i,\ell})-c_{i,t+1} -\left\langle g_{i,t}+\eta_t v_i^U(x^t), q_{i,\ell}-x_i^{t+1}\right\rangle\ge0. \label{wsref-0-65-71-3a-66-34} \end{equation}
5. Marked payoff gaps: \begin{equation} R_{i_j,s_j}^U(x^{T_j})\ge1/b\qquad(1\le j\le r). \label{wsref-0-65-71-3a-66-35} \end{equation}

Every test is finite and closed in its real feasibility variables. In particular, for each fixed denominator label the argument of the regularizer in (eq:f3) ranges in a compact subset of its relative interior, where it is continuous. The payoff dependence occurs only in the polynomials (eq:p), (eq:f4), and (eq:f5). Everything else belongs to the fixed rule and the fixed probe system. The root can be included even when $K_a$ is empty; then it has no valid children and is well-founded.

Proof of the full equivalence

Regret and distance have the same vanishing criterion. The function $R^U$ is continuous and nonnegative: a player's mixed payoff is a convex combination of its pure-action payoffs, so at least one of its pure deviations has nonnegative regret. Moreover $R^U(x)=0$ if and only if every pure deviation is unprofitable, which is equivalent by linearity to $x\in\operatorname{NE}(U)$. The Nash set is nonempty by the finite-game existence theorem [nash] and is closed in compact $X$.

For any sequence $z_t\in X$, if its distance to the Nash set tends to zero, uniform continuity of $R^U$ implies $R^U(z_t)\to0$. Conversely, if $R^U(z_t)\to0$ but its Nash distance does not, a subsequence with distance at least some $\varepsilon>0$ has a compact subsequential limit $z$. Continuity gives $R^U(z)=0$, hence $z\in\operatorname{NE}(U)$, a contradiction.

Failure of convergence produces an infinite branch. Suppose an actual trajectory from interior $x^1$ fails to approach the Nash set. Choose $a$ with $x^1\in K_a$. Its nonnegative regrets fail to tend to zero, so for some $b\ge1$ there are strictly increasing times $T_j$ with $R^U(x^{T_j})\ge1/b$. Choose a player and a pure action attaining this maximum at each such time.

Put $c_{i,t}=h_i(x_i^t)$, and let $g_{i,t}$ be the normalized relative gradient supplied by the declared rule. All these numbers are finite. Choose integer $B_t$ exceeding their absolute values. Property (eq:dp) and Lemma Lemma (Dense interior-ray certificate) supply integer denominators $N_{i,t,\ell,k}$ for every date, probe, and precision. Fix each such choice once. Lemma Lemma (Dense-probe optimizer certificate) applied to (eq:md) gives all the update inequalities. At depth $r$, the actual finite prefix through $T_r$ satisfies (eq:f1)--(eq:f5). Its labels extend the preceding node. These nodes form an infinite branch of $T_{a,b}(U)$, so (eq:wf) fails.

An infinite branch produces one exact bad trajectory. Conversely, suppose $T_{a,b}(U)$ has an infinite branch. Its marked times strictly increase and therefore tend to infinity. Along the branch every bound $B_t$ is eventually assigned and never changed. Each denominator $N_{i,t,\ell,k}$ is also eventually assigned and never changed.

At each depth choose one finite feasibility witness. Extend it beyond its last date by arbitrary points of the coordinate boxes \begin{equation} \prod_{t\ge1}\left[X\times \prod_i[-B_t,B_t]\times\prod_i[-B_t,B_t]^{S_i}\right]. \label{wsref-0-65-71-3a-62-6f-78} \end{equation} These boxes are all compact and nonempty. Extract a subsequence converging in the first date's coordinates, then a subsequence converging in the second date's coordinates, and so on. The diagonal subsequence converges coordinatewise to arrays $(x^t,c_{i,t},g_{i,t})_{t\ge1}$. Each constraint from any fixed node involves only finitely many coordinates and is closed; all sufficiently deep witnesses satisfy it. Its limit therefore satisfies that constraint. This proves simultaneously every constraint on the branch, without assuming continuity of a mirror-descent trajectory map.

For fixed $i,t$, each probe $\ell$ and precision $k$ eventually occurs in a branch node. Hence the limit arrays satisfy the full conditions of Lemma Lemma (Dense interior-ray certificate), with the same fixed denominator for each pair. It follows that $c_{i,t}=h_i(x_i^t)$, and the vector $g_{i,t}$ has the certified linear slopes on every fixed interior probe ray. We do not infer a full Fréchet gradient at an arbitrary coded boundary point. All update probes eventually occur as well, so Lemma Lemma (Dense-probe optimizer certificate) identifies $x_i^{t+1}$ as the maximizer with score $g_{i,t}+\eta_t v_i^U(x^t)$.

We now identify the sequence with the actual declared rule by induction. The first point belongs to $K_a\subseteq\operatorname{relint} X$, where the original gradient exists. Its directional slopes satisfy (eq:dp). The certified slopes (eq:d) match them on every probe ray, and the dense directions span the tangent space. Therefore $g_{i,1}$ is the original normalized gradient. The optimizer just identified is the original (eq:md) optimizer and is unique, so $x^2$ is the actual next iterate. The canonical admissibility assumption puts $x^2$ in the original declared gradient domain. At this known actual point, (eq:dp), the certified ray identities, and dense spanning again identify $g_{i,2}$ with the normalized original gradient. The same argument proves the assertion at every date.

This induction uses the original gradient-domain preservation; it does not deduce that arbitrary points admitted by a ray certificate belong to that domain. It permits the original finite-domain Gâteaux interpretation as well as the Fréchet interpretation, and does not require the regularizer to be finite near an allowed boundary iterate.

Finally all marked inequalities (eq:f5) survive in the limit, so $R^U(x^{T_j})\ge1/b$ at infinitely many dates. This trajectory does not approach the Nash set. We have proved the equivalence of assertions 1 and 2.

The ordinal version. For a countable well-founded tree, well-founded recursion defines \[ \rho(v)=\sup\{\rho(w)+1:w\text{ is an immediate child of }v\}, \qquad \sup\varnothing=0. \] Each rank is a countable ordinal, since each node has at most countably many children and a countable supremum of countable ordinals is countable. The tree has countably many nodes, so all its ranks are bounded by a single countable ordinal. The ranks strictly decrease along extensions. Conversely an infinite branch would give an infinite strictly decreasing sequence of ordinals, which is impossible. This proves assertions 2 and 3 equivalent and completes Theorem Theorem (Full payoff characterization).

Scope

The original regularizers and every original step are retained. No entropy, summability, small-step, strong-convexity modulus, potential structure, gradient Lipschitz bound, or boundary-gradient continuity is added. The interior initial set is covered by all compact cores, rather than replaced by one selected core. The update is unique by hypothesis, so there is no additional tie-breaking convention. All players use the same old profile in the simultaneous payoff vectors of (eq:f4). The target is distance to the Nash set, not action convergence, time-averaged convergence, or convergence to one equilibrium.

The condition is a payoff-structure criterion in a closed-certificate sense: it consists of explicitly specified finite constraints with payoff-polynomial coefficients, followed by well-foundedness or an ordinal ranking. Real trajectory coordinates appear only as finite feasibility variables and are eliminated from the countable tree itself. Neither exact gradient evaluation nor infinite orbit quantification defines node validity. The supporting regularizer probes and ray-specific secant certificates are needed because ordinary compactness applied to unclosed update graphs would be insufficient.

This is an infinitary representation. An arbitrary fixed regularizer or step sequence need not have an effective finite encoding. Even decidability of each finite node test would not decide well-foundedness of the entire tree. Accordingly no recognition algorithm or running-time bound is claimed. For general regularizers these finite tests need not be polynomial or semialgebraic: fixed epigraph membership is part of the rule's data.

The tree has countably many possible waiting times and secant-denominator labels. In general, countable well-founded trees need not have finite height; the criterion itself imposes no uniform finite horizon. No uniform bound on the number of bad dates or natural-number ranking is inferred. Countable ordinals retain the full pointwise-in-initialization convergence property.

A boundary test for pointwise ray certificates

On the three-action simplex write the first two probabilities as $x,y$, so $x,y\ge0$ and $x+y\le1$. Consider \begin{equation} h(x,y)=x^2+y^2+\frac{y^2}{\sqrt x}\quad(x>0),\qquad h(0,0)=0,\qquad h(0,y)=+\infty\quad(y>0). \label{wsref-0-65-71-3a-62} \end{equation} It is proper and lower semicontinuous. The Hessian of $y^2/\sqrt x$ for $x>0$ has nonnegative diagonal entries and determinant $y^2/(2x^3)\ge0$, so this term is convex there. Nonnegativity gives lower semicontinuity at the origin, and the term $y^2/\sqrt{x}$ tends to infinity when $x\downarrow0$ and $y$ approaches a positive boundary value. For a segment from the origin to a finite-value point with $x>0$, $h(tx,ty)=t^2(x^2+y^2)+t^{3/2}y^2/\sqrt{x}\le t h(x,y)$ for $0\le t\le1$; the interior Hessian handles all other finite-value segments, so the stated extension is convex. Adding $x^2+y^2$ makes $h$ strictly convex, and it is smooth on the relative interior.

At the vertex $(0,0)$, every finite-domain ray has linear directional gradient zero: for a fixed interior probe $q=(a,b,1-a-b)$, put $d=q-(0,0,1)=(a,b,-a-b)$, using the ambient Euclidean norm. Then \[ \frac{h(\theta a,\theta b)}{\theta} =\theta(a^2+b^2)+\sqrt\theta\,\frac{b^2}{\sqrt a} \longrightarrow0. \] Yet $h(r^4,r)=r^8+r^2+1$ does not even tend to $h(0,0)$. A uniform Fréchet certificate would exclude this declared weak boundary gradient. The ray certificate includes it: take $c=0$, $g=0$. The supporting probes are nonnegative, and, for each fixed $q$ and $k$, choose a sufficiently large integer $N$ so that \[ N h(a/N,b/N)=\frac{a^2+b^2}{N}+\frac{b^2}{\sqrt{aN}} \le\frac{\|d\|}{k}. \] This is exactly (eq:g2), with no uniformity over probes required.

For one player, $\eta_1=1$, payoff vector $(7/8,-7/2,0)$, and the interior profile $(1/16,1/4,11/16)$, the regularizer gradient representative is $(-15/8,5/2,0)$. The next optimization score is $(-1,-1,0)$, so its unique optimizer is $(0,0,1)$: every other point has strictly negative score minus the nonnegative regularizer. If the declared boundary gradient is the finite-domain linear directional gradient zero, the following unit-step optimizer is $(7/16,0,9/16)$. The ray certificate permits this exact prefix. We do not use this test as a replacement for the full theorem or claim a separate all-initialization convergence result from this prefix.

Use of AI tools

References

• [potentialness] Martin Bichler, Davide Legacci, Panayotis Mertikopoulos, Matthias Oberlechner, and Bary Pradelski. Characterizing the Convergence of Game Dynamics via Potentialness, arXiv:2503.16285v1, submitted 20 March 2025. https://arxiv.org/html/2503.16285v1. Sections 3--4 provide game/potentialness context; Section 6 states the general classification agenda.
• [nash] J. F. Nash, Jr., Equilibrium points in n-person games, Proceedings of the National Academy of Sciences USA 36$1$, 48--49 $1950$, DOI: 10.1073/pnas.36.1.48. https://pmc.ncbi.nlm.nih.gov/articles/PMC1063129/.