| paper | Strategyproof facility location for concave cost functions |
| authors | Dimitris Fotakis, Christos Tzamos |
| venue | SIGECOM 2013 |
| filed under | coalition · wvg |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: The requirements are compatible. Support-based Equal Cost is weakly group-strategyproof under rational mass transfers and provides weighted social-cost factor \(1/\min_t\mu_t\), asymptotically sharp for this construction. No factor depending only on \(\tau\) and \(k\) holds for this construction. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3.1
Given \(k\), finitely many location types \(T\) with positions \(z_t\), a rational distribution \(\mu\in\Delta(T)\), and a common nondecreasing concave cost function \(c\) with \(c(0)=0\), construct a randomized \(k\)-facility mechanism \(\mathcal M(\mu,c)\) that is group-strategyproof against feasible mass transfers \(\delta_{tu}\ge 0\), and guarantees \(\mathbb E[\max_{t:\mu_t>0} c(\min_j|z_t-Y_j|)]\le 2\,\mathrm{MC}^*_{\mu}\) and \(U_t(\mu)\le\mathrm{MC}^*_{\mu}\) for every supported type \(t\), while characterising its weighted social-cost guarantee.
A high-multiplicity society on the line has types \(t\in T\), mass \(\mu_t\), and ideal locations \(z_t\). The mechanism computes a minimum-length cover of the supported locations by \(k\) equal disjoint intervals, samples the Equal Cost offset \(X_\ell\in[0,\ell]\), and places point facilities according to the alternating-offset rule; utilities are \(U_t=\mathbb E[c(\min_j|z_t-Y_j|)]\), and mass deviations move \(\delta_{tu}\) between reported types.
The mirror's mechanism is largely support-sensitive rather than mass-sensitive, so its main contribution may be high-multiplicity compression rather than a new mass-dependent complexity phenomenon.
fatal: False
The mirror covers Theorem 3.1's Equal Cost mechanism, group strategyproofness, the \(2\)-approximation for Max Cost, the per-type bound, and the induced \(1/\mu_{\min}\) weighted-social-cost bound; it leaves Pick the Loser, the convex impossibility result, and the other extensions untouched.
The strongest honest case is a narrow but credible Class A mirror of the paper’s main Equal Cost result, specifically its Max Cost and per-type guarantee. I would not use Pick the Loser as an anchor: its condition \(n=k+1\) makes it a poor high-multiplicity regime, since repeated locations would usually leave \(k\) facilities for at most \(\tau\) distinct types.
A natural regime is municipal facility planning along a large urban corridor. There are \(N\) residents, with \(N\gg \tau\), but only \(\tau\) standardized residential zones or location types. Type \(t\) means an ideal location \(z_t\), with the common commuting-cost function \(c\) used by the paper. Thus \(\mu_t\) is the fraction of residents in zone \(t\). This is genuine high multiplicity: residents of the same type are indistinguishable for the problem, while the number of residents may be enormous.
My anchor is Theorem 3.1, proved in this paper. It states, in full, that for every concave cost function, Equal Cost is group strategyproof, has approximation ratio \(2\) for Max Cost, has approximation ratio \(n\) for Social Cost, and additionally gives every agent expected cost at most the optimal Max Cost. The theorem is stated in the paper’s [Section 3](https://arxiv.org/html/1305.3333v1). This is an algorithmic approximation result, not an NP-hardness theorem; that limitation matters.
The corresponding problem should be called *Continuous Concave \(k\)-Facility Location with Mass Strategyproofness*. An instance consists of \(k\), a finite ordered type set \(T=\{1,\ldots,\tau\}\), locations \(z_t\in\mathbb R\), a distribution \(\mu\in\Delta(T)\), and a common nondecreasing concave cost function \(c\) with \(c(0)=0\). The decision variable is a randomized placement of \(k\) point facilities, namely a distribution \(\mathcal M(\widehat\mu,c)\) over \(k\)-tuples \(Y=(Y_1,\ldots,Y_k)\) of facility locations. The cost of a true type \(t\), when the reported population is \(\widehat\mu\), is
\(\displaystyle U_t(\widehat\mu)=\mathbb E_{Y\sim\mathcal M(\widehat\mu,c)}\left[c\left(\min_j|z_t-Y_j|\right)\right].\)
A mass deviation is a matrix \(\delta_{tu}\ge 0\), where mass of true type \(t\) reports type \(u\). It produces the reported distribution \(\widehat\mu_u=\mu_u-\sum_v\delta_{uv}+\sum_v\delta_{vu}\). The mechanism is mass-group-strategyproof if there is no nonzero feasible transfer for which every type sending positive mass strictly lowers its true-type cost \(U_t\). This is the nonvacuous continuum analogue of the paper’s coalition definition; unilateral measure-zero deviations would otherwise have no effect.
The continuous problem is to construct such a mechanism satisfying
\(\displaystyle \mathbb E\left[\max_{t:\mu_t>0}c\left(\min_j|z_t-Y_j|\right)\right]\le 2\,\mathrm{MC}^*_\mu,\)
and \(U_t(\mu)\le \mathrm{MC}^*_\mu\) for every supported type \(t\), where \(\mathrm{MC}^*_\mu\) is the best deterministic \(k\)-facility Max Cost for the supported locations. The population-weighted social objective is also well-defined as \(\mathrm{SC}_\mu=\sum_t\mu_tU_t\). The natural translation of the paper’s \(n\)-factor is \(1/\mu_{\min}\), where \(\mu_{\min}=\min_{t:\mu_t>0}\mu_t\): the per-type bound implies \(\mathrm{SC}_\mu\le \mu_{\min}^{-1}\mathrm{SC}^*_\mu\). For a finite profile with \(\mu_t=n_t/n\), this recovers the paper’s \(n\)-bound.
The intended mechanism is a direct population version of Equal Cost. Ignore zero-mass types and cover the supported locations with \(k\) disjoint equal-length intervals of minimum length \(\ell\). Choose \(X_\ell\in[0,\ell]\) so that \(\mathbb E[c(|x-X_\ell|)]\) is identical for every \(x\in[0,\ell]\). Then place facilities at \(\alpha_i+X_\ell\) in odd intervals and at \(\alpha_i+\ell-X_\ell\) in even intervals. Facilities remain point facilities; neither the outcome space nor the population is being fractionalized. The randomness is the same policy randomization already present in the paper.
This is plausibly Class A. The interval cover is a finite computation over the \(\tau\) supported locations, and for the paper’s piecewise-linear concave costs the equalizing distribution is obtained from a finite linear system. For rational \(\mu\), the bridge is exact: replicate type \(t\) \(n_t\) times and recover the finite profile with proportions \(\mu_t=n_t/n\). Conversely, any repeated-location finite profile compresses to this distributional instance. Since Equal Cost depends on the support for its Max Cost guarantee, partial mass changes that leave the support unchanged do nothing; support-changing deviations reduce to the paper’s finite coalition argument.
The mirror covers Theorem 3.1, not the whole paper. In particular, I would not claim that it establishes a new hardness-dissolution phenomenon: the paper contains no comparable NP-hardness anchor. The further computational questions are whether the equalizing distribution has polynomial bit complexity for arbitrary finite descriptions of \(c\), whether a genuinely mass-sensitive mechanism can obtain a constant approximation for \(\mathrm{SC}_\mu\), and what changes for a continuous location density rather than finite support.
The weakest point is that, under Max Cost, the masses \(\mu_t\) are largely invisible once the support is fixed. A critic can therefore call this a high-multiplicity compression of the original location profile rather than a deeply mass-sensitive continuous theory. I think that objection is limited—Max Cost in the original theorem is itself multiplicity-insensitive, and the per-type guarantee is exactly what the theorem proves—but it makes this a modest, mechanism-design Class A mirror rather than a flagship complexity result.
The negative case is stronger than an objection to the municipal example: the paper has no qualifying computational anchor. Its numbered results are distortion and strategyproofness theorems, not complexity results for a computational problem. Theorem 3.1 does not establish membership in \(\mathrm{P}\), hardness, an exact algorithmic complexity bound, or a parameterized algorithm. The interval enumeration and linear-system construction are implementation observations, with no input-encoding or polynomial-time theorem; for arbitrary continuous concave \(c\), the paper explicitly leaves computation “beyond the scope.” Thus the proponent’s anchor is precisely the kind of distortion result the programme’s gate excludes.
Even setting that gate aside, the proposed lift is a support compression, not a genuinely population-continuous version of the theorem. For any two distributions \(\mu\) and \(\nu\) with the same positive-support locations,
\[ \{z_t:\mu_t>0\}=\{z_t:\nu_t>0\}, \]
Equal Cost produces the same intervals and the same facility distribution, and both \(\mathrm{MC}^*_\mu\) and every type’s utility are unchanged. Partial mass transfers that leave the support unchanged therefore cannot affect anyone’s cost. A transfer matters only when it deletes a type entirely, at which point the problem has become a discrete support-deletion problem. The distribution’s magnitudes never enter the anchored objective or mechanism.
The per-type guarantee does not repair this. The bound \(U_t\leq \mathrm{MC}^*\) is pointwise, so its weighted version is immediate bookkeeping:
\[ \mathrm{SC}_\mu\leq \mathrm{MC}^* \leq \frac{1}{\mu_{\min}}\mathrm{SC}^*_\mu. \]
It supplies no mass-sensitive algorithm and no new structural result. The proponent’s reverse dictionary—replicate type \(t\) \(n_t\) times and then compress duplicates—is exactly a quotient of an anonymous finite location profile, not a continuous-population phenomenon of the kind ChoCo is meant to study.
The strongest rescue would replace Max Cost by population-weighted Social Cost and ask for a mechanism whose outcome genuinely depends on \(\mu\). That is a legitimate research problem, but it is no longer the paper’s theorem. The paper gives only the vacuous \(1/\mu_{\min}\) consequence, which can be as large as the population scale, and says nothing about a mass-responsive mechanism or its computational complexity. One would have to introduce a new objective, a new mass-deviation incentive notion, and a new mechanism-design problem. That may be worthwhile facility-location research, but it is not a continuization of a named computational result here.
A continuous location density does not help: with full support, Equal Cost depends only on the support’s geometry, not on the density; with gaps, it depends discontinuously on whether a region has zero mass. Adding type-specific cost functions or other attributes merely turns the exercise into a new heterogeneous-cost model, which the paper lists as an open direction rather than proves.
Pick the Loser offers no rescue either. Its \(n=k+1\) premise and single-agent loser are inherently finite-agent/order-statistic objects; under repeated locations the paper itself makes the problem trivial by placing facilities at every distinct location.
So I would reject this as a ChoCo mirror. The paper can motivate a new continuous facility-location project, especially around mass-weighted social cost, but its actual theorem either erases \(\mu\) or requires replacing the theorem with a different problem. The absolute claim that no such broader project could ever be worthwhile would be too strong; the claim that this paper supplies a worthwhile continuous computational mirror is not.
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.