Selfish bin coloring

Leah Epstein (), Sven O. Krumke (), Asaf Levin () and Heike Sperber ()
Additional contact information
Leah Epstein: University of Haifa
Sven O. Krumke: University of Kaiserslautern
Asaf Levin: The Technion
Heike Sperber: University of Kaiserslautern

Journal of Combinatorial Optimization, 2011, vol. 22, issue 4, No 5, 548 pages

Abstract: Abstract The bin packing problem, a classical problem in combinatorial optimization, has recently been studied from the viewpoint of algorithmic game theory. In this bin packing game each item is controlled by a selfish player minimizing its personal cost, which in this context is defined as the relative contribution of the size of the item to the total load in the bin. We introduce a related game, the so-called bin coloring game, in which players control colored items and each player aims at packing its item into a bin with as few different colors as possible. We establish existence of Nash and strong as well as weakly and strictly Pareto optimal equilibria in these games in the cases of capacitated and uncapacitated bins. For both kinds of games we determine the prices of anarchy and stability concerning those four equilibrium concepts. Furthermore, we show that extreme Nash equilibria, representatives of the set of Nash equilibria with minimal or maximal number of colors in a bin, can be found in time polynomial in the number of items for the uncapacitated case.

Keywords: Algorithmic game theory; Bin coloring; Nash equilibria; Strong equilibria; Weakly/Strictly Pareto optimal Nash equilibria; Price of anarchy; Price of stability; Extreme Nash equilibria (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9302-1 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:22:y:2011:i:4:d:10.1007_s10878-010-9302-1

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

DOI: 10.1007/s10878-010-9302-1

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 ().