Capacity Modification in the Stable Matching Problem

The strongest case is a mirror of the paper’s unbudgeted pair-matching result.

Take a large course-allocation or entry-level hiring market. There are \(N\) workers but only \(\tau\ll N\) worker types. A type records the worker’s complete ranking over firms, acceptability, and every qualification relevant to firms. Thus \(\mu_w\) is the fraction of workers of type \(w\). Firms remain a finite set \(F\) of named institutions, each with a capacity fraction \(q_f\) and a strict ranking over worker types. This is a credible high-multiplicity regime: thousands of applicants may share a preference-and-qualification profile, while the number of firms and profiles is modest. The paper itself already motivates capacity changes through course allocation, so this is a scenario its authors should recognise.

The continuous matching is a transport plan \(x\), where \(x_{wf}\) is the mass of type \(w\) assigned to firm \(f\), and \(x_{w0}\) is unmatched mass. It satisfies

\[ \sum_{f\in F}x_{wf}+x_{w0}=\mu_w \]

and

\[ \sum_w x_{wf}\le q_f+\Delta_f. \]

Here \(\Delta_f\) is the added capacity at firm \(f\). Stability is the usual responsive-preference condition at mass level. Define

\[ b_{wf}(x)=\sum_{g:\,f\succ_w g}x_{wg} \]

as the mass of type \(w\) assigned somewhere it prefers less than \(f\), and

\[ a_{wf}(x)=q_f+\Delta_f-\sum_{u:\,u\succeq_f w}x_{uf} \]

as the capacity available at \(f\) after retaining all workers that \(f\) ranks at least as highly as \(w\). There is no blocking mass precisely when \(b_{wf}(x)a_{wf}(x)=0\) for every acceptable pair \((w,f)\), with no unacceptable worker mass assigned to a firm.

The lead problem is Add-Pair\(_\infty\):

Given rational \(\mu\), capacities \(q\), preferences, a target type-firm pair \((w^\star,f^\star)\), a target mass \(\delta\le\mu_{w^\star}\), and a capacity budget \(\ell\), decide whether there exist \(\Delta\) and a stable mass matching \(x\) such that

\[ \Delta_f\ge0,\qquad \sum_f\Delta_f\le\ell,\qquad x_{w^\star f^\star}\ge\delta. \]

Equivalently, the optimization version minimizes \(\sum_f\Delta_f\) subject to those conditions. A solution is the pair \((\Delta,x)\), not merely the modified capacities.

This mirrors the paper’s Theorem 4.1, “Add Capacity To Match Pair can be solved in polynomial time,” which is proved in this paper. The only semantic change is forced by the atomless population: “a fixed worker is matched to \(f^\star\)” becomes “at least \(\delta\) mass of an otherwise indistinguishable worker type is matched to \(f^\star\).” Taking \(\delta\) to be one seat’s population share recovers the finite-clone interpretation; taking \(\delta\) to be, say, \(2\%\) expresses the genuinely population-level question of placing a target cohort.

I expect Add-Pair\(_\infty\) to be Class A. The proof strategy of Theorem 4.1 is structural rather than dependent on individual identities. Form the distracting firms preferred by \(w^\star\) to \(f^\star\), and the distracting worker types preferred by \(f^\star\) to \(w^\star\); truncate the relevant preference lists; then use the paper’s key observation that, in the unbudgeted case, any useful capacity increase can be concentrated at \(f^\star\). Deferred acceptance can be run at type level, moving whole masses or one boundary fraction at each rejection event. There are only polynomially many type-firm breakpoints, so the expected running time is polynomial in \(|F|\), \(\tau\), and the input bit length, without expanding \(N\) individual workers.

The high-multiplicity bridge is also clean. For rational data, clear denominators and replace each type \(w\) by many identical worker clones, each firm capacity by repeated seats, and each mass transfer by the corresponding number of clones. Aggregating any such finite matching gives \(x\); conversely, clearing denominators of a rational mass solution gives a finite clone realization. Preferences, stability, capacity budgets, and the target mass are preserved. Thus this is not merely fractional matching over arbitrary individuals: it is the compressed description of repeated workers with identical complete types.

I would not use Theorem 4.2 as a second anchor. It proves that Budgeted Add Capacity To Match Pair is NP-hard, via the cited result of Boehmer et al. [9], but that hardness is tied to selecting individually addable named men, equivalently activating particular firms. If capacity itself becomes divisible mass, that selection combinatorics may disappear. A worthwhile follow-up is therefore to determine whether the budgeted mass version is tractable, remains hard through heterogeneous firms, or becomes a genuinely continuum-specific Class C problem. That boundary would be informative, but it should not be presented as an established transfer.

The weakest point is the target. A literal named worker has measure zero in an atomless population, so the continuous problem cannot preserve the paper’s identity-sensitive pair exactly. It must replace that identity with a target cohort and an explicit threshold \(\delta\). I regard that as a legitimate high-multiplicity extension, not a change of subject, because the original pair objective is still present at the type level and the \(\delta=1/N\) finite-clone slice recovers the “some worker of this type” question. But if a referee insists that only a designated individual counts, this mirror fails; the positive case then rests on accepting cohort-level matching as the honest continuous form of the paper’s objective.