Optimal Transport for
Facility Location

基于最优输运理论设计设施选址问题的最优真实机制

—— 论文深度学术总结与经济管理启示专报（100% Word 原生公式版）

【论文题目】Leveraging Optimal Transport to Design Optimal Mechanisms for the Facility Location Problem
【文章作者】Gennaro Auricchio（Department of Mathematics, University of Padua, Padova, Italy；E-mail: gennaro.auricchio@unipd.it）
Jie Zhang（Department of Computer Science, University of Bath, Bath, UK；E-mail: jz2558@bath.ac.uk）
【发表期刊】ACM Transactions on Economics and Computation (TEAC), Vol. 14, No. 3, Article 9 (September 2026), 44 pages.
【数字标识】https://doi.org/10.1145/3757106
【前序版本】早期精简版曾发表于第 17 届算法博弈论国际学术研讨会（SAGT 2024）。
【JEL分类号】D82（Asymmetric and Private Information; Mechanism Design；不对称与私人信息；机制设计）、C78（Bargaining Theory; Matching Theory；议价理论；匹配理论）、R53（Public Facility Location Analysis; Public Investment；公共设施选址分析；公共投资）、C61（Optimization Techniques; Programming Models；最优化技术；规划模型）、H41（Public Goods；公共品供给）。
【核心关键词】Automated mechanism design; Bayesian mechanism design; Optimal transport; Facility location problem; Percentile mechanisms; Wasserstein projection; Truthfulness.

一、 研究背景与文章核心理论贡献

设施选址问题（$k$-Facility Location Problem, 简称 $k$-FLP）是运筹优化、微观经济学机制设计与算法博弈论的交叉前沿基础议题。在经典的一维线段设定中，公共部门或平台规划者需要在地理主干道或单维空间中选址设立 $k$ 个同质公共设施（如公立医院、消防救援站、中小学、公交换乘枢纽等），为 $n$ 个拥有私有物理坐标的自利智能体（Agents）提供服务。每个智能体理性选择前往距离最近的设施，其负效用表现为出行空间阻力。由于此类纯公共品配置场景天然排斥排他性的货币转移支付（即属于无货币机制设计，Mechanism Design without Money），掌握私有真实位置的自利参与者存在极大的诱因进行虚假陈述，策略性操纵设施落点以迎合个人私利。

自 Procaccia & Tennenholtz (2013) 奠定无货币真实设施选址的研究范式以来，“占优策略真实性（Truthfulness / Strategyproofness）”便构成了选址机制的制度红线。然而，经典计算机科学文献长期奉行防御性的“最坏情况分析（Worst-Case Analysis）”，以近似比（Approximation Ratio）衡量真实机制相对于无约束社会最优选址的最大福利损失。在单设施（$k = 1$）时，经典中位数机制不仅真实且绝对最优（近似比为 $1$）；但在多设施（$k \geq 3$）时，学术界遭遇了极其悲观的“不可能定理”壁垒：Fotakis & Tzamos (2014) 与 Walsh (2022) 严格证明，在线段上针对 $k \geq 3$ 个设施，不存在任何具有有界最坏情况近似比的确定性、匿名真实机制（即使仅有 $k + 2$ 个智能体，其最坏情况近似比也是无穷大 $+ \infty$）。

分位数机制（Percentile Mechanisms, Sui et al., 2013）作为中位数机制的自然高维推广，根据智能体排序后的固定百分比位次（次序统计量）确定设施落点，天然满足匿名性与真实性。然而在最坏情况对抗视角下，其近似比同样暴跌至 $+ \infty$，这使得该类机制长期被认为在理论上缺乏效率保障。

针对上述重大理论僵局，Gennaro Auricchio 与 Jie Zhang 在本篇长达 44 页的 TEAC 奠基性论文中另辟蹊径，将设施选址全面置于贝叶斯机制设计（Bayesian Mechanism Design）框架下，假设智能体位置独立同分布地抽样自连续先验概率分布 $\mu$。更为精妙的是，论文开创性地架起了机制设计与数学物理领域的“最优输运理论（Optimal Transport, OT）”之间的桥梁，将选址决策转化为测度空间上的 Wasserstein 投影问题。基于这一崭新视角，文章取得了以下八项里程碑式的核心理论突破：

1. 建立设施选址与 Wasserstein 测度投影的严格对偶等价性： 论文证明，线段上的 $k$-FLP 在数学本质上完全等价于智能体离散经验测度在 $k$ 点离散测度子空间 $\mathcal{P}_{k}\mathbb{(R)}$ 上的 $p$ 阶 Wasserstein 投影问题。通过该对偶关系，成功将最优输运领域的偏微分方程、变分几何与实证测度收敛工具系统注入机制设计。

2. 彻底破除多设施真实机制“近似比必定无界”的理论魔咒： 证明了在贝叶斯环境下，只要先验分布满足一阶矩有限的基本正则性，对于任意设施数量 $k$，分位数机制的贝叶斯近似比（期望机制成本与期望最优成本之比）在参与者数量趋向无穷大时必定收敛于一个确定的有限常数界，终结了最坏情况下的悲观绝境。

3. 确立“渐近最优分位数机制”的存在性（贝叶斯近似比趋向 1）： 论文严格证明：对于任意给定的连续先验分布 $\mu$，必定存在一组严格处于内部开区间的最优分位数向量 ${\overrightarrow{v}}_{\mu} \in (0,1)^{k}$，其诱导的分位数机制能够完全渐近消除策略防范带来的社会福利损失，即贝叶斯近似比在样本量增长时严格收敛至 $1$。这雄辩地证实，在大样本下仅采用分位数机制是“无损的（Without Loss of Generality）”。

4. 精确刻画收敛速率并建立首个有限样本非渐近性能界： 利用次序统计量的 Bahadur 强表示理论与一致可积性，证明了贝叶斯比收敛到极限的代数速度：社会成本与最大成本下为 $O(n^{- 1/2})$，广义 $l_{p}$ 成本下为 $O(n^{- 1/(2p)})$。据此推导出对任意有限样本规模 $n > k$ 均成立的非渐近显式性能保证公式，填补了有限群体应用场景的理论空白。

5. 发现最优分位数向量与极限比的正仿射“尺度不变性（Scale-Invariance）”： 证明了最优分位数向量与极限贝叶斯近似比在任意正仿射线性变换 $X' = \sigma X + m$（$\sigma > 0$）下严格保持不变。规划者仅凭先验分布的族类形态（如正态分布、均匀分布、指数分布）即可锁定最优选址百分比，完全无需探知真实的均值位置与方差尺度，极大降低了政策落地的认知门槛。

6. 构造求解最优分位数机制的 $k$ 元代数方程组与解析式： 将传统自动化机制设计（AMD）中棘手的高维离散搜索，化简为由 $k$ 个非线性代数方程组成的局部中位数方程组。并在追求平均主义公平的最大成本（MC）下，直接推导出了对任意 $k$ 通用的显式闭式分位数解析解。

7. 建立先验分布估计误差下的稳定性与鲁棒性界： 针对现实中规划者只能依赖历史抽样或人口普查数据获得近似分布 $\overset{\sim}{\mu}$ 的痛点，证明了最优分位数的效率损失被真实分布与近似分布间的无穷 Wasserstein 距离严格线性控制，理论界为 $3\frac{W_{\infty}(\mu,\overset{\sim}{\mu})}{W_{p}(\mu,\nu^{(k)})}$，证明了机制对统计抽样误差具备极强的韧性。

8. 统一社会效益（功利主义）、极端公平（最大成本）与广义 $l_{p}$ 范数： 全方位覆盖了功利主义社会成本（$l_{1}$ 范数）、罗尔斯主义最大成本（$l_{\infty}$ 范数）以及权衡效率与公平的 $l_{p}$ 范数，系统揭示了不同社会福利哲学在机制构造与空间博弈中的内在统一性。

二、 核心概念、严谨数学定义与模型符号体系

为确保后文定理阐述与实例分析的数学严密性，本节系统定义文章所使用的基础博弈模型、福利评价指标以及最优输运测度几何符号体系。

1. 空间环境、参与者与个体成本

（1）智能体集合与真实位置：考虑实数轴 $\mathbb{R}$ 上的自利智能体集合 $\mathcal{N = \lbrack}n\rbrack ≔ \{ 1,2,\ldots,n\}$。每个智能体 $i$ 拥有私有的真实地理坐标 $x_{i}\mathbb{\in R}$。在不失一般性前提下，将智能体位置按单调递增次序编号，即 $x_{1} \leq x_{2} \leq \ldots \leq x_{n}$。全体智能体的位置组合向量记为 $\overrightarrow{x} ≔ (x_{1},x_{2},\ldots,x_{n}) \in \mathbb{R}^{n}$。

（2）设施候选位置：规划者需在 $\mathbb{R}$ 上选址放置 $k$ 个同质公共设施，设施位置向量记为 $\overrightarrow{y} ≔ (y_{1},y_{2},\ldots,y_{k}) \in \mathbb{R}^{k}$，同样默认非降序排列：$y_{1} \leq y_{2} \leq \ldots \leq y_{k}$。设施无容量上限，提供完全同质的服务。

（3）个体出行成本：位于 $x_{i}$ 的智能体将理性就近选择设施，其承担的个体出行阻力成本 $c_{i}(x_{i},\overrightarrow{y})$ 定义为其到最近设施的欧氏距离：

$$c_{i}(x_{i},\overrightarrow{y}) ≔ \underset{j \in \lbrack k\rbrack}{\text{min}}\left| x_{i} - y_{j} \right|$$

2. 社会目标成本函数体系

规划者的选址决策取决于其所秉持的社会福利哲学，文章统一考察三类标准目标函数。为使样本规模 $n$ 趋向无穷大时度量保持同阶稳定性，文章对社会成本与 $l_{p}$ 成本进行了标准化的每人平均化处理（Rescaling）：

（1）社会成本（Social Cost, SC，功利主义目标，Utilitarian Cost）：度量全体智能体出行成本的算术平均值，旨在最大化全社会总福利（最小化社会总出行功耗）：

$$SC(\overrightarrow{x},\overrightarrow{y}) ≔ \frac{1}{n}\sum_{i = 1}^{n}{}c_{i}(x_{i},\overrightarrow{y})$$

（2）最大成本（Maximum Cost, MC，罗尔斯主义平等目标，Egalitarian Cost）：度量全社会遭受最大出行不便的个体成本，旨在缩小空间服务鸿沟，提供最底层的服务包容性保障：

$$MC(\overrightarrow{x},\overrightarrow{y}) ≔ \underset{i \in \lbrack n\rbrack}{\text{max}}c_{i}(x_{i},\overrightarrow{y})$$

（3）广义 $l_{p}$ 成本（Generalized $l_{p}$ Cost, $p \in (1, + \infty)$）：个体成本的 $l_{p}$ 平均范数，$p$ 越大越倾向于压制极端偏远距离（惩罚严重不平等）：

$$C_{l_{p}}(\overrightarrow{x},\overrightarrow{y}) ≔ \left( \frac{1}{n}\sum_{i = 1}^{n}{}c_{i}(x_{i},\overrightarrow{y})^{p} \right)^{\frac{1}{p}}$$

3. 选址机制、真实性与经典最坏情况近似比

（1）设施选址机制：机制定义为一个映射函数 $f:\mathbb{R}^{n} \rightarrow \mathbb{R}^{k}$，它汇集所有智能体上报的位置信息剖面 $\overrightarrow{x}$，输出 $k$ 个设施的具体落点 $\overrightarrow{y} = f(\overrightarrow{x})$。

（2）占优策略真实性（Truthfulness / Strategyproofness）：机制 $f$ 是真实的，当且仅当对于任意智能体 $i$、任意真实位置 $x_{i}$ 以及任意虚假策略性上报 $x'_{i}$，真实报告均能实现成本的弱最小化：

$$c_{i}(x_{i},f(\overrightarrow{x})) \leq c_{i}(x_{i},f({\overrightarrow{x}}_{- i},x'_{i}))$$

（3）最坏情况近似比（Worst-Case Approximation Ratio）：经典算法机制设计中，机制 $f$ 相对于全知最优社会成本 $SC_{opt}(\overrightarrow{x})$ 的近似比定义为全空间极端恶劣输入下的最坏比值：

$$ar(f) ≔ \underset{\overrightarrow{x} \in \mathbb{R}^{n}}{\text{sup}}\frac{SC_{f}(\overrightarrow{x})}{SC_{opt}(\overrightarrow{x})}$$

在经典文献中，当 $k \geq 3$ 时，任何确定性匿名真实机制在此指标下的近似比均为无穷大（$ar(f) = + \infty$）。

4. 贝叶斯机制设计与贝叶斯近似比

贝叶斯分析假定智能体位置不是由恶意对抗的对手任意指定，而是从共同的先验概率分布 $\mu$ 中独立同分布抽样得到，即 $X_{i} \sim \mu$（i.i.d.），记随机向量为 ${\overrightarrow{X}}_{n} = (X_{1},\ldots,X_{n})$。在此设定下：

（1）贝叶斯真实性：由于占优策略真实机制在每一个确定的样本实现上均保证真实报告最优，因此其自动在期望意义下满足贝叶斯真实性：

$$\mathbb{E}_{{\overrightarrow{X}}_{- i}}\lbrack c_{i}(x_{i},f(x_{i},{\overrightarrow{X}}_{- i}))\rbrack \leq \mathbb{E}_{{\overrightarrow{X}}_{- i}}\lbrack c_{i}(x_{i},f(x'_{i},{\overrightarrow{X}}_{- i}))\rbrack$$

（2）贝叶斯近似比（Bayesian Approximation Ratio）：以机制的期望社会成本与全知无约束期望最优成本之比，度量机制的平均绩效损失：

$$B_{ar,1}^{(n)}(f) ≔ \frac{\mathbb{E\lbrack}SC_{f}({\overrightarrow{X}}_{n})\rbrack}{\mathbb{E\lbrack}SC_{opt}({\overrightarrow{X}}_{n})\rbrack}$$

对应于 $l_{p}$ 成本与最大成本的贝叶斯近似比分别记为 $B_{ar,p}^{(n)}(f)$ 与 $B_{ar,\infty}^{(n)}(f)$。

5. 分位数机制（Percentile Mechanisms, $\mathcal{P}\mathcal{M}_{\overrightarrow{v}}$）

给定一个 $k$ 维分位数比例向量 $\overrightarrow{v} ≔ (v_{1},v_{2},\ldots,v_{k})$，满足 $0 \leq v_{1} \leq v_{2} \leq \ldots \leq v_{k} \leq 1$。当智能体上报并排定序位 $x_{1} \leq \ldots \leq x_{n}$ 时，分位数机制 $\mathcal{P}\mathcal{M}_{\overrightarrow{v}}$ 将 $k$ 个设施直接定位在对应百分比位次的智能体坐标上：

$$y_{j} = x_{i_{j}},其中序号\ i_{j} ≔ \lfloor(n - 1)v_{j}\rfloor + 1$$

该机制具有高度的匿名性（仅依赖序位统计量）与免货币占优策略真实性，是单设施中位数机制在高维设施空间的典范拓展。

6. 最优输运（OT）与 Wasserstein 测度几何

（1）经验测度与离散设施测度空间：智能体样本位置 $\overrightarrow{x}$ 诱导的离散经验测度为 $\mu_{\overrightarrow{x}} ≔ \frac{1}{n}\sum_{i = 1}^{n}{}\delta_{x_{i}}$。实数轴上至多包含 $k$ 个质点的离散概率测度集合记为 $\mathcal{P}_{k}\mathbb{(R)}$，即测度 $\nu \in \mathcal{P}_{k}\mathbb{(R)}$ 表达为 $\nu = \sum_{j = 1}^{k}{}\nu_{j}\delta_{y_{j}}$，其中 $\nu_{j} \geq 0$ 且 $\sum_{}^{}{}\nu_{j} = 1$。

（2）$p$ 阶与无穷 Wasserstein 距离：对任意两概率分布 $\alpha,\beta \in \mathcal{P}\mathbb{(R)}$，其 $p$ 阶 Wasserstein 距离 $W_{p}(\alpha,\beta)$（$p \in \lbrack 1, + \infty)$）与无穷 Wasserstein 距离 $W_{\infty}(\alpha,\beta)$ 分别为：

$$W_{p}(\alpha,\beta) ≔ \left( \underset{\pi \in \Pi(\alpha,\beta)}{\text{min}}\int_{\mathbb{R \times R}}^{}{}|x - y|^{p}d\pi \right)^{\frac{1}{p}}$$

$$W_{\infty}(\alpha,\beta) ≔ \underset{\pi \in \Pi(\alpha,\beta)}{\text{min}}\underset{(x,y) \in spt(\pi)}{\text{max}}|x - y|$$

（3）先验测度正则性基本假设：本文全篇设定先验测度 $\mu$ 满足三项温和假设：① $\mu$ 是绝对连续的，具有概率密度函数 $\rho_{\mu}$；② $\mu$ 的支撑集 $spt(\mu)$ 是连通区间（可以有界或无界），且在支撑集内部 $\rho_{\mu}(x) > 0$；③ 密度函数 $\rho_{\mu}$ 在支撑集上可微。这保证了分布函数 $F_{\mu}(x)$ 是严格单调且局部双射的，其反函数（分位数函数）$F_{\mu}^{\lbrack - 1\rbrack}(v)$ 在 $(0,1)$ 上处处良定。

（4）Voronoi 中点分界与极限测度：对一组给定的设施坐标 $y_{1} < y_{2} < \ldots < y_{k}$，相邻两设施的服务分界中点记为 $z_{i} ≔ \frac{y_{i} + y_{i + 1}}{2}$（其中 $z_{0} = \text{inf}spt(\mu)$，$z_{k} = \text{sup}spt(\mu)$）。在分位数向量 $\overrightarrow{v}$ 引导下，所诱导的渐近极限离散测度定义为：

$$\nu_{Q_{\overrightarrow{v}}} ≔ \sum_{i = 1}^{k}{}\left( F_{\mu}(z_{i}) - F_{\mu}(z_{i - 1}) \right)\delta_{F_{\mu}^{\lbrack - 1\rbrack}(v_{i})}$$

三、 主文核心定理、引理与推论的系统解读与实例化阐释

本节对文章第三部分与第四部分提出的全部 23 项核心理论成果（包含定理、引理与推论）进行逐一展开。遵循学术严谨与直观落地原则，对每一项理论成果均给出精准的原生公式化表述与内涵解析，并设计生动贴切的现实生活或数值算例，直观揭示其背后的经济逻辑，免除繁复的纯数学证明。

（一） 设施选址与 Wasserstein 测度投影的对偶桥梁

定理 3.1（$k$-FLP 与 Wasserstein 空间投影问题的完全等价性）

【核心结论】设 $\overrightarrow{x} = (x_{1},\ldots,x_{n})$ 为 $n$ 个智能体的上报位置向量，$\overrightarrow{y} = (y_{1},\ldots,y_{k})$ 为社会成本下 $k$-FLP 的最优选址解。则支撑集为 $\{ y_{j}\}_{j \in \lbrack k\rbrack}$ 的离散测度 $\nu^{(k,n)}$ 是经验测度 $\mu_{\overrightarrow{x}}$ 在 $k$ 点概率测度子空间 $\mathcal{P}_{k}\mathbb{(R)}$ 上的 $1$ 阶 Wasserstein 投影最优解，且最优社会成本与最小 $1$-Wasserstein 距离严格相等：

$$SC_{opt}(\overrightarrow{x}) = W_{1}(\mu_{\overrightarrow{x}},\nu^{(k,n)}) = \underset{\lambda \in \mathcal{P}_{k}\mathbb{(R)}}{\text{min}}W_{1}(\mu_{\overrightarrow{x}},\lambda)$$

反之亦然。对于最大成本，该等价性在无穷 Wasserstein 距离 $W_{\infty}$ 下成立；对于广义 $l_{p}$ 成本，该等价性在 $p$ 阶 Wasserstein 距离 $W_{p}$ 下成立。

【通俗理解】定理 3.1 首次在博弈机制设计的物理选址与纯粹数学的最优输运之间建立了坚不可摧的“直通车”。它表明：在地理线上给居民找 $k$ 个最佳公共设施落点，在数学本质上完全等同于将由全体居民构成的离散人口沙堆，用最小的“推土机移动功耗（Earth Mover's Distance）”，聚合压缩成仅由 $k$ 堆沙子构成的离散测度。

【生活实例】某长途高速公路全长 $100$ 公里，沿线有 $1000$ 辆电量耗尽的电动汽车散落各处，道路运营方需要建设 $2$ 座集中式大型充电站。寻找这两座充电站以使所有车主总拖车费用最低的决策，完全等同于在数学上寻找 $2$ 个带权重的质点（两座站各服务若干比例的车辆），使得将这 $1000$ 辆车的位置概率质量“推运”到这两座充电站的 $1$ 阶 Wasserstein 距离达到全局最小。

定理 3.2（任意选址机制成本的受限 Wasserstein 投影属性）

【核心结论】对于任意给定的 $k$ 设施选址机制 $f:\mathbb{R}^{n} \rightarrow \mathbb{R}^{k}$，其诱导的社会成本等价于经验测度 $\mu_{\overrightarrow{x}}$ 在一个支撑点位置被机制输出 $\overrightarrow{y} = f(\overrightarrow{x})$ 锁定的受限离散测度子集上的最小 $1$-Wasserstein 距离：

$$SC_{f}(\overrightarrow{x}) = \underset{\{\lambda_{j}\}_{j \in \lbrack k\rbrack}}{\text{min}}W_{1}(\mu_{\overrightarrow{x}},\lambda),其中\ \lambda = \sum_{j \in \lbrack k\rbrack}^{}{}\lambda_{j}\delta_{y_{j}}\ 且\ \overrightarrow{y} = f(\overrightarrow{x})$$

类似结论在 $W_{p}$ 与 $W_{\infty}$ 下分别对应于 $l_{p}$ 成本与最大成本。

【通俗理解】如果说定理 3.1 是“既选址又分流”的完全自由投影，那么定理 3.2 则是“落点已被机制锁死，仅允许自由优化客流分配”的受限投影。在固定落点后，每个居民理性选择最近设施，自然形成了基于 Voronoi 中点分割的最佳质量分配权重。

【生活实例】规划局出台硬性政策：无论居民如何分布，$2$ 所社区小学必须直接设在全体上报居民位置中的第 $25\backslash\%$ 位次和第 $75\backslash\%$ 位次的居民家门口。一旦这两个物理点被固定，全体居民前往就近学校所产生的平均总路程，在数学上恰好等于经验人口分布到这两个固定点组成的测度的 $1$-Wasserstein 距离（每所学校服务的人口比例即为输运计划中分配的权重）。

（二） 社会成本下分位数机制的贝叶斯渐近分析

引理 3.1（期望最优社会成本的渐近收敛性）

【核心结论】若先验分布 $\mu$ 满足一阶矩有限条件（即 $\int_{\mathbb{R}}^{}{}|x|d\mu < + \infty$），则当智能体规模 $n \rightarrow \infty$ 时，无约束最优选址的期望社会成本收敛于连续先验分布 $\mu$ 在 $\mathcal{P}_{k}\mathbb{(R)}$ 上的 $1$ 阶 Wasserstein 投影距离：

$$\underset{n \rightarrow \infty}{\text{lim}}\mathbb{E\lbrack}SC_{opt}({\overrightarrow{X}}_{n})\rbrack = W_{1}(\mu,\nu^{(k)}) ≔ \underset{\lambda \in \mathcal{P}_{k}\mathbb{(R)}}{\text{min}}W_{1}(\mu,\lambda)$$

【通俗理解】随着线段上随机散落的居民数量由几百人膨胀到数十万人，根据大数定律，随机样本的整体空间形态不可阻挡地逼近宏观人口密度分布。因此，规划者针对海量随机样本制定的完美选址，其人均最优出行成本将平滑收敛到一个确定的宏观常数。

【生活实例】在一段长 $10$ 公里的主干道上，居民独立随机分布且服从均匀分布 $U\lbrack 0,10\rbrack$。若要建 $2$ 座便民超市，无论样本是 $500$ 位还是 $50$ 万位实际住户，全知最优规划下的人均往返路程期望值，最终必定精确稳定在 $1.25$ 公里（即连续均匀分布到两个最佳测度质点的 $1$-Wasserstein 距离）。

引理 3.2（分位数机制期望社会成本的渐近收敛性）

【核心结论】设 $\overrightarrow{v} \in (0,1)^{k}$ 为不含边界 $0$ 或 $1$ 的内部正分位数向量。当 $n \rightarrow \infty$ 时，分位数机制 $\mathcal{P}\mathcal{M}_{\overrightarrow{v}}$ 的期望社会成本严格收敛于连续先验 $\mu$ 到由该分位数向量诱导的确定性离散测度 $\nu_{Q_{\overrightarrow{v}}}$ 的 $1$-Wasserstein 距离：

$$\underset{n \rightarrow \infty}{\text{lim}}\mathbb{E\lbrack}SC_{\overrightarrow{v}}({\overrightarrow{X}}_{n})\rbrack = W_{1}(\mu,\nu_{Q_{\overrightarrow{v}}})$$

【通俗理解】分位数机制选择的是样本的“经验分位数”（例如样本的第 $30\backslash\%$ 分位居民）。根据数理统计中样本分位数的强相合性与 Bahadur 表示理论，在大样本下，样本经验分位数以极快速度向真实总体的理论分位数汇聚。因此机制产生的期望成本也必然平稳收敛到理论分位数测度的输运距离。

【生活实例】市政部门采用 $(0.3,0.7)$ 分位数规则建立两座社区医院。当辖区实际入住居民达到几万人时，样本中排在第 $30\backslash\%$ 和第 $70\backslash\%$ 位的具体住户家庭坐标，与全市总体人口分布理论上的 $30\backslash\%$ 和 $70\backslash\%$ 分位点几乎分毫不差。因此，这项简单规则所实现的平均人均就医路程，高度确定地收敛至宏观理论计算值。

定理 3.3（社会成本下分位数机制贝叶斯近似比的收敛极限）

【核心结论】对于任意内部正分位数向量 $\overrightarrow{v} \in (0,1)^{k}$，其贝叶斯近似比收敛为一个严格有界的有限常数：

$$\underset{n \rightarrow \infty}{\text{lim}}B_{ar,1}^{(n)}\mathcal{(P}\mathcal{M}_{\overrightarrow{v}}) = \frac{W_{1}(\mu,\nu_{Q_{\overrightarrow{v}}})}{W_{1}(\mu,\nu^{(k)})} < + \infty$$

【通俗理解】这是全文的核心里程碑成果之一！在最坏情况分析下，恶意对手可以通过构造极端点让分位数机制的近似比变成无穷大；但在贝叶斯大样本世界里，分位数机制的平均损失永远被限制在一个确定的有限倍数之内。

【生活实例（论文例 3.1）】假设市民在 $\lbrack 0,1\rbrack$ 区间上服从均匀分布 $U\lbrack 0,1\rbrack$，规划设置 $k$ 座设施。论文计算表明，对于任意合法内部向量 $\overrightarrow{v}$，贝叶斯近似比的渐近极限绝不会超过 $4k$。例如对于 $k = 3$，即便盲目设置分位数比例，在大样本下其平均社会成本也绝对不会超过最优选址成本的 $12$ 倍——而在经典对抗理论中这个数值是 $+ \infty$！

定理 3.4（社会成本贝叶斯近似比的收敛速度与有限样本界）

【核心结论】若先验分布 $\mu$ 具有紧支撑或具有 $2 + \delta$ 阶有限矩（$\delta > 0$），则贝叶斯近似比收敛到其极限的速率严格达到 $O(n^{- 1/2})$。即存在常数 $C > 0$，对任意有限样本规模 $n > k$ 满足非渐近性能上界：

$$B_{ar,1}^{(n)}\mathcal{(P}\mathcal{M}_{\overrightarrow{v}}) \leq \frac{W_{1}(\mu,\nu_{Q_{\overrightarrow{v}}})}{W_{1}(\mu,\nu^{(k)})} + \frac{C}{\sqrt{n}}$$

【通俗理解】定理 3.4 消除了“只有无穷大样本才有保证”的学术疑虑。它给出了有限人数下的安全兜底公式：机制绩效与理论极限的偏差随着人数增加以 $1/\sqrt{n}$ 的经典统计速率衰减，保证了该机制在现实几十到几百人的中小规模群体中同样具备高度可靠性。

【生活实例】某新建大型住宅区目前仅入住了 $n = 400$ 户居民，需要选址 $2$ 所幼儿园。虽然 $400$ 并非无穷大，但根据定理 3.4，有限样本引起的扰动偏差仅约为 $C/\sqrt{400} = C/20$，即误差被压缩在很小的百分比内，政府完全可以放心按照大样本推导的分位数规则执行选址。

（三） 边界分位数（包含 0 或 1）的特殊退化与严格劣后性

定理 3.5（紧支撑下包含边界分位数的收敛性）

【核心结论】若 $\mu$ 的支撑集为有界闭区间 $\lbrack a,b\rbrack$，即便分位数向量 $\overrightarrow{v}$ 中含有 $0$ 或 $1$（如第 $1$ 个设施定在最左端居民 $v_{1} = 0$ 处），期望社会成本依然能够收敛至 $W_{1}(\mu,\nu_{Q_{\overrightarrow{v}}})$。

【通俗理解】在封闭有界的城市区域内，无论随机抽样多少人，最外侧的那名居民的位置始终被地理边界限制，大样本下最左侧居民的坐标必然收敛到城市物理边界 $a$。因此即便机制包含了极端极值点，成本依然保持收敛。

【生活实例】在一条封闭的人工岛主干道 $\lbrack 0,5km\rbrack$ 上，若规划者固执地规定：$1$ 号警务室必须设在抽样居民中最靠近西端的那户居民（$v_{1} = 0$）门前。随着岛上居民增多，最西端居民的家必然无限逼近 $0$ 公里起点，因此 $1$ 号警务室最终就稳定在起点处，全社会期望成本依然平稳收敛。

定理 3.6（紧支撑严格正密度下的快速收敛）

【核心结论】若紧支撑区间上概率密度处处大于某正下界（$\rho_{\mu}(x) \geq \delta > 0$），则即便含有边界分位数 $0$ 或 $1$，其收敛速率依然能维持 $O(n^{- 1/2})$。

【通俗理解】只要地理区间内没有任何人口空白荒漠（即人口密度处处充沛），最边缘居民向城市物理边界收敛的速度就会非常敏捷，不影响整体平方根级别的收敛稳定性。

【生活实例】在人口密集的主城区（密度处处饱满），即使采用了包含最边缘居民的分位数选址，由于边界处总是能迅速被随机居民填满，极值选址的不确定性迅速被平抑，收敛速度丝毫不受拖累。

定理 3.7（无界支撑下边界分位数的资源浪费与测度退化）

【核心结论】若先验分布的支撑集为全实数轴 $\mathbb{R}$（如正态分布），且分位数向量 $\overrightarrow{v}$ 中含有 $0$ 或 $1$。则当 $n \rightarrow \infty$ 时，位于 $0$ 或 $1$ 分位处的设施会被样本极值拖拽至 $- \infty$ 或 $+ \infty$，其有效服务质量完全蒸发。贝叶斯比依然收敛，但该设施在极限离散测度中直接退化消失，仅相当于利用剩余内部设施进行服务：

$$\underset{n \rightarrow \infty}{\text{lim}}\frac{\mathbb{E\lbrack}SC_{\overrightarrow{v}}({\overrightarrow{X}}_{n})\rbrack}{\mathbb{E\lbrack}SC_{opt}({\overrightarrow{X}}_{n})\rbrack} = \frac{W_{1}(\mu,\nu_{{\overset{\sim}{Q}}_{\overrightarrow{v}}})}{W_{1}(\mu,\nu^{(k)})}$$

【通俗理解】在无边无际的地理空间中，样本容量越大，越有可能抽样出距离中心极其遥远的极端“荒野隐居者”。如果机制承诺把一个设施建在最极端的居民家门口（$v_{1} = 0$），这个设施就会被彻底浪费在茫茫荒野中，对绝大多数居民毫无用处。

【生活实例】假设某市居民分布在全域无界平原上（服从正态分布），政府决定建 $3$ 所消防站，规则却设定为 $(0,0.5,0.85)$。当人口基数极大时，全市最西侧的那个居民可能住在距离市中心上百公里之外的深山老林。按照规则，$1$ 号消防站将被强行建在深山荒野中，导致真正发挥作用的只剩下市中心的 $2$ 号与 $3$ 号站，白白浪费了一座关键设施配额！

定理 3.8（边界分位数的严格劣后性 / 内部向量的绝对占优）

【核心结论】对于任意含有 $0$ 或 $1$ 分位数的向量 $\overrightarrow{v} \in \lbrack 0,1\rbrack^{k} \smallsetminus (0,1)^{k}$，必定存在一个纯内部正分位数向量 $\overrightarrow{w} \in (0,1)^{k}$，使得 $\overrightarrow{w}$ 诱导的极限期望成本严格更低：

$$\underset{n \rightarrow \infty}{\text{lim}}\mathbb{E\lbrack}SC_{\overrightarrow{w}}({\overrightarrow{X}}_{n})\rbrack < \underset{n \rightarrow \infty}{\text{lim}}\mathbb{E\lbrack}SC_{\overrightarrow{v}}({\overrightarrow{X}}_{n})\rbrack$$

【通俗理解】定理 3.8 给出了极其强烈的机制设计实务准则：永远不要把设施选址定在样本的最极值两端（$0\backslash\%$ 或 $100\backslash\%$ 位次）。将边界设施适度向内收拢至该区域的局部中位数，必定能在不增加任何成本的前提下大幅降低周围居民的平均总通行阻力。

【生活实例】与其把沿海公路的公交首末站死死焊在最边缘礁石上的独户灯塔看守人家门前（$v_{1} = 0$），不如将其向内陆移动 $3$ 公里设立在临海村落的中心分位点（$v_{1} = 0.05$）。这样不仅灯塔看守人多走的路程极为有限，而且整片沿海社区成百上千居民的出行成本均实现了断崖式下降。

（四） 广义 $l_{p}$ 范数与最大成本（公平性）下的分析推广

定理 3.9（$l_{p}$ 成本下贝叶斯近似比的渐近收敛性）

【核心结论】若先验测度 $\mu$ 满足 $p$ 阶矩有限条件（$\int_{\mathbb{R}}^{}{}|x|^{p}d\mu < + \infty$，$p \in (1, + \infty)$），则分位数机制在 $l_{p}$ 成本度量下的贝叶斯近似比收敛于两测度间的 $p$ 阶 Wasserstein 距离之比：

$$\underset{n \rightarrow \infty}{\text{lim}}B_{ar,p}^{(n)}\mathcal{(P}\mathcal{M}_{\overrightarrow{v}}) = \frac{W_{p}(\mu,\nu_{Q_{\overrightarrow{v}}})}{W_{p}(\mu,\nu^{(k)})}$$

【通俗理解】当社会目标函数由简单距离和转向惩罚长距离的 $l_{p}$ 范数（例如 $p = 2$ 对应的均方距离优化）时，最优输运理论中高阶 $W_{p}$ 距离的严谨性质依然能够完美护航，确保机制绩效拥有确定且可预测的宏观渐近界。

【生活实例】在物流配送规划中，为了避免出现极度偏远订单导致超时重度罚款，企业采用均方根里程（$l_{2}$ 成本）作为考核标准。定理 3.9 说明，采用固定的分位数次序派单策略，在大数据订单池下，企业的平均惩罚支出依然稳定收敛至理论 $W_{2}$ 投影比值。

定理 3.10（$l_{p}$ 成本下贝叶斯近似比的收敛速度与有限样本界）

【核心结论】若先验分布具有 $2p + \delta$ 阶有限矩（$\delta > 0$），则在 $l_{p}$ 成本下，贝叶斯近似比的收敛速度为 $O(n^{- 1/(2p)})$，有限样本满足非渐近上界：

$$B_{ar,p}^{(n)}\mathcal{(P}\mathcal{M}_{\overrightarrow{v}}) \leq \frac{W_{p}(\mu,\nu_{Q_{\overrightarrow{v}}})}{W_{p}(\mu,\nu^{(k)})} + \frac{C_{p}}{n^{\frac{1}{2p}}}$$

【通俗理解】目标函数的范数阶数 $p$ 越高，对极端扰动越敏感，其向极限收敛的统计震荡就平复得越慢。当 $p = 1$ 时收敛速率为最快的 $1/\sqrt{n}$；而当 $p = 2$ 时，收敛速率衰减为 $n^{- 1/4}$。

【生活实例】当评估指标从“平均通勤时间”（$p = 1$）切换为“通勤时间平方和”（$p = 2$）时，样本量从 $100$ 增至 $10,000$，$p = 1$ 的误差衰减为原来的 $1/10$，而 $p = 2$ 的误差仅衰减为原来的 $1/\sqrt{10} \approx 0.316$，启示管理者高阶风险防范指标需要更庞大的样本规模才能彻底稳定。

定理 3.11（紧支撑下 $l_{p}$ 成本的高阶收敛与边界性质）

【核心结论】若 $\mu$ 具有紧支撑区间且密度处处大于 $\delta > 0$，则对于任意 $l_{p}$ 成本，其收敛速度重新恢复至最快的 $O(n^{- 1/2})$ 水平。

【通俗理解】一旦物理空间有了天然的地理边界隔离，极高阶范数下的“极值发散效应”就会被空间边界彻底扼杀，从而让所有 $l_{p}$ 成本都恢复与社会成本相同的超高速率。

【生活实例】在一个被河流包围的环形开发区内，无论采用多么苛刻的加权距离不平等惩罚机制（哪怕 $p = 10$），由于最偏远员工也不可能超过开发区外墙，选址机制在样本量增加时依然能以 $1/\sqrt{n}$ 的极快速度趋近最优解。

定理 3.12（最大成本/公平目标下贝叶斯近似比的收敛性与有限样本界）

【核心结论】若 $\mu$ 具有紧支撑区间，在最大成本 $MC$ 下，分位数机制的贝叶斯近似比收敛至无穷 Wasserstein 距离之比 $\frac{W_{\infty}(\mu,\nu_{Q_{\overrightarrow{v}}})}{W_{\infty}(\mu,\nu^{(k)})}$，且收敛速度严格保持 $O(n^{- 1/2})$：

$$B_{ar,\infty}^{(n)}\mathcal{(P}\mathcal{M}_{\overrightarrow{v}}) \leq \frac{W_{\infty}(\mu,\nu_{Q_{\overrightarrow{v}}})}{W_{\infty}(\mu,\nu^{(k)})} + \frac{C}{\sqrt{n}}$$

【通俗理解】最大成本关注的是“全社会底线救助”，如急救车到达时间上限。由于关注的是极限包容性，只要地理支撑集有界，大样本下最边缘人群的距离极限受控于 $W_{\infty}$ 范数，收敛性极佳。

【生活实例】在某封闭森林景区配置 $3$ 处直升机救援降落点。游客安全规程要求：必须确保全景区内任意被困游客步行到最近降落点的最长极限距离（最大成本）尽可能小。定理 3.12 表明，使用分位数规则分配降落点，最糟糕游客的等待救援极限距离在大样本下精准收敛且可预测。

定理 3.13（最大成本下包含边界分位数机制的收敛性）

【核心结论】在紧支撑区间 $\lbrack a,b\rbrack$ 下，即便分位数向量 $\overrightarrow{v}$ 包含 $0$ 或 $1$，最大成本的贝叶斯近似比依然有界收敛，且在密度有正下界时保持 $O(n^{- 1/2})$ 速率。

【通俗理解】与社会成本不同，在追求极端公平的最大成本下，有时候把设施直接放置在城市最外围边界（$v_{1} = 0$）反而有助于阻截最边缘居民出现极端出行距离，因此边界分位数在此指标下不会导致整体崩塌。

【生活实例】沿边境公路巡逻哨所的布局中，直接把一所哨卡钉在公路的终点界桩上（$v_{k} = 1$），反而能强力封死最偏远边境居民的最大巡逻响应盲区。

（五） 最优分位数机制的构造、尺度不变性与稳健性

定理 4.1（正仿射变换下的尺度与位置不变性 / Scale-Invariance）

【核心结论】设 $X$ 为描述智能体空间分布的随机变量，${\overrightarrow{v}}_{\mu}$ 为其对应的最优分位数向量。对于任意正仿射线性变换 $X' ≔ \sigma X + m$（其中放大系数 $\sigma > 0$，平移常数 $m\mathbb{\in R}$），其诱导的全新随机变量 $X'$ 的最优分位数向量完全不变，依然严格为 ${\overrightarrow{v}}_{\mu}$。并且，任意分位数机制 $\mathcal{P}\mathcal{M}_{\overrightarrow{v}}$ 的贝叶斯近似比均与分布的真实均值 $m$ 和标准差 $\sigma$ 彻底无关！

【通俗理解】这是机制设计实务中极具穿透力的发现：分位数机制由纯序位定义，天然抵抗物理尺度的缩放与坐标原点的移动。无论你在 $100$ 米长的学校走廊上选址饮水机，还是在 $1000$ 公里长的高铁线上选址检修站；无论使用千米还是英里，无论以市中心还是以省界为坐标原点，只要人口密度的相对分布轮廓同属正态分布（或均匀分布、指数分布），最优选址比例就丝毫不变！规划者无需精确测量物理距离与人口绝对方差。

【生活实例】某国际连锁超市在评估两座城市的分店选址：A 城主干道全长 $10$ 公里，人口高度集中在中心，服从 $\mathcal{N}(5,1^{2})$；B 城主干道全长 $50$ 公里，服从 $\mathcal{N}(25,5^{2})$。两市在绝对距离、人口密度离散度上天差地别。但定理 4.1 证明，针对功利主义总路程最小化目标，两市建立 $2$ 家分店的最优分位数选址百分比完全一模一样，均应精准设在全体顾客位置的第 $25\backslash\%$ 和第 $75\backslash\%$ 分位数处！

定理 4.2（渐近最优分位数向量的构造：$(v_{\mu})_{j} = F_{\mu}(y_{j})$）

【核心结论】设 $\{ y_{j}\}_{j \in \lbrack k\rbrack}$ 为连续测度投影问题 $\underset{\lambda \in \mathcal{P}_{k}\mathbb{(R)}}{\text{min}}W_{1}(\mu,\lambda)$ 的连续最优落点解。则由先验分布累积分布函数 $F_{\mu}$ 在最优落点处取值所定义的向量 ${\overrightarrow{v}}_{\mu}$ 是社会成本下的渐近最优分位数向量：

$$(v_{\mu})_{j} = F_{\mu}(y_{j}),\forall j \in \lbrack k\rbrack$$

其诱导的机制使贝叶斯近似比渐近收敛至 $1$，即 $\underset{n \rightarrow \infty}{\text{lim}}B_{ar,1}^{(n)}\mathcal{(P}\mathcal{M}_{{\overrightarrow{v}}_{\mu}}) = 1$。广义 $l_{p}$ 成本在 $W_{p}$ 投影下同理成立。

【通俗理解】定理 4.2 彻底回答了“如何设计出理论上最完美的真实分位数机制”：先通过最优输运计算出该先验概率密度下连续最优设施应该建在哪些地理坐标 $y_{j}$，然后通过累计分布函数 $F_{\mu}$ 查出这些坐标对应的累计人口百分比，将这些百分比直接作为分位数机制的比例参数！这样设计出来的机制，既有防作弊的免货币真实性，又在大样本下完全消除了效率损失。

【生活实例】在区间 $\lbrack 0,1\rbrack$ 的均匀分布人口下建 $2$ 所小学，理论连续最优选址是 $1/4$ 和 $3/4$。由于是均匀分布，$F_{\mu}(1/4) = 0.25$，$F_{\mu}(3/4) = 0.75$。因此最优分位数向量就是 $(0.25,0.75)$。即使居民根据自身利益随时企图虚报位置，只要依据 $(0.25,0.75)$ 分位数选址，大样本下的平均就学距离与上帝视角的全局无约束最优完全无异（近似比精确逼近 $100\backslash\%$）。

定理 4.3（社会成本下最优分位数的 $k$ 元非线性方程组特征）

【核心结论】对于社会成本，最优分位数向量 ${\overrightarrow{v}}_{\mu}$ 对应的设施落点坐标 $y_{1} < y_{2} < \ldots < y_{k}$ 严格由以下由 $k$ 个局部中位数条件组成的方程组唯一确定：

$$\left\{ \begin{matrix} 2F_{\mu}(y_{1}) = F_{\mu}\left( \frac{y_{1} + y_{2}}{2} \right) & \\ 2\left( F_{\mu}(y_{i}) - F_{\mu}\left( \frac{y_{i - 1} + y_{i}}{2} \right) \right) = F_{\mu}\left( \frac{y_{i} + y_{i + 1}}{2} \right) - F_{\mu}\left( \frac{y_{i - 1} + y_{i}}{2} \right),i = 2,\ldots,k - 1 & \\ 2\left( F_{\mu}(y_{k}) - F_{\mu}\left( \frac{y_{k - 1} + y_{k}}{2} \right) \right) = 1 - F_{\mu}\left( \frac{y_{k - 1} + y_{k}}{2} \right) & \end{matrix} \right.\$$

【通俗理解】每个设施服务于其左右相邻设施之间的 Voronoi 中点分割区间。为了使区间内居民的距离总和最小，该设施必须恰好是其所服务“领地”内人口分布的“局部中位数”！方程组将原本不可解的高维博弈搜寻转化成了确定性的数值求根方程组。

【生活实例】规划 $2$ 座市政公园时，两公园分界线必定在两座公园的几何中点 $z_{1} = (y_{1} + y_{2})/2$。$1$ 号公园必须建在 $( - \infty,z_{1})$ 范围内人口的中位数位置，$2$ 号公园必须建在 $(z_{1}, + \infty)$ 范围内人口的中位数位置。解一个二元联立方程，即可秒级解出最优选址。

定理 4.4（最优分位数机制逼近绝对最优的收敛速度）

【核心结论】在最优分位数向量 ${\overrightarrow{v}}_{\mu}$ 下，社会成本与紧支撑 $l_{p}$ 成本的贝叶斯近似比以 $O(n^{- 1/2})$ 的速度向 $1$ 极速收敛：

$$B_{ar,1}^{(n)}\mathcal{(P}\mathcal{M}_{{\overrightarrow{v}}_{\mu}}) \leq 1 + \frac{C}{\sqrt{n}}$$

广义无界支撑 $l_{p}$ 成本下满足：$B_{ar,p}^{(n)}\mathcal{(P}\mathcal{M}_{{\overrightarrow{v}}_{\mu}}) \leq 1 + \frac{C_{p}}{n^{\frac{1}{2p}}}$。

【通俗理解】这给出了公共决策效率保障的最硬核量化保证：机制防范操纵的代价（即近似比超出 $1$ 的多余部分）随着参与者人数增长以 $1/\sqrt{n}$ 速度飞速蒸发。

【生活实例】在拥有 $2500$ 名选民的社区开展公共选址，近似比超出 $1$ 的潜在误差被压缩至 $C/\sqrt{2500} = C/50$。在实际政策意义上，这一福利微损与绝对理论最优已经无实质区别。

引理 4.1（紧支撑区间上最大成本投影的显式几何构型）

【核心结论】对任意支撑在紧闭区间 $\lbrack a,b\rbrack$ 上的连续概率测度 $\mu$，其在无穷 Wasserstein 空间 $W_{\infty}$ 上的投影最优解与人口密度无关，必为均匀等分点的区间中心：

$$y_{j} = a + \frac{b - a}{2k}(2j - 1),且全局最优最大成本严格恒等于\ \frac{b - a}{2k}$$

【通俗理解】当目标是极度平等（让全区走得最远的居民尽可能少走）时，最优物理落点完全取决于城市地理的绝对物理边界，与哪个地段人多、哪个地段人少彻底脱钩！必须将全区等距离切分成 $k$ 个服务半径相等的防区。

【生活实例】在一条长度 $100$ 公里的线状边防线上布置 $2$ 处雷达站，要使边防线上任意一点到最近雷达站的距离上限最小。无论边防巡逻队平常习惯扎堆在哪个哨所，两座雷达站必须且只能设在第 $25$ 公里和第 $75$ 公里处，此时最大盲区半径严格恒等于 $25$ 公里。

定理 4.5（最大成本下最优分位数向量的闭式解析公式）

【核心结论】对于任意有界区间 $\lbrack a,b\rbrack$ 上的分布 $\mu$，最大成本（公平目标）下的最优分位数向量直接拥有通用的显式闭式代数解，完全无需数值求解方程：

$$(v_{\mu})_{j} = F_{\mu}\left( a + \frac{b - a}{2k}(2j - 1) \right)$$

【通俗理解】通过结合引理 4.1 与定理 4.2，最大成本的最优分位数机制被彻底“公式化”：只需将等间距几何中心代入累积分布函数，即可一秒输出满足真实性的最优百分比配置。

【生活实例】在长 $100$ 米的美术馆长廊 $\lbrack 0,100\rbrack$ 设立 $2$ 处应急灭火器。游客游览时由于名画主要挂在后半段，人流分布函数为 $F(x) = (x/100)^{2}$。为了公平防范火灾，灭火器最佳物理位置是 $25$ 米和 $75$ 米。代入累积分布函数，管理方直接推算出最优分位数向量为 $v_{1} = (25/100)^{2} = 0.0625$（第 $6.25\backslash\%$ 位次）和 $v_{2} = (75/100)^{2} = 0.5625$（第 $56.25\backslash\%$ 位次）。

定理 4.6（最大成本下贝叶斯近似比的通用常数上界 $2k$）

【核心结论】在有界区间 $\lbrack a,b\rbrack$ 上，任意合法分位数向量 $\overrightarrow{v} \in \lbrack 0,1\rbrack^{k}$ 在最大成本下的渐近贝叶斯近似比，严格被一个仅与设施数量相关的常数 $2k$ 所封顶：

$$\underset{n \rightarrow \infty}{\text{lim}}B_{ar,\infty}^{(n)}\mathcal{(P}\mathcal{M}_{\overrightarrow{v}}) \leq 2k$$

【通俗理解】在追求极端公平的指标下，即便机制设计者缺乏数学推导能力，随意盲选了一组分位数，其期望最惨居民的出行路程在大样本下也绝对不会恶化超过最优公平距离的 $2k$ 倍，绝不会出现无法收场的灾难性选址。

【生活实例】选址 $3$ 座应急避难所，即使规划人员粗心选了一组次优的分位数比例，在数万居民参与的博弈下，全区最偏远住户前往避难所的最大距离，也绝不会超过理论极限公平距离的 $2 \times 3 = 6$ 倍。

定理 4.7（先验分布估计误差下的稳定性与鲁棒性界）

【核心结论】若规划者无法获得真实分布 $\mu$，而仅掌握其估计分布 $\overset{\sim}{\mu}$。基于近似分布 $\overset{\sim}{\mu}$ 计算出的最优分位数向量为 ${\overrightarrow{v}}_{\overset{\sim}{\mu}}$。则在真实分布 $\mu$ 下，机制的渐近效率损失被两分布间的无穷 Wasserstein 距离严格控制：

$$\underset{n \rightarrow \infty}{\text{lim}}\left. \backslash left|\frac{\mathbb{E\lbrack}SC_{{\overrightarrow{v}}_{\overset{\sim}{\mu}}}({\overrightarrow{X}}_{n})\rbrack}{\mathbb{E\lbrack}SC_{opt}({\overrightarrow{X}}_{n})\rbrack} - 1 \right.\backslash right| \leq 3\frac{W_{\infty}(\mu,\overset{\sim}{\mu})}{W_{1}(\mu,\nu^{(k)})}$$

类似结论在 $l_{p}$ 与最大成本下同样成立。在有限样本下满足：$\left| B_{ar,p}^{(n)}\mathcal{(P}\mathcal{M}_{{\overrightarrow{v}}_{\mu}}) - B_{ar,p}^{(n)}\mathcal{(P}\mathcal{M}_{{\overrightarrow{v}}_{\overset{\sim}{\mu}}}) \right| \leq 3\frac{W_{\infty}(\mu,\overset{\sim}{\mu})}{W_{p}(\mu,\nu^{(k)})} + \frac{C}{\sqrt{n}}$。

【通俗理解】定理 4.7 是最具现实政策应用价值的成果！它表明分位数机制是一套极其“皮实”、高度容错的系统。如果人口统计年鉴或问卷调查得出的数据与市民真实居住分布有一定出入，只要两者的最大分位数偏差受控，最终选址所产生的社会效率损失就严格保持在微小比例之内，不会因统计噪声而导致决策崩塌。

【生活实例】某市十年前的人口普查显示居民分布为 $\overset{\sim}{\mu}$，而当前真实人口分布为 $\mu$，两者之间的最大分位数位移为 $0.02$（即 $W_{\infty} = 0.02$）。如果城市规划者依然沿用十年前旧数据推导的最优分位数规则建校，定理 4.7 保证：全市民众如今实际平均上学路程相对于绝对最优选址的额外增加比例，绝不会超过 $3 \times 0.02/W_{1} \approx 6\backslash\%$，展现出惊人的抗调查老化稳健性！

四、 附录经典机制与经典分布命题的实例化阐释

论文附录对 $1$、$2$、$3$ 设施下经典连续分布（均匀分布、正态分布、指数分布）的最优分位数参数解进行了全景式数值求解，并对经典机制（中位数机制 med、极左机制 lt、极右机制 rt、极左极右机制 lrt）的贝叶斯性能进行了全面审视。本节对附录中的 10 项核心命题与推论进行原生公式化与实例化解析：

定理 A.1（$k = 1$ 单设施选址：中位数机制的最优性与均值差异）

【核心结论】当选址单个设施（$k = 1$）时：对于任意对称分布，无论是社会成本（$l_{1}$ 成本）还是均方成本（$l_{2}$ 成本），最优分位数向量均严格为 $\overrightarrow{v} = (0.5)$，即经典的中位数机制是绝对渐近最优的。若先验分布不对称，中位数机制对社会成本依然保持最优；但对于 $l_{2}$ 成本，最优分位数必须调整为累积分布函数在分布均值 $m$ 处的取值 $\overrightarrow{v} = (F_{\mu}(m))$。特别地，对于标准指数分布 $\mathcal{E}(1)$，$l_{2}$ 最优分位数为 $1 - e^{- 1} \approx 0.632$。

【通俗理解】绝对值误差之和的极小点位于几何中位数（$50\backslash\%$ 分位），而平方误差之和的极小点位于算术平均值。当人口偏斜分布时，追求平方惩罚的设施必须迎合长尾偏移，分位数应从 $50\backslash\%$ 调整为均值对应的百分比。

【生活实例】在一条沿海公路设立 $1$ 座垃圾回收站。若居民密集居住在西段，极少数长尾分散在东段（右偏分布，如指数分布）。若目标是让居民总走路距离最小，应将垃圾站设在西侧中位数家庭门前（第 $50\backslash\%$ 分位）；若目标是均方距离最小（重度惩罚极端远距离），垃圾站必须向东侧长尾移动，设在第 $63.2\backslash\%$ 分位的住户门前。

定理 A.2（$k = 2$ 对称分布社会成本的最优分位数恒等于 $(0.25,0.75)$）

【核心结论】若先验分布 $\mu$ 对称，在社会成本度量下，设立 $2$ 座设施的最优分位数向量必定是恒定的 $\overrightarrow{v} = (0.25,0.75)$，完全独立于具体的分布函数形态。

【通俗理解】对称性保证了两座设施以中心中位线（$50\backslash\%$ 分位）为分界线，左半区与右半区的人口各占一半。左设施应成为左半区人口的中位数（即总人口的 $25\backslash\%$ 分位），右设施应成为右半区人口的中位数（即总人口的 $75\backslash\%$ 分位）。这一结论对任何对称分布（不论是平坦的均匀分布、钟形的正态分布，还是厚尾分布）完全通用！

【生活实例】某开发区主轴线上居民呈完全轴对称分布。政府建设 $2$ 所便民菜市场以使居民平均步行距离最短，无需进行任何复杂的数学微积分积分，直接将 $1$ 号菜场定在由西向东第 $25\backslash\%$ 户居民处，$2$ 号菜场定在第 $75\backslash\%$ 户居民处，即为绝对理论最优！

定理 A.3（$k = 2$ 对称分布 $l_{2}$ 成本的最优分位数形态）

【核心结论】若 $\mu$ 对称且均值为 $m$，在 $l_{2}$ 成本下，$2$ 设施最优分位数为 $\overrightarrow{v} = (F_{\mu}(m_{-}),F_{\mu}(m_{+}))$，其中 $m_{-}$ 和 $m_{+}$ 分别为分布在中心点左侧与右侧的截断条件均值。对于标准正态分布 $\mathcal{N}(0,1)$，最优向量精确为 $(\Phi( - 1),\Phi(1)) \approx (0.16,0.84)$；对于均匀分布 $U\lbrack 0,1\rbrack$，仍为 $(0.25,0.75)$。

【通俗理解】在平方成本惩罚下，设施需要位于半区的条件均值而非条件中位数。对于正态分布，中间高两头翘的尾部拉力将条件均值向两端推移，最优分位数从 $(0.25,0.75)$ 向外张开至 $(0.16,0.84)$。

【生活实例】在正态分布的大都市配置 $2$ 座急救站，若考核指标是急救时间平方和（严防偏远猝死风险），急救站不能简单放在 $25\backslash\%$ 和 $75\backslash\%$ 分位，而必须向城市两端外扩至第 $16\backslash\%$ 和第 $84\backslash\%$ 分位的人口聚集区，更好地兼顾远端郊区的生命底线。

定理 A.4（$k = 2$ 指数分布的最优分位数解）

【核心结论】对于非对称的标准指数分布 $\mathcal{E}(1)$，两座设施的连续最优物理坐标为 $y_{1} = ln(3/2) \approx 0.405$，$y_{2} = ln(6) \approx 1.792$。代入分布函数 $F(x) = 1 - e^{- x}$，得出社会成本最优分位数向量为 ${\overrightarrow{v}}_{\mathcal{E}} = (0.33,0.83)$。而在 $l_{2}$ 成本下，最优分位数向量为 ${\overrightarrow{v}}_{\mathcal{E}} \approx (0.45,0.92)$。

【通俗理解】指数分布代表人口从市中心（$x = 0$）向外单调衰减的城市形态。由于密度随距离指数衰减，两座设施呈现出非对称的向内靠拢布局：$1$ 号设施建在第 $33\backslash\%$ 分位，$2$ 号设施建在第 $83\backslash\%$ 分位。

【生活实例】沿河而建的城镇，越靠近下游源头人口越密，向上游逐渐稀疏呈指数衰减。建设 $2$ 所图书馆时，$1$ 号图书馆应当放在第 $33\backslash\%$ 居民处（紧邻人口高密区），$2$ 号图书馆放在第 $83\backslash\%$ 居民处，完美契合了单调递减的人口梯度。

定理 A.5（$k = 3$ 对称分布的最优分位数构型）

【核心结论】若先验分布 $\mu$ 对称且均值为 $0$，在 $3$ 设施选址中，无论社会成本还是 $l_{p}$ 成本，中央设施分位数必定严格锁定在 $0.5$。两侧设施分位数关于中心对称。对于社会成本：均匀分布最优分位数约为 $(0.16,0.5,0.83)$；正态分布约为 $(0.15,0.5,0.85)$。对于 $l_{2}$ 成本：正态分布约为 $(0.17,0.5,0.83)$。

【通俗理解】$3$ 设施在对称城市下的结构极为优美：中央设施镇守 $50\backslash\%$ 核心地带，另外两座设施以完美的几何对称性分布于两侧外围。

【生活实例】在一条笔直主干道两侧对称居住的居民区建设 $3$ 座公交枢纽，$2$ 号枢纽必定直接放在整条主干道中央中位数居民处（$0.5$ 分位），$1$ 号与 $3$ 号枢纽分别放置在 $15\backslash\%$ 和 $85\backslash\%$ 位次，形成“一主两副”的高效空间服务格局。

定理 A.6（$k = 3$ 指数分布的最优分位数解）

【核心结论】对于指数分布，设立 $3$ 座设施时：社会成本下的最优分位数向量精确为 ${\overrightarrow{v}}_{\mathcal{E}} = (0.25,0.67,0.92)$；$l_{2}$ 成本下的最优分位数向量为 ${\overrightarrow{v}}_{\mathcal{E}} \approx (0.35,0.8,0.97)$。

【通俗理解】三座设施在非对称长尾分布下呈现出逐级递进梯次：前两座设施密集覆盖密集市区，第三座设施深插偏远长尾腹地，形成了梯度分层的分位数覆盖体系。

【生活实例】对依山而建梯次展开的山区带状小镇配置 $3$ 个快递取件点，社会总步行距离最优的落点百分比精确为：第 $25\backslash\%$ 户、第 $67\backslash\%$ 户与第 $92\backslash\%$ 户，确保近端不拥挤、远端不脱节。

定理 B.1（经典中位数机制 med 的贝叶斯渐近表现）

【核心结论】对于单个设施选址，经典中位数机制 med 在社会成本下在贝叶斯大样本意义下绝对最优（渐近比严格为 $1$）。但对于 $l_{2}$ 成本，其中位数选址存在结构性偏差，极限贝叶斯比满足：

$$\underset{n \rightarrow \infty}{\text{lim}}\frac{\mathbb{E\lbrack(}C_{l_{2}})_{med}({\overrightarrow{X}}_{n})\rbrack}{\mathbb{E\lbrack(}C_{l_{2}})_{opt}({\overrightarrow{X}}_{n})\rbrack} = \left( \frac{\int_{\mathbb{R}}^{}\left| x - med(\mu) \right|^{2}d\mu}{\int_{\mathbb{R}}^{}\left| x - m(\mu) \right|^{2}d\mu} \right)^{\frac{1}{2}} \leq 1 + \frac{\left| med(\mu) - m(\mu) \right|}{Var(\mu)}$$

【通俗理解】这解释了为什么中位数机制在经济学中享誉盛名：在功利主义社会成本下，它永远是 $100\backslash\%$ 满分机制；但若考核指标偏向均方距离且人口不对称，中位数机制便会出现轻微的偏离，但偏离上限被均值中位数之差与方差的比值严格锁死。

【生活实例】若某城市人口分布偏斜，中位数机制依然能完美最小化市民每天上下学的总累计公里数（社会成本 $1$-近似）；但若考核的是“最远学生的痛苦指数平方”（$l_{2}$ 成本），中位数机制选址就会略逊于均值选址，产生一个可控的微小福利折损。

推论 B.1（极左机制 lt 与极右机制 rt 的贝叶斯崩溃条件）

【核心结论】单设施极左机制 lt（始终选最左侧报告者 $x_{1}$ 为设施）的贝叶斯近似比有界，当且仅当分布有左边界 $a$。此时，社会成本极限比值为：

$$\underset{n \rightarrow \infty}{\text{lim}}\frac{\mathbb{E\lbrack}SC_{lt}({\overrightarrow{X}}_{n})\rbrack}{\mathbb{E\lbrack}SC_{opt}({\overrightarrow{X}}_{n})\rbrack} = \frac{m(\mu) - a}{\int_{a}^{\infty}\left| x - med(\mu) \right|d\mu}$$

若分布无界（如正态分布），其贝叶斯比彻底发散。对于 $\lbrack 0,1\rbrack$ 均匀分布，lt 的极限贝叶斯比严格等于 $2$（而经典最坏情况下近似比高达 $n - 1$）。

【通俗理解】极左机制是一种极度偏袒单侧的独裁机制。在全域无界空间，极左机制会随着样本增加无限漂移至负无穷，导致机制完全报废；但在有界区间内，它最多只有常数 $2$ 倍的损失，远优于最坏情况下与人数成正比的恶劣结果。

【生活实例】若规定公共汽车站必须建在沿线最西端住户门前（极左机制）：如果这是一条无界穿越戈壁的大道，随着居民增加，最西端住户可能住在几百里外，整个公交站形同虚设；但如果这是一条长 $1$ 公里的封闭社区道路，最西端永远是 $0$ 公里起点，全社区平均乘车距离仅为最优选址（$0.5$ 公里处）的 $2$ 倍。

推论 B.2（极左-极右机制 lrt 对两设施选址的有限表现）

【核心结论】极左-极右机制 lrt 将 $2$ 座设施强制放置在最左与最右两名报告者处（$x_{1},x_{n}$）。在支撑集至少单侧有界时其贝叶斯比收敛。对于均匀分布 $U\lbrack 0,1\rbrack$，其社会成本与 $l_{2}$ 成本的极限贝叶斯比均为 $2$（而在最坏情况分析下，其近似比为 $n - 2$，随人数线性爆炸）。对于指数分布，极限比约为 $2.4$。

【通俗理解】在最坏情况分析中，两个设施被锁死在两端是毁灭性的（中间居民被完全抛弃，$ar = n - 2$）；但在贝叶斯均匀分布下，两端设施自然形成了“左右包抄”之势，中间居民最远也就走 $0.25$，期望社会成本仅为最优选址的 $2$ 倍。

【生活实例】在一条规整的 $1$ 公里步行街两头（$0$ 米和 $1000$ 米处）各建一座公厕（lrt 机制）。在最坏情况下如果有几百人全挤在中间 $500$ 米处，这一机制极度糟糕；但在真实生活中顾客均匀散布在整条街上，顾客去任意一端的平均路程仅为把公厕建在 $250$ 米和 $750$ 米处的 $2$ 倍，依然具有实用的保底服务价值。

推论 B.3（经典机制在最大成本下的通用贝叶斯近似比上界 2）

【核心结论】在紧闭支撑区间 $\lbrack a,b\rbrack$ 上，经典机制 med、lt、rt 在最大成本度量下的极限贝叶斯近似比至多为 $2$；机制 lrt 在最大成本下的极限贝叶斯近似比同样至多为 $2$。

【通俗理解】追求最大公平底线时，经典极值机制和中位数机制在有界空间内天然具有自我限制能力：在最极端情况下，任何居民距离两端或中间设施的最大距离也不会超过全域跨度的一半，因此相对最优最大距离的比值永远被锁定在 $2$ 之内。

【生活实例】在一条长度 $10$ 公里的海滨跑道上设立 $1$ 处急救点，哪怕设立在最东端（极右机制）或正中央（中位数机制），跑道上任意游客突发伤病时的最远送医距离绝对不会超过 $10$ 公里（相对最优最大距离 $5$ 公里的比值严格为 $2$），绝不会出现无限制恶化。

五、 全文结论的经济学与公共管理启示总结

本篇论文不仅在纯数学工具（最优输运理论）与理论计算机科学（算法机制设计）的跨学科交叉上取得了奠基性的理论突破，更为现实世界中公共部门的设施规划、政府治理、区域协同投资以及社会公共政策制定提供了极其深刻的经济学与公共管理启示：

1. 治理哲学的重大转向：从极端防御性“最坏情况博弈”走向务实的“贝叶斯分布治理”
长久以来，理论计算机科学主导的算法机制设计深受对抗性思维影响，过度偏向极端防御性的“最坏情况分析（Worst-Case Analysis）”。在这种视角下，机制设计者被迫将全体公众假想为串通一气、不惜代价寻找算法逻辑死角来摧毁系统的“恶意超级对抗者”。这种极其悲观的哲学设定导致了毁灭性的理论死锁——多设施选址真实机制的近似比被迫判定为“无穷大（$+ \infty$）”，从而在政策实务上剥夺了规则设计的理论自信。
本研究表明：在现实公共管理中，市民的地理空间分布是由城市经济集聚、通勤网络、生态地形等客观规律塑造的，服从具备一定稳定特征的概率统计规律，绝非恶意制造的极端对抗样本。当公共部门从“假想全员恶意”转向“贝叶斯分布治理”，原本在最坏情况下彻底失效的简单真实规则，不仅近似比迅速收敛为良定常数，更能够在大样本下完全消除效率纯损（逼近 $100\backslash\%$ 绝对最优，$B_{ar} \rightarrow 1$）。这一范式转向为公共政策破除了理论虚无主义，树立了制度设计信心的基石。

2. 免货币补偿机制的制度红利：零寻租、低摩擦的高效公共决策体系
在公立学校划片、社区卫生服务中心落点、公共绿地布局等纯公共品供给中，基于庇古税、克拉克税（VCG 机制）等依赖现金转移支付的补偿机制，往往面临着严重的法律伦理制约与社会公平质疑（例如“花钱买就近入学”涉嫌教育歧视与特权垄断）。
分位数机制属于纯粹的“无货币机制（Mechanism Design without Money）”，它仅依赖参与者报告位置的次序统计量（序位排定）进行决策。由于其具备严格的占优策略真实性，任何居民虚报自身住宅位置不仅无法获得更近的选址，反而可能承受更差的服务排定。这种“按真实位次选址”的制度设计，从根本上消除了公众进行虚假陈述、游说寻租与策略性博弈的空间，极大地节约了政府开展资格审查、资产核验与事后审计的巨额行政监督摩擦成本。

3. 极低信息门槛与尺度不变性：跨区域公共规划标准化复制的管理利好
论文揭示的最优分位数向量“正仿射尺度不变性（定理 4.1）”具有非凡的实践管理价值。在传统规划认知中，不同城市由于辖区面积不同（例如大都市全长 $100$ 公里 vs. 县城全长 $5$ 公里）、人口方差各异，管理者往往认为必须针对每一个具体行政单元进行定制化的海量微观测绘与高昂的模型校准。
尺度不变性彻底打破了这一认知误区：只要不同城市人口空间分布具有相似的宏观形态特征（如均呈现中心高、边缘低的准正态单峰分布），其针对社会福利最大化的最优分位数配置比例便完全通用一致！市级乃至国家级发改与住建部门完全可以制定标准化的“分位数选址国家指南”（例如发布“双中心对称型城镇推荐采用 $25\backslash\%$ 与 $75\backslash\%$ 分位选址法”），以极低的信息收集成本在全国不同规模的下辖区域实现即插即用的制度化复用。

4. 统计调查容错与鲁棒性护航：抗击人口数据老化与抽样偏差的制度盾牌
现实中，政府决策所依赖的人口普查数据、手机信令数据或抽样调查总是存在客观误差，甚至面临数据滞后老化（如每十年一次普查）。管理者普遍担忧：基于存在偏差的先验分布设计的政策，是否会导致灾难性的选址失误？
定理 4.7 提供的鲁棒性理论界为决策者服下了“定心丸”：即便采用的先验分布与真实人口存在偏差，由此引发的渐近社会效率损失也被两分布间的最大分位数距离严格按线性常数比例封顶（上界为 $3\frac{W_{\infty}(\mu,\overset{\sim}{\mu})}{W_{p}}$），绝不会产生非线性放大或灾难性崩塌。这意味着，即使城市在微观层面经历了局部人口迁移流动，宏观分位数选址规则依然具有极强的抗干扰韧性，保障了重大公共基础设施投资生命周期内的长期稳健运转。

5. 效率（功利主义）与公平（罗尔斯主义）在空间规划中的精细化权衡范式
长期以来，公共设施投资在“追求全市平均路程最短（功利主义总效率）”与“保障最偏远郊区居民不被遗忘（罗尔斯主义底线公平）”之间充满激烈争议。论文对社会成本（SC）、广义 $l_{p}$ 成本与最大成本（MC）的统一解构，为解决该争议提供了清晰的数理坐标：
① 商业便利型与日常服务型设施（如邮筒、自提柜、公立图书馆、便民菜场）应当以社会成本为导向，依据定理 4.3 求解局部中位数方程组，最大限度压缩社会总通行能耗；
② 应急救援型与生命保障型设施（如消防站、急救中心、避难所、防空设施）必须以最大成本为核心导向，严格执行定理 4.5 导出的闭式分位数解，确保全域任意死角居民的最大等待极限达到物理最低，筑牢城市安全底线；
③ 当兼顾两者时，可设定特定 $l_{p}$ 范数，通过适度向长尾人口外扩分位数比例，实现兼顾整体出行效率与局部偏远包容性的科学平衡。

6. 自动化机制设计（AMD）的跃升：从离散组合算力黑洞走向连续微积分求解
自动化机制设计（Automated Mechanism Design）传统上依赖于高阶混合整数规划或复杂的强化学习算法，在面对多参与者、多设施的连续选址问题时，面临极其恐怖的组合维度爆炸和算力瓶颈。
本文的成功典范宣告了“最优输运几何学”在机制设计自动化上的降维打击优势：它将原本必须通过庞大离散模拟和算法黑盒搜索的最优机制构造问题，优雅地转化为可解析分析的连续 Wasserstein 投影和代数方程组求解。这为未来基于大数据与人工智能的公共政策自动化生成、区域资源智能配置算法开发开辟了极具前途的全新技术路径。

六、 规范学术参考文献

[1] Auricchio, G., & Zhang, J. (2026). Leveraging optimal transport to design optimal mechanisms for the facility location problem. ACM Transactions on Economics and Computation (TEAC), 14(3), Article 9, 1-44.

[2] Auricchio, G., & Zhang, J. (2024). The k-facility location problem via optimal transport: A Bayesian study of the percentile mechanisms. In Proceedings of the 17th Symposium on Algorithmic Game Theory (SAGT 2024), Lecture Notes in Computer Science (Vol. 14986, pp. 147-164). Springer Nature.

[3] Auricchio, G., Wang, Z., & Zhang, J. (2024). Facility location problems with capacity constraints: Two facilities and beyond. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI 2024), 2651-2659.

[4] Auricchio, G., Zhang, J., & Zhang, M. (2024). Extended ranking mechanisms for the m-capacitated facility location problem in Bayesian mechanism design. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024), 87-95.

[5] Procaccia, A. D., & Tennenholtz, M. (2013). Approximate mechanism design without money. ACM Transactions on Economics and Computation (TEAC), 1(4), Article 18, 1-26.

[6] Fotakis, D., & Tzamos, C. (2014). On the power of deterministic mechanisms for facility location games. ACM Transactions on Economics and Computation (TEAC), 2(4), Article 15, 1-37.

[7] Sui, X., Boutilier, C., & Sandholm, T. (2013). Analysis and optimization of multi-dimensional percentile mechanisms. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), 367-374.

[8] Walsh, T. (2022). Strategy proof mechanisms for facility location in Euclidean and Manhattan space. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI 2022), 527-533.

[9] Villani, C. (2009). Optimal Transport: Old and New (Grundlehren der mathematischen Wissenschaften, Vol. 338). Springer-Verlag Berlin Heidelberg.

[10] Bobkov, S., & Ledoux, M. (2019). One-Dimensional Empirical Measures, Order Statistics, and Kantorovich Transport Distances (Memoirs of the American Mathematical Society, Vol. 261, No. 1259). AMS.

[11] Santambrogio, F. (2015). Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Modeling (Progress in Nonlinear Differential Equations and Their Applications, Vol. 87). Birkhäuser.

[12] Ambrosio, L., Gigli, N., & Savaré, G. (2005). Gradient Flows: In Metric Spaces and in the Space of Probability Measures. Birkhäuser Verlag.

[13] Hartline, J. D., & Lucier, B. (2010). Bayesian algorithmic mechanism design. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), 301-310.

[14] Hartline, J. D., & Lucier, B. (2013). Bayesian mechanism design. Foundations and Trends in Theoretical Computer Science, 8(3), 143-263.

[15] Sandholm, T. (2003). Automated mechanism design: A new application area for search algorithms. In Principles and Practice of Constraint Programming (CP 2003), Lecture Notes in Computer Science (Vol. 2833, pp. 19-36). Springer.

[16] Daskalakis, C., Deckelbaum, A., & Tzamos, C. (2013). Mechanism design via optimal transport. In Proceedings of the 14th ACM Conference on Electronic Commerce (EC 2013), 269-286.

[17] Nisan, N., & Ronen, A. (1999). Algorithmic mechanism design. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC 1999), 129-140.

[18] Feigenbaum, I., Sethuraman, J., & Ye, C. (2017). Approximately optimal mechanisms for strategyproof facility location: Minimizing Lp norm of costs. Mathematics of Operations Research, 42(2), 434-447.

[19] Bahadur, R. R. (1966). A note on quantiles in large samples. The Annals of Mathematical Statistics, 37(3), 577-580.

[20] Alon, N., Feldman, M., Procaccia, A. D., & Tennenholtz, M. (2010). Strategyproof approximation of the minimax on networks. Mathematics of Operations Research, 35(3), 513-526.

[21] Black, D. (1948). On the rationale of group decision-making. Journal of Political Economy, 56(1), 23-34.

[22] Moulin, H. (1980). On strategy-proofness and single peakedness. Public Choice, 35(4), 437-455.