On Open-End Bin Packing Games

In this paper, we study the open-end bin packing game with a proportional cost-sharing mechanism. In this context, items act as agents responsible for covering the costs associated with packing into a bin. The cost incurred by each item is calculated as the size of the item divided by the load of the bin. As self-interested and rational agents, each item will seek to switch between bins to minimize its individual cost. Given that the social cost is defined as the total number of bins utilized, we investigate whether a Nash Equilibrium exists after a limited number of deviations and assess the performance of the worst equilibrium in terms of social cost. We consider three versions of open-end bin packing game: the general open-end bin packing game, the minimum open-end bin packing game, and the maximum open-end bin packing game. We prove the existence of the pure Nash Equilibrium for all three versions, and prove the upper bound of price of Anarchy to be 2. The ratio is proved to be tight by presenting the corresponding lower bound. Furthermore, we study the performance of the price of Anarchy in the general open-end bin packing game with conflict, as well as in the general open-end bin packing game with punishment.