Abstract
We study the multidimensional vector packing problem with selfish items. An item is a d-dimensional non-zero vector, whose rational components are in [0, 1]. A set of items can be packed into a bin if for every \(1 \le i \le d\), the sum of the ith components of all items of this set does not exceed 1. Items share costs of bins proportionally to the \(\ell _1\)-norms of items, and each item corresponds to a selfish player in the sense that it prefers to be packed into a bin minimizing its resulting cost. This defines a class of games called vector packing games. We show that any game in this class has a packing that is a strong equilibrium, and that both the strong price of anarchy and the strong price of stability are logarithmic in d. We also provide an algorithm that constructs a packing that is a strong equilibrium. Furthermore, we show improved and nearly tight lower and upper bounds of \(d+0.657067\) and \(d+0.657143\), respectively, for any \(d\ge 2\), on the price of anarchy. This exhibits a difference between the multidimensional problem and the one-dimensional problem, for which that price of anarchy is at most 1.6428.
Similar content being viewed by others
Notes
This result can be generalized for \(d\ge 2\) by adding \(d-1\) zero components to each item in the instance.
References
Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. Games Econ. Behav. 65(2), 289–317 (2009)
Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008)
Aumann, R.J.: Acceptable points in general cooperative \(n\)-person games. In: Tucker, A.W., Luce, R.D. (eds.) Contributions to the Theory of Games IV, Annals of Mathematics Study, vol. 40, pp. 287–324. Princeton University Press, Princeton (1959)
Aumann, Y., Dombb, Y.: Pareto efficiency and approximate Pareto efficiency in routing and load balancing games. In: Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT2010), pp. 66–77 (2010)
Bilò, V.: On the packing of selfish items. In: Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS2006). IEEE (2006)
Chekuri, C., Khanna, S.: On multidimensional packing problems. SIAM J. Comput. 33(4), 837–851 (2004)
Chien, S., Sinclair, A.: Strong and Pareto price of anarchy in congestion games. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP2009), pp. 279–291 (2009)
Coffman, E.G., Jr., Csirik, J., Galambos, G., Martello, S., Vigo, D.: Bin packing approximation algorithms: survey and classification. In: Pardalos, P.M., Du, D.Z., Graham, R.L.L. (eds.) Handbook of Combinatorial Optimization, pp. 455–531. Springer, New York (2013)
Dósa, G., Epstein, L.: Generalized selfish bin packing (2012). CoRR, arXiv:1202.4080
Dósa, G., Epstein, L.: The convergence time for selfish bin packing. Acta Cybern. 23(3), 853–865 (2018)
Dósa, G., Epstein, L.: A new lower bound on the price of anarchy of selfish bin packing. Inf. Process. Lett. 150, 6–12 (2019)
Dósa, G., Epstein, L.: Pareto optimal equilibria for selfish bin packing with uniform cost sharing. J. Comb. Optim. 37(3), 827–847 (2019)
Dósa, G., Epstein, L.: Quality of strong equilibria for selfish bin packing with uniform cost sharing. J. Sched. 22(4), 473–485 (2019)
Dósa, G., Epstein, L.: Quality of equilibria for selfish bin packing with cost sharing variants. Discrete Optim. 38, 100556 (2020)
Dósa, G., Kellerer, H., Tuza, Z.: Using weight decision for decreasing the price of anarchy in selfish bin packing games. Eur. J. Oper. Res. 278(1), 160–169 (2019)
Dubey, P.: Inefficiency of Nash equilibria. Math. Oper. Res. 11(1), 1–8 (1986)
Epstein, L., Kleiman, E.: Selfish bin packing. In: Proceedings of the 16th Annual European Symposium (ESA2008), pp. 368–380 (2008)
Epstein, L., Kleiman, E.: On the quality and complexity of Pareto equilibria in the job scheduling game. In: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS2011), pp. 525–532 (2011)
Epstein, L., Kleiman, E.: Selfish bin packing. Algorithmica 60(2), 368–394 (2011)
Epstein, L., Kleiman, E.: Selfish vector packing. In: Proceedinngs of the 23rd Annual European Symposium on Algorithms (ESA2015), pp. 471–482 (2015)
Epstein, L., Kleiman, E., Mestre, J.: Parametric packing of selfish items and the Subset Sum algorithm. Algorithmica 74(1), 177–207 (2016)
Fiat, A., Kaplan, H., Levy, M., Olonetsky, S.: Strong price of anarchy for machine load balancing. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP2007), pp. 583–594 (2007)
Garey, M.R., Graham, R.L., Johnson, D.S.: Resource constrained scheduling as generalized bin packing. J. Comb. Theory Ser. A 21(3), 257–298 (1976)
Graham, R.L.: Bounds on multiprocessing anomalies and related packing algorithms. In: Proceedings of the 1972 Spring Joint Computer Conference, pp. 205–217 (1972)
Holzman, R., Law-Yone, N.: Strong equilibrium in congestion games. Games Econ. Behav. 21(1–2), 85–101 (1997)
Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 256–278 (1974)
Kou, L.T., Markowsky, G.: Multidimensional bin packing algorithms. IBM J. Res. Dev. 21(5), 443–448 (1977)
Koutsoupias, E., Papadimitriou, C.H. Worst-case equilibria. In: Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS1999), pp. 404–413 (1999)
Lee, S., Panigrahy, R., Prabhakaran, V., Ramasubrahmanian, V., Talwar, K., Uyeda, L., Wieder, U.: Validating heuristics for virtual machine consolidation. In: Microsoft Research, MSR-TR-2011-9 (2011)
Luc, D.T.: Pareto optimality. In: Chinchuluun, A., Pardalos, P.M., Migdalas, A., Pitsoulis, L. (eds.) Pareto Optimality, Game Theory and Equilibria, pp. 481–515. Springer, Berlin (2008)
Ma, R., Dósa, G., Han, X., Ting, H.F., Ye, D., Zhang, Y.: A note on a selfish bin packing problem. J. Glob. Optim. 56(4), 1457–1462 (2013)
Mavronicolas, M., Spirakis, P.G.: The price of selfish routing. Algorithmica 48(1), 91–126 (2007)
Tennenholtz, M., Rozenfeld, O.: Strong and correlated strong equilibria in monotone congestion games. In: Proceedings of the 2nd International Workshop on Internet and Network Economics (WINE2006), pp. 74–86 (2006)
Wang, Z., Han, X., Dósa, G., Tuza, Z.: A general bin packing game: interest taken into account. Algorithmica 80(5), 1534–1555 (2018)
Ye, D., Chen, J.: Non-cooperative games on multidimensional resource allocation. Future Gener. Comput. Syst. 29(6), 1345–1352 (2013)
Yin, B., Wang, Y., Meng, L., Qiu, X.: A multi-dimensional resource allocation algorithm in cloud computing. J. Inf. Comput. Sci. 9(11), 3021–3028 (2012)
Yu, G., Zhang, G.: Bin packing of selfish items. In: The 4th International Workshop on Internet and Network Economics (WINE2008), pp. 446–453 (2008)
Zhang, Q., Cheng, L., Boutaba, R.: Cloud computing: state-of-the-art and research challenges. J. Internet Serv. Appl. 1(1), 7–18 (2010)
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 as [20].
Rights and permissions
About this article
Cite this article
Epstein, L., Kleiman, E. Selfish Vector Packing. Algorithmica 83, 2952–2988 (2021). https://doi.org/10.1007/s00453-021-00849-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-021-00849-0