具有缩放效应的设施选址博弈
内容提要
本文综述设施选址博弈的机制设计研究，涵盖策略证明机制、成本最小化、公平公理、多阶段重分配及在线算法。研究给出单设施与两设施问题的逼近度下界并提出近似算法，分析一维及任意度量空间中的NP难性与多项式可解情形，探讨设施与客户均策略性时纳什均衡的存在性、唯一性及计算复杂性，并提出3-近似子博弈完美均衡算法。
延伸解读
研究脉络与核心问题
本文综述了设施选址博弈的机制设计研究，核心问题包括策略证明机制、成本最小化（总成本和最大成本）、公平公理、多阶段重分配及在线算法。研究覆盖单设施与两设施问题，给出逼近度下界和近似算法，并分析一维及任意度量空间中的NP难性与多项式可解情形。
策略性与均衡分析
当设施与客户均策略性时，研究探讨了纳什均衡的存在性、唯一性及计算复杂性。例如，在非合作两侧设施定位博弈中，客户均衡存在、唯一且可高效计算，但子博弈完美均衡可能不存在且判定为NP难，不过存在3-近似子博弈完美均衡算法。
公平与多阶段扩展
公平性方面，研究提出基于距离的比例公平概念层次结构，并计算比例公正定价的紧界。多阶段设施重新分配问题涵盖离线和在线场景，设计了可实行的策略证明机制并给出最优性证明，同时在线算法也得到探讨。
Q&A
设施选址博弈的机制设计主要研究哪些问题？
主要研究策略证明机制、成本最小化（包括总成本和最大成本）、公平公理、多阶段重分配以及在线算法等。
单设施和两设施选址问题的近似算法有哪些成果？
针对单设施和两设施问题，分别证明了逼近度的下界，并提出了相应的近似算法。
一维设施选址问题的计算复杂性如何？
在一维设置中，优化问题是NP难的，但当设施数量受限或设施容量完全相同时，可以在多项式时间内计算出最优解。
当设施和客户都是策略性时，纳什均衡存在吗？
存在。研究证明客户子博弈纳什均衡存在、唯一且可计算，但子博弈完美均衡不一定存在，且判断其存在性是NP难的。
如何计算设施选址博弈的近似子博弈完美均衡？
研究提供了一种简单有效的算法来计算3-近似的子博弈完美均衡。
设施选址博弈中有哪些公平公理？
提出了基于距离的比例公平概念层次结构，并在确定性和随机机制中考虑了这些公平公理，计算了比例公正定价的紧密界限。
