Answer: Polynomial-time solvable: in \(\mathrm{P}\) for the stated model with \(m=1\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe CSWM—Y problem is coNP-complete, even for a simple weighted typed market with only one college that has an additively separable utility.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given complete student types \(\Theta\) with rational masses \(\mu_\theta\) summing to \(1\), one college with per-capita budget \(b\), type-specific wages \(w_\theta\), additive utilities \(u_\theta\), acceptability, and a current mass matching \(y_\theta\in[0,\mu_\theta]\), decide whether there exist incoming home masses \(z_\theta\in[0,\mu_\theta-y_\theta]\) and rejected matched masses \(r_\theta\in[0,y_\theta]\) such that incoming agents strictly prefer their contract to home, \(\sum_\theta w_\theta(y_\theta-r_\theta+z_\theta)\le b\), and \(\sum_\theta u_\theta(z_\theta-r_\theta)>0\).
A society is given by its support: a list \(\Theta\) of \(\tau\geq 1\) complete student types with positive binary rational masses \(\mu_\theta\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There is one college, so \(m=1\), with positive rational per-capita budget \(b\). Each type specifies whether its sole college contract exists, its nonnegative rational wage \(w_\theta\), its rational college utility \(u_\theta\), and a strict student preference between that contract and home with zero wage.
College utility is additive in assigned mass and does not subtract wages; home contributes zero utility. The college weakly accepts a type exactly when \(u_\theta\geq 0\). Let \(E\) contain the types whose contract exists, whose students strictly prefer it to home, and which the college weakly accepts.
The input includes a feasible rational current matching: \(0\leq y_\theta\leq\mu_\theta\), \(y_\theta=0\) outside \(E\), and \(\sum_\theta w_\theta y_\theta\leq b\). All remaining mass is at home.
A blocking deviation consists of real incoming masses \(0\leq z_\theta\leq\mu_\theta-y_\theta\) and rejected masses \(0\leq r_\theta\leq y_\theta\), with \(z_\theta=0\) outside \(E\) and \(\sum_\theta z_\theta>0\). Rejected students need not consent.
It must satisfy \(\sum_\theta w_\theta(y_\theta-r_\theta+z_\theta)\leq b\) and \(\sum_\theta u_\theta(z_\theta-r_\theta)>0\).
Is deciding whether a blocking deviation exists in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard, where \(L\) is the total binary input length?
For finite students, checking coalitional stability is \(\mathrm{coNP}\)-complete, even with one college, one contract per student, additive college utility, and ordered wage types; equivalently, detecting a blocking coalition is \(\mathrm{NP}\)-complete. [Source](https://jair.org/index.php/jair/article/download/11582/26504)
No result settling this precise mass decision problem was located.
Deciding whether a blocking deviation exists is in \(\mathrm{P}\) for the stated model with \(m=1\). An exact algorithm optimizes a fractional knapsack problem and compares its optimum with the current college utility.
The proof covers real deviations, zero wages, zero utilities, and the strict requirement of positive incoming mass.
Restrict attention to \(E\). By definition, \(u_\theta\geq 0\) for every \(\theta\in E\), and the current assignment is zero outside \(E\).
Define the set of feasible final assignments by
\(\displaystyle \mathcal F=\left\{x\in\mathbb R^E:0\leq x_\theta\leq\mu_\theta\text{ for all }\theta\in E,\quad \sum_{\theta\in E}w_\theta x_\theta\leq b\right\},\)
and define college utility by
\(\displaystyle U(x)=\sum_{\theta\in E}u_\theta x_\theta.\)
Lemma. A blocking deviation exists if and only if some \(x\in\mathcal F\) satisfies \(U(x)>U(y)\).
Proof. Suppose first that \((z,r)\) is a blocking deviation. Set \(x_\theta=y_\theta-r_\theta+z_\theta\). Its bounds imply
\(\displaystyle x_\theta\geq y_\theta-r_\theta\geq 0,\qquad x_\theta\leq y_\theta+z_\theta\leq\mu_\theta.\)
The deviation’s budget condition gives \(x\in\mathcal F\), and its utility condition gives
\(\displaystyle U(x)-U(y)=\sum_{\theta\in E}u_\theta(z_\theta-r_\theta)>0.\)
Conversely, suppose \(x\in\mathcal F\) and \(U(x)>U(y)\). Define
\(\displaystyle z_\theta=\max\{x_\theta-y_\theta,0\},\qquad r_\theta=\max\{y_\theta-x_\theta,0\},\)
and set both quantities to zero outside \(E\). Since \(0\leq x_\theta\leq\mu_\theta\),
\(\displaystyle 0\leq z_\theta\leq\mu_\theta-y_\theta,\qquad 0\leq r_\theta\leq y_\theta.\)
Also \(y_\theta-r_\theta+z_\theta=x_\theta\), so the budget condition holds and the utility gain is strictly positive.
It remains to check positive incoming mass. If \(\sum_{\theta\in E}z_\theta=0\), every \(z_\theta\) is zero, so \(x_\theta\leq y_\theta\) for every eligible type. Because all their utilities are nonnegative, this implies \(U(x)\leq U(y)\), a contradiction. Thus the constructed deviation satisfies every required condition. \(\square\)
Consequently, it suffices to compute an optimal feasible assignment \(g\) and answer yes exactly when \(U(g)>U(y)\).
For every eligible type with \(w_\theta=0\), set \(g_\theta=\mu_\theta\). This costs nothing and cannot reduce utility.
Index the remaining eligible types by \(1,\ldots,n\), so each \(w_i>0\). Sort them in nonincreasing order of utility per unit wage:
\(\displaystyle \frac{u_1}{w_1}\geq\frac{u_2}{w_2}\geq\cdots\geq\frac{u_n}{w_n}.\)
Ties may be resolved arbitrarily. Define \(S_0=0\) and
\(\displaystyle S_j=\sum_{i=1}^j w_i\mu_i\qquad (1\leq j\leq n).\)
If \(S_n\leq b\), set \(g_i=\mu_i\) for every positive-wage type. This includes the case \(n=0\).
Otherwise, let \(k\) be the smallest index with \(S_k>b\). Set
Minimality of \(k\) gives \(S_{k-1}\leq b<S_k\), hence \(0\leq g_k<\mu_k\). The constructed assignment spends exactly \(b\). In particular, it is feasible. If \(S_{k-1}=b\), then \(g_k=0\).
If \(S_n\leq b\), the algorithm assigns the full eligible mass of every type. For any \(x\in\mathcal F\), each \(x_\theta\leq g_\theta\); nonnegative utilities therefore give \(U(x)\leq U(g)\).
Now suppose \(S_n>b\), and define
\(\displaystyle \lambda=\frac{u_k}{w_k}\geq 0.\)
For any \(x\in\mathcal F\), the following identity holds:
\(\displaystyle U(x)-U(g)=\lambda\sum_{\theta\in E}w_\theta(x_\theta-g_\theta)+\sum_{\theta\in E}(u_\theta-\lambda w_\theta)(x_\theta-g_\theta).\)
The first term is nonpositive: \(x\) spends at most \(b\), \(g\) spends exactly \(b\), and \(\lambda\geq 0\).
Every summand in the second term is also nonpositive:
Thus \(U(x)\leq U(g)\) for every feasible \(x\). This proves optimality, including when some utilities or the threshold \(\lambda\) equal zero.
Together with the lemma, this proves the exact decision criterion
\(\displaystyle \text{a blocking deviation exists}\quad\Longleftrightarrow\quad U(g)>U(y).\)
When the answer is yes, the lemma’s formulas construct a rational blocking deviation.
Determining \(E\) requires inspecting the explicitly listed \(\tau\) types. No enumeration of other possible types is needed.
The sorting step uses \(O(\tau\log(\tau+1))\) exact comparisons. Since positive-wage denominators are positive, a ratio comparison can be performed by comparing \(u_iw_j\) and \(u_jw_i\), using rational arithmetic.
The remaining computation consists of prefix sums of the products \(w_i\mu_i\), at most one division to construct a fractional coordinate, and the sums defining \(U(g)\) and \(U(y)\).
These operations have polynomial bit complexity. To see why denominator sizes do not cause an exponential encoding:
Standard exact integer arithmetic therefore implements all operations in time polynomial in \(\tau\) and \(L\). The strict comparison \(U(g)>U(y)\) is exact; it requires neither a numerical tolerance nor a prescribed minimum gain. Since \(m=1\), this is polynomial in \(m,\tau,L\) on the stated input class.
The cited finite-student work establishes hardness of checking coalitional stability. [Ismaili et al., *Weighted Matching Markets with Budget Constraints*](https://research.rug.nl/en/publications/weighted-matching-markets-with-budget-constraints/). Here, however, the specified deviations allow arbitrary fractions of each type’s mass. The proof above uses that divisibility directly.
For example, take two eligible types with \(\mu_1=\mu_2=1/2\), wages \(w_1=1,w_2=2\), utilities \(u_1=1,u_2=3\), budget \(b=1/2\), and current assignment \(y_1=1/2,y_2=0\). Both types’ students prefer their contract to home.
Rejecting \(r_1=1/2\) and admitting \(z_2=1/4\) spends \(2(1/4)=1/2\) and yields utility gain
\(\displaystyle 3(1/4)-1(1/2)=1/4>0.\)
If each type instead represented one indivisible student of mass \(1/2\), admitting the second student would cost \(2(1/2)=1>b\). No blocking deviation would then exist. Thus allowing fractional mass can change the answer, and it permits the polynomial optimization proved above.
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated decision problem correctly: detecting a blocking deviation is in \(\mathrm{P}\) for the specified divisible-mass model with \(m=1\).
The equivalence, explicit optimization algorithm, optimality proof, and binary running-time argument all stand. I found no major or minor mathematical issues requiring repair.
Restricting the argument to \(E\) is justified.
Outside \(E\), the input requires \(y_\theta=0\), and deviations require \(z_\theta=0\). The rejection bound then forces \(r_\theta=0\). Consequently, such types contribute nothing to the resulting assignment, expenditure, or utility change, even if their utilities are negative.
Within \(E\), every utility is nonnegative. This hypothesis is used correctly throughout the proof.
Forward direction. For an admissible deviation, the definition \(x_\theta=y_\theta-r_\theta+z_\theta\) satisfies both coordinate bounds:
\[ x_\theta\geq y_\theta-r_\theta\geq0, \qquad x_\theta\leq y_\theta+z_\theta\leq\mu_\theta. \]
These bounds remain valid when both incoming and rejected masses are positive for the same type. The deviation’s budget condition is exactly the feasibility condition for \(x\), and its strict utility condition is exactly \(U(x)>U(y)\).
Reverse direction. The proposed positive-part formulas satisfy the incoming and rejection bounds, and reconstruct \(x\) exactly. Setting both quantities to zero outside \(E\) respects every eligibility restriction.
The positive-incoming requirement is established rather than assumed: if all incoming coordinates were zero, then \(x_\theta\leq y_\theta\) throughout \(E\), and nonnegative utilities would imply \(U(x)\leq U(y)\). This contradicts strict improvement.
Thus the lemma handles the strict condition correctly. No consent condition for rejected students is introduced.
Assigning all eligible zero-wage mass is valid because it consumes no budget and cannot reduce utility.
Every ratio used in sorting has a strictly positive wage denominator. Zero utilities and arbitrary ordering within ratio ties cause no difficulty.
In the budget-constrained branch, the smallest index \(k\) with \(S_k>b\) exists because \(S_n>b\). Its minimality gives
\[ S_{k-1}\leq b<S_k, \]
which establishes \(0\leq g_k<\mu_k\). Substitution into the expenditure expression confirms that \(g\) spends exactly \(b\).
The boundary case \(S_{k-1}=b\) is explicitly covered: the fractional coordinate is zero. The full-assignment branch correctly covers \(n=0\), using the defined value \(S_0=0\).
In the full-assignment branch, coordinatewise domination and nonnegative utilities establish optimality directly.
In the budget-constrained branch, the displayed identity is algebraically correct. Its first term is nonpositive because \(\lambda\geq0\), \(x\) spends at most \(b\), and \(g\) spends exactly \(b\).
The signs of all remaining summands are correctly justified:
These cases exhaust \(E\). The proof works unchanged when ratios tie or \(\lambda=0\).
Accordingly, the decision criterion \(U(g)>U(y)\) follows from established optimality and the equivalence lemma. No unverified fractional-knapsack theorem is needed: the output supplies its own proof.
The complexity argument is sufficient for binary rational inputs.
Sorting uses polynomially many exact rational comparisons. Cross multiplication is valid because all relevant wages are positive.
Products of input rationals have polynomial encoding length. For prefix sums, the proposed common denominator has bit length bounded by the sum of the constituent denominator lengths; this bounds encoding length even though the denominator’s numerical value can be large. The corresponding numerators also have polynomial bit length.
The single fractional coordinate uses rational subtraction and division by a nonzero wage. Subsequent utility products and sums retain polynomial bit length. Thus polynomially many integer arithmetic operations on polynomial-size operands suffice.
The strict utility comparison is exact and requires no lower bound on a positive improvement. Real deviations introduce no additional computational obstacle because the proved optimum is rational, and the supplied formulas produce a rational witness whenever the answer is yes.
The claimed dependence on \(m,\tau,L\) is correctly restricted to the input class \(m=1\).
The written argument also covers \(E=\varnothing\), all eligible utilities being zero, only zero-wage eligible contracts, and fully assigned eligible mass. None creates a false positive.
The illustrative calculation is correct: the proposed fractional deviation spends \(1/2\) and gains utility \(1/4\). In the indivisible interpretation, the second student alone costs \(1>b\); the first student is already assigned. Therefore that example has no indivisible blocking deviation.
The contextual claim that finite-student coalitional-stability verification is coNP-complete is supported by the cited [publication’s abstract](https://research.rug.nl/en/publications/weighted-matching-markets-with-budget-constraints/). That result is not used as a premise in the continuous proof.
No additional lemma, clarification, or mathematical repair is required. The prover establishes the polynomial-time classification it claims.
⟨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.