Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateDeciding whether a complete envy-free alloca- tion exists is NP-complete for an instance with 3 agents.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite category set \(J\), three strict ranking types \(A,B,C\) of mass \(1/3\), and supply \(1/3\) of each category, decide whether bundle masses \(\lambda_{t,S}\) can exhaust every type's mass and category's supply, with each person receiving an integral bundle \(S\subseteq J\) containing at most one copy of each category, such that no positively represented bundle is envied under the paper's responsive set extension.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible rankings. Here \(T=\{A,B,C\}\), \(\tau=3\), each type has mass \(1/3\), and total population mass is \(1\).
Let \(J\) be a nonempty set of \(m\) categories, each with supply \(1/3\); each type \(t\) has a strict ranking \(\succ_t\) over \(J\). A person receives a bundle \(S\subseteq J\), with at most one copy of each category.
Define \(S\succeq_t^{RS}R\) when there is an injection \(f:R\to S\) satisfying \(f(j)=j\) or \(f(j)\succ_t j\) for every \(j\in R\).
A feasible allocation consists of real masses \(\lambda_{t,S}\geq0\) satisfying \(\sum_{S\subseteq J}\lambda_{t,S}=1/3\) for every \(t\), and \(\sum_{t\in T}\sum_{S\ni j}\lambda_{t,S}=1/3\) for every \(j\in J\).
Require \(S\succeq_t^{RS}R\) whenever \(\lambda_{t,S}>0\) and \(\lambda_{u,R}>0\), for all \(t,u\in T\), including \(t=u\). Thus every represented person's bundle must dominate every other represented bundle from that person's perspective.
Is deciding whether such an allocation exists in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), support size \(\tau=3\), and total binary input length \(L\).
For three discrete agents with strict item rankings, deciding whether a complete responsive-set envy-free allocation exists is NP-complete; the later [journal treatment](https://real.mtak.hu/187117/1/1-s2.0-S0165489623000677-main.pdf) also establishes this for every fixed number of agents at least three.
No complexity classification for precisely the mass-and-integral-bundle problem above was located.
The problem is \(\mathrm{NP}\)-complete, already with support size \(\tau=3\) and all masses and supplies equal to \(1/3\).
The decisive condition is that envy-freeness also applies within each type. Under strict rankings, this forces each type to receive a single bundle. The resulting problem is exactly complete responsive-set envy-free allocation among three discrete agents.
Fix a type \(t\). Write its ranking as \(j_1\succ_t\cdots\succ_t j_m\), and define its prefix sets by \(P_t(k)=\{j_1,\ldots,j_k\}\), with \(P_t(0)=\varnothing\).
Lemma. For any bundles \(S,R\subseteq J\), responsive-set dominance \(S\succeq_t^{RS}R\) holds if and only if
\(\lvert S\cap P_t(k)\rvert\geq\lvert R\cap P_t(k)\rvert\) for every \(k\in\{1,\ldots,m\}\).
Proof. Suppose the required injection \(f:R\to S\) exists. If \(j\in R\cap P_t(k)\), then \(f(j)\) is either \(j\) or a better category, so it also belongs to \(P_t(k)\). Restricting the injection therefore proves the prefix inequality.
Conversely, assume all prefix inequalities. List the elements of \(R\) from best to worst as \(r_1,\ldots,r_q\), and those of \(S\) as \(s_1,\ldots,s_p\). The inequality at \(k=m\) gives \(p\geq q\). For each \(i\leq q\), let \(k_i\) be the position of \(r_i\) in the ranking. Exactly \(i\) elements of \(R\) belong to \(P_t(k_i)\), so at least \(i\) elements of \(S\) belong to that prefix. Consequently, \(s_i\) is at least as good as \(r_i\). Thus \(f(r_i)=s_i\) is a valid injection. When \(R=\varnothing\), the empty injection suffices. This proves the lemma.
In particular, if both \(S\succeq_t^{RS}R\) and \(R\succeq_t^{RS}S\) hold, their prefix counts are equal for every \(k\). Membership of \(j_k\) is the difference between the counts at \(k\) and \(k-1\). Hence every category has the same membership in both bundles, and \(S=R\).
Suppose an allocation satisfies the requirements. For a fixed type \(t\), take any bundles \(S,R\) with \(\lambda_{t,S}>0\) and \(\lambda_{t,R}>0\).
Applying the envy condition with \(u=t\), in both ordered directions, gives \(S\succeq_t^{RS}R\) and \(R\succeq_t^{RS}S\). Section 1 therefore gives \(S=R\).
Since the masses of type \(t\) sum to \(1/3>0\), there is exactly one positively represented bundle, denoted \(S_t\), and its mass is \(\lambda_{t,S_t}=1/3\).
For each category \(j\), the supply equation now becomes
\(\frac13\sum_{t\in T}\mathbf{1}_{\{j\in S_t\}}=\frac13\).
Thus exactly one of \(S_A,S_B,S_C\) contains \(j\). These bundles partition \(J\).
The remaining envy conditions are precisely \(S_t\succeq_t^{RS}S_u\) for every ordered pair of types \(t,u\).
Conversely, given a partition \(J=S_A\mathbin{\dot\cup}S_B\mathbin{\dot\cup}S_C\) satisfying these dominance conditions, set \(\lambda_{t,S_t}=1/3\) and all other masses to zero. Each type then has its prescribed mass, each category has supply \(1/3\), and every required envy comparison holds.
We have therefore proved an exact equivalence:
A required mass allocation exists if and only if a complete responsive-set envy-free allocation exists for the three discrete agents with the same rankings.
As an additional necessary condition, all three bundles have equal cardinality: dominance in each direction implies both cardinality inequalities. Consequently, feasibility requires \(m\) to be divisible by \(3\).
Theorem 1 of Aziz, Schlotter, and Walsh establishes \(\mathrm{NP}\)-completeness of complete necessary envy-free allocation for exactly three agents with strict item rankings. Its fairness requirement is the responsive-set injection condition. [Journal treatment, Sections 2–3](https://real.mtak.hu/187117/1/1-s2.0-S0165489623000677-main.pdf).
Map such an instance to the present problem by retaining its categories and rankings and assigning every type mass \(1/3\) and every category supply \(1/3\). Section 2 proves that this transformation preserves the answer in both directions.
All hypotheses match: allocations are complete, bundles contain no repeated category, and rankings are strict. Between distinct discrete agents, bundles are disjoint, so allowing an injection to map a category to itself does not change their envy comparisons. Self-comparisons in the target hold by the identity injection.
Moreover, the cited hardness construction gives the three agents different top categories in its initial block. Its rankings are therefore distinct, so the reduction uses exactly three supported preference types even when types are identified by their rankings. [Journal treatment, Section 3, initial block](https://real.mtak.hu/187117/1/1-s2.0-S0165489623000677-main.pdf).
The transformation copies the rankings and appends rational constants, taking \(O(L)\) time and preserving \(m\). This proves \(\mathrm{NP}\)-hardness.
For membership in \(\mathrm{NP}\), a certificate assigns each category to one of the three types. It has \(O(m\log\tau)=O(m)\) bits. It specifies a partition, and the lemma verifies every required dominance relation by checking prefix counts. Section 2 then supplies a valid mass allocation. Thus arbitrary real masses require no additional certificate.
With categories indexed and using standard word-RAM operations:
The verifier also has polynomial bit complexity in \(L\); for fixed \(\tau=3\), a straightforward implementation using sequential scans takes \(O(L^2)\) bit operations.
Therefore the requested classification is \(\mathrm{NP}\)-complete. A polynomial-time decision algorithm exists if and only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument correctly reduces the mass allocation problem to complete responsive-set envy-free allocation for three discrete agents. The cited theorem applies, and the claimed certificate and running times are valid. I found no major or minor mathematical issues.
The forward implication is correct: an injection witnessing \(S\succeq_t^{RS}R\) sends every element of \(R\cap P_t(k)\) into \(S\cap P_t(k)\). Its restriction remains injective, establishing the required count inequality.
The converse is also correct. The inequality at \(k=m\) guarantees \(p\geq q\), so every \(s_i\) used in the proposed injection exists. Strict rankings ensure that exactly \(i\) elements of \(R\) occur in the prefix ending at \(r_i\). The prefix inequality therefore places \(s_i\) no later than \(r_i\). Distinct indices select distinct elements of \(S\), so the proposed map is injective and satisfies the dominance requirement.
The empty-bundle case is explicitly covered. The lemma applies to overlapping bundles as well as disjoint ones.
Both dominance relations give opposite inequalities for every prefix, hence equal prefix counts. Subtracting successive counts determines membership of each category. At the first category, the preceding prefix is \(P_t(0)=\varnothing\), whose count is zero.
Thus the conclusion \(S=R\) is fully justified. Strictness of the ranking is essential and is supplied by the task.
The task quantifies over every ordered comparison, including comparisons within a type. Consequently, two positively represented bundles of the same type must dominate each other under that type’s ranking. Applying the preceding result is valid.
There are only finitely many bundles, and the type’s total mass is positive. Therefore at least one bundle has positive mass; the equality argument allows at most one. Its mass must be \(1/3\).
This step excludes fractional mixing without imposing any additional assumption on the real allocation variables.
Substitution into each supply equation gives
\[
\sum_{t\in T}\mathbf{1}_{\{j\in S_t\}}=1.
\]
Therefore each category belongs to exactly one type’s bundle. The resulting bundles form a complete partition.
Once each type has one positively represented bundle, the quantified envy requirement becomes exactly the stated ordered bundle comparisons. The converse construction assigns mass \(1/3\) to each designated bundle and satisfies every population, supply, and envy constraint. Self-comparisons hold through the identity injection.
Both directions of the equivalence are established.
An injection witnessing dominance implies that the dominating bundle has at least as many elements as the dominated bundle. Applying the comparisons in both ordered directions yields equal cardinalities, even though the comparisons use different rankings.
Since the bundles partition \(J\), divisibility of \(m\) by \(3\) is a valid necessary condition. The prover does not incorrectly claim sufficiency. Empty bundles and nondivisible positive values of \(m\) are already handled by the argument.
The journal’s Theorem 1 states NP-completeness of deciding whether a complete necessary envy-free allocation exists for exactly three agents. Its input consists of strict rankings over indivisible items, and completeness means partitioning all items among the agents. Its fairness definition uses an injection assigning a preferred item to each item of another agent’s bundle. The initial block gives the three agents different first-ranked items, confirming distinct preference types. These facts match the prover’s citation. [Aziz, Schlotter, and Walsh, Sections 2–3](https://real.mtak.hu/187117/1/1-s2.0-S0165489623000677-main.pdf).
The difference between strict preference in that definition and the target’s permission to map an item to itself causes no mismatch: distinct agents’ bundles are disjoint. The target’s additional self-comparisons are automatically satisfied.
Retaining rankings and attaching the prescribed rational constants is a polynomial transformation. The established equivalence preserves both yes and no answers. The distinct rankings in the cited construction ensure that hardness applies with exactly three supported types, even when types are identified by rankings.
A category-to-type assignment is a finite certificate of \(O(m\log\tau)\) bits, hence \(O(m)\) bits for \(\tau=3\). It specifies a complete partition.
The proved prefix characterization verifies all ordered dominance comparisons. The converse equivalence then supplies the required mass allocation. Thus the use of real variables in the original formulation creates no certificate gap.
Scanning each ranking for each ordered type pair permits verification in \(O(\tau^2m)\) word-RAM operations after input processing. The stated total bound \(O(L+\tau^2m)\), specialized to \(O(L+m)\), is valid.
There are \(\tau^m\) assignments, so the exhaustive decision bound \(O(L+\tau^m\tau^2m)\), specialized to \(O(L+3^m m)\), is also valid. The conservative \(O(L^2)\) bit-operation verification bound is consistent with sequential scans and indexed category encodings.
NP membership and NP-hardness establish NP-completeness. The final statement that polynomial-time decidability is equivalent to \(\mathrm{P}=\mathrm{NP}\) follows.
No additional clarification or mathematical 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.