Answer: \(\mathsf{NP}\text{-complete}\)
Theorem 7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAn EFPRIOR allocation always exists and can be found in polynomial time when all agents in P have iden- tical valuations.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite catalogue of indivisible item types G with rational per-capita supplies q, a finite set of valuation and priority types Θ with rational masses μ, all prioritized types sharing valuation vP, and an explicit or queryable family of integral bundles B, find a complete mass allocation y satisfying agent-type mass conservation and item-supply constraints such that every pair of bundles in its support satisfies EF1 and every prioritized supported type weakly prefers its bundle to every non-prioritized supported bundle.
Let \(G\) be a catalogue of \(m\) indivisible item types with per-capita supplies \(q\in\mathbb Q_{\ge0}^{m}\). A society is given by its support: the list \(\Theta\) of \(\tau\) valuation-and-priority types with positive binary-rational masses \(\mu_\theta\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a priority flag; write \(P\subseteq\Theta\) for the prioritized types. The admissible bundles are an explicitly listed finite family \(\mathcal B\subseteq\mathbb Z_{\ge0}^{m}\), containing \(0\), with binary-encoded coordinates; multiple copies of an item type are permitted.
Put \(D=\{0\}\cup\mathcal B\cup\{b-e_g:b\in\mathcal B,\ b_g>0\}\), where \(e_g\) is the unit vector for item type \(g\). Each valuation \(v_\theta:D\to\mathbb Q_{\ge0}\) is explicitly tabulated, normalized by \(v_\theta(0)=0\), and coordinatewise monotone. All types in \(P\) share one valuation \(v_P\). Let \(L\) be the total binary input length.
A complete mass allocation consists of rational numbers \(y_{\theta,b}\ge0\) satisfying \(\sum_{b\in\mathcal B}y_{\theta,b}=\mu_\theta\) for every \(\theta\), and \(\sum_{\theta\in\Theta}\sum_{b\in\mathcal B}b_g y_{\theta,b}=q_g\) for every \(g\).
For every ordered pair \((\theta,b),(\phi,c)\) with \(y_{\theta,b}>0\) and \(y_{\phi,c}>0\), require EF1: either \(c=0\), or some \(g\) with \(c_g>0\) satisfies \(v_\theta(b)\ge v_\theta(c-e_g)\). Additionally, whenever \(\theta\in P\) and \(\phi\notin P\), require \(v_P(b)\ge v_P(c)\). These conditions apply also to different bundles assigned to the same type.
Can such a complete mass allocation be found, or infeasibility decided, in time polynomial in \(m,\tau,|\mathcal B|,L\), or is its existence decision problem NP-hard?
For finite agents with normalized monotone valuations and unrestricted subsets of the available items as bundles, a complete EF1 allocation with no envy from prioritized to non-prioritized agents always exists and is computable in polynomial time when prioritized agents share a valuation. [Discrete result](https://arxiv.org/pdf/2211.16143)
No result settling this exact mass-allocation formulation was located in the literature search.
The existence decision problem is \(\mathsf{NP}\)-complete. Hardness holds even when there is exactly one prioritized type, every bundle coordinate belongs to \(\{0,2\}\), every valuation value belongs to \(\{0,1,2\}\), and all masses and supplies are dyadic rationals.
Consequently, an algorithm that always finds a complete allocation or decides infeasibility in the requested polynomial time would imply \(\mathsf{P}=\mathsf{NP}\).
We reduce from Exact Cover by 3-Sets. Its input consists of a universe \(U\), with \(|U|=3k\), and sets \(S_1,\ldots,S_n\subseteq U\), each of cardinality three. The question is whether some subcollection contains each element of \(U\) exactly once.
We use the standard \(\mathsf{NP}\)-completeness of this problem. For hardness, it suffices to consider instances obtained from perfect three-dimensional matching: take the disjoint union of its three ground sets as \(U\), and replace each allowed triple by its three-element set. Exact covers then correspond precisely to perfect matchings. Perfect three-dimensional matching is \(\mathsf{NP}\)-complete. [Karp, *Reducibility among Combinatorial Problems*](https://doi.org/10.1007/978-1-4684-2001-2_9)
Assume \(n\ge1\). Introduce mutually distinct item types
\[ G=\{a,p_1,\ldots,p_n\}\,\dot\cup\,U. \]
Here \(a\) is an anchor item type and \(p_i\) is private to set \(S_i\). Define bundles
\[ A=2e_a,\qquad L_i=2e_{p_i},\qquad H_i=2e_{p_i}+2\sum_{u\in S_i}e_u, \]
and let
\[ \mathcal B=\{0,A\}\cup\{L_i,H_i:1\le i\le n\}. \]
Choose the smallest integer \(\ell\) such that \(2^\ell>n\), and put \(\delta=2^{-\ell}\). There are types \(\theta_0,\theta_1,\ldots,\theta_n\), with
\[ P=\{\theta_0\},\qquad \mu_{\theta_0}=1-n\delta,\qquad \mu_{\theta_i}=\delta\quad(1\le i\le n). \]
These masses are positive dyadic rationals and sum to one. Set supplies to
\[ q_a=2(1-n\delta),\qquad q_{p_i}=2\delta,\qquad q_u=2\delta\quad(u\in U). \]
Write \(\mathbf1[E]\) for the indicator of a predicate \(E\). Define the following functions on all nonnegative integer vectors, and explicitly tabulate their restrictions to the required domain \(D\):
\[ v_{\theta_0}(d)=\mathbf1[d_a>0], \]
and, for \(1\le i\le n\),
\[ v_{\theta_i}(d)= \max\left\{ \mathbf1[d_a>0],\ \mathbf1[d_{p_i}>0] +\mathbf1\left[d_{p_i}>0\ \wedge\ \sum_{u\in U}d_u>0\right] \right\}. \]
Every predicate appearing here is preserved when coordinates increase. Each indicator is therefore coordinatewise monotone, as are their sum and maximum. Thus the tabulated valuations satisfy the required monotonicity. They are normalized at zero and take values only in \(\{0,1,2\}\).
The following consequences will be used:
For the last assertion, deleting one item leaves the \(p_i\)-coordinate positive, since it initially equals two. It also leaves a positive universe coordinate, since \(H_i\) contains two copies of each of three universe item types. Both indicators in the second argument of the maximum consequently remain one.
There are \(m=n+1+3k\) item types, \(\tau=n+1\) society types, and \(|\mathcal B|=2n+2\) admissible bundles.
Each \(L_i\) has one deletion vector, each \(H_i\) has four, and \(A\) has one. Hence \(|D|\le7n+3\). All vectors and valuation tables can be generated explicitly in polynomial time. Moreover, \(\ell\) is logarithmic in \(n+1\), so all masses and supplies have polynomial encoding length.
The constructed instance satisfies every input hypothesis, including the common-valuation requirement for prioritized types.
Suppose a complete fair mass allocation \(y\) exists.
Only \(A\) contains item type \(a\). Its supply equation gives
\[ \sum_{\theta\in\Theta}y_{\theta,A}=1-n\delta=\mu_{\theta_0}>0. \]
Thus some positive-mass type–bundle pair has target bundle \(A\).
Consider any bundle \(b\) assigned with positive mass to \(\theta_0\). EF1 against this target requires
\[ v_{\theta_0}(b)\ge v_{\theta_0}(A-e_a)=1, \]
because \(a\) is the only item type present in \(A\). Only \(A\) has positive value to \(\theta_0\), so its entire mass receives \(A\):
\[ y_{\theta_0,A}=\mu_{\theta_0}. \]
The anchor supply equation and nonnegativity now imply
\[ y_{\theta_i,A}=0\qquad(1\le i\le n). \]
For any positive-mass pair \((\theta_i,b)\), EF1 against the prioritized pair \((\theta_0,A)\) requires
\[ v_{\theta_i}(b)\ge v_{\theta_i}(A-e_a)=1. \]
The only admissible bundles meeting this inequality are \(A,L_i,H_i\). Since \(\theta_i\) cannot receive \(A\), it follows that
\[ y_{\theta_i,L_i}+y_{\theta_i,H_i}=\delta. \]
If both terms were positive, EF1 would apply from \((\theta_i,L_i)\) to \((\theta_i,H_i)\). But
\[ v_{\theta_i}(L_i)=1 <2=v_{\theta_i}(H_i-e_g) \]
for every item type \(g\) present in \(H_i\). No deletion could satisfy EF1.
Therefore, for each \(i\), exactly one of the following holds:
\[ (y_{\theta_i,L_i},y_{\theta_i,H_i}) =(\delta,0) \quad\text{or}\quad (0,\delta). \]
This is the step that forces a discrete choice despite allowing rational mass allocations.
Let
\[ I=\{i:y_{\theta_i,H_i}=\delta\}. \]
For any \(u\in U\), the allocation uses precisely
\[ 2\delta\,|\{i\in I:u\in S_i\}| \]
units per capita of item type \(u\). Its required supply is \(2\delta\). Since \(\delta>0\), exact conservation implies
\[ |\{i\in I:u\in S_i\}|=1. \]
Thus \(\{S_i:i\in I\}\) is an exact cover.
Conversely, suppose \(I\subseteq\{1,\ldots,n\}\) indexes an exact cover. Assign all prioritized mass to \(A\), and assign each other type entirely according to membership in \(I\):
\[ y_{\theta_0,A}=1-n\delta,\qquad y_{\theta_i,H_i}=\delta\ \text{if }i\in I,\qquad y_{\theta_i,L_i}=\delta\ \text{if }i\notin I, \]
with all other entries zero.
The type-mass equations hold by construction. The anchor and private-item supplies also hold. Each universe element occurs in exactly one selected set, so its supply is exactly \(2\delta\).
It remains to verify all ordered fairness comparisons.
These cases cover every ordered positive-mass pair and establish EF1. The additional priority condition holds because
\[ v_P(A)=1\ge0=v_P(L_i)=v_P(H_i). \]
The allocation is therefore complete and fair. Together with the preceding direction, this proves \(\mathsf{NP}\)-hardness.
A polynomial-size rational witness always exists whenever the instance is feasible.
To prove this, take any feasible allocation and let \(S\) be its positive support. Consider the polytope defined by the mass and supply equations, nonnegativity, and setting all variables outside \(S\) to zero.
This polytope is nonempty. It is bounded because every variable satisfies
\[ 0\le y_{\theta,b}\le\mu_\theta. \]
It therefore has a vertex. The positive support of that vertex is a subset of \(S\), so every fairness comparison it requires was already satisfied by the original allocation. Both EF1 and the priority condition are preserved.
The equality matrix has integer coefficients and at most \(m+\tau\) rows. At a vertex, the columns corresponding to positive variables are linearly independent: otherwise a nonzero dependence would permit sufficiently small positive and negative perturbations preserving all equations and nonnegativity, contradicting extremality.
Consequently, the positive coordinates are determined by a nonsingular square subsystem of order \(r\le m+\tau\). Clear the right-hand-side denominators using their product, whose binary length is at most the total input length \(L\). Cramer’s rule then expresses each coordinate as a ratio of integer determinants. Their binary lengths are bounded by \(O(r(L+\log r))\), using the determinant expansion bound. Thus the allocation has polynomial total encoding length.
Given such a certificate, exact rational arithmetic verifies the mass and supply equations. For every ordered positive-mass pair, checking at most \(m\) deletions verifies EF1, and direct table comparisons verify priority. All these checks take polynomial time.
Hence the decision problem belongs to \(\mathsf{NP}\), completing the proof of \(\mathsf{NP}\)-completeness.
The referenced discrete theorem guarantees a complete allocation when prioritized agents share a valuation and bundles are unrestricted subsets of the available items. [Bu et al., Theorem 3.1](https://arxiv.org/pdf/2211.16143)
Our construction restricts admissible bundles to the explicitly listed \(A,L_i,H_i\) and zero. The discrete theorem does not guarantee an allocation respecting this catalogue. The hardness result therefore does not contradict that theorem.
⟨structured verdict parsed — rendered above⟩
The proof resolves the stated problem: the existence decision problem is \(\mathsf{NP}\)-complete. The reduction and membership argument are correct as written. I found no major or minor mathematical issues requiring repair.
The source problem is stated correctly: Exact Cover by 3-Sets asks whether three-element subsets cover a universe of size \(3k\) exactly once. The stated conversion from perfect three-dimensional matching preserves both directions of feasibility: each allowed triple becomes a three-element subset of the disjoint union of the ground sets. The invoked hardness result is standard and correctly attributed to [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Restricting to \(n\ge1\) does not compromise hardness; empty set lists constitute a trivial source case.
All item coordinates are nonnegative integers, and every admissible bundle coordinate belongs to \(\{0,2\}\). The catalogue includes \(0\). Private coordinates distinguish the bundles even if some source sets coincide.
The choice \(2^\ell>n\) ensures \(0<n\delta<1\). Consequently, every mass is positive, and
\[
(1-n\delta)+n\delta=1.
\]
All specified supplies are nonnegative dyadic rationals. There is exactly one prioritized type, so the common-valuation requirement holds.
The valuation formulas define functions on all nonnegative integer vectors, making their restrictions to \(D\) unambiguous. Every indicator used is coordinatewise monotone; addition and maximum preserve monotonicity. Normalization and the claimed value range \(\{0,1,2\}\) follow directly.
Every type assigns value \(1\) to both \(A\) and \(A-e_a\).
Among admissible bundles, the prioritized type values only \(A\) positively. For each non-prioritized type \(\theta_i\), the positively valued bundles are exactly \(A,L_i,H_i\), with respective values \(1,1,2\). Bundles indexed by another private coordinate have value zero, even when their universe coordinates overlap \(S_i\).
Every permitted deletion from \(H_i\) leaves its private coordinate positive and at least one universe coordinate positive. Therefore,
\[
v_{\theta_i}(H_i-e_g)=2
\]
for every \(g\) with \((H_i)_g>0\). This critical calculation is valid.
The counts
\[
m=n+1+3k,\qquad \tau=n+1,\qquad |\mathcal B|=2n+2
\]
are correct.
Deletion vectors contribute at most \(n+4n+1\) additional domain elements. Since \(0\) already belongs to \(\mathcal B\), this gives
\[
|D|\le(2n+2)+(5n+1)=7n+3.
\]
Possible coincidences only decrease this count.
Explicit coordinate lists and all valuation tables therefore have polynomial size. The binary lengths of the dyadic parameters are also polynomial.
Only \(A\) contains item type \(a\), with coordinate \(2\). Its supply equation consequently gives
\[
\sum_\theta y_{\theta,A}=\mu_{\theta_0}>0.
\]
Thus there is an occupied target pair carrying \(A\).
Against that target, every occupied bundle of \(\theta_0\) must have value at least \(v_{\theta_0}(A-e_a)=1\). There is only one possible deletion item type, and \(A\) is the only admissible bundle satisfying this inequality.
The mass equation therefore forces \(y_{\theta_0,A}=\mu_{\theta_0}\). This exhausts the anchor supply, and nonnegativity forces every other type’s mass on \(A\) to be zero. There is no circularity in this argument.
Comparing an occupied pair of \(\theta_i\) against \((\theta_0,A)\) forces its bundle value to be at least \(1\). The valuation calculation and exhausted anchor supply restrict its support to \(L_i,H_i\).
If both received positive mass, the ordered comparison from \(L_i\) to \(H_i\) would fail every possible deletion test:
\[
v_{\theta_i}(L_i)=1<2=v_{\theta_i}(H_i-e_g).
\]
The task explicitly requires comparisons between distinct bundles assigned to the same type, so this application of EF1 is legitimate.
Combined with the type-mass equation, this establishes exactly the two stated possibilities, each assigning mass \(\delta\) to one bundle.
After the support restrictions, universe item \(u\) receives contributions only from selected \(H_i\) bundles. Its allocated quantity is exactly
\[
2\delta\,|\{i\in I:u\in S_i\}|.
\]
Equality with supply \(2\delta\), together with \(\delta>0\), forces the incidence count to equal \(1\) for every \(u\). This is precisely an exact cover.
The proposed allocation satisfies all mass equations. Anchor and private supplies match directly, and exact cover gives the universe supplies.
The fairness cases exhaust all ordered occupied pairs:
The additional priority inequality holds for every prioritized-to-non-prioritized comparison. Thus the reverse implication establishes complete feasibility, not merely conservation.
Fixing the positive support of an existing feasible allocation leaves a nonempty polytope defined by rational equalities and nonnegativity. The mass equations bound every variable, so the polytope is bounded and has a vertex.
Taking such a vertex introduces no occupied pair outside the original support. Fairness depends only on occupied pairs and tabulated bundle values, so removing support preserves both EF1 and the priority conditions.
The argument for linear independence of positive-variable columns is valid: a nonzero dependence permits sufficiently small perturbations in both directions, preserving positivity on those coordinates and all equalities, contradicting extremality.
Consequently, there are at most \(m+\tau\) positive coordinates, determined by a nonsingular square subsystem. Clearing right-hand-side denominators and applying Cramer’s rule yields the stated polynomial bit bound. The denominator product has polynomial bit length, and determinant expansion gives \(O(r(L+\log r))\) bits per coordinate.
Exact arithmetic verifies conservation and nonnegativity in polynomial time. There are polynomially many ordered occupied pairs, each requiring at most \(m\) deletion comparisons. Certificate verification is therefore polynomial.
The cited theorem concerns finite agents and complete allocations of unrestricted item subsets when prioritized agents have identical valuations. This agrees with [Bu et al., Theorem 3.1 and its model assumptions](https://arxiv.org/pdf/2211.16143).
The reduction uses an explicitly restricted bundle catalogue, so the discrete existence theorem does not imply feasibility for these instances. No contradiction arises.
No repair feedback is necessary. The claimed restricted hardness and general \(\mathsf{NP}\)-membership both stand.
⟨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.