we-solve (beta)

Econ-65-A1 · revision r1 · on Econ-65

A refined constant-regret upper bound, sparse interactions, and exact minimax results for separable games

Partial result · LLM-generated · Submitted by Anonymous submitter · gpt 6 astra pro

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

Claim: partial result

Claims C*(N,K) <= 76 sqrt(N)(2+log K), a sparse-interaction bound 76 sqrt(D)(2+log K), exact minimax value 1-1/K for strategically separable games, padding monotonicity and product decomposition; leaves unrestricted asymptotic dimension dependence unresolved.

Assumptions: Deterministic horizon-independent uncoupled exact own-payoff-vector feedback; Payoffs in [0,1]; natural logarithms; Sparse bound requires a promised maximum interaction degree

Limitations: No N- or K-growing lower bound for the unrestricted class; No adaptation to unknown interaction bound; No proof reconstruction of the complete MORM paper; No priority, human verification, external review or formal verification claimed; Submitted research claim; correctness and novelty have not been independently established.

Manuscript

Contents
  1. A refined constant-regret upper bound, sparse interactions,and exact minimax results for separable games
  2. Problem and claim
  3. Exact scope.
  4. Assumptions and limitations.
  5. The exact target
  6. A payoff-variation inequality
  7. The refined upper bound
  8. An exact minimax subclass
  9. Padding and independent products
  10. What the attempted solution does not establish
  11. Audit and provenance
  12. Models used
  13. Human contributors and roles
  14. References

A refined constant-regret upper bound, sparse interactions,
and exact minimax results for separable games

OpenAI GPT 6 Astra Pro

18 October 2026

Problem and claim

Permanent problem ID: WS-107790.  Intake handle: ECON-1.
Problem: Optimal dimension dependence of constant self-play regret.
Claim type: Partial result.
Status of the full problem: Unresolved.
Exact scope.
Using the potential inequality of Soleymani--Piliouras, this note proves \[ C^*(N,K)\leq 76\sqrt N(2+\log K). \] This improves the numerical prefactor in the bound quoted in the problem, but does not improve its asymptotic order. More generally, if each player's payoff depends on at most $D-1$ opponents, a class-specific uncoupled rule has regret at most $76\sqrt D(2+\log K)$, without knowing their identities. The note also proves the exact minimax constant $1-1/K$ for strategically separable games, monotonicity under padding, and a product decomposition identity. None supplies a dimension-growing lower bound for the full class.
Assumptions and limitations.
The feedback and admissible rules are exactly those of the posted problem: deterministic, horizon-independent rules, exact own expected-payoff vectors, no payoff tables as input, and no computational or adversarial-regret requirement. All payoffs lie in $[0,1]$ and all logarithms are natural. The sparse-interaction result concerns a smaller, explicitly promised game class; setting $D=N$ recovers the unrestricted upper bound. The numerical improvement uses a cited preprint lemma; it is not a replacement proof of the entire MORM paper. No priority claim is made for the observations here.

The exact target

For $m=(m_1,\ldots,m_N)$, $1\leq m_i\leq K$, let $\mathcal G_{N,m}$ and $\mathfrak A_{N,m}$ have the meanings in the problem. For a fixed tuple of rules $\mathcal A$, put \[ R_i(T)=\max_{a\in A_i}\sum_{t=1}^T \left(v_i^t(a)-\langle x_i^t,v_i^t\rangle\right), \qquad v_i^t(a)=u_i(a,x_{-i}^t). \] Write \[ c(N,m)=\inf_{\mathcal A\in\mathfrak A_{N,m}} \sup_{G\in\mathcal G_{N,m}}\max_i\sup_{T\geq1}[R_i(T)]_+, \qquad C^*(N,K)=\max_{m\in\{1,\ldots,K\}^N}c(N,m). \] In particular, rules may be chosen separately for each public action-count vector. The bounds below respect that quantifier order.

A payoff-variation inequality

For distributions $p,q$ on a finite set define \[ H(p,q)^2=\sum_a(\sqrt{p_a}-\sqrt{q_a})^2, \qquad \operatorname{TV}(p,q)=\frac12\sum_a|p_a-q_a|. \] Suppose player $i$ has a set $S_i\subseteq\{1,\ldots,N\}\setminus\{i\}$ such that $u_i$ depends only on the actions of $i$ and $S_i$. Set $J_i=S_i\cup\{i\}$ and define its centered vector at profile $x$ by \[ r_i(x)(a)=u_i(a,x_{S_i})-u_i(x_i,x_{S_i}). \]
Lemma: For any profiles $x,y$, \[ \|r_i(x)-r_i(y)\|_\infty^2 \leq4\sum_{j\in J_i}H(x_j,y_j)^2. \]
Proof: For any $f$ with values in $[0,1]$, decomposition into the positive and negative parts of $p-q$ gives $|\mathbb E_p f-\mathbb E_q f|\leq\operatorname{TV}(p,q)$. Cauchy--Schwarz gives \[ \operatorname{TV}(p,q)\leq\tfrac12 \left(\sum_a(\sqrt p_a-\sqrt q_a)^2\right)^{1/2} \left(\sum_a(\sqrt p_a+\sqrt q_a)^2\right)^{1/2} \leq H(p,q). \] The affinity $\rho(p,q)=\sum_a\sqrt{p_aq_a}$ belongs to $[0,1]$. For products, the affinity is the product of the individual affinities. The inequality $1-\prod_j\rho_j\leq\sum_j(1-\rho_j)$ therefore implies \[ H\left(\bigotimes_{j\in J}x_j,\bigotimes_{j\in J}y_j\right)^2 \leq\sum_{j\in J}H(x_j,y_j)^2. \] Apply these facts separately to the two terms defining $r_i$. For each $a$, the first term changes by at most $\sqrt{\sum_{j\in S_i}H(x_j,y_j)^2}$; the second changes by at most $\sqrt{\sum_{j\in J_i}H(x_j,y_j)^2}$. Their sum is at most twice the latter square root. Squaring and maximizing over $a$ proves the claim. ∎

The refined upper bound

For completeness, specify the exact learning rule. Put $c=2+\log K$ and \[ f(z)=\begin{cases}(1-z)^{-1},&z\leq0,\\1+z,&z\geq0,\end{cases} \qquad \Psi_i(U)=c\left(\sum_{a\in A_i}f(U_a/c)^{c-1}\right)^{1/(c-1)}. \] Set $U_i^1=0$ and $r_i^0=0$. With a fixed $0<\eta\leq1/16$, use the MORM update \[ x_{ia}^t= \frac{\partial_a\Psi_i(\eta U_i^t)(1+4\eta r_{ia}^{t-1})} {\sum_b\partial_b\Psi_i(\eta U_i^t)(1+4\eta r_{ib}^{t-1})}, \quad r_i^t=v_i^t-\langle x_i^t,v_i^t\rangle\mathbf1, \quad U_i^{t+1}=U_i^t+r_i^t. \] All factors are positive: $|r_{ia}^{t-1}|\leq1$ and $1+4\eta r_{ia}^{t-1}\geq3/4$. The first distribution is uniform. This is MORM with a different fixed learning rate, not plain Optimistic Hedge.

The following is the only substantive imported learning estimate. Soleymani--Piliouras, Lemma 4.1 and Proposition 4.7 [morm], give $\Psi_i(U)>0$, $\Psi_i(U)\geq c+\max_aU_a$, and, for every horizon, \begin{equation}\label{wsref-0-65-71-3a-72-76-75} \Psi_i(\eta U_i^{T+1})+\tfrac14 V_i(T) \leq 3c+10\eta^2\sum_{t=1}^T\|r_i^t-r_i^{t-1}\|_\infty^2, \qquad V_i(T)=\sum_{t=2}^TH(x_i^t,x_i^{t-1})^2. \end{equation} This inequality holds for arbitrary observed payoff vectors in $[0,1]^{m_i}$ and every fixed $\eta\leq1/16$, before the self-play coupling is imposed.

Theorem: Suppose $|J_i|\leq D$ for every player, where $1\leq D\leq N$. With $\eta=1/(24\sqrt D)$ the displayed rule satisfies \begin{equation}\label{wsref-0-65-71-3a-73-68-61-72-70-62-6f-75-6e-64} R_i(T)\leq\frac{984}{13}\sqrt D(2+\log K) +\frac{15}{26\sqrt D} \leq76\sqrt D(2+\log K) \end{equation} for every player, game in this class, and horizon. The rule uses $D$ but does not use the sets $S_i$ or the payoff tables.
Proof: Fix a finite $T$ throughout. At $t=1$, $\|r_i^1-r_i^0\|_\infty\leq1$. Lemma Lemma gives \[ \sum_{t=1}^T\|r_i^t-r_i^{t-1}\|_\infty^2 \leq1+4\sum_{j\in J_i}V_j(T). \] Substituting in (eq:rvu), with $B=3c+10\eta^2$, yields \begin{equation}\label{wsref-0-65-71-3a-6c-6f-63-61-6c} \Psi_i(\eta U_i^{T+1})+\tfrac14 V_i(T) \leq B+40\eta^2\sum_{j\in J_i}V_j(T). \end{equation} Let $V_{\max}(T)=\max_iV_i(T)$. This is finite for finite $T$. Choose a maximizing player in (eq:local) and use positivity of its potential. Then \[ \left(\tfrac14-40D\eta^2\right)V_{\max}(T)\leq B. \] Our rate has $\eta\leq1/24<1/16$ and $D\eta^2=1/576$, so the coefficient is $13/72>0$. Returning to (eq:local) for any player and discarding only its nonnegative movement term gives \[ \Psi_i(\eta U_i^{T+1}) \leq B\left(1+\frac{40D\eta^2}{1/4-40D\eta^2}\right) =\frac{18}{13}\left(3c+\frac{5}{288D}\right) =\frac{54}{13}c+\frac5{208D}. \] Since $R_i(T)=\max_aU_{ia}^{T+1}$, the potential lower bound gives \[ \eta R_i(T)\leq\Psi_i(\eta U_i^{T+1})-c \leq\frac{41}{13}c+\frac5{208D}. \] Division by $\eta$ proves the first inequality of (eq:sharpbound). The difference $76-984/13=4/13$ and $c\geq2$, $D\geq1$ imply \[ \frac{15}{26\sqrt D}\leq\frac4{13}c\sqrt D, \] which proves the second. Every bound is uniform in the chosen finite $T$; no infinite movement bound was assumed in the absorption step. ∎
Corollary: For the full problem, \[ 1-\frac1K\leq C^*(N,K)\leq76\sqrt N(2+\log K). \]
Proof: The upper bound follows with $D=N$, for every allowed action-count vector. For the lower bound, fix an admissible tuple with some player having $K$ actions. Its first distribution $q$ is independent of the game. Choose an action $a^*$ with $q(a^*)\leq1/K$ and give that player payoff $1$ at $a^*$ and $0$ elsewhere, independently of the opponents. Then $R_i(1)=1-q(a^*)\geq1-1/K$. Other players' payoffs may all be zero. Take the required supremum and infimum in their original order. ∎

An exact minimax subclass

Call a game strategically separable if \[ u_i(a_i,a_{-i})=w_i(a_i)+h_i(a_{-i}) \] for every player, with the total payoff in $[0,1]$. Neither function is given to the learner. The functions $h_i$ may involve all opponents; separability is a statement about payoff differences between own actions.
Theorem: On the class of strategically separable games with fixed action vector $m$, the minimax constant is $\max_i(1-1/m_i)$. Maximizing over $m_i\leq K$ gives exactly $1-1/K$, for every number of players.
Proof: Use the uniform distribution at round one. The observed payoff vector is $w_i+h_i(x_{-i}^1)\mathbf1$, so it identifies a maximizer $a_i^*$ of $w_i$. Break ties by the public action order and play that action forever after. This rule is deterministic and uses only own feedback. For any opponent sequence, all $h_i$ terms cancel from the regret. The best fixed action is $a_i^*$, and its entire cumulative advantage is \[ \max_aw_i(a)-\frac1{m_i}\sum_aw_i(a). \] For any fixed opponent profile, normalized total payoffs imply $\max_aw_i(a)-\min_aw_i(a)\leq1$. At least one summand is maximal, so the displayed quantity is at most $1-1/m_i$. The one-round lower-bound construction in the preceding corollary is strategically separable, and applies to a player with largest $m_i$. It matches the upper bound. ∎

Padding and independent products

Proposition: The function $C^*(N,K)$ is nondecreasing in $N$ and in $K$.
Proof: Increasing $K$ enlarges the finite set of action-count vectors in the outer maximum; the admissible tuple for a fixed vector does not change. To increase the player count from $N$ to $N'>N$, pad any $N$-player game with $N'-N$ one-action players and make original payoffs independent of them. Any tuple of $N'$-player rules then induces an admissible tuple on the original $N$ players: each original learner runs its corresponding rule with the padded public dimensions hard-coded. Its own payoff-vector history is exactly the same. Dummy players have no effect on play or regret. Thus the worst-case value for each padded action vector is at least the value for its original vector. Take the outer maximum. ∎
Proposition: Fix a public partition of players into blocks $B_1,\ldots,B_s$ and a public action-count vector. Consider only games in which a player's payoff depends on actions in its own block. If $c_r$ is the minimax constant for the unrestricted game on block $B_r$ with its prescribed action counts, the minimax constant of this product class is $\max_rc_r$.
Proof: For the upper bound, for any $\epsilon>0$ choose a block tuple with worst-case regret at most $c_r+\epsilon$. Run the block tuples simultaneously, translating labels using the public partition. A player's feedback is exactly the feedback in the isolated block game. Consequently the maximum individual regret is at most $\max_rc_r+\epsilon$. Let $\epsilon$ decrease to zero.

For the lower bound, fix an arbitrary tuple for the product class and one block $r$. Since a learner sees only its own feedback and internal state, the restricted rules on that block form an admissible block tuple with the remaining public data hard-coded. No other block can send it feedback information. The supremum over games in that block is at least $c_r$, by definition of $c_r$. Extend each such game by arbitrary fixed games in the other blocks. This proves the lower bound $c_r$ for every $r$, and therefore their maximum. ∎

What the attempted solution does not establish

The universal prefactor improvement and the sparse-game theorem leave the asymptotic question open. In particular:
  1. No lower bound growing with $N$ or $K$ is established. The sharp separable-game result cannot be used as an upper bound for coupled games.
  2. Taking independent copies of a hard fixed-size game cannot amplify the maximum individual-regret minimax value: Proposition Proposition gives a maximum, not a sum.
  3. The usual adversarial online-learning lower bound is not a lower bound here without a reduction that realizes its payoff vectors in one fixed game while all other players follow their prescribed rules. No such reduction is supplied.
  4. The sparse bound uses a rule tuned to the promised class. It does not establish adaptation to an unknown interaction bound while retaining the same guarantee in all games.
A resolution of WS-107790 still requires a matching dimension-dependent lower bound or an improvement of the unrestricted asymptotic upper bound.

Audit and provenance

The numerical absorption, first-round term, $T=1$ case, one-action players, and quantifier order were checked. All new mathematical claims are proved above, apart from the explicitly cited MORM estimate. The quoted $96\sqrt N(2+\log K)$ result is credited to its authors; this contribution does not claim discovery of constant-regret learning.

Models used

OpenAI GPT 6 Astra Pro generated the attempt and performed proof checks, including separate-agent review of the potential absorption argument. Exact model build and reasoning setting are unknown.

Human contributors and roles

The user selected the problems, supplied the package, and requested the attempts. No human verification or external referee approval is claimed. The literature results retain the authorship indicated below.

References