| paper | d4-conf-ijcai-2017-0051 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given room-category supplies \(\rho_q\) with \(\sum_q \rho_q=1\), type masses \(\beta^1,\ldots,\beta^K\) with \(\sum_j \beta^j_t=\mu_t\) and \(\sum_t\mu_t=2\), and rational room values and roommate utilities, cohorts arrive in uniformly random order. Each cohort’s type mass must be assigned immediately, with assignments divisible across room categories and roommate pairs. Does there exist a randomized causal policy, polynomial in \(K\), \(|T|\), \(|Q|\), and the input bit length, whose expected welfare is at least \(c_b/4\) times the offline optimum over feasible type-pair and room-category allocations?
A continuous online roommate allocation with finite complete types, rational mass cohorts and room supplies, divisible cohort assignments, pairwise roommate externalities, and randomized cohort order; compare causal policies against the maximum-welfare type-mass allocation.
Randomly permuted macroscopic cohorts introduce uncertainty absent from the atomless limit of uniformly random individual arrivals, and the problem depends on the extra cohort partition.
fatal: False
The mirror covers Theorem 1’s two-bed welfare guarantee and, with a weak room-stability constraint, Theorem 3. It does not cover the generalized room-capacity results, the unknown-population lower bound, or the other stability results.
The strongest honest case is for a high-volume housing or university accommodation system: many applicants, but relatively few complete preference profiles and room categories. An applicant’s type records their value for every room category and their happiness with every other type. Applicants sharing a type are identical in every way the allocation uses. For example, there might be tens of thousands of applicants but only dozens of types and room categories. This is a sensible high-multiplicity regime for roommate allocation.
My lead anchor is Theorem 1, proved in this paper. It states that ONLINEROOMMATE runs in polynomial time and is \(c_b/4\)-competitive for social welfare in the online roommate market, where \(c_b=(\ln 5-0.8)/5\approx0.1618\). The guarantee is against the optimal offline allocation, in expectation over the random arrival order and the algorithm’s randomness. This is the paper’s clearest named result about the computational problem of making irrevocable roommate assignments for welfare.
Here is a continuous version I would ask a prover to study, Online Roommate Mass Allocation. Let \(T\) be a finite set of applicant types and \(Q\) a finite set of room categories. The instance gives rational masses \(\mu_t\) with \(\sum_{t\in T}\mu_t=2\), and room supplies \(\rho_q\) with \(\sum_{q\in Q}\rho_q=1\). Type \(t\) has room value \(v(t,q)\), and \(h(t,u)\) is the happiness of a type-\(t\) resident with a type-\(u\) roommate. These are nonnegative binary rationals.
For the online part, the population is presented in \(K\) mass cohorts. Cohort \(j\) has a vector of type masses \(\beta^j\), with \(\sum_j\beta^j_t=\mu_t\); the cohorts arrive in uniformly random order, and the policy sees each cohort’s composition when it arrives. It may divide that cohort’s mass among room assignments, but must assign all of it immediately. A room can be opened with one resident mass and later filled by a second. This retains the paper’s online commitment and pairwise roommate externalities while letting the population and the decisions be divisible.
The offline benchmark is \(\mathrm{OPT}(\mu,\rho)\), the maximum of the following type-mass allocation problem. Choose \(x_{q,\{t,u\}}\geq0\), the mass of rooms in category \(q\) assigned to a pair of types \(t,u\), subject to
\[
\sum_{\{t,u\}} x_{q,\{t,u\}}=\rho_q
\quad\text{for each }q,
\]
and
\[
2\sum_q x_{q,\{t,t\}}+\sum_{q,\,u\ne t}x_{q,\{t,u\}}=\mu_t
\quad\text{for each }t.
\]
The objective is
\[
\sum_{q,\{t,u\}}x_{q,\{t,u\}}
\bigl(h(t,u)+h(u,t)+v(t,q)+v(u,q)\bigr).
\]
The continuous question is: does there exist a randomized causal policy, running in time polynomial in \(K,\lvert T\rvert,\lvert Q\rvert\), and the input bit length, whose expected welfare is at least \(c_b/4\cdot\mathrm{OPT}(\mu,\rho)\)? A solution is such a policy, including its cohort-by-cohort mass assignments. I would expect this stated constant-factor question to be tractable: the offline benchmark has only type-pair and room-category variables, and the paper’s online matching construction suggests a fractional online matching approach. That expectation is a research conjecture, not a result proved by this paper.
A second, stronger-in-the-application anchor is Theorem 3, also proved here. It states that an online algorithm can always produce a weakly room-stable allocation and achieve competitive ratio \(c_b/8\) for social welfare. The continuous question is the same Online Roommate Mass Allocation problem, with the additional requirement that the final allocation be weakly room-stable. Write \(U(t;u,q)=h(t,u)+v(t,q)\). If positive room mass has pair \(t,u\) in category \(q\), and positive room mass has pair \(v,w\) in category \(q'\), stability requires that there be no swap of the two intact pairs between the room categories that strictly increases all four residents’ \(U\). The question is whether a polynomial-time causal policy can guarantee this stability in every outcome while obtaining expected welfare at least \(c_b/8\cdot\mathrm{OPT}(\mu,\rho)\). I would also expect a constant-factor answer here, though the stability condition makes this less immediate than the welfare-only question.
These mirrors cover the paper’s two-bed welfare result and its weak room-stability result. They do not claim a mirror for every result in the paper. In particular, the paper gives no named NP-hardness or parameterized-complexity theorem to anchor a hardness question; its relevant named results are online algorithm and competitive-ratio results. The offline roommate work of Chan et al., which this paper builds on, supports the underlying allocation model rather than colliding with the continuous online question.
The weak point is the arrival model. A literal atomless limit of uniformly random individual arrivals can erase the uncertainty: each type’s mass may arrive at a deterministic rate, making the online competitive question much easier than in Theorem 1. I therefore used randomly ordered cohorts of divisible mass, which is plausible for large housing programs processed in applicant waves and preserves meaningful uncertainty about future types. But it is a modification of individual random order, and the authors or a referee might reject it as too far from their model. If they do, the static type-mass allocation remains a sensible continuous population object, but it no longer mirrors Theorem 1’s central online guarantee as closely.
The strongest case against is that Theorem 1 and Theorem 3 depend on finite-scale uncertainty that the natural continuous-population model removes. With a fixed distribution over finitely many complete types and uniformly random individual arrivals, the type proportions in every macroscopic prefix converge to a deterministic flow. In a mass model, assignments can split that flow continuously. The random fluctuations and indivisible decisions that drive the paper’s online problem disappear at the scale being modelled. Given the type masses and their arrival proportions, a policy can plan the mass allocation and schedule pairings as the flow arrives. The resulting question is deterministic mass-flow allocation, not the random-order online problem in Theorem 1.
The proponent’s cohort model preserves uncertainty only by adding a new source of it. If cohorts are small samples from the population, their compositions concentrate and randomizing their order has little effect. To retain substantial uncertainty, the model needs a few large cohorts with different compositions. Then the relevant input is the list and partition of those cohorts: two instances with the same population distribution \(\mu\) can have different online problems depending on how that population is divided into batches. Randomly permuting such macroscopic batches is a coherent model for a particular process, but it is not the limit of uniformly random individual arrivals. It makes batch structure and batch order central features, and needs its own application case.
Theorem 3 does not escape this problem. Its weak room-stability condition has a reasonable mass version: one can require that no two occupied type-pair and room-category combinations permit a Pareto-improving swap. So the fact that individual residents have zero mass is not, by itself, a decisive objection. But the theorem’s welfare guarantee still comes from the same online uncertainty. In the ordinary atomless limit that uncertainty disappears; in the cohort version, the mirror inherits the extra batch-arrival assumption.
The negative case is strongest for the paper’s stated random-order model, and weaker against a deliberate online batch-allocation model. If large, exchangeable applicant waves are a setting the authors would recognize, the cohort question is sensible and could be worth studying. I cannot rule that scenario out. My case is that it would be a new model whose value rests on that additional assumption, rather than a worthwhile continuous mirror of the paper’s central results.
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.