Facility Location Problems with Capacity Constraints: Two Facilities and Beyond

本文研究了一维$m$-有容量设施选址问题($m$-CFLP)的机制设计方面。我们专注于两个框架。在第一个框架中，设施数量是任意的，所有设施的容量相同，代理人的数量等于所有设施的总容量。在第二个框架中，我们旨在放置两个设施，每个设施的容量至少为总代理人数的一半。对于这两个框架，我们提出了具有有界逼近比的诚实机制，其相对于社会成本(SC)和最大成本(MC)。当$m>2$时，这个结果与经典的$m$-设施选址问题\cite{fotakis2014power}的不可能性结果形成了鲜明对比，其中不考虑容量限制。此外，我们所有的机制都是(i)相对于MC最优的，(ii)在匿名机制中相对于SC最优或几乎最优的。对于这两个框架，我们提供了任何诚实且确定性机制相对于SC和MC可以实现的逼近比的下界。

研究$m$-Capacitated Facility Location Problem ($m$-CFLP) on a line的机制设计方面。研究两种情况：任意数量的设施，每个设施的容量相同，代理数量等于所有设施的总容量；放置两个设施，每个设施的容量至少为总代理数的一半。

提出了一种关于SC和MC的有界近似比的诚实机制，当$m>2$时，该结果与不考虑容量约束的经典$m$-Facility Location Problem的不可能结果形成鲜明对比。

所有机制都是最优的，或者在匿名机制中相对于SC最优或接近最优。对于两种情况，都提供了关于任何诚实和确定性机制相对于SC和MC所能实现的近似比的下界。

相关研究包括经典的$m$-Facility Location Problem和其他机制设计问题。