Selfish bin covering
Selfish bin covering
复制标题
DOI：
10.1016/j.tcs.2011.09.017
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
Zhigang Cao;Xiaoguang Yang
中科院分区：
文献类型：
--
作者：
Zhigang Cao;Xiaoguang Yang
在这篇文章中，我们讨论了自私的箱子覆盖问题，它与箱子覆盖问题和加权多数对策有很大的关系。我们主要关心的是，缺乏中央协调对社会福利的损害有多大。除了基于纳什均衡的标准POA和POS外，我们还考虑了强纳什均衡，以及几个新的均衡概念。对于每个均衡概念，给出了相应的POA和POS，并考虑了计算任意均衡以及逼近最佳均衡的问题。
In this paper, we address the selfish bin covering problem, which is greatly related both to the bin covering problem, and to the weighted majority game. What we are mainly concerned with is how much the lack of central coordination harms social welfare. Besides the standard PoA and PoS, which are based on Nash equilibrium, we also take into account the strong Nash equilibrium, and several new equilibrium concepts. For each equilibrium concept, the corresponding PoA and PoS are given, and the problems of computing an arbitrary equilibrium, as well as approximating the best one, are also considered.