Strategyproof and Proportionally Fair Facility Location

The strongest positive case is a single anchor: the paper’s welfare-approximation theorem.

The relevant regime is a large public-good electorate. There may be millions of residents, voters, or taxpayers, but only a small number \(\tau\) of distinct ideal provision levels: for example, residents may have peaks on a policy grid \(T=\{x_1,\ldots,x_\tau\}\subseteq[0,L]\). A type is a peak location \(x_t\), together with the common utility convention used in the paper, \(u_t(y)=L-|y-x_t|\). The society is a rational mass vector \(\mu\in\Delta(T)\), where \(\mu_t\) is the fraction of residents of type \(t\). The action remains one facility location \(y\in[0,L]\); only the population is continuized.

My lead question is:

Continuous Proportional-Fair Welfare Design. Given \(L\), a finite rational type set \(T\), and rational masses \(\mu\), construct a rule \(F\) assigning a location \(F(\mu)\in[0,L]\) to every such society. The rule must satisfy the continuum version of Proportional Fairness: for every measurable group \(A\) of positive mass, with range
\[ r(A)=\operatorname*{ess\,sup}_{x\in A}x-\operatorname*{ess\,inf}_{x\in A}x, \]
every \(x\in A\) must satisfy
\[ |F(\mu)-x|\le L(1-\mu(A))+r(A). \]
Its welfare is
\[ \Phi_\mu(y)=\int_{[0,L]}(L-|y-x|)\,d\mu(x), \]
and its approximation ratio is
\[ \rho(F)=\sup_\mu \frac{\max_{y\in[0,L]}\Phi_\mu(y)} {\Phi_\mu(F(\mu))}. \]
The task is to compute or characterize the optimal rule \(F\) minimizing \(\rho(F)\), and, for a given finite-support input \(\mu\), to output \(F(\mu)\) exactly.

This is a direct high-multiplicity version of the paper’s problem. A rational mass vector is exactly a finite profile after clearing denominators, while the continuum formulation removes the irrelevant number of repeated agents. The paper’s fairness term \(|S|/n\) becomes the group mass \(\mu(A)\), and the finite welfare sum becomes the integral above. The facility itself is not being fractionalized.

The natural candidate is the continuum Uniform Phantom rule. In the paper, the finite rule takes the median of the \(n\) reported locations together with phantom locations \(L/n,2L/n,\ldots,(n-1)L/n\). As \(n\) grows, this converges to the median of the mixture
\[ \frac12\mu+\frac12\lambda_L, \]
where \(\lambda_L\) is the uniform distribution on \([0,L]\). Thus \(F_{\mathrm{UP}}(\mu)\) is the unique median of that mixture. For a finite-support rational \(\mu\), it can be computed by sorting the types and scanning cumulative masses; it is therefore an exact polynomial-time evaluation problem in \(\tau\) and the input bit length.

The named anchor is Theorem 5, proved in this paper. It states that, among all mechanisms satisfying UFS, proportionality, or PF, the Uniform Phantom mechanism gives the best welfare approximation guarantee, including among mechanisms that are not strategyproof. It achieves the lower bound established in Lemma 2, also proved in this paper: every UFS, proportional, or PF mechanism has approximation ratio at least
\[ \max_{k\in\mathbb{N}:0\le k\le n/2} \frac{n(n-k)}{k^2+(n-k)^2}, \]
which tends, as \(n\to\infty\), to
\[ \frac{\sqrt{2}+1}{2}\approx 1.207. \]

The lower-bound construction survives particularly cleanly in the continuum. Take mass \(1-\alpha\) at \(0\) and mass \(\alpha\) at \(L\), with \(0\le\alpha\le 1/2\). UFS forces the outcome to be \(y=\alpha L\). The welfare-optimal outcome is \(0\), while the fair outcome has approximation ratio
\[ \frac{1-\alpha}{\alpha^2+(1-\alpha)^2}. \]
Maximizing over \(\alpha\) gives \(\alpha=(2-\sqrt{2})/2\) and ratio \((\sqrt{2}+1)/2\). Thus the finite theorem identifies the exact obstruction that should remain in the population limit, rather than merely suggesting an analogy.

I would expect this mirror to be Class A. Evaluating the Uniform Phantom rule is straightforward one-dimensional computation, and the global bound plausibly follows by the same extremal reduction to two-point populations. The resulting theorem would say that the continuum Uniform Phantom rule is PF-feasible and optimal, with exact worst-case ratio \((\sqrt{2}+1)/2\). Further computational questions include whether PF feasibility admits a polynomial-time separation oracle over all groups \(A\), how quickly finite-\(n\) mechanisms converge to \(F_{\mathrm{UP}}\), and whether the result remains true for atomless distributions rather than finite-support societies.

The authors should recognise this as their problem: it preserves the same one-dimensional facility, the same distance-based fairness, the same welfare objective, and the same mechanism-design comparison. The only substantive change is replacing repeated named agents by their empirical distribution. The appearance of the uniform phantom measure is not an unrelated smoothing device; it is the exact limit of the phantom locations in their own mechanism.

I would not use Theorem 2 or Corollary 2 as a second anchor. Their characterization of strategyproofness is important, but individual deviations become vacuous for zero-mass agents in an atomless population. A meaningful version would need type-block or positive-mass coalition strategyproofness, which is a defensible co-modification but not literally the paper’s notion.

The weakest point is therefore clear: this paper contains no NP-hardness, polynomial-time classification, or parameterized-complexity theorem. The anchor is an approximation-design result, and the finite rational-support mirror has an exact dictionary back to replicated finite profiles. Its positive value is that the mass formulation makes the limiting object—and the \(1.207\) fairness/welfare barrier—explicit and computationally testable. It is a credible Class A continuization of Theorem 5, but not a strong example of discrete computational hardness dissolving in the continuum.