| paper | d4-conf-sagt-2023-0008 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) for every fixed rational \(c\in(0,1)\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6
Given housing categories \(H\), a finite support \(T\) of complete strict preference rankings, rational type masses \(\mu_t\) summing to \(1\), rational per-capita capacities \(q_h\), and fixed rational \(c\in(0,1)\), does there exist a feasible assignment \(x_{t,a}\) of each type’s mass to an acceptable category or to being unmatched such that every feasible reassignment \(z_{t,a,b}\) of the same mass, respecting capacities \(q_h\), has strictly improving mass \(\sum_{t,a,b:\,b\succ_t a}z_{t,a,b}<c\)?
Types \(t\in T\) carry masses \(\mu_t\); \(x_{t,a}\) assigns that mass across categories or unmatched under capacities \(q_h\). A feasible alternative \(z_{t,a,b}\) has row sums \(x_{t,a}\) and respects the same capacities. Minimize over feasible \(x\) the maximum over feasible \(z\) of \(\sum_{t,a,b:\,b\succ_t a}z_{t,a,b}\).
The mirror covers Theorem 6’s existence question for incomplete-preference house allocation; it leaves the paper’s verification results, other preference restrictions, and marriage and roommates results aside.
The strongest mirror is Continuous \(c\)-Stable House Allocation. Imagine a large public-housing allocation in which many households choose among a small set of interchangeable housing categories, such as district and bedroom count. A type \(t\) is a complete strict ranking of the acceptable categories; \(\mu_t\) is that type’s fraction of the applicant population. For example, \(100{,}000\) households might have only a few dozen recurring preference types. Each category \(h\) has supply \(q_h\) per capita. Scaling category supply with the population is part of making this market coherent as a population limit.
My lead anchor is Theorem 6, proved in the paper: for every fixed \(c\) with \(0<c<1\), it is NP-complete to decide whether a house-allocation instance with incomplete preference lists has a matching in which no alternative matching is strictly preferred by at least \(cn\) agents. The paper proves this using a reduction based on Exact Cover by 3-Sets and scaling gadgets. [Theorem 6](https://arxiv.org/pdf/2307.03794)
Here is the continuous problem. The input is finite sets of preference types \(T\) and housing categories \(H\), rational masses \(\mu_t\ge 0\) summing to \(1\), rational per-capita supplies \(q_h\), each type’s strict ranking \(\succ_t\) over its acceptable categories, and a fixed rational \(c\in(0,1)\). Unmatched is below every acceptable category. A matching is an aggregate assignment \(x_{t,a}\ge 0\), where \(a\) is an acceptable category or unmatched, with \(\sum_a x_{t,a}=\mu_t\) for every type and \(\sum_t x_{t,h}\le q_h\) for every category. Each unit of mass still receives one category or remains unmatched; fractional \(x\) records how the continuum of households is divided across those integral assignments.
For a baseline \(x\), let \(z_{t,a,b}\) describe a feasible alternative assignment of the *same mass*: its row sums are \(x_{t,a}\), and its alternative assignments respect the category supplies. Because the population is atomless, any such coupling can be implemented by assigning the relevant parts of each type to their old and new categories. Its improving mass is \(\sum_{t,a,b:\,b\succ_t a}z_{t,a,b}\). Define \(\Phi(x)\) as the maximum improving mass over feasible \(z\). The decision question is whether there is a feasible \(x\) with \(\Phi(x)<c\). Equivalently, can we assign the population so that no alternative assignment improves at least a fraction \(c\) of it? The objective is to minimize the largest mass that could improve.
This is a credible analogue of the authors’ problem: it preserves the house-allocation setting, strict improvement, and the paper’s distinctive “count only those who improve” stability test. Replacing counts by population mass and scaling interchangeable-object supply with the population are direct co-modifications for this market. The mirror covers Theorem 6’s incomplete-preference house-allocation existence problem; it makes no claim about marriage or roommates markets, or about the paper’s verification results.
My first forecast for the genuinely type-compressed regime is Class A: with fixed \(x\), finding the largest improving mass is an LP, so a prover has a concrete continuous-optimization route to investigate. That does not already give an algorithm—the harder step is choosing \(x\) to control that worst-case improvement. The theorem’s discrete hardness does not transfer automatically: its reduction encodes an exact-cover instance using many specifically distinguished agents and objects, while continuum mass can split across assignments. Useful next questions are whether the outer choice admits an LP or separation formulation in \(\tau=|T|\), \(|H|\), and the input bit length, and whether a rounding theorem connects its solutions back to large discrete markets.
The weakest point is precisely that split: the continuous matching permits type mass to divide among categories, whereas a finite agent cannot split their assignment. That could change the authors’ existence question substantially. The case survives because the proposed problem retains their objective and market structure, and that change is the high-multiplicity relaxation to be tested—not an unrelated move to fractional outcomes.
The best case against is that the proposed public-housing story may depend on pooling houses into interchangeable categories. Real homes differ by location, condition, and eligibility constraints. If those details matter, they must enter the type or object space, and the small-support model may disappear. If there are only finitely many actual homes while the applicant population grows, the mass assigned to any one home vanishes, making the \(c\)-fraction question degenerate.
That objection does not defeat the stronger mirror, though. Applicants to a small set of colleges or housing programmes can have recurring preference and eligibility profiles, while each programme’s capacity scales with the applicant pool. The paper itself points to college admissions as an application. Under that model, types are complete descriptions, capacities are per capita, and an alternative assignment can be compared by the mass of applicants it improves. Those are natural co-modifications of the population limit, and splitting a type’s mass across assignments is explicitly part of the programme’s notion of a continuous society.
The anchor is also a named computational result: the paper proves NP-completeness for \(c\)-stable house allocation for every fixed \(0<c<1\). Its reduction uses distinguished agents and objects, but that does not disqualify the mirror; whether hardness survives mass splitting is precisely a question the programme permits. The paper’s result therefore gives a concrete problem to mirror, and I see no basis for claiming that continuous treatments already answer it.
So the honest negative case is weak. A finite-stock, individually differentiated housing market is a poor setting for this mirror, but a capacitated market with repeated applicant types is plausible and preserves the paper’s objective. I cannot defend the universal claim 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.