Facility Location Games with Scaling Effects

The strongest positive case is a modest but genuine one: the paper has a direct high-multiplicity mirror for its exact facility-location computations. It is a Class A mirror, not a claim that the paper contains a new hardness result.

Consider a municipality with \(N\) residents distributed among \(\tau\) standardized residential locations \(z_1,\ldots,z_\tau\), where \(N\gg\tau\). Residents at the same location are identical for the paper’s model: they face the same public scaling function \(q\) and incur the same cost \(q(y)|y-z_t|\) at facility location \(y\). Let \(\mu_t\in\mathbb{Q}_{\ge 0}\) be the fraction of residents at \(z_t\), with \(\sum_t\mu_t=1\). The scaling function remains the paper’s external environmental object—terrain, transport access, signal quality—and \(y\in[0,1]\) remains the facility’s continuous placement. Only the population is continuized.

This is a direct high-multiplicity mirror. If \(\mu_t=n_t/N\), then the continuous total cost is \(\mathrm{TC}_\infty(q,y,\mu)=q(y)\sum_t\mu_t|y-z_t|=\mathrm{TC}(q,y,\mathbf{x})/N\), so the minimizers are identical. Likewise, \(\mathrm{MC}_\infty(q,y,\mu)=q(y)\max_{t:\mu_t>0}|y-z_t|\) is exactly the discrete maximum cost. Clearing denominators recovers the finite repeated-agent instance.

My lead anchor is Corollary 3.4, proved in this paper, building on the paper’s proved Theorem 3.3. The authors show that when \(q\) is continuous and piecewise linear with a constant number of local minima, an optimal total-cost placement can be found in linear time by checking agent locations and local minima of \(q\).

The corresponding problem is Mass-Total-Scaled-Facility\(_\infty\). An instance consists of rational locations \(z_1<\cdots<z_\tau\), rational masses \(\mu_1,\ldots,\mu_\tau\), and a positive continuous piecewise-linear \(q\) with rational breakpoints and coefficients and \(O(1)\) local minima. The task is to output an exact \(y^\star\in[0,1]\) minimizing \(\mathrm{TC}_\infty(q,y,\mu)\), together with the optimum value. A solution is accepted precisely when \(y^\star\in\arg\min_y\mathrm{TC}_\infty(q,y,\mu)\).

Theorem 3.3 gives the structural certificate: \(y^\star\) lies among the occupied locations \(z_t\) and the local minima of \(q\). With prefix sums of the masses and their first moments, all weighted distance terms at the \(z_t\)’s can be evaluated in one scan. Thus the mass problem is solvable in polynomial time, in fact in \(O(\tau+k)\) arithmetic work after reading a \(k\)-segment description of \(q\), up to rational bit complexity. This is not a softened welfare problem: it is exactly the authors’ total-cost objective with repeated residents compressed into masses. It is the clearest example of the paper’s result becoming an exact high-multiplicity algorithm.

A second, independent anchor is Proposition 3.7, also proved here. For a linear scaling function, the paper proves that an optimum for maximum cost belongs to \(\{0,(x_1+x_n)/2,1\}\).

The corresponding problem is Mass-Max-Scaled-Facility\(_\infty\). An instance consists of rational type locations and masses as above and a positive rational linear function \(q(y)=ay+b\). Let \(z_-=\min\{z_t:\mu_t>0\}\) and \(z_+=\max\{z_t:\mu_t>0\}\). The task is to output an exact minimizer of \(\mathrm{MC}_\infty(q,y,\mu)=q(y)\max_{t:\mu_t>0}|y-z_t|\). Proposition 3.7 gives the candidate set \(\{0,(z_-+z_+)/2,1\}\), so the problem is in \(\mathrm{P}\), with only a scan to find \(z_-\) and \(z_+\), followed by three evaluations. This is again a direct mirror: repeated agents affect neither the feasible placements nor the maximum-cost semantics.

The authors should recognize both problems as their own questions. The facility, location domain, scaling function, total-cost and maximum-cost objectives, and exact placement decision are unchanged. The only alteration is replacing a long list of repeated residents by their rational type distribution. The natural scenario is not a seven-person committee but a large population living in a small number of residential zones or geographic cohorts—precisely the regime in which the paper’s sums and extrema admit high-multiplicity compression.

These mirrors are Class A. They generate useful follow-up questions: whether the \(O(1)\)-local-minimum condition can be removed; how exact complexity depends on the number of pieces of \(q\); what can be proved for an oracle-represented general continuous \(q\); and whether multiple facilities or higher-dimensional locations turn the simple candidate-set structure into a genuine configuration or separation problem.

I am deliberately not anchoring on the paper’s strategyproofness results. In a literal atomless population, unilateral deviations have zero mass, so preserving those results would require a cohort-deviation or finite-\(N\) interpretation. That would be an extension rather than a direct mirror. Nor do I claim an NP-hardness transfer: the paper contains no such named result.

The weakest point is therefore novelty. These are easy subclasses, and much of the gain is representational—computing exactly from \(\tau\) types instead of \(N\) repeated agents—rather than a new complexity phenomenon. The maximum-cost mirror in particular depends only on the extreme occupied locations. But that weakness does not defeat the positive case: the programme explicitly treats exact high-multiplicity compression and Class A tractability as legitimate outcomes. On that standard, Corollary 3.4 supplies a strong, faithful continuous-population mirror.