WAOA 2018 Paper Abstract

TITLE: Bin Packing Games with Weight Decision: how to get a small value for the Price of Anarchy
AUTHORS: György Dósa, Hans Kellerer and Zsolt Tuza

Abstract:
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 nonnegative 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). We are interested in the Price of Anarchy (PoA), which is the limsup of NE/OPT ratios. Recently there is a growing interest in defining such games where the PoA is low.
We give a setting for the weights where the PoA is between 1.4646 and 1.5. The lower bound is valid also for the special case of the game where the weight of any item is the same as its size, and any item has size at most one half. The previous bound was about 1.46457.
We give another setting where the PoA is at most 16/11=1.4545.
This value is better than any previous one for such games.