Improving the Hk-bound on the price of stability in undirected Shapley network design games
Improving the Hk-bound on the price of stability in undirected Shapley network design games
复制标题
提高无向 Shapley 网络设计博弈稳定性价格的 Hk-bound
DOI：
10.1016/j.tcs.2014.10.037
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Matús Mihalák
中科院分区：
文献类型：
--
作者：
Y. Disser;A. Feldmann;Max Klimm;Matús Mihalák
在这篇文章中，我们证明了k个参与者的无向图上的Shapley网络设计游戏的稳定性代价至多为k3（k +1）/2− k2 1+ k3（k+ 1）/2− k2 Hk =（1− Θ（1/k4））Hk，其中Hk表示k次调和数。这提高了已知的上限H k，这也是有效的有向图，但对于这些，相反，是紧的。因此，我们给出了无向Shapley网络设计游戏的稳定性价格的第一个非平凡上界，它对任意数量的玩家都有效。我们的界限是通过分析的价格限制的纳什均衡，最大限度地减少游戏的潜在功能的稳定。我们还提出了一个游戏，其中k= 3的球员，这种限制价格的稳定性是1.634。这表明，Billehand和Bove（2011）[3]的分析是严密的。此外，我们给出了一个三个参与者的例子，它将（不受限制的）稳定价格的下限提高到1.571。
In this article we show that the price of stability of Shapley network design games on undirected graphs with k players is at most k 3 (k+ 1)/2− k 2 1+ k 3 (k+ 1)/2− k 2 H k=(1− Θ (1/k 4)) H k, where H k denotes the k-th harmonic number. This improves on the known upper bound of H k, which is also valid for directed graphs but for these, in contrast, is tight. Hence, we give the first non-trivial upper bound on the price of stability for undirected Shapley network design games that is valid for an arbitrary number of players. Our bound is proved by analyzing the price of stability restricted to Nash equilibria that minimize the potential function of the game. We also present a game with k= 3 players in which such a restricted price of stability is 1.634. This shows that the analysis of Bilò and Bove (2011)[3] is tight. In addition, we give an example for three players that improves the lower bound on the (unrestricted) price of stability to 1.571.