| paper | d4-conf-atal-2018-0077 |
| 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→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: \(\mathrm P\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 7.2
statement extracted from the paper’s text layer
Given a finite locality set \(L\), a finite support \(T\) of family types with strict rankings and one-dimensional demands, a population distribution \(\mu\) over \(T\), per-capita locality capacities \(c_\ell\), and a feasible incumbent allocation \(x_{t,a}\) with \(\sum_a x_{t,a}=\mu_t\), does there exist a feasible reassignment in which every unit of mass strictly improves? Equivalently, do there exist \(z_{t,a,b}\geq 0\) such that \(\sum_b z_{t,a,b}=x_{t,a}\), \(z_{t,a,b}>0\) only if \(b\succ_t a\), and \(\sum_{t,a}d_t z_{t,a,\ell}\leq c_\ell\) for every \(\ell\in L\)?
A distribution \(\mu\) over complete family types, each encoding a strict locality ranking and service demand; incumbent and reassignment masses \(x_{t,a}\) and \(z_{t,a,b}\); and per-capita locality capacities. Test whether all mass can be moved along strictly improving preference edges while preserving feasibility.
The mirror depends on a moderate number of exact preference-demand types and capacities that scale with the cohort; the proponent gives a plausible recurring-profile scenario but no evidence about how common that regime is.
fatal: False
Covers Proposition 7.2's weak Pareto-optimality test over a continuous population. The proposed extension related to Proposition 7.3 is weakened by the contradiction between its stated indifference restriction and its proof; the case leaves the stability taxonomy, HFPDA, master-list results, and other Pareto results aside.
The strongest mirror is the paper’s Pareto-improvement problem. It keeps the same decision at issue—whether a feasible assignment of refugee families can be improved—while making the family population continuous.
Take a fixed finite set \(L\) of localities and a finite support \(T\) of family types. A type \(t\) specifies a family’s service demand \(d_t\) and its complete preference ordering over \(L\cup\{\varnothing\}\). The society is a distribution \(\mu\) over these types, with \(\sum_t\mu_t=1\). Each locality \(\ell\) has a service capacity \(c_\ell\) measured per unit of population. A feasible incumbent allocation is a set of masses \(x_{t,a}\geq 0\), for \(a\in L\cup\{\varnothing\}\), with \(\sum_a x_{t,a}=\mu_t\) and \(\sum_t d_t x_{t,\ell}\leq c_\ell\) at each locality. Here \(x_{t,\ell}\) is the mass of type \(t\) assigned to \(\ell\); \(\varnothing\) means unmatched. Each family still receives one locality or remains unmatched. It is the mass of a type that can be divided among assignments.
This is a plausible high-multiplicity regime for a large resettlement programme: many families arrive over a planning period, while relatively few combinations of household needs and locality rankings recur. The type description includes everything relevant to the two anchors below: preferences and service demands. The paper’s localities can be indifferent among families, as in its hardness results. Scaling their capacities with the cohort is a co-modification of the population model that keeps the allocation question meaningful.
My lead anchor is Proposition 7.2, proved in this paper. It states that testing weak Pareto optimality is strongly coNP-complete even when families have strict preferences, every family is acceptable, and demands and capacities are unidimensional. The paper’s weak Pareto optimality means there is no feasible allocation in which *every* family strictly prefers its new assignment. Its reduction is from 3-Partition.
The corresponding continuous problem is Continuous Weak-Pareto Improvement. Given \(L,T,\mu,d,c\) and a feasible incumbent allocation \(x\), ask whether there is a feasible reassignment in which every family strictly prefers the new assignment to the incumbent one. A witness can be given as masses \(z_{t,a,b}\): the mass of type \(t\) currently at \(a\) that moves to \(b\). Require \(\sum_b z_{t,a,b}=x_{t,a}\), allow positive \(z_{t,a,b}\) only when \(b\succ_t a\), and enforce \(\sum_{t,a}d_tz_{t,a,\ell}\leq c_\ell\) for every locality. A feasible \(z\) is a strict-improvement witness; if none exists, the incumbent is weakly Pareto optimal.
This problem is a linear-program feasibility test with \(O(|T||L|^2)\) variables, so I expect it to be tractable in the support size, number of localities, and input bit length. The discrete hardness can disappear because the families of a type are no longer indivisible *as a cohort*: a mass of them can be reassigned while each individual still goes to exactly one locality. The mirror does not change the Pareto question; it changes the population regime in which that question is asked.
A second useful hardness anchor is Proposition 7.3, also proved here. It states that testing Pareto optimality is strongly coNP-complete even when every family is indifferent among all localities, every family is acceptable, and demands and capacities are unidimensional. Pareto optimality here rules out a feasible allocation in which every family weakly prefers the new assignment and at least one family strictly prefers it.
Its mirror, Continuous Pareto Improvement, has the same instance format. Ask whether there is a feasible reassignment where all families weakly prefer their new assignments and a positive mass strictly prefers them. Use the same flow variables, permit \(z_{t,a,b}>0\) only when \(b\succeq_t a\), and maximize the total mass on strict-preference moves. A positive optimum is an improvement witness; an optimum of zero means the incumbent is Pareto optimal. This is again a linear program, so I expect the same tractability outcome. It is a distinct anchor from Proposition 7.2: it mirrors the standard Pareto test and the paper’s separate indifference-based hardness result.
Both are faithful questions for these authors. The paper studies allocations of families to localities and asks whether feasible family allocations are Pareto-improvable; the mirrors ask exactly those questions for a distribution of complete family types. They cover Propositions 7.2 and 7.3, not the paper’s stability taxonomy, deferred-acceptance algorithm, or master-list results.
The weakest point is the population limit itself. In the finite problem, the 3-Partition reduction relies on indivisible families, while a continuous type mass can split across localities. That is a real change in the feasible aggregate allocations, and the continuous answers may therefore be easier. But it is the intended high-multiplicity change: a large cohort can be represented by the fractions of each type assigned to each locality. The result would be most useful as a limit or relaxation of large resettlement markets, not as a model of a small allocation committee.
The strongest objection is that both anchors are one underlying mirror: test whether a type-by-locality allocation can be rerouted along improving preference edges while respecting locality capacities. Proposition 7.2 permits only strictly better destinations; Proposition 7.3’s standard Pareto test permits weakly better destinations and requires a positive mass to improve strictly. Those are different predicates on essentially the same flow model, not two independent continuous directions.
The population regime is the harder concern. A family’s type must include its full ranking over localities and its service-demand vector. In refugee allocation, household needs and preferences may vary enough that the number of exact types grows with the cohort. Then the small-support regime the mirror needs is a poor description of the market. The proposed per-capita capacities also fit a resettlement programme whose resources grow with its cohort, but that assumption deserves justification for a setting where capacity may be fixed. These points weaken the case for this as a central mirror; they do not rule it out. A large cohort with recurring household profiles and common locality rankings is plausible, and the programme explicitly allows supply to scale with population.
There is a specific problem with the second anchor as stated in the paper. Proposition 7.3 claims hardness when every family is indifferent among localities, but its proof gives \(f^\ast\) a strict ranking between \(\ell'\), \(\ell^\ast\), and the other localities, and gives each \(f_i\) a strict ranking between \(\ell'\) and \(\ell^\ast\). Under literal complete indifference, no allocation can make anyone strictly better, so that subclass’s Pareto test is trivial. The proof supports a nearby restricted result, not the stated complete-indifference case. Still, the ordinary Pareto-improvement question remains a legitimate mirror.
I cannot honestly defeat the better version of Proposition 7.2’s mirror. With finitely many complete family types, a continuous society, and capacities scaled to the cohort, the incumbent masses \(x_{t,a}\) retain the information the Pareto comparison uses. A reassignment can give every unit of mass a whole locality while splitting a type’s mass across destinations. That is a coherent population continuization, not an outcome-space substitute. The negative case therefore lowers confidence in the mirror’s empirical fit and novelty, but it does not establish that no worthwhile scenario exists; the lead anchor survives.
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.