| paper | d4-conf-wine-2025-0007 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\); a winning rational \(y\) always exists. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2.5
statement extracted from the paper’s text layer
Given finite type and housing-class sets \(T\) and \(H\), rational type masses \(\mu_t\), per-capita capacities \(q_h\), and each type’s acceptable classes, weak ranking, and voting weight \(w_t\), can one find in time polynomial in \(|T|\), \(|H|\), and input bit length \(L\) a rational array \(y_{t,a,b}\)? Each entry is the mass of type \(t\) receiving acceptable class \(a\) or \(\bot\) in the first matching and \(b\) or \(\bot\) in the second; each plan must respect the capacities. Require that for every feasible competing assignment, including any split of each \((t,a,b)\) cell among allowed assignments \(c\), the total weight of residents who strictly prefer their better assignment from the pair to \(c\) is at least the total weight who strictly prefer \(c\) to that pair.
An atomless population with finitely many complete preference-and-voting types carries mass \(\mu_t\); each resident still receives one indivisible housing unit, while interchangeable housing classes have per-capita capacities \(q_h\). The decision variables \(y_{t,a,b}\) retain which portions of each type receive each pair of assignments, so popularity compares those residents against every capacity-feasible competing assignment.
The mirror covers the house-allocation size-two algorithm in Theorem 2.5, with Observation 2.1 supplying the discrete lower bound for exact dimension two. It leaves the marriage and roommates results aside.
My lead is a continuous, high-multiplicity version of house allocation. Imagine a recurring housing allocation for a very large cohort: residents fall into a moderate number \(\tau\) of complete preference-and-voting types, while the supply of each housing class scales with the cohort. A type fixes an acceptable set, a weak ranking over it, and a voting weight. The housing classes can stand for pools of interchangeable units; a resident still receives one indivisible unit, while a type’s mass can be split across classes. That supply adjustment is part of the mirror.
The anchor is Theorem 2.5, proved in this paper. It says that for general house allocation with weighted agents and ties in preference lists, a popular winning set of two matchings can be found in polynomial time, so the popular dimension is at most two. Together with Observation 2.1—which reproduces the lower-bound example attributed to Abraham et al. [1]—the worst-case dimension is exactly two. The paper has no comparable named hardness result, so this is the right algorithmic anchor.
Here is the continuous problem I would hand to a prover: Type-Distribution Popular House Allocation. The input is a finite set \(T\) of types with rational masses \(\mu_t\) summing to one, a finite set \(H\) of housing classes with rational per-capita capacities \(q_h\), and each type’s acceptable classes, weak ranking, and rational vote weight \(w_t\). Unmatched, written \(\bot\), ranks below every acceptable class. The number of people is absent from the input; the intended regime has many residents and relatively few types.
A matching is a measurable assignment of each resident either one acceptable class or \(\bot\), with at most \(q_h\) population mass assigned to class \(h\). The requested solution is a pair of matchings \(A_1,A_2\) such that, against every feasible matching \(A'\), the total voting weight of residents who strictly prefer their better assignment in \(\{A_1,A_2\}\) is at least the weight of those who strictly prefer their assignment in \(A'\). As in the paper, residents indifferent between the two sides contribute to neither side. Duplicate the same matching if a singleton suffices.
A finite output can be a rational array \(y_{t,a,b}\): the mass of type \(t\) assigned to \(a\) in \(A_1\) and to \(b\) in \(A_2\), where \(a,b\in H\cup\{\bot\}\). For each type these entries sum to \(\mu_t\); in each plan, the mass assigned to any \(h\) is at most \(q_h\). This joint array matters: it records which portions of a type receive which pair of assignments, not just the separate totals in the two plans.
The winning condition can also be stated finitely. Let \(z_{t,a,b,c}\) describe the mass in cell \((t,a,b)\) that a competing matching assigns to \(c\). Require \(\sum_c z_{t,a,b,c}=y_{t,a,b}\), and require the competitor’s capacity constraints. For every such feasible \(z\), the sum of \(w_t z_{t,a,b,c}\) over cells where the type prefers its better of \(a,b\) to \(c\) must be at least the corresponding sum where it prefers \(c\) to that better assignment. Atomlessness lets any such \(z\) be realized by splitting each cell, so this condition compares the pair against every actual measurable matching, not merely against selected type-level summaries.
I expect this problem to be tractable in \(\tau\), \(|H|\), and the rational input bit length \(L\). The paper’s weighted top-choice construction is a credible starting point, and for a fixed candidate pair, checking for a more popular competitor is a finite transportation optimization problem. The continuous task is to find the pair directly from type masses and capacities, without expanding a denominator-\(N\) population into \(N\) individual residents. That distinction is substantive: \(N\) can be exponential in \(L\).
The authors should recognize this as their problem’s continuous form. Residents still vote on matchings using the same ordinal comparison, and the winning object is still a popular winning set. The changes are the population distribution and the associated per-capita supplies; the fractional entries in \(y\) describe how many residents of a type receive each integral assignment.
The weakest point is that Theorem 2.5 does not itself give this type-level algorithm. Its proof uses discrete agent-by-agent steps, and a mass version must preserve the alignment between a person’s two candidate assignments when calculating votes. The joint array makes that issue explicit, but it does not prove the algorithm extends. Establishing a polynomial algorithm directly in \(\tau,|H|,L\)—or finding an obstruction—is the actual continuous-complexity question. This mirror covers Theorem 2.5’s house-allocation result only; the paper’s marriage and roommates results raise additional pairing issues that this case does not need to take on.
I cannot make a strong case against the anchor. Theorem 2.5 is a named polynomial-time result about a computational problem, so the “no result to mirror” objection does not apply. And house allocation has a plausible high-multiplicity setting: a large recurring cohort assigned among a fixed number of housing classes, with supply scaling with the cohort. Types can include each resident’s ranking, acceptable classes, and voting weight. The population then enters as type masses, while each resident still receives an integral assignment.
The best objection is that this setting changes the resource model. In literal house allocation, houses are named, individually scarce objects; scaling supply while keeping finitely many housing classes treats units as interchangeable and moves toward a capacitated variant. If preferences over exact addresses are essential, a fixed type space may be unrealistic. But that does not defeat the stronger mirror: residents competing for interchangeable units in recurring housing or placement cohorts is a credible matching problem, and the paper itself recognizes capacity extensions. Its popularity comparison does not depend on tracking residents’ names. The proposed joint array also preserves which portions of a type receive each pair of assignments.
So the objection narrows the mirror to settings with genuinely interchangeable, scalable resources; it does not rule out those settings. I cannot honestly defeat the Theorem 2.5 mirror, and the case against it is weak.
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.