| paper | A stable marriage requires communication |
| authors | Yannai A. Gonczarowski, Noam Nisan, R. Ostrovsky, Will Rosenbaum |
| venue | GEB 2019 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: other · adjudication: proved
full proof & adversarial review →
Corollary 3.1
statement extracted from the paper’s text layer
Given finite woman-type and man-type sets \(A\) and \(B\), rational masses \(\mu\) and \(\nu\), and strict rankings of opposite-side types, find a nonnegative mass matching \(x=(x_{ab})\) with \(\sum_b x_{ab}=\mu_a\) and \(\sum_a x_{ab}=\nu_b\) whose type-level blocking pairs are absent, or whose aggregate divorce distance \(d_\infty(x)=1-\max_{y\in\mathcal S}\sum_{a,b}\min\{x_{ab},y_{ab}\}\) is at most fixed \(\varepsilon<\tfrac12\).
A capacitated typed stable-matching model: types carry masses, \(x_{ab}\) is matched mass, agents within a type are interchangeable, and stability forbids a pair of types with positive mass on both sides preferring one another to their assigned type distributions. The computational objective is to find such an \(x\), or minimize \(d_\infty(x)\).
The proposed \(d_\infty\) identifies matchings that differ on every named couple whenever those agents share types, so it is not literally the paper's divorce distance; the proponent does not fully resolve that semantic loss.
fatal: False
It covers Corollary 3.1's \(\Omega(n^2)\) lower bound for finding a \((1-\varepsilon)\)-stable marriage, recast over typed masses; it leaves the localized communication lower bounds, blocking-pairs questions, and rotation-poset algorithm unmirrored.
The strongest positive case is a high-multiplicity version of the paper’s approximate-stable-marriage problem. My lead anchor is Corollary 3.1, proved in this paper from Theorem 3.1; its underlying disjointness lower bound is cited from Kalyanasundaram–Schintger and Razborov.
Corollary 3.1 states that, for a marriage market with \(n\) women and \(n\) men, full preference lists, and \(0\leq\varepsilon<\tfrac12\), every deterministic or randomized algorithm using any Boolean queries to the women’s and, separately, the men’s preferences needs \(\Omega(n^2)\) queries in the worst case to find a \((1-\varepsilon)\)-stable marriage. Here \((1-\varepsilon)\)-stability means that the output marriage differs in at most \(\varepsilon n\) couples from some exactly stable marriage. The result is proved here, via Theorem 3.1’s \(\Omega(n^2)\) communication lower bound.
My continuous problem is:
Continuous Approximate Stable Marriage. An instance consists of finite sets \(A\) and \(B\) of woman-types and man-types; rational population masses \(\mu_a\) and \(\nu_b\), each summing to \(1\); and, for every \(a\in A\) and \(b\in B\), a strict ranking of the opposite-side types. A solution is a mass matching \(x=(x_{ab})_{a\in A,b\in B}\) satisfying
\[ \sum_{b\in B}x_{ab}=\mu_a \quad\text{and}\quad \sum_{a\in A}x_{ab}=\nu_b. \]
The matching is stable if there is no pair of types \((a,b)\) such that positive mass of type \(a\) is matched below \(b\), while positive mass of type \(b\) is matched below \(a\). Formally, for every \((a,b)\), at least one of
\[ \sum_{b':\,b\succ_a b'}x_{ab'}=0, \qquad \sum_{a':\,a\succ_b a'}x_{a'b}=0 \]
must hold.
For a proposed matching \(x\), define its normalized divorce distance by
\[ d_\infty(x) = 1-\max_{y\in\mathcal S} \sum_{a,b}\min\{x_{ab},y_{ab}\}, \]
where \(\mathcal S\) is the set of stable mass matchings. The task is to output \(x\) with \(d_\infty(x)\leq\varepsilon\), for fixed \(0\leq\varepsilon<\tfrac12\). In particular, an exactly stable \(x\) is an acceptable answer.
This is genuinely a population continuization. A type is a cohort of agents with the same relevant preference order over counterpart types; \(x_{ab}\) is the mass of type-\(a\) agents matched to type-\(b\) agents. Individuals still receive one integral partner: the fractional object is only the aggregate matching matrix. If all masses have denominator \(N\), then \(Nx_{ab}\) is the number of finite agents of the two corresponding types matched together.
The natural regime is a large centralized matching market—say residency applicants and programme slots, or graduates and employers—with \(N\) agents per side but only \(\tau=|A|+|B|\) repeated preference classes. One might have \(N\) in the millions and \(\tau\) in the hundreds or thousands. Types could encode qualification bands, specialties, locations, and standardized preference profiles. This is exactly a high-multiplicity regime: the population is large, while the number of distinct computationally relevant agent types is comparatively small.
I expect this problem to be Class A. A mass-splitting deferred-acceptance procedure can let each man-type propose its remaining mass down its preference order, while each woman-type retains its most preferred incoming mass up to capacity \(\mu_a\). Each type-pair is processed only finitely many times, with rational arithmetic, giving a procedure polynomial in \(\tau\) and the input bit length. Its output is exactly stable, hence also \((1-\varepsilon)\)-stable.
The important point is what happens to the paper’s lower bound. Its \(\Omega(n^2)\) barrier is an information barrier caused by the need to discover almost all pair-specific preference information. In the high-multiplicity instance, that information is compressed into the type-level rankings and masses, whose description has size polynomial in \(\tau\), not \(N\). Thus the lower bound should not transfer as \(\Omega(N^2)\); it is precisely the kind of population-multiplicity difficulty that can disappear under continuization.
The authors should recognize this as their problem rather than as an unrelated relaxation. The paper explicitly motivates implicit preferences through participant “types,” and its central object remains unchanged: a two-sided preference profile, a matching, blocking pairs, and distance from stability. What changes is only the representation of a large repeated population. The continuous question therefore tests the paper’s own central claim in a new regime: is quadratic information necessary because stable marriage is intrinsically global, or because the input contains \(N^2\) individually addressable preference facts?
This mirror covers only Corollary 3.1’s approximate-stable-marriage result. It does not claim to continuize the paper’s localized marital-status problems or its rotation-poset algorithm. Natural follow-up questions include the complexity of computing \(d_\infty(x)\) for a given matching, the dependence on \(\tau\) and minimum type mass, and rounding a continuous solution back to \(N\) finite agents.
The weakest point is that the paper’s theorem concerns strict preferences over named individuals, whereas the mirror uses strict preferences over types and therefore quotients away within-type identity. A hostile referee could call this a new typed stable-flow model. I think that objection is limited rather than fatal: in a true high-multiplicity regime, counterpart identity is not part of the relevant type description, and aggregate mass matching is the natural analogue of a marriage. Still, this is a narrower positive case than a claim that every theorem in the paper has a literal continuum counterpart.
The best negative case attacks the proposed object’s fidelity to Corollary 3.1, not its tractability. The theorem is about strict preferences over named counterpart identities, and its approximate-stability distance counts exact named couples. A finite type-mass matrix erases both features.
For example, take two women and two men, with every woman ranking \(m_1\succ m_2\) and every man ranking \(w_1\succ w_2\). The unique stable marriage is \(\{(w_1,m_1),(w_2,m_2)\}\). The swapped marriage has divorce distance \(2\). Yet if both women form one type and both men another, both marriages induce the same aggregate matching \(x_{AB}=1\), and the proposed \(d_\infty\) regards both as identical and stable. Thus \(\sum_{a,b}\min\{x_{ab},y_{ab}\}\) is not the continuum counterpart of the paper’s divorce distance; it permits freely relabelling same-type people.
There are only two repairs. One can retain the strict identity-level preferences, but then the rank of \(m_1\) versus \(m_2\) is part of the relevant type information. In general, every counterpart’s identity or within-type rank becomes a separate type, so the number of types grows with \(N\) and the high-multiplicity compression disappears. Alternatively, one can declare agents within a type indifferent and study stable fractional flows. That is coherent, but it is a new stable-marriage-with-ties/capacities model, not the high-multiplicity version of the paper’s strict marriage problem. An integral realization of \(Nx\) is not enough: an arbitrary realization can be unstable in the original market.
The same mismatch appears in the complexity measure. Corollary 3.1 derives its \(\Omega(n^2)\) bound from independently addressable pairwise preference information and arbitrary Boolean queries to those individual profiles. In the proposed model, the type rankings are already compressed into an input of size polynomial in \(\tau\). The disappearance of an \(N^2\) query lower bound is therefore not a consequence about the paper’s problem; it follows from replacing its oracle by a different, much smaller input representation. A faithful continuous version would need either an identity-level measure-valued preference object, whose representation and query model are unspecified, or a finite typed model that no longer preserves the theorem’s semantics.
This is the strongest case against the anchor, but it is not airtight. If ChoCo explicitly accepts indifference within cohorts and defines “approximate stability” as overlap of aggregate type flows, the proponent’s problem is a sensible population-continuized matching problem, and the paper’s authors would likely recognize it as relevant. I therefore cannot honestly support the universal claim that no worthwhile mirror exists. The negative case can show that the proposed mirror is not faithful to Corollary 3.1’s named-couple/query-complexity result; it cannot defeat the broader typed-flow mirror altogether.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.