论文标题
在受互联网交换点（IXP）启发的小组编队游戏中形成更好的稳定解决方案
Forming better stable solutions in Group Formation Games inspired by Internet Exchange Points (IXPs)
论文作者
论文摘要
我们研究了一个由Internet交换点（IXP）组成的协调游戏，代理商选择加入哪些设施。加入与与您交流的其他代理商相同的设施具有好处，但不同的设施对每个代理商的成本都不同。因此，玩家希望加入与他们的“朋友”相同的设施，但是他们不想支付加入设施的费用。我们首先表明，该游戏的稳定性价格（$ pos $）最多是2，而且更一般而言，总是存在$α$ - 昂贵的平衡，最多最多是$ \ frac {2}α$ optimum。然后，我们专注于如何形成更好的稳定解决方案。如果我们允许代理商向邻居付款以防止他们偏离偏差（即，一个$ i $ $ $ $ $ $ $ $ $ $ $ j $ $ j $，以便$ j $加入相同的设施），那么我们提供了一个付款方案，该计划可以稳定解决方案，以最低的社交成本$ s^*$稳定解决方案，即POS的最低pos是1。在我们的主要技术结果中，我们可以付费求职者，以订购的效果，可以订购一台中心的工具。让$δ$表示为稳定$ s^*$，即，如果玩家将策略从$ s^*$中的策略更改为策略，则需要支付给玩家的付款总额。我们证明，$δ$和稳定价格之间存在权衡：$ \fracδ{copt（s^*）} \ le 1 - \ frac {2} {5} {5} pos $。因此，当没有良好的稳定解决方案时，只需要少量额外付款即可稳定$ s^*$；而且，当已经存在良好的稳定解决方案（即$ pos $很小）时，我们应该对这些解决方案感到满意。最后，我们考虑找到最佳解决方案$ s^*$的计算复杂性，并设计一个多项式时间$ o（\ log n）$近似算法，以解决此问题。
We study a coordination game motivated by the formation of Internet Exchange Points (IXPs), in which agents choose which facilities to join. Joining the same facility as other agents you communicate with has benefits, but different facilities have different costs for each agent. Thus, the players wish to join the same facilities as their "friends", but this is balanced by them not wanting to pay the cost of joining a facility. We first show that the Price of Stability ($PoS$) of this game is at most 2, and more generally there always exists an $α$-approximate equilibrium with cost at most $\frac{2}α$ of optimum. We then focus on how better stable solutions can be formed. If we allow agents to pay their neighbors to prevent them from deviating (i.e., a player $i$ voluntarily pays another player $j$ so that $j$ joins the same facility), then we provide a payment scheme which stabilizes the solution with minimum social cost $s^*$, i.e. PoS is 1. In our main technical result, we consider how much a central coordinator would have to pay the players in order to form good stable solutions. Let $Δ$ denote the total amount of payments needed to be paid to the players in order to stabilize $s^*$, i.e., these are payments that a player would lose if they changed their strategy from the one in $s^*$. We prove that there is a tradeoff between $Δ$ and the Price of Stability: $\fracΔ{cost(s^*)} \le 1 - \frac{2}{5} PoS$. Thus when there are no good stable solutions, only a small amount of extra payment is needed to stabilize $s^*$; and when good stable solutions already exist (i.e., $PoS$ is small), then we should be happy with those solutions instead. Finally, we consider the computational complexity of finding the optimum solution $s^*$, and design a polynomial time $O(\log n)$ approximation algorithm for this problem.
