Answer: \(\mathrm{NP}\text{-complete}\) for every fixed rational \(c\in(0,1)\).
Theorem 6 — class: hardness
Given housing categories \(H\), a finite support \(T\) of complete strict preference rankings, rational type masses \(\mu_t\) summing to \(1\), rational per-capita capacities \(q_h\), and fixed rational \(c\in(0,1)\), does there exist a feasible assignment \(x_{t,a}\) of each type’s mass to an acceptable category or to being unmatched such that every feasible reassignment \(z_{t,a,b}\) of the same mass, respecting capacities \(q_h\), has strictly improving mass \(\sum_{t,a,b:\,b\succ_t a}z_{t,a,b}<c\)?
Let \(H\) be a finite set of housing categories, with \(m=|H|\), and put \(A=H\cup\{\bot\}\), where \(\bot\) denotes being unmatched. Each type \(t\) has a complete strict ranking \(\succ_t\) of \(H\); every category is acceptable and ranks above \(\bot\). Categories have no preferences.
A society is given by its support: the list \(T\) of the \(\tau\) types with positive mass, each with its mass \(\mu_t\) as a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible rankings. Capacities \(q_h\) are nonnegative binary rationals; their sum is unrestricted. Let \(L\) be the total input bit length.
A feasible assignment consists of real masses \(x_{t,a}\geq0\) satisfying \(\sum_{a\in A}x_{t,a}=\mu_t\) and \(\sum_t x_{t,h}\leq q_h\) for every \(h\in H\).
A feasible reassignment of \(x\) consists of real masses \(z_{t,a,b}\geq0\), indexed by \(t\in T\) and \(a,b\in A\), satisfying \(\sum_b z_{t,a,b}=x_{t,a}\) and \(\sum_{t,a}z_{t,a,h}\leq q_h\) for every \(h\in H\). Mass may stay, improve, worsen, or become unmatched; unmatched mass has no capacity bound.
For a fixed rational \(c\in(0,1)\), call \(x\) stable at threshold \(c\) if every feasible reassignment satisfies \(\sum_{t,a,b:\,b\succ_t a}z_{t,a,b}<c\).
For each fixed rational \(c\in(0,1)\), is deciding whether an assignment stable at threshold \(c\) exists in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
In discrete house allocation with complete strict preferences and unit-capacity objects, existence of a matching for which every alternative strictly improves fewer than \(cn\) of the \(n\) agents is \(\mathrm{NP}\)-complete for every fixed \(c\in(0,1)\). [Aziz, Csáji, and Cseh](https://cgi.cse.unsw.edu.au/~haziz/kstable.pdf)
No prior result settling this exact mass-and-reassignment formulation was located in the literature search.
For every fixed rational \(c\in(0,1)\), the decision problem is \(\mathrm{NP}\)-complete, and hence \(\mathrm{NP}\)-hard.
The key point is that maximum improving mass is a concave function of the initial assignment. Consequently, whenever a stable assignment exists, a stable vertex of the assignment polytope exists. On instances obtained by scaling a discrete house-allocation instance, every such vertex represents a discrete matching.
Let \(P\) denote the polytope of feasible assignments. For \(x\in P\), define
\(\displaystyle F(x)=\max_z\sum_{t,a,b:\,b\succ_t a}z_{t,a,b},\)
where the maximum ranges over all feasible reassignments of \(x\).
This maximum exists. The reassignment keeping everyone at their current outcome is feasible. Moreover, every reassignment coordinate lies between zero and its corresponding \(x_{t,a}\), and the constraints define a closed set. Thus the feasible reassignment set is nonempty and compact.
It follows, including at the strict boundary, that
\(\displaystyle x\text{ is stable at threshold }c\quad\Longleftrightarrow\quad F(x)<c.\)
Lemma 1. For rational \(x\), the value \(F(x)\) is computable exactly in polynomial time.
Proof. Construct a directed network with source \(s\), sink \(r\), a node \(u_{t,a}\) for each pair \((t,a)\), and a node for each category \(h\in H\). Its arcs are:
The capacity one on intermediate arcs suffices because the total population mass is one.
Any feasible reassignment induces a flow consisting of its improving movements. Its value is exactly the improving mass. Conversely, given a feasible flow, put
\(\displaystyle z_{t,a,h}=f(u_{t,a},h)\quad\text{whenever }h\succ_t a,\)
and send every remaining part of each row to \(\bot\):
\(\displaystyle z_{t,a,\bot}=x_{t,a}-\sum_{h\succ_t a}f(u_{t,a},h).\)
Set all other coordinates to zero. Flow conservation makes the residual nonnegative, and the category-to-sink capacities ensure feasibility. Since no movement to \(\bot\) is improving, the improving mass equals the flow value.
Therefore \(F(x)\) is the maximum-flow value. The network has polynomially many vertices and arcs, and exact maximum flow with binary rational capacities is polynomial-time computable. \(\square\)
The ability to send all nonimproving residual mass to \(\bot\) is essential to this equivalence and is explicitly allowed by the problem.
Lemma 2. The function \(F\) is concave on \(P\).
Proof. Take \(x,x'\in P\), and let \(z,z'\) be maximizing reassignments for them. For \(\lambda\in[0,1]\), the reassignment
\(\displaystyle \widehat z=\lambda z+(1-\lambda)z'\)
has row sums \(\lambda x+(1-\lambda)x'\). For every category, its incoming mass is at most
\(\displaystyle \lambda q_h+(1-\lambda)q_h=q_h.\)
Hence it is feasible for \(\lambda x+(1-\lambda)x'\). Linearity of the improving-mass objective gives
\(\displaystyle F\bigl(\lambda x+(1-\lambda)x'\bigr)\geq \lambda F(x)+(1-\lambda)F(x').\)
This is concavity. \(\square\)
Corollary 3. If a stable assignment exists, a stable vertex of \(P\) exists.
Proof. The polytope \(P\) is nonempty, because everyone may be unmatched. It is bounded, because \(0\leq x_{t,a}\leq\mu_t\), and is defined by finitely many linear constraints. Consequently, every point \(x\in P\) is a finite convex combination of vertices:
\(\displaystyle x=\sum_i\lambda_i v_i,\qquad \lambda_i\geq0,\qquad \sum_i\lambda_i=1.\)
By Lemma 2,
\(\displaystyle F(x)\geq\sum_i\lambda_iF(v_i)\geq\min_iF(v_i).\)
If \(F(x)<c\), some vertex therefore satisfies \(F(v_i)<c\). \(\square\)
In fact, the same argument proves
\(\displaystyle \min_{x\in P}F(x)=\min_{v\in\operatorname{vert}(P)}F(v).\)
Lemma 4. Suppose \(D\) is a positive integer such that every \(D\mu_t\) and \(Dq_h\) is integral. At every vertex \(v\) of \(P\), every coordinate \(Dv_{t,a}\) is integral.
Proof. Write \(y_{t,a}=Dx_{t,a}\), and introduce a nonnegative slack \(s_h\) for each category. The scaled constraints become
\(\displaystyle \sum_{a\in A}y_{t,a}=D\mu_t,\)
\(\displaystyle -\sum_t y_{t,h}-s_h=-Dq_h.\)
Let \(B\) be their coefficient matrix. A column for \(y_{t,h}\) has a positive one in its type row and a negative one in its category row. A column for \(y_{t,\bot}\) has only a positive one; a slack column has only a negative one.
This matrix is totally unimodular. Indeed, in any square submatrix, a column with at most one nonzero entry permits determinant expansion and induction. If every column has two nonzero entries, those entries have opposite signs, so the sum of the rows is zero and the determinant vanishes. Thus every square minor belongs to \(\{0,1,-1\}\).
The matrix has full row rank: the unmatched-variable columns and slack columns supply signed unit vectors for all rows. At a vertex of the standard-form polyhedron, the columns corresponding to positive variables are linearly independent; otherwise a sufficiently small perturbation in both directions along a dependence would contradict extremality. Extend those columns to a nonsingular square basis. Its determinant is positive or negative one, so its solution is integral by Cramer’s rule, since the right-hand side is integral.
Finally, the slacks are uniquely determined by \(y\), and scaling and adding these slacks preserve vertices. Hence every \(Dv_{t,a}\) is integral. \(\square\)
We use the discrete hardness theorem stated in the question: for every fixed rational \(c\in(0,1)\), deciding whether a discrete house-allocation instance with complete strict preferences admits a matching for which every alternative improves fewer than \(cn\) agents is \(\mathrm{NP}\)-complete. This is the complete-preference result of [Aziz, Csáji, and Cseh, Theorem 5.7](https://cgi.cse.unsw.edu.au/~haziz/kstable.pdf).
Take such an instance with \(n\) agents and unit-capacity objects \(H\). Group agents with identical rankings into types. If type \(t\) contains \(n_t\) agents, set
\(\displaystyle \mu_t=\frac{n_t}{n},\qquad q_h=\frac1n\quad(h\in H).\)
This construction is polynomial-time: the support has at most \(n\) types, each mass and capacity has polynomial encoding length, and all rankings remain complete and strict.
For a discrete matching \(M\), define its aggregate assignment by
\(\displaystyle x^M_{t,a}=\frac{|\{i:\ i\text{ has type }t,\ M(i)=a\}|}{n}.\)
Let \(I(M)\) be the maximum number of agents strictly improved by any alternative matching.
Lemma 5. For every discrete matching \(M\),
\(\displaystyle F(x^M)=\frac{I(M)}n.\)
Proof. Every alternative matching induces a feasible reassignment, assigning mass \(1/n\) to each agent’s movement. Therefore \(F(x^M)\geq I(M)/n\).
For the reverse inequality, multiply all capacities in the network of Lemma 1 by \(n\). Source-to-row capacities become integer numbers of agents currently assigned to each pair \((t,a)\). Intermediate capacities become \(n\), and each category-to-sink capacity becomes one.
All capacities are integral, so the integral maximum-flow theorem supplies an integral maximum flow. Each unit routed from a row \((t,a)\) can be assigned to a distinct agent currently in that row. There are enough such agents by the source capacity. Every selected agent receives a strictly better category, and each category is given to at most one agent. Leave all other agents unmatched.
This produces an alternative discrete matching improving exactly \(nF(x^M)\) agents. Hence \(I(M)\geq nF(x^M)\), proving equality. \(\square\)
We now prove both directions of the reduction.
Forward direction. If \(M\) satisfies \(I(M)<cn\), Lemma 5 gives
\(\displaystyle F(x^M)=I(M)/n<c.\)
Thus the mass instance admits a stable assignment.
Reverse direction. Suppose the mass instance admits a stable assignment. By Corollary 3, it admits a stable vertex \(v\). Apply Lemma 4 with \(D=n\). Every \(nv_{t,a}\) is a nonnegative integer, and these integers sum to \(n_t\) within each type. Furthermore,
\(\displaystyle \sum_t nv_{t,h}\leq1\quad(h\in H).\)
Thus these counts can be realized by a discrete matching \(M\): assign the indicated number of agents of each type to each outcome. Its aggregate assignment is \(v\). Lemma 5 then gives
\(\displaystyle I(M)=nF(v)<cn.\)
This proves exact equivalence. In particular, arbitrary real splitting introduces no additional yes-instances.
The strict threshold is preserved literally. Since \(I(M)\) is integral, \(I(M)<cn\) equivalently means \(I(M)\leq\lceil cn\rceil-1\); no approximation is involved.
For arbitrary rational input, let \(D\) be the product of the denominators of all masses and capacities. Its binary length is \(O(L)\), and it makes every scaled mass and capacity integral.
If the instance is a yes-instance, Corollary 3 and Lemma 4 supply a stable vertex \(v\) whose coordinates have the form \(k_{t,a}/D\). Since every assignment coordinate lies in \([0,1]\), each numerator satisfies \(0\leq k_{t,a}\leq D\). Therefore this assignment has polynomial encoding length.
A verifier checks its feasibility, computes \(F(v)\) exactly using Lemma 1, and checks the strict rational inequality \(F(v)<c\). All these operations take time polynomial in \(m,\tau,L\).
Combining membership with the reduction proves \(\mathrm{NP}\)-completeness for every fixed rational \(c\in(0,1)\). A polynomial-time algorithm in \(m,\tau,L\) would therefore imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the assigned problem: for every fixed rational \(c\in(0,1)\), the decision problem is \(\mathrm{NP}\)-complete. I found no major or minor mathematical issues.
Keeping every mass at its current outcome satisfies the reassignment constraints because the initial assignment is feasible. Every reassignment coordinate satisfies \(0\leq z_{t,a,b}\leq x_{t,a}\). The feasible set is closed, bounded, and nonempty in a finite-dimensional space, so the linear objective attains its maximum.
Consequently, the equivalence between stability and \(F(x)<c\) is correct. Attainment is essential here: if \(F(x)=c\), a feasible reassignment actually achieves the prohibited improving mass.
The network correctly includes all potentially improving movements, including movements from \(\bot\) to any category. No improving movement has destination \(\bot\).
In the reassignment-to-flow direction, the improving mass leaving each row is at most its row sum \(x_{t,a}\), and the improving mass entering each category is at most its total incoming reassignment mass, hence at most \(q_h\). These quantities therefore define a feasible flow with the claimed value.
In the flow-to-reassignment direction, flow conservation and the source capacities ensure that each residual row mass is nonnegative. Sending that residual to \(\bot\) completes every row without consuming category capacity or adding improving mass. This remains valid when the original outcome is already \(\bot\).
Intermediate capacity one is sufficient because total population mass is one. The network has \(\tau(m+1)+m+2\) vertices and at most \(\tau m(m+1)+\tau(m+1)+m\) arcs, so its size is polynomial.
The exact polynomial-time maximum-flow assertion applies to binary rational capacities. Its running time includes the encoding length of the supplied rational assignment. Thus Lemma 1 is valid.
The convex combination of maximizing reassignments has precisely the required convex-combination row sums. Its incoming category masses remain bounded by the same fixed capacities \(q_h\).
Its objective value is the convex combination of the two maximum values, establishing the stated concavity inequality. The direction of that inequality is correct.
The assignment polytope is nonempty and bounded, so the finite convex-combination representation by vertices applies. Concavity then gives
\(F(x)\geq\sum_i\lambda_iF(v_i)\geq\min_iF(v_i)\).
Therefore \(F(x)<c\) implies that some vertex also has value below \(c\). No continuity assumption or limiting argument is needed, and the strict inequality survives.
The additional equality between the minimum over assignments and the minimum over vertices follows from the same inequality and the inclusion of vertices in the polytope.
The scaled equations and slack signs are correct. Every column of the coefficient matrix has at most two nonzero entries, and any two have opposite signs.
The determinant argument establishes total unimodularity: expansion handles a column with at most one nonzero entry, while a square submatrix whose columns all contain two opposite entries has dependent rows.
The unmatched and slack columns establish full row rank. The argument that positive-variable columns at a vertex must be independent is valid because a sufficiently small perturbation supported on those positive coordinates preserves nonnegativity in both directions.
Extending those columns to a square basis and applying Cramer’s rule with integral right-hand side yields integral coordinates. Scaling and adjoining uniquely determined slacks preserve extremality. Thus the lemma applies to all rational capacities, including zero capacities and capacities exceeding total population mass.
The cited Theorem 5.7 states the complete, strict house-allocation hardness result for every fixed \(0<c<1\). The paper’s definitions allow unmatched agents, rank acceptable objects above being unmatched, and count improvements without requiring other agents to avoid worsening. These hypotheses match the reduction. [Aziz, Csáji, and Cseh, definitions and Theorem 5.7](https://cgi.cse.unsw.edu.au/~haziz/kstable.pdf).
The prover also explicitly uses the discrete threshold theorem as stated in USER_TASK. Therefore its source problem has exactly the required strict improvement threshold; no unsupported rounding change is introduced.
Grouping identical rankings preserves all preference information relevant to improvement. The resulting support has at most \(n\) types, and masses \(n_t/n\) and capacities \(1/n\) have polynomial encoding length.
Each alternative discrete matching produces a feasible reassignment with improving mass equal to its improving-agent count divided by \(n\).
Conversely, scaling the flow network by \(n\) gives integral capacities. The integral maximum-flow theorem applies to this finite network and supplies an integral optimum. Source capacities bound the number of selected agents in each original row, and category capacities one prevent duplicate allocation of an object.
Leaving all unselected agents unmatched is permitted. Such agents cannot become strictly better through that movement, so the constructed matching improves exactly the claimed number. Hence \(F(x^M)=I(M)/n\) is established in both directions.
The forward implication follows directly from Lemma 5.
For the reverse implication, Corollary 3 supplies a stable vertex, and Lemma 4 applies with \(D=n\). Its scaled coordinates are integral, sum to the correct number \(n_t\) of agents within each type, and assign at most one agent to each object. They therefore represent a discrete matching whose aggregate assignment is that vertex.
Applying Lemma 5 preserves the strict threshold exactly. The arithmetic equivalence \(I(M)<cn\) if and only if \(I(M)\leq\lceil cn\rceil-1\) is correct, including when \(cn\) is integral.
The product of all input denominators has binary length \(O(L)\), even though its numerical value may be large. It clears every mass and capacity denominator.
The stable vertex guaranteed by the earlier lemmas has coordinates \(k_{t,a}/D\), with \(0\leq k_{t,a}\leq D\). There are \(\tau(m+1)\) coordinates, each of polynomial encoding length. This gives a polynomial-size certificate despite allowing arbitrary real assignments in the problem definition.
Feasibility and the strict comparison with fixed rational \(c\) can be checked exactly in polynomial time, using Lemma 1. Thus membership in \(\mathrm{NP}\) is proved.
No repair or additional clarification is needed. The proof handles the relevant degeneracies: zero capacities, unrestricted total capacity, unmatched mass, and an empty category set.
⟨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.