Selfish colorful bin packing games

Vittorio Bilò (), Francesco Cellinese (), Giovanna Melideo () and Gianpiero Monaco ()
Additional contact information
Vittorio Bilò: University of Salento
Francesco Cellinese: Gran Sasso Science Institute
Giovanna Melideo: University of L’Aquila
Gianpiero Monaco: University of L’Aquila

Journal of Combinatorial Optimization, No 0, 26 pages

Abstract: 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\ge 2$$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\ge 3$$m≥3, while they are equal to 3 when $$m=2$$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.

Keywords: Noncooperative games; Nash equilibria; Price of anarchy and stability; Selfish colorful bin packing games (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00599-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v::y::i::d:10.1007_s10878-020-00599-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00599-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().