| paper | Ordinal Hedonic Seat Arrangement under Restricted Preference Domains: Swap Stability and Popularity |
| authors | Anaëlle Wilczynski |
| venue | IJCAI 2023 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 8
statement extracted from the paper’s text layer
Given a finite type set \(\Theta\), rational masses \(\mu_\theta\ge 0\) with \(\sum_{\theta\in\Theta}\mu_\theta=1\), and each type's strict order \(\succ_\theta\) over partner types, form \(A=\bigsqcup_{\theta\in\Theta}A_\theta\) with \(\lambda(A_\theta)=\mu_\theta\), treating partners of the same type as tied. On mass-IMB instances, obtained by iteratively removing \(\delta=\min(r_\theta,r_\phi)\) of mutually best residual types, decide whether there exists a measurable fixed-point-free involution \(M:A\to A\) such that \(\Delta(M',M)\le 0\) for every feasible involution \(M'\), where \(\Delta(M',M)\) is the mass preferring its partner type under \(M'\) minus the mass preferring its partner type under \(M\); equivalently, construct such an \(M\) or a symmetric type-flow \(x_{\theta\phi}\) with a realization.
An atomless typed roommate market with finite types \(\Theta\), masses \(\mu\), partner-type orders \(\succ_\theta\), and mass-IMB elimination; the decision object is a measurable fixed-point-free involution \(M\), or a symmetric type-flow \(x_{\theta\phi}\) plus realization, and the objective is \(\min_M\sup_{M'}\Delta(M',M)\).
Strict named-agent IMB does not automatically descend to mass-IMB: type anonymity can create mutually best type masses even when no named clone pair is mutually best, so stability-to-popularity must be reproved for weak type preferences and positive diagonal mass.
fatal: False
The mirror covers Theorem 8's constructive popularity guarantee for \(2\)-cluster graphs under IMB, while leaving the swap-stability results, path and cycle cases, larger cluster cases, negative propositions, and preference-extension classification untouched.
The strongest positive case is a high-multiplicity typed roommate market, mirroring the paper’s Theorem 8:
There always exists a polynomial-time computable popular arrangement in a \(2\)-cluster graph under iteratively mutual best preferences.
This theorem is proved in the paper. Its proof uses Abizada’s earlier exchange-stability result and the known implication that a stable roommate matching is popular, but the stated arrangement theorem itself is proved here.
The scenario is a large population of \(Q\) people divided among \(\tau\) recurring preference types, with \(Q\gg\tau\). Think of repeated cohorts of students, residents, or employees being assigned to \(Q/2\) identical two-person rooms or work pairs. A type records the agent’s complete relevant preference over partner types; \(\mu_\theta\in\mathbb{Q}_{\ge0}\) is the fraction of the population of type \(\theta\), with \(\sum_\theta\mu_\theta=1\). In a \(2\)-cluster graph, neighborhoods are singletons, so the choice of Fishburn, Gärdenfors, or responsive-set extension is immaterial: the only relevant comparison is between potential partners.
I would call the continuous problem Mass-Popular Roommate Arrangement, \(\mathrm{MPRA}_\infty\). Its population is the atomless space
\[ A=\bigsqcup_{\theta\in\Theta}A_\theta, \qquad \lambda(A_\theta)=\mu_\theta . \]
A feasible arrangement is a measurable fixed-point-free involution \(M:A\to A\): every agent is assigned exactly one partner and \(M(M(a))=a\) almost everywhere. Equivalently, it can be represented by a symmetric type-flow \(x_{\theta\phi}\), where \(x_{\theta\phi}\) is the mass of type-\(\theta\) agents paired with type \(\phi\), satisfying
\[ x_{\theta\phi}=x_{\phi\theta}, \qquad \sum_{\phi\in\Theta}x_{\theta\phi}=\mu_\theta . \]
The diagonal \(x_{\theta\theta}\) represents pairs formed by two different agents of the same type; it is not self-matching. Thus \(x\) is an aggregate census of indivisible two-person rooms, not fractional assignment of one person to several partners.
For two arrangements \(M\) and \(M'\), define the popularity margin
\[ \Delta(M',M) = \lambda\!\left(\left\{a: \operatorname{type}(M'(a)) \succ_{\theta(a)} \operatorname{type}(M(a)) \right\}\right) - \lambda\!\left(\left\{a: \operatorname{type}(M(a)) \succ_{\theta(a)} \operatorname{type}(M'(a)) \right\}\right). \]
The continuous objective is to find \(M\) minimizing its worst defeat margin
\[ \Phi(M)=\sup_{M'}\Delta(M',M). \]
The decision version asks whether some \(M\) satisfies \(\Phi(M)\le0\); a solution is a measurable matching, or equivalently a finite type-flow together with a realization of it, satisfying that inequality against every alternative arrangement.
The preference restriction is the natural mass version of IMB. Starting with residual masses \(r_\theta=\mu_\theta\), repeatedly choose two residual types \(a,b\) such that \(a\) ranks \(b\) above every currently available partner type and \(b\) ranks \(a\) above every currently available partner type. Pair mass
\[ \delta=\min(r_a,r_b), \]
decrease both residual masses by \(\delta\), and continue. If two residual portions of one type are mutually best, they may be paired with each other. The instance is mass-IMB if this elimination exhausts the population. The decomposition is not supplied as part of the solution; it can be found by scanning the finite type orders and masses.
The expected result is a direct continuous analogue of Theorem 8:
\[ \text{Mass-IMB } \mathrm{MPRA}_\infty \text{ is solvable in } \mathrm{poly}(\tau,L) \text{ time,} \]
where \(L\) is the encoding length of the rational masses. The greedy mutual-best elimination constructs the candidate arrangement. The paper’s blocking-pair argument should lift from counts to measures: no positive mass of two agents can mutually prefer one another to their assigned partners. The standard matching argument that converts stability into popularity then becomes a measure-preserving injection from better-off mass to at least as much worse-off mass, proving \(\Delta(M',M)\le0\) for every \(M'\). I therefore expect this mirror to be Class A, with a finite greedy algorithm rather than a difficult continuous optimization problem.
The high-multiplicity bridge is clean. If \(\mu_\theta=a_\theta/Q\), replace type \(\theta\) by \(a_\theta\) clones and create \(Q/2\) two-seat components. Rational type-flows scale to integer pair counts, and the popularity margin divided by \(Q\) is exactly the mass margin. The only quotient convention is that agents of the same type are indistinguishable and tied when compared solely as members of that type. This is a modest extension of the paper’s strict named-agent model, but it preserves its actual \(2\)-cluster object: pairing people, comparing partner preferences, and counting supporters of a rematching.
The authors should recognize this as their problem rather than a tractable problem with the story removed. The paper explicitly identifies \(2\)-cluster arrangements with roommate matching, and \(\mathrm{MPRA}_\infty\) is precisely the large typed-roommate regime of that case. Existing high-multiplicity or typed-roommate work would strengthen this interpretation; it would be supporting evidence, not a novelty collision.
This mirror deliberately covers only Theorem 8. It does not claim to continuize the whole path/cycle/cluster classification, nor the cited NP-hardness results for unrestricted popular roommate matching. It generates useful follow-up questions: whether unrestricted \(\mathrm{MPRA}_\infty\) remains hard when \(\tau\) is the parameter; whether the same mass construction works for paths and cycles; and how much popularity can be guaranteed when no popular matching exists.
The weakest point is the clone-tie issue. The paper’s agents have strict preferences over named individuals, whereas a finite type quotient naturally makes agents indifferent among same-type partners. A referee could therefore call this an extension rather than a literal direct mirror. The objection is limited, however: the \(2\)-cluster case only compares singleton partners, the aggregate matching remains indivisible, and the type convention is exactly what makes a repeated-cohort roommate market well-defined. The central computational question—constructing an arrangement immune to a positive-mass majority-supported rematching—remains recognisably the paper’s popularity problem.
The strongest objection is that the proposed \(\mathrm{MPRA}_\infty\) is not literally the high-multiplicity version of Theorem 8. The paper’s IMB condition concerns named agents with strict rankings: at every stage, two specific agents must be each other’s best remaining partners. That property is not preserved by collapsing agents into types.
For example, suppose there are two \(A\)-agents and two \(B\)-agents, with both types ranking the other type first. A strict clone-level realization might have
\(a_1:b_1\succ b_2,\quad a_2:b_2\succ b_1,\quad b_1:a_2\succ a_1,\quad b_2:a_1\succ a_2.\)
No pair is mutually best, so the named-agent profile is not IMB. Yet the proposed mass condition declares \(A\) and \(B\) mutually best and pairs their masses. Thus “mass-IMB” is not inherited from the paper; it is a new preference restriction.
There are only two repairs. If one preserves strict tie-breaking among clones, those tie-breaks are relevant preferences, so agents with different rankings are different types; as the population grows, \(\tau\) grows with it and the high-multiplicity regime disappears. If one identifies same-type partners, one obtains weak preferences over types and must prove anew that the mass elimination construction yields popularity. The paper’s finite implication from stable roommate matching to popularity does not automatically establish that result for atomless matchings with type ties and positive diagonal mass.
That is the best negative case: the proponent has shown a plausible new typed roommate theorem, not a direct continuization of Theorem 8. But it does not support the universal conclusion requested here. The repaired model is exceptionally natural: a large population of recurring cohorts assigned to anonymous two-person rooms is precisely a high-multiplicity roommate market. The \(2\)-cluster graph removes irrelevant seat identities, and the type-flow \(x_{\theta\phi}\) preserves the indivisible pairing structure. Its popularity margin is a meaningful positive-mass analogue, not a degenerate limit.
Consequently, I cannot honestly defeat this anchor. The clone-tie issue means the proposed mirror needs a precise new theorem, but it is not a fundamental obstruction to a worthwhile continuous mirror. The negative verdict is therefore weak: Theorem 8 survives as a credible narrow Class A candidate, even though the proponent overstates how directly its proof transfers.
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.