Selfish Square Packing

We consider a game-theoretical bin packing problem. The 1D (one dimensional) case has been treated in the literature as the ʼselfish bin packing problemʼ. We investigate a 2D version, in which the items to be packed are squares and the bins are unit squares. In this game, a set of items is packed into bins. Each player controls exactly one item and is charged with a cost defined as the ratio between the area of the item and the occupied area of the respective bin. One at a time, players selfishly move their items from one bin to another, in order to minimize the costs they are charged. At a Nash equilibrium, no player can reduce the cost he is charged by moving his item to a different bin. In the 2D case, to decide whether an item can be placed in another bin with other items is NP-complete, so we consider that players use a packing algorithm to make this decision. We show that this game converges to a Nash equilibrium, independently of the packing algorithm used. We prove that the price of anarchy is at least 2.27. We also prove that, using the NFDH packing algorithm, the asymptotic price of anarchy is at most 2.6875.