×

A bin packing game with cardinality constraints under the best cost rule. (English) Zbl 1411.91027

Summary: We consider the bin packing problem with cardinality constraints in a noncooperative game setting. In the game, there are a set of items with sizes between 0 and 1, and a number of bins each of which has a capacity of 1. Each bin can pack at most \(k\) items, for a given integer parameter \(k \geq 2\). The social cost is the number of bins used in the packing. Each item tries to be packed into one of the bins so as to minimize its cost. The selfish behaviors of the items result in some kind of equilibrium, which greatly depends on the cost rule in the game. We say a cost rule encourages sharing if for an item, compared with sharing a bin with some other items, staying in a bin alone does not decrease its cost. In this paper, we first show that for any bin packing game with cardinality constraints under an encourage-sharing cost rule, the price of anarchy of it is at least \(2 - \frac{2}{k}\). We then propose a cost rule and show that the price of anarchy of the bin packing game under the rule is \(2 - \frac{2}{k}\) when \(k \geq 7\).

MSC:

91A10 Noncooperative games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adar, R. and Epstein, L., Selfish bin packing with cardinality constraints, Theoret. Comput. Sci.495 (2013) 66-80. · Zbl 1295.91005
[2] Anshelevich, E., Dasgupta, A., Kleinberg, J. M., Tardos, E., Wexler, T. and Roughgarden, T., The price of stability for network design with fair cost allocation, SIAM J. Comput.38(4) (2008) 1602-1623. · Zbl 1173.91321
[3] Bil’o, V., On the packing of selfish items, in Proc. of the 20th Int. Parallel and Distributed Processing Symp. IPDPS (IEEE, New York, 2006), pp. 25-29.
[4] Chen, X., Nong, Q. Q. and Fang, Q. Z., An improved mechanism for selfish bin packing, Int. Conf. Combinatorial Optimization and Applications, Springer, Cham, 2017, pp. 241-257. · Zbl 1474.90248
[5] Chien, S. and Sinclair, A., Strong and pareto price of anarchy in congestion games, in Proc. of the 36th Int. Colloquium on Automata, Languages and Programming ICALP (2009), pp. 279-291. · Zbl 1248.91009
[6] Coffman, E. G., Garey, M. R. and Johnson, D. S., Approximation algorithms for bin-packing — An updated survey, in Algorithm Design for Computer System Design, eds. Ausiello, G., Lucertini, M. and Serafini, P., , Vol. 284 (Springer, Vienna, 1984), pp. 49-106.
[7] D’osa, G., The tight bound of First Fit Decreasing bin-packing algorithm is FFD \((I) \check{} 11/9\) OPT(I) + 6/9, in Proc. 1st Int. Symp. on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE), , Vol. 4614 (2007), pp. 1-11.
[8] G. D’osa and L. Epstein, Generalized selfish bin packing, CoRR, abs/1202.40809 (2012).
[9] D’osa, G. and Sgall, J., First Fit bin packing: A tight analysis, in Proc. 30th Int. Symp. on Theoretical Aspects of Computer Science STACS (Kiel, Germany, , 2013), pp. 538-549. · Zbl 1354.68118
[10] Epstein, L., Bin packing games with selfish items, in Mathematical Foundations of Computer Science, eds. Chatterjee, K. and Sgall, J., , Vol. 8087 (Springer, Berlin, Heidelberg, 2013), pp. 8-21. · Zbl 1400.91007
[11] Epstein, L. and Kleiman, E., Selfish bin packing.Algorithmica60(2) (2011) 368-394. · Zbl 1213.90211
[12] Epstein, L., Kleiman, E. and Mestre, J., Parametric packing of selfish items and the subset sum algorithm, in WINE 2009, ed. Leonardi, S., , Vol. 5929 (Springer, Heidelberg, 2009), pp. 67-78. · Zbl 1394.68440
[13] Garey, M. R., Graham, R. L., Johnson, D. S. and Yao, A. C. C., Resource constrained scheduling as generalized bin packing, J. Combin. Theory Ser. A21(3) (1976) 257-298. · Zbl 0384.90053
[14] Holzman, R. and Law-Yone, N., Strong equilibrium in congestion games, Games Econom. Behav.21(1-2) (1997) 85-101. · Zbl 0899.90169
[15] Ieong, S., McGrew, B., Nudelman, E., Shoham, Y. and Sun, Q., Fast and compact: A simple class of congestion games, in Proc. of the 20th National Conf. on Artificial Intelligence (Pittsburgh, Pennsylvania, USA, 2005), pp. 489-494.
[16] Johnson, D. S., Demers, A. J., Ullman, J. D., Garey, M. R. and Graham, R. L., Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM J. Comput.3(4) (1974) 299-325. · Zbl 0297.68028
[17] Ma, R. X., D’osa, G., Han, X., Ting, H. F., Ye, D. and Zhang, Y., A note on a selfish bin packing problem, J. Global Optim.56 (2013) 1457-1462. · Zbl 1275.90082
[18] Mavronicolas, M. and Spirakis, P. G., The price of selfish routing, Algorithmica48(1) (2007) 91-126. · Zbl 1137.91007
[19] Nash, J., Non-cooperative games, Ann. Math.54(2) (1951) 286-295. · Zbl 0045.08202
[20] Nong, Q. Q., Sun, T., Cheng, T. C. E. and Fang, Q. Z., Bin packing game with a price of anarchy of 3/2, J. Combin. Optim.2 (2017) 1-9.
[21] Roughgarden, T. and Tardos, E., How bad is selfish routing?J. ACM49(2) (2002) 236-259. · Zbl 1323.90011
[22] Tennenholtz, M. and Rozenfeld, O., Strong and correlated strong equilibria in monotone congestion games, in Proc. of the 2nd Int. Workshop on Internet and Network Economics (WINE) (Patras, Greece, 2006), pp. 74-86.
[23] J. D. Ullman, The performance of a memory allocation algorithm, Technical Report 100, Princeton University, Princeton, NJ (1971).
[24] Yu, G. and Zhang, G., Bin packing of selfish items, in Proc. of the 4th Int. Workshop on Internet and Network Economics (WINE 2008), , Vol. 5385 (Shanghai, China, 2008), pp. 446-453.
[25] Zhang, C. and Zhang, G., Cost-sharing mechanisms for selfish bin packing, Int. Conf. Combinatorial Optimization and Applications (Springer, Cham, 2017), pp. 355-368. · Zbl 1470.90043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.