Answer: The stated seed promise does not guarantee feasibility. Even with an additional feasibility promise, the search problem is \(\mathrm{NP}\)-hard, already for \(\tau=2\), identical menus, constant latencies, and \(\beta=2\).
Theorem 4.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a weighted congestion setting denoted by G = (𝑁, (𝑤)𝑖∈𝑁,𝐺, (𝑐𝑒)𝑒∈𝐸(𝐺), (𝑆𝑖)𝑖∈𝑁), let 𝑁𝑤 be the set of agents derived after replacing each agent of 𝑁 with 𝑤 agents. Suppose that there exists an outcome s′ of the unweighted setting G′ = (𝑁𝑤, (1)𝑖∈𝑁𝑤,𝐺, (𝑐𝑒)𝑒∈𝐸(𝐺), (P𝑖)𝑖∈𝑁𝑤), where the envy-ratio is at most 𝛽 and the approximation ratio to the minimum social cost is at most 𝛼. Then, for G, there exists an outcome s with envy-ratio at most 1 + 𝛽−1 𝑤 and approximation ratio at most 𝛼.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite network \(G\), polynomial edge latencies \(c_e\), total fleet mass \(M\), common fleet size \(w\), type masses \(\mu_t\), route menus \(\mathcal P_t\), and unit-route masses \(y_{t,p}\) satisfying \(\sum_{p\in\mathcal P_t}y_{t,p}=w\mu_t\), with seed envy-ratio at most \(\beta\), find a succinct bundle-mass distribution \(\lambda_{t,B}\) over \(B\in\mathcal P_t^w\) such that \(\sum_B\lambda_{t,B}=\mu_t\), \(\sum_B\lambda_{t,B}\#_p(B)=y_{t,p}\), and the resulting fleet envy-ratio is at most \(1+(\beta-1)/w\). Here \(L_e=M\sum_t\sum_{p\in\mathcal P_t:e\in p}y_{t,p}\), bundle cost is \(C(B)=\sum_{p\in B}\sum_{e\in p}c_e(L_e)\), and social cost is \(\sum_eL_ec_e(L_e)\).
A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
The input includes a finite undirected network \(G=(V,E)\), nonempty explicitly listed menus \(\mathcal P_t\) of simple paths joining each type's endpoints, positive binary-rational total fleet mass \(M\), binary-encoded common fleet size \(w\in\mathbb Z_{\ge1}\), and binary-rational \(\beta\ge1\). Let \(m=\sum_t|\mathcal P_t|\). Edge latencies are \(c_e(x)=\sum_{r=0}^{d}a_{e,r}x^r\), with nonnegative binary-rational coefficients explicitly listed.
Given binary-rational unit-route masses \(y_{t,p}\ge0\) satisfying \(\sum_{p\in\mathcal P_t}y_{t,p}=w\mu_t\), define \(L_e=M\sum_t\sum_{p\in\mathcal P_t:e\in p}y_{t,p}\) and \(\ell_p=\sum_{e\in p}c_e(L_e)\). The seed promise is \(\ell_p\le\beta\ell_q\) whenever \(\mathcal P_t=\mathcal P_u\), \(y_{t,p}>0\), and \(y_{u,q}>0\).
A bundle \(B\in\mathcal P_t^w\) may repeat paths; write \(\#_p(B)\) for its multiplicities and \(C(B)=\sum_p\#_p(B)\ell_p\). A bundle-mass distribution has nonnegative rational masses \(\lambda_{t,B}\) satisfying \(\sum_B\lambda_{t,B}=\mu_t\) and \(\sum_B\lambda_{t,B}\#_p(B)=y_{t,p}\).
Its envy-ratio is the least \(\gamma\ge1\) such that \(C(B)\le\gamma C(D)\) for every pair of positive-mass bundles belonging to types with identical menus; this inequality convention includes zero costs. Require \(\gamma\le1+(\beta-1)/w\). The marginal constraints preserve social cost \(\sum_eL_ec_e(L_e)\).
The search problem is to find such a distribution succinctly: list its positive-mass bundles using binary-encoded path multiplicities and rational masses, with total encoding length polynomial in the input length. Let \(L\) be the total input bit length.
Is this promised mass-bundling search problem solvable in time polynomial in \(m,\tau,L,|V|+|E|,d,\log(w+1)\), or is it NP-hard?
For finite fleets of equal integer size, a polynomial-time regrouping of an explicitly supplied unit-route assignment preserves edge loads and social cost and improves envy-ratio from \(\beta\) to at most \(1+(\beta-1)/w\). [Discrete regrouping result](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2025/pdfs/p923.pdf).
No result settling this exact continuous mass-bundling search problem was identified in the literature search.
With the prescribed type-by-type marginals, the search problem is \(\mathrm{NP}\)-hard even if feasibility is additionally promised. This holds with two types, identical menus, constant latencies, and \(\beta=2\).
There is also a defect in the stated promise: it does not guarantee that a required distribution exists. For example, take \(w=2\), \(\beta=2\), two types of mass \(1/2\), and a common menu containing routes of constant costs \(1\) and \(2\). Prescribe that the first type uses only the first route and the second only the second route. Their forced bundle costs are \(2\) and \(4\), whereas the required ratio is \(3/2\).
The following reduction addresses the substantive question after adding a feasibility promise.
We reduce from \(\mathrm{PARTITION}\): given positive integers \(a_1,\ldots,a_n\), decide whether some subset has sum half the total. This problem is \(\mathrm{NP}\)-complete. [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
We may assume \(n\ge2\) and that the total is even: multiplying every input integer by \(2\) preserves the answer and ensures an even total.
Let \(w\) be the smallest power of two satisfying \(w\ge n\). Pad the sequence with zeros to obtain \(a_1,\ldots,a_w\), and define
\[
\]
<!-- All mathematical expressions below use the requested inline delimiters. -->
\(S=\sum_{i=1}^{w}a_i,\qquad H=wS+1,\qquad R=w+1.\)
Define positional weights and a positive baseline by
\(\Delta_i=H R^{i-1},\qquad U=\Delta_w+\max_i a_i,\qquad K=4U.\)
For each index introduce two routes with costs
\(\ell_{p_i^0}=K+\Delta_i,\qquad \ell_{p_i^1}=K+\Delta_i+a_i.\)
Finally, define
\(T=wK+\sum_{i=1}^{w}\Delta_i+S/2,\qquad \theta=T/w,\qquad g=1+1/w.\)
Introduce one further route \(q\), whose cost is
\(\ell_q=g\theta.\)
The positional weights will force an exact-cost bundle to choose exactly one route from each pair.
Both types have the same explicitly listed menu
\(\mathcal P=\{p_i^0,p_i^1:1\le i\le w\}\cup\{q\}.\)
Their masses are \(\mu_0=\mu_1=1/2\). Set \(M=1\) and \(\beta=2\). Prescribe the marginals as follows:
Thus each type’s marginals sum to \(w/2=w\mu_t\).
To realize these costs in a simple undirected network, create distinct internal vertices \(v_p\), one for each route \(p\). Route \(p\) is the two-edge path \(s,v_p,t\). Assign constant latency \(\ell_p\) to \(\{s,v_p\}\) and zero latency to \(\{v_p,t\}\). All coefficients are nonnegative, and the latencies have degree \(d=0\).
We now verify the seed promise. Every paired-route cost belongs to \([K,K+U]\). Also,
\(\theta=K+\frac1w\sum_{i=1}^{w}(\Delta_i+a_i/2),\)
so \(K\le\theta\le K+U\). Since \(w\ge2\),
\(K\le\ell_q=g\theta\le\frac32(K+U)=\frac{15}{8}K<2K.\)
Consequently, every used route has cost between \(K\) and \(2K\). Any two used routes therefore satisfy \(\ell_p\le2\ell_{p'}\), establishing the seed promise with \(\beta=2\).
The required bundle envy bound is exactly \(g=1+1/w\).
Consider any distribution satisfying the prescribed marginals and the envy bound.
The anchor bundle is forced. Type \(1\) has zero marginal on every route other than \(q\). Because masses and multiplicities are nonnegative, every positive-mass bundle of this type consists of \(w\) copies of \(q\). Its cost is
\(w\ell_q=wg\theta=gT.\)
Therefore, for every positive-mass type-\(0\) bundle \(B\), the envy inequality from the anchor bundle to \(B\) gives
\(gT\le gC(B),\)
and hence \(C(B)\ge T\).
The fixed mean forces equality. The type-\(0\) marginals give
\(\sum_B\lambda_{0,B}C(B)=\frac14\sum_{i=1}^{w}(\ell_{p_i^0}+\ell_{p_i^1})=\frac12T.\)
Since the total type-\(0\) bundle mass is \(1/2\), its conditional average bundle cost is \(T\). Every positive-mass bundle has cost at least \(T\); thus every such bundle must have cost exactly \(T\).
Fix one of these bundles. It cannot contain \(q\), because \(y_{0,q}=0\). Write
\(x_i^b=\#_{p_i^b}(B),\qquad r_i=x_i^0+x_i^1.\)
The bundle size and exact-cost equations are
\(\sum_{i=1}^{w}r_i=w\)
and
\(\sum_{i=1}^{w}r_i\Delta_i+\sum_{i=1}^{w}x_i^1a_i=\sum_{i=1}^{w}\Delta_i+S/2.\)
Every \(\Delta_i\) is divisible by \(H\). Reducing the latter equation modulo \(H\) gives
\(\sum_i x_i^1a_i\equiv S/2\pmod H.\)
Both quantities lie in \([0,H)\): indeed,
\(0\le\sum_i x_i^1a_i\le w\max_i a_i\le wS<H.\)
Thus the congruence is an equality:
\(\sum_i x_i^1a_i=S/2.\)
Subtracting this equality from the cost equation and dividing by \(H\) yields
\(\sum_{i=1}^{w}r_iR^{i-1}=\sum_{i=1}^{w}R^{i-1}.\)
Each \(r_i\) is an integer satisfying \(0\le r_i\le w<R\). Uniqueness of base-\(R\) representation therefore implies \(r_i=1\) for every \(i\). Explicitly, reduction modulo \(R\) gives \(r_1=1\); subtracting and dividing by \(R\), and repeating, gives all remaining equalities.
Consequently, each \(x_i^1\) belongs to \(\{0,1\}\). The indices with \(x_i^1=1\) form a partition of total weight \(S/2\). Removing padded zero entries gives a partition of the original instance.
This proves that every valid output encodes a solution to the source instance, despite bundles being allowed to repeat routes.
Conversely, suppose \(I\subseteq\{1,\ldots,w\}\) satisfies \(\sum_{i\in I}a_i=S/2\).
Construct two type-\(0\) bundles:
Give each bundle mass \(1/4\). Each paired route occurs in exactly one of these bundles, so its prescribed marginal is \(1/4\). Both bundle costs equal \(T\), because \(I\) and its complement each have weight \(S/2\).
For type \(1\), give the bundle consisting of \(w\) copies of \(q\) mass \(1/2\). Its cost is \(gT\).
The only positive bundle costs are therefore \(T\) and \(gT\), so the envy-ratio is exactly \(g\). All marginals are satisfied, and hence edge loads and social cost are preserved.
This output uses only three bundles, encoded by path multiplicities and rational masses.
The construction has \(\tau=2\), menu size \(2w+1\), and \(m=2(2w+1)\). Its graph has \(2w+3\) vertices and \(2(2w+1)\) edges.
Because \(w<2n\), its numerical encoding is polynomial in the source input length. In particular,
\(\log_2\Delta_w=O(\log_2 S+w\log_2(w+1)).\)
All masses are dyadic. Since \(w\) is a power of two and \(T\) is an integer, \(\theta=T/w\) and \(\ell_q=(w+1)T/w^2\) are also dyadic. Thus the reduction works even under the interpretation that “binary-rational” requires a power-of-two denominator.
We have proved the exact equivalence:
\(\text{source instance has a partition}\quad\Longleftrightarrow\quad\text{constructed instance has a valid distribution}.\)
Moreover, every valid distribution yields a partition by inspecting any positive-mass type-\(0\) bundle.
For precision, suppose an algorithm is guaranteed to produce a valid output in polynomial time whenever a constructed instance is feasible. Run it for its polynomial time bound and inspect its output for a valid partition. On a yes-instance it necessarily supplies one. On a no-instance no candidate can pass the partition check, regardless of the algorithm’s behavior outside its feasibility promise. This would decide \(\mathrm{PARTITION}\) in polynomial time.
Therefore, even the search problem with an additional feasibility promise is \(\mathrm{NP}\)-hard.
The cited regrouping algorithm reallocates routes among compatible fleets while preserving aggregate traffic and social cost. [Gollapudi et al., Theorem 4.1 and Algorithm 1](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2025/pdfs/p923.pdf).
The present task additionally requires preservation of each type’s individual route marginals. Those constraints fix each type’s average bundle cost. The reduction exploits precisely this requirement: the anchor imposes a lower bound, and the other type’s fixed mean forces every bundle to attain that bound exactly.
Thus aggregate load preservation and type-by-type marginal preservation lead to different problems. The hardness above concerns the exact latter formulation.
⟨structured verdict parsed — rendered above⟩
Assessment: proved. The reduction is correct, respects the input encoding, and establishes the claimed search hardness through the explicit polynomial-time cutoff argument. The feasibility counterexample is also correct. I found no major or minor mathematical gaps.
The conclusion needs to be understood exactly as the prover states it: the original seed promise does not ensure existence of an output, and finding an output on feasible instances is already computationally hard.
The example satisfies the task’s assumptions:
The forced bundle costs are consequently \(2\) and \(4\). Their envy-ratio is \(2\), exceeding the required bound
\(1+(\beta-1)/w=3/2\).
Thus the original promise genuinely permits infeasible inputs. This is a defect in the search problem’s existence guarantee, not an error in the prover’s argument.
The source problem is stated precisely: positive-integer \(\mathrm{PARTITION}\), asking for a subset of weight half the total. Its NP-completeness is the standard result attributed to [Karp](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Multiplying all integers by \(2\) preserves the answer and makes \(S\) even. Restricting to \(n\ge2\) excludes only trivial source instances. Zero padding is internal to the construction and does not violate the positive-integer source specification.
The definitions ensure:
The network realization is valid. Distinct internal vertices produce distinct simple two-edge paths in a simple undirected graph. Constant nonnegative edge latencies realize the specified route costs independently of loads. Choosing \(M=1\) and \(d=0\) is permitted.
The prescribed marginals are correctly normalized: type \(0\) has \(2w\) entries of mass \(1/4\), totaling \(w/2\); type \(1\) assigns mass \(w/2\) to \(q\). These totals equal \(w\mu_t\).
Since \(\Delta_i\le\Delta_w\) and \(a_i\le\max_j a_j\), every paired-route cost lies in \([K,K+U]\).
The expression
\[
\]
\( \theta=K+\frac1w\sum_i(\Delta_i+a_i/2) \)
also lies in this interval: every summand inside the average lies between \(0\) and \(U\).
Using \(w\ge2\) and \(K=4U\), the claimed bound is correct:
\(g\theta\le\frac32(K+U)=\frac{15}{8}K<2K\).
Also, \(g\theta\ge K\).
Hence every used route has cost at least \(K\) and less than \(2K\). This establishes every ordered comparison required by the seed promise, including comparisons between the two types.
The target envy bound is correctly identified as \(g=1+1/w\).
Type \(1\)’s zero marginals on all paired routes force every positive-mass bundle of that type to consist of \(w\) copies of \(q\). Its positive total type mass guarantees such a bundle exists.
Its cost is \(w\ell_q=gT\). Because the menus are identical, the envy constraint applies from this anchor to every positive-mass type-\(0\) bundle. The inequality \(gT\le gC(B)\) is therefore justified and implies \(C(B)\ge T\).
The weighted type-\(0\) cost calculation is correct:
\( \frac14\sum_i(\ell_{p_i^0}+\ell_{p_i^1})=\frac12T \).
Dividing by the total type mass \(1/2\) gives conditional mean \(T\). Since every positive-mass bundle has cost at least \(T\), all such bundles must have cost exactly \(T\).
There is no issue involving infinite support: for each input, the available bundle set is finite, although potentially very large.
The zero marginal on \(q\) excludes it from positive-mass type-\(0\) bundles. The multiplicities therefore satisfy the stated bundle-size and exact-cost equations.
Reduction modulo \(H\) is legitimate because all relevant terms are integers and \(H\) divides every \(\Delta_i\). The bound
\(0\le\sum_i x_i^1a_i\le w\max_i a_i\le wS<H\)
is correct. Also, \(0\le S/2<H\). Thus the congruence forces equality, rather than merely equality modulo \(H\).
After subtraction and division by \(H\), each coefficient \(r_i\) lies in \(\{0,\ldots,w\}\), strictly below the base \(R=w+1\). The positional representation is consequently unique. The prover additionally supplies the repeated reduction-modulo-\(R\) justification, so no missing lemma remains.
It follows that \(r_i=1\) and \(x_i^1\in\{0,1\}\). The selected indices have total weight \(S/2\). Removing padded zeros and undoing the initial scaling preserves the partition of the original input.
This implication handles repeated routes explicitly and correctly.
Given a partition, the complementary bundles each have exactly \(w\) paths and cost \(T\). Every paired route occurs in exactly one of them, so assigning each bundle mass \(1/4\) gives precisely the required type-\(0\) marginals.
The anchor bundle of mass \(1/2\) gives the type-\(1\) marginals. All positive bundle costs are \(T\) or \(gT\), with \(T>0\), so every ordered envy inequality holds and the envy-ratio is exactly \(g\).
The output contains three bundles with polynomially many binary-encoded multiplicities and constant-size rational masses. The succinct-output requirement is satisfied.
The assertion about preserving loads and social cost follows directly from satisfaction of the prescribed marginal constraints.
The graph and menu counts are correct:
\(\tau=2\), \(m=2(2w+1)\), \(|V|=2w+3\), and \(|E|=2(2w+1)\).
Since \(w<2n\), the explicit construction has polynomial size. The stated bit-length estimate for \(\Delta_w\) correctly accounts for its large magnitude. The subsequent sums, products, and rational quantities also have polynomial bit length.
The dyadic claim is correct: \(w\) is a power of two and \(T\) is integral, so both \(T/w\) and \((w+1)T/w^2\) have power-of-two denominators.
The feasibility equivalence follows from Sections 4 and 5.
The promise-search argument is also sound. Assuming a solver with a uniform polynomial running-time bound on feasible inputs, its execution can be stopped after that bound. On a yes-instance it must return a distribution from which a partition can be extracted. On a no-instance no extracted candidate can pass the partition check, regardless of the solver’s behavior.
This establishes the claimed consequence that a polynomial-time solver on feasibility-promised inputs would imply \(\mathrm{P}=\mathrm{NP}\). The reduction is not promise-preserving on source no-instances; the prover’s explicit cutoff argument correctly addresses that distinction.
The description of the cited result is accurate. The paper’s regrouping algorithm redistributes an aggregate collection of assigned paths, and its proof preserves edge traffic and social cost. It does not impose the individual route-marginal constraints required here. [Theorem 4.1 and Algorithm 1](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2025/pdfs/p923.pdf)
The prover does not apply that theorem to establish feasibility or hardness. It uses it only to explain why the discrete result does not contradict the reduction. No unverified theorem application enters the proof.
No mathematical repair is required. The proved scope is seed-promise insufficiency together with search hardness under an additional feasibility promise. The output does not claim an unconditional separation from polynomial time or strong NP-hardness.
⟨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.