Nov, 2019

具有容量限制的设施选址问题：算法和机制设计角度

PDF
TL;DR在一维设置中考虑设施位置问题及算法和机制设计的视角。从算法设计的角度出发，证明了相应的优化问题是 NP 难问题，但是在限制设施数量或设施容量完全相同时可以在多项式时间内计算出最优解。从机制设计的角度出发，提出一些新方法提高了策略性，并且获得了接近下限的近似保证。
facility location problemalgorithmic perspectivemechanism design perspectivestrategyproofapproximation guarantees
发现论文，激发创造
  • 候选位置设施选址博弈机制设计

    机制设计，通过策略证明机制来解决设施选址游戏，最小化代理的总成本和最大成本，并针对单设施问题和两设施问题分别证明了逼近度的下界和逼近算法。

    Oct, 2020

  • 设施定位问题的机制设计：一份调查报告

    综述了近几十年来在人工智能和经济学交叉领域中解决设施选址问题的近似机制设计研究，包括问题的各种变体和方法以及未来研究的方向。

    Jun, 2021

  • 具有缩放效应的设施选址博弈

    我们对传统的设施位置问题进行了变体研究，研究了代理人的个体成本函数与设施到代理人的距离乘以某一由设施位置决定的缩放因子的乘积；我们探讨了总成本和最大成本的最优解计算，以及在近似机制设计中代理人偏好不再是单峰时的条件并寻找了满足这些条件的缩放函数对应的策略稳定和匿名机制可达到的总成本和最大成本的近似比例。

    Feb, 2024

  • 具有入场费的设施位置

    该论文研究了设施位置博弈中的一种新模型，其中每个代理商的成本由到设施的距离和设施的进入费用组成，介绍了一些新的战略，讨论了利益共享和平等的问题以及可重塑的近似比率。

    Apr, 2022

  • 关于确定性机制在设施选址博弈中的威力

    考虑 K-Facility Location games 中的确定性策略对象机制，证明了确定性策略对象机制最佳逼近率为 n-2，并研究了在不同情况下的适用特点，如线性空间情况下存在唯一的独裁者机制，而简单情况下的策略不可能实现有界逼近率。

    Jul, 2012

  • 生产线上的设备重新分配

    研究多阶段设施重新分配问题，包括在离线和在线两种情况下算法的设计和性能证明，提出了一种可实行的策略证明机制并给出最优性证明。

    Mar, 2021

  • 具有战略客户和设施的两阶段设施选址博弈

    本论文研究了非合作设施定位博弈，其中设施和客户都是策略性的，并且对彼此产生重大影响。在这种情况下，研究者提出了一种以自私的客户为中心的自然客户行为的博弈模型，证明了其次博弈纳什均衡存在，同时简要介绍了社会最佳设施放置的计算难度和其与客户行为的相关性。

    May, 2021

  • 最小化总等待时间的客户战略设施位置

    该研究探讨了一个非合作的两侧设施定位博弈，其中设施和客户的行为是战略性的，它呈现出一个原子可分拥堵博弈的客户阶段，从而意味着原始博弈的客户均衡存在、唯一且计算有效。然而，该研究证明了该博弈的所有情况下都不存在子博弈完美均衡，并且存在子博弈完美均衡是 NP 难的。但积极的一面是，该研究提供了一个简单而有效的算法来计算 3 - 近似的子博弈完美均衡。

    Nov, 2022

  • 纳什福利与设施选址

    我们考虑了沿着一条线分布的一组代理人中设施定位的问题。我们应用了纳什福利目标函数，将个体成本转化为效用，分析了最大化纳什福利的设施位置。最后，我们从机制设计的角度提出了一种有界近似比的策略证明机制。

    Oct, 2023

  • 随机效用和路由约束下的竞争性设施选址

    研究基于竞争市场背景下的设施选址问题，采用随机实用选择模型预测客户需求。引入了路由约束，确保所选择的位置存在一个符合指定上界的旅行访问所有选定位置的路径。通过外估计近似法、子模割平面法和子回路消除法解决非线性目标函数和复杂路由约束问题，并开发了两种精确解法。同时，基于局部搜索的元启发式方法用于解决大规模实例，并与精确方法进行比较，实验证明了我们方法在解决方案质量和计算时间方面的优越性。

    Mar, 2024