| paper | Settling the Distortion of Distributed Facility Location |
| authors | — |
| venue | AAMAS 2023 |
| filed under | frontier · tools-data |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper contains no numbered result classifying the complexity of a computational problem; its theorems concern distortion, mechanism performance, unanimity, or strategyproofness, and distortion bounds are expressly excluded. The proposed continuous lifts are coherent high-multiplicity research questions, but they are post hoc extensions and cannot repair bit (a). Therefore the paper is red despite offering plausible future continuous-population facility-location problems.
fails bit a — no named computational result to mirror
The proposed lifts cover the unrestricted Sum-of-Max result in Theorem 5.3 and the unrestricted Max-of-Sum result in Theorem 6.1. They leave the remaining distortion bounds and strategyproofness results outside the proposed continuous-population formulation, and none supplies a qualifying computational anchor.
The strongest honest answer is that this paper fails the programme’s named-anchor gate. It contains no numbered theorem, lemma, corollary, or proposition asserting NP-hardness, polynomial-time solvability, FPT, W[1]-hardness, or another computational-complexity classification. Its named results—Theorems 3.7, 4.1–4.2, 5.3–5.5, and 6.1–6.3—are distortion bounds; Lemmas 2.1 and 2.2 concern unanimity and strategyproofness. Under ChoCo’s strict rule, therefore, there are no qualifying anchors and no valid per-anchor continuous problem to report.
There is nevertheless a strong salvage candidate, though it must be labelled an extension rather than a mirror anchored by the paper. The lead would be a Continuous Distributed Sum-of-Max Facility Location problem inspired by Theorem 5.3, proved in this paper. Take \(k\) districts and a finite rational location-type set \(X\subseteq\mathbb{Q}\). District \(d\) has a rational mass distribution \(\mu_d\) over \(X\), with total mass \(1\). A complete type is \((d,x)\): district and location. This represents many interchangeable residents—after clearing denominators, \(\mu_d(x)\) becomes the fraction of a large clone population at \(x\).
A distributed solution must first compute a representative \(y_d\) from \(\mu_d\) alone, then output \(w\in\{y_1,\ldots,y_k\}\). Define
\[ F_{\mathrm{SoM}}(\mu,w) = \sum_{d=1}^{k} \max_{x:\mu_d(x)>0}|x-w|. \]
The problem is to output the distributed representatives and final facility location minimizing \(F_{\mathrm{SoM}}\). The natural solution is
\[ y_d=\frac{\min\operatorname{supp}(\mu_d)+\max\operatorname{supp}(\mu_d)}{2}, \qquad w=\operatorname{median}(y_1,\ldots,y_k). \]
Indeed,
\[ \max_{x\in\operatorname{supp}(\mu_d)}|x-w| = \frac{b_d-a_d}{2} + \left|w-\frac{a_d+b_d}{2}\right|, \]
so a median of the district midpoints is globally optimal. This is a plausible Class A problem, solvable in polynomial time by computing supports and a median. It is recognisably the authors’ distributed facility-location problem, while genuinely making the population—not merely the facility location—the continuous object.
A second plausible extension uses Theorem 6.1, proved here. With
\[ F_{\mathrm{MoS}}(\mu,w) = \max_d\sum_{x\in X}\mu_d(x)|x-w|, \]
let each district report its mean
\[ y_d=\sum_x\mu_d(x)x \]
and let the final output be the leftmost representative. Theorem 6.1’s argument extends directly and gives a \(2\)-approximation; the two point-mass districts at \(-1\) and \(1\) show that factor \(2\) remains unavoidable. This is also likely Class A, and it is the more mass-sensitive formulation because population proportions affect the objective rather than merely determining support endpoints.
The weakest point is decisive: these are new computational formulations built from distortion theorems, not computational results stated by the paper. The paper’s strategyproofness results are even less suitable: with atomless agents, unilateral deviations have zero mass and become vacuous; replacing them by positive-mass coalition deviations would be a substantive re-modeling. Thus the paper offers a convincing source for a future high-multiplicity facility-location programme, but not a qualifying ChoCo anchor under the stated rules.
The paper fails ChoCo’s anchor gate. Its numbered results—Theorems 3.7, 4.1–4.2, 5.3–5.5, and 6.1–6.3—are distortion bounds, while Lemmas 2.1 and 2.2 concern unanimity and strategyproofness. None classifies the complexity of a computational problem. Thus there is no paper-stated computational result whose population high-multiplicity version ChoCo could mirror.
The proposed Sum-of-Max extension is especially weak as a continuization. Its natural lift is
\[ F_{\mathrm{SoM}}(\mu,w) = \sum_d \operatorname{ess\,sup}_{x\sim\mu_d}|x-w|. \]
Writing \(a_d=\operatorname{ess\,inf}\operatorname{supp}(\mu_d)\) and \(b_d=\operatorname{ess\,sup}\operatorname{supp}(\mu_d)\), each district contributes
\[ \operatorname{ess\,sup}_{x\sim\mu_d}|x-w| = \frac{b_d-a_d}{2} + \left|w-\frac{a_d+b_d}{2}\right|. \]
The masses \(\mu_d(x)\) disappear entirely. Replacing every district distribution by two arbitrarily small atoms at \(a_d\) and \(b_d\) leaves the objective, representatives, and winner unchanged. This is not a continuous population problem in any substantive computational sense; it is a problem about district extrema. Making mass matter would require changing the objective to an integral, quantile loss, or similar quantity, which is no longer the paper’s Sum-of-Max result.
Strategyproofness does not rescue it. Under an atomless population, one individual has zero measure and cannot change the aggregate distribution, so unilateral strategyproofness becomes vacuous. A positive-mass deviation is a coalition or type-block deviation, not the paper’s notion of strategyproofness. That is a new incentive concept, not a harmless limiting reformulation.
The proposed Max-of-Sum extension is the strongest salvage:
\[ F_{\mathrm{MoS}}(\mu,w) = \max_d\int |x-w|\,d\mu_d(x). \]
Here mass genuinely matters, and the mean-based mechanism has a coherent high-multiplicity interpretation. But it is still an extension invented after the fact, not a mirror of a computational theorem in the paper. With finite rational support, the input is scanned directly to compute means and costs; the paper contributes no complexity bottleneck, separation problem, approximation algorithm, or parameterized question. With general distributions, the computational model for representing and integrating \(\mu_d\) is unspecified. To make this a genuine ChoCo problem one would have to design a new computational formulation—perhaps optimizing over finitely represented local mechanisms—which is precisely evidence that the paper itself supplies no anchor.
The same issue applies to the better mass-sensitive lift of Theorem 3.7 using
\[ \sum_d\int |x-w|\,d\mu_d(x). \]
It is mathematically coherent, and unlike Sum-of-Max it does not collapse to supports. But it remains a new continuous mechanism-design problem, not a computational result of this paper. The paper’s population is finite and individuated; its continuity lies in the facility-location outcome space, which ChoCo explicitly excludes as its continuization axis.
So the strong negative verdict is that this paper should not enter ChoCo as an anchored computational mirror: the proposed Sum-of-Max mirror degenerates, strategyproofness loses its meaning, and the mass-sensitive variants are post hoc extensions with no complexity claim to inherit. The universal claim that no worthwhile mirror exists in any scenario is weaker than this verdict and cannot honestly be proved: the Max-of-Sum and social-cost lifts are defensible new high-multiplicity research questions. The paper is therefore a poor source for the programme, but not evidence that continuous-population facility location is intrinsically unworthwhile.
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.