Answer: \(\mathrm{NP}\)-complete, and hence \(\mathrm{NP}\)-hard, even for \(\kappa=0\) and \(K=\{\ell\geq 0:\sum_c\ell_c\leq 1/2\}\)
Theorem 5.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateChecking whether an EF-𝑘(𝑘< 𝑛−1) and nonwaste- ful matching exists or not is NP-complete, even when distributional constraints form a hereditary M♮-convex set.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(\Theta\), rational masses \(\mu_\theta\) summing to \(1\), type-level strict student preferences \(\succ_\theta\) over \(C\cup\{\varnothing\}\), type-level college priority orders \(\succ_c\), a rational downward-closed generalized-polymatroid \(K\subseteq\mathbb{R}_{\ge0}^{m}\), and \(\alpha\in[0,1]\), decide whether there are \(x_{\theta a}\ge0\) for \(a\in C\cup\{\varnothing\}\) with \(\sum_a x_{\theta a}=\mu_\theta\) and \(q_c=\sum_\theta x_{\theta c}\in K\), such that every occupied assignment \(x_{\theta a}>0\) has \(E_x(\theta,a)=\sum_{c\succ_\theta a}\sum_{\theta':\,\theta\succ_c\theta'\succ_c\varnothing}x_{\theta'c}\le\alpha\), and no positive \(\delta\le x_{\theta a}\) can move from \(a\) to a preferred acceptable college \(c\) while preserving \(q+\delta(e_c-e_a)\in K\), with \(e_\varnothing=0\).
Definitions. An instance has finite \(C,T\), rational masses \(\mu_t\geq0\) with \(\sum_t\mu_t=1\), strict preferences \(\succ_t\) on \(C\cup\{\varnothing\}\), strict priorities \(\succ_c\) on \(T\), and a rational inequality description of a per-capita load region \(K\subseteq\mathbb{R}^C_+\), promised to arise from a hereditary \(M^\natural\)-convex family.
An assignment has \(y_{t,c}\geq0\), \(y_{t,c}=0\) for unacceptable \(c\), \(\sum_c y_{t,c}\leq\mu_t\), \(y_{t,\varnothing}:=\mu_t-\sum_cy_{t,c}\), and \(\ell_c:=\sum_t y_{t,c}\in K\). It is EF-\(\kappa\) if, for every \(t\) and \(d\in C\cup\{\varnothing\}\) with \(y_{t,d}>0\), \(\sum_{c\succ_t d}\sum_{u:\,t\succ_c u}y_{u,c}\leq\kappa\).
It is nonwasteful if, for every such \(t,d\) and every acceptable \(c\succ_t d\), no \(\epsilon\in(0,y_{t,d}]\) has \(\ell+\epsilon e_c-\mathbf{1}_{d\in C}\epsilon e_d\in K\).
Target. Is deciding whether a nonwasteful EF-\(\kappa\) assignment exists NP-hard or solvable in polynomial time?
Nearest known results. In the finite-student version, deciding whether a nonwasteful EF-\(k\) matching exists is NP-complete for \(k<n-1\), even under hereditary \(M^\natural\)-convex distributional constraints.
No result for the stated mass formulation is established by the supplied source.
The stated decision problem is \(\mathrm{NP}\)-complete. It is already weakly \(\mathrm{NP}\)-hard when \(\kappa=0\) and
\[ K=\left\{\ell\in\mathbb{R}_+^C:\sum_{c\in C}\ell_c\le \frac12\right\}. \]
Thus divisibility of type masses does not make the problem polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
Write the rational inequality description of \(K\) as \(A\ell\le b\). For \(c\succ_t d\), define
\[ v^{c,d}:=e_c-\mathbf 1_{d\in C}e_d. \]
Fix a feasible assignment and suppose \(y_{t,d}>0\). Because \(y_{t,d}\le \ell_d\) when \(d\in C\), decreasing coordinate \(d\) by any \(\epsilon\le y_{t,d}\) preserves nonnegativity.
There exists no sufficiently small positive \(\epsilon\) with \(\ell+\epsilon v^{c,d}\in K\) if and only if some row \(r\) of the given description satisfies
\[ A_r\ell=b_r \qquad\text{and}\qquad A_rv^{c,d}>0. \]
Indeed, such a tight row excludes every positive \(\epsilon\). Conversely, if no such row exists, every row having \(A_rv^{c,d}>0\) has positive slack. Since there are finitely many rows, one may choose a positive \(\epsilon\le y_{t,d}\) smaller than every relevant slack-to-slope ratio. All other inequalities remain satisfied.
Consequently, after guessing the support of \(y\) and one blocking row for every required nonwastefulness condition, all remaining conditions are rational linear equalities and inequalities:
If such a system has a real solution, it has a polynomial-bit rational solution. To see this, introduce \(\delta\) and require every supported variable to be at least \(\delta\). Maximizing \(\delta\) is a bounded rational linear program whose optimum is positive whenever the guessed support is realizable. A rational optimal basic solution has polynomial encoding length by the standard determinant bound for rational linear programs.
A polynomial-size rational assignment is therefore a certificate. Feasibility, EF-\(\kappa\), and the blocking-row characterization above can all be checked in polynomial time. Hence the problem belongs to \(\mathrm{NP}\).
Use the restriction of PARTITION in which the total weight is even. This remains \(\mathrm{NP}\)-complete: multiplying every weight in an arbitrary PARTITION instance by \(2\) produces an equivalent instance with even total weight.
Let \(a_1,\ldots,a_m\) be positive integers and let
\[ A:=\sum_{i=1}^m a_i \]
be even. The question is whether some \(S\subseteq\{1,\ldots,m\}\) satisfies
\[ \sum_{i\in S}a_i=\frac A2. \]
For every item \(i\), create two types \(p_i,q_i\), each having mass
\[ \mu_{p_i}=\mu_{q_i}:=\frac{a_i}{2A}. \]
Their total mass is
\[ \sum_i\left(\mu_{p_i}+\mu_{q_i}\right) =\sum_i\frac{a_i}{A}=1. \]
Create two colleges \(P_i,Q_i\) for every item \(i\). The acceptable parts of the type preferences are
\[ P_i\succ_{p_i}Q_i\succ_{p_i}\varnothing, \qquad Q_i\succ_{q_i}P_i\succ_{q_i}\varnothing. \]
Every other college is unacceptable to these types and is placed below \(\varnothing\). Complete all orders strictly.
At \(P_i\), set
\[ q_i\succ_{P_i}p_i, \]
and at \(Q_i\), set
\[ p_i\succ_{Q_i}q_i. \]
The remaining parts of the college priorities may be completed arbitrarily.
Set \(\kappa=0\), and use the load region
\[ K:=\left\{\ell\in\mathbb{R}_+^C: \sum_{c\in C}\ell_c\le\frac12\right\}. \]
The construction has polynomial encoding length.
Consider the integer family
\[ F:=\left\{z\in\mathbb{Z}_+^C: \sum_{c\in C}z_c\le A\right\}. \]
It is hereditary. It is also \(M^\natural\)-convex. To verify the exchange axiom, take \(x,y\in F\) with \(x_c>y_c\).
If \(\sum_d y_d<A\), then both \(x-e_c\) and \(y+e_c\) belong to \(F\). If instead \(\sum_d y_d=A\), then \(\sum_d x_d\le A=\sum_d y_d\), so some \(d\) satisfies \(x_d<y_d\). Both exchanged vectors
\[ x-e_c+e_d \qquad\text{and}\qquad y+e_c-e_d \]
remain nonnegative and preserve their respective total masses, hence belong to \(F\).
Moreover,
\[ \frac{1}{2A}\operatorname{conv}(F) = \left\{\ell\in\mathbb{R}_+^C: \sum_c\ell_c\le\frac12\right\} =K. \]
Thus \(K\) is precisely a per-capita normalization of a hereditary \(M^\natural\)-convex family.
Let \(y\) be any nonwasteful assignment in the constructed instance.
First, \(p_i\) cannot receive positive mass at \(Q_i\). If \(y_{p_i,Q_i}>0\), moving any sufficiently small positive amount from \(Q_i\) to the preferred college \(P_i\) preserves the total load and therefore remains in \(K\), contradicting nonwastefulness. Similarly, \(q_i\) cannot receive positive mass at \(P_i\).
Hence define
\[ x_i:=y_{p_i,P_i}, \qquad z_i:=y_{q_i,Q_i}. \]
All assigned mass is represented by these variables.
Next, the total load must equal \(1/2\). If it were strictly smaller, then, because the total population mass is \(1\), some type would have positive outside-option mass. Moving a sufficiently small part of that mass to its top college would keep the total load at most \(1/2\), again contradicting nonwastefulness. Therefore,
\[ \sum_i(x_i+z_i)=\frac12. \]
Suppose \(x_i>0\). If \(z_i<\mu_{q_i}\), then \(q_i\) has positive mass at \(\varnothing\). Type \(q_i\) prefers \(P_i\) to \(\varnothing\), and \(q_i\succ_{P_i}p_i\). Its EF-\(0\) expression therefore contains the positive term \(x_i\), a contradiction. Hence
\[ x_i>0\quad\Longrightarrow\quad z_i=\mu_{q_i}. \]
Symmetrically, using \(p_i\succ_{Q_i}q_i\),
\[ z_i>0\quad\Longrightarrow\quad x_i=\mu_{p_i}. \]
It follows that, for every \(i\), exactly one of the following holds:
\[ x_i=z_i=0, \]
or
\[ x_i=\mu_{p_i} \qquad\text{and}\qquad z_i=\mu_{q_i}. \]
Thus each item-pair is assigned all-or-nothing despite the divisibility of masses.
Let
\[ S:=\{i:x_i>0\}. \]
By the all-or-nothing property and tightness of the capacity,
\[ \frac12 =\sum_i(x_i+z_i) =\sum_{i\in S}\frac{a_i}{A}. \]
Multiplying by \(A\) gives
\[ \sum_{i\in S}a_i=\frac A2. \]
Hence a nonwasteful EF-\(0\) assignment yields a valid partition.
Conversely, suppose \(S\) satisfies \(\sum_{i\in S}a_i=A/2\). For each \(i\in S\), assign all \(p_i\)-mass to \(P_i\) and all \(q_i\)-mass to \(Q_i\). Leave both types outside for every \(i\notin S\).
The total load is
\[ \sum_{i\in S}\frac{a_i}{A}=\frac12, \]
so the assignment is feasible.
It is nonwasteful: assigned types receive their top choices, while any movement of outside mass to a college would increase the already tight total load.
It is EF-\(0\): assigned types have no mass at a worse outcome, and for every unassigned pair \(i\notin S\), both acceptable colleges \(P_i,Q_i\) are empty. Thus every applicable envy expression equals \(0\).
Therefore the PARTITION instance is positive if and only if the constructed mass-assignment instance admits a nonwasteful EF-\(0\) assignment.
The reduction proves weak \(\mathrm{NP}\)-hardness even for fixed \(\kappa=0\) and a single global capacity inequality defining \(K\). Together with membership in \(\mathrm{NP}\), the stated problem is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes weak \(\mathrm{NP}\)-hardness by reduction from PARTITION and polynomial certificate size, hence \(\mathrm{NP}\)-completeness. The construction respects the hereditary \(M^\natural\)-convex promise. No substantive gaps or false statements were found.
The directional characterization of nonwastefulness is correct.
For a feasible load \(\ell\) and direction
\[
v^{c,d}=e_c-\mathbf 1_{d\in C}e_d,
\]
a tight inequality \(A_r\ell=b_r\) with \(A_rv^{c,d}>0\) excludes every positive movement in that direction. Conversely, if no such tight row exists, every row with positive directional slope has positive slack. Finiteness of the inequality system then permits a sufficiently small positive rational \(\epsilon\).
Nonnegativity is handled correctly: when \(d\in C\), the bound
\[
\epsilon\le y_{t,d}\le\ell_d
\]
prevents coordinate \(d\) from becoming negative. When \(d=\varnothing\), no load coordinate decreases.
The certificate argument is also valid:
Here “support” must include the derived outside-option variables \(y_{t,\varnothing}\); the surrounding phrase “supported outcomes” makes that intended interpretation clear.
The even-total restriction of PARTITION is valid. Doubling all input weights is a polynomial-time equivalence-preserving transformation, including when the original total is odd.
The masses are correctly normalized:
\[
\sum_i\left(\mu_{p_i}+\mu_{q_i}\right)
=\sum_i\frac{a_i}{A}=1.
\]
All rational numbers in the construction have polynomial encoding length because their denominators and numerators have bit length polynomial in the PARTITION input.
The family
\[
F=\left\{z\in\mathbb Z_+^C:\sum_c z_c\le A\right\}
\]
is hereditary.
The stated exchange verification correctly proves \(M^\natural\)-convexity:
The normalization is correct:
\[
\frac1{2A}\operatorname{conv}(F)
=
\left\{\ell\in\mathbb R_+^C:\sum_c\ell_c\le\frac12\right\}.
\]
Thus the constructed region satisfies the promised structural restriction.
If \(p_i\) receives positive mass at \(Q_i\), transferring a sufficiently small amount to \(P_i\) preserves total load and nonnegativity, so it remains in \(K\). Since \(P_i\succ_{p_i}Q_i\), this contradicts nonwastefulness. The symmetric argument for \(q_i\) at \(P_i\) is valid.
Consequently, all college-assigned mass is represented by
\[
x_i=y_{p_i,P_i},\qquad z_i=y_{q_i,Q_i}.
\]
The capacity must be tight. If total load were below \(1/2\), some type would have positive outside mass because total population mass is \(1\). A sufficiently small movement from the outside option to that type’s top acceptable college would remain feasible, contradicting nonwastefulness. Hence
\[
\sum_i(x_i+z_i)=\frac12.
\]
Suppose \(x_i>0\). If \(z_i<\mu_{q_i}\), then \(q_i\) has positive outside mass because nonwastefulness already ruled out assignment of \(q_i\) to \(P_i\). For the supported outcome \(\varnothing\), the EF expression of \(q_i\) includes \(x_i\), since
\[
P_i\succ_{q_i}\varnothing
\quad\text{and}\quad
q_i\succ_{P_i}p_i.
\]
This contradicts EF-\(0\). Therefore
\[
x_i>0\Longrightarrow z_i=\mu_{q_i}.
\]
The symmetric implication
\[
z_i>0\Longrightarrow x_i=\mu_{p_i}
\]
is equally valid. Combining them gives exactly the claimed all-or-nothing alternatives.
From any admissible assignment, capacity tightness and the all-or-nothing property give
\[
\frac12
=\sum_{i\in S}\left(\mu_{p_i}+\mu_{q_i}\right)
=\sum_{i\in S}\frac{a_i}{A},
\]
and therefore \(\sum_{i\in S}a_i=A/2\).
Conversely, a partition of weight \(A/2\) produces load exactly \(1/2\). The resulting assignment is:
These arguments cover all supported outcomes and both reduction directions.
The prover’s conclusion follows. The proof establishes weak \(\mathrm{NP}\)-hardness under the stated promise and membership in \(\mathrm{NP}\), so the claimed \(\mathrm{NP}\)-completeness is justified. No additional clarification is necessary for verification.
⟨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.