Cost-Sharing Mechanisms for the Selfish Open-End Bin Packing Problem

In this paper, we study games modeled after the open-end bin packing problem, where each bin has a unit cost, and each item can be viewed as a player whose goal is to choose a bin that can be accessed to minimize the cost they need to share the cost. We mainly study the cost-sharing mechanism for the maximum open-end bin packing (Max-OEBP) problem and the minimum open-end bin packing (Min-OEBP) problem. We give two lower bounds of PoA for any cost-sharing mechanism, assuming that each item lies in \(\left[ \frac{1}{m},1\right] \) . Further we apply the LSB cost-sharing mechanism to both open-end bin packing models. We prove that PoA does not exceed 2 and PoS equals to 1 under the Max-OEBP model, and PoA does not exceed 4 and PoS does not exceed \(\frac{71}{60}\) under the Min-OEBP model. We also show that the packing scheme output by the FFD algorithm is a Nash equilibrium under both models, which implies that we can output a stable packing scheme in polynomial time under this mechanism.