Selfish colorful bin packing games (Q2023116)

The authors consider selfish colorful bin packing games in which a set of items, each one controlled by a selfish player, are to be packed into a minimum number of unit capacity bins. Each item has one of \(m \geq 2\) colors and no items of the same color may be adjacent in a bin. All bins have the same unitary cost which is shared among the items it contains, so that players are interested in selecting a bin of minimum shared cost. Two standard cost sharing functions are considered: the egalitarian and the proportional ones. Under both cost functions, these games do not converge in general to a (pure) Nash equilibrium, however, they show that the Nash equilibria are guaranteed to exist. They also provide a complete characterization of the efficiency of Nash equilibria under both cost functions for general games, by showing that the prices of anarchy and stability are unbounded when \(m \geq 3\), while they are equal to \(3\) when \(m = 2\). Furthermore, they focus on the subcase of games with uniform sizes (i.e., all items have the same size): they show a tight characterization of the efficiency of Nash equilibria and design an algorithm which returns Nash equilibria with best achievable performance.