Answer: \(\mathrm{NP}\text{-complete}\), even when \(m=2\tau\) and \(\mu_t=b_g=1/\tau\) for every type and category.
Proposition 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIf n agents express their pref- erences over m goods using SCI-nets, then deciding whether there exists a complete NEF allocation is NP-complete (even if m = 2n).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of categories \(G\), a finite support \(T\) of SCI-net types with strict rankings and rational masses \(\mu_t>0\) summing to \(1\), and rational per-capita stocks \(b_g\), does there exist a bundle \(B_t\subseteq G\) for each type such that \(\sum_{t:g\in B_t}\mu_t=b_g\) for every category \(g\), and for every \(t,u\), either \(B_t=B_u\) or \(B_t\succ_t B_u\), where \(\succ_t\) is the partial bundle order induced by type \(t\)'s SCI-net?
Let \(G\) be a set of \(m\geq1\) categories. A society is given by its support: a list \(T\) of \(\tau\geq1\) distinct types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Each category has binary rational per-capita stock \(0<b_g\leq1\); let \(L\) be the total input bit length.
Each type supplies an SCI-net, meaning a strict linear ranking \(\triangleright_t\) of \(G\). Its bundle order \(\succ_t\) is the smallest strict partial order containing \(A\succ_t B\) whenever \(A\supsetneq B\), and \(S\cup\{x\}\succ_t S\cup\{y\}\) whenever \(x\triangleright_t y\) and \(S\subseteq G\setminus\{x,y\}\).
An allocation assigns one bundle \(B_t\subseteq G\) to the entire mass of each type; a type cannot be split among bundles. It is complete if \(\sum_{t\in T:g\in B_t}\mu_t=b_g\) for every \(g\in G\), and necessarily envy-free if, for every \(t,u\in T\), either \(B_t=B_u\) or \(B_t\succ_t B_u\).
Is deciding whether a complete, necessarily envy-free allocation exists solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finitely many agents and distinct indivisible goods, existence of a complete necessarily envy-free allocation under SCI-net preferences is NP-complete, even with \(m=2n\), where \(n\) is the number of agents; it is in \(\mathrm{P}\) for two agents. [Source](https://recherche.noiraudes.net/resources/papers/COMSOC10.pdf)
No result settling the exact mass model defined above was located in the literature search.
The problem is \(\mathrm{NP}\)-complete, even when \(m=2\tau\) and every type mass and category stock equals \(1/\tau\).
The proof uses the finite-agent hardness result stated in the question, but explicitly handles the requirement that supported types be distinct.
Fix a type \(t\), and write its ranking as \(g_1\triangleright_t\cdots\triangleright_t g_m\). Define \(P_k=\{g_1,\ldots,g_k\}\).
Lemma. For distinct bundles \(A,B\),
\[
A\succ_t B
\quad\Longleftrightarrow\quad
|A\cap P_k|\geq |B\cap P_k|
\text{ for every }k\in\{1,\ldots,m\}.
\]
Proof. Adding goods never decreases any prefix count. Replacing a good by a higher-ranked good also never decreases any prefix count. Thus every generating comparison, and consequently every comparison in their transitive closure, satisfies the displayed inequalities.
Conversely, suppose the inequalities hold. Put \(C=A\setminus B\) and \(D=B\setminus A\). Cancelling the common goods gives \(|C\cap P_k|\geq|D\cap P_k|\) for every \(k\).
List \(C=\{c_1,\ldots,c_p\}\) and \(D=\{d_1,\ldots,d_q\}\) in decreasing preference order. The inequality for \(k=m\) gives \(p\geq q\). For each \(i\leq q\), consider the prefix ending at \(d_i\). It contains exactly \(i\) goods of \(D\), so it contains at least \(i\) goods of \(C\). Therefore \(c_i\) ranks at least as high as \(d_i\). Since \(C\cap D=\varnothing\), the ranking is strict: \(c_i\triangleright_t d_i\).
Starting from \(B\), replace each \(d_i\) by \(c_i\), and then add \(c_{q+1},\ldots,c_p\). Each replacement is an allowed improvement: its incoming good is absent, and its outgoing good is present. The final bundle is \(A\). Since \(A\neq B\), at least one improvement occurs. Hence \(A\succ_t B\). \(\square\)
The lemma gives a comparison algorithm taking \(O(m)\) time once the ranking positions are available.
A certificate specifies the incidence bit of every category in every type’s bundle, using \(m\tau\) bits.
Completeness is verified by checking, for each \(g\),
\[
\sum_{t:g\in B_t}\mu_t=b_g.
\]
Exact addition and comparison of the input rationals take polynomial time in \(L\): a common denominator obtained by multiplying their denominators has bit length at most the sum of their input bit lengths.
For every ordered pair \(t,u\), first check whether \(B_t=B_u\). Otherwise apply the lemma to check \(B_t\succ_t B_u\). All envy checks take \(O(\tau^2m)\) time after preprocessing the rankings.
Thus the decision problem belongs to \(\mathrm{NP}\).
Use the following known source problem: deciding whether \(n\) agents with SCI-net rankings over \(2n\) distinct indivisible goods admit a complete necessarily envy-free allocation. This problem is \(\mathrm{NP}\)-complete by Proposition 7 of [Bouveret, Endriss, and Lang](https://recherche.noiraudes.net/resources/papers/COMSOC10.pdf).
In the source problem, completeness means that the bundles partition the goods.
If two source agents have the same top-ranked good \(x\), the source instance is a no-instance. Indeed, completeness assigns \(x\) to exactly one agent. At least one of the two agents therefore lacks \(x\). For that agent, its own bundle has prefix count zero on \(\{x\}\), whereas the recipient’s bundle has prefix count one. The lemma rules out the required dominance.
Accordingly, when the source instance has repeated top-ranked goods, output this fixed mass-model no-instance:
The two rankings are distinct. Completeness forces each category to belong to exactly one type’s bundle. Whichever type lacks \(a\) fails the prefix comparison against the type receiving \(a\). Hence this is a valid no-instance, with \(m=2\tau\).
Now suppose all source agents have distinct top-ranked goods. Their rankings are consequently distinct.
Create one supported type per source agent, retaining its ranking, and set
\[
\tau=n,\qquad \mu_t=\frac1n\quad\text{for every }t,\qquad
b_g=\frac1n\quad\text{for every }g.
\]
Retain all \(2n\) goods as categories. These are valid positive rational masses and stocks, and the masses sum to one.
For any proposed allocation, completeness at category \(g\) is equivalent to
\[
\frac1n\,\bigl|\{t:g\in B_t\}\bigr|=\frac1n,
\]
which is equivalent to exactly one type receiving \(g\). Thus complete allocations in the constructed instance are precisely partitions of the categories among the source agents.
The rankings and induced bundle orders are unchanged. Moreover, a complete necessarily envy-free partition has no empty bundle: an agent with an empty bundle cannot dominate any nonempty bundle, by the lemma at \(k=m\). Hence distinct agents’ bundles are nonempty and disjoint, so they cannot be equal. The mass model’s allowance for equal bundles therefore introduces no additional feasible allocation.
Consequently, the constructed mass instance admits a complete necessarily envy-free allocation if and only if the source instance does.
The construction has polynomial size: each added rational \(1/n\) uses \(O(\log n)\) bits. Together with the repeated-top case, this is a polynomial-time many-one reduction.
The exact, unsplittable mass model is \(\mathrm{NP}\)-complete. Hardness already holds with \(m=2\tau\) and uniform masses and stocks \(1/\tau\). In this restriction, the completeness equations enforce the indivisibility needed by the source hardness result.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the task: the exact mass model is \(\mathrm{NP}\)-complete, including the claimed restriction \(m=2\tau\) with \(\mu_t=b_g=1/\tau\). I found no major or minor mathematical issues.
The lemma correctly restricts its equivalence to distinct bundles. Without that restriction, the prefix inequalities would also hold for equality, which cannot belong to a strict order.
The forward implication is valid. Adding a category increases some prefix counts and decreases none. Replacing a category by a higher-ranked category likewise decreases no prefix count. These inequalities persist under composition, so every comparison generated by transitivity satisfies them.
The converse is also valid:
The proposed replacements are legal throughout: each \(d_i\) remains present until its replacement, and each \(c_i\) is initially absent and differs from every previously inserted category. The subsequent additions are also legal. The final bundle is exactly \(A\).
The edge cases are covered. If \(q=0\), only additions are needed. If \(p=q=0\), then \(A=B\), excluded by the lemma’s hypothesis. Thus at least one strict improvement occurs.
The claimed \(O(m)\) comparison time is correct using bundle incidence bits and a scan through the ranking.
The certificate has \(m\tau\) incidence bits, polynomial in the stated input parameters.
Exact completeness checks are polynomial in the binary input length. Multiplying the rational denominators produces a denominator whose bit length is bounded by the sum of their bit lengths. Rescaling numerators, adding them, and comparing the resulting rational with \(b_g\) require only polynomially many operations on integers of polynomial bit length.
The envy verification matches the task exactly: equality is accepted, and distinct bundles must pass the strict comparison lemma for every ordered pair. The stated \(O(\tau^2m)\) combinatorial running time is valid.
The citation is accurate. Proposition 7 states that existence of a complete necessarily envy-free allocation under SCI-net preferences is \(\mathrm{NP}\)-complete even with \(m=2n\). Definition 1 uses precisely the task’s linear ranking and smallest strict partial order generated by monotonicity and context-independent singleton replacements. The source’s allocations assign disjoint bundles, and completeness requires their union to contain every good. These are the hypotheses needed by the reduction. [Bouveret, Endriss, and Lang, Definition 1 and Proposition 7](https://recherche.noiraudes.net/resources/papers/COMSOC10.pdf)
The prover may invoke this established theorem without reproducing its hardness proof. There is no mismatch in preference representation or completeness.
This rejection branch is correct. If two agents have the same top-ranked good \(x\), at least one lacks \(x\) in every complete partition. That agent’s bundle differs from the recipient’s bundle, and its prefix count on \(\{x\}\) is zero rather than one. The comparison lemma therefore excludes the required dominance.
The fixed target instance satisfies all input restrictions: its rankings are distinct, its masses are positive and sum to one, its stocks are valid, and \(m=4=2\tau\).
With masses and stocks equal to \(1/2\), completeness forces each category into exactly one bundle. The shared top category \(a\) then supplies the same obstruction. Consequently, this branch maps source no-instances to a valid target no-instance.
Distinct top-ranked goods imply distinct rankings, so the construction satisfies the distinct-supported-types requirement.
All numerical restrictions hold: \(\mu_t=1/n>0\), the masses sum to one, and \(0<b_g=1/n\leq1\).
The completeness equation correctly reduces to exactly one recipient per category. Thus target complete allocations and source complete partitions correspond in both directions.
The equality allowance causes no discrepancy. In a complete partition of a nonempty goods set, some bundle is nonempty. Any agent with an empty bundle would fail the comparison against that bundle at \(k=m\), so a necessarily envy-free partition has no empty bundle. Distinct nonempty disjoint bundles cannot be equal.
The source and target therefore impose the same envy comparisons on every potentially feasible complete allocation. Both directions of the asserted equivalence follow.
Each rational \(1/n\) has binary encoding length \(O(\log n)\). The rankings are retained, the repeated-top test is polynomial, and the alternative output has constant size. Hence the entire construction is a polynomial-time many-one reduction preserving \(m=2\tau\) and uniform masses and stocks.
Together with membership in \(\mathrm{NP}\), this proves the claimed \(\mathrm{NP}\)-completeness. 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.