| paper | d4-conf-ecai-2024-0121 |
| 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: The continuous assigned-mass decision problem is in \(\mathrm{P}\), with bit running time \((m\tau+\tau+mt+L)^{O(1)}\); for \(m=3\), this is \(L^{O(1)}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given an explicitly listed support \(A\) of family types with rational masses \(\mu_a\ge 0\), \(\sum_{a\in A}\mu_a=1\), integral service requirements \(r_a\), three places with rational per-capita supplies \(q_{p,s}\), and a target \(\theta\), is there an allocation \(x_{a,p}\ge 0\) such that \(\sum_p x_{a,p}\le\mu_a\), \(\sum_a r_a[s]x_{a,p}\le q_{p,s}\), and \(\sum_{a,p}x_{a,p}\ge\theta\)?
Types are complete family profiles, including service requirements and equal positive utilities across places. Assign mass \(x_{a,p}\) of each type to each place, subject to the type-mass limits and per-capita service supplies, and maximize \(\sum_{a,p}x_{a,p}\).
Mirrors Theorem 5's MAXUTIL-RR result for equal utilities. It also gives the equal-preference PARETO-RR analogue if a strict improvement means that positive mass becomes assigned; it leaves the paper's other parameterized algorithms and hardness results unaddressed.
The lead—and only anchor I would carry—is the MAXUTIL-RR part of Theorem 5, proved in this paper by a reduction from 3-COLORING. The theorem also proves that PARETO-RR is NP-hard with \(m=3\), no lower quotas, and equal preferences; its MAXUTIL-RR result is that deciding whether an assignment reaches the utility bound is NP-hard even with \(m=3\), maximum upper quota \(c_{\max}=1\), no lower quotas, and equal utilities for all family–place pairs. In the reduction, families correspond to graph vertices, services to edges, and places to the three colors. A family requires one unit of each service corresponding to an incident edge, and each place offers one unit of each service. A complete feasible assignment exists exactly when the graph is 3-colorable. Setting every utility to one and the target to the number of families makes the utility question ask whether all families can be placed.
My mirror is Continuous Maximum-Placement Refugee Resettlement. There are three places and an explicitly listed support of \(\tau\) family types. A type is a complete description of a family for this problem: its service requirement vector, utility vector, and preferences. For the Theorem 5 restriction, utilities are equal and positive across all places, and for the Pareto interpretation all places are acceptable and tied. Type \(a\) has rational mass \(\mu_a\), with \(\sum_a\mu_a=1\). Each place \(p\) has a rational per-capita supply \(q_{p,s}\) of each service \(s\); there are no lower quotas.
Let \(x_{a,p}\) be the mass of type \(a\) assigned to place \(p\). The question is whether there is an allocation meeting a target \(\theta\):
\[ \sum_p x_{a,p}\le \mu_a,\qquad \sum_a r_a[s]x_{a,p}\le q_{p,s},\qquad \sum_{a,p}x_{a,p}\ge\theta,\qquad x_{a,p}\ge 0. \]
Equivalently, maximize \(\sum_{a,p}x_{a,p}\) and return an optimal allocation. Equal positive utilities make this exactly the maximum-utility objective after normalization. With equal preferences, a maximum-mass allocation is also Pareto-optimal: a Pareto improvement would have to place positive mass that was previously unassigned without making anyone worse off, increasing the total placed mass.
The regime I have in mind is a large resettlement programme assigning many families across a few host regions. Families with the same household size and school, housing, and medical requirements—and the same relevant place preferences or utilities—share a type. The number of families \(N\) can be much larger than \(\tau\). A mass \(x_{a,p}\) means that this share of the type-\(a\) cohort goes to \(p\); it does not mean an individual household is split across places. In a discrete sequence approximating the model, counts scale as \(N\mu_a\) and supplies as \(Nq_{p,s}\). That per-capita scaling is part of the mirror: the theorem’s literal \(c_{\max}=1\) bound need not remain a constant absolute quota as the population grows.
This is a sensible analogue of the authors’ allocation problem. The same families, destinations, service requirements, upper quotas, and objective remain. The change is that the society is represented by masses of indistinguishable families, and assignments are made to cohorts. A plausible instance has repeated household profiles and a common planner objective of placing as many families as possible. The paper itself studies family allocations and maximum utility, so this does not replace their question with a different outcome-space or axiomatic problem.
I expect this mirror to be Class A. It is a linear program with \(3\tau\) assignment variables and constraints listed over types, places, and services, so it is solvable in time polynomial in the explicit input size, including the binary lengths of masses and supplies. The graph reduction also shows where the finite hardness can go: in its continuous version, each vertex-type mass can be divided among the three places. If each vertex has mass \(1/|V|\) and each place has per-capita capacity \(1/|V|\) for every edge service, assigning one third of every type to each place uses only \(2/(3|V|)\) of each edge service at any place. The resulting allocation is feasible regardless of whether the graph is 3-colorable. The reduction’s indivisible color choices no longer encode feasibility.
The main further questions are how well an optimal mass allocation can be rounded for a finite population, what additive error depends on \(m,\tau,t\), and when the continuous optimum is integral. The mirror covers Theorem 5’s equal-utility maximum-placement result and, as a stronger output, its equal-preference Pareto result; it does not purport to continuize the paper’s entire parameterized-complexity landscape.
The soft spot is that Theorem 5’s reduction itself gives families highly varied service vectors—typically \(\tau\) grows with the number of families—and its hardness uses whole-family assignments. It does not establish hardness in a moderate-support high-multiplicity regime, nor does it show that these authors already endorse a cohort-mass model. The case rests instead on the naturalness of that regime for large resettlement programmes and on retaining the paper’s central family-to-place allocation question while making population mass the object.
The strongest negative case is that Theorem 5’s hardness comes from each family making an indivisible color choice. In its continuous mirror, the paper’s own graph construction becomes easy: split every vertex type equally across the three places. Each edge service then uses \(2/(3|V|)\) at a place, below its \(1/|V|\) supply. The continuous instance accepts every graph, so it says little about where this resettlement model’s computational difficulty goes.
The general maximum-placement mirror remains a clear LP over the explicit type support. That makes it a valid computational question, though a routine one: its tractability follows directly from linear programming, without the paper’s parameterized techniques or a nontrivial pricing problem. The hardness construction also uses services for individual graph edges and typically a distinct type for each vertex. That is a weak match for a programme whose families share a small set of recurring service profiles. A larger cohort with repeated household profiles is plausible, but the resulting LP is then a generic fractional packing model.
The Pareto part needs an extra modeling choice. With an atomless population, changing the assignment of one unassigned family changes no aggregate load, yet counts as a strict Pareto improvement under the literal individual-level definition. Requiring a positive mass of families to improve repairs this, and makes the maximum-mass allocation Pareto-optimal under equal preferences. The MAXUTIL-RR anchor needs no such repair. It also has a useful discrete bridge: with no lower quotas, flooring the \(3\tau\) type-place allocations preserves upper-capacity feasibility and loses fewer than \(3\tau\) placed families. That additive bound is a concrete reason the LP could be useful for large populations.
So the negative case is that this is a narrow, conventional fractional relaxation whose headline hardness witness loses all its force, and whose Pareto interpretation needs care. I cannot honestly make that defeat the MAXUTIL-RR mirror: the cohort scenario is sensible, the mass problem is well-posed, and its simple LP yields an approximation guarantee. The claim that no scenario makes it worthwhile 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.