PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimality and Impossibility in Multidimensional Strategyproof Facility Location

Jianan Lin

arXiv:2610.36613v1cs.GT

TL;DR

The paper asks how much social-cost efficiency deterministic strategyproof facility-location mechanisms can achieve in multidimensional normed spaces, especially as anonymity, the norm, and facility count vary. It proves optimality results for one facility and impossibility results for multiple facilities. The conclusions distinguish Euclidean and ℓ∞ settings and specify when the impossibility results extend to higher dimensions and more facilities.

  • Problem

    The paper asks what social-cost approximation deterministic strategyproof mechanisms can achieve in multidimensional normed spaces, and how the answer depends on anonymity, the norm, and the number of facilities.

    Source: §1 · pp. 1–2

  • Method

    The paper proves lower bounds using geometric restrictions on attainable facility locations and extends two-facility bounds through a distant-agent reduction.

    Source: §1.1 · p. 2, §3.1 · p. 7, §4.1 · p. 14

  • Results

    The coordinate-wise median is optimal among deterministic strategyproof mechanisms for one Euclidean-plane facility, while no finite ratio is possible for multiple facilities under the stated norm and symmetry conditions.

    Source: §1.1 · p. 2, §6 · p. 20

  • Takeaways & Limitations

    The conclusions depend on the spatial norm and symmetry assumptions: ℓ∞ admits a strategyproof optimal single-facility mechanism, while the multiple-facility impossibility extends to k < n.

    Source: §1.1 · p. 2, §6 · p. 20

    The higher-dimensional multiple-facility impossibility assumes anonymity or invariance under exchanging one fixed pair, and the endpoint norms p = 1 and p = ∞ remain open.

    Source: §4.3 · p. 18, §6 · p. 20

Abstract

from arXiv · show

We study facility location in multidimensional normed spaces with the objective of minimizing social cost, the sum of agents' distances to their nearest facility. A deterministic mechanism selects $k$ facility locations based on the reports of $n$ agents and is strategyproof (SP) if no agent can reduce her distance by misreporting her location. We establish optimal approximation ratios and impossibility results. For a single facility in the Euclidean plane, we prove that the optimal approximation ratios among deterministic SP mechanisms are exactly those obtained by Goel and Hann-Caruthers [SCW 2023] for the coordinate-wise median (CM): $\frac{\sqrt{2(n^2+1)}}{n+1}$ for odd $n\ge3$ and $\sqrt{2}$ for even $n\ge4$. We remove the anonymity assumption from their optimality result. However, CM is not always optimal in non-Euclidean spaces: we give an SP mechanism that minimizes social cost exactly in $\ell_\infty^d$, whereas CM has a tight uniform approximation ratio of $2$ already in the plane. We then consider two facilities in $\ell_p$ spaces with $1<p<\infty$ and prove two impossibility results for every $n>2$. In the plane, no deterministic SP mechanism has a finite approximation ratio. In higher dimensions, the same impossibility holds for anonymous deterministic SP mechanisms. Finally, a reduction using distant agents and a limiting argument extends both impossibility results to every $k>2$ with $n>k$.

1 Introduction

The paper studies how deterministic strategyproofness constrains social-cost efficiency in multidimensional facility location, where open questions concern anonymity, spatial norms, and multiple facilities. It establishes single-facility optimality results and multiple-facility impossibility results, with scope depending on the norm and symmetry assumptions.

1.1 Our Contributions

  • The Euclidean-plane coordinate-wise median is optimal among all deterministic strategyproof mechanisms for every n ≥3, removing the anonymity requirement.For n = 2, a dictatorship attains ratio 1.Source: §1.1 · p. 2
  • In ℓ∞^d, the lexicographically smallest social-cost minimizer is anonymous, strategyproof, and optimal, while the coordinate-wise median has tight uniform ratio 2 already in the plane.This shows that coordinate-wise median optimality does not persist across spatial norms.Source: §1.1 · p. 2
  • For every 1 < p < ∞, no deterministic strategyproof two-facility mechanism has a finite approximation ratio in the plane; in higher dimensions, this holds for anonymous mechanisms.In higher dimensions, invariance under exchanging one fixed pair of agents suffices for the impossibility.Source: §1.1 · p. 2
  • A distant-agent reduction extends both multiple-facility impossibility results to every 3 ≤k < n while preserving strategyproofness, approximation guarantees, and retained-agent symmetry.It converts a mechanism for n agents and k facilities into one for n −k + 2 agents and two facilities.Source: §1.1 · p. 3

1.2 Related Work

  • Prior work studies strategyproof facility location across Euclidean and other normed spaces, alternative social-cost objectives, and randomized mechanisms for single- and multiple-facility settings.The introduction situates the paper alongside characterization, approximation-bound, and mechanism-design results in these settings.Source: §1.2 · p. 3

2 Preliminaries

The preliminaries define the agents, facility outputs, incentive constraint, and social-cost benchmark used in the paper. They also specify the scope of facility counts and how approximation guarantees are interpreted.

2 Preliminaries

  • A deterministic k-facility mechanism maps reported profiles to a nonempty set of at most k locations; facilities may coincide and agents use a nearest facility.The paper focuses on 1 ≤k < n because k ≥n permits zero cost by placing facilities at every distinct report.Source: §2 · p. 4
  • Social cost sums agents’ distances to their nearest facilities, and the optimal k-facility social cost is the minimum over nonempty facility sets of size at most k.The approximation ratio compares a mechanism’s cost with this optimum.Source: §2 · p. 4
  • A mechanism is strategyproof when no agent can lower her cost by misreporting, with costs evaluated at her true location.Anonymity means permuting reports leaves the facility set unchanged, and is imposed only when stated.Source: §2 · p. 4
  • A finite approximation guarantee requires zero mechanism cost whenever the optimal social cost is zero; an unbounded ratio means no finite guarantee across profiles for fixed parameters and space.The ratio is defined as the infimum of valid ρ ≥1, and is infinite when no finite ρ works.Source: §2 · p. 4

3 Single-Facility Location

The section examines optimal strategyproof mechanisms for single-facility location in Euclidean and ℓ∞ spaces. It establishes coordinate-wise median optimality in the Euclidean plane and presents a strategyproof, social-cost-minimizing flex mechanism in ℓ∞^d.

3.1 Lower Bounds in the Euclidean Plane

  • This Euclidean optimality result removes anonymity from Goel and Hann-Caruthers ’s result for anonymous mechanisms.They also determined the exact ratio for odd n.Source: §3.1 · p. 4, §3 · p. 4

3.2 Exact Optimization in ℓ∞Spaces

  • In ℓ∞ spaces, lexicographically selecting a social-cost minimizer is anonymous and strategyproof with approximation ratio 1; the coordinate-wise median has tight uniform ratio 2 in the plane.The lexicographic rule successively minimizes each coordinate among the remaining social-cost minimizers.Source: §3.2 · pp. 9–10
  • The ℓ∞^d flex mechanism is strategyproof: a profitable misreport would imply a lexicographically smaller output that remains socially optimal.The proof perturbs the truthful and misreported optimal outputs in opposite directions; the cost changes sum to at most zero, so both perturbed points remain optimal, contradicting the tie-break.Source: §3.2 · p. 10
  • The flex mechanism can be computed using d + 1 linear programs: one to minimize total ℓ∞ distance and d sequential programs to fix the output coordinates.The first program minimizes the sum of variables r_i subject to |y_j − x_i,j| ≤ r_i; subsequent programs minimize and fix y_1 through y_d in order.Source: §3.2 · p. 10

4 Two-Facility Location

The section studies deterministic strategyproof mechanisms for locating two facilities in ℓ_p spaces with 1 < p < ∞. It establishes that no such mechanism has a finite approximation ratio in the plane, and that the same impossibility holds in higher dimensions under anonymity.

4.1 Common Structural Lemmas

  • For n ≥ 3 agents and two facilities, any deterministic SP ρ-approximation yields a three-agent mechanism with the same approximation guarantee; if the original is invariant under exchanging a specified pair, the reduction preserves that symmetry.Source: §4.1 · p. 11
  • SP menus are closed, contain the fixed reports, and preserve a nearest menu point when the agent reports along the segment toward it.These properties support the later local-menu and propagation arguments.Source: §4.1 · p. 12
  • If one agent’s local direction cone is pointed at any q ≠ a, the other agent is exactly served at every report while the third agent is fixed at a.Exact service means a facility is placed at that agent’s reported location.Source: §4.1 · p. 14

4.2 Lower Bounds in the Plane

  • No deterministic SP two-facility mechanism has a finite social-cost approximation ratio in the plane for any 1 < p < ∞ and n ≥ 3.The section’s higher-dimensional result requires anonymity, and both impossibility results hold for each fixed n ≥ 3.Source: §4 · pp. 10–11, §4.2 · p. 15
  • In the plane, either one agent is exactly served throughout the fixed-report problem or both agents’ local menus lie on fixed, distinct lines through zero.The lines are mutually orthogonal under the duality map, and the section rules out this complementary-lines alternative to establish impossibility.Source: §4.2 · p. 16
  • In the plane, no deterministic strategyproof two-facility mechanism has a finite social-cost approximation ratio for n > 2.The proof reduces to three agents, propagates complementary line structures to a contradiction, and rules out the remaining restrictions by showing that exact service makes approximation unbounded or fails as agents approach coincident locations.Source: §4.2 · p. 17

4.3 Anonymous Lower Bounds in Higher Dimensions

  • For finite d ≥ 2, 1 < p < ∞, and n ≥ 3, anonymous deterministic strategyproof two-facility mechanisms in ℓ_p^d have no finite approximation ratio; the result also holds under invariance to exchanging one fixed pair.Exchange symmetry makes the pair’s direction sets coincide; the proof shows their common cone is pointed, propagates exact service, and derives a contradiction as two agents approach the same point.Source: §4.3 · pp. 17–18
  • The impossibility proofs use strict convexity for segment persistence and local uniqueness, and a differentiable duality map for propagation.The cases p = 1 and p = ∞ remain open.Source: §4.3 · p. 18

5 Extension to Multiple Facilities

A distant-agent reduction converts any finite-guarantee mechanism with k facilities into a two-facility mechanism on fewer agents, preserving strategyproofness and anonymity. This yields impossibility results for multiple facilities in the stated ℓ_p settings.

5 Extension to Multiple Facilities

  • Taking limits also preserves symmetry among retained agents, completing the reduction from k facilities to at most two finite facilities.The limit contains at least one finite facility; duplicate or infinite entries are removed.Source: §5 · pp. 18–19
  • A finite-guarantee k-facility mechanism induces a two-facility mechanism for n − k + 2 agents, preserving its guarantee, strategyproofness, anonymity, and retained-agent pair symmetries.The reduced instance has at least three agents when k < n.Source: §5 · p. 18
  • Placing the k − 2 additional agents increasingly far apart forces distinct facilities near them, leaving at most two facilities to serve the retained agents.The construction bounds the optimum of the augmented instance by the two-facility optimum of the retained profile.Source: §5 · p. 18
  • Deleting distant facilities preserves each fixed incentive comparison for sufficiently large separation, because retained agents’ relevant service distances stay bounded.The threshold may depend on the profile and deviation.Source: §5 · p. 19
  • A common convergent subnet across all profiles preserves the limiting mechanism’s strategyproofness and approximation guarantee.The product-space construction ensures convergence along the same indices for truthful and deviating profiles.Source: §5 · p. 19
  • For 1 < p < ∞, no deterministic strategyproof mechanism has a finite social-cost approximation ratio for 2 ≤ k < n in the plane; in higher dimensions, this holds for anonymous mechanisms.In higher dimensions, invariance under exchanging just one fixed pair of agents suffices.Source: §5 · p. 19

6 Conclusion

The paper establishes deterministic strategyproof facility-location results for single and multiple facilities under social cost. Its conclusions include a planar Euclidean optimality result, a norm-specific exact mechanism, and multi-facility impossibility results, alongside open questions.

6 Conclusion

  • The coordinate-wise median is optimal among all deterministic strategyproof mechanisms in the Euclidean plane for every n ≥ 3, while ℓ∞^d has a strategyproof exact social-cost minimizer.For 2 ≤ k < n in ℓ_p spaces with 1 < p < ∞, no deterministic strategyproof mechanism has a finite ratio in the plane; higher-dimensional impossibility holds under pair-exchange invariance.Source: §6 · p. 20
  • Open questions include removing the higher-dimensional symmetry assumption, resolving endpoint norms p = 1 and p = ∞ for multiple facilities, and removing anonymity for 3 ≤ k < n on the line.The line question follows prior impossibility results under anonymity.Source: §6 · p. 20
  • The author reports using GPT Astra-6 to explore proof approaches and Codex to assist with drafting and proof checking, and says the content was carefully checked.The author takes responsibility for correctness.Source: §6 · p. 20
Loading 2610.36613v1…