Answer: The finite decision problem is \(\mathrm{NP}\)-complete. For the specified atomless kernels, \(D_\infty=1/8\).
Proposition 4.1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIf $n$ is an odd integer representing the number of players, then $d_\ged(T_\Ord,T_\Rps) = \nicefrac{1}{8}(n^2-1)$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite type sets \(I,J\), rational mass distributions \(a,b\), rational tournament kernels \(W,U\) with \(W_{ii'}+W_{i'i}=1\) and \(U_{jj'}+U_{j'j}=1\), and a rational threshold \(\epsilon\), decide whether there is a coupling \(\pi\) with marginals \(a,b\) such that \(\frac12\sum_{i,i',j,j'}\pi_{ij}\pi_{i'j'}|W_{ii'}-U_{jj'}|\le\epsilon\). For the continuous ordered and cyclic kernels corresponding to \(T_{\Ord}\) and \(T_{\Rps}\), determine whether the minimum equals the normalized limit \(1/8\) from Proposition 4.1 or is smaller under fractional couplings.
A society is given by its support: the list of types with positive mass, each mass a binary rational; its support size counts listed types, not possible types. Let the two nonempty supports be \(I,J\), with sizes \(\tau_I,\tau_J\); put \(\tau=\max(\tau_I,\tau_J)\), \(m=|I|+|J|\), and let \(L\) be the total input bit length. State running times in \(m,\tau,L\).
The input masses satisfy \(a_i,b_j>0\) and \(\sum_i a_i=\sum_j b_j=1\). The input kernels have rational entries in \([0,1]\), with \(W_{ii'}+W_{i'i}=U_{jj'}+U_{j'j}=1\), including diagonal entries \(1/2\); the threshold \(\epsilon\) is rational.
A coupling is a real nonnegative matrix \(\pi\) satisfying \(\sum_j\pi_{ij}=a_i\) and \(\sum_i\pi_{ij}=b_j\). Define \(D(W,U;a,b)=\min_\pi\frac12\sum_{i,i',j,j'}\pi_{ij}\pi_{i'j'}|W_{ii'}-U_{jj'}|\).
For the atomless comparison, both type spaces are \([0,1)\) with Lebesgue probability measure. Define \(W_{\mathrm{ord}}(x,x')=\mathbf1_{x<x'}\) off the diagonal, with diagonal value \(1/2\). Define \(W_{\mathrm{cyc}}(y,y')=\mathbf1_{0<(y'-y)\bmod1<1/2}\), except that differences \(0\) and \(1/2\) receive value \(1/2\).
Let \(D_\infty=\min_\gamma\frac12\int|W_{\mathrm{ord}}(x,x')-W_{\mathrm{cyc}}(y,y')|\,d\gamma(x,y)\,d\gamma(x',y')\), where \(\gamma\) ranges over all Borel probability couplings with Lebesgue marginals.
Is deciding \(D(W,U;a,b)\le\epsilon\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For the specified atomless kernels, does \(D_\infty=1/8\), or is \(D_\infty<1/8\)?
For odd \(n\), the minimum number of edge reversals up to vertex bijection between the transitive tournament and the cyclic tournament on \(\mathbb Z/n\mathbb Z\), whose edges satisfy \(i\to i+k\) for \(1\le k\le(n-1)/2\), is \((n^2-1)/8\); dividing by \(n^2\) gives limit \(1/8\). [Nikolow, Faliszewski, and Szufa](https://arxiv.org/html/2601.18348v1)
Discrete tournament edit distance is \(\mathrm{NP}\)-hard even when one tournament is transitive. [Alon](https://epubs.siam.org/doi/10.1137/050623905)
The coupling objective is the network Gromov–Wasserstein distance with \(p=1\), for which optimal couplings exist; this existence result does not settle either target question. [Chowdhury and Mémoli](https://research.math.osu.edu/networks/pubs/gw-nets.pdf)
The finite decision problem is \(\mathrm{NP}\)-complete, even for equal uniform masses, tournament kernels, and one transitive kernel. For the specified atomless kernels, \(D_\infty=1/8\).
The proofs below account explicitly for fractional couplings.
Let \(H\) be a tournament on \(N\) vertices, with kernel \(U\). Let \(W\) be the transitive tournament kernel:
\(W_{ii'}=1\) if \(i<i'\), \(W_{ii'}=0\) if \(i>i'\), and \(W_{ii}=1/2\).
Give every type in both societies mass \(1/N\). Define \(\operatorname{fas}(H)\) as the minimum number of backward edges over all total orders of the vertices of \(H\). We prove
\[ D(W,U;a,b)=\frac{\operatorname{fas}(H)}{N^2}. \]
Here and below, write \(F(\pi)\) for the objective evaluated at a particular coupling.
For an arbitrary feasible coupling \(\pi\), put \(p_{ij}=N\pi_{ij}\). Each column of \(p\) sums to one. Independently for each vertex \(j\) of \(H\), choose a random rank \(R_j\) with \(\Pr(R_j=i)=p_{ij}\). Break equal ranks using independent continuous uniform random variables. This produces a total order of all vertices.
Let \(B\) be its number of backward edges. For distinct vertices \(j,j'\), conditional on their sampled ranks:
Consequently, the conditional probability of disagreement with the edge of \(H\) is precisely \(\lvert W_{R_jR_{j'}}-U_{jj'}\rvert\). Independence of the sampled ranks gives
\[ \mathbb E B = \frac12\sum_{j\ne j'}\sum_{i,i'} p_{ij}p_{i'j'}\lvert W_{ii'}-U_{jj'}\rvert. \]
The terms with \(j=j'\) in the coupling objective are nonnegative. More precisely, because \(U_{jj}=1/2\),
\[ N^2F(\pi) = \mathbb E B+ \frac14\sum_j\left(1-\sum_i p_{ij}^2\right). \]
Indeed, \(\lvert W_{ii'}-1/2\rvert\) is zero for \(i=i'\) and \(1/2\) otherwise, while \(\sum_i p_{ij}=1\).
Every realization of the random order has at least \(\operatorname{fas}(H)\) backward edges. Also, \(\sum_i p_{ij}^2\le 1\). Hence
\[ F(\pi)\ge \frac{\operatorname{fas}(H)}{N^2}. \]
Conversely, choose an order attaining \(\operatorname{fas}(H)\), and couple the type at position \(i\) in the transitive tournament to the vertex at position \(i\) in that order, assigning mass \(1/N\). This is feasible. Each backward edge contributes \(1/N^2\) to the objective, and all other terms vanish. It attains the asserted lower bound.
We use the known \(\mathrm{NP}\)-hardness of deciding whether a tournament has a total order with at most \(K\) backward edges. This is the tournament feedback arc set problem proved hard by [Alon, *Ranking Tournaments*](https://epubs.siam.org/doi/10.1137/050623905).
Given a tournament \(H\) on \(n\) vertices, let \(N\) be the smallest power of two with \(N\ge n\). Add \(N-n\) vertices which precede every original vertex and form a transitive tournament among themselves. Call the resulting tournament \(H^+\).
Restriction of any order of \(H^+\) to the original vertices proves \(\operatorname{fas}(H^+)\ge\operatorname{fas}(H)\). Prepending the added vertices in their transitive order to an optimal order of \(H\) proves the reverse inequality. Thus \(\operatorname{fas}(H^+)=\operatorname{fas}(H)\).
Construct the instance from Section 1 using \(H^+\), and set \(\epsilon=K/N^2\). Then
\[ D(W,U;a,b)\le\epsilon \quad\Longleftrightarrow\quad \operatorname{fas}(H)\le K. \]
All kernel entries satisfy the required hypotheses. The masses \(1/N\) are dyadic, so the reduction works even if “binary rational” is interpreted as requiring a finite binary expansion.
Here \(m=2N\), \(\tau=N\), and the output length is \(L=O(m^2+m\log m)\), assuming the nontrivial range \(0\le K\le n(n-1)/2\). Construction takes \(O(m^2\log m)\) bit operations. This proves \(\mathrm{NP}\)-hardness under polynomial-time many-one reductions.
For completeness, the general problem belongs to \(\mathrm{NP}\), despite allowing real couplings.
Put \(k=\tau_I\tau_J\), and flatten a coupling into a vector \(z\) of length \(k\). Let \(Az=c\) express its marginal constraints, where \(A\) has \(m\) rows and entries in \(\{0,1\}\). Define
\[ C_{(i,j),(i',j')}=\lvert W_{ii'}-U_{jj'}\rvert. \]
The complement identities imply that \(C\) is symmetric. The objective is therefore \(q(z)=\tfrac12z^{\mathsf T}Cz\), on the nonempty compact polytope \(Az=c,\ z\ge0\).
Choose a minimizer \(z_*\), and let \(S\) be its positive support. On this support, every direction \(v\) satisfying \(A_Sv=0\) permits sufficiently small perturbations in both signs. First-order optimality therefore gives \(v^{\mathsf T}C_Sz_*=0\). By elementary linear algebra, some multiplier vector \(\lambda_*\) satisfies
\[ A_Sz_*=c,\qquad C_Sz_*=A_S^{\mathsf T}\lambda_*. \]
Consider the rational linear feasibility system
\[ A_Sz=c,\qquad C_Sz=A_S^{\mathsf T}\lambda,\qquad z\ge0, \]
with \(\lambda\) unrestricted. It is feasible. Splitting each multiplier into a difference of nonnegative variables puts it in standard linear-programming form. A basic feasible solution then supplies rational \(z,\lambda\) of polynomial encoding length, by the determinant bounds for rational linear systems.
Every feasible solution of this system has the same objective value as \(z_*\). Indeed, symmetry gives
\[ q(z)-q(z_*) = \frac12(z-z_*)^{\mathsf T}C_S(z+z_*) = \frac12\bigl(A_S(z-z_*)\bigr)^{\mathsf T}(\lambda+\lambda_*) =0. \]
Extending \(z\) by zeros outside \(S\) thus yields a rational global minimizer of polynomial encoding length. A verifier checks its marginals, nonnegativity, and objective threshold using polynomial-time rational arithmetic. This proves membership in \(\mathrm{NP}\), and hence \(\mathrm{NP}\)-completeness.
The same argument gives an exact algorithm: enumerate all supports \(S\), solve the displayed linear feasibility system, and evaluate one solution whenever it is feasible. Every candidate is a feasible coupling, and at least one candidate attains the global minimum.
There are at most \(2^k\) supports. The running time is
\[ 2^{\tau_I\tau_J}\operatorname{poly}(m,\tau,L) \subseteq 2^{O(\tau^2)}\operatorname{poly}(L). \]
A candidate objective uses \(O(k^2)\) rational arithmetic operations. These bounds depend on the listed supports; no additional possible types are introduced.
Let \(\gamma\) be any Borel probability coupling with Lebesgue marginals. For each fixed \((x,y)\), the integral triangle inequality gives
\[ \int \lvert W_{\mathrm{ord}}(x,x')-W_{\mathrm{cyc}}(y,y')\rvert \,d\gamma(x',y') \ge \left| \int W_{\mathrm{ord}}(x,x')\,dx' - \int W_{\mathrm{cyc}}(y,y')\,dy' \right|. \]
The two marginal identities justify replacing the respective integrals against \(\gamma\) by Lebesgue integrals. Directly from the kernel definitions,
\[ \int W_{\mathrm{ord}}(x,x')\,dx'=1-x, \qquad \int W_{\mathrm{cyc}}(y,y')\,dy'=\frac12. \]
The exceptional diagonal and antipodal points have Lebesgue measure zero. Integrating the lower bound against \(\gamma(x,y)\), and using its first marginal, yields
\[ F_\infty(\gamma) \ge \frac12\int_0^1\left|\frac12-x\right|\,dx = \frac18. \]
Thus this bound applies to arbitrary fractional or singular couplings.
Take the identity coupling, the law of \((X,X)\) for uniform \(X\in[0,1)\). It has the required marginals.
For this coupling, away from the null sets where \(x=x'\) or \(\lvert x-x'\rvert=1/2\), the two kernels disagree exactly when \(\lvert x-x'\rvert>1/2\). Therefore
\[ F_\infty(\gamma_{\mathrm{id}}) = \frac12\int_0^1\int_0^1 \mathbf1_{\{\lvert x-x'\rvert>1/2\}}\,dx'\,dx = \int_0^{1/2}\left(\frac12-x\right)\,dx = \frac18. \]
Combined with the universal lower bound, this proves \(D_\infty=1/8\).
⟨structured verdict parsed — rendered above⟩
The output resolves both targets correctly. The finite decision problem is \(\mathrm{NP}\)-complete, and the specified atomless value is \(D_\infty=1/8\). I found no major or minor mathematical issues.
The normalization \(p_{ij}=N\pi_{ij}\) is correct: each column sums to one, so it defines the stated distribution of \(R_j\). Independently sampling ranks and breaking ties with independent continuous random variables produces a total order almost surely.
For distinct vertices \(j,j'\), the conditional disagreement probability is correctly identified:
Independence therefore justifies the displayed expression for \(\mathbb E B\). The factor \(1/2\) correctly compensates for counting each unordered pair twice.
The diagonal correction is also correct. For each \(j\), its contribution to \(N^2F(\pi)\) is
\(\frac14\sum_{i\ne i'}p_{ij}p_{i'j}
=\frac14(1-\sum_i p_{ij}^2)\).
It is nonnegative because the column entries form a probability distribution.
Every resulting order has at least \(\operatorname{fas}(H)\) backward edges, giving the claimed lower bound for every real coupling. The coupling induced by an optimal order has the correct marginals and contributes exactly \(1/N^2\) per backward edge. Thus the equality
\(D(W,U;a,b)=\operatorname{fas}(H)/N^2\)
is established, including the case \(N=1\).
The invoked tournament feedback arc set hardness agrees with the cited [Alon paper](https://epubs.siam.org/doi/10.1137/050623905). Its formulation by edge reversals corresponds to minimizing backward edges in a total order.
The padding argument preserves the optimum:
Consequently, \(\operatorname{fas}(H^+)=\operatorname{fas}(H)\), and the threshold \(\epsilon=K/N^2\) gives the stated decision equivalence.
The construction meets every input restriction: positive normalized masses, permitted rational kernel entries, complement identities, and diagonal entries \(1/2\). Choosing a power of two makes both the masses and threshold dyadic when \(K\) is integral.
Since \(N<2n\) for \(n>1\), padding is polynomial in the source size. The stated output length and construction time are valid upper bounds under the explicit matrix encoding. Restricting to the nontrivial threshold range does not undermine hardness; thresholds outside that range have immediate answers.
This argument correctly handles the possibility of real optimal couplings.
The complement identities imply symmetry of \(C\), including when either pair of indices coincides. The feasible polytope is nonempty and compact, so a minimizer exists.
On the positive support \(S\), every vector in \(\ker A_S\) permits sufficiently small perturbations in both signs. First-order optimality therefore gives
\(C_Sz_*\in(\ker A_S)^\perp=\operatorname{im}A_S^{\mathsf T}\),
which justifies the multiplier equation without requiring independent marginal constraints.
The resulting rational linear system is feasible. After splitting unrestricted multipliers, the standard basic feasible solution and determinant bounds apply. Redundant equations do not obstruct this application. Its dimensions and coefficient encoding lengths are polynomial in the input size, so the resulting rational solution has polynomial encoding length.
The assertion that every feasible solution of this system has the same objective is verified by the displayed identity. It uses precisely symmetry, the multiplier equations, and equality of the marginals. It remains valid when the new solution has zero coordinates within \(S\).
Thus a rational global minimizer of polynomial encoding length exists. Exact rational verification establishes membership in \(\mathrm{NP}\), completing the \(\mathrm{NP}\)-completeness claim.
The support enumeration argument is sound. Every feasible candidate extends to a feasible coupling, and the enumeration includes the positive support of a global minimizer. On that support, every returned solution has the optimal objective value.
There are at most \(2^{\tau_I\tau_J}\) supports. Each rational linear feasibility problem has polynomial size, and its objective can be evaluated using \(O(k^2)\) rational arithmetic operations with polynomial bit complexity.
Accordingly, the stated bound
\(2^{\tau_I\tau_J}\operatorname{poly}(m,\tau,L)
\subseteq 2^{O(\tau^2)}\operatorname{poly}(L)\)
is justified. It uses listed support sizes as required.
The integral triangle inequality applies to these bounded measurable kernels. The marginal identities justify replacing each separate kernel integral by its Lebesgue integral, even for singular couplings.
The row integrals are correctly computed as \(1-x\) and \(1/2\). Exceptional diagonal and antipodal points have zero measure in these integrations. The resulting lower bound is
\(\frac12\int_0^1|1/2-x|\,dx=1/8\).
For the identity coupling, the kernels disagree exactly when \(|x-x'|>1/2\), outside the stated null sets. That region has area \(1/4\), so the objective is \(1/8\). This explicitly attains the universal lower bound and establishes the claimed minimum.
No additional clarification or repair 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.