设施位置机制设计的 MAC 建议
考虑 K-Facility Location games 中的确定性策略对象机制,证明了确定性策略对象机制最佳逼近率为 n-2,并研究了在不同情况下的适用特点,如线性空间情况下存在唯一的独裁者机制,而简单情况下的策略不可能实现有界逼近率。
Jul, 2012
在一维设置中考虑设施位置问题及算法和机制设计的视角。从算法设计的角度出发,证明了相应的优化问题是 NP 难问题,但是在限制设施数量或设施容量完全相同时可以在多项式时间内计算出最优解。从机制设计的角度出发,提出一些新方法提高了策略性,并且获得了接近下限的近似保证。
Nov, 2019
本文研究了度量实例的本地搜索算法,针对设备位置问题:无容量设备位置问题(UFL),以及 $k$-median,$k$-center 和 $k$-means 的无容量版本。
Sep, 2008
探讨 “移动设施位置” 问题,在公共度量空间中移动设施以减少总体成本,并使用一种基于局部搜索的近似算法,实现任意常数 ε>0 的(3+ε)- 近似度。
Jan, 2013
我们对传统的设施位置问题进行了变体研究,研究了代理人的个体成本函数与设施到代理人的距离乘以某一由设施位置决定的缩放因子的乘积;我们探讨了总成本和最大成本的最优解计算,以及在近似机制设计中代理人偏好不再是单峰时的条件并寻找了满足这些条件的缩放函数对应的策略稳定和匿名机制可达到的总成本和最大成本的近似比例。
Feb, 2024
我们提出了一种叫做 “强比例” 的概念,可以用来解决设施选址问题。我们证明了一个称为随机排名机制的方法,可以在期望上满足强比例,但是没有确定性的策略证明机制可以满足该性质。最后,我们证明了在强比例的基础上,即使弱化了普遍的真实性,通过减少策略真实性可以达到更强的后验公平保证。
May, 2022
该论文研究了设施位置博弈中的一种新模型,其中每个代理商的成本由到设施的距离和设施的进入费用组成,介绍了一些新的战略,讨论了利益共享和平等的问题以及可重塑的近似比率。
Apr, 2022