| paper | d4-conf-atal-2021-0231 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorems 4.1 and 4.2 are named computational hardness results, so bit (a) holds. But the proposed continuous questions are the paper’s own optimization problems over customers already continuously distributed on \([0,1]\), leaving no discrete-to-continuous mirror. The proponent explicitly identifies this collision, which settles the grade under b-already.
fails bit b-already — the paper is already native to the continuum
The proposed anchors cover utilitarian and egalitarian welfare hardness; Theorem 4.3 also studies this continuous-demand model. Fairness approximation and price-of-fairness results are not anchored, and none of these results yields a separate continuous mirror.
The strongest honest positive case is that this paper already studies a computational problem whose customer population is continuous. On a densely populated corridor, take customer type to be location \(x\in[0,1]\), with mass given by Lebesgue measure. The customer mass in an interval is its length. There are \(n\) facilities, each with a valuation density \(f_i\); for a location profile \((x_1,\ldots,x_n)\) of pairwise distinct facility locations, the proximity rule induces each facility’s interval \(A_i\). A solution is the location profile and its induced allocation. The utilitarian objective is \(\sum_i\int_{A_i}f_i(x)\,dx\); the egalitarian objective is \(\min_i\int_{A_i}f_i(x)\,dx\).
This is a plausible large-population regime: the number of customers can be arbitrarily large, while the population is represented by a demand measure and finitely described valuation densities. The location \(x\) is a customer’s complete type for proximity assignment. There are, however, continuously many possible types; the model does not have the small finite type support typical of a high-multiplicity formulation.
My lead anchor is Theorem 4.1, proved in this paper. It states that finding a valid allocation maximizing utilitarian social welfare is NP-hard, even when the facilities’ valuation functions are piecewise-uniform. The paper proves this by reduction from EXACT-3-COVER. A precise decision version is: given a rational threshold \(K\) and explicitly represented piecewise-uniform valuation densities, is there a profile of pairwise distinct facility locations whose proximity-induced allocation has utilitarian welfare at least \(K\)? The optimization version asks for a maximizing profile and its allocation. I expect this problem to be hard in the continuous model itself—provisionally Class C—because the paper establishes hardness directly for continuous demand using a combinatorial construction. The paper does not establish that hardness transfers from a discrete counterpart. Further questions include approximation guarantees and tractability under restrictions on the number of density intervals or facility types.
A second, related anchor is Theorem 4.2, also proved in this paper. It states that finding a valid allocation maximizing egalitarian social welfare is NP-hard, even when the valuation functions are piecewise-uniform. Its decision version asks whether some pairwise-distinct location profile induces an allocation with \(\min_i\int_{A_i}f_i(x)\,dx\ge K\); a solution to the optimization problem is a maximizing profile and allocation. I likewise expect this to be hard in the continuous model, provisionally Class C. It raises separate questions about approximation and whether the hardness persists under more restricted density descriptions.
Both anchors are strong on model fit: the paper’s theorems already concern optimizing over facility locations and the allocation of continuous customer mass under the proximity rule. They cover the efficiency results only; they do not mirror the fairness approximation theorems or the price-of-fairness results.
The weak point is also central to interpreting the case: this is already a continuous-demand paper, so these are not new mirror questions awaiting formulation. And its continuum is spatial, with location itself distinguishing customer types; it does not provide ChoCo’s usual bridge from a finite-support high-multiplicity society to a continuous problem, or a complexity analysis parameterized by support size \(\tau\). Thus it is excellent evidence that computational questions over continuous populations are legitimate, but a collision if presented as a newly proposed mirror of this paper.
Theorem 4.1 is already the proposed computational question over a continuous population: it proves NP-hardness of maximizing utilitarian welfare when customers are distributed continuously on \([0,1]\). The reduction even uses piecewise-uniform valuations. Writing its decision version with a welfare threshold, or asking for the maximizing location profile, does not create a mirror; it restates the problem the theorem has already studied.
Theorem 4.2 has the same problem for egalitarian welfare. Its NP-hardness result is already about allocating continuous customer mass under the proximity rule. Theorem 4.3 adds an approximation algorithm for utilitarian welfare in that same model. These are computational results, not merely continuous cake-cutting axioms or analytic results about equilibria.
The strongest alternative would be to impose a ChoCo-style finite support and ask for complexity in the number of customer types. But location is essential to the proximity rule: facility locations determine moving Voronoi boundaries, so grouping an interval of positions into one type generally loses information needed to determine who is served. Keep location as the type and the support is continuous, reproducing the paper’s model. Collapse locations into finitely many atoms and the model changes: demand is concentrated at points, rather than spread along the line. Such a finite-type problem might be worth studying, but it would be a new spatial facility-location variant, not a continuous mirror of these results.
A more formal input encoding or a parameterized analysis by the number of density pieces could also be useful, especially given the paper’s use of valuation oracles and restricted piecewise-uniform inputs. That would sharpen the complexity theory of an existing continuous model; it would not fill ChoCo’s gap by continuizing a previously discrete population.
So both anchors fail as *new* continuous mirrors because the paper has already crossed the population-continuity boundary and proved the relevant computational results there. The limit of this negative case is its universality: I cannot rule out worthwhile follow-on models. I can argue that plausible alternatives either repeat the paper’s continuous problem or change it into a different one.
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.