we-solve (beta)

Econ-11-A3 · revision r1 · on Econ-11

C73-11: An infinitary payoff-array characterization of universal convergence of fictitious play

Partial result · LLM-generated · Submitted by Ji Ho Bae · Ji Ho Bae · gpt-6 astra, claude opus 5.5, gpt-6 astra pro

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness.

Claim: partial result

An infinitary tree with finite polynomial payoff tests and ordinal ranks characterizes fictitious-play convergence for every initial profile and legal tie choice.

Limitations: The result encodes possible nonconvergent trajectories; substantive game-classification credit remains for editorial assessment.; No finite recognition algorithm, familiar-class classification, hardness, or undecidability theorem is claimed.; Unverified; no independent community acceptance or formal certification asserted.

Manuscript

Contents
  1. C73-11: An infinitary payoff-array characterization of universal convergence of fictitious play
  2. The problem and the claim
  3. Explicit finite polynomial tests
  4. The payoff-generated tree and the main theorem
  5. Exact interpretation and the Nash residual
  6. Branches recover one common initial profile
  7. Ordinal rankings and a root rank of $\omega$
  8. A coanalytic payoff-space consequence
  9. Scope and boundary cases
  10. Use of AI tools
  11. References

C73-11: An infinitary payoff-array characterization
of universal convergence of fictitious play

Ji Ho Bae
LawAll AI

10 October 2026

\begin{abstract} For every finite normal-form game we construct a countable tree from finite polynomial-sign tests on its payoff entries. Simultaneous fictitious play approaches the Nash set from every initial profile and under every legal tie choice if and only if this tree admits a strictly decreasing countable-ordinal labeling. The proof retains a common initial profile through nested compact feasible sets. The criterion is infinitary. It also yields a coanalytic upper bound for the convergence class and an elementary example whose tree has root rank $\omega$. \end{abstract}

The problem and the claim

Let $G=(N,(S_i),(u_i))$ be a finite normal-form game, where $N=\{1,\ldots,n\}$, $n\ge1$, and every $S_i$ is nonempty. Put $A=\prod_iS_i$ and $X=\prod_i\Delta(S_i)$. Payoff entries are arbitrary real numbers; payoffs on $X$ are their multilinear extensions. Starting from any $x^1\in X$, the simultaneous fictitious-play rule is \begin{equation}\label{wsref-0-65-71-3a-66-70} \begin{aligned} a_i^{t+1}&\in\operatorname*{arg\,max}_{b\in S_i}u_i(b,x_{-i}^t),\\ x_i^{t+1}&=\frac{t x_i^t+e_{a_i^{t+1}}}{t+1}\quad(t\ge1). \end{aligned} \end{equation} Every legal, time-dependent selection among ties is permitted. The catalogue problem C73-11 asks for necessary and sufficient conditions on the finite payoff arrays for membership in \begin{equation}\label{wsref-0-65-71-3a-63-6c-61-73-73} \mathcal C_{\mathrm{FP}}=\left\{G: \begin{array}{l} \text{for every $x^1\in X$ and every legal sequence in \eqref{wsref-0-65-71-3a-66-70},}\\[-2pt] \displaystyle\operatorname{dist}(x^t,\operatorname{NE}(G))\longrightarrow0 \end{array}\right\}, \qquad \operatorname{dist}(x,K)=\inf_{z\in K}\|x-z\|_2. \end{equation}

The condition below is a necessary and sufficient condition for this class. It consists of a countable tree determined by finite quantifier-free payoff tests, together with an ordinal-ranking condition. It is not a finite membership algorithm or a classification by familiar game classes. The learning-dynamics discussion and theoretical open item 5 of Li et al. [li] motivate this problem. No broader classification is claimed.

Explicit finite polynomial tests

Introduce the finite real vector $\zeta=(\zeta_{i,b})$ and the simplex constraints \begin{equation}\tag{S}\label{wsref-0-65-71-3a-53} \zeta_{i,b}\ge0,\qquad \sum_{b\in S_i}\zeta_{i,b}=1 \quad(i\in N,\ b\in S_i). \end{equation} Fix an integer $T\ge1$ and a finite joint-action word $v=(a^2,\ldots,a^T)$, with $a^q\in A$. The word is empty when $T=1$. For $1\le t\le T$, define \begin{align} c_{i,b}^t(v)&=\#\{q\in\{2,\ldots,t\}:a_i^q=b\}, &Z_{i,b}^t(\zeta)&=\zeta_{i,b}+c_{i,b}^t(v),\label{wsref-0-65-71-3a-63-6f-75-6e-74-73}\\ P_{i,b}^t(\zeta;u)&= \sum_{s_{-i}\in\prod_{j\ne i}S_j} u_i(b,s_{-i})\prod_{j\ne i}Z_{j,s_j}^t(\zeta),\label{wsref-0-65-71-3a-50}\\ H_{i,b}^t(\zeta;u)&= tP_{i,b}^t(\zeta;u) -\sum_{d\in S_i}Z_{i,d}^t(\zeta)P_{i,d}^t(\zeta;u). \label{wsref-0-65-71-3a-48} \end{align} For $n=1$, the empty product in (eq:P) is one and the sum has one term. These are explicit polynomials in $\zeta$ and the payoff entries, with rational coefficients determined by the finite integer/action data. Impose the legality inequalities \begin{equation}\tag{L}\label{wsref-0-65-71-3a-4c} P_{i,a_i^{t+1}}^t-P_{i,b}^t\ge0 \quad(1\le t<T,\ i\in N,\ b\in S_i). \end{equation}

A record consists of this word, a positive integer $m$, marked times $1\le t_1<\cdots<t_r=T$, $r\ge1$, and witnesses $h_\ell=(i_\ell,b_\ell)$ with $b_\ell\in S_{i_\ell}$. Add \begin{equation}\tag{B}\label{wsref-0-65-71-3a-42} mH_{i_\ell,b_\ell}^{t_\ell}-t_\ell^n\ge0 \quad(1\le\ell\le r). \end{equation} Write $C_q(u)\subseteq X$ for the $\zeta$ satisfying (eq:S), (eq:L), and (eq:B) for record $q$. It is closed and compact, and it is semialgebraic. A record is admitted precisely when $C_q(u)\ne\varnothing$.

For a definition entirely in the payoff entries, apply real quantifier elimination [tarski] to the finite formula \begin{equation}\label{wsref-0-65-71-3a-51-45} \exists\zeta\;\left[\text{\eqref{wsref-0-65-71-3a-53}, \eqref{wsref-0-65-71-3a-4c}, and \eqref{wsref-0-65-71-3a-42}} \right], \end{equation} treating every $u_i(s)$ as a free variable. Denote a resulting quantifier-free finite Boolean combination of polynomial signs by $\Theta_q(u)$. Thus \begin{equation}\label{wsref-0-65-71-3a-61-64-6d-69-73-73-69-6f-6e} C_q(u)\ne\varnothing\quad\Longleftrightarrow\quad\Theta_q(u). \end{equation} The compilation depends only on $q$ and eliminates $\zeta$ entirely. It works for arbitrary real arrays. For rational arrays, each individual finite test is decidable. This does not decide the later well-foundedness condition on the countable tree.

The payoff-generated tree and the main theorem

Define $\mathcal T(u)$ to have a root $e$ and one nonroot vertex for each record satisfying $\Theta_q(u)$. A record with $r=1$ marks has parent $e$. For $r\ge2$, its parent deletes the last mark and witness and truncates the word after $t_{r-1}$. Extension always preserves $m$ and every earlier action, mark, and witness. Equivalently, an edge appends a nonempty finite action block ending at a new marked time; only the first block can be empty, when the first mark is at time one.

Each admitted record has an admitted parent, since its feasible set is contained in the parent's feasible set. The root is always present. There are countably many possible records. The tree may have infinitely many children at a vertex because the next marked time is unbounded. Its definition by (eq:admission) uses only payoff entries and finite integer/action labels.

Definition (Payoff-array condition (O)): There exist a countable ordinal $\alpha$ and a labeling $\rho:\mathcal T(u)\to\alpha$ such that \begin{equation}\tag{O}\label{wsref-0-65-71-3a-4f} \rho(w)<\rho(q)\qquad\text{whenever $w$ is a child of $q$}. \end{equation} The labeling includes the root. Neither a finite encoding of $\alpha$ nor computability of $\rho$ is required.
Theorem: For every finite normal-form game as above, the following are equivalent:
  1. $G\in\mathcal C_{\mathrm{FP}}$.
  2. Its payoff array satisfies condition (O).
  3. $\mathcal T(u)$ is well founded, meaning that it has no infinite branch.

Exact interpretation and the Nash residual

Lemma: For an initial profile $\zeta\in X$ and a finite word $v$, the update (eq:fp) has the identities \begin{equation}\label{wsref-0-65-71-3a-69-64-65-6e-74-69-74-79} \begin{aligned} x_{i,b}^t&=\frac{Z_{i,b}^t}{t},\qquad u_i(b,x_{-i}^t)=\frac{P_{i,b}^t}{t^{n-1}},\\ u_i(b,x_{-i}^t)-u_i(x^t)&=\frac{H_{i,b}^t}{t^n}. \end{aligned} \end{equation} Consequently (L) is exactly legality of the finite word, and (B) is exactly the specified gain of at least $1/m$ at each mark.
Proof: The first identity holds at $t=1$. Multiplying the update by $t+1$ adds one to exactly the next chosen action's count, proving it by induction. Substituting it in the multilinear payoff gives the second identity. Since $u_i(x^t)=\sum_d(Z_{i,d}^t/t)(P_{i,d}^t/t^{n-1})$, the third follows from (eq:H). All denominators are positive, so clearing them gives precisely (eq:L) and (eq:B), including weak ties. ∎

Define \begin{equation}\label{wsref-0-65-71-3a-72-65-73-69-64-75-61-6c} R(x)=\max_{i\in N,\,b\in S_i} \left[u_i(b,x_{-i})-u_i(x)\right]. \end{equation} For each player the $x_i$-weighted mean of the bracketed gains is zero, so $R\ge0$. It is continuous, and $R(x)=0$ exactly when no pure deviation improves payoff. A mixed deviation is a convex combination of pure ones; thus the zero set is exactly $\operatorname{NE}(G)$.

The zero set is nonempty by Nash's finite-game existence theorem [nash]. For completeness, the following continuous-map argument proves existence using Brouwer's fixed-point theorem. Set $g_{i,b}(x)=[u_i(b,x_{-i})-u_i(x)]_+$, $G_i(x)=\sum_b g_{i,b}(x)$, and consider the continuous map \[ F_{i,b}(x)=\frac{x_{i,b}+g_{i,b}(x)}{1+G_i(x)} \quad\text{from }X\text{ to }X. \] Brouwer's fixed-point theorem supplies a fixed point. There, $g_{i,b}=x_{i,b}G_i$. If $G_i>0$, every action with positive $x_i$-mass has strictly positive gain, contradicting the zero weighted mean of gains. Hence all $G_i=0$, giving a Nash equilibrium. Continuity also shows that the Nash set is compact.

Lemma: For every sequence $x^t\in X$, \begin{equation}\label{wsref-0-65-71-3a-64-69-73-74-61-6e-63-65} R(x^t)\longrightarrow0 \quad\Longleftrightarrow\quad \operatorname{dist}(x^t,\operatorname{NE}(G))\longrightarrow0. \end{equation} Failure is equivalent to the existence of one integer $m\ge1$ and infinitely many times at which a witnessed pure-deviation gain is at least $1/m$.
Proof: Uniform continuity of $R$ on compact $X$, its vanishing on the Nash set, and attainment of distance to that compact set prove the implication from distance convergence. Conversely, suppose $R(x^t)\to0$ but distance stays at least some $\varepsilon>0$ along a subsequence. A further subsequence converges to $x^*\in X$. Then $R(x^*)=0$, so $x^*$ is Nash, contradicting the positive distance bound.

Since $R\ge0$, failure of its convergence to zero means that $R(x^t)\ge\varepsilon$ infinitely often for some $\varepsilon>0$. Choose $m$ with $1/m\le\varepsilon$. The finite maximum in (eq:residual) has a witness at every such time. Conversely, infinitely many gains at least one fixed $1/m$ prevent residual convergence. ∎

Branches recover one common initial profile

Proof[Proof of Theorem Theorem, (i)$\Leftrightarrow$(iii)]: If a legal fictitious-play orbit fails convergence, Lemma Lemma gives one $m$, increasing times $t_1,t_2,\ldots$, and witnesses $(i_\ell,b_\ell)$. At stage $r$, take the orbit's word through $t_r$ and its first $r$ marks. Its actual initial profile satisfies all the finite constraints by Lemma Lemma. These admitted records are successive vertices of an infinite branch.

Conversely, let $q_1,q_2,\ldots$ be an infinite branch after the root. The first vertex fixes $m$ forever. Successive marked times strictly increase and hence tend to infinity. Consistent word extensions specify an action at every update date. The sets $C_{q_r}(u)$ are nonempty closed subsets of the same compact $X$, and \begin{equation}\label{wsref-0-65-71-3a-69-6e-74-65-72-73-65-63-74-69-6f-6e} C_{q_{r+1}}(u)\subseteq C_{q_r}(u),\qquad \bigcap_{r\ge1}C_{q_r}(u)\ne\varnothing. \end{equation} The last assertion is the nested compact-set property. Choose one $\zeta$ in this intersection. Every legality inequality at any finite update date occurs in all sufficiently long records, so the union word is a legal simultaneous orbit from this same $\zeta$. Every marked gain is at least $1/m$. Its residual therefore fails to converge to zero; Lemma Lemma gives failure of Nash-set convergence. ∎

Retaining all earlier constraints is crucial: separate feasibility of unrelated records would not recover a common initial profile. Weak inequalities retain every tie and make (eq:intersection) applicable. The fixed threshold is also crucial; a branch cannot increase $m$ to turn shrinking residuals into an obstruction.

Ordinal rankings and a root rank of $\omega$

Proof[Proof of Theorem Theorem, (ii)$\Leftrightarrow$(iii)]: Condition (O) forbids an infinite branch, since ordinals have no infinite strictly descending sequence. For the converse, let the countable tree be well founded. Its child relation supports well-founded recursion: \begin{equation}\label{wsref-0-65-71-3a-72-61-6e-6b} \operatorname{rank}(q)=\sup\{\operatorname{rank}(w)+1:w\text{ is a child of }q\}, \qquad\sup\varnothing=0. \end{equation} By well-founded induction, every rank is countable: assuming this for all children of a vertex, their ranks have countable supremum because there are only countably many children. Since there are countably many vertices, \[ \alpha=\sup_{q\in\mathcal T(u)}(\operatorname{rank}(q)+1) \] is countable. Every rank is less than $\alpha$, and the ranks strictly decrease along edges, proving (O).

∎

Example (A fictitious-play tree of root rank $\omega$): One player has actions $0,1$ with payoffs $0,1$. Action $1$ is the unique legal update. If the initial mass on action $0$ is $c\in[0,1]$, its mass at time $t$ is $c/t$, and the Nash residual is $c/t$. Only deviation to action $1$ can witness a positive gain.

For a record at threshold $1/m$ ending at time $T$, admission requires $c/T\ge1/m$, hence $T\le m$. Conversely, every increasing list of marked times ending at $T\le m$ is admitted by $c=1$ and the unique legal word. An admitted vertex with last time $T$ has at most $m-T$ further marks, and can realize all times $T+1,\ldots,m$. Its rank is therefore exactly $m-T$. In particular, the vertex first marked at time one has rank $m-1$. The combined tree's root has \[ \operatorname{rank}(e)=\sup_{m\ge1}\ \sup_{1\le T\le m}(m-T+1) =\sup_{m\ge1}m=\omega. \] The game converges from every initialization, but its root has no finite ordinal rank. This makes no claim that higher ranks are realized by this particular family of dynamics.

A coanalytic payoff-space consequence

Fix the action sets and identify payoff arrays with $U=\mathbb R^D$, where $D=n|A|$. For each possible record $q$, let $Q_q=\{u:C_q(u)\ne\varnothing\}$.

Proposition: Every $Q_q$ is closed and semialgebraic in $U$. The subset $\mathcal C_{\mathrm{FP}}\subseteq U$ is coanalytic, equivalently a $\Pi^1_1$ set.
Proof: Semialgebraicity follows from (eq:QE). To prove closedness, let $u_k\in Q_q$ converge to $u$ and choose $\zeta_k\in C_q(u_k)$. Compactness of $X$ supplies a convergent subsequence. All finitely many polynomial constraints pass to its limit, proving $u\in Q_q$.

Enumerate all syntactically valid complete records by $\mathbb N$. An element $p\in\mathbb N^{\mathbb N}$ names successive potential vertices $q(p_0),q(p_1),\ldots$. Define $B\subseteq U\times\mathbb N^{\mathbb N}$ by requiring:

  1. $q(p_0)$ has one mark;
  2. $q(p_{k+1})$ is a child of $q(p_k)$ for every $k$;
  3. $u\in Q_{q(p_k)}$ for every $k$.
The first record includes $m$, and the child relation preserves it. These requirements define a closed set. Explicitly, if $(u_j,p_j)\to(u,p)$, convergence in Baire space, with its discrete coordinate topology, makes each fixed finite list of coordinates eventually constant and equal to the corresponding list of $p$. Requirements (a) and (b) pass to the limit. For each fixed $k$, the record named by $(p_j)_k$ is eventually exactly $q(p_k)$, so closedness of $Q_{q(p_k)}$ passes (c) to the limit as well.

Theorem Theorem says that the projection of $B$ onto $U$ is exactly $U\setminus\mathcal C_{\mathrm{FP}}$. A projection of a closed subset of $U\times\mathbb N^{\mathbb N}$ is analytic; its complement is coanalytic. This proves the asserted upper bound. ∎

This argument establishes no $\Pi^1_1$ hardness or completeness, non-Borelness, undecidability, or necessity of high ordinal ranks for fictitious-play games.

Scope and boundary cases

The initial domain is the entire product of closed simplexes, including boundary faces and irrational coordinates. Weak best-response inequalities include all payoff ties. Every player updates simultaneously, and the target is distance to the exact Nash set, not point convergence, action convergence, or convergence of joint empirical play to a correlated-equilibrium concept.

Singleton action sets cause no change in the formulas. The empty products for a one-player game have already been specified. If all payoffs are constant, then $H=0$, no marked inequality is feasible, and the tree has only its root, of rank zero; every profile is Nash. If a convention admits an empty-player game, that trivial case may separately be assigned the root-only tree and is convergent. Positive playerwise payoff rescaling and adding a function of opponents' actions preserve legal choices and the Nash set. They may alter a numerical threshold, but not the existence of some fixed integer obstruction threshold.

Use of AI tools

The author used research AI agents that the author built and configured (GPT-6 Astra max, Claude Opus 5.5 max and GPT-6 Astra Pro) during the proof work, for proof search and construction, proof checking, translation, Python computation and similar tasks. The final manuscript was written, and the proofs were checked, by the human author. All responsibility for this work rests with the author personally.

References

  • [li] Hanyu Li, Wenhan Huang, Zhijian Duan, David Henry Mguni, Kun Shao, Jun Wang, and Xiaotie Deng. A survey on algorithms for Nash equilibria in finite normal-form games. arXiv:2312.11063v1, 18 December 2023. Learning-dynamics discussion and concluding "Open problems and future directions," theoretical item 5, printed page 30. Primary v1 PDF.
  • [nash] John F. Nash, Jr. Equilibrium points in $n$-person games. Proceedings of the National Academy of Sciences 36$1$, 48--49 $1950$. DOI: 10.1073/pnas.36.1.48. Finite-game existence theorem. Primary paper scan.
  • [tarski] Alfred Tarski. A Decision Method for Elementary Algebra and Geometry: Prepared for Publication with the Assistance of J. C. C. McKinsey. RAND Corporation, Report R-109, 1951 edition. Edition record; primary scan.