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

On Colorful Bin Packing Games

Gianpiero Monaco
2018-01-01

Abstract

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
2018
978-3-319-94775-4
File in questo prodotto:
File Dimensione Formato  
2018_COCOON18_OnColorfulBinPackingGames.pdf

Solo gestori archivio

Dimensione 303.05 kB
Formato Adobe PDF
303.05 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11564/795091
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact