| paper | Approximate Mechanism Design for Distributed Facility Location |
| authors | Aris Filos-Ratsikas, A. Voudouris |
| venue | SAGT 2021 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper's numbered results establish distortion guarantees, strategyproofness, and lower bounds on achievable distortion, but none asserts a running-time result, computational hardness result, or computable optimization formulation. The proposed finite-alternative high-multiplicity MM/DM models are coherent and easy to evaluate, yet the rubric explicitly excludes distortion bounds and rule-impossibility statements as satisfying bit \(a\). Thus the mass mirror is statable, but no named result supplies the required computational anchor.
fails bit a — no named computational result to mirror
Against the strongest proposed anchor, Theorem 3.5, the opponent's point survives: its distortion guarantee does not itself assert a computational result, and distortion bounds are explicitly excluded by the gate.
fatal: True
The proposed mirror covers the finite-alternative MM and DM results under a mass dictionary, including Theorems 3.1, 3.5, 3.6, 4.2, and 4.5, but not the paper's alternative-space continuous setting, proxy voting, asymmetric districts, or other objectives.
The strongest honest case is a high-multiplicity version of the paper’s finite-alternative distributed facility-location problem. I would make this the lead rather than rely on the paper’s own “continuous setting”: there, it is the alternative space that becomes continuous, whereas here \(A\) remains finite and only the population is continuized.
Take \(k\) symmetric districts, a finite set of alternatives \(A\subseteq\mathbb Q\), and a finite set \(X\subseteq\mathbb Q\) of ideal positions. A type is \(t=(d,x)\): district \(d\), ideal position \(x\), and therefore the complete information relevant to the problem. A society is a rational mass vector \(\mu_{d,x}\ge 0\) satisfying \(\sum_x\mu_{d,x}=1/k\) for each district. Its social cost at \(a\in A\) is
\[ \mathrm{SC}_\mu(a)=\sum_{d=1}^k\sum_{x\in X}\mu_{d,x}|x-a|. \]
The local action is a district representative \(r_d\in A\); the final decision is one of the representatives, \(z\in\{r_1,\dots,r_k\}\). A distributed mechanism must choose \(r_d\) from the distribution in district \(d\) alone, then aggregate the representatives. Its objective is worst-case distortion,
\[ \frac{\mathrm{SC}_\mu(z)}{\min_{a\in A}\mathrm{SC}_\mu(a)}. \]
This is genuinely high multiplicity. If \(\mu_{d,x}=n_{d,x}/n\), then it is exactly the finite election with \(n_{d,x}\) agents of type \((d,x)\). We can choose \(n\) arbitrarily large while keeping \(k\), \(|X|\), and the number of distinct types small.
The lead anchor is Theorem 3.5, proved in this paper: “The distortion of MM is at most \(3\).” Here MM chooses, for each district,
\[ r_d^{\mathrm{MM}}\in \arg\min_{a\in A}\sum_x\mu_{d,x}|x-a|, \]
with the paper’s leftmost tie-breaking rule, and then chooses the median representative. Its population mirror is:
\[ \mathsf{HM\text{-}MM}: \quad \text{given }(k,A,X,\mu),\text{ compute }(r_1,\dots,r_k,z) \text{ and the distortion of }z. \]
At the design level, the corresponding question is to minimize worst-case distortion over all local two-stage mechanisms. A solution is a rule assigning representatives and a final representative to every mass profile. The paper’s Theorem 4.2, also proved here, gives the matching lower bound: in the discrete setting, every mechanism has distortion at least \(3-\varepsilon\), for every \(\varepsilon>0\). Thus the high-multiplicity design problem should have exact optimum \(3\), achieved by MM.
This mirror is tractable: evaluate \(O(|A|)\) weighted costs per district, select the representatives, and take their median. Its running time is polynomial in \(k\), \(|X|\), \(|A|\), and the encoding length of \(\mu\), independent of the underlying population size \(n\). The distortion proof transfers exactly because normalization merely divides every social cost by \(n\).
A second worthwhile mirror preserves the paper’s strategyproofness question. Theorem 3.6, proved here, states that “The distortion of DM is at most \(7\).” Theorem 3.1 proves that DM is strategyproof, while MM is not. The matching negative result is Theorem 4.5, proved here: in the discrete setting, every strategyproof mechanism has distortion at least \(7-\varepsilon\), for every \(\varepsilon>0\).
The corresponding problem is
\[ \mathsf{HM\text{-}SP\text{-}DFL}: \quad \min_{M} \sup_{\mu} \frac{\mathrm{SC}_\mu(M(\mu))} {\min_{a\in A}\mathrm{SC}_\mu(a)}, \]
where \(M\) must be local, deterministic, and strategyproof on every finite replication of every rational mass profile. This last clause prevents strategyproofness from becoming vacuous in a literal nonatomic model: if one agent changes report, the corresponding mass vector changes by one unit of the replication. A solution must specify the local rule and the final aggregation rule.
The continuous-population DM rule takes a weighted median ideal position in each district, selects the closest alternative in \(A\), and then takes the median of those representatives. The expected answer is exactly \(7\): DM supplies the upper bound, and Theorem 4.5’s repeated-position constructions transfer directly to rational masses. These constructions can use \(n\) much larger than the number of types, so the lower bound is compatible with the high-multiplicity regime.
The original authors should recognize both mirrors as their problem. The districts, locality restriction, finite alternative set, absolute-distance objective, representative aggregation, and distortion benchmark are unchanged. Only the list of individually named agents is replaced by a distribution over indistinguishable district-position types. The paper’s own proofs already use fractions such as \(\lambda/2\) and \(\lambda/4\), and its lower-bound instances are made almost entirely from repeated positions.
The main weakness is that this paper contains no named NP-hardness, \(P\), FPT, or parameterized-complexity theorem. Its named results are distortion and strategyproofness theorems, so this is an algorithmic mechanism-design mirror rather than a complexity-landscape result. There is also a modelling choice in extending individual strategyproofness to finite-replication strategyproofness. If that convention is rejected, the strategyproof anchor weakens. The first MM mirror survives that objection: it is a clean population continuization, has an exact high-multiplicity dictionary, and yields a tractable problem with optimal distortion \(3\).
The decisive objection is that none of the proposed anchors is a computational result in the ChoCo sense. Theorems 3.5 and 3.6 are distortion bounds, Theorem 3.1 is a strategyproofness claim, and Theorems 4.2 and 4.5 are impossibility results for mechanism classes. The paper has no complexity theorem, hard optimization problem, approximation algorithm, or parameterized result whose population axis can be continuized.
The MM mirror is certainly coherent, but it is only a compressed implementation of the existing mechanism. For explicit finite \(A\) and \(X\), one computes
\[ r_d\in\arg\min_{a\in A}\sum_{x\in X}\mu_{d,x}|x-a| \]
by direct weighted summation, then takes a median and evaluates the benchmark. This takes polynomial time in \(k\), \(|A|\), \(|X|\), and the encoding length of \(\mu\). The corresponding finite-agent computation was already elementary: replacing repeated agents by multiplicities merely replaces repeated additions by weighted additions. No column-generation problem, separation problem, relaxation, or complexity phenomenon appears.
Theorem 4.2 does not repair this. The proposed
\[ \min_M\sup_\mu \frac{\mathrm{SC}_\mu(M(\mu))} {\min_{a\in A}\mathrm{SC}_\mu(a)} \]
is a mathematical optimization over unrestricted functions \(M\), not a finite computational problem. To make it algorithmic one must specify how mechanisms are represented and how their behavior on the infinitely many mass profiles is queried. If one restricts to MM, DM, or another explicitly listed family, evaluation is trivial. If one searches over a finitely encoded mechanism class, that is a new mechanism-design problem, not a computational mirror of Theorem 4.2.
The strategyproofness anchor is weaker still. In an actual nonatomic population, a unilateral agent has measure zero, so changing one report leaves \(\mu\) unchanged. Strategyproofness therefore becomes vacuous for any mechanism depending only on the population distribution. The proponent’s repair—requiring strategyproofness on every finite replication—does produce a sensible dictionary, but it is a family of discrete games indexed by the hidden replication size \(n\), not a native continuum game. It restores the original individual deviations rather than continuizing them.
One can instead let a positive-mass type misreport, or permit coalitions controlling an \(\varepsilon\)-mass. But then the strategic unit is no longer an individual, and the resulting notion is not what Theorems 3.1 and 4.5 establish. Choosing among these notions would create a new research programme rather than mirror the paper’s result. Under the finite-replication convention, Theorem 4.5 transfers only because its constructions already use repeated agents and rational fractions.
The strongest possible concession is important: the MM high-multiplicity model is not nonsensical. Districts containing large cohorts of agents at the same ideal position are plausible, and there is no identity-dependent objective blocking aggregation. If the criterion were merely “can one write down a valid mass version?”, this paper would pass. But under ChoCo’s computational criterion, the anchors fail: they continuize a population in a model whose substantive results are already count-insensitive and whose algorithms are elementary. I would therefore reject this paper as a worthwhile source of a continuous computational mirror, while acknowledging that the negative case rests on the absence of a computational target, not on any impossibility of modelling its agents by masses.
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.