| paper | d4-conf-ecai-2025-0457 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 11
statement extracted from the paper’s text layer
Given rational resident masses \(\mu_t\) over \(\tau\) complete preference types and rational room supplies \(\rho_q\) over \(\kappa\) room categories, with \(\sum_t\mu_t=1\) and \(\sum_q\rho_q=1/2\), find a feasible mass assignment \(x_{\{t,u\},q}\) with no positive-mass 4PS-blocking exchange. Feasibility requires \(\sum_q(2x_{\{t,t\},q}+\sum_{u\ne t}x_{\{t,u\},q})=\mu_t\) for each type \(t\), and \(\sum_{t\le u}x_{\{t,u\},q}=\rho_q\) for each category \(q\). A blocking exchange is possible if two positive-mass room cohorts \((\{t,u\},q)\) and \((\{v,w\},p)\) contain a \(t\)-resident and a \(v\)-resident whose swap would strictly improve the utilities of both movers and both roommates.
Represent each room by an unordered pair of resident types and a room category, with \(x_{\{t,u\},q}\) giving its mass. Maximize total utility: a unit of mass in \((\{t,u\},q)\), for \(t\ne u\), contributes \(h_t(u)+v_t(q)+h_u(t)+v_u(q)\); a unit in \((\{t,t\},q)\) contributes \(2(h_t(t)+v_t(q))\). The rational LP has \(O(\tau^2\kappa)\) variables, and any 4PS-blocking exchange strictly increases its objective, so an optimum is 4PS-stable.
The mirror has no rounding or approximation guarantee connecting a mass-stable assignment to a finite high-multiplicity market with few blocking residents.
fatal: False
The mirror covers the 4PS assignment objective of Theorem 11 under repeated preference types and room categories, but does not transfer CTTCR's \(O(n^5)\) procedure or cover the paper's strategy-proofness, Pareto-optimality, 2PS, and TTC results.
The best mirror is a large housing market where residents are assigned in pairs to rooms. Residents’ roommate preferences and room utilities stay exactly as in the paper; what becomes continuous is the population and the room supply. The many residents share a moderate number \(\tau\) of complete preference types, and rooms fall into a moderate number \(\kappa\) of equivalent categories. A type records utility toward every roommate type and every room category, so agents grouped together are indistinguishable for the problem. A large university or co-living provider with recurring resident profiles and standardized rooms is plausible, especially when roommate compatibility comes from a common questionnaire. Exact repetition is a real assumption: if almost every profile is unique, this mirror offers little compression.
The paper has two numbered tractability results that make useful anchors. Theorem 11, proved here, says that CTTCR outputs a 4-person stable assignment in \(O(n^5)\) time. Theorem 12, also proved here, says that with symmetric binary valuations, swapping a 2-person blocking pair increases social welfare; the paper uses this to obtain a 2PS assignment by repeated swaps in \(O(n)\) steps. The paper’s general 2PS NP-completeness statement is attributed to Chan et al. [11], so it is relevant context but not an in-paper numbered anchor.
Use rational resident masses \(\mu_t\), with \(\sum_t\mu_t=1\), and rational room supplies \(\rho_q\), with \(\sum_q\rho_q=1/2\). Let \(x_{\{t,u\},q}\) be the mass of rooms in category \(q\) occupied by types \(t\) and \(u\), where the pair is unordered. Feasibility requires \(\sum_{\{t,u\},q:\,t\text{ occurs in }\{t,u\}} x_{\{t,u\},q}=\mu_t\), counting \(2x_{\{t,t\},q}\) when both occupants have type \(t\), and \(\sum_{t\le u}x_{\{t,u\},q}=\rho_q\) for each room category. Thus each unit of room mass still houses two residents; the model does not make their bundles fractional.
The linear objective is total welfare. A room of type pair \(\{t,u\}\) in category \(q\), for \(t\ne u\), contributes \(h_t(u)+v_t(q)+h_u(t)+v_u(q)\) per unit of room mass; a \(\{t,t\}\) room contributes \(2(h_t(t)+v_t(q))\). The resulting LP has \(O(\tau^2\kappa)\) variables and rational input. This welfare-maximization problem is the computational engine for both mirrors.
For Theorem 11, the continuous question is: *given these type masses, room supplies, and additive utilities, find a feasible mass assignment with no 4PS-blocking exchange.* A block exists if two positive-mass room cohorts \((t,u,q)\) and \((v,w,p)\) contain occupants \(t\) and \(v\) who would both strictly gain by swapping, while their roommates \(u\) and \(w\) would also strictly prefer their new roommates. The answer is the maximizing \(x\). Any such block lets us exchange a small positive mass of the two room cohorts and strictly increase total welfare, contradicting maximality. This is a Class A mirror, polynomial in \(\tau,\kappa\), and the input bit length. It preserves the paper’s four-person stability question under general additive valuations.
My lead is the stronger-stability mirror of Theorem 12: *under symmetric binary roommate compatibility and binary room values, find a feasible mass assignment with no 2PS-blocking exchange.* Here a block requires only that the two swapping residents strictly gain. Theorem 12 supplies the key argument: such a swap strictly raises welfare. If a positive mass of two room cohorts forms a block, exchanging a small amount of that mass raises the LP objective, so a welfare maximum is 2PS. This is again Class A. The symmetry and binary assumptions are narrow, but plausible in settings where compatibility is mutual and yes/no, and where residents accept or reject a small number of room categories. The result is especially interesting beside the paper’s cited NP-completeness result for general 2PS: the tractable mirror isolates a structured regime rather than claiming that hardness disappears in general.
The shared LP does not transfer the paper’s algorithms step for step: the finite swap process relies on discrete people and bounded integer welfare, while this mirror uses optimization over mass. That still computes the same stability notions on a continuous population, which is the relevant object. Further questions include when a rational mass solution can be rounded to a finite high-multiplicity assignment with few blocking residents, and how far the Theorem 12 welfare argument extends beyond symmetric binary preferences. The paper also studies strategy-proofness, but I would leave those results outside this mirror: a single resident has zero mass here, so unilateral-report incentives need a separate model.
The weakest point is the repeated-type regime, especially for the 2PS lead. Real roommate preferences can be idiosyncratic, and a room-by-room preference list can make \(\tau\) or \(\kappa\) grow with the market. Also, continuous stability lets any positive mass form a blocking exchange, even where a finite market’s smallest available exchange is one person. So the LP gives a precise and plausible continuous problem, but a rounding or approximation theorem is still needed to connect its answer back to large finite housing markets.
The strongest case against these mirrors is that the paper’s key input is a *dyadic* preference structure: an agent values particular roommates and rooms. Grouping residents into types works only when compatibility is determined by a compact, repeatable profile. In many housing markets, preferences depend on the particular people involved, so a resident’s type would need to encode a large row of pairwise values. Then the support may grow with the market, and the hoped-for high-multiplicity regime disappears.
That concern weakens the case for both anchors, but it does not defeat the best version of either. A large provider using standardized rooms and questionnaire-based compatibility could plausibly have repeated types. In that setting, Theorem 11 has a direct mirror: maximize welfare over masses of type pairs assigned to room categories. This is a small LP, and Pareto optimality rules out a 4PS blocking exchange. The result may be less distinctive than CTTCR’s algorithm—the continuous answer follows from generic welfare optimization—but the question is well-posed and computational.
The same LP defeats the strongest objection to the Theorem 12 mirror. Its finite swap process uses a bounded discrete potential, which does not carry over as an iteration bound for masses. But under the theorem’s symmetric binary assumptions, a blocking swap strictly increases total welfare. A welfare-maximizing mass assignment therefore has no positive-mass 2PS block. Binary mutual compatibility is a plausible cohort model, so this is more than a literal translation of the paper’s algorithm.
I cannot make the universal negative case hold: both anchors survive in a credible repeated-type setting, and the continuous questions are coherent. The honest negative is narrower: the mirrors’ practical reach depends on strong structure in interpersonal compatibility, and their answers may be elementary LP results rather than new complexity boundaries. That makes their eventual contribution uncertain; it does not establish that no worthwhile continuous mirror exists.
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.