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\) 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\), 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Indeed, it is possible to lower the computational complexity of the algorithm by considering only the \(n^2\) pairs \((c^*,k^*)\) by noting that the algorithm used within observation (ii) can be easily adapted to deal with the case in which |B| is not known.
References
Adar R, Epstein L (2013) Selfish bin packing with cardinality constraints. Theor Comput Sci 495:66–80
Balogh J, Békési J, Dósa G, Epstein L, Kellerer H, Levin A, Tuza Z (2015a) Offline black and white bin packing. Theor Comput Sci 596:92–101
Balogh J, Békési J, Dósa G, Epstein L, Kellerer H, Tuza Z (2015b) Online results for black and white bin packing. Theory Comput Syst 56(1):137–155
Bilò V (2006) On the packing of selfish items. In: The 20th international parallel and distributed processing symposium (IPDPS). IEEE
Bilò V, Cellinese F, Melideo G, Monaco G (2018) On colorful bin packing games. In: 24th international conference on computing and combinatorics (COCOON), pp 280–292
Böhm M, Sgall J, Veselỳ P (2014) Online colored bin packing. In: International workshop on approximation and online algorithms (WAOA). Springer, Berlin, pp 35–46
Böhm M, Dósa G, Epstein L, Sgall J, Veselỳ P (2018) Colored bin packing: online algorithms and lower bounds. Algorithmica 80(1):155–184
Cao Z, Yang X (2011) Selfish bin covering. Theor Comput Sci 412(50):7049–7058
Coffman E Jr, Garey M, Johnson D (1996) Approximation algorithms for bin packing: a survey. In: Approximation algorithms for NP-hard problems. PWS Publishing Company, Boston, pp 46–93
Dosa G, Epstein L (2012) Generalized selfish bin packing. arXiv preprint arXiv:1202.4080
Dósa, G, Epstein L (2014a). Colorful bin packing. In: Scandinavian workshop on algorithm theory (SWAT). Springer, Berlin, pp 170–181
Dósa, G, Epstein, L (2014b) The convergence time for selfish bin packing. In: International symposium on algorithmic game theory (SAGT). Springer, Berlin, pp 37–48
Dósa G, Epstein L (2019) A new lower bound on the price of anarchy of selfish bin packing. Inf Process Lett 150:6–12
Epstein L (2013) Bin packing games with selfish items. In: International symposium on mathematical foundations of computer science (MFCS). Springer, Berlin, pp 8–21
Epstein L, Kleiman E (2011) Selfish bin packing. Algorithmica 60(2):368–394
Epstein L, Kleiman E (2015) Selfish vector packing. In: The 23rd European symposium on algorithms (ESA). Springer, Berlin, pp 471–482
Epstein L, Krumke SO, Levin A, Sperber H (2011) Selfish bin coloring. J Comb Optim 22(4):531–548
Faigle U, Kern W (1998) Approximate core allocation for binpacking games. SIAM J Discrete Math 11(3):387–399
Fernandes CG, Ferreira CE, Miyazawa FK, Wakabayashi Y (2011) Selfish square packing. Electron Notes Discrete Math 37:369–374
Krumke SO, de Paepe WE, Rambau J, Stougie L (2008) Bincoloring. Theor Comput Sci 407(1–3):231–241
Ma R, Dósa G, Han X, Ting H-F, Ye D, Zhang Y (2013) A note on a selfish bin packing problem. J Global Optim 56(4):1457–1462
Qiu X, Kern W (2016) Approximate core allocations and integrality gap for the bin packing game. Theor Comput Sci 627:26–35
Yu G, Zhang G (2008) Bin packing of selfish items. In: International workshop on internet and network economics (WINE). Springer, Berlin, pp 446–453
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
A preliminary version of this paper appeared in Bilò et al. (2018).
Rights and permissions
About this article
Cite this article
Bilò, V., Cellinese, F., Melideo, G. et al. Selfish colorful bin packing games. J Comb Optim 40, 610–635 (2020). https://doi.org/10.1007/s10878-020-00599-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-020-00599-9