Bin Packing Games with Weight Decision: How to Get a Small Value for the Price of Anarchy

A selfish bin packing game is a variant of the classical bin packing problem in a game theoretic setting. In our model the items have not only a size but also a positive weight. The cost of a bin is 1, and this cost is shared among the items being in the bin, proportionally to their weights. A packing is a Nash equilibrium (NE) if no item can decrease its cost by moving to another bin, and OPT means a packing where the items are packed optimally (into minimum number of bins). Without any misunderstanding we denote by NE both the packing and the number of bins in the packing, and the same holds for the OPT packing. We are interested in the Price of Anarchy (PoA), which is the limsup of NE/OPT ratios. Recently there is a growing interest for games where the PoA is low.