Answer: \(\mathrm{NP\text{-}complete}\)
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor binary additive valuations, MMS- COMPLETION and Prop1-COMPLETION can be solved in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite good types \(G\), rational student-type masses \(\mu_t\), binary approval vectors \(a_t\), frozen bundles \(F_t\), and rational per-capita supplies \(q_g\), decide whether there exists a mass distribution \(x_{t,B}\) over whole bundles \(B\subseteq G\setminus F_t\) satisfying type-mass and supply constraints, with every occupied bundle meeting its evaluator type’s MMS threshold \(\lambda_t\), where \(\lambda_t\) is the maximum minimum value over all mass-feasible hypothetical completions of the frozen-slot population under \(a_t\).
Let \(M\) be finitely many good categories, \(T\) binary-additive valuation types, positive rational masses \(\mu_t\), rational supplies \(q_g\), and frozen integral bundles \(F_t\subseteq M\). A feasible allocation is nonnegative rational \(x_{t,B}\), for \(B\supseteq F_t\), with \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}x_{t,B}\le q_g\).
A positive-mass configuration is a pair \((t,B)\) with \(x_{t,B}>0\). The allocation is EF1 if for every two such configurations \((t,B)\) and \((t',B')\), either \(B'=\varnothing\) or some \(g\in B'\) satisfies \(v_t(B)\ge v_t(B'\setminus\{g\})\).
The frozen baseline is required to be Pareto optimal: no feasible redistribution of only the frozen-good quantities gives every positive-mass recipient of type \(t\) value at least \(v_t(F_t)\) and gives a positive mass strictly greater value.
Is deciding whether such an EF1 feasible allocation exists solvable in polynomial time, or is it NP-hard?
For finitely many named agents with binary additive valuations, EF1 completion is NP-complete even when the frozen allocation is Pareto optimal.
Without frozen goods, a finite-agent EF1 allocation can be computed in polynomial time.
On the promised class of instances whose frozen baseline is Pareto optimal, deciding whether an EF1 feasible allocation exists is \(\mathrm{NP}\)-complete. In particular, it is \(\mathrm{NP}\)-hard even when every supply is \(1\) and every type mass belongs to \(\{1,3\}\).
Consider an instance \((G,K)\) of \(\mathrm{Independent\ Set}\), where \(G=(V,E)\) and \(1\le K\le |V|\). The question is whether \(G\) contains an independent set of cardinality at least \(K\).
Construct the following allocation instance.
For every vertex \(v\in V\), introduce a vertex good also denoted \(v\). Introduce additionally the dummy goods
\[ D=\{d_1,\ldots,d_{K+1}\}. \]
Every good \(g\in V\cup D\) has supply \(q_g=1\).
Introduce:
The chooser approves every good:
\[ v_c(g)=1\qquad\text{for every }g\in V\cup D. \]
The special type approves exactly the dummy goods:
\[ v_s(d)=1\text{ for }d\in D,\qquad v_s(v)=0\text{ for }v\in V. \]
For an edge \(e=\{u,v\}\), type \(e\) approves exactly its two endpoints:
\[ v_e(u)=v_e(v)=1, \]
and \(v_e(g)=0\) for every other good \(g\).
Set
\[ F_s=D,\qquad F_c=\varnothing,\qquad F_e=\varnothing\text{ for every }e\in E. \]
The construction has polynomial size.
Only the dummy goods occur in frozen bundles. Every recipient of type \(s\) has baseline value \(K+1\), which is the maximum value obtainable from the \(K+1\) frozen goods.
Consequently, in any redistribution of only the frozen-good quantities that leaves every positive-mass recipient of type \(s\) with value at least \(K+1\), every such recipient must receive all of \(D\). Since \(\mu_s=1\) and every dummy supply equals \(1\), this exhausts every dummy good.
Thus no positive mass of chooser recipients can receive a dummy good and become strictly better. Edge types value every dummy good at \(0\), so they cannot become strictly better either. Hence no permitted redistribution Pareto dominates the frozen baseline.
Suppose \(G\) contains an independent set of cardinality at least \(K\). Taking a subset if necessary, fix an independent set \(S\subseteq V\) with \(|S|=K\).
Use the allocation
\[ x_{c,S}=1,\qquad x_{s,D}=1,\qquad x_{e,\varnothing}=3\text{ for every }e\in E, \]
with all other variables equal to \(0\). It is feasible because \(S\cap D=\varnothing\), every used good has total consumption \(1\), and unused vertex goods may remain unallocated.
It remains to verify EF1 for every ordered pair of positive-mass configurations.
The chooser values its own bundle at \(K\), while it values \(D\setminus\{d\}\) at \(K\) for every \(d\in D\). Thus the chooser does not envy the special bundle after one dummy is removed.
The special type values \(S\) at \(0\), so it does not envy the chooser after any good of \(S\) is removed.
Fix \(e=\{u,v\}\in E\). Since \(S\) is independent, \(|S\cap\{u,v\}|\le1\). If the intersection contains one vertex, removing that vertex leaves value \(0\) for type \(e\); if it is empty, removing any member of the nonempty set \(S\) leaves value \(0\). Hence the empty edge configuration is EF1 relative to the chooser configuration.
Every edge type values \(D\) at \(0\). Comparisons against an empty bundle satisfy the explicit \(B'=\varnothing\) clause. Self-comparisons are immediate by removing any good from the compared nonempty bundle.
Therefore the allocation is EF1.
Suppose an EF1 feasible allocation \(x\) exists.
Every bundle in the support of type \(s\) contains \(F_s=D\). Therefore, for each \(d\in D\), the amount of \(d\) consumed by type \(s\) is
\[ \sum_B x_{s,B}=\mu_s=1=q_d. \]
Thus no positive-mass configuration of any other type can contain a dummy good.
Let \(B\) be any positive-mass chooser configuration. There exists a positive-mass special configuration \(C\), and \(C\supseteq D\).
Applying EF1 from \((c,B)\) toward \((s,C)\), there is some \(g\in C\) such that
\[ v_c(B)\ge v_c(C\setminus\{g\}). \]
Because \(C\) contains \(K+1\) dummy goods and at most one good is removed,
\[ v_c(C\setminus\{g\})\ge K. \]
Hence \(v_c(B)\ge K\). The chooser cannot receive dummy goods, so \(B\) contains at least \(K\) vertex goods.
Fix an edge \(e=\{u,v\}\). The expected value received by type \(e\) is
\[ \sum_B x_{e,B}v_e(B) = \sum_{w\in\{u,v\}}\sum_{B:w\in B}x_{e,B} \le q_u+q_v=2. \]
If every positive-mass configuration of type \(e\) had value at least \(1\), then the same expression would be at least
\[ \sum_B x_{e,B}=\mu_e=3, \]
a contradiction. Therefore there is a positive-mass edge configuration \(C_e\) satisfying \(v_e(C_e)=0\).
Let \(B\) again be any positive-mass chooser configuration. Since \(B\) contains at least \(K\ge1\) vertex goods, it is nonempty. EF1 from \((e,C_e)\) toward \((c,B)\) gives some \(g\in B\) such that
\[ 0=v_e(C_e)\ge v_e(B\setminus\{g\}). \]
Nonnegativity implies \(v_e(B\setminus\{g\})=0\). If both \(u\) and \(v\) belonged to \(B\), removing any single good would leave at least one of them, giving value at least \(1\) to type \(e\). Hence \(B\) cannot contain both endpoints of \(e\).
This holds for every edge \(e\), so the vertex goods in \(B\) form an independent set. Since \(B\) contains at least \(K\) vertex goods, \(G\) has an independent set of cardinality at least \(K\).
Combining Lemmas \(2\) and \(3\), the constructed allocation instance admits an EF1 feasible allocation if and only if \((G,K)\) is a yes-instance of \(\mathrm{Independent\ Set}\). This proves \(\mathrm{NP}\)-hardness.
Although there are exponentially many possible bundles, every yes-instance has a polynomial-size certificate.
Suppose \(x\) is an EF1 allocation and let \(\mathcal S\) be its positive support. Restrict attention to variables indexed by \(\mathcal S\) and consider the polytope determined by the type-mass equalities, the good-supply inequalities, and nonnegativity. It is nonempty because it contains \(x\), and it is bounded because every variable \(x_{t,B}\) is at most \(\mu_t\).
Choose an extreme point \(y\) of this polytope. It has at most \(|T|+|M|\) positive variables. Indeed, if more variables were positive, their columns in the \(|T|+|M|\) type-and-good constraint matrix would be linearly dependent. A sufficiently small perturbation in both directions along such a dependence would preserve all type masses and all good consumptions while maintaining nonnegativity, contradicting extremality.
Moreover, \(\operatorname{supp}(y)\subseteq\mathcal S\). Deleting positive-mass configurations cannot create a new EF1 comparison, so \(y\) remains EF1. Since the constraint matrix has entries in \(\{0,1\}\) and all right-hand sides are rational, the usual determinant bound for basic feasible solutions shows that the numerators and denominators of \(y\) have polynomial bit length.
A certificate therefore lists at most \(|T|+|M|\) bundles and their rational masses. Feasibility and all ordered EF1 comparisons among these configurations can be checked in polynomial time.
The problem is \(\mathrm{NP}\)-complete on Pareto-optimal frozen baselines. The mass-splitting relaxation does not restore tractability: the edge types of mass \(3\) force a zero-valued support configuration for every edge, and the support-wise EF1 condition then forces each chooser bundle itself to encode an independent set.
⟨structured verdict parsed — rendered above⟩
The prover claims that, under the promise that the frozen baseline is Pareto optimal, EF1 feasibility is \(\mathrm{NP}\)-complete, with hardness even when every supply is \(1\) and every mass belongs to \(\{1,3\}\).
The reduction addresses the requested continuous, mass-splitting model rather than merely invoking the finite-agent result.
The construction introduces:
Because \(K\leq |V|\), the number of goods, types, and valuation entries is polynomial in the Independent Set instance size. All frozen bundles and masses are valid under the definitions.
This part is correct.
The only frozen goods are the \(K+1\) dummy goods assigned to type \(s\).
Every positive-mass recipient of type \(s\) has baseline value \(K+1\). Since type \(s\) values precisely those \(K+1\) frozen goods, retaining value at least \(K+1\) requires every such recipient to receive all dummy goods. Because \(\mu_s=1\) and every dummy has supply \(1\), this exhausts every dummy supply.
Consequently:
Thus no permitted redistribution of frozen-good quantities Pareto dominates the baseline. The promise is correctly verified.
Given an independent set \(S\) of size \(K\), the proposed allocation is feasible:
The EF1 comparisons are also correct.
Thus the forward implication is correct.
Every allowed special-type bundle contains \(D\). Therefore each dummy is consumed by type \(s\) in total mass
\[ \sum_B x_{s,B}=\mu_s=1. \]
Since its supply is \(1\), no positive-mass configuration of another type can contain a dummy. This is correct.
A positive-mass special configuration exists and contains all \(K+1\) dummies. Applying EF1 from any positive chooser configuration \(B\) toward that special configuration shows that the chooser values \(B\) at least \(K\), since deleting one good leaves at least \(K\) approved dummies.
Because chooser configurations cannot contain dummies, \(B\) contains at least \(K\) vertex goods. This argument is correct.
For an edge \(e=\{u,v\}\), binary additivity gives
\[ \sum_B x_{e,B}v_e(B) = \sum_{w\in\{u,v\}}\sum_{B:w\in B}x_{e,B} \leq q_u+q_v=2. \]
If every positive-mass edge configuration had value at least \(1\), the left side would be at least
\[ \sum_B x_{e,B}=\mu_e=3, \]
which is impossible. Hence some positive-mass edge configuration has value \(0\). This is correct and is precisely where mass \(3\) is used.
Applying EF1 from that zero-valued edge configuration toward a chooser bundle \(B\) requires some \(g\in B\) such that
\[ 0\geq v_e(B\setminus\{g\}). \]
Nonnegativity forces the remaining value to be \(0\). If \(B\) contained both endpoints of \(e\), deleting any one good would leave at least one approved endpoint, contradicting this equality.
Therefore every chooser bundle is independent. Since every chooser bundle contains at least \(K\) vertices, the graph has an independent set of size at least \(K\). The reverse implication is correct.
Restricting to the support of an existing EF1 allocation and passing to an extreme point correctly preserves EF1, because the new support is a subset of the old support and therefore introduces no new ordered comparisons.
The support bound of at most \(|T|+|M|\) is justified by linear dependence among the corresponding columns of the type-and-good incidence matrix. A dependence permits a sufficiently small perturbation in both directions that preserves type masses, all good consumptions, and nonnegativity, contradicting extremality.
There is one minor expositional gap: the statement that the “usual determinant bound” gives polynomial-bit rational coordinates is not stated precisely. The write-up should identify the active square subsystem defining a basic feasible solution and state the applicable coefficient/right-hand-side bit-length bound. All required hypotheses appear to be present—there are polynomially many rows, coefficients lie in \(\{0,1\}\), and the right-hand sides are rational—so this omission does not threaten the conclusion.
Given the asserted encoding bound, feasibility and every ordered EF1 comparison can plainly be checked in polynomial time.
The reduction is correct in both directions, handles mass splitting explicitly, and correctly establishes \(\mathrm{NP}\)-hardness on Pareto-optimal frozen baselines. The membership argument is sound in substance, with only a minor omission in the presentation of the standard bit-complexity bound.
⟨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.