Answer: \(\mathrm{NP}\)-complete
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven two task allocations~$\task \in \mathbb{R}_{\geq 0}^{n \times m}$ and~$\task' \in \mathbb{R}_{\geq 0}^{n \times m}$ and an real number~$d$, deciding whether~$\idealdist(\task, \task') \leq d$ is~\nphard{}.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) goods and two finite-support rational distributions \(\mu,\nu\) over \(\Delta_m=\{u\in\mathbb{Q}_{\ge 0}^m:\sum_{j=1}^m u_j=1\}\), with their supports and masses listed explicitly, and a rational threshold \(d\), decide whether there exist a good permutation \(\pi\in S_m\) and a coupling \(\lambda\) of \(\mu,\nu\) such that \(\sum_{u,v}\lambda_{uv}\lVert u-\pi(v)\rVert_1\le d\).
Let \(m\ge 2\) and \(\Delta_m=\{u\in\mathbb Q_{\ge0}^m:\sum_{j=1}^m u_j=1\}\). Input consists of two probability societies \(\mu,\nu\) on \(\Delta_m\) and a threshold \(d\in\mathbb Q\).
Each society is given by its support: distinct types with positive binary rational masses summing to \(1\). Write \(\tau_\mu,\tau_\nu\) for their support sizes and \(\tau=\tau_\mu+\tau_\nu\); these count listed types, not possible types. Let \(L\) be the total binary input length, including utility coordinates, masses, and \(d\).
A coupling is an array \(\lambda_{uv}\in\mathbb R_{\ge0}\) with \(\sum_v\lambda_{uv}=\mu(u)\) and \(\sum_u\lambda_{uv}=\nu(v)\). Mass may split among types.
A single permutation \(\pi\in S_m\) acts on every type of \(\nu\), with \((\pi(v))_j=v_{\pi(j)}\). Decide whether some \(\pi\) and coupling satisfy \(\sum_{u,v}\lambda_{uv}\lVert u-\pi(v)\rVert_1\le d\).
Is this decision problem solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For two finite lists of equally many normalized utility vectors, minimizing total \(\ell_1\) distance over simultaneous agent and good permutations is \(\mathrm{NP}\)-hard; fixing either permutation makes the discrete problem polynomial-time solvable. [Verified discrete results](https://arxiv.org/html/2504.20161v2#A2.SS2)
No verified literature result was found settling the distributional problem defined above.
The problem is \(\mathrm{NP}\)-hard, and in fact \(\mathrm{NP}\)-complete. Allowing mass to split does not remove the discrete hardness: for empirical societies obtained from equally long lists, fractional transport has exactly the same optimum as matching the list entries, after normalization.
We use the discrete decision problem supplied in the question. Given two lists
\((a_1,\ldots,a_n)\) and \((b_1,\ldots,b_n)\) of rational vectors in \(\Delta_m\), and a rational threshold \(D\), decide whether
\(\displaystyle \min_{\sigma\in S_n,\ \pi\in S_m}\sum_{i=1}^n\lVert a_i-\pi(b_{\sigma(i)})\rVert_1\le D.\)
This problem is \(\mathrm{NP}\)-hard by [Theorem 5 of *Putting Fair Division on the Map*](https://arxiv.org/html/2504.20161v2#A2.SS2). Its reduction uses preference ranks divided by their common sum, so the hardness applies to rational normalized vectors and rational thresholds of polynomial encoding length. The correct rank sum is \(F=\sum_{j=1}^m j=m(m+1)/2\).
The lists may contain repeated vectors. The next lemma explicitly handles this.
Lemma. Let \(a_1,\ldots,a_n,b_1,\ldots,b_n\in\Delta_m\). Define societies by giving every list occurrence mass \(1/n\), merging identical vectors. Thus, writing
\(r_u=\lvert\{i:a_i=u\}\rvert,\qquad s_v=\lvert\{k:b_k=v\}\rvert,\)
their positive masses are \(\mu(u)=r_u/n\) and \(\nu(v)=s_v/n\). For every fixed \(\pi\in S_m\),
\(\displaystyle \min_{\lambda\text{ coupling }\mu,\nu}\sum_{u,v}\lambda_{uv}\lVert u-\pi(v)\rVert_1 =\frac1n\min_{\sigma\in S_n}\sum_{i=1}^n\lVert a_i-\pi(b_{\sigma(i)})\rVert_1.\)
Proof. Fix \(\pi\), and put \(c_{ik}=\lVert a_i-\pi(b_k)\rVert_1\).
First consider matrices \(X=(x_{ik})\) satisfying
\(x_{ik}\ge0,\qquad \sum_kx_{ik}=1/n,\qquad \sum_ix_{ik}=1/n.\)
Such a matrix induces a society coupling by
\(\displaystyle \lambda_{uv}=\sum_{\substack{i:a_i=u\\k:b_k=v}}x_{ik}.\)
Its row marginal at \(u\) is \(r_u/n\), and its column marginal at \(v\) is \(s_v/n\). Since the cost is constant within each block of identical types,
\(\displaystyle \sum_{i,k}x_{ik}c_{ik}=\sum_{u,v}\lambda_{uv}\lVert u-\pi(v)\rVert_1.\)
Conversely, any society coupling \(\lambda\) lifts to such a matrix by setting
\(\displaystyle x_{ik}=\frac{\lambda_{a_i b_k}}{r_{a_i}s_{b_k}}.\)
Indeed, for \(a_i=u\),
\(\displaystyle \sum_kx_{ik}=\sum_v s_v\frac{\lambda_{uv}}{r_us_v} =\frac{\mu(u)}{r_u}=\frac1n.\)
The column calculation is identical. Each block contains \(r_us_v\) entries, so this lift also preserves the cost. Therefore the society transport optimum equals the minimum of \(\sum_{i,k}x_{ik}c_{ik}\) over these matrices.
Now \(P=nX\) is doubly stochastic. The Birkhoff–von Neumann theorem states that every nonnegative square matrix with all row and column sums equal to \(1\) is a convex combination of permutation matrices. Its hypotheses hold here. Consequently, for some nonnegative coefficients \(\alpha_\sigma\) summing to \(1\),
\(\displaystyle \sum_{i,k}x_{ik}c_{ik} =\frac1n\sum_{\sigma\in S_n}\alpha_\sigma\sum_i c_{i,\sigma(i)} \ge\frac1n\min_{\sigma\in S_n}\sum_i c_{i,\sigma(i)}.\)
For the reverse inequality, choose a minimizing permutation \(\sigma\) and set \(x_{i,\sigma(i)}=1/n\), with all other entries zero. This matrix is feasible and attains the right-hand side. The lemma follows. \(\square\)
In particular, the lemma permits arbitrary real split couplings; it imposes no integrality restriction on them.
Given a discrete instance \((a_1,\ldots,a_n),(b_1,\ldots,b_n),D\), construct the empirical societies from the lemma and set \(d=D/n\).
The construction meets every input requirement:
Equality comparisons between rational vectors and the required rational arithmetic take polynomial time in the discrete input length. Thus the construction is a polynomial-time many-one reduction.
Applying the lemma separately to every good permutation gives
\(\displaystyle \min_{\pi\in S_m}\min_{\lambda\text{ coupling }\mu,\nu} \sum_{u,v}\lambda_{uv}\lVert u-\pi(v)\rVert_1 = \frac1n\min_{\pi\in S_m,\ \sigma\in S_n} \sum_i\lVert a_i-\pi(b_{\sigma(i)})\rVert_1. \)
Hence the constructed instance has cost at most \(d=D/n\) exactly when the discrete instance has cost at most \(D\). This proves \(\mathrm{NP}\)-hardness.
Notice that the reduction constructs its support directly from the explicitly given lists. It never expands binary masses into a potentially enormous population.
A certificate consists of the good permutation \(\pi\), encoded using \(O(m\log m)\) bits.
Given this permutation, compute the rational costs
\(\displaystyle c_{uv}=\sum_{j=1}^m|u_j-v_{\pi(j)}|.\)
Then test feasibility of the rational linear program
\(\displaystyle \lambda_{uv}\ge0,\qquad \sum_v\lambda_{uv}=\mu(u),\qquad \sum_u\lambda_{uv}=\nu(v),\qquad \sum_{u,v}c_{uv}\lambda_{uv}\le d. \)
It has \(\tau_\mu\tau_\nu\) variables and polynomially many constraints. Exact rational additions and subtractions produce coefficients of polynomial binary encoding length in \(m,\tau,L\). Polynomial-time feasibility algorithms for rational linear programming therefore provide a polynomial-time verifier.
If the instance is a yes-instance, some permutation makes this program feasible. Conversely, feasibility for the certified permutation supplies exactly the coupling required by the question. Thus the problem belongs to \(\mathrm{NP}\).
Combining membership and hardness proves \(\mathrm{NP}\)-completeness. A polynomial-time algorithm in \(m,\tau,L\) would therefore imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The reduction preserves the optimum even when types repeat and couplings split mass. The argument also establishes membership in \(\mathrm{NP}\), so the claimed \(\mathrm{NP}\)-completeness is justified. No major or minor mathematical issues were found.
The discrete decision problem stated in Section 1 matches the verified result supplied in USER_TASK: equally long lists of normalized utility vectors, one common coordinate permutation, one permutation matching list entries, and a total \(\ell_1\) threshold.
The cited [Theorem 5 and its reduction](https://arxiv.org/html/2504.20161v2#A2.SS2) support the rational encoding restriction. Their construction uses integer preference ranks and a common normalization factor, giving rational coordinates and a rational threshold of polynomial encoding length.
The source contains an erroneous binomial expression for the rank sum. The prover explicitly gives the correct value, \(F=m(m+1)/2\). Its normalization statement is therefore correct. The discrete hardness result is also expressly provided as verified in the task; the prover is entitled to use it.
For fixed \(\pi\), the occurrence costs \(c_{ik}=\lVert a_i-\pi(b_k)\rVert_1\) are constant on each block determined by identical original types.
Aggregating a feasible matrix \(X\) over these blocks gives nonnegative coupling entries. Summing its occurrence rows gives the required marginal \(r_u/n\); summing its occurrence columns gives \(s_v/n\). The displayed cost identity follows directly from blockwise constancy.
This argument respects the requirement that a single \(\pi\) act on every type.
The formula \(x_{ik}=\lambda_{a_i b_k}/(r_{a_i}s_{b_k})\) is well-defined: every listed occurrence belongs to a type of positive multiplicity.
The row calculation is correct. The corresponding column calculation yields \(\nu(v)/s_v=1/n\). A block has exactly \(r_us_v\) entries, so its entries sum to \(\lambda_{uv}\), preserving the objective.
Thus aggregation and lifting establish equality of the two feasible objective-value sets. Repeated vectors cause no loss of information relevant to transport cost.
The theorem is stated precisely enough for this application. The matrix \(P=nX\) is square, nonnegative, and has every row and column sum equal to one.
Its decomposition into permutation matrices makes the transport objective a convex combination of matching costs, scaled by \(1/n\). The resulting lower bound has the correct direction and scaling.
Conversely, the matrix supported on a minimizing matching has all required marginals and attains that bound. Since there are finitely many matching permutations, a minimizing matching exists.
The proof applies to arbitrary real feasible matrices, so it fully addresses the permission to split mass.
Merging identical vectors produces distinct support types with positive rational masses summing to one. The bound \(\tau\le 2n\) is correct.
Numerators and denominators of multiplicity masses require \(O(\log n)\) bits. Forming \(D/n\) increases threshold encoding length by at most \(O(\log n)\). Rational equality comparisons and merging take polynomial time in the explicitly listed source input.
The fixed-\(\pi\) equality holds for every coordinate permutation. Taking minima over the same finite set of permutations therefore preserves equality. Setting \(d=D/n\) gives the stated equivalence of yes-instances.
The construction does not expand arbitrary binary masses into occurrences: its occurrences are already present in the source lists.
A permutation has polynomial certificate length. For that permutation, the displayed linear program has exactly the required marginal constraints, nonnegativity constraints, and cost inequality.
Its number of variables and constraints is polynomial in the support sizes. Computing rational coordinate differences and summing their absolute values produces coefficients of polynomial bit length.
The invoked theorem—that rational linear-program feasibility is decidable in polynomial time in the encoded program length—applies. It provides an exact feasibility test, including equality at the threshold. A coupling need not itself appear in the certificate because the verifier decides its existence in polynomial time.
The empirical construction uses nonempty lists, as required to define probability societies. The hardness premise supplies the relevant nondegenerate instances with \(m\ge 2\).
Negative thresholds and threshold equality do not invalidate either the reduction or the feasibility formulation. All couplings considered satisfy the stated real-valued domain.
Consequently, the hardness proof and membership proof establish the claimed complexity classification. No additional lemma, 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.