Answer: Polynomial-time solvable exactly; hence the additive guarantee \(2m(2S_R+S_C)\) is achievable.
Theorem 8 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateDenote OPT the cost of the optimal transfor- mation path from (r(1), C(1)) to (r∗, C∗).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational payoff matrices \(R\) and \(C\), row strategies \(r_0\) and \(r^*\), and rational population distributions \(\mu_0\) and \(\mu^*\) over column strategies, with both endpoints population Nash equilibria, compute the minimum total normalized reward over finite transition sequences \((r_0,\mu_0),\ldots,(r^*,\mu^*)\) where each step costs \(A(\mu^t,r^{t+1})+B(r^t,\mu^{t+1})\), \(A(\mu,b)=\max_a \sum_q \mu_q R(a,c_q)-\sum_q \mu_q R(b,c_q)\), and \(B(a,\nu)=\max_q C(a,c_q)-\sum_q \nu_q C(a,c_q)\).
Let \(R,C\in\mathbb{Q}_{\geq0}^{m\times n}\), with \(m,n\geq1\), describe one pure-strategy row player and a unit-mass column population whose available strategies are \(c_1,\ldots,c_n\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here types are occupied column strategies; for the two input societies use \(\tau=\max\{|\operatorname{supp}(\mu_0)|,|\operatorname{supp}(\mu_*)|\}\).
A state is \((a,\mu)\), where \(a\in\{1,\ldots,m\}\) and \(\mu\in\Delta_n\); masses are nonnegative and sum to one. Intermediate populations may use any available column strategy and real masses.
Define \(A(\mu,b)=\max_{a\in\{1,\ldots,m\}}\sum_{q=1}^{n}\mu_qR(a,c_q)-\sum_{q=1}^{n}\mu_qR(b,c_q)\) and \(B(a,\nu)=\max_{q\in\{1,\ldots,n\}}C(a,c_q)-\sum_{q=1}^{n}\nu_qC(a,c_q)\).
The input endpoints \((r_0,\mu_0)\) and \((r_*,\mu_*)\) are population Nash equilibria: \(A(\mu,a)=B(a,\mu)=0\). Ties permit any maximizing strategy.
A finite transition sequence may change both components simultaneously, including leaving either unchanged; its cost is \(\sum_{t=0}^{T-1}[A(\mu^t,r^{t+1})+B(r^t,\mu^{t+1})]\). Intermediate states need not be equilibria. Let \(\mathrm{OPT}\) be the infimum of these costs between the endpoints.
Write \(S_R=\sum_{a=1}^{m}\sum_{q=1}^{n}R(a,c_q)\), \(S_C=\sum_{a=1}^{m}\sum_{q=1}^{n}C(a,c_q)\), and let \(L\) be the total binary input length.
Can a transition sequence of cost at most \(\mathrm{OPT}+2m(2S_R+S_C)\) be computed in time polynomial in \(m,n,\tau,L\), or is achieving this additive guarantee NP-hard?
For finite populations, a polynomial-time algorithm achieves additive error \(2m(2S_R+S_C)\) in total, unnormalized reward, independently of population size. [Source](https://arxiv.org/pdf/2312.07603)
The search located no result establishing this guarantee for the exact continuous model stated above.
The stated continuous model is polynomial-time solvable exactly. Consequently, the requested additive guarantee can be achieved.
The additive guarantee alone is immediate: the direct transition has cost at most \(S_R+S_C\), which is at most \(2m(2S_R+S_C)\), and \(\mathrm{OPT}\geq 0\). We therefore address the stronger, nontrivial question of computing an optimal sequence.
For row strategies \(i,j\), define
\(w(i,j)=\min_{\nu\in\Delta_n}\bigl[B(i,\nu)+A(\nu,j)\bigr].\)
This minimum exists because the objective is continuous and \(\Delta_n\) is compact. Moreover, it can be computed by one linear program.
Let \(\beta_i=\max_q C(i,c_q)\) and \(M_R=\max_{a,q}R(a,c_q)\). Use variables \(x_1,\ldots,x_n,z\), with objective
\(\displaystyle \min\ \beta_i-\sum_{q=1}^{n}x_qC(i,c_q)+z,\)
subject to
For each fixed \(x\in\Delta_n\), the smallest feasible \(z\) is exactly \(A(x,j)\). Indeed, the second family of constraints gives its defining maximum. The constraint indexed by \(a=j\) gives \(z\geq 0\), and nonnegativity of \(R\) implies \(A(x,j)\leq M_R\). Thus the last constraint does not exclude any minimizing population.
The LP consequently has optimum \(w(i,j)\). Its feasible region is nonempty and compact: any \(x\in\Delta_n\), together with \(z=M_R\), is feasible. Store an optimal rational population \(\nu^{ij}\) for each ordered pair.
Construct a directed graph \(G\) on the \(m\) row strategies, giving edge \(i\to j\) weight \(w(i,j)\). All weights are nonnegative. Let \(D\) be its shortest-path distance from \(r_0\) to \(r_*\), allowing the empty path when these strategies coincide.
We will prove
\(\mathrm{OPT}=2D.\)
Consider a conceptual directed bipartite graph \(H\). Its two vertex classes are the row strategies and the populations in \(\Delta_n\), treated as disjoint classes. Its edge weights are
\(\operatorname{wt}(i\to\nu)=B(i,\nu),\qquad \operatorname{wt}(\nu\to j)=A(\nu,j).\)
Every finite walk in \(H\) alternates between row strategies and populations.
First consider any such walk from \(r_0\) to \(r_*\). Group its edges into consecutive pairs \(i\to\nu\to j\). Each pair costs at least \(w(i,j)\), by the definition of that minimum. The corresponding row walk in \(G\) therefore costs no more than the original walk, and its cost is at least \(D\). Hence every row-to-row walk in \(H\) from \(r_0\) to \(r_*\) costs at least \(D\).
The equilibrium hypotheses give four zero-cost edges:
\(r_0\to\mu_0,\quad \mu_0\to r_0,\quad r_*\to\mu_*,\quad \mu_*\to r_*.\)
Consequently, every finite walk in \(H\) starting in \(\{r_0,\mu_0\}\) and ending in \(\{r_*,\mu_*\}\) costs at least \(D\). To verify this, prepend \(r_0\to\mu_0\) if it starts at \(\mu_0\), and append \(\mu_*\to r_*\) if it ends at \(\mu_*\). These additions give a row-to-row walk without changing its cost.
Now take an arbitrary transition sequence \((r^t,\mu^t)\), indexed by \(t=0,\ldots,T\). Form two alternating walks:
At every time step, their two edge costs are exactly
\(A(\mu^t,r^{t+1})\quad\text{and}\quad B(r^t,\mu^{t+1}),\)
with their assignment to the two walks determined by parity. Thus their total cost equals the transition sequence’s cost.
Both walks start in \(\{r_0,\mu_0\}\) and end in \(\{r_*,\mu_*\}\). Each costs at least \(D\), so the sequence costs at least \(2D\). This applies to every finite sequence, including those with arbitrary real intermediate masses. Therefore
\(\mathrm{OPT}\geq 2D.\)
Choose a shortest path in \(G\),
\(a_0=r_0,\ a_1,\ldots,a_k=r_*.\)
Because edge weights are nonnegative, deleting cycles cannot increase cost. We may therefore choose \(k\leq m-1\). When \(r_0=r_*\), choose \(k=0\).
For each edge, let \(\nu_i=\nu^{a_{i-1}a_i}\) be its stored optimal population. Expand the path into the alternating walk
\(\mu_0\to a_0\to\nu_1\to a_1\to\cdots\to\nu_k\to a_k\to\mu_*.\)
The first and last edges cost zero by the endpoint equilibrium hypotheses. Each internal pair \(a_{i-1}\to\nu_i\to a_i\) costs \(w(a_{i-1},a_i)\). Thus this alternating walk has total cost \(D\).
Turn every consecutive pair of vertices into a state, putting its row component first. For \(k\geq 1\), the resulting sequence is
\((r_0,\mu_0),\ (a_0,\nu_1),\ (a_1,\nu_1),\ (a_1,\nu_2),\ldots,(a_k,\nu_k),\ (r_*,\mu_*).\)
For \(k=0\), it is simply the direct transition between the endpoints.
To calculate its cost precisely, write the expanded alternating walk as \(v_0,\ldots,v_\ell\), where \(\ell=2k+2\), and let \(e_j\) be the weight of \(v_j\to v_{j+1}\). The constructed state indexed by \(j\) consists of \(v_j,v_{j+1}\), ordered with the row first.
The transition between two consecutive constructed states costs \(e_{j-1}+e_j\):
These are exactly the two incident directed edge weights. Summing gives
\(\displaystyle \operatorname{cost}=e_0+2\sum_{j=1}^{\ell-2}e_j+e_{\ell-1}=2D,\)
because \(e_0=e_{\ell-1}=0\).
Together with the lower bound, this proves \(\mathrm{OPT}=2D\). In particular, the infimum is attained. The constructed sequence uses \(2k+1\leq 2m-1\) transitions.
The algorithm solves \(m^2\) rational LPs, each with \(n+1\) variables and \(O(m+n)\) constraints, and then computes one shortest path.
We use the standard theorem that an explicitly given feasible rational LP with finite optimum admits an exact optimal rational solution computable in time polynomial in its binary encoding length. Polynomial-time LP algorithms and polynomial bounds on rational optimal-solution encodings are covered in these [algorithm notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/c61e649bf05c7123da984519955da0bd_lec9.pdf) and [bit-complexity notes](https://courses.csail.mit.edu/6.854/18/Notes/n12-duality.html).
Here every LP is feasible and bounded, as verified above. Its coefficients are input rationals or differences of input rationals, so its encoding length is polynomial in \(m,n,L\). The stored populations and edge weights consequently have polynomial binary length. Shortest-path arithmetic also has polynomial bit complexity.
The output contains at most \(2m\) states, each with at most \(n\) occupied strategies and rational masses of polynomial encoding length. Intermediate support need not be bounded by \(\tau\); the problem explicitly permits all available strategies. Reading and reproducing the endpoints takes polynomial time in their support encoding.
Thus the complete algorithm runs in time polynomial in \(m,n,\tau,L\) and achieves zero additive error.
The [cited finite-population paper](https://arxiv.org/pdf/2312.07603) uses alternating paths and optimization over integer strategy counts. In the stated continuous model, the corresponding population optimization is exactly the LP above, so no rounding is necessary.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned task correctly. The requested additive guarantee follows from the direct-transition bound, and the stronger claim of exact polynomial-time optimization is also established. I found no major or minor mathematical issues requiring repair.
The direct transition costs \(A(\mu_0,r_*)+B(r_0,\mu_*)\). Since the payoffs are nonnegative and populations have unit mass, the two terms are bounded respectively by \(S_R\) and \(S_C\). All transition costs are nonnegative, so \(\mathrm{OPT}\geq 0\).
The comparison \(S_R+S_C\leq 2m(2S_R+S_C)\) holds for every \(m\geq 1\), including when either payoff sum is zero. Thus this observation already settles the requested additive guarantee under the stated normalization.
For fixed \(i,j\), the objective \(B(i,\nu)+A(\nu,j)\) is continuous on the nonempty compact simplex, so its minimum exists.
The constraints on \(z\) encode precisely the maximum defining \(A(x,j)\). The constraint indexed by \(a=j\) supplies the zero term. Nonnegativity of \(R\) and unit mass imply \(0\leq A(x,j)\leq M_R\), so the upper bound on \(z\) does not remove any population from consideration.
The objective increases with \(z\), so for each fixed feasible \(x\), minimization selects \(z=A(x,j)\). Consequently, the LP optimum is exactly \(w(i,j)\).
Feasibility and compactness are correctly established: the simplex bounds \(x\), the stated interval bounds \(z\), and \(z=M_R\) satisfies every payoff-difference constraint. This remains valid when \(M_R=0\).
Every ordered pair has a finite attained edge weight. Both regret terms are nonnegative, so all weights are nonnegative.
Removing cycles cannot increase a walk’s cost. Therefore a shortest path can be selected with at most \(m-1\) edges when the endpoints differ. When the row endpoints coincide, the empty path has minimum cost zero. Zero-weight edges and cycles cause no difficulty.
Every row-to-row walk in the conceptual bipartite graph has an even number of edges and decomposes into pairs \(i\to\nu\to j\). Each pair costs at least \(w(i,j)\), so the associated row walk costs at least \(D\).
All four endpoint edges identified in the output have zero cost by the equilibrium assumptions. The proposed prefix and suffix therefore convert any walk between the indicated endpoint sets into a row-to-row walk without changing its cost.
The parity decomposition of an arbitrary transition sequence is correct. At each step, one walk contributes \(B(r^t,\mu^{t+1})\), and the other contributes \(A(\mu^t,r^{t+1})\). Their assignments interchange with parity, while their sum remains exactly the transition cost.
Both walks consequently cost at least \(D\). This reasoning applies to every finite sequence with arbitrary real intermediate masses; it makes no unsupported restriction to rational populations or bounded supports.
Substituting the stored minimizing populations into a shortest row path produces an alternating walk of cost \(D\), with zero-cost first and last edges.
Consecutive vertex pairs yield valid states with the prescribed endpoints. Each transition changes only one component, which the task expressly allows.
The edge-cost formula is correct: for the transition from constructed state \(j-1\) to constructed state \(j\), the cost is \(e_{j-1}+e_j\). Summation counts each internal edge twice and each boundary edge once. Since both boundary edges vanish, the total is exactly \(2D\).
The construction has \(2k+2\) states and \(2k+1\) transitions, giving the claimed bounds. When \(k=0\), both endpoint populations are equilibria for the same row, so the direct transition has zero cost. Identical endpoints and the case \(m=1\) are covered.
Together with the lower bound, this establishes \(\mathrm{OPT}=2D\) and attainment of the infimum.
The invoked rational-LP theorem is stated with the relevant hypotheses: explicit rational input, feasibility, and finite optimum. These hypotheses have been verified for every constructed LP. Polynomial-time LP solvability and polynomial-size rational solution encodings are supported by the cited [algorithm notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/c61e649bf05c7123da984519955da0bd_lec9.pdf) and [bit-complexity notes](https://courses.csail.mit.edu/6.854/18/Notes/n12-duality.html).
Taking differences of input rationals introduces only polynomial encoding growth. Solving \(m^2\) LPs, storing their solutions, and performing shortest-path arithmetic therefore require polynomial time and space.
The output contains at most \(2m\) states with polynomial-size rational masses. Allowing intermediate support up to \(n\) is consistent with the task; no bound by \(\tau\) is required.
The cited paper does use alternating paths and optimization over integer column-strategy counts, followed by relaxation and rounding. The output’s comparison is supported by its [approximation section](https://arxiv.org/pdf/2312.07603). The continuous proof itself does not depend on importing an unverified result from that paper.
No additional mathematical clarification is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.