| paper | d4-journals-jair-2024-0043 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 7
statement extracted from the paper’s text layer
Given two societies with finite type sets \(T,T'\), rational masses \(\mu,\nu\), and weak rankings of types that tie members of each type, decide whether there is a coupling \(\pi\) with marginals \(\mu,\nu\) such that the probability of reversed strict comparisons is at most \(q\). Compute that probability by drawing three matched type pairs independently from \(\pi\), and charging one when the source focal type ranks the source alternatives one way while the aligned focal type ranks the aligned alternatives in the opposite order; tied comparisons contribute zero.
Each society is a finite distribution over roommate preference types; a type ranks cohorts and ties members of its own cohort. A coupling \(\pi\) aligns fractions of the two populations. The objective is the probability, over three independent draws from \(\pi\), that the focal agents disagree on the ordering of the other two agents. This gives a finite threshold problem with a cubic objective in \(\pi\).
The paper chose Stable Roommates partly because it has strict rankings over named agents and no agent categories; the proponent offers a cohort scenario but does not establish that the authors would accept this change to the preference model.
fatal: False
The mirror covers Proposition 7’s NP-completeness result for comparing Stable Roommates instances by swap distance. It leaves the Spearman-distance result, the mutual-attraction results, the synthetic-instance maps, and the stable-matching experiments untouched.
My lead is a high-multiplicity version of the paper’s problem of comparing two Stable Roommates instances by their swap distance. That is a good fit for this paper: comparing instances is one of its central computational objects, and its map is meant to organize instances by similarity.
The anchor is Proposition 7, proved in this paper. Given two Stable Roommates instances \(I=(A,(\succ_a)_{a\in A})\) and \(I'=(A',(\succ_{a'})_{a'\in A'})\) with equally many agents, and an integer \(\ell\), decide whether
\[
\min_{\sigma\in\Pi(A,A')}\ \sum_{a\in A}\operatorname{swap}\bigl(\sigma(\succ_a),\succ_{\sigma(a)}\bigr)\le \ell.
\]
Here \(\sigma\) is a bijection between agents, it relabels the names in each preference order, and \(\operatorname{swap}\) counts the pairs ranked in opposite orders. Proposition 7 proves this decision problem NP-complete, by reduction from Kemeny Score.
I would mirror it with Continuous Swap Alignment. An instance consists of two societies \(S=(T,\mu,\succ)\) and \(S'=(T',\nu,\succ')\). Each has finitely many agent types, rational masses summing to one, and a strict ranking of the types by each type. Agents of a type share its ranking; members of any one type are tied with each other. Thus a type is a complete description of how its agents rank the available cohorts, and its mass is their fraction of the population.
An alignment is a transport plan \(\pi_{tu}\ge 0\) with row sums \(\mu_t\) and column sums \(\nu_u\). It says what fraction of type \(t\)'s mass is aligned with type \(u\)'s mass. For three independently sampled agents \(x,y,z\) from \(S\), use \(\pi\) to align each with an agent in \(S'\). Charge one if \(x\) strictly prefers \(y\) to \(z\) while its aligned agent strictly prefers the aligned \(y\) to the aligned \(z\) in the opposite order; pairs tied in either society contribute zero. The cost \(D(\pi)\) is this disagreement probability. The problem is: given \(S,S'\) and a rational threshold \(q\), is there an alignment with \(D(\pi)\le q\)? A solution is such a transport plan; equivalently, it is a measurable relabeling of the mass in atomless versions of the two societies. In type notation, \(D\) is a cubic polynomial in \(\pi\), so this is a concrete finite-dimensional optimization problem.
A plausible regime is a large roommate pool drawn from recurring cohorts whose members share preferences over cohorts—for example, applicants in a housing system who distinguish program, shift, or accessibility groups but not individual identities within a group. The population can then be very large while the number of preference types stays modest. For this particular mirror, fractional cohort alignment is the natural co-modification: the thing being compared remains the agents’ preferences over other agents, while identity-by-identity bijections become transport of mass.
I expect hardness to transfer (Class B). Proposition 7’s reduction is driven by rankings over an expanding set of agents, through Kemeny ordering, rather than by the sheer multiplicity of identical voters. But the transfer is a conjecture, not a result: a proof would need to show that fractional alignments and within-type ties do not erase the reduction. That raises the immediate further questions: can a clone-stable reduction establish hardness, and, if so, does Continuous Swap Alignment remain hard when the number of types is bounded? The mirror covers Proposition 7’s instance-comparison problem, not the paper’s experiments or its stable-matching objectives.
The weakest point is the type symmetry. The paper deliberately studies strict, complete rankings of named agents and emphasizes that Stable Roommates has no distinct agent categories. The proposed regime changes that into rankings of cohorts with indifference within cohorts. This is a recognizable high-multiplicity extension of comparing roommate preference environments, but a referee could reasonably say it is less faithful to the paper’s strict model than the direct continuous analogue is to the paper’s map-making goal.
Proposition 7 is a genuine computational anchor, so I would not dismiss it on the ground that the paper has nothing to mirror. The difficulty is that its distance compares rankings of named agents. A single bijection \(\sigma\) relabels each agent and every name in that agent’s ranking; each disagreement concerns a focal agent and two particular other agents. That shared identity structure is central to the problem.
There are two ways to carry that structure into a high-multiplicity model, and each changes what the question is about. If a type retains strict rankings over individual identities, then those identities and their positions must be part of the type’s description. For generic Stable Roommates instances, that gives little reason to expect a small, stable support as the population grows. Adding an internal priority order to distinguish members of a cohort has the same effect: it reintroduces the individual distinctions the aggregation was meant to remove.
If instead agents rank cohorts and are indifferent among members of a cohort, the proposed transport objective is mathematically coherent, but it measures a different thing. It counts disagreement about cohort-level rankings, with within-cohort comparisons tied. Those comparisons can have positive probability in a continuum, so the change does not disappear as the population grows. The result is a cubic optimization over alignments of cohort preferences, not the high-multiplicity version of the paper’s strict-order distance. A richer continuum model could retain individual distinctions through continuous within-cohort attributes, but then the finite list of types and its support parameter no longer describe the input.
The paper gives unusually direct evidence about whether that quotient is one its authors would recognize: it presents Stable Roommates’ strict, complete rankings and lack of agent categories as reasons for choosing the problem. It also introduces the polynomial-time mutual attraction distance after showing that the more fine-grained swap distance is hard to compute. A cohort-level swap distance might be useful for a new map of cohort environments, but it would not obviously serve the paper’s aim of comparing the individual-level instances that its existing map and experiments study. Its cubic objective also offers no evident route to the programme’s LP and separation tools, though that weakens the expected payoff rather than ruling out a worthwhile complexity result.
So the strongest case against this anchor is about model identity: preserving the paper’s object appears to preserve its individual identities, while obtaining a compact population model replaces them with cohort preferences and a new comparison measure. That is a substantial objection, but it is not airtight. If the authors would accept cohort-level weak preferences as their problem, Continuous Swap Alignment is a well-posed computational question and could be worth studying. My negative case depends on judging that extension a new problem rather than a continuous mirror of Proposition 7.
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.