Answer: NP-hard, even for one type with a strict ranking; NP-complete when the allowed bundles are explicitly listed.
Theorem 11(i) — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe following problems are NP-complete: (i) check whether there exists a weak SD envy-free (equivalently possible com- pletion envy-free) discrete assignment, (ii) check whether there exists a possible envy-free discrete assignment, and (iii) check whether there exists an SD envy-free discrete assignment.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite object kinds \(O\), a finite set of ranking types \(T\), rational type masses \(\mu_t\), rational per-capita supplies \(\rho_o\), and a finite family of integral bundles \(\mathcal{B}\), decide whether there exist masses \(x_{t,B}\ge 0\) satisfying \(\sum_{B\in\mathcal{B}}x_{t,B}=\mu_t\) and \(\sum_{t\in T}\sum_{B\in\mathcal{B}}B_o x_{t,B}=\rho_o\) for every \(o\), such that whenever \(x_{t,B}>0\), no bundle \(C\) with positive aggregate mass is strictly SD-preferred to \(B\) by type \(t\); if so, output \(x\).
Definitions. Each type \(t\in T\) has a complete ordinal ranking \(\succeq_t\) of object kinds \(O\). For bundles \(B,C\in\mathbb{Z}_{\ge0}^{O}\), write \(C\succ_t^{SD}B\) if, for every rank cutoff of \(\succeq_t\), \(C\) contains at least as many objects above that cutoff as \(B\), and strictly more for some cutoff.
An instance gives rational masses \(\mu_t\), supplies \(\rho_o\), and allowed integral bundles \(\mathcal{B}\). A feasible allocation is \(x_{t,B}\ge0\) with \(\sum_{B\in\mathcal{B}}x_{t,B}=\mu_t\) and \(\sum_{t\in T}\sum_{B\in\mathcal{B}}B_o x_{t,B}=\rho_o\). Let \(y_C=\sum_{t\in T}x_{t,C}\). It is weakly SD envy-free if \(x_{t,B}>0\) implies that no \(C\in\mathcal{B}\) with \(y_C>0\) satisfies \(C\succ_t^{SD}B\).
Target. Is deciding whether such a weakly SD envy-free feasible allocation exists (and computing one when it does) polynomial-time solvable, or NP-hard?
Nearest known results. For finite-agent allocations of indivisible objects with ordinal preferences, deciding whether a weakly SD envy-free discrete allocation exists is NP-complete, including when ties are allowed.
Result. The problem is NP-hard, even with one type, a strict ranking, and an explicitly listed family of bundles. With explicitly listed bundles, the decision problem is NP-complete.
The proof below uses divisible allocation masses throughout.
1. Encoding stochastic dominance by coordinatewise order. Let \(V\subseteq\{-2,-1,0,1,2\}^{D}\), and let \(z\in[-2,2]^D\) be rational. Consider the following auxiliary problem: find weights \(\lambda_v\geq 0\) such that \(\sum_{v\in V}\lambda_v=1\), \(\sum_{v\in V}\lambda_vv=z\), and the positive-weight vectors form an antichain under coordinatewise order.
Here, an antichain means that no two distinct vectors \(v,w\) in the support satisfy \(v_k\leq w_k\) for every coordinate \(k\).
This problem can be encoded as the allocation problem with one type of mass \(1\). Introduce objects ranked strictly as \(o_1\succ o_2\succ\cdots\succ o_D\). For each \(v\in V\), define an integral bundle \(B(v)\) by
\(B(v)_{o_1}=4+v_1,\qquad B(v)_{o_k}=4+v_k-v_{k-1}\quad(2\leq k\leq D).\)
Every entry is nonnegative because the coordinates of \(v\) lie between \(-2\) and \(2\). Its cumulative counts are
\(\sum_{i=1}^{k}B(v)_{o_i}=4k+v_k.\)
Consequently, \(B(w)\succ^{SD}B(v)\) holds exactly when \(w\geq v\) coordinatewise and \(w\neq v\).
Set the supplies to
\(\rho_{o_1}=4+z_1,\qquad \rho_{o_k}=4+z_k-z_{k-1}\quad(2\leq k\leq D).\)
These supplies are rational and nonnegative. For weights summing to \(1\), the supply equations are equivalent to \(\sum_v\lambda_vv=z\): this follows by summing the supply equations over each initial segment of the ranking, and conversely by taking consecutive differences.
Because there is only one type, weak SD envy-freeness is exactly the requirement that the positive-weight vectors form an antichain. Thus it suffices to prove NP-hardness of the auxiliary problem.
2. Construction from satisfiability. Start with a 3-CNF formula with variables \(X_1,\ldots,X_n\) and clauses \(C_1,\ldots,C_m\), where \(n,m\geq1\). Treat all three literal occurrences in each clause as distinct, including repeated literals.
Let \(U=\{u_{i,b}:1\leq i\leq n,\ b\in\{0,1\}\}\) contain the two assignment choices for each variable. Let \(W\) contain the \(3m\) literal occurrences. For an occurrence \(w\), let \(\operatorname{bad}(w)\in U\) denote the unique assignment choice that makes that occurrence false.
There are \(g=n+m\) groups: one for each variable and one for each clause. Write \(\delta_r\) for the \(r\)-th standard basis vector of \(\mathbb{R}^g\), and \(\mathbf{1}_g\) for its all-ones vector.
Use another coordinate block indexed by \(U\cup W\cup\{*\}\), of dimension \(d=2n+3m+1\). Denote its standard basis vectors by \(e_k\).
The complete vectors have five blocks:
\((h,G,E,s_1,s_2)\in\mathbb{R}\times\mathbb{R}^{g}\times\mathbb{R}^{d}\times\mathbb{R}\times\mathbb{R}.\)
Define the following choice vectors:
\(v_{i,b}=(0,\delta_i,e_{u_{i,b}}-e_*,0,0)\).
\(v_w=(1,\mathbf{1}_g+\delta_{n+j},e_{\operatorname{bad}(w)}+e_w,0,0)\).
Also introduce auxiliary vectors
\(f_0=(0,0_g,0_d,1,-1)\)
and, for every \(k\in U\cup W\),
\(f_k=(0,0_g,2e_*-2e_k,1,-1).\)
All coordinates belong to \(\{-2,-1,0,1,2\}\). Let \(V\) consist of all these vectors.
Finally, put
\(a=\dfrac{1}{2g},\qquad H=ma,\qquad z=\left(H,(a+H)\mathbf{1}_g,2He_*,\dfrac12,-\dfrac12\right).\)
The construction has polynomial size, and \(z\in[-2,2]^{g+d+3}\).
3. Exact comparability relations. We now verify every possible kind of comparison between distinct vectors.
Two assignment vectors are incomparable: at their respective \(U\)-coordinates, each has a \(1\) where the other has a \(0\).
Two occurrence vectors are incomparable: at their respective \(W\)-coordinates, each has a \(1\) where the other has a \(0\).
An occurrence vector cannot be coordinatewise below an assignment vector, because its \(h\)-coordinate is \(1\), whereas an assignment vector has \(h=0\).
For an assignment vector \(v_{i,b}\) and an occurrence vector \(v_w\),
\(v_{i,b}\leq v_w\quad\Longleftrightarrow\quad u_{i,b}=\operatorname{bad}(w).\)
Indeed, if the two assignment labels differ, the \(u_{i,b}\)-coordinate is \(1\) in \(v_{i,b}\) and \(0\) in \(v_w\), preventing the comparison. If the labels agree, the comparison holds in every block:
Every auxiliary vector is incomparable with every choice vector. In the final two coordinates, auxiliary vectors have \((1,-1)\), while choice vectors have \((0,0)\), preventing either direction of comparison.
Finally, distinct auxiliary vectors are incomparable. Their embedding blocks are distinct and all have coordinate sum \(0\). If two distinct such blocks were coordinatewise ordered, their coordinate sums would be strictly ordered, a contradiction.
Therefore, the only comparabilities are between a clause occurrence and the assignment choice that makes it false.
4. A satisfying assignment gives a feasible antichain mixture. Suppose the formula is satisfiable. Select the assignment vector corresponding to each variable’s value, and select one true occurrence from each clause. Give each of these \(g\) vectors weight \(a\), for total choice-vector weight \(ga=1/2\).
By the comparison analysis, the selected choice vectors form an antichain.
Their weighted \(h\)-coordinate is \(ma=H\). Their weighted group block is
\(a\mathbf{1}_g+ma\mathbf{1}_g=(a+H)\mathbf{1}_g,\)
because precisely one selected vector belongs to each group, and each selected occurrence vector contributes an additional \(\mathbf{1}_g\).
Let \(q\) be their weighted embedding block. For every \(k\in U\cup W\), we have \(q_k\geq0\). Moreover,
\(\sum_{k\in U\cup W}q_k=(n+2m)a,\qquad q_*=-na.\)
The first equality holds because every selected assignment vector contributes one positive unit to these coordinates, while every selected occurrence vector contributes two.
Give auxiliary vector \(f_k\) weight \(q_k/2\), and give \(f_0\) the remaining weight
\(\dfrac12-\dfrac12\sum_{k\in U\cup W}q_k =\dfrac12-\dfrac{n+2m}{4(n+m)} =\dfrac{n}{4(n+m)}\geq0.\)
Thus the total auxiliary weight is \(1/2\). The resulting embedding block is
\(q+\sum_{k\in U\cup W}\dfrac{q_k}{2}(2e_*-2e_k) =\left(q_*+\sum_{k\in U\cup W}q_k\right)e_* =2mae_*=2He_*.\)
The auxiliary vectors leave the \(h\)- and group blocks unchanged and contribute \((1/2,-1/2)\) to the final two coordinates. The complete weighted mean is therefore exactly \(z\).
All auxiliary vectors are mutually incomparable and incomparable with all choice vectors. Hence the complete positive-weight support is an antichain.
5. A feasible antichain mixture gives a satisfying assignment. Conversely, suppose weights \(\lambda\) form an antichain mixture with mean \(z\).
The \(s_1\)-coordinate implies that the total auxiliary weight is \(1/2\). The \(h\)-coordinate implies that the total occurrence-vector weight is \(H\).
For each group \(r\), let \(R_r\) be the total weight of its choice vectors. The mean of group coordinate \(r\) is exactly \(R_r+H\): choice vectors in that group contribute their group indicator, every occurrence vector contributes the common additional \(1\), and auxiliary vectors contribute \(0\).
Since the target value is \(a+H\), we obtain \(R_r=a>0\) for every group.
Thus every variable has at least one positive-weight assignment choice, and every clause has at least one positive-weight occurrence. Choose any positive-weight assignment choice for each variable.
Consider a clause and any positive-weight occurrence \(w\) in it. Its false assignment choice \(\operatorname{bad}(w)\) cannot have positive weight, since its vector is comparable with \(v_w\). The variable appearing in \(w\) nevertheless has a positive-weight assignment choice. Therefore its chosen value makes \(w\) true.
Every clause consequently has a true occurrence, so the selected assignment satisfies the formula.
Combining this implication with the preceding construction proves the equivalence between satisfiability and existence of the required antichain mixture. Section 1 then gives the claimed polynomial reduction to weakly SD envy-free allocation.
6. Membership in NP and the computational conclusion. Assume that the allowed bundles are explicitly listed, with binary-encoded integer entries, and that masses and supplies are binary-encoded rationals.
Given an allocation certificate, feasibility is checked by rational arithmetic. Its envy condition is checked by examining every positive allocation entry \(x_{t,B}\) and every used bundle \(C\), and comparing cumulative counts at the rank cutoffs of type \(t\). There are polynomially many such comparisons.
It remains to justify a certificate of polynomial bit length. Suppose a feasible envy-free allocation exists, and restrict allocation variables to its positive support. The resulting feasibility system is \(Ax=b,\ x\geq0\), with rational input data.
Choose a feasible solution with the fewest positive entries. Its positive-support columns of \(A\) must be linearly independent. Otherwise, a nonzero linear dependence gives a direction preserving all equalities; choosing its sign and moving until the first positive coordinate becomes zero produces a feasible solution with smaller support.
For these independent columns, select an invertible square submatrix of rows. The positive entries are its unique solution. After clearing denominators, Cramer’s rule and determinant bounds show that their bit lengths are polynomial in the input length.
This rational solution uses a subset of the original support. Deleting supported allocation entries cannot introduce envy: every remaining assigned bundle and every remaining used bundle was already present. Thus a polynomial-length certificate exists.
The explicitly listed problem is therefore NP-complete. A polynomial-time algorithm that decides existence and constructs an allocation when one exists would imply \(\mathrm{P}=\mathrm{NP}\). If the bundle family is represented implicitly, the reduction still establishes NP-hardness for representations that can encode these lists efficiently; NP membership would require specifying that representation.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the target: existence is NP-hard even with one type and a strict ranking, and is NP-complete for explicitly listed bundles. The reduction uses divisible masses throughout. I found no substantive gaps or internal inconsistencies.
The encoding is valid.
Thus dominance at every rank cutoff is exactly coordinatewise comparison of the underlying vectors. Distinct vectors differ at some coordinate, so coordinatewise comparison between distinct vectors gives strict dominance at some cutoff. The map from vectors to bundles is also injective, because cumulative counts recover every coordinate.
The supply construction is nonnegative under the stated bound \(z\in[-2,2]^D\). With total mass \(1\), the cumulative supply equations are precisely the mean equations for \(z\); consecutive differences give the converse.
For one type, a bundle is used exactly when that type assigns it positive weight. Consequently, the envy condition excludes exactly the comparable pairs in the positive support. This establishes the claimed equivalence with antichain mixtures.
All blocks and indices are well-defined. In particular, assignment labels, occurrence labels, and the special label \(*\) are disjoint. Treating repeated literal occurrences as distinct ensures that distinct occurrence vectors have distinct occurrence coordinates.
The dimension is \(g+d+3\), and the number of vectors is \(4n+6m+1\). Both are linear in the formula size. Explicitly writing all coordinates therefore takes polynomial space.
Every vector coordinate lies in the specified set:
The target is also within the required range. Since \(n,m\geq1\), we have \(0<H<1/2\), \(0<2H<1\), and
\(a+H=(m+1)/(2(n+m))\leq1/2\).
The other target coordinates are \(0\), \(1/2\), or \(-1/2\). All rationals have polynomial encoding length.
The source problem is ordinary satisfiability of formulas with three literal occurrences per clause. Allowing repeated literals and restricting to nonempty instances does not invalidate its standard NP-hardness.
The case analysis is exhaustive and correct.
Two assignment vectors. Their distinct assignment coordinates witness failure of comparison in both directions. Their common negative \(*\)-coordinate does not affect this.
Two occurrence vectors. Each has its own occurrence coordinate equal to \(1\), while the other has \(0\) there. This remains true for repeated literals and for occurrences with the same false assignment choice.
An occurrence below an assignment. The \(h\)-coordinate prevents this.
An assignment below an occurrence. If its label differs from \(\operatorname{bad}(w)\), its assignment coordinate prevents comparison. If the labels agree, every block satisfies the required inequality, including the special coordinate, where \(-1\leq0\). Hence the stated equivalence holds.
An auxiliary vector and a choice vector. Their final coordinates prevent both comparison directions.
Two auxiliary vectors. Their embedding blocks are distinct and all have coordinate sum zero. Coordinatewise comparison between distinct finite vectors would strictly increase the coordinate sum, so comparison is impossible. This argument includes comparisons involving \(f_0\).
Therefore the only comparable distinct pairs are exactly the intended incompatibilities between an occurrence and the assignment choice making it false.
The selected choice vectors have total weight \(ga=1/2\). No selected occurrence is false under a selected assignment choice, so the comparability analysis establishes that their support is an antichain.
The \(h\)-coordinate and group-block calculations are correct: there are \(m\) selected occurrences, and exactly one selected choice vector contributes the individual indicator for each group.
For the embedding block, the claimed identities correctly count contributions:
\(\sum_{k\in U\cup W}q_k=(n+2m)a\) and \(q_*=-na\).
Every ordinary embedding coordinate is nonnegative.
All assigned auxiliary weights are nonnegative. The residual weight is correctly computed as
\(1/2-(n+2m)/(4(n+m))=n/(4(n+m))\).
Thus the auxiliary weights total exactly \(1/2\), and all weights together total \(1\).
The auxiliary contribution cancels every ordinary embedding coordinate. The remaining special coordinate is
\(-na+(n+2m)a=2ma=2H\).
The other blocks receive exactly the stated contributions.
Finally, adding auxiliary vectors cannot introduce comparable pairs. The constructed mixture therefore satisfies both the mean requirement and the antichain requirement.
The converse correctly handles arbitrary fractional weights; it does not assume integral or uniquely selected choices.
The final coordinate fixes total auxiliary weight at \(1/2\), and the \(h\)-coordinate fixes total occurrence weight at \(H\). For each group, its coordinate receives the group’s choice weight plus the common occurrence contribution \(H\). Therefore \(R_r=a>0\) for every group.
This guarantees a positive assignment choice for every variable and a positive occurrence for every clause.
For any positive occurrence, antichain support excludes its unique false assignment choice. Its variable still has a positive assignment choice, which must therefore make the occurrence true. This reasoning applies to any selection of one positive assignment choice per variable, so the selected choices constitute a single assignment satisfying every clause.
The argument also handles repeated literals and clauses containing both signs of a variable. No assumption of distinct variables within clauses is used.
The forward and reverse implications establish the required equivalence.
Under the stated explicit encoding, verification uses polynomially many rational-arithmetic operations and dominance comparisons. Ties cause no difficulty: comparisons use the cumulative counts at the ranking’s cutoffs.
The polynomial certificate argument is sound.
The restricted feasibility system is nonempty by hypothesis. Among its feasible solutions, a minimum positive-support size exists because there are finitely many variables.
If the corresponding columns were dependent, a nonzero null direction supported on those columns would preserve the equalities. Choosing its sign and moving to the first coordinate reaching zero preserves nonnegativity and reduces support, contradicting minimality. Thus those columns are independent.
An invertible square row submatrix consequently exists, and its unique solution determines the positive coordinates. Clearing denominators and applying Cramer’s rule and determinant bounds gives polynomial bit length for rational input of polynomial size. These are routine linear-algebra and bit-complexity facts, and their required hypotheses are present.
Crucially, the new solution uses only entries from the original envy-free support. Every remaining assigned bundle and used bundle was present before, so no new envy pair can arise. This justifies retaining envy-freeness after changing the weights.
The proof establishes NP-completeness for explicit bundle lists and NP-hardness already under the claimed one-type, strict-ranking restriction. This settles the requested complexity alternative. The statement about a polynomial-time algorithm that both decides existence and constructs an allocation follows from the decision hardness.
The qualification concerning implicit representations is appropriate: no unsupported NP-membership claim is made for unspecified encodings.
No repair or additional 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.