New bounds on the price of anarchy of selfish bin packing with partial punishment

The selfish bin packing with partial punishment is studied in this paper. In this problem, the utility of an item is defined as the load of the bin it is in. Each item plays the role of a selfish agent and wants to maximize its own utility. If an item with size si moves to another bin, it has to pay the partial punishment of alpha s i , where 0 < alpha < 1. We prove that the price of anarchy (PoA) of this game is at least 1.6424 for any alpha is an element of (0 , 1). In particular, the PoA of this game is at least 5/3 approximate to 1.6667 for any alpha is an element of (2/5, 1). Furthermore, we obtain a new upper bound of h (alpha) <= 31/18 approximate to 1.7222 on the PoA.