On Colorful Bin Packing Games

We consider colorful bin packing games in whichselfish players control a set of items which are to be packed intoa minimum number of unit capacity bins. Each item has one of m≥2 colors and cannot be packed next to an item of the samecolor. All bins have the same unitary cost which is shared amongthe items it contains, so that players are interested in selecting abin of minimum shared cost. We adopt two standard cost sharingfunctions: the egalitarian cost function which equally shares thecost of a bin among the items it contains, and the proportionalcost function which shares the cost of a bin among the items itcontains proportionally to their sizes. Although, under both costfunctions, colorful bin packing games do not converge in generalto a (pure) Nash equilibrium, we show that Nash equilibria areguaranteed to exist and we design an algorithm for computinga Nash equilibrium whose running time is polynomial under theegalitarian cost function and pseudo-polynomial for a constantnumber of colors under the proportional one. We also providea complete characterization of the efficiency of Nash equilibriaunder both cost functions for general games, by showing that theprices of anarchy and stability are unbounded when m≥3 while they are equal to 3 for black and white games, where m=2. Wefinally focus on games with uniform sizes (i.e., all items have thesame size) for which the two cost functions coincide. We showagain a tight characterization of the efficiency of Nash equilibriaand design an algorithm which returns Nash equilibria with bestachievable performance