| paper | Stable Marriage in Euclidean Space |
| authors | — |
| venue | AAMAS 2023 |
| filed under | coalition · matching |
| judged by | gpt-5.6-terra / high (triple__gpt-5.6-terra__high__ctx2r8-rejudge1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4.3
statement extracted from the paper’s text layer
Given finite male coordinate types \(i\in I\) with masses \(p_i\) at \(x_i\in\mathbb R\), female coordinate types \(j\in J\) with masses \(q_j\) at \(y_j\in\mathbb R\), and \(\rho\in[0,1]\), does a stable transport \(z_{ij}\geq0\) with marginals \(p,q\) exist that assigns mass only to pairs whose strict-distance population rank is at most \(\rho\) for both endpoints?
A high-multiplicity \(1\)-dimensional Euclidean matching market: types are coordinate cohorts with masses \(p_i,q_j\), variables \(z_{ij}\) transport cohort mass, and the objective minimizes worst normalized distance-rank subject to marginal and no-blocking-mass constraints.
The mirror covers complete-list \(1\)-Euclidean Regret-SMT in Theorem 4.3; it leaves the forced, egalitarian, incomplete-list, and higher-dimensional results alone.
The strongest mirror is the paper’s one-dimensional, complete-list regret problem: Theorem 4.3, proved in this paper, states that *1-Euclid-Reg-SMT* is polynomial-time solvable when preference lists are complete.
Call the continuous problem 1D Euclidean Regret-Stable Transport (lead). An instance has finitely many male types \(i\in I\) at coordinates \(x_i\in\mathbb R\), with masses \(p_i\), and female types \(j\in J\) at coordinates \(y_j\), with masses \(q_j\), where both totals are one. Each type’s preference is, exactly as in the paper, increasing Euclidean distance; lists are complete. A solution is a nonnegative transport matrix \(z_{ij}\), with row sums \(p_i\) and column sums \(q_j\). Thus \(z_{ij}\) is the fraction of the whole market consisting of type-\(i\) men matched to type-\(j\) women.
Stability has a direct mass interpretation. For every type pair \((i,j)\), it must not be the case that a positive mass of type \(i\) is assigned to women strictly farther away than \(j\), while a positive mass of type \(j\) is assigned to men strictly farther away than \(i\). If both occurred, an arbitrarily small amount of those two dissatisfied cohorts could form a blocking mass-pair. This is precisely the paper’s strict-blocking-pair definition, with people replaced by interchangeable infinitesimal people.
For regret, replace an absolute rank by a population percentile. Define the rank of female type \(j\) for male type \(i\) as the total female mass strictly closer to \(x_i\) than \(y_j\) (with one fixed, explicit convention for equal-distance ties). Define the reverse rank analogously. Given \(\rho\in[0,1]\), ask whether there is a stable transport \(z\) that assigns positive mass only to pairs whose rank for both sides is at most \(\rho\). Equivalently, optimize the minimum possible worst normalized rank. A rational matrix \(z\) satisfying the marginal, regret-support, and no-blocking conditions is a solution certificate.
This is not merely “fractional matching” dressed up as continuity. The continuous object is the society: \(p_i\) and \(q_j\) are cohort sizes, and the flow records how those cohorts are matched. With all masses \(1/n\) and integral flows, one recovers the paper’s finite model, up to the harmless normalization/off-by-one choice between rank \(t\) and percentile roughly \(t/n\). Allowing the flow to split is the high-multiplicity relaxation.
There is a very plausible regime. Take a large dating or employment platform that represents people by a one-dimensional compatibility or geographic coordinate, with categories such as region, qualification band, age band, or an explicitly coarse questionnaire score. There may be millions of participants but dozens or hundreds of materially distinct cohorts. A platform or regional planner naturally says “no cohort should be assigned outside its best \(8\%\) of the feasible opposite-side population,” not “no person should receive their 4th-ranked named individual.” This is particularly close to the paper’s own dating-agency motivation; it changes neither the distance-based preference rule nor the stability notion, only replaces named agents by the populations that the application already aggregates.
I would expect this lead problem to be Class A, though that is a research prediction rather than a consequence of Theorem 4.3. The theorem is meaningful evidence: in one dimension, complete Euclidean preferences impose the same strong interval geometry that makes the authors’ discrete regret problem tractable. More importantly, the hard indivisible re-selection chains of finite matching become divisible cohort adjustments. A likely route is a characterization of stable transports by one-dimensional interval cuts, followed by a flow/LP or interval dynamic program. It is not enough simply to write an ordinary transportation LP: the exact no-blocking condition is disjunctive in a naïve formulation, especially with ties. Establishing the right stable-transport polytope is therefore the first real computational question, not a cosmetic reformulation.
The immediate follow-ups are worthwhile: does the stable-transport feasible region in 1D admit a polynomial separation oracle; does an optimal continuous solution round to additive-regret guarantees for a finite high-multiplicity market; and does the phase change in Theorem 3.1—NP-hardness in two dimensions—survive mass splitting or disappear? The last would sharply test the programme’s central claim about which discrete combinatorics are caused by indivisible population.
The scope of this case is deliberately narrow: it covers the complete-list, one-dimensional Regret-SMT result of Theorem 4.3, not the paper’s forced, egalitarian, incomplete-list, or two-dimensional results. That is enough. It is the result for which the population-level reading is most natural, because regret already has a direct percentage-of-market interpretation.
The weak point is that this needs a genuinely high-multiplicity institution. A small dating pool, a kidney exchange, or a committee hiring a handful of people is not rescued by calling agents “mass”; the original finite model is the right object there. Also, some real matching markets have idiosyncratic information that creates too many types. But neither objection touches the large-platform or regional-cohort regime above, where anonymity within a type is a substantive feature of the model rather than an approximation convenience.
I cannot make the requested universal negative case honestly. Theorem 4.3’s anchor survives.
The best objection is that the proposed percentile-regret objective is not literally the paper’s named-agent rank objective: coarsening people into coordinate types creates substantial ties, and a “best 8% of mass” guarantee deliberately ignores distinctions among individuals at the same distance. Moreover, real dating platforms often rely on idiosyncratic features, messaging, and bilateral consent, so their effective type space may be too large for high multiplicity.
But neither point defeats the better mirror. A market genuinely organized around a coarse, one-dimensional compatibility/geographic score has many interchangeable agents per type; that is exactly a high-multiplicity regime, not an illicit loss of identity. The transport matrix retains every fact the proposed problem uses—type, distance preference, partner type, and cohort mass. Its no-blocking condition is also a legitimate weak-stability analogue: if mutually dissatisfied positive cohorts exist, arbitrarily small matched subcohorts can deviate.
Nor is fractional pairing a fundamental objection. Rational transport can be implemented by scaling the market, and the continuum model is precisely the relaxation of such large replicated markets. The proponent’s recovery claim for unit masses and integral flows is sound up to the stated normalization and tie convention.
Thus one can argue that this mirror is narrower than the paper’s motivating applications and that its percentile regret is a new population-level objective. One cannot plausibly argue that no worthwhile scenario exists. A large regional employment or platform market with coarse observable cohorts supplies one, and it preserves the paper’s central symmetric Euclidean preference structure. The negative case is therefore weak at its decisive point: it cannot rule out the lead continuous question, so this paper should not be rejected on continuization grounds.
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.