A Simple 1.5-approximation Algorithm for a Wide Range of Maximum Size Stable Matching Problems

The strongest positive case is a deliberately bounded one: a high-multiplicity, continuous version of the paper’s Max-\(c\gamma\)-SMTI problem. I would use only one anchor, because Theorem 3.1 is a special case of Theorem 3.2 rather than an independent result.

The anchor is Theorem 3.2, proved in this paper: “Max-\(c\gamma\)-smti can be \(\frac32\)-approximated in \(O((s+t)|E|)\) time.” The theorem is the paper’s own main result, not a cited result. I would mirror its legal subfamily with \(C=E_c=\varnothing\). This retains the paper’s central matching problem—ties, incomplete preferences, thresholded blocking, and maximization of matched agents—while postponing the technically more delicate critical-vertex machinery.

Call the problem Typed Max-\(c\gamma\)-SMTI\(_\infty\). An instance has finite left and right type sets \(A\) and \(B\), rational masses \(\mu_a\) and \(\nu_b\), and a finite set \(\mathcal E\) of contract types. A contract type \(e\) has endpoints \(a(e)\in A\) and \(b(e)\in B\); parallel contracts between the same two types remain distinct, exactly as in the paper. Each type contains the complete local information relevant to the problem: its preference values \(p_a(e)\), \(p_b(e)\), its value for being unmatched, and the threshold parameters \(\gamma_{a,e},\delta_{a,e}\) and \(\gamma_{b,e},\delta_{b,e}\).

A solution is a nonnegative mass assignment \(x=(x_e)_{e\in\mathcal E}\), with \(\sum_{e:a(e)=a}x_e\le \mu_a\) and \(\sum_{e:b(e)=b}x_e\le\nu_b\). Thus \(x_e\) is the mass of agents using contract type \(e\), and the objective is to maximize \(\sum_{e\in\mathcal E}x_e\).

To define stability, let a current status of type \(a\) be either a contract \(f\) with \(x_f>0\), or the unmatched status \(\varnothing\) when \(a\) has positive unmatched mass. A contract \(e=(a,b)\) blocks \(x\) if there are positive masses of type \(a\) and \(b\) currently using statuses \(f\) and \(g\), respectively, such that either

\[ p_a(e)-p_a(f)\ge \gamma_{a,e} \quad\text{and}\quad p_b(e)-p_b(g)\ge \delta_{b,e}, \]

or

\[ p_a(e)-p_a(f)\ge \delta_{a,e} \quad\text{and}\quad p_b(e)-p_b(g)\ge \gamma_{b,e}. \]

Because all thresholds are positive, these inequalities already imply strict improvement on both sides. A feasible assignment with no such blocking contract is \(c\gamma\)-stable. The problem asks for a \(c\gamma\)-stable assignment whose matched mass is at least \(\frac23\) of the maximum matched mass among all \(c\gamma\)-stable assignments.

This is a genuine population mirror, not merely a fractional outcome model. The mass is the population: it represents residents, applicants, or unit-capacity positions. A matching unit is still used once, and every type records the complete information that makes its agents interchangeable. For rational masses, clearing denominators gives an exact clone interpretation. If \(\mu_a=n_a/D\), \(\nu_b=r_b/D\), and \(x_e=q_e/D\), create \(n_a\) left clones, \(r_b\) right clones, and assign \(q_e\) clone pairs through \(e\). A positive-mass blocking pattern is then exactly a blocking pair of clones. Thus the continuous formulation is the high-multiplicity version of the paper’s matching semantics, not a coalition-deviation replacement.

A plausible regime is a national or regional clearinghouse with millions of residents and training positions but only a few hundred or thousand local profiles. A resident type might specify specialty, ranking over hospitals and contract categories, eligibility, and switching thresholds. A position type might specify hospital, specialty, contract conditions, and its ranking over resident profiles. Many residents share one profile, and many positions are interchangeable within a position type. The number of agents can therefore be in the millions while \(|A|+|B|+|\mathcal E|\) remains moderate. This is exactly the kind of market in which “\(547\) agents” is less meaningful than “\(0.5\%\) of the resident population.”

The authors should recognize this as their problem. Nothing essential has been replaced by a welfare surrogate: agents still have one-to-one contracts, preferences are still over the paper’s edges, blocking is still pairwise, threshold parameters still govern blocking, and the objective is still maximum matching size. The only change is that repeated agents are represented by their type masses.

The expected classification is Class A for this typed subproblem. Apply the paper’s edge-duplication construction to each contract type, creating the \(a(e),b_0(e),b_1(e),c(e)\) copies and the strict rankings described in the proof. Then run deferred acceptance at the type-mass level: a proposer type sends mass down its strict list, while a receiver type retains its most preferred incoming mass up to its available mass. This is a finite flow-like computation over types and copied contract types; it need not materialize the millions of clones. Projecting copied-contract mass back to the original contract types gives a candidate solution.

The paper’s two essential arguments have natural aggregate forms. The projection argument is local: a positive-mass \(c\gamma\)-block would produce a blocking copied contract. The approximation argument can be expressed using a decomposition of the difference between two mass matchings into alternating paths and cycles, replacing the finite symmetric-difference argument in Theorem 3.2. I would therefore expect a polynomial-time \(\frac32\)-approximation in the number of types, contract types, and input bit length, independent of the population size. In the weak-stability parameter regime, this directly contains the homogeneous high-multiplicity version of Max-SMTI.

I am not claiming that the full critical-vertex and critical-edge theorem transfers automatically. A natural full extension would give critical types masses, critical contract types, define \(K(x)\) as the total critical mass covered by critical contracts, require \(K(x)\) to be maximal, and permit a blocking exchange only when it preserves \(K(x)\). That is a sensible further problem, and criticality itself has a max-flow flavour. But the proof of Theorem 3.2 uses \(s+t\) layers of copied edges indexed by individual critical vertices. Under cloning, those counts scale with the population, so the paper’s stated running time does not immediately become a type-polynomial bound.

That is the weakest point of the positive case: the cleanest transfer covers the theorem’s no-critical slice, while the full theorem needs a new argument for critical mass. There is also a genuine atomless-limit issue: an individual clone pair has zero measure in a literal atomless society. The rational-clone formulation handles this honestly by defining blocking through positive residual type mass and showing exact equivalence on every rational high-multiplicity instance. The extension to arbitrary real measures would still need a careful stability convention.

The resulting research questions are concrete: does the \(\frac32\) guarantee hold for the full critical-mass version; can the critical-copy construction be replaced by residual-flow tests over type masses; what rounding guarantees relate continuous solutions to finite clone markets; and does exact optimization remain polynomial when the number of types is fixed but the contract agenda grows? Even without those extensions, Typed Max-\(c\gamma\)-SMTI\(_\infty\) is a recognizable, computationally substantive continuous mirror of Theorem 3.2.