Optimal Capacity Modification for Stable Matchings with Ties

The paper admits a credible continuous mirror. My strongest anchor is Theorem 1, proved in this paper: MINSUM-SS is solvable in polynomial time. The natural mirror is a high-multiplicity resident population with finitely many resident types and finitely many named hospitals.

A resident type \(t\) is a complete matching signature: its acceptable hospitals, strict preference order over them, and its rank at every hospital. Residents with the same type are indistinguishable to the entire instance. The society is a rational mass vector \(\mu\), where \(\mu_t\) is the fraction of residents of type \(t\) and \(\sum_t\mu_t=1\). Hospitals remain distinct public institutions, with rational normalized capacities \(q_h\) and weak preference orders \(\succeq_h\) over resident types; ties represent equal-priority cohorts.

A matching is a flow \(x_{t,h}\ge 0\), together with unmatched mass \(x_{t,\bot}\), satisfying \(\sum_hx_{t,h}+x_{t,\bot}=\mu_t\). The decision variable is a capacity increase \(\Delta_h\ge0\), giving hospital \(h\) capacity \(q_h+\Delta_h\). The objective is to minimize \(\sum_{h\in H}\Delta_h\).

Strong stability is defined at positive mass. Let \(d_h=q_h+\Delta_h-\sum_t x_{t,h}\) be the unused capacity, viewed as dummy residents ranked below every acceptable resident. A type-level pair \((t,h)\) blocks if some positive mass of type \(t\) is assigned to \(h'\ne h\), and either \(h\succ_t h'\) while \(h\) has positive mass of a type \(u\) with \(t\succeq_h u\) or unused capacity, or \(h\succeq_t h'\) while \(h\) has positive mass of a type \(u\) with \(t\succ_h u\) or unused capacity. A solution is an optimal \((\Delta,x)\) with no such blocking pair.

Call this problem Continuous MINSUM-SS. It is not merely a fractional welfare relaxation. If every input quantity is rational, clearing denominators turns \(\mu_t\) into multiplicities of identical residents, \(x_{t,h}\) into assignments of those clones, and \(\Delta_h\) into integer quota increases. Conversely, any discrete HR-HT instance with repeated residents having the same complete signature maps to this mass instance. Splitting a type’s mass across hospitals simply means assigning different identical clones differently.

This regime is plausible in centralized school or residency allocation: millions of applicants may fall into a much smaller number of cohorts with the same ordered hospital list and the same priority status at every hospital. Quotas and quota increases are naturally measured as fractions of the applicant population. The paper’s equal-treatment motivation for strong stability survives exactly; only the multiplicity representation changes.

I expect Continuous MINSUM-SS to be Class A. Algorithm 1 becomes a mass-proposal algorithm: a hospital proposes to the entire mass of a resident type at a given tied rank, resident types retain their most-preferred proposal, and the resulting oversubscription determines \(\Delta_h\). The arguments in Claims 1 and 2 and Lemma 2 are counting arguments that become mass inequalities. The output has polynomial-size rational data, and the algorithm should run in time polynomial in the number of hospitals, the number of resident types, and the encoding length. This is a genuine mirror of the paper’s problem, not a tractable substitute with a different stability notion.

A second, weaker but still convincing anchor is Theorem 2, also proved by the authors, with details deferred in this version to Ranjan et al. (2024): MINSUM-SS-FE is solvable in polynomial time. Its continuous counterpart is Continuous MINSUM-SS-FE. In addition to \(\mu,q\), the instance contains rational forced masses \(\lambda_{t,h}\), requiring \(x_{t,h}\ge\lambda_{t,h}\) for specified type–hospital pairs, with \(\sum_h\lambda_{t,h}\le\mu_t\). The question is to report infeasibility or output a strongly stable flow and capacity augmentation minimizing \(\sum_h\Delta_h\).

This is the right continuum analogue of the paper’s course-allocation application. A positive mass of final-year students of a given type may be required to receive a particular course or hospital; requiring merely that one named individual be assigned there would disappear in an atomless model. If exact clone fidelity is desired, the forced mass can be represented as a separate forced resident type. I expect this problem also to be Class A: the paper’s pruning of edges that would create blocking pairs with the forced set becomes pruning of type–hospital assignments, followed by the same mass-proposal procedure.

The mirror deliberately does not claim the paper’s negative results. Theorem 3 proves that MINSUM-COST is NP-hard and inapproximable within any multiplicative factor, even with costs in \(\{0,1\}\), and Theorem 4 proves that MINMAX-SS is NP-hard. Their reductions use one-copy gadget residents and Boolean occupancy choices. Aggregating those residents into positive-mass types may permit fractional splitting and destroy the reduction. These are valuable boundary questions, but I would not present their hardness as transferred without a separate clone-integrality argument.

The weakest point is that the lead mirror continuizes the resident population while retaining named hospitals. That is a real regime rather than a full two-sided continuum, and arbitrary instances in the paper may have essentially one resident type per resident because hospital priorities distinguish everyone. The mirror therefore applies only to instances with many genuinely interchangeable residents. I think that is acceptable: the programme asks whether a sensible high-multiplicity regime exists, not whether every instance has one. The school and residency-cohort regime is natural, the stability predicate and capacity action are preserved, and Theorem 1 gives a precise computational question whose polynomial structure is genuinely exposed by passing from individuals to mass.