| paper | A Map of Diverse Synthetic Stable Roommates Instances |
| authors | — |
| venue | AAMAS 2023 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 10
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\), and piecewise-constant profiles \(R_t:[0,1]\to[0,1]\) on quantile blocks induced by \(\mu\), decide whether strict type orders \(\succ_t\) over \(T\setminus\{t\}\) exist such that, whenever type \(u\) occupies quantile \(z\) in \(t\)'s order, \(R_t(z)\) equals the normalized position of \(t\) in \(u\)'s order; the equal-mass step-function case is the matrix-realizability problem of Theorem 10.
A society consists of types \(T\) with masses \(\mu\); each type has a strict order over other types, and the input specifies reciprocal-rank profiles. The decision variables are the type orders \((\succ_t)_{t\in T}\), and the objective is exact profile feasibility, with approximate realizability minimizing profile discrepancy as a natural variant.
The equal-mass matrix is essentially the original \(q\)-agent problem renamed, while cloning cohorts changes the reciprocal-rank dimensions, so the proposed model does not yet establish an exact high-multiplicity realization of strict Stable Roommates.
fatal: False
The mirror covers Theorem 10 and the mutual-attraction distance computation in Observation 9; it leaves stable-matching existence, blocking-pair statistics, statistical-culture experiments, and ILP running-time behavior alone.
The strongest positive case is narrow but real: the paper’s computational core—the distance between stable-roommates instances—has a clean high-multiplicity continuation, and its realizability obstruction has a second continuation in which hardness survives. I would lead with the first.
My lead problem is Continuous Mutual-Attraction Distance, \(\mathrm{CMAD}_\infty\), mirroring Observation 9. Observation 9 is proved in this paper: \(d_{\mathrm{MAD}}\) can be computed in \(O(n^3)\) time by minimum-weight perfect matching.
Consider a roommate platform with a very large population divided into \(q\) recurring cohorts: for example, residents in the same campus programme, work shift, neighbourhood, accessibility category, or lifestyle group. Agents in cohort \(t\) share the same preference kernel over cohort types. The population is represented by rational masses \(\mu_t\), with \(\sum_t\mu_t=1\), and \(q\ll N\), where \(N\) is the number of actual residents. This is a scenario, not a claim that arbitrary SR instances are high-multiplicity: uniformly random named-agent preferences would generally have \(q\) close to \(N\).
For each type \(t\), let \(v_t:[0,1]\to[0,1]\) be its normalized mutual-attraction profile. The coordinate \(z\) is a quantile in \(t\)’s ordered list of potential partners; \(v_t(z)\) records the normalized position in which the partner at quantile \(z\) ranks type \(t\). With finitely many cohort types, these are rational step functions. They are the continuum counterparts of the rows \(MA_I(a)\) in the paper.
An instance of \(\mathrm{CMAD}_\infty\) consists of two such societies, \((T,\mu,v)\) and \((T',\mu',v')\). Its decision variable is a coupling \(\pi=(\pi_{tu})\), where \(\pi_{tu}\) is the mass of type \(t\) in the first society matched to type \(u\) in the second:
\[ \sum_{u\in T'}\pi_{tu}=\mu_t,\qquad \sum_{t\in T}\pi_{tu}=\mu'_u,\qquad \pi_{tu}\ge 0. \]
The objective is
\[ \min_{\pi}\; \sum_{t\in T}\sum_{u\in T'} \pi_{tu}\int_0^1 |v_t(z)-v'_u(z)|\,dz. \]
The solution is the optimal coupling and its value. Thus \(\mathrm{CMAD}_\infty\) is precisely a Wasserstein-type transport version of the paper’s mutual-attraction distance, with population mass replacing individual agents.
This is not merely fractionalizing an outcome. The continuous object is the society itself, while the action is a mass-level analogue of the paper’s agent matching. If every type has rational mass, scaling by a common denominator turns the coupling into a matching between clones. Conversely, aggregating identical agents in a finite instance produces the mass formulation. For unit masses and step functions encoding the rows \(MA_I(a)\), the objective is \(d_{\mathrm{MAD}}\), up to the fixed normalization of ranks.
The expected classification is Class A. The problem is a rational minimum-cost transportation LP with \(|T||T'|\) variables, hence is solvable in time polynomial in the number of types, the number of step-function pieces, and the encoding length. Observation 9’s perfect-matching algorithm is exactly the unit-mass special case. The natural continuation questions are distance to a specified statistical culture, barycentres of roommate populations, nearest realizable mutual-attraction profile, and approximation when the type kernels are given succinctly.
The mirror is especially plausible because \(d_{\mathrm{MAD}}\) is the paper’s own proposed practical distance, not an unrelated stable-matching quantity. The paper explicitly treats mutual-attraction vectors as the representation on which its map is built. I would not claim that \(\mathrm{CMAD}_\infty\) captures every later experiment in the paper: it does not directly solve stable matching, nor does it explain the empirical ILP running times. It mirrors the paper’s distance-computation result and the population-comparison problem underlying the map.
A second, harder mirror is Continuous Mutual-Attraction Realizability, based on Theorem 10. Theorem 10 is proved in this paper, with the proof supplied in the full version: deciding whether a given \((2n)\times(2n-1)\) matrix is the mutual-attraction matrix of some SR instance is NP-complete.
Define \(q=2n\) anonymous cohorts, each with mass \(1/q\), and let \(M\in\{1,\ldots,q-1\}^{q\times(q-1)}\) be a proposed aggregate mutual-attraction profile. A solution consists of a strict type-level preference order \(\succ_i\) over the other \(q-1\) cohort types for every \(i\in[q]\). If \(u_i(j)\) denotes the type in position \(j\) of \(i\)’s order, the solution must satisfy
\[ M_{i,j} = \operatorname{pos}_{\succ_{u_i(j)}}(i) \]
for every \(i\) and \(j\). In words, the \(j\)-th cohort that type \(i\) prefers must rank type \(i\) at exactly the reciprocal position specified by \(M_{i,j}\). The arbitrary-mass version replaces positions by normalized rank intervals and asks for equality of the resulting step functions.
This is a genuine high-multiplicity interpretation: each of the \(q\) roles may represent an arbitrarily large cohort, while the question concerns whether the observed aggregate reciprocal-rank data have any consistent underlying preference system. It is also a natural data-validation problem for a matching platform: can reported mutual-attraction summaries actually have arisen from any coherent population of preferences?
The expected classification is Class B. The equal-mass typed restriction is already the matrix-realizability problem in Theorem 10, so the NP-hardness lives in the number of distinct types and their reciprocal constraints, not in the number of named individuals. Cloning every cohort arbitrarily many times does not remove that obstruction. This is exactly the kind of hardness the programme expects continuization to preserve: multiplicity can disappear while type-level combinatorics remain.
It generates useful further questions: weighted realizability for arbitrary rational masses, approximate realizability under \(L_1\) or transport distance, parameterized complexity in the number of types or distinct rows, and whether a convex relaxation characterizes the closure of realizable continuous profiles. The distance from an arbitrary profile to the realizable set would connect this anchor back to \(\mathrm{CMAD}_\infty\).
The weakest point is the strict-preference issue. The paper’s SR agents rank named individuals strictly and explicitly says that there are no agent types. A high-multiplicity cohort model naturally creates block preferences, so the exact continuous mirror is a measure-valued or weak-preference extension, with within-cohort distinctions suppressed. A referee could reasonably say that this changes the original SR model. The answer is that the lead problem is anchored in \(d_{\mathrm{MAD}}\), whose input is already the mutual-attraction profile rather than the full local stability structure, while the second problem preserves the paper’s global reciprocal-consistency constraint and its NP-completeness. Thus the case is not that the whole paper continuizes unchanged; it is that one of its central computational objects has an exact transport relaxation, and another has a meaningful high-multiplicity version where hardness remains.
The negative case cannot honestly rest on “there is no computational result.” The paper has two clear anchors: Observation 9 and Theorem 10. The stronger objection is that neither proposed continuation preserves the object being computed.
For Observation 9, \(d_{\mathrm{MAD}}\) is a minimum-weight matching between rows whose coordinates are positions in a strict preference order over individual agents. The proposed \(v_t:[0,1]\to[0,1]\) suppresses precisely the structure that makes those rows mutual-attraction rows. If a cohort has positive mass, a partner type occupies a block of ranks, not one rank. Its reciprocal rank is therefore an interval or a distribution of ranks, depending on how individuals inside the block are ordered. A single step function \(v_t\) does not encode that information.
This is not repaired by cloning. Start with \(q\) cohorts and clone every member \(K\) times. The resulting stable-roommates instance has \(qK\) agents, so its mutual-attraction rows have \(qK-1\) coordinates. The proposed profile still has only \(q-1\) cohort-level coordinates. Thus the coupling \(\pi\) is a valid transport problem on summaries, but it is not the high-multiplicity expansion of \(d_{\mathrm{MAD}}\). The claim that rational masses can be scaled to clones applies to the transport variables, not to the profile costs supplied to that transport problem.
There are only three ways to close this gap. One can retain strict individual rankings, in which case the within-cohort tie-breaking information must be included in the type. As the cohorts grow, that information is essentially individual-level, so the fixed-type high-multiplicity regime disappears. One can quotient agents inside a cohort and allow block preferences or ties, but that is a different matching model. Or one can retain the whole distribution of within-block rank profiles; then the type space becomes a measure over preference kernels, and the proposed problem is a generic Wasserstein distance between feature distributions rather than the paper’s \(d_{\mathrm{MAD}}\).
A finite role-template or graphon-style model could certainly be designed. But that would be a new model whose relation to stable-roommates instances, blow-up conventions, and stability would need to be proved. The paper itself shows why this matters: mutual-attraction matrices can coincide for non-isomorphic instances, one admitting a stable matching and the other not. Consequently, the proposed transport can be a useful comparison of derived profiles while being largely blind to the central stable-roommates structure. Its polynomial transportation formulation is mathematically correct, but generic; the paper supplies no reason that this feature-space problem is the computational object worth continuizing.
Theorem 10 presents the same problem more sharply. The proposed \(q\)-by-\((q-1)\) matrix with \(q\) equal-mass cohorts is simply the original matrix-realizability problem with its \(q\) agents renamed “cohorts.” The multiplicity is inert. If every cohort is cloned \(K\) times, the actual mutual-attraction matrix is \(qK\)-by-\((qK-1)\), not the proposed \(M\). Hence the exact NP-completeness result no longer applies to the mass model.
A better quotient model would define reciprocal rank by cumulative cohort mass, perhaps using rank intervals or a preference graphon. That is a respectable continuous question, but Theorem 10 gives no hardness result for it. In the atomless limit, the individual rank slots on which the theorem depends have measure zero; the discrete reciprocal-position constraints may collapse into cumulative-mass equalities, inequalities, or a different feasibility problem altogether. Conversely, preserving the original slot-level constraints requires reinstating within-cohort identities and tie-breaking, which again removes the high-multiplicity interpretation.
This is not the forbidden objection that the resulting problem might be easy, nor that hardness surviving would be uninteresting. The issue is prior: the proposed reductions have not shown that either transport or realizability is a continuous population version of the named result. They either discard the individual reciprocal structure or retain it by smuggling individuality back into the types.
The honest conclusion is therefore weaker than the requested universal claim. The paper does not provide a compelling continuous mirror as stated. The first anchor can be rescued as a new population-level transport study over mutual-attraction profiles, and the second can be rescued as a new block-preference realizability problem. But once rescued, both require substantial new modelling and theory; neither is established by the paper’s results. I cannot honestly claim that no worthwhile mirror could ever be invented, but the proponent’s two anchors do not yet show one.
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.