We 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≥ 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. We adopt two standard cost sharing functions, i.e., the egalitarian and the proportional ones. Although, under both cost functions, these games do not converge in general to a (pure) Nash equilibrium, we show that Nash equilibria are guaranteed to exist. We 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≥ 3 , while they are equal to 3 when m= 2. We finally focus on the subcase of games with uniform sizes (i.e., all items have the same size). We show a tight characterization of the efficiency of Nash equilibria and design an algorithm which returns Nash equilibria with best achievable performance. All of our bounds on the price of anarchy and stability hold with respect to both their absolute and asymptotic version.

Selfish colorful bin packing games

Monaco G.
2020-01-01

Abstract

We 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≥ 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. We adopt two standard cost sharing functions, i.e., the egalitarian and the proportional ones. Although, under both cost functions, these games do not converge in general to a (pure) Nash equilibrium, we show that Nash equilibria are guaranteed to exist. We 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≥ 3 , while they are equal to 3 when m= 2. We finally focus on the subcase of games with uniform sizes (i.e., all items have the same size). We show a tight characterization of the efficiency of Nash equilibria and design an algorithm which returns Nash equilibria with best achievable performance. All of our bounds on the price of anarchy and stability hold with respect to both their absolute and asymptotic version.
File in questo prodotto:
File Dimensione Formato  
s10878-020-00599-9.pdf

Solo gestori archivio

Tipologia: PDF editoriale
Dimensione 622.13 kB
Formato Adobe PDF
622.13 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/795057
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact