Jul, 2012

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

PDF
TL;DR考虑 K-Facility Location games 中的确定性策略对象机制，证明了确定性策略对象机制最佳逼近率为 n-2，并研究了在不同情况下的适用特点，如线性空间情况下存在唯一的独裁者机制，而简单情况下的策略不可能实现有界逼近率。
facility location gamesdeterministic strategyproof mechanismsapproximation ratiometric spaceconnection cost
发现论文，激发创造
  • 候选位置设施选址博弈机制设计

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

    Oct, 2020

  • 设施位置机制设计的 MAC 建议

    基于预测的机制设计研究设施位置问题中的鲁棒性及其影响

    Mar, 2024

  • 随机排序法：惟一无二的无欺诈、比例公平的随机设施选址机制

    我们提出了一种叫做 “强比例” 的概念，可以用来解决设施选址问题。我们证明了一个称为随机排名机制的方法，可以在期望上满足强比例，但是没有确定性的策略证明机制可以满足该性质。最后，我们证明了在强比例的基础上，即使弱化了普遍的真实性，通过减少策略真实性可以达到更强的后验公平保证。

    May, 2022

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

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

    Feb, 2024

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

    在一维设置中考虑设施位置问题及算法和机制设计的视角。从算法设计的角度出发，证明了相应的优化问题是 NP 难问题，但是在限制设施数量或设施容量完全相同时可以在多项式时间内计算出最优解。从机制设计的角度出发，提出一些新方法提高了策略性，并且获得了接近下限的近似保证。

    Nov, 2019

  • 具有入场费的设施位置

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

    Apr, 2022

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

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

    Mar, 2021

  • 讨厌设施位置中的比例公平

    本文讨论了令人反感的设施位置问题，并提出了基于距离的比例公平概念层次结构。我们在确定性和随机机制方面考虑了这些公平公理，并计算出比例公正的定价的紧密界限。

    Jan, 2023

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

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

    May, 2021

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

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

    Jun, 2021