Fair Stable Matching Meets Correlated Preferences

The strongest honest mirror is a high-multiplicity stable matching market, with the continuous object being the population of residents and positions rather than the outcome matching itself.

The paper has one clean numbered computational anchor: Corollary 1, proved in this paper. It states that a sex-equal stable matching can be computed in polynomial time whenever either \(S_M(\mu_M)\ge S_W(\mu_M)\) or \(S_M(\mu_W)\le S_W(\mu_W)\). Lemma 1, attributed to Kato [36], supplies the structural reason: under either inequality, the relevant extreme stable matching is already sex-equal. The paper also reports that arbitrary sex-equal stable marriage is strongly NP-hard, due to Kato, but that statement is unnumbered and cited from elsewhere, so I do not treat it as a formal anchor.

My lead problem is Continuous Corollary-1 Sex-Equal Stable Matching.

There are two sides, with finite type sets \(A\) and \(B\). A type is a cohort of agents indistinguishable for the market: every \(a\in A\) has the same strict ranking \(\succ_a\) over the position types \(B\), and every \(b\in B\) has the same strict ranking \(\succ_b\) over the resident types \(A\). The input gives rational masses \(\mu_a\) and \(\nu_b\), with \(\sum_a\mu_a=\sum_b\nu_b=1\). Thus the number of actual residents and positions may be enormous, while \(|A|+|B|\) remains moderate.

A feasible solution is a mass-matching matrix \(x=(x_{ab})\), where \(x_{ab}\ge0\), \(\sum_bx_{ab}=\mu_a\), and \(\sum_ax_{ab}=\nu_b\). The quantity \(x_{ab}\) is the fraction of society of resident type \(a\) assigned to position type \(b\). Write \(r_a(b)\) and \(r_b(a)\) for the corresponding ranks, and define the two aggregate welfare scores by \(S_A(x)=\sum_{a,b}x_{ab}r_a(b)\) and \(S_B(x)=\sum_{a,b}x_{ab}r_b(a)\). The sex-equality cost is \(c_\infty(x)=|S_A(x)-S_B(x)|\).

Stability is the natural no-blocking-mass condition. For every pair \((a,b)\), let \(P_{ab}(x)=\sum_{b'\,:\,b\succ_a b'}x_{ab'}\) be the mass of type \(a\) currently assigned below \(b\), and let \(Q_{ab}(x)=\sum_{a'\,:\,a\succ_b a'}x_{a'b}\) be the mass of type \(b\) currently assigned below \(a\). The matching is stable if there is no \((a,b)\) with both \(P_{ab}(x)>0\) and \(Q_{ab}(x)>0\). In other words, no positive mass on both sides can mutually improve by moving to one another.

The problem is: given this typed market, promised that either the \(A\)-optimal stable mass matching \(x^A\) satisfies \(S_A(x^A)\ge S_B(x^A)\), or the \(B\)-optimal matching \(x^B\) satisfies \(S_A(x^B)\le S_B(x^B)\), output a stable mass matching minimizing \(c_\infty(x)\).

This is a direct continuous version of Corollary 1. The \(A\)-optimal and \(B\)-optimal matchings are computed by deferred acceptance with batches of mass: a type proposes its mass down its preference list, while the receiving type retains the most-preferred incoming mass up to its capacity. If the first inequality holds, output \(x^A\); otherwise output \(x^B\). Lemma 1's monotonicity argument carries over: at the \(A\)-optimal endpoint, every other stable matching weakly worsens \(A\)'s score and weakly improves \(B\)'s score, so if \(S_A(x^A)\ge S_B(x^A)\), its equality gap can only increase elsewhere. The other case is symmetric.

The expected classification is therefore Class A on the promised instances. Batch deferred acceptance takes time polynomial in \(|A|+|B|\) and the encoding length of the masses, independent of the number of individual agents. This is precisely the kind of high-multiplicity gain the programme is seeking.

A plausible regime is a large residency, school-placement, or labour-allocation market. Millions of residents may fall into a modest number of preference cohorts determined by specialty, location, training background, or visa status; positions may likewise fall into program or employer types. Within a cohort, agents have the same preferences and priorities over counterpart types. The paper's Mallows model supplies a natural correlated version: the masses \(\mu\) and \(\nu\) are concentrated around reference rankings, with dispersion parameters \(\phi_A\) and \(\phi_B\). The Mallows distribution is not itself the continuization; it is a plausible mechanism generating the continuous type masses.

The authors should recognize this as their problem rather than a tractable surrogate. It preserves one-to-one stability at the slot level, the stable lattice's two extreme outcomes, the exact sex-equality objective, and the endpoint condition in Corollary 1. The only change is that repeated agents and interchangeable slots are represented by their masses. That is the high-multiplicity relaxation, not an unrelated simplification.

The main weakness is that this mirror covers the paper's conditional polynomial result, not its central empirical claim that asymmetric Mallows markets usually satisfy the condition. The experiments do not prove that this remains true for continuous masses, nor that every correlated market has an endpoint sex-equal solution. The unpromised continuous problem—find a minimum-sex-equality stable mass matching when the welfare-score sign changes across the lattice—could remain hard, or could expose a genuinely continuum-specific phenomenon. That is a limitation, but also a useful research boundary rather than a reason to reject the mirror.

It generates several concrete follow-up questions: whether asymmetric Mallows masses imply the endpoint condition with high probability or in a suitable limit; whether the unrestricted continuous problem is tractable; how discrete high-multiplicity instances round from \(x\) back to integral matchings while preserving stability; and whether the paper's reported exponential stable lattices survive aggregation or collapse because many individual rotations become mass rotations.