| paper | d4-conf-atal-2016-0243 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Exactly polynomial-time solvable; therefore admits an EPTAS unconditionally. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite set of source and receiver types \(T\), rational masses \(\mu_t\) summing to \(1\), rational type-interaction coefficients \(K_{t,s}\), a global quota \(p\), local caps \(p_s\), and linear benefit and damage rates \(b_t,d_s\), choose open mass \(y_t\in[0,\mu_t]\) to maximize \(R(y)=\sum_t b_t y_t-\sum_s\mu_s d_s E_s(y)\), where \(E_s(y)=\sum_t K_{t,s}y_t\), subject to \(\sum_t y_t\le p\) and \(E_s(y)\le p_s\) for every \(s\).
A continuum of pollution sources grouped by complete source and exposure profile. Each member still chooses open or shut; \(y_t\) is the open mass of type \(t\). Type-level coefficients give the shared exposure field, and the regulator maximizes aggregate linear welfare subject to global and local pollution caps.
Theorem 2’s hardness witness uses item-specific weights and two exceptional hubs, so it does not itself exhibit a repeated-type regional network; the proponent limits the mirror to that regime but does not connect it to the reduction’s topology.
fatal: False
The mirror covers the linear-welfare allocation question anchored by Theorem 2 in a repeated-source, shared-exposure regime. It does not cover the SAT feasibility result in Theorem 1, the truthful-mechanism results, or finite-population implementation and rounding.
The strongest mirror I see is the paper’s linear social welfare problem in a high multiplicity network. A type is a complete source profile: its benefit and damage parameters, operating options, and its pollution effects on every receiving type. Agents with identical profiles are grouped into a type of mass \(\mu_t\), with \(\sum_t\mu_t=1\). In the intended regime there are many sources but relatively few such profiles—for example, large cohorts of industrial sources with the same operating characteristics and dispersion pattern.
Keep each source’s action binary: it is open or shut. In an atomless population, however, any share of a type can be open. Let \(y_t\in[0,\mu_t]\) be the mass of open sources of type \(t\). With a rational type-to-type diffusion coefficient \(K_{t,s}\), the common pollution field at members of receiving type \(s\) is
\[
E_s(y)=\sum_t K_{t,s}y_t.
\]
The regulator imposes \(E_s(y)\le p_s\) for each type and \(\sum_t y_t\le p\). For the paper’s linear benefit and damage functions, welfare is linear:
\[
R(y)=\sum_t b_t y_t-\sum_s \mu_s d_s E_s(y),
\]
where \(b_t\) and \(d_s\) are the respective marginal benefit and damage rates. Thus the continuous question is a rational linear program in the type masses. The type members still each take an integral open-or-shut action; \(y_t\) records how much of the population takes each action.
My lead anchor is Theorem 2, proved in this paper by a reduction from two-dimensional knapsack. It states: “There is no EPTAS for PG with binary variables on the directed planar graph \(G=(V,E)\) when \(b_v\) and \(d_v\) are both linear functions, for any \(v\in V\).” Its reduction uses a simple planar network with item vertices and two hub vertices, encoding the two knapsack capacities through local pollution constraints.
The mirror problem is Planar Mass Pollution Welfare: given rational type masses, a planar type-interaction network with rational coefficients, linear benefit and damage rates, a global quota, and local pollution caps, compute a feasible mass vector \(y\) maximizing \(R(y)\). A solution is the vector of open mass by type. The knapsack correspondence is natural here: item types contribute pollution to the two receptor types, their benefits are the welfare gains, and the mass \(y_t\) can vary continuously between closed and fully open. I expect this mirror to be Class A: the LP solves it exactly in time polynomial in the number of types and input bit length. The paper’s discrete no-EPTAS result makes the question worth asking; it does not transfer once item choices become portions of large homogeneous cohorts.
A second, distinct anchor is Theorem 1, also proved here, by reduction from monotone 1-in-3 SAT. It states that finding a feasible PG allocation satisfying the exact quota \(\sum_v x_v=p\) and the local constraints, when \(p_v=1\) for every vertex and \(w_{uv}>0\) on every edge, is NP-complete.
Its mirror is Exact Mass-Quota Feasibility: given rational type masses, positive rational diffusion coefficients on the type network, and local caps \(p_s=1\), determine whether there is a vector \(y\) with \(0\le y_t\le\mu_t\), exact total mass \(\sum_t y_t=q\), and \(E_s(y)\le1\) for every type \(s\). A solution is such a feasible vector. This too is LP feasibility, so I expect Class A. Here the SAT combinatorics remain in the network of type profiles, but the individual selection integrality that the reduction uses is removed.
These questions cover the paper’s underlying pollution allocation and feasibility problems, not its truthful-mechanism results. They also suggest useful follow-ups: how closely the optimum of the mass LP tracks finite replicated populations, and when mass-feasible quota solutions can be implemented exactly in a finite cohort without losing local-cap feasibility.
The soft spot is the network assumption. The paper permits arbitrary vertex-by-vertex neighborhoods, while this mirror assumes repeated profiles with a common type-level diffusion field. In a geographically irregular network, a complete type must include its whole interaction profile, so the number of types may approach the number of sources. Also, the atomless limit removes each source’s self-contribution from local pollution. That is a natural scaling for a continuum, but it changes the paper’s pointwise local constraint. The mirror is strongest for large, repeated source classes under shared regional exposure limits; it should not be claimed for every network instance in the paper.
The strongest case against is that both anchors derive their difficulty from a graph whose vertices are individually situated. In the paper, an agent’s exposure depends on its particular neighbors, and each vertex has its own local constraint. A type that preserves everything the problem uses must therefore preserve its weighted neighborhood. In the reductions, those neighborhoods encode the hard instance: clause incidence in Theorem 1 and item-specific weights in Theorem 2. Grouping vertices by benefit or damage parameters alone would discard the information that defines feasibility.
Theorem 1 is especially exposed to this problem. Its reduction encodes a SAT instance in the network, so the vertices are not repeated copies of a small set of agent profiles. Aggregating them into masses with type-level exposure constraints replaces that incidence structure with a pooled feasibility problem. A richer continuum model could retain locations or a graphon of interactions, but then the input must describe how exposure varies across the population; in sparse planar networks, that description can require essentially one location or type per vertex. The continuum no longer compresses the relevant structure.
Theorem 2 has a better proposed mirror: repeated source classes contributing to exposure limits at receiver regions. But the reduction’s items are distinguished by their weights and values, while its two hubs are exceptional constraint locations. Making the hubs into positive-mass types and giving every member of a source class the same exposure field changes the network semantics: local, vertex-specific constraints become regional aggregate limits. Keeping individual neighborhoods instead requires preserving the item distinctions and the special hubs. So the proposed mass LP is a sensible model of pooled regional pollution, but its link to the theorem’s planar-network result is loose.
There is a real limit to this negative case. A large population of genuinely repeated sources subject to shared regional exposure limits is plausible, and the authors could recognize its mass-allocation LP as their problem. The paper has named computational results, and the usual objections about the answer being easy or the hardness not transferring do not apply. I can argue that neither theorem supplies a strong, topology-preserving high-multiplicity mirror; I cannot honestly rule out the regional-source mirror. The universal claim that no worthwhile mirror exists is therefore weak, particularly against the Theorem 2 anchor.
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.