Answer: \(\mathrm{NP}\)-hard
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe Cycle Elimination algorithm satisfies OE, SEF, and 1-LEF. It runs in 𝑂(𝑛3 + 𝑛𝑚+ 𝑛|Σ|) time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite type and item sets \(T\) and \(I\), rational type masses \(\mu_t\), item capacities \(q_j\), complete item rankings \(\pi_t\), and a finite distribution \(\Sigma\) over priority profiles ordering types as exchangeable blocks with atomless internal tie-breaking, compute \(p_{tj}\ge0\) with \(\sum_j p_{tj}=\mu_t\) and \(\sum_t p_{tj}=q_j\), together with a measurable matching lottery inducing it, such that no feasible assignment typewise stochastically dominates it, stochastic priority dominance implies stochastic allocation dominance, and a type placed ahead of another in every profile receives a strictly preferred item almost surely.
A society is given by its support: the list of \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Let \(T\) be this support, \(I\) contain \(m\) item categories, and \(\sum_t\mu_t=\sum_jq_j=1\), with \(q_j>0\) binary rational. Each type has a strict complete ranking \(\pi_t\) of \(I\).
Agents of type \(t\) form \(\{t\}\times[0,1)\), with measure \(\mu_t\,du\); each receives one item category. Input \(\Sigma=\{(\sigma_k,\rho_k)\}_{k=1}^s\) explicitly lists strict orders of the type blocks, with positive binary rational probabilities summing to one.
Define \(b_{kt}=\sum_{v:\sigma_k(v)<\sigma_k(t)}\mu_v\). Exchangeable atomless internal tie-breaking means a representative type-\(t\) agent's priority position has distribution \(S_t=\sum_k\rho_k\operatorname{Unif}[b_{kt},b_{kt}+\mu_t]\); smaller positions are better.
A feasible mass assignment satisfies \(p_{tj}\geq0\), \(\sum_jp_{tj}=\mu_t\), and \(\sum_tp_{tj}=q_j\). Write \(x_t=p_t/\mu_t\) for its per-agent allocation lottery.
Ordinal efficiency means no distinct feasible mass assignment weakly first-order stochastically dominates \(x_t\) under \(\pi_t\) for every type, with strict improvement for at least one type. Stochastic envy-freeness means that whenever \(S_t\) weakly first-order stochastically dominates \(S_v\) toward smaller positions, \(x_t\) weakly first-order stochastically dominates \(x_v\) under \(\pi_t\).
A matching lottery is a jointly measurable map \(f_z(t,u)\in I\), with uniform seed \(z\in[0,1)\), having category masses \(q_j\) almost surely and marginals \(\Pr_z[f_z(t,u)=j]=x_{tj}\) for almost every \(u\). Its finite encoding consists of rational polyhedral regions in \((u,z)\), labelled by items, for each type.
The additional fairness requirement is: for distinct \(t,v\), if \(\sigma_k(t)<\sigma_k(v)\) for every \(k\), then \(\pi_t(f_z(t,u))<\pi_t(f_z(v,w))\) for almost every \((z,u,w)\). Receiving the same category does not satisfy this strict comparison.
Compute an ordinally efficient, stochastically envy-free mass assignment together with such a lottery satisfying the additional requirement, or determine that none exists. Let \(L\) be the total binary input length.
Is this continuous assignment problem solvable in polynomial time in \(m,\tau,s,L\), or is it NP-hard?
For finite agents and distinct unit-capacity items, Cycle Elimination achieves ordinal efficiency, stochastic envy-freeness, and the probability-one strict comparison requirement in \(O(n^3+nm+ns)\) time. [Source](https://arxiv.org/html/2301.13804).
No result settling exactly the atomless problem defined here was located.
The problem is \(\mathrm{NP}\)-hard, already with three item categories and identical preferences for all types. This holds even when every input mass and probability is dyadic.
The proof is a polynomial-time reduction from PARTITION. The strict comparison requirement forces an integral choice at almost every lottery seed; mixing a partition with its complement then provides stochastic envy-freeness.
We use the standard \(\mathrm{NP}\)-complete PARTITION problem: given positive binary integers \(a_1,\ldots,a_n\), decide whether some subset has half their total weight. See [Mertens, *The Easiest Hard Problem: Number Partitioning*](https://arxiv.org/abs/cond-mat/0310317).
We may restrict to instances whose total weight \(W\) is a power of two. Here is an explicit reduction establishing that restriction.
Let the original total be \(A\). If \(A\) is odd, output the fixed NO-instance \((1,3)\), whose total is four. Otherwise, choose a power of two \(W>3A\), and append two copies of the integer \(d=(W-A)/2\). The new total is \(W\).
Any subset of weight \(W/2\) must contain exactly one appended copy: without either copy its weight is at most \(A<W/2\), whereas both copies already weigh \(W-A>W/2\). Its original elements must consequently weigh \(W/2-d=A/2\). Conversely, any original partition extends by adding one copy of \(d\). Choosing the smallest suitable power of two keeps all encodings polynomial.
Henceforth, let \(a_1,\ldots,a_n\) denote the resulting positive integers, with \(n\geq2\) and total \(W\), a power of two.
For each index \(i\), introduce two distinct type blocks \(H_i,L_i\), each with mass
\(\mu_{H_i}=\mu_{L_i}=\alpha_i:=a_i/(2W).\)
Thus \(\sum_i\alpha_i=1/2\), and the total population mass is one.
There are three categories \(a,b,c\), with quotas
\((q_a,q_b,q_c)=(1/4,1/2,1/4).\)
Every type has the strict ranking \(a\succ b\succ c\). Distinct type blocks sharing a ranking are permitted by the stated hypotheses.
For each \(k\in\{1,\ldots,n\}\), define \(\sigma_k\) by listing the pairs cyclically, beginning with pair \(k\), and placing \(H_i\) immediately before \(L_i\) within every pair. For example,
\(\sigma_1:\ H_1,L_1,H_2,L_2,\ldots,H_n,L_n.\)
Choose a power of two \(D\geq n\), and give these orders positive probabilities
\(\rho_k=1/D\) for \(k<n\), and \(\rho_n=(D-n+1)/D\).
These probabilities sum to one.
Two facts about these priorities will be used.
Certain precedence. The only distinct-type comparisons holding in every order are \(H_i\) before \(L_i\). Indeed, two different pairs occur in opposite relative orders in the cyclic orders beginning with their respective indices.
No lower type stochastically dominates any upper type. Write \(F_t(r)=\Pr[S_t\leq r]\), and let \(\delta=\min_i\alpha_i>0\). Every interval contributing to \(S_{L_i}\) begins at least at \(\alpha_i\geq\delta\), because \(H_i\) precedes \(L_i\). Consequently,
\(F_{L_i}(\delta/2)=0.\)
In order \(\sigma_j\), type \(H_j\) comes first, so its priority interval is \([0,\alpha_j]\). Therefore,
\(F_{H_j}(\delta/2)\geq\rho_j\delta/(2\alpha_j)>0.\)
Stochastic dominance toward smaller positions requires the dominating distribution’s CDF to be at least the other’s everywhere. Thus \(S_{L_i}\) cannot dominate \(S_{H_j}\), for any \(i,j\).
Suppose the constructed instance admits a lottery satisfying capacity feasibility and the additional strict comparison requirement. This direction does not need ordinal efficiency or stochastic envy-freeness.
For a seed \(z\), define the realized category masses
\(r_{tj}(z):=\mu_t\int_0^1\mathbf{1}_{\{f_z(t,u)=j\}}\,du.\)
By joint measurability, Fubini’s theorem, and the finitely many required comparisons, there is a full-measure set of seeds on which all category quotas hold and every comparison between \(H_i\) and \(L_i\) holds for almost every \((u,w)\). Fix any such seed and suppress \(z\).
Since \(H_i\) certainly precedes \(L_i\), their received categories must satisfy \(f(H_i,u)\succ f(L_i,w)\) for almost every \((u,w)\). In particular, they cannot both receive \(b\) on sets of positive measure. Explicitly,
\(\displaystyle 0=\int_0^1\int_0^1\mathbf{1}_{\{f(H_i,u)=b=f(L_i,w)\}}\,du\,dw=\frac{r_{H_i b}r_{L_i b}}{\alpha_i^2}.\)
Thus at least one of \(r_{H_i b},r_{L_i b}\) is zero. Each is at most \(\alpha_i\), so
\(r_{H_i b}+r_{L_i b}\leq\alpha_i.\)
Summing these bounds gives exactly the middle-category quota:
\(\displaystyle \sum_i(r_{H_i b}+r_{L_i b})=q_b=\frac12=\sum_i\alpha_i.\)
Every individual bound must therefore be tight. There are only two possibilities for each pair:
| Middle-category recipient | Forced allocation of the pair |
|---|---|
| \(L_i\) receives all its mass in \(b\) | \(H_i\) receives all its mass in \(a\) |
| \(H_i\) receives all its mass in \(b\) | \(L_i\) receives all its mass in \(c\) |
To justify the forced allocations, if \(L_i\) receives \(b\) almost everywhere, the only category strictly better than its allocation is \(a\). Similarly, if \(H_i\) receives \(b\) almost everywhere, the only category strictly worse is \(c\).
Let \(B\) contain the indices realizing the first possibility. The quota for \(a\) now implies
\(\displaystyle \frac14=q_a=\sum_{i\in B}\alpha_i=\frac{1}{2W}\sum_{i\in B}a_i.\)
Hence \(\sum_{i\in B}a_i=W/2\), giving a partition.
This argument applies at almost every seed. In particular, randomizing across seeds cannot rescue a NO-instance.
Conversely, suppose \(B\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in B}a_i=W/2\).
Define a lottery independent of the internal agent coordinate \(u\). For \(0\leq z<1/2\), assign:
For \(1/2\leq z<1\), use the same rule with \(B\) replaced by its complement.
In either half of the seed interval, category \(b\) receives mass \(\sum_i\alpha_i=1/2\). Categories \(a\) and \(c\) each receive mass \(1/4\), because both \(B\) and its complement have weight \(W/2\).
Every pair receives either \((a,b)\) or \((b,c)\), with the better category assigned to \(H_i\). These are precisely the comparisons required by certain precedence.
The lottery is jointly measurable and has a rational polyhedral encoding: for each type, divide the \((u,z)\)-square at the rational line \(z=1/2\), and label the resulting two rectangles. Boundary choices have no effect on any required almost-everywhere property.
Every type \(H_i\) has per-agent lottery
\(x_{H_i}=(1/2,1/2,0),\)
and every type \(L_i\) has per-agent lottery
\(x_{L_i}=(0,1/2,1/2),\)
in category order \(a,b,c\). Set \(p_{tj}=\mu_t x_{tj}\). The capacity calculations above show that this mass assignment is feasible.
Allocations within either layer are identical. Moreover, every upper-layer allocation stochastically dominates every lower-layer allocation under the common ranking: their probabilities of receiving the top category are respectively \(1/2\) and zero, and their probabilities of receiving one of the top two categories are respectively one and \(1/2\).
Section 2 proved that no lower-layer priority distribution dominates an upper-layer one. Thus every priority-dominance implication either compares types within one layer, where their allocations coincide, or compares an upper type to a lower type, where the required allocation dominance holds. This proves stochastic envy-freeness.
Under identical strict rankings, every feasible mass assignment is ordinally efficient. We verify this directly, using efficiency against all feasible assignments.
Let \(p,p'\) be feasible, and suppose \(p'_t/\mu_t\) weakly stochastically dominates \(p_t/\mu_t\) for every type. For the common top-\(r\) category set \(A_r\), define
\(\Delta_{tr}:=\sum_{j\in A_r}(p'_{tj}-p_{tj}).\)
Stochastic dominance and \(\mu_t>0\) imply \(\Delta_{tr}\geq0\). Feasibility gives
\(\displaystyle \sum_t\Delta_{tr}=\sum_{j\in A_r}\left(\sum_t p'_{tj}-\sum_t p_{tj}\right)=0.\)
A finite sum of nonnegative numbers is zero only when every summand is zero. Therefore every type’s prefix masses coincide under \(p\) and \(p'\). Taking differences of consecutive prefixes shows \(p'_{tj}=p_{tj}\) for every type and category.
No distinct feasible assignment can dominate \(p\), proving ordinal efficiency and, in particular, efficiency of the assignment constructed above.
The construction has \(m=3\), \(\tau=2n\), and \(s=n\). It explicitly lists only polynomially many priority-order entries. All numerical encodings have polynomial length; because \(W\) and \(D\) are powers of two, all masses and probabilities are dyadic.
We have proved the exact equivalence:
\(\text{the PARTITION instance is YES}\quad\Longleftrightarrow\quad\text{the constructed assignment instance admits the requested output}.\)
Thus even deciding existence is \(\mathrm{NP}\)-hard. An algorithm that computes the requested assignment and lottery or correctly reports nonexistence in time polynomial in \(m,\tau,s,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
This does not contradict the [finite-agent Cycle Elimination result](https://arxiv.org/html/2301.13804): that theorem compares distinct individual items. Here, receiving the same category is explicitly excluded from satisfying the strict comparison, and that exclusion produces the integral choices in Section 3.
⟨structured verdict parsed — rendered above⟩
The prover resolves the target: the reduction establishes \(\mathrm{NP}\)-hardness of deciding existence, already with three categories, identical preferences, and dyadic numerical inputs. I found no major or minor mathematical issues.
The source problem is correctly specified: PARTITION on positive binary integers asks whether a subset has exactly half the total weight. Its standard hardness applies to this encoding; the cited [Mertens paper](https://arxiv.org/pdf/cond-mat/0310317) discusses integer number partitioning and its dependence on binary precision.
The restriction to power-of-two totals is valid.
Selecting the smallest power of two exceeding \(3A\) requires only polynomially many bits. The resulting instances have at least two positive entries, including in the fixed NO branch. There is no omitted exceptional case affecting the reduction.
Every mass \(\alpha_i=a_i/(2W)\) is positive, and the population normalization is correct:
\( \sum_i(\mu_{H_i}+\mu_{L_i})=2\sum_i\alpha_i=1. \)
The quotas are positive and sum to one. Since \(W\) is a power of two, all masses are dyadic.
The probabilities are also valid. With \(D\geq n\), every probability is positive, including \(\rho_n=(D-n+1)/D\), and
\( \sum_{k=1}^{n}\rho_k=((n-1)+(D-n+1))/D=1. \)
All orders are strict complete orders of the explicitly listed type blocks. The task does not require distinct blocks to have distinct preference rankings, so the use of identical preferences is admissible.
Certain precedence. Every order puts \(H_i\) immediately before \(L_i\). For different pairs \(i,j\), the order starting with pair \(i\) places both members of pair \(i\) before both members of pair \(j\), whereas the order starting with pair \(j\) reverses that relation. Thus the only required distinct-type comparisons are exactly those from \(H_i\) to \(L_i\).
Exclusion of lower-to-upper stochastic dominance. The CDF calculation is correct. Every interval for \(L_i\) begins at least at \(\alpha_i\), so, for \(\delta=\min_i\alpha_i>0\),
\( F_{L_i}(\delta/2)=0. \)
The order starting with pair \(j\) contributes a positive-probability uniform interval \([0,\alpha_j]\) to \(S_{H_j}\). Since \(0<\delta/2<\alpha_j\),
\( F_{H_j}(\delta/2)\geq \rho_j\delta/(2\alpha_j)>0. \)
Dominance toward smaller positions requires the dominating CDF to be everywhere at least the dominated CDF. This single threshold therefore excludes \(S_{L_i}\) dominating \(S_{H_j}\), for every \(i,j\). Unequal order probabilities do not invalidate this argument.
The measure-theoretic quantifiers are handled correctly. Joint measurability makes the violation indicators measurable and integrable. Fubini’s theorem converts each almost-everywhere condition in \((z,u,w)\) into an almost-everywhere condition in \((u,w)\) for almost every seed. There are finitely many required comparisons, so their good-seed sets and the capacity-feasibility set have a common full-measure intersection.
At any seed in that intersection, strict comparison excludes simultaneous positive-measure allocation of \(b\) to both members of a pair. The displayed factorization
\( r_{H_i b}r_{L_i b}/\alpha_i^2=0 \)
is correct: the two indicators depend separately on \(u\) and \(w\). As both realized masses lie in \([0,\alpha_i]\), their sum is at most \(\alpha_i\).
The saturation argument is valid. The sum of these pairwise upper bounds equals the required total \(b\)-mass. Consequently, every pair attains its bound. Together with the zero-product condition, this forces exactly one member to receive its entire mass in \(b\).
The two remaining allocations are correctly forced by strict comparison:
These conclusions use the full pairwise almost-everywhere comparison, not merely a comparison of expected allocations.
The quota for \(a\) then gives precisely
\( \sum_{i\in B}a_i=W/2. \)
Thus existence of the required lottery implies a YES-instance of PARTITION. No efficiency or envy-freeness assumption is needed in this direction, and randomization cannot evade the obstruction.
The two-seed-region construction satisfies capacities. In either region, the total mass receiving \(b\) is \(\sum_i\alpha_i=1/2\); the selected subset and its complement each have mass \(1/4\), supplying the quotas for \(a\) and \(c\).
Each required comparison receives either \((a,b)\) or \((b,c)\), with the better category assigned to \(H_i\). Section 2 has already excluded any additional certain-precedence comparisons.
The lottery is independent of \(u\), so its marginals hold for every internal coordinate. Its two rectangular regions per type have rational boundaries and give the required finite polyhedral encoding. Boundary conventions do not affect any almost-everywhere condition.
The marginal lotteries are correctly calculated:
\( x_{H_i}=(1/2,1/2,0),\qquad x_{L_i}=(0,1/2,1/2). \)
Multiplication by the positive masses produces a feasible mass assignment.
The proof covers every possible priority-dominance implication:
There is no need to characterize the remaining priority comparisons more precisely. The argument establishes stochastic envy-freeness exactly as defined in the task.
The efficiency proof is correct and considers all feasible competing assignments.
For every common preference prefix, typewise stochastic dominance makes each mass difference \(\Delta_{tr}\) nonnegative. Multiplication by \(\mu_t>0\) preserves the per-agent dominance inequality. Category feasibility makes the sum of these differences zero.
Since there are finitely many types, every \(\Delta_{tr}\) must therefore vanish. Equality of all consecutive prefix masses implies equality of every category mass. Hence a dominating feasible assignment must equal the original assignment, excluding any distinct improvement.
This proves the claimed statement that every feasible assignment under identical strict rankings is ordinally efficient.
The construction explicitly uses \(m=3\), \(\tau=2n\), and \(s=n\). Listing the orders takes polynomial space, and all numerical bit lengths remain polynomial. The YES construction itself has a constant number of rational regions per type.
Both directions of the existence equivalence are established. Therefore a polynomial-time algorithm producing the requested output or correctly reporting nonexistence would decide PARTITION in polynomial time.
The reduction proves ordinary \(\mathrm{NP}\)-hardness; it does not claim strong hardness or membership of the general existence problem in \(\mathrm{NP}\).
The final comparison with the [finite-agent paper](https://arxiv.org/html/2301.13804) is consistent with its distinct-item setting and is not used as a premise of the reduction.
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.