Selfish colorful bin packing games
- PDF / 647,009 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 8 Downloads / 188 Views
Selfish colorful bin packing games Vittorio Bilò1 · Francesco Cellinese2 · Giovanna Melideo3 · Gianpiero Monaco3
© Springer Science+Business Media, LLC, part of Springer Nature 2020
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. Keywords Noncooperative games · Nash equilibria · Price of anarchy and stability · Selfish colorful bin packing games
1 Introduction A classical problem in combinatorial optimization is the one-dimensional bin packing problem, in which items with different sizes in [0, 1] have to be packed into the smallest possible number of unit capacity bins. This problem is known to be NP-hard
A preliminary version of this paper appeared in Bilò et al. (2018).
B
Gianpiero Monaco [email protected]
Extended author information available on the last page of the article
123
Journal of Combinatorial Optimization
(see Coffman et al. 1996 for a survey). The study of bin packing in a game theoretical context has been introduced in Bilò (2006). In such a setting, items are handled by selfish players and the unitary cost of each bin is shared among the items it contains. In the literature, two natural cost sharing functions have been considered: the egalitarian cost function, which equally shares the cost of a bin among the items it contains (see Dósa and Epstein 2014b; Ma et al. 2013), and the proportional cost function, where the cost of a bin is split among the items proportionally to their sizes. Namely, each player is charged with a cost according to the fraction of the used bin space her item requires (see Bilò 2006; Dosa and Epstein 2012). We stress that for games with uniform sizes, where all the items have the same size s, the two cost functions coincide. Each player would prefer to choose a strategy that minimizes her own cost, where the strategy is th
Data Loading...
