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 \(s_i\) $s_i$ moves to another bin, it has to pay the partial punishment of \(\alpha s_{i}\) $\alpha s_i$ , where \(0<\alpha <1\) $0<\alpha <1$ . We prove that the price of anarchy (PoA) of this game is at least 1.6424 for any \(\alpha \in (0,1)\) $\alpha \in (0,1)$ . In particular, the PoA of this game is at least \(5/3 \approx 1.6667\) $5/3\approx 1.6667$ for any \(\alpha \in (\frac{2}{5},1)\) $\alpha \in (\frac{2}{5},1)$ . Furthermore, we obtain a new upper bound of \(h(\alpha ) \le 31/18 \approx 1.7222\) $h(\alpha )\le 31/18\approx 1.7222$ on the PoA.