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.
Selfish bin packing (SBP for short), which combines the idea of decentralization into the classic bin packing problem, has a great analogy to SBC. In SBP, there are also @math items, each of which has a size and is controlled by a selfish agent, and sufficiently many bins with identical capacities @math . The difference is that the total size of items that are packed into a bin should not exceed @math , and every nonempty bin incurs a cost of 1, which is shared among its members proportional to their sizes. This model is introduced by Bil o ( @cite_3 ). The exact @math is still unknown up to now, and the current best lower bound and upper bound are 1.6416 (by Epstein and Kleiman ( @cite_18 ), Yu and Zhang ( @cite_21 ), independently) and 1.6428 (by Epstein and Kleiman ( @cite_18 )), respectively, with a narrow gap to cover. Epstein and Kleiman also show that @math , and @math . Yu and Zhang also show that computing an NE can be done in @math time.
@cite_18 @cite_21 @cite_3
1584124593 2121115143
We study a bin packing game in which any item to be packed is handled by a selfish agent. Each agent aims at minimizing his sharing cost with the other items staying in the same bin, where the social cost is the number of bins used. We first show that computing a pure Nash equilibrium can be done in polynomial time. We then prove that the price of anarchy for the game is in between 1.6416 and 1.6575, improving the previous bounds. In the non cooperative version of the classical minimum bin packing problem, an item is charged a cost according to the percentage of the used bin space it requires. We study the game induced by the selfish behavior of the items which are interested in being packed in one of the bins so as to minimize their cost. We prove that such a game always converges to a pure Nash equilibrium starting from any initial packing of the items, estimate the number of steps needed to reach one such equilibrium, prove the hardness of computing good equilibria and give an upper and a lower bound for the price of anarchy of the game. Then, we consider a multidimensional extension of the problem in which each item can require to be packed in more than just one bin. Unfortunately, we show that in such a case the induced game may not admit a pure Nash equilibrium even under particular restrictions. The study of these games finds applications in the analysis of the bandwidth cost sharing problem in non cooperative networks.