arXiv:2609.19394 · v2

Strategyproof Aggregation in Euclidean Spaces: Rigidity and Median Optimality

首次提交 2026-09-17 04:25

版本更新 2026-11-05 07:50

雷达观测 2026-11-06 11:06

摘要

We study deterministic strategyproof mechanisms for facility location in finite-dimensional Euclidean spaces. For every population of at least three agents and every finite dimension, the coordinate-wise median minimizes the worst-case approximation ratio among anonymous mechanisms. Agent identities can improve the ratio at a fixed population size, and we give an explicit four-agent separation. Nevertheless, for every fixed dimension, the optimal ratio over all deterministic strategyproof mechanisms converges, as the population grows, to the supremum of the median's ratios over finite populations. Combined with the sharp bound for the median, this gives the optimal guarantee $\sqrt{6\sqrt3-8}$ uniform over populations and dimensions. The main structural ingredient is a rigidity theorem for strategyproof aggregation. We characterize unanimous, anonymous, translation-equivariant strategyproof mechanisms with bounded individual influence as fixed coordinate-wise order-statistic rules in a single orthonormal frame. We also prove that, for strategyproof mechanisms, continuity is equivalent to convexity of the full range in every finite dimension. An approximation-preserving normalization and a reflection argument yield the fixed-population anonymous comparison. To remove anonymity in the large-population limit, we develop an extraction theorem that converts a common guarantee on arbitrarily large populations into an anonymous deterministic mechanism on any prescribed finite population.