| paper | Experimental paper on stable roommates |
| 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 |
Observation 9
statement extracted from the paper’s text layer
Given two finite-type societies \(P=(T,\mu,(r_t)_{t\in T})\) and \(Q=(U,\nu,(s_u)_{u\in U})\), with rational masses and finitely encoded reciprocal-rank curves, find a coupling \(y\) minimizing \(\sum_{t,u} y_{t,u}\int_0^1 |r_t(q)-s_u(q)|\,dq\) subject to marginals \(\mu\) and \(\nu\).
A finite distribution of reciprocal-attraction types, with type masses as transport supply and demand, rational step-function rank curves, and a minimum-cost transportation coupling objective.
Arbitrary reciprocal-rank profiles may not be jointly realizable by a population with mutually consistent strict preferences, so applications should either justify the profiles as measured summaries or impose a realizability condition.
fatal: False
The lead mirror covers Observation 9, mutual-attraction comparison, maps, and statistical-culture comparisons; the second covers Proposition 6, while Theorem 10 and stable-matching optimization experiments remain outside it.
I think this paper has a real continuous mirror, but it is a mirror of its central *instance-comparison/map* contribution—not a claim that Stable Roommates itself becomes an easy continuum matching problem. My lead is Continuous Mutual-Attraction Distance, anchored in Observation 9 (proved here): “Given two SR instances \(I\) and \(I'\) with \(2n\) agents each, \(d_{\mathrm{MAD}(I,I')}\) can be computed in \(O(n^3)\) time.”
In a large matching platform—say a municipal co-living, mutual-aid, or peer-support programme—people need not be treated as individually named vertices when the purpose is to compare whole markets. There may be \(10^5\) participants but only tens or hundreds of recurring behavioural reciprocity types: same eligibility/need category, stated preference pattern, and reciprocal-attraction profile. Here mass \(\mu_t\) is the fraction of participants of type \(t\). A type’s relevant description for this comparison problem is its normalized reciprocal-rank curve
\[
r_t:[0,1]\to[0,1].
\]
At preference quantile \(q\), \(r_t(q)\) records the percentile at which the prospective partner ranks a type-\(t\) participant. It is the population-limit version of a row of the paper’s mutual-attraction matrix. It need not retain every feature of a person’s preference ordering, because neither does mutual attraction distance; it is deliberately the sufficient object for this particular map statistic.
Continuous Mutual-Attraction Distance (lead). An instance consists of two finite-type societies
\[
P=(T,\mu,(r_t)_{t\in T}), \qquad
Q=(U,\nu,(s_u)_{u\in U}),
\]
where masses are rational and sum to one, and curves are rational step functions (or, equivalently, are specified at finitely many rank-quantile bins). A solution is a mass coupling \(y_{t,u}\geq0\), with
\[
\sum_u y_{t,u}=\mu_t,\qquad \sum_t y_{t,u}=\nu_u.
\]
The question is to minimize
\[
\sum_{t,u}y_{t,u}\int_0^1 |r_t(q)-s_u(q)|\,dq.
\]
Thus the decision variable is not a matching of individuals: it is the amount of societal mass identified as one reciprocal-attraction type in the first market and another in the second. This is a transportation LP. With finitely described curves, its pairwise costs are computable directly and the LP is polynomial in the number of types and curve-description length.
This is not merely analogous to Observation 9. If every discrete agent has mass \(1/(2n)\), the coupling polytope is integral, so an optimal coupling is a bijection of rows; after the harmless normalization from ranks to percentiles, the problem is exactly the paper’s minimum-weight bipartite matching formulation. The continuous question therefore retains the authors’ object while making the market population, rather than the list of named participants, the primitive.
I expect this to be Class A. It is precisely the kind of continuization that exposes standard optimization machinery: the discrete assignment behind Observation 9 becomes optimal transport between type masses. It also gives the authors’ maps a more natural applied interpretation: not “how similar are two samples of 200 named agents?”, but “how similar are two estimated preference societies, and which population segments account for the difference?”
A second, weaker but worthwhile anchor is Proposition 6 (proved here): “There is no polynomial-time algorithm to compute \(d_{\mathrm{spear}}\), unless Graph Isomorphism is in P.” Its continuous counterpart retains the global relabelling that mutual-attraction distance intentionally drops.
Continuous Isomorphic Spearman Distance. A finite-type society has type masses \(\mu\) and, for each type \(t\), a strict ranking of partner types. Let \(\rho_t(u)\) be the percentile/midrank of type \(u\) in \(t\)’s ranking. Given two societies with the same type-mass multiset, ask for a mass-preserving bijection \(\phi:T\to U\) minimizing
\[
\sum_{t,u\in T}\mu_t\mu_u
\left|\rho_t(u)-\rho'_{\phi(t)}(\phi(u))\right|.
\]
A solution is the single global renaming \(\phi\), not an independently chosen transport plan for each row. This is the continuous population analogue of Definition 4’s isomorphism-respecting Spearman distance: it compares preference structures after identifying the same social roles across markets.
A plausible regime is repeated large markets with a fixed standardized catalogue of participant categories—for example, the same service areas, support needs, and schedules in successive annual cohorts—but changing preferences between categories. There may be millions of people and only a moderate number of categories; their frequencies are stable by construction. If composition changes too, one can report it separately or add a composition term, but that would no longer be the exact isomorphic-distance question.
I expect this one to be Class B: setting every type mass equal and taking one type per original agent recovers the discrete distance, up to fixed normalization. Proposition 6 gives the paper’s Graph-Isomorphism barrier for that embedded boundary case. This does not establish NP-hardness, but it does say that passing to population fractions does not automatically dissolve the hard global relabelling combinatorics.
The first question is the stronger case. It covers the paper’s practical contribution in Observation 9, its maps, and its comparison of statistical cultures. The second covers Proposition 6 and explains a meaningful boundary: preserving full isomorphism is qualitatively more demanding than transporting reciprocal-attraction mass.
The main weakness is also visible in the paper itself: mutual-attraction distance is not isomorphic and can identify non-isomorphic instances with different stable-matching existence behaviour. So Continuous Mutual-Attraction Distance is not a valid surrogate for stability, egalitarian stable matching, or every other SR outcome. But that does not defeat this mirror. The paper explicitly offers it as a computationally usable, practically predictive distance for mapping instances, not as a complete invariant. In that declared role, the high-multiplicity version is especially natural.
I would not stretch the claim to Theorem 10. Its exact realizability question is built around individual rows of a mutual-attraction matrix; whether an equally faithful aggregate realizability notion survives type compression is a substantive further problem, not something this positive case should assume away.
The best negative case starts from a genuine mismatch: Stable Roommates is relational at the individual level. An agent’s mutual-attraction row is not an intrinsic preference type; it is produced by that agent’s position in everyone else’s rankings. Compressing a market into masses of reciprocal-rank curves can therefore erase the compatibility information that makes an SR instance an SR instance. The paper’s own Theorem 10 is a warning here: even finite mutual-attraction matrices are not freely specifiable—realizability already encodes difficult global consistency constraints. A transportation LP over arbitrary row-curves risks comparing summaries that need not arise from any population of mutually ranking agents.
That objection substantially weakens the claimed applied story for Continuous Mutual-Attraction Distance. In an actual co-living or peer-support platform, people do not normally recur in large multiplicities with the same complete reciprocal-rank curve; the curve depends on whom they and everyone else encounter. If instead types are meaningful, exogenous categories—need, schedule, eligibility, geography—then their category labels already provide the cross-market correspondence. Transporting anonymous “reciprocal-attraction types” is no longer clearly the question a platform needs answered.
But it does not defeat Observation 9’s anchor. This is because \(d_{\mathrm{MAD}}\) itself deliberately factors through exactly such row summaries. It is not an isomorphism-respecting SR invariant, and the authors explicitly accept that it cannot predict stable-matching existence. Once the target is the paper’s map statistic rather than stability, a society may reasonably be specified directly as a distribution of reciprocal-rank profiles. Repeated, category-based markets can make that a sensible high-multiplicity object, and the proposed transport distance exactly recovers the discrete assignment formulation when every row has equal atomic mass. Calling it “only generic optimal transport” is a reason it may be low-priority, not a reason the continuous question is ill-posed.
The Proposition 6 anchor is weaker in application but harder to rule out. Its proposed model works only under a restrictive regime: the two societies must have the same multiset of type masses, and a single global relabelling of types is meaningful only when categories are structurally anonymous. In a standardized annual market, categories normally have semantic identities, so one would align them directly rather than solve for an isomorphism; in a changing endogenous taxonomy, type splitting and changing frequencies make the required bijection brittle. Thus this is unlikely to be a broadly useful empirical comparison framework.
Still, that limitation does not eliminate the mirror. There are coherent settings—unlabelled recurring social roles or structurally compared generated markets—in which global relabelling is precisely the desired invariance. Equal-mass types recover the original discrete problem up to normalization, so it is a faithful continuous/high-multiplicity boundary case rather than a formal trick.
So I cannot honestly sustain the requested universal negative conclusion. The strongest criticism is that these mirrors continuize a deliberately lossy *instance-comparison statistic*, not the stable-roommates allocation problem, and their natural applied regimes are narrower than the proponent suggests. Yet the Continuous Mutual-Attraction Distance anchor survives that criticism: it is a well-defined high-multiplicity comparison problem matching the paper’s stated central contribution. Since one surviving anchor is enough, this paper should not be rejected as having no worthwhile continuous mirror.
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.