Answer: \(\mathrm{NP}\)-complete, hence \(\mathrm{NP}\)-hard; hardness holds already with \(d=1\) and guaranteed feasibility.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateSMTI-DIVERSE is ΣP 2-complete, and remains ΣP 2-hard even if feasible matchings always exist, there are no ties, m = 4, and u∞= 3.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type support \(T\), rational masses \(\mu_\theta>0\) summing to \(1\), attribute vectors \(a_\theta\), and each type’s preferences over acceptable colleges, decide whether there exists a mass assignment \(x_{\theta,w}\ge 0\) satisfying \(\sum_w x_{\theta,w}\le\mu_\theta\), each college’s per-capita capacity \(q_w\), and attribute quota shares \(\ell_{wz}\le\sum_\theta a_\theta[z]x_{\theta,w}\le u_{wz}\), with no positive-mass blocking opportunity. Such an opportunity exists if, for some type \(\theta\), college \(w\), and current destination \(k\in W\cup\{\perp\}\), \(x_{\theta,k}>0\) and \(\theta\) prefers \(w\) to \(k\), and some \(\delta>0\) of that mass can enter \(w\) by removing masses \(0\le y_s\le x_{s,w}\) only from types \(s\) that \(w\) ranks strictly below \(\theta\), while satisfying \(w\)’s capacity and quota constraints after the change. As in the paper’s local blocking convention, feasibility at the source college is not checked.
A society is given by its support \(T\): the list of \(\tau\) types with positive binary-rational masses \(\mu_\theta\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. There are \(m\ge1\) colleges \(W\) and \(d\ge1\) binary attributes, with \(a_\theta\in\{0,1\}^d\).
Each type has a weak preference order over its acceptable colleges; each college has a weak preference order over its acceptable types. Acceptability is mutual, every acceptable set is nonempty, and every acceptable college is strictly preferred to being unmatched, denoted \(\perp\). Members of a type share their attributes, preferences, and position in each college’s order; ties are allowed and are not broken.
Capacities and quotas are binary rationals satisfying \(0<q_w\le1\) and \(0\le\ell_{wz}\le u_{wz}\le1\). Quotas measure shares of the entire society, not shares of a college’s enrollment, and apply even to empty colleges.
A feasible assignment consists of real masses \(x_{\theta,w}\ge0\), zero on unacceptable pairs, satisfying \(\sum_{w\in W}x_{\theta,w}\le\mu_\theta\), \(\sum_{\theta\in T}x_{\theta,w}\le q_w\), and \(\ell_{wz}\le\sum_{\theta\in T}a_\theta[z]x_{\theta,w}\le u_{wz}\) for every college and attribute. Set \(x_{\theta,\perp}=\mu_\theta-\sum_{w\in W}x_{\theta,w}\).
A blocking opportunity consists of an acceptable pair \((\theta,w)\), a destination \(k\in W\cup\{\perp\}\) with \(x_{\theta,k}>0\) and \(w\succ_\theta k\), and real masses \(0<\delta\le x_{\theta,k}\), \(0\le y_s\le x_{s,w}\), where \(y_s=0\) unless \(\theta\succ_w s\). The destination vector \(x'_{s,w}=x_{s,w}-y_s+\delta\mathbf{1}_{s=\theta}\) must satisfy all capacity and attribute quotas at \(w\). All removals may be zero; feasibility at the source college is not checked. An assignment is stable if it has no blocking opportunity.
Is deciding whether a feasible stable mass assignment exists solvable in polynomial time, or is it NP-hard? State running times in \(m\), \(\tau\), \(d\), and the total input bit length \(L\).
The discrete existence problem is \(\Sigma_2^P\)-complete, remaining hard with strict preferences, four colleges, maximum attribute upper quota three, and guaranteed feasibility ([Chen–Ganian–Hamm](https://arxiv.org/pdf/2001.10087)).
Fractional stable solutions are known for a different model with categories partitioned at each college and quotas proportional to that college’s enrollment ([Nguyen–Vohra](https://web.ics.purdue.edu/~nguye161/proportional.pdf)); that result does not settle the fixed society-share quotas above. No result settling this exact mass problem was identified.
Result. The problem is \(\mathrm{NP}\)-complete, hence \(\mathrm{NP}\)-hard. Hardness already holds with \(\ d=1\), all types having that attribute, equal masses, and guaranteed feasibility. The proof uses the ties permitted in the question.
1. A discrete hardness source
We use the following established theorem: given two sets of equal size with incomplete preference lists and ties, deciding whether there is a perfect weakly stable matching is \(\mathrm{NP}\)-complete. Weak stability means that no mutually acceptable pair strictly prefers each other to their assigned partners. This is Theorem 1 of [Iwama–Manlove–Miyazaki–Morita, *Stable Marriage with Incomplete Lists and Ties*](https://eprints.gla.ac.uk/1066/1/ICALP99.pdf); their definition explicitly requires the matching to be perfect.
We can restrict the source problem to instances whose acceptability graph admits a perfect matching. To justify this restriction, test for a perfect matching in polynomial time. If none exists, replace the instance by this fixed negative instance:
Its unique perfect matching is \(\{(\alpha,v),(\beta,u)\}\), blocked by \((\alpha,u)\). Thus the replacement preserves the answer and has a perfect acceptable matching. Every vertex in every resulting source instance consequently has a nonempty acceptable set.
Let the resulting source instance have \(\ n\) agents on each side. Pad it with isolated acceptable pairs until each side has size \(\ N\), where \(\ N\) is the least power of two satisfying \(\ N\ge n\). Each added agent accepts only its paired partner. Padding preserves perfect weakly stable matching existence, and \(\ N<2n\).
2. Construction of the mass instance
Create one type for each left agent and one college for each right agent. Copy acceptability and preferences, including ties. Set
\(\displaystyle m=\tau=N,\qquad d=1,\qquad \mu_\theta=\frac1N,\qquad a_\theta[1]=1.\)
For every college, set
\(\displaystyle q_w=\ell_{w1}=u_{w1}=\frac1N.\)
These numbers are dyadic rationals. They satisfy all stated input conditions.
Every feasible assignment satisfies
\(\displaystyle \sum_\theta x_{\theta,w}=\frac1N\quad\text{for every }w.\)
Summing over the colleges gives total assigned mass \(\ 1\). Since the total available mass is also \(\ 1\), and no type can exceed its available mass, necessarily
\(\displaystyle \sum_w x_{\theta,w}=\frac1N,\qquad x_{\theta,\perp}=0\quad\text{for every }\theta.\)
The constructed instance is guaranteed feasible: any perfect matching in the source acceptability graph supplies a feasible assignment by putting mass \(\ 1/N\) on each matched pair.
3. Equivalence of stable existence
First suppose the source instance has a perfect weakly stable matching \(\ M\). Define \(\ x_{\theta,M(\theta)}=1/N\), with every other entry zero.
Suppose this mass assignment has a blocking opportunity at \(\ (\theta,w)\). Its positive source mass must be at \(\ k=M(\theta)\), so \(\ w\succ_\theta M(\theta)\). Let \(\ s=M^{-1}(w)\) be the unique incumbent at \(\ w\).
The college initially contains exactly \(\ 1/N\) mass. Its exact enrollment quota requires
\(\displaystyle \sum_t y_t=\delta>0.\)
Only \(\ s\) has positive mass there. Hence \(\ y_s>0\), which is permitted only if \(\ \theta\succ_w s\). Thus \(\ (\theta,w)\) blocks \(\ M\), contradicting weak stability. Therefore the mass assignment is stable.
Conversely, suppose the constructed instance has a feasible stable mass assignment \(\ x\). Form the bipartite graph \(\ H\) whose edges are precisely the pairs with \(\ x_{\theta,w}>0\).
For any set \(\ S\) of types, let \(\ \Gamma_H(S)\) denote its college neighbors. The equal row and column sums give
\(\displaystyle \frac{|S|}{N} =\sum_{\theta\in S}\sum_{w\in\Gamma_H(S)}x_{\theta,w} \le\sum_{w\in\Gamma_H(S)}\sum_\theta x_{\theta,w} =\frac{|\Gamma_H(S)|}{N}. \)
Therefore \(\ |\Gamma_H(S)|\ge |S|\) for every \(\ S\). Hall’s theorem supplies a perfect matching \(\ M\) contained in the positive support of \(\ x\).
We claim that \(\ M\) is weakly stable. Otherwise an acceptable pair \(\ (\theta,w)\) satisfies
\(\displaystyle w\succ_\theta M(\theta),\qquad \theta\succ_w M^{-1}(w).\)
Write \(\ k=M(\theta)\) and \(\ s=M^{-1}(w)\). Because \(\ M\) lies in the positive support,
\(\displaystyle \delta=\min\{x_{\theta,k},x_{s,w}\}>0.\)
Move this mass from \(\ k\) to \(\ w\), removing exactly \(\ \delta\) mass of \(\ s\) at \(\ w\). The removal is allowed because \(\ \theta\succ_w s\). The destination’s total enrollment and attribute mass remain exactly \(\ 1/N\), so all its constraints remain satisfied. This is a blocking opportunity for \(\ x\), a contradiction.
Consequently, the source instance has a perfect weakly stable matching if and only if the constructed instance has a feasible stable mass assignment. The construction has polynomial size and establishes \(\mathrm{NP}\)-hardness.
4. Polynomial verification of rational assignments
Let a rational assignment \(\ x\) have total encoding length \(\ B\). First check feasibility by exact rational arithmetic.
For each acceptable pair \(\ (\theta,w)\) and each \(\ k\in W\cup\{\perp\}\) satisfying \(\ w\succ_\theta k\), solve the following linear program:
The zero solution is feasible. The program is bounded, and its optimum is positive exactly when this triple admits a blocking opportunity. This equivalence follows directly from the definition; no source-college constraint is introduced.
There are at most \(\ \tau m(m+1)\) such programs, each with at most \(\ \tau+1\) variables and \(\ O(\tau+d)\) constraints. Exact rational linear programming therefore verifies stability in time
\(\displaystyle \tau m(m+1)\operatorname{poly}(\tau+d+L+B).\)
It remains to show that allowing arbitrary real assignments does not prevent polynomial certificates.
5. Polynomial-size rational certificates
Include unmatched masses as variables and impose the equalities
\(\displaystyle \sum_{w\in W}x_{\theta,w}+x_{\theta,\perp}=\mu_\theta.\)
Omit unacceptable college coordinates. Let \(\ P\) be the resulting feasible polytope. Its inequalities consist of coordinate nonnegativity, capacities, and the two bounds for every attribute quota.
We first prove a structural fact:
Blocking depends only on which coordinates are positive and which capacity and quota inequalities are tight.
Indeed, let \(\ x,z\in P\) have identical such patterns, and suppose \(\ x\) has a blocking opportunity with parameters \(\ \delta,y\), source \(\ k\), and destination \(\ w\). Define its destination direction by
\(\displaystyle v_s=\delta\mathbf1_{s=\theta}-y_s.\)
Every destination inequality tight at \(\ x\) has nonpositive change along \(\ v\), because the proposed destination vector is feasible. The same inequalities are tight at \(\ z\), so they remain satisfied along \(\ z_w+t v\) for every \(\ t\ge0\).
Every other destination inequality has strictly positive slack at \(\ z\), so it remains satisfied for sufficiently small positive \(\ t\). Moreover:
Thus we can choose \(\ t>0\) small enough that \(\ t\delta\le z_{\theta,k}\) and \(\ ty_s\le z_{s,w}\) for every removal. The scaled parameters \(\ t\delta,ty\) give a blocking opportunity at \(\ z\). Interchanging \(\ x,z\) proves the structural fact.
Now suppose a real stable point \(\ x\in P\) exists. Write the inequalities of \(\ P\) as \(\ A_i z\le b_i\), and let \(\ I\) be those tight at \(\ x\). Consider the rational linear program maximizing \(\ \varepsilon\), subject to the mass equalities and
\(\displaystyle A_i z=b_i\ \ (i\in I),\qquad A_j z+\varepsilon\le b_j\ \ (j\notin I),\qquad 0\le\varepsilon\le1. \)
This program has a feasible point with \(\ \varepsilon>0\): take \(\ z=x\) and choose \(\ \varepsilon\) smaller than every positive slack. Its feasible region is bounded because \(\ z\in P\) and every coordinate lies in \(\ [0,1]\).
Hence it has an optimal rational vertex \(\ (z^*,\varepsilon^*)\) with \(\ \varepsilon^*>0\). The point \(\ z^*\) has exactly the same tight inequalities, and therefore the same positive coordinates, as \(\ x\). By the structural fact, \(\ z^*\) is stable.
For completeness, let \(\ n_P\le\tau(m+1)\) be the number of assignment coordinates. All coefficients of the auxiliary program belong to \(\ \{-1,0,1\}\). A common denominator for its rational right-hand sides has bit length \(\ O(L)\). Cramer’s rule and Hadamard’s determinant bound therefore give coordinate bit lengths
\(\displaystyle O\bigl(L+(n_P+1)\log(n_P+2)\bigr).\)
The total encoding length of \(\ z^*\) is consequently polynomial in \(\ m,\tau,d,L\). Together with polynomial verification, this proves membership in \(\mathrm{NP}\).
6. Running times and scope
The decision problem is \(\mathrm{NP}\)-complete. Its nondeterministic running time is \(\ \operatorname{poly}(m,\tau,d,L)\); a deterministic polynomial-time algorithm would imply \(\ \mathrm P=\mathrm{NP}\).
An explicit deterministic upper bound follows by enumerating tight-inequality patterns. There are at most
\(\displaystyle h=\tau(m+1)+m(2d+1)\)
inequalities. For each of the \(\ 2^h\) patterns, solve the auxiliary slack program above and, if its optimum is positive, verify the resulting rational point. The structural fact proves this procedure complete. Its running time is
\(\displaystyle 2^{\,O(m\tau+md)}\operatorname{poly}(m,\tau,d,L).\)
The reduction settles the exact model asked about, including its real masses and destination-only blocking condition. It does not assert the additional discrete restrictions of strict preferences or four colleges.
⟨structured verdict parsed — rendered above⟩
The argument establishes that the decision problem is \(\mathrm{NP}\)-complete. The reduction respects the exact mass model, and the certificate argument covers arbitrary real assignments. I found no major or minor issue requiring repair.
The cited theorem is applicable. Theorem 1 in the cited paper establishes \(\mathrm{NP}\)-completeness for stable marriage with incomplete lists and ties. The paper explicitly defines matchings as perfect and defines blocking through strict improvement on both sides. This is precisely the source problem used by the prover. [Iwama–Manlove–Miyazaki–Morita](https://eprints.gla.ac.uk/1066/1/ICALP99.pdf)
The restriction to acceptability graphs admitting a perfect matching is valid. An instance without any perfect acceptable matching cannot have a perfect weakly stable matching. The proposed replacement has exactly one perfect acceptable matching, namely the matching stated in the output. The pair \((\alpha,u)\) strictly prefers each other to their partners in that matching, so the replacement is a negative instance. It also has no empty acceptable set.
Padding preserves the answer. Every added pair is isolated from the original instance, and its members accept only each other. Consequently, any perfect matching must match each added pair together, and these pairs create no blocking pairs involving original agents. For nonempty source instances, the stated bound \(N<2n\) holds. Restricting the hardness source to nonempty instances is harmless.
Choosing a power of two makes all constructed masses and quotas dyadic rationals. Padding increases the number of agents by less than a factor of two.
All constructed parameters satisfy the task’s restrictions:
Because every type has the attribute, each college’s attribute quota forces its enrollment to equal \(1/N\). Summing these enrollments gives total assigned mass \(1\).
The deduction that every type exhausts its mass is valid: all type totals are bounded above by their respective masses, and the sum of those upper bounds already equals total assigned mass. Thus every unmatched coordinate is zero.
Guaranteed feasibility follows from the perfect acceptable matching ensured by preprocessing. No stability assumption is used for this feasibility claim.
The integral assignment induced by a perfect matching is feasible.
For any alleged blocking opportunity, the moving type’s only positive source coordinate is its matched college. Strict improvement therefore gives the required preference on the type’s side.
The destination’s exact enrollment quota forces total removals to equal the added mass. Since there is only one incumbent type with positive mass at the destination, that incumbent must supply a positive removal. The removal rule then requires the college to strictly prefer the moving type to its matched incumbent.
These two strict preferences constitute a blocking pair for the source matching. The contradiction is valid even with ties, because neither side’s indifference qualifies as strict improvement.
The support graph is finite and bipartite. The displayed calculation correctly proves Hall’s condition for every subset of types, using the equal row and column sums. Its two vertex classes have equal size, so Hall’s theorem supplies a perfect matching contained in the positive support.
If this matching had a blocking pair, both coordinates used to define \(\delta\) would be positive. Thus the stated minimum is strictly positive and satisfies both the source-mass bound and the incumbent-removal bound.
The replacement keeps destination enrollment and its sole attribute total unchanged. The removal is permitted by the college’s strict preference. Therefore it is a blocking opportunity under the task’s definition.
Crucially, this argument does not require source-college feasibility after the move. The prover uses exactly the destination-only condition specified in the task.
The equivalence and the resulting \(\mathrm{NP}\)-hardness are established.
The blocking linear program accurately represents the definition for a fixed acceptable pair and strictly worse source destination.
After feasibility has been checked, the zero choice of \(\delta\) and all removals is feasible. The objective is bounded by the available source mass. A positive optimum is equivalent to the existence of permitted parameters with \(\delta>0\); a zero optimum excludes such a block.
All possible blocking opportunities are covered by enumerating acceptable pairs and strictly worse source destinations, including unmatched mass. The upper bound of \(\tau m(m+1)\) programs is valid.
Each program has at most \(\tau+1\) variables and \(O(\tau+d)\) constraints. Exact rational linear programming gives the stated verification bound
\[
\tau m(m+1)\operatorname{poly}(\tau+d+L+B).
\]
The structural fact is proved correctly. It concerns feasible assignments having identical positive-coordinate patterns and identical tight capacity and quota inequalities.
For a block at one assignment, the destination direction satisfies every active destination inequality in the required direction. At the other assignment, the same inequalities are active and remain satisfied under positive scaling.
Every inactive destination inequality has positive slack. There are finitely many such inequalities, so sufficiently small positive scaling preserves all of them simultaneously.
The positive-coordinate pattern ensures positive source mass and positive availability for every nonzero removal. Scaling can therefore satisfy all source and removal bounds simultaneously. The strict preference conditions are unchanged.
The argument handles lower quotas as well as upper quotas: both are linear inequalities, with their respective inequality orientations. Coordinate nonnegativity is preserved by the explicit removal bounds.
The auxiliary linear program preserves exactly the required pattern. Equalities enforce all inequalities active at the original point. A positive common slack makes every other inequality strict, including coordinate nonnegativity inequalities. Consequently, the resulting point has exactly the same positive coordinates and active constraints.
The claimed positive feasible slack exists because there are finitely many inactive inequalities, each with positive slack at the original point. The feasible region is bounded by the mass equalities, nonnegativity, and the bound on \(\varepsilon\). An optimal rational vertex therefore exists, with positive objective value.
The structural fact then transfers stability to its assignment coordinates.
The bit bound is valid. The auxiliary constraint coefficients are integers in \(\{-1,0,1\}\). A common denominator for the input right-hand sides has bit length \(O(L)\). The stated application of Cramer’s rule and Hadamard’s bound yields
\[
O\bigl(L+(n_P+1)\log(n_P+2)\bigr)
\]
bits per coordinate. With at most \(\tau(m+1)\) assignment coordinates, this gives a certificate of polynomial total length.
Together with the verifier, this establishes membership in \(\mathrm{NP}\) for the real-mass existence problem.
The nondeterministic polynomial-time bound follows from the polynomial certificate length and verification algorithm.
The inequality count
\[
h=\tau(m+1)+m(2d+1)
\]
is a valid upper bound: coordinate nonnegativity, one capacity inequality per college, and two inequalities per college–attribute pair.
Enumerating all tightness patterns is complete because any stable assignment contributes a pattern whose positive-slack program yields a stable rational representative. Infeasible patterns are discarded, and feasible patterns with positive optimum are checked by the rational verifier.
Thus the deterministic upper bound
\[
2^{O(m\tau+md)}\operatorname{poly}(m,\tau,d,L)
\]
is justified.
The hardness restrictions actually proved are one attribute, equal masses, and guaranteed feasibility, with ties allowed. The output correctly refrains from claiming hardness with strict preferences or four colleges.
No additional mathematical clarification 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.