| paper | Strategyproof Matching of Roommates and Rooms |
| authors | Hadi Hosseini, Shivika Narang, Sanjukta Roy |
| venue | AAAI 2025 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.6
statement extracted from the paper’s text layer
Given finitely many complete agent types with masses summing to 2 and finitely many complete room types with masses summing to 1, binary type-to-type compatibility and type-to-room valuations, compute or approximate the maximum utilitarian welfare achievable by assigning room mass to unordered pairs of agent types subject to all mass-balance constraints.
A finite type-capacity model: agent and room types carry masses; variables \(x_{aa'b}\) assign room mass of type \(b\) to pairs of agent types \(a,a'\); feasibility enforces agent and room mass conservation; the objective sums the two agents' binary Leontief utilities for every assigned triple.
With few complete types, the compatibility structure becomes a block-constant capacity problem and may collapse to a routine LP, losing the individual relational structure behind the APX-hardness reduction.
fatal: False
Covers Theorem 3.6's maximum-welfare problem under binary Leontief utilities, including the symmetric high-multiplicity variant; it does not cover the strategyproofness theorems or the paper's other welfare guarantees.
The strongest honest positive case is a single anchor: Theorem 3.6, proved in this paper. It states that “finding a maximum SW roommate matching is APX-hard under binary Leontief utilities.” The paper’s construction strengthens this to binary symmetric valuations, degree-three preference graphs, and instances consisting only of L-shaped triples.
The continuous mirror I would propose is Continuous Binary-Leontief Roommate Welfare.
There are finitely many complete agent types \(A\) and room types \(B\). An agent type \(a\) specifies:
A room type \(b\) has mass \(q_b\), with \(\sum_b q_b=1\); one unit of room mass houses two units of agent mass. Types are complete: two agents of type \(a\) have identical compatibility with every type and identical room valuations. For the symmetric version, \(\chi_a(a')=\chi_{a'}(a)\).
A solution is a nonnegative mass \(x_{aa'b}\) for every unordered agent-type pair \(a\leq a'\) and room type \(b\). It denotes the mass of rooms of type \(b\) occupied by a pair of agent types \(a,a'\). It must satisfy
\[ 2\sum_b x_{aab} +\sum_{a'\ne a}\sum_b x_{\min(a,a'),\max(a,a'),b} =p_a \]
for every agent type \(a\), and
\[ \sum_{a\leq a'}x_{aa'b}=q_b \]
for every room type \(b\). The objective is to maximize
\[ \sum_{a\leq a'}\sum_b x_{aa'b} \left( \min\{\chi_a(a'),\rho_a(b)\} + \min\{\chi_{a'}(a),\rho_{a'}(b)\} \right). \]
The question is: compute an optimal feasible \(x\), or an approximation to its maximum welfare.
This is a genuine high-multiplicity version of the paper’s problem, not merely fractional welfare. If \(p_a=n_a/N\) and \(q_b=r_b/N\), clearing denominators gives \(n_a\) agents of type \(a\) and \(r_b\) rooms of type \(b\). Conversely, any rational mass solution can be realized exactly by sufficiently many clones. The variable \(x_{aa'b}\) records the limiting density of actual roommate-room triples.
The regime is plausible in large housing markets: a university or accommodation platform may have tens of thousands of residents but only a few dozen recurring preference profiles—such as smoking status, quiet-hours preference, accessibility needs, or study programme—and a small number of repeated room templates. Both agents and rooms scale together: \(2N\) residents and \(N\) rooms, with \(N\gg |A|,|B|\).
I expect this mirror to be Class A. Its formulation is an explicit linear program with \(O(|A|^2|B|)\) variables and polynomially many constraints. The APX-hardness in Theorem 3.6 comes from integral 3-dimensional-matching structure among individually represented agents. In the high-multiplicity regime, masses of one complete type can be split across several compatible triple types, making that population-level integrality obstruction disappear.
The mirror is author-recognisable: it keeps the same roommate pairing, room assignment, binary compatibility, Leontief complementarity, and utilitarian objective. It changes only the representation from named agents and rooms to repeated complete types with scaled supply.
The main weakness is that the paper’s hard reduction is highly endpoint-sensitive: every agent may have a distinct neighbourhood, so its combinatorics need not survive type aggregation. Also, this mirror does not yet cover the paper’s central strategyproofness results. Individual deviations in an atomless population are delicate and may become vacuous unless one specifies identities, priority coordinates, or a finite-clone limit. I would therefore present this as a strong continuous mirror of Theorem 3.6’s welfare problem, not as evidence that Theorems 4.4 or 4.10 automatically continuize.
It naturally generates further questions: whether the LP has bounded-gap rounding for finite clone markets; whether exact high-multiplicity integer matching is fixed-parameter tractable in the number of types; whether arbitrary cardinal Leontief values remain polynomial; and whether a meaningful, non-vacuous continuous analogue of the paper’s strategyproof mechanisms exists.
The strongest negative case is that Theorem 3.6’s hardness is carried almost entirely by identity-specific compatibility structure. Its reduction encodes a 3-dimensional matching instance in the individual agents’ neighbourhoods. A type, however, must include that entire neighbourhood. If many agents share a type, their compatibility graph is necessarily a blow-up of a much smaller type-level graph: every copy of type \(a\) has exactly the same relation to every copy of type \(a'\).
That is a severe loss of the theorem’s object. The proposed \(x_{aa'b}\) is the standard fractional capacity formulation of weighted 3-set packing. It permits the mass of one type to be divided among all compatible triples, whereas Theorem 3.6 is about selecting disjoint triples among individually specified vertices. Clearing denominators shows that the fractional solution can be implemented after creating sufficiently many clones, but that is an asymptotic replacement of the original instance by a different, highly symmetric clone market. It does not preserve the combinatorial structure that made the theorem interesting.
There is a genuine dilemma here. If the model has a fixed, small number of behavioural types—say smoking status, quiet-hours preference, and accessibility needs—then it is plausible as a housing-market story, but the problem collapses to a routine finite-dimensional capacity LP. The hard compatibility graph has disappeared. If one enriches the types enough to retain the reduction’s arbitrary neighbourhoods, then the number of types must grow with the number of agents, often making types effectively singletons. The “mass” is then merely a fractional encoding of the original matching instance, not a meaningful high-multiplicity population. A continuum of latent coordinates or an arbitrary compatibility kernel has the same problem: either the kernel is block-constant and reduces to the type-capacity model, or it carries individual-level information and the population is no longer composed of interchangeable types.
The same objection defeats attempts to rescue the mirror by adding identity-specific exceptions, priority coordinates, or richer roommate preferences. Those devices retain the paper’s matching structure only by putting the discarded identities back into the type description. They may define an interesting continuum matching or graphon problem, but it would be a different continuous model whose complexity comes from the representation of the compatibility kernel, not from continuizing this paper’s population.
This is not an objection that the continuous problem becomes tractable; the programme explicitly regards that as a potentially valuable result. Nor is it an objection that the literal matching formalism has become fractional. The deeper issue is that the only natural high-multiplicity regime removes the individual relational structure on which Theorem 3.6 rests, while any regime preserving that structure ceases to be high-multiplicity.
That said, this negative case is ultimately weak against the proponent’s actual construction. A large residence with repeated, feature-based compatibility profiles is a sensible author-recognisable scenario, and its aggregate LP is a legitimate high-multiplicity limit. I therefore cannot honestly claim to have defeated Theorem 3.6 as a continuous anchor. The best conclusion is narrower: the mirror is probably a simple fractional-capacity reformulation rather than a rich new ChoCo frontier, and it does not continuize the paper’s strategyproofness results. But the universal claim that no worthwhile continuous mirror exists is not supported; this anchor survives.
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.