Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 9 — class: hardness
Given house categories \(H\), valuation types \(T\) with rational masses \(\mu_t\) summing to \(1\), rational valuations \(v_t(h)\), rational per-applicant supplies \(q_h\), and a threshold \(B\), decide whether there is a feasible mass assignment \(x_{t,h},x_{t,0}\geq 0\), with \(\sum_{h\in H}x_{t,h}+x_{t,0}=\mu_t\) and \(\sum_{t\in T}x_{t,h}\leq q_h\), that first lexicographically maximizes \(r(x)=\sum_{t,h:v_t(h)>0}x_{t,h}\) and the minimum positive value used, then has maximum per-capita total envy at most \(B\). Here \(y_g=\sum_t x_{t,g}\), \(v_t(0)=0\), and the envy for a type-\(t\) person assigned \(h\in H\cup\{0\}\) is \(E_t(h;x)=\sum_{g\in H}y_g\max\{v_t(g)-v_t(h),0\}\); take the maximum over every \((t,h)\) with \(x_{t,h}>0\).
A society is given by its support: the list \(T\) of its \(\tau\) valuation types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) house categories \(H\), nonnegative rational valuations \(v_t(h)\), nonnegative rational supplies \(q_h\) per applicant, and a nonnegative rational threshold \(B\). Valuation ties are allowed. Let \(L\) be the total binary input length.
An assignment consists of real masses \(x_{t,h},x_{t,0}\geq0\) satisfying \(\sum_{h\in H}x_{t,h}+x_{t,0}=\mu_t\) and \(\sum_{t\in T}x_{t,h}\leq q_h\). The outcome \(0\) means unassigned, with \(v_t(0)=0\); zero-valued house assignments are allowed and supplies may remain unused.
Define \(r(x)=\sum_{t\in T}\sum_{h\in H:v_t(h)>0}x_{t,h}\) and \(\beta(x)=\min\{v_t(h):h\in H,\ x_{t,h}>0,\ v_t(h)>0\}\), setting \(\beta(x)=0\) when \(r(x)=0\).
Call an assignment efficient if it lexicographically maximizes \((r(x),\beta(x))\) over all feasible assignments, first maximizing positively served mass and then its minimum received value.
Set \(y_g=\sum_{t\in T}x_{t,g}\) and \(E_t(h;x)=\sum_{g\in H}y_g\max\{v_t(g)-v_t(h),0\}\). Define \(M(x)=\max\{E_t(h;x):t\in T,\ h\in H\cup\{0\},\ x_{t,h}>0\}\), including unassigned and zero-valued recipients.
The decision problem asks whether an efficient assignment exists with \(M(x)\leq B\).
Is this decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite agents and individual houses, minimizing maximum aggregate envy among allocations maximizing the corresponding egalitarian efficiency is NP-hard; its threshold decision version is NP-complete. [Source](https://journals.sagepub.com/doi/pdf/10.3233/FAIA240920).
No result settling exactly the mass-assignment decision problem above was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when all valuations belong to \(\{0,1,2,3\}\), all masses and supplies are dyadic rationals, and every efficient assignment positively serves the entire population.
The key is that the envy constraint can force a valuation type to make an indivisible choice, despite allowing real assignment masses.
First, the optimal efficiency pair can be computed in polynomial time.
Construct a flow network with source-to-type capacities \(\mu_t\), type-to-house arcs whenever \(v_t(h)>0\), and house-to-sink capacities \(q_h\). Each type-to-house capacity can be set to \(1\), since total population mass is \(1\). Its maximum flow value is exactly the maximum positively served mass, denoted \(r^*\): every assignment induces such a flow, and every such flow extends to an assignment by leaving the remaining mass unassigned.
If \(r^*=0\), the answer is yes: the entirely unassigned assignment is efficient and has \(M=0\).
Suppose \(r^*>0\). For each distinct positive input valuation \(b\), retain only type-to-house arcs satisfying \(v_t(h)\geq b\). The optimal bottleneck value \(\beta^*\) is the largest \(b\) for which this network still admits flow \(r^*\). Indeed, such a flow gives an assignment with positively served mass \(r^*\) and bottleneck at least \(b\), and conversely any such assignment gives the required flow. There are at most \(\tau m\) candidate values, so rational maximum-flow computations determine \(r^*\) and \(\beta^*\) in polynomial time.
Now guess a set \(S\subseteq T\times(H\cup\{0\})\) of permitted assignment coordinates. Check feasibility of the following rational linear program:
\(\displaystyle \sum_{g\in H}\left(\sum_{u\in T}x_{u,g}\right)\max\{v_t(g)-v_t(h),0\}\leq B.\)
These are linear constraints: every coefficient involving valuations is a fixed input rational. Their number and binary encoding length are polynomial in the input length, and rational linear-program feasibility is decidable in polynomial time.
If the program is feasible, every positive assignment coordinate belongs to \(S\), so all relevant envy inequalities hold. The assignment has \(r=r^*\) and \(\beta\geq\beta^*\), hence is efficient. Conversely, any desired assignment makes the program feasible when \(S\) is its actual support.
Thus a polynomial-size guessed set \(S\), followed by polynomial-time verification, establishes membership in \(\mathrm{NP}\).
We use the standard \(\mathrm{NP}\)-complete Independent Set problem: given a simple graph \(G=(V,E)\) and an integer \(k\), decide whether there is a set of at least \(k\) vertices containing no adjacent pair. We restrict to \(n=|V|\geq1\) and \(1\leq k\leq n\); instances outside these bounds are trivial.
Write \(s=|E|\), and define
\(\displaystyle \ell=\lceil\log_2(n+s+1)\rceil,\qquad \delta=2^{-\ell},\qquad \rho=1-(n+s)\delta-\frac{\delta}{2}.\)
Since \(2^\ell\geq n+s+1\), we have \(\rho\geq\delta/2>0\). All these quantities are dyadic rationals.
Create the following types:
| Type | Mass | Nonzero valuations |
|---|---:|---|
| Vertex type \(t_i\), for each \(i\in V\) | \(\delta\) | \(v_{t_i}(S_i)=2,\ v_{t_i}(C)=1,\ v_{t_i}(D)=3\) |
| Edge type \(t_e\), for each \(e=\{i,j\}\in E\) | \(\delta\) | \(v_{t_e}(S_i)=v_{t_e}(S_j)=2,\ v_{t_e}(P_e)=1\) |
| Reserved type \(t_D\) | \(\delta/2\) | \(v_{t_D}(D)=1\) |
| Filler type \(t_F\) | \(\rho\) | \(v_{t_F}(F)=1\) |
Every valuation not listed is zero. The masses sum to \(1\).
The houses are the vertex houses \(S_i\), edge houses \(P_e\), and three additional houses \(C,D,F\). Set supplies and threshold as follows:
\(\displaystyle q_{S_i}=\delta,\qquad q_{P_e}=\delta,\qquad q_C=(n-k)\delta,\qquad q_D=\frac{\delta}{2},\qquad q_F=\rho,\qquad B=\delta.\)
The types have distinct valuation vectors. The construction has \(\tau=n+s+2\) types and \(m=n+s+3\) houses, and its total binary encoding length is polynomial in the graph input length.
An assignment with \(r=1\) exists: assign each vertex type entirely to its own \(S_i\), each edge type entirely to its \(P_e\), and the two remaining types to \(D\) and \(F\), respectively. Consequently, \(r^*=1\).
For any assignment with \(r=1\), no mass can be unassigned or assigned to a zero-valued house. This follows because the total mass is \(1\), while \(r\) counts exactly the mass assigned along positive-valued coordinates.
In particular, type \(t_D\) must receive its entire mass at \(D\), its only positively valued house. Hence its received value is \(1\), so \(\beta\leq1\). Every positive input valuation is at least \(1\), so also \(\beta\geq1\).
Therefore \(\beta^*=1\), and an assignment in this instance is efficient exactly when \(r=1\).
Suppose \(I\subseteq V\) is independent and \(|I|\geq k\). Assign:
The supply of \(C\) suffices because \((n-|I|)\delta\leq(n-k)\delta\). All other supply constraints hold directly. Every type is positively served, so the assignment is efficient.
Its house totals satisfy \(y_D=\delta/2\) and \(y_{S_i}=\delta\) for \(i\in I\), with \(y_{S_i}=0\) otherwise.
For a selected vertex type, the only house valued above its received value \(2\) is \(D\). Thus
\(\displaystyle E_{t_i}(S_i;x)=y_D(3-2)=\frac{\delta}{2}\leq B.\)
For an unselected vertex type receiving \(C\),
\(\displaystyle E_{t_i}(C;x)=y_D(3-1)+y_{S_i}(2-1)=\delta=B.\)
For an edge \(e=\{i,j\}\),
\(\displaystyle E_{t_e}(P_e;x)=y_{S_i}+y_{S_j}\leq\delta=B,\)
because independence ensures at most one endpoint belongs to \(I\).
Types \(t_D,t_F\) receive their highest-valued houses, so their envy is zero. These are all occupied coordinates; therefore \(M(x)\leq B\).
Conversely, suppose an efficient assignment satisfies \(M(x)\leq B=\delta\). By Section 3, it has \(r=1\), so all mass is assigned along positive-valued coordinates.
Type \(t_D\) must receive mass \(\delta/2\) at \(D\). This exhausts its supply, implying
\(\displaystyle y_D=\frac{\delta}{2}\)
and preventing every other type from receiving \(D\).
Each vertex type \(t_i\) can therefore receive only \(S_i\) and \(C\), giving
\(\displaystyle x_{t_i,S_i}+x_{t_i,C}=\delta.\)
If \(x_{t_i,C}>0\), the envy constraint at that occupied coordinate implies
\(\displaystyle \delta+y_{S_i}=2y_D+y_{S_i}=E_{t_i}(C;x)\leq B=\delta.\)
Nonnegativity gives \(y_{S_i}=0\). Hence \(x_{t_i,S_i}=0\) and \(x_{t_i,C}=\delta\).
If instead \(x_{t_i,C}=0\), then \(x_{t_i,S_i}=\delta\). Since \(q_{S_i}=\delta\), this implies \(y_{S_i}=\delta\) and exhausts the house’s supply.
Thus every vertex type is assigned entirely to either \(C\) or \(S_i\). Moreover, no other type can receive any \(S_i\): when its vertex is unselected, the house total is zero; when selected, the vertex type exhausts its supply.
Define
\(\displaystyle I=\{i\in V:x_{t_i,S_i}=\delta\}.\)
An edge type \(t_e\), where \(e=\{i,j\}\), positively values only \(S_i,S_j,P_e\). The first two cannot accommodate it, by the preceding argument. Therefore it receives its entire mass at \(P_e\).
The envy constraint there gives
\(\displaystyle y_{S_i}+y_{S_j}=E_{t_e}(P_e;x)\leq\delta.\)
Each endpoint total is either \(0\) or \(\delta\). Hence both endpoints cannot belong to \(I\). This proves that \(I\) is independent.
Only vertex types positively value \(C\). Since zero-valued assignments are absent, its total assigned mass is
\(\displaystyle y_C=(n-|I|)\delta.\)
The supply constraint yields
\(\displaystyle (n-|I|)\delta\leq(n-k)\delta.\)
As \(\delta>0\), it follows that \(|I|\geq k\).
The construction is polynomial and satisfies both directions of the equivalence: the graph has an independent set of size at least \(k\) exactly when the society admits an efficient assignment with \(M(x)\leq B\).
Together with membership in \(\mathrm{NP}\), this proves \(\mathrm{NP}\)-completeness for the stated mass-assignment problem.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the stated continuous mass-assignment problem. The reduction establishes NP-hardness despite allowing arbitrary real assignment masses, and the support-guessing argument establishes membership in \(\mathrm{NP}\). I found no major or minor mathematical issues.
The flow formulation correctly computes the maximum positively served mass.
Consequently, the maximum flow value is exactly \(r^*\). All network capacities are input rationals, and the network has polynomial size, so the stated polynomial-time rational maximum-flow computation applies.
The case \(r^*=0\) is handled correctly. The entirely unassigned assignment has efficiency pair \((0,0)\), and all house totals vanish, giving \(M=0\leq B\).
For \(r^*>0\), the bottleneck search is also correct. Every assignment with positive served mass has a bottleneck belonging to the finite set of positive input valuations. Restricting the flow network to coordinates with valuation at least \(b\) characterizes whether an assignment with \(r=r^*\) and \(\beta\geq b\) exists. Taking the largest successful candidate therefore computes \(\beta^*\). There are at most \(\tau m\) candidates.
No attainment or domain issue is left unresolved here: the candidates form a finite nonempty set, and the successful flow networks provide the required assignments.
The guessed set \(S\) has polynomial encoding length because there are only \(\tau(m+1)\) possible assignment coordinates.
For a fixed \(S\), every listed constraint is linear with rational coefficients. In particular, the envy coefficients are fixed numbers
\[
\max\{v_t(g)-v_t(h),0\},
\]
rather than expressions depending on assignment variables. Their binary encoding lengths remain polynomial in the input length. The stated polynomial-time theorem for rational linear-program feasibility therefore applies to this system.
Both implications are valid:
Allowing coordinates in \(S\) to receive zero mass creates no problem: this only imposes additional inequalities, and the converse uses the actual support.
The verifier can decide feasibility directly in polynomial time after receiving \(S\); it need not receive or encode an arbitrary real assignment. The membership claim is established.
The source problem is stated precisely: Independent Set on simple graphs, with the target cardinality interpreted as “at least \(k\).” Restricting to \(n\geq1\) and \(1\leq k\leq n\) removes only trivial cases and preserves the hardness claim.
The numerical construction satisfies the task’s input requirements. From
\[
2^\ell\geq n+s+1
\]
one obtains the claimed bound
\[
\rho=1-(n+s)\delta-\frac{\delta}{2}\geq\frac{\delta}{2}>0.
\]
Thus all type masses are strictly positive. Their sum is exactly
\[
(n+s)\delta+\frac{\delta}{2}+\rho=1.
\]
All masses and supplies are dyadic rationals. The supply of \(C\) is nonnegative because \(k\leq n\), and the threshold is positive. Every valuation belongs to the stated set \(\{0,1,2,3\}\).
The valuation vectors are distinct: vertex types have their respective \(S_i\) coordinates, edge types have their respective \(P_e\) coordinates, and the reserved and filler types have their specified distinct vectors. Hence the claimed \(\tau=n+s+2\) is indeed the support size, as required by the task.
The construction uses polynomially many types, houses, and valuation entries, with polynomial-length rational encodings.
The displayed assignment serving every vertex at \(S_i\), every edge at \(P_e\), and the remaining types at \(D,F\) respects all supplies and gives \(r=1\). Since total population mass is \(1\), this proves \(r^*=1\).
When \(r=1\), the assignment conservation constraints leave no mass for outcome \(0\) or zero-valued coordinates. The reserved type must therefore receive all of its mass at \(D\), its only positive-valued house.
This guarantees a positive occupied coordinate of value \(1\), so \(\beta\leq1\). All positive valuations are at least \(1\), so \(\beta\geq1\). Consequently, every assignment with \(r=1\) has \(\beta=1\), and efficiency is exactly equivalent to \(r=1\).
This reasoning correctly accounts for the task’s allowance of zero-valued assignments and unused supplies.
For an independent set \(I\) with \(|I|\geq k\), the proposed assignment is feasible. Its use of \(C\) is
\[
(n-|I|)\delta\leq(n-k)\delta,
\]
and every other used house respects its specified capacity. Every type receives a positive-valued house, so the assignment is efficient.
The envy computations include every occupied coordinate:
All these quantities are at most \(B=\delta\). No unassigned or zero-valued recipients require additional checks because none occur in this assignment.
Efficiency forces \(r=1\). The reserved type therefore fills \(D\), establishing \(y_D=\delta/2\) and preventing any vertex type from receiving \(D\).
Each vertex type can then receive positive mass only at \(S_i\) and \(C\). If it receives any mass at \(C\), that occupied coordinate imposes
\[
E_{t_i}(C;x)=2y_D+y_{S_i}=\delta+y_{S_i}\leq\delta.
\]
Nonnegativity forces \(y_{S_i}=0\), and hence the vertex’s entire mass goes to \(C\).
If it receives no mass at \(C\), its entire mass \(\delta\) goes to \(S_i\), filling that house’s capacity. Thus the asserted indivisible choice follows from the constraints even though assignments may use arbitrary real masses.
The resulting statement that no other type can receive any \(S_i\) is justified in both cases: an unselected house has zero total assignment, while a selected house is already filled by its vertex type.
Every edge type must consequently receive all its mass at \(P_e\). Its occupied-coordinate inequality gives
\[
y_{S_i}+y_{S_j}\leq\delta.
\]
Since each endpoint total is either \(0\) or \(\delta\), adjacent vertices cannot both be selected.
Finally, only vertex types can occupy \(C\) in an assignment with \(r=1\). Therefore
\[
y_C=(n-|I|)\delta\leq(n-k)\delta,
\]
and division by the strictly positive \(\delta\) yields \(|I|\geq k\).
The reverse implication is complete.
Both directions of the polynomial reduction hold, and the membership argument covers the full input domain of the original task. The prover establishes \(\mathrm{NP}\)-completeness, including the claimed restricted family. 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.