| paper | d4-conf-aldt-2017-0004 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathsf{NP}\)-complete even for \(k=1\); \(\mathsf{FPT}\) parameterized by \(k\) if and only if \(\mathsf P=\mathsf{NP}\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given finite good classes \(G\), a rational distribution \(\mu\) over supported ranking types \(T\), and rational per-capita supplies \(s_g\), choose deletion masses \(d_g\) and a distribution \(x_{t,b}\) over integral bundles \(b\in\mathbb{Z}_{\ge 0}^{G}\). Require \(0\le d_g\le s_g\), \(\sum_b x_{t,b}=\mu_t\), \(\sum_{t,b}x_{t,b}b_g=s_g-d_g\), and, for every bundle assigned positive mass to type \(t\), \(\sum_{g\in P_t(j)}b_g\ge\left\lceil\sum_{g\in P_t(j)}(s_g-d_g)\right\rceil\) for each ranked prefix \(P_t(j)\). Minimize \(\sum_g d_g\), or decide whether it is at most a given rational budget \(\kappa\).
A high-multiplicity allocation model with mass \(\mu_t\) for each ranking type, per-capita stock \(s_g\) of each good class, deletion mass \(d_g\), and configuration variables \(x_{t,b}\) assigning type mass to integral bundles that satisfy the rounded prefix quotas.
The proposed class-boundary quotas omit constraints at prefixes within a class of individually ranked items, and rounded quotas can make positive-mass bundle feasibility jump sharply; the case does not establish an exact counterpart for the paper’s strict item rankings.
fatal: False
The mirror covers the unbounded-agent deletion problem anchored by Theorem 2. It leaves the three-agent algorithm of Theorem 5 and the paper’s finite-instance running-time bounds aside.
The strongest case is for a mass version of Proportionality by Item Deletion, in a large allocation programme where households fall into a small number of recurring preference types. Think of a planner withholding unsuitable or surplus goods from a round so that the remaining stock can be allocated proportionally. A finite base cohort has \(\tau\)\) ranking types; in a high-multiplicity regime, each type appears many times and each good class has stock proportional to the population. The number of people can therefore be much larger than \(\tau\)\), even as \(\tau\)\) grows across instances.
My anchor is Theorem 2, proved in this paper: Proportionality by Item Deletion is W[3]-hard when parameterized by \(k\), the maximum number of items deleted. The proof reduces from weighted satisfiability for formulas of the form \(\bigwedge_i \bigvee_j \bigwedge_\ell \neg x_{i,j,\ell}\)\), with target assignment weight \(k\). The theorem concerns an unbounded number of agents.
Here is the continuous question I would ask. Call it Mass-PID. The instance has a finite set \(G\) of good classes, a distribution \(\mu\)\) over supported types \(T\), where each type is a strict ranking of \(G\), and rational per-capita supplies \(s_g\). Choose deletion masses \(d_g\), with \(0\le d_g\le s_g\). The objective is to minimize \(\sum_{g\in G} d_g\)\).
A solution must also allocate all remaining supply. Write \(x_{t,b}\) for the mass of type-\(t\) agents receiving bundle \(b\), where \(b\in\mathbb{Z}_{\ge0}^{G}\) gives integral counts of each good class. Require \(\sum_b x_{t,b}=\mu_t\)\) and \(\sum_{t,b}x_{t,b}b_g=s_g-d_g\)\) for every \(g\). Each unit of agent mass receives one integral bundle; the real-valued \(x_{t,b}\) records how much of a type gets each bundle.
For type \(t\), let \(P_t(j)\) be its first \(j\) good classes. Every bundle assigned positive mass to that type must satisfy
\[ \sum_{g\in P_t(j)} b_g \;\ge\; \left\lceil\sum_{g\in P_t(j)}(s_g-d_g)\right\rceil \qquad\text{for every }j. \]
This applies the paper’s prefix proportionality condition at class boundaries: the right-hand side is the integral quota induced by the remaining top-ranked supply per agent. The decision form asks whether Mass-PID has a solution with \(\sum_g d_g\le\kappa\)\), for a rational per-capita budget \(\kappa\)\).
I would initially expect continuum-specific hardness for Mass-PID. The reduction’s structure lives in item choices and ranked-prefix patterns, which remain in this model; mass allocation does not make an individual bundle fractional. Also, the ceiling quotas change discretely as deletion masses move across thresholds, so a configuration LP is not automatically a tractability result. The key algorithmic question is whether those choices admit a compact flow or LP formulation with an efficient pricing problem.
The paper’s parameter \(k\) does not directly become \(\kappa\)\): \(k\) counts individual deletions, while \(\kappa\)\) measures deleted supply per unit population. So Theorem 2 motivates the Mass-PID question but does not establish its W[3]-hardness. A useful further question is whether any natural parameterization of Mass-PID has a W-hierarchy analogue, or whether fractional deletion makes it tractable.
The weak point is the goods representation. I treat repeated copies within a class as indistinguishable and impose the prefix condition at class boundaries. The paper assumes strict rankings over individual items, so an exact common tie-break among copies may add constraints. If the authors insist that every individual-item prefix must be preserved, this mirror needs refinement before it can claim to be their problem. I would still take the class-based version to them: it keeps their deletion action, proportionality goal, and integral bundles while giving population mass and per-capita supply a precise role. It covers the unbounded-agent hardness result, not their separate three-agent algorithm or the paper’s finite-instance running-time bounds.
Theorem 2 is the proponent’s only anchor, and its parameter \(k\) is the part least preserved by a population limit. In a society normalized to mass one, deleting a fixed number \(k\) of named items has mass \(k/n\), which tends to zero as the population grows. Giving deletion a nonzero per-capita budget \(\kappa\) instead means allowing roughly \(\kappa n\) discrete deletions. That may define a useful new control problem, but Theorem 2’s W[3]-hardness for small \(k\) does not anchor its complexity. Keeping an absolute number of deletions means keeping discrete atoms, which gives up the continuous control the mirror was meant to study.
The stronger obstacle is the paper’s individual fairness guarantee. In Mass-PID, every positive-mass bundle must satisfy the prefix quotas. Consider one preference type, with \(A\) ranked above \(B\), and per-capita supplies \(s_A=s_B=1/2\). At the prefix containing \(A\), the proposed quota is \(\lceil 1/2\rceil=1\). Every member of the type must receive an \(A\), though only \(1/2\) unit of \(A\) is available per capita. The exact mirror is infeasible. More generally, fractional prefix supplies can make the integer quotas impossible for a large type. The assignment variables can mix integral bundles across mass, but that does not help when every bundle must meet the same rounded quota.
One repair is to constrain only the type’s average bundle. In this example, half the mass could receive \(A\) and half could receive \(B\), meeting an average quota of \(1/2\). But then half the agents receive nothing from their first-choice prefix, contrary to the paper’s necessary proportionality condition. That repair changes the fairness question rather than resolving a technicality. A class-based goods model also needs care: the paper ranks distinct items strictly, and its prefix conditions can depend on the order of individual items within a class, information a class-supply vector omits.
This makes the proposed Mass-PID a weak mirror of Theorem 2: its per-capita budget changes the parameterized question, while its exact fairness condition can turn fractional supplies into coarse feasibility jumps. I cannot honestly conclude that no worthwhile mirror exists in any scenario. A planner allocating scaled stocks to recurring preference cohorts is plausible, and the feasibility jumps themselves could merit study. But the case for this particular anchor is weaker than it first appears: making its mass model behave smoothly seems to require relaxing the individual guarantee that defines PID.
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.