| paper | d4-conf-aaai-2026-4680 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\); the threshold decision problem is \(\mathrm{NP}\text{-complete}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given housing classes \(H\) on a common axis, a list of \(\tau\) complete strict single-peaked rankings \(r\), rational type masses \(\mu_r\geq 0\) summing to \(1\), and rational per-capita class capacities \(\sigma_h\) with \(\sum_h \sigma_h>1\), choose assignment masses \(y_{r,h}\geq 0\) satisfying \(\sum_h y_{r,h}=\mu_r\) and \(\sum_r y_{r,h}\leq \sigma_h\). Let \(S(y)=\{h:\sum_r y_{r,h}>0\}\) and \(\mathcal E(y)=\sum_{r,h}y_{r,h}\mathbf{1}[\exists g\in S(y):g\succ_r h]\). Find a feasible assignment minimizing \(\mathcal E(y)\).
A continuum of applicants grouped by complete strict single-peaked ranking type, with rational mass per type and scalable supplies of indivisible units in each housing class. Assignment variables \(y_{r,h}\) are type-level mass averages; the objective is the mass assigned to a class when some occupied class is preferred.
The envy objective jumps when a class’s assigned mass tends to zero, so it is not stable under every convergent sequence of allocations; the proponent notes support sensitivity but does not resolve that limit issue.
fatal: False
The mirror covers Theorem 3’s minimum-Envy result for single-peaked preferences. It leaves Theorems 1, 2, and 4, Pareto-efficiency results, and the welfare experiments without a continuous question.
There is no numbered hardness theorem in this paper. Its introduction reports hardness results from earlier work, but those are cited context, not numbered results proved here. My anchors are therefore the paper’s own algorithmic results: Theorem 3 is the lead, with Theorem 1 as a second, distinct mirror.
The lead scenario is a large public-housing allocation: many applicants, and many units in a limited set of genuinely interchangeable housing classes, such as combinations of location, size, and amenities. Each applicant still receives one whole unit. The number of applicants and units grows, while the number \(\tau\) of distinct preference types remains much smaller; applicants with the same ranking are indistinguishable for the allocation problem. Mass records the fraction of applicants of each type, and per-class capacity scales with the population. This is a high-multiplicity regime, not a claim that all housing markets are one.
Theorem 3 is the lead anchor, an algorithmic result proved by the authors, with some proof details deferred to the full version. It says that for complete, strict single-peaked preferences over houses with a common axis, minimizing the number of envious agents can be done in time \(O(|H|^2)\).
Its continuous mirror is Single-Peaked Minimum Envy with Class Supplies. An instance has an ordered set \(H\) of housing classes, a list of \(\tau\) complete strict single-peaked rankings \(r\) over that axis, rational masses \(\mu_r\geq 0\) summing to \(1\), and rational capacities \(\sigma_h\) with \(\sum_h \sigma_h\geq 1\). Choose assignment masses \(y_{r,h}\geq 0\), with \(\sum_h y_{r,h}=\mu_r\) for each type and \(\sum_r y_{r,h}\leq \sigma_h\) for each class. Let \(S(y)=\{h:\sum_r y_{r,h}>0\}\). The envious mass is
\[
\mathcal E(y)=\sum_{r,h} y_{r,h}\,
\mathbf 1\!\left[\exists g\in S(y)\text{ such that }g\succ_r h\right].
\]
The question is to find a feasible \(y\) minimizing \(\mathcal E(y)\); a solution is the assignment matrix and its attained minimum. The expected direction is Class A: the shared one-dimensional order seems to preserve useful structure, and a weighted interval algorithm or LP-based method may handle rational type masses and capacities. Theorem 3’s \(O(|H|^2)\) algorithm does not by itself prove this weighted version, so the complexity in \(m=|H|\), \(\tau\), and input bit length remains the question.
Theorem 1 is a second anchor, also the authors’ own result. Given a house-allocation instance, an initial complete allocation \(\hat A\), and positive integers \(k,q\), it decides whether there is an allocation \(A\) with \(\mathrm{Envy}(A)\leq \mathrm{Envy}(\hat A)-k\) and \(|A\mathbin{\Delta}\hat A|\leq q\). It gives randomized and deterministic FPT algorithms parameterized by \(q+d\), where \(d\) is the maximum degree in the preference graph; the stated running times are \(O^*(3^{3q(d+1)})\) and \(O^*(8^{qd\log(3q(d+1))})\), respectively.
Its continuous mirror is Mass-Bounded Envy Refinement. A type is a pair \((r,a)\): a complete ranking \(r\) over housing classes and the class \(a\) assigned initially. Its rational mass is \(\mu_{r,a}\); initial occupancy of class \(a\) is \(\sum_r\mu_{r,a}\leq\sigma_a\). Choose transfer masses \(x_{r,a,h}\geq0\), where \(x_{r,a,h}\) is type \((r,a)\)’s mass moved from \(a\) to \(h\). Require \(\sum_h x_{r,a,h}=\mu_{r,a}\) and final class occupancy \(\sum_{r,a}x_{r,a,h}\leq\sigma_h\). With \(S(x)=\{h:\sum_{r,a}x_{r,a,h}>0\}\), define \(\mathcal E(x)\) by the same envy formula, summing over \(r,a,h\). Given a reallocation budget \(Q\) and a target reduction \(\kappa\), ask whether such an \(x\) exists with
\[
\sum_{r,a}\sum_{h\ne a}x_{r,a,h}\leq Q
\quad\text{and}\quad
\mathcal E(\hat x)-\mathcal E(x)\geq\kappa,
\]
where \(\hat x\) leaves all mass at its initial class. The solution is a feasible transfer plan. This follows the theorem’s limited-reallocation question, measuring changes as mass; the printed symmetric-difference budget uses a discrete edge-count convention.
I would provisionally expect the general version of Mass-Bounded Envy Refinement to be Class C when the number of classes varies: which classes receive positive mass affects which residents count as envious, creating a support-selection problem of its own. That is a hypothesis, not a hardness claim. A useful next question is whether bounded class count or additional structure in the preference graph yields a polynomial algorithm, and whether any hardness persists when \(\tau\) is small. Theorem 1’s FPT result in the number of changed agents does not automatically imply FPT in a changed-mass budget.
The main weakness is the aggregation of physical houses into classes. It is convincing only where many units are genuinely interchangeable for the decisions being modeled; if individual house identities and rankings matter, the number of types or classes may grow with the population and the high-multiplicity regime weakens. The envy definition also makes occupied support consequential: even a small positive assignment to a preferred class can make mass assigned to a worse class envious. Those are explicit features of the proposed population mirror, and the paper’s public-housing motivation gives a plausible setting in which to ask whether authors and referees would accept them.
This case covers Theorems 3 and 1 only. It does not claim a continuous result for TotalEnvy, MaxEnvy, Pareto efficiency, or the paper’s welfare experiments.
The strongest objection to both mirrors is that envy is not stable under the population limit. It depends on whether *any* better house is occupied, however small the number of occupants. For example, suppose half the applicants prefer class \(x\) to class \(y\), and they are assigned to \(y\). If one applicant occupies \(x\), that can make half the population envious. With \(n\) applicants, that occupant has mass \(1/n\); as \(n\) grows, the allocation measures converge to one with no mass at \(x\), where that envy disappears. The proposed \(\mathcal E(y)\) records this through the support \(S(y)\), but support is lost when positive masses converge to zero. Thus the continuous objective is well-defined, yet it is not a stable high-multiplicity limit of the discrete objective.
For Theorem 3, keeping the paper’s strict rankings over distinct, unit-capacity houses does not yield a large population with a fixed, moderate number of types: the paper assumes \(m>n\), and scaling the number of houses also scales the identities agents rank. The proponent’s class-supply model is the best way around that obstacle, and it is plausible for public housing. But it replaces distinct houses with repeatable classes, so many applicants can receive interchangeable units and preferences over copies become ties. Theorem 3 is for complete, strict preferences; the paper itself lists single-peaked preferences with ties as future work. A polynomial algorithm for the class-supply variant would be a useful new result, but the paper’s theorem does not make that question its continuous mirror.
For Theorem 1, the reallocation budget creates a sharper scaling mismatch. A fixed \(q\) means only finitely many assignment changes as the population grows. Their moved mass tends to zero, even though—by the support effect above—they can still change the envy of a positive fraction of applicants. A fixed positive mass budget \(Q\), by contrast, allows \(\Theta(n)\) changes, outside the theorem’s bounded-\(q\) regime; its FPT guarantee gives no corresponding bound. The proposed mass-refinement question remains definable, but its budget no longer captures the theorem’s sparse-intervention result.
This is the best case against the anchors: their natural class-based versions introduce a different preference domain, and the envy objective makes neither version a faithful limit of the discrete problem. The case against *any worthwhile* mirror is weaker. A class-based housing market is credible, and minimizing envious mass there could be worth studying on its own. I cannot honestly rule that out; the narrower claim I can defend is that Theorems 3 and 1 do not, by themselves, establish the promised high-multiplicity bridge.
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.