利用最优运输理论设计设施选址问题的最优机制

《ACM Transactions on Economics and Computation》：Leveraging Optimal Transport to Design Optimal Mechanisms for the Facility Location Problem

本文研究贝叶斯机制设计框架下的在线k-设施定位问题，分析百分位机制的极限成本比、收敛速度及贝叶斯近似比上界，提出最优机制刻画方法并评估近似分布下的损失，结果适用于社会、最大和l_p成本模型。

　　

摘要

在本文中，我们在贝叶斯机制设计框架内研究了线上的k设施选址问题，并分析了百分位数机制（一类基于代理人报告顺序来选址的真实机制）。首先，我们将k设施选址问题与Wasserstein投影问题联系起来，并利用这种联系来求解百分位数机制的预期成本与最优预期成本之间的比率极限。此外，我们还描述了该比率的极限值及其收敛速度。当n > k时，我们得出了贝叶斯近似比率的上界，这与经典的最坏情况分析结果形成了对比——在经典分析中，当k > 2时，百分位数机制的近似比率是无限的。这使我们能够制定标准，以确定哪种百分位数机制更适合处理特定的代理人分布。接着，我们证明了最优百分位数机制的存在性，并通过一组k个方程对其进行了描述。最后，我们估算了如果使用代理人分布的近似值来获取最优百分位数机制时所造成的最优性损失。所有结果均适用于社会成本、最大成本以及

_p

成本情况。