Selfish bin covering
Copyright policy )Selfish bin covering
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 mainly concern is how much the lack of coordination harms the 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 other new equilibria. For each equilibrium, 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.
16 pages
- Chinese Academy of Science China (People's Republic of)
- Academy of Mathematics and Systems Science China (People's Republic of)
- Chinese Academy of Sciences China (People's Republic of)
- Chinese Academy of Sciences (中国科学院) China (People's Republic of)
- Chinese Academy of Science (中国科学院) China (People's Republic of)
FOS: Computer and information sciences, Selfish bin covering, price of anarchy, Weighted majority games, price of stability, Nash equilibrium, selfish bin covering, Theoretical Computer Science, Noncooperative games, Price of stability, Computer Science - Computer Science and Game Theory, Combinatorial games, weighted majority games, Price of anarchy, Computer Science(all), Computer Science and Game Theory (cs.GT)
FOS: Computer and information sciences, Selfish bin covering, price of anarchy, Weighted majority games, price of stability, Nash equilibrium, selfish bin covering, Theoretical Computer Science, Noncooperative games, Price of stability, Computer Science - Computer Science and Game Theory, Combinatorial games, weighted majority games, Price of anarchy, Computer Science(all), Computer Science and Game Theory (cs.GT)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).11 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!