1 论文原文
Paper 原文： Paper Link
Facility-location-games-with-distinct-desires
李闽溟-设施定位.pdf
2 论文关键词
2.1 Facility location game
Facility location game（设施定位博弈）
2.2 Strategyproofness
Strategyproofness（策略性）
2.3 Approximation ratio
Approximation ratio（近似因子）
2.4 Happiness
Happiness（幸福度、满意度）
2.5 注
由于读该论文的时，被各种事情打断，所以战线拉得很长，而且断断续续，所以对于同一个词的描述可能会不一致，在此标注：
agent: 智能体、个体、客户
client: 客户
game: 博弈，游戏
facility location game: 设施定位博弈，设施选址博弈
obnoxious facility game: 反设施定位博弈，讨厌的设施选址博弈
strategy-proof: 防护策略，抗策略操作
group strategy-proof: 抗群体策略操作
sp/ic 的核心就是说真话
机制上则是保证了说真话的人有好结果
即真话这种战略是经得住考验
口语一点直接叫 耐用战略好了
摘自知乎
3 摘要
3.1 摘要内容
在设施位置博弈中，所有的智能体都想离工厂越近越好（最小化与工厂的距离）
而在反设施位置博弈中，所有的智能体都想离工厂越远越好（最大化与工厂的距离）
我们旨在设计一种机制，以根据所有智能体报告的地址来确定设施位置。
在本篇论文中，主要研究在一条直线上的设施位置博弈。
根据设施位置的满意度来定义了另一个合理的智能体效用函数：幸福因子。
幸福因子的值域在 $[0, 1]$ 上，是为了度量：对于该智能体，设施的最好位置与策略给定的设施位置之间的差异。
我的理解：若策略给定的位置，处在对于该智能体最好的位置上，则幸福因子为 1，若处在对于该智能体最差的位置上，则幸福因子为 0
这个理解是正确的，在 Introduction 中可以印证
对于单个智能体来说，当然是想要最大化自己的快乐因子，但是对于整个社会满意度来说，则想要最大化所有的智能体快乐因子之和。
中位数策略（Procaccia and Tennenholtz, 2009）给出了一个近似因子为 $\frac{3}{2}$ 的近似算法。
该篇论文设计了一个近似因子为 $\frac{5}{4}$ 的团体防护策略（？？？）
然后还研究了一个该问题的变体：最大化最小快乐因子。
不可以二分吗？
不可以，博弈问题无精确解，见下文 3.2 引发的思考 中的 问题二
对于反设施位置博弈：众数策略（Cheng et al., 2011）仍然保持着最优的近似因子：2
最后，该论文设计了一种近似因子为 $\frac{4}{3}$ 的随机策略。
3.2 引发的思考
一、设施位置博弈中的满意度函数是怎样的呢？
每个个体的成本和效用仅仅是其到设施位置的距离的函数。
二、是不是原设施位置博弈已经有精确算法，可以得到精确最优解了呢？
没有，设施位置优化问题有精确算法，设施位置博弈并没有精确算法。
其之所以叫博弈，是因为每个人上报的个人位置可能不是真实的（为了让自己收益更大而说谎）
具体问题分析可见下文。
三、如果该博弈设定为，使得设施离所有智能体的距离之和最小，那么取所有智能体位置的中位数，是不是可以证明的是最优的解？
博弈无精确解（原因见问题二）
若是设施位置优化问题，中位数即为最优解。
四、如果该博弈设定为，使得设施离所有智能体的距离之和最大，那么去最左边的位置或者取最右边的位置，是不是可以证明的是最优的解？
博弈无精确解（原因见问题二）
若是反设施位置优化问题，最边上的即为最优解。
五、就算是按这种幸福因子，那当智能体的位置给定时，设施在坐标轴上任意一点的总收益都是确定的，其最优解不应该也是确定的吗？
博弈无精确解（原因见问题二）
4 Introduction
4.1 设施选址问题
4.1.1 完全透明的设施选址问题
设施定位是基本的优化问题之一，它在给定的网络上分配一个或几个设施，以便为网络中的所有客户端（智能体）提供服务，并使总成本最小化。
在上述问题中，假定客户的全部信息对于彼此来说均公开。
个人理解：
全部信息都是真实的，并且每个个体的选址位置不允许变动的情况下，该问题有精确的最优解
若是所有的选址在一条直线上，即所有位置的中位数，即为最优解
4.1.2 设施选址博弈
而在博弈中，每个客户的位置（在博弈论中的术语称为智能体(agent)）都是私有的（即不公开），这些信息在你的算法设定之前都是未知的。
机制的设计者必须首先公开算法（即设施定位的方案/机制），然后，智能体们根据该机制如何确定设施位置，来报告其在网络中的位置。
在设施位置博弈中，每个智能体都希望最小化其与设施的距离，而在反设施位置博弈中，每个智能体都希望尽可能远离设施。
因此，机制的设计者的目标是一种（strategy-proof mechanism ？？？）针对策略（最大限度的降低每个个体说谎能获得的收益？）的机制，以最大化代理的总效用（或最小化总成本）。
在之前的设施定位博弈和反设施定位博弈中，每个个体的成本和效用仅仅是其到设施位置的距离的函数。
但是对于处于不同位置的个体，其可以实现的最佳效用（或最低的成本）是不同的，即使其距离相同，其满意程度也可能不同。
例如：街道上的房屋通常具有不同的价格。那些靠近街道中心的人更容易使用附近的设施，因此价格会更高。
因此，如果一个人在街道的中心买了房子，那么如果重要的设施建在街道的尽头，他将不会很高兴（因为他在购买时已经付了很多钱）。
另一方面，如果一个人在街道的尽头以较低的价格买了房子，那么如果设施建在街道的中心，他会更快乐，尽管这两种情况下的距离是相同的。
为了反映每个个体的相对幸福感与其所能达到的最佳相对满意度，在本文中，我们介绍了每个个体的幸福因子（将在下一节中定义），该因子衡量代理对设施位置的满意度。
4.2 相关文献
机制设计的研究解决了两类问题。
One is characterizing the strategy-proof mechanisms and the other is designing strategy-proof mechanisms with good performance.
对于设施定位博弈，每个个体都希望将成本降到最低。
这个问题的第一个结果可以追溯到80年代。
Moulin characterized all the anonymous, strategy-proof and efficient mechanisms for the single-peaked preference.
Schummer 和 Vohra 研究了其他网络上所有策略防错机制（strategy-proof mechanisms）的特征。
Fotakis 和 Tzamos 描述了具有有界逼近比的策略证明机制，以最小化在直线上的2-设施定位博弈的总成本函数。
最近，Filos-Ratsikas 等人考虑了具有双峰偏好的设施定位博弈。
Procaccia and Tennenholtz 最先研究了
Approximate mechanism design without money for the facility location game
**没有钱的设施定位博弈**的近似机制设计？？？
他们提出了下述两种设施选址博弈的最佳策略证明机制，一种是最小化总成本(minSum)，另一种是最小化最大成本(minMax)。
他们还将设施选址博弈扩展到 2-设施选址博弈 和 每个个体多个地址模型。
multiple locations per agent model.
每个个体多个地址模型？？？
Lu 等人针对 maxSum 目标改进了2-设施选址博弈 和 每个个体多个地址模型 的一些结果。
在讨厌的设施选址博弈中，每个个体都想尽可能的远离设施，Ibara和Nagamochi描述了防策略机制（strategy-proof）。
在近似机制的设计方向，Cheng 等人提出并研究了使所有个体效用之和(maxSum)最大化的反设施定位博弈。
随后，Cheng等人将该模型扩展到其他网络。
最近，Zou, Li, Feigenbaum等人[考虑了这样一种模式:一些个体想要靠近设施，而另一些个体想要远离它。
Zou 等人还处理了这样一个问题：
设计者需要设置两个设施，但对相对距离有限制，个体希望靠近其中一个设施，但远离另一个设施。
Serafino 和 Ventre 讨论了每个个体更喜欢两个设施中的一个或两个都喜欢的设施选址博弈。
在该模型中，每个个体的成本是每个个体到自己喜欢的设施的距离之和，社会目标是最小化所有个体成本之和或最小化最大个体成本。
Yuan 等人研究了设施定位博弈和设施厌恶博弈中各个个体对两个不同的设施的可选偏好模型。
每个个体的成本(或效用)是他/她喜欢的设施的最小(或最大)距离。
Fong 等人提出了一种，其中每个个体对所有设施都有 fractional 偏好。
4.3 该篇文章的贡献
本文通过定义另一个合理的个体效用函数（幸福因子）来重新审视在直线网络上的设施选址博弈和讨厌的设施选址博弈。
即引入 $[0, 1]$ 内的幸福因子来度量个体的最佳设施位置与机制给出的最佳设施位置之间的差异。
对于设施选址博弈，我们首先证明了中位数选址机制，对于使所有个体的幸福因子之和最大化这一目标来说，其近似因子为 $\frac{3}{2}$。
在此基础上，我们探讨了一种更优的近似比为 $\frac{5}{4}$ 的 抗群体策略操作（group strategy-proof） 机制
此机制在只有在一个闭区间的线段网络上才能保证有效，若在开放的直线网络上，这种机制便不是 抗群体策略操作（group strategy-proof） 的策略
然后，本文证明了该博弈的下界为 $1.086$
当个体数量为 $2$ 时，作者建立了一个 $1.07$ 近似的 抗群体策略操作（group strategy-proof） 机制，而且该机制是最合理（最优的？？？）的。
最后，作者简要讨论了在所有个体中最大化最小幸福因子的变体问题。
对于讨厌的设施选址博弈，我们证明了 Cheng 等人提出的众数机制是 2-近似的，这种机制是最合理（最优的？？？）的。
最后，我们设计了一个具有 $\frac{3}{4}$ -因子的随机化策略防护机制（近似因子 $\frac{3}{4}$ 岂不是比最优解还优？？？）
4.4 本文的脉络
本文将在第 $2$ 节中正式定义这些模型
在第 $3$ 节和第 $4$ 节中，我们分别研究了设施选址博弈和讨厌的设施选址博弈。
第 $5$ 节是本文的结论。