[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Selfish Vector Packing

  • Conference paper
  • First Online:
Algorithms - ESA 2015

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9294))

Abstract

We study the multidimensional vector packing problem with selfish items. An item is d-dimensional non-zero vector, whose rational components are in [0,1], and a set of items can be packed into a bin if for any 1 ≤ i ≤ d, the sum of the ith components of all items of this set does not exceed 1. Items share costs of bins proportionally to their ℓ1-norms, 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 the strong price of anarchy (and the strong price of stability) is logarithmic in d, and provide an algorithm that constructs such a packing. We also show improved and nearly tight lower and upper bounds of d + 0.657067 and d + 0.657143 respectively, on the price of anarchy, exhibiting a difference between the multidimensional problem and the one dimensional problem, for which that price of anarchy is at most 1.6428.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. Games and Economic Behavior 65(2), 289–317 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  2. Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM Journal on Computing 38(4), 1602–1623 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  3. 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 40, pp. 287–324. Princeton University Press (1959)

    Google Scholar 

  4. Aumann, Y., Dombb, Y.: Pareto efficiency and approximate Pareto efficiency in routing and load balancing games. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 66–77. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  5. Bilò, V.: On the packing of selfish items. In: Proc. of the 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), IEEE (2006)

    Google Scholar 

  6. Chekuri, C., Khanna, S.: On multidimensional packing problems. SIAM Journal on Computing 33(4), 837–851 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  7. Chien, S., Sinclair, A.: Strong and Pareto price of anarchy in congestion games. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 279–291. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  8. Coffman Jr., E.G., 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)

    Chapter  Google Scholar 

  9. Dósa, G., Epstein, L.: Generalized selfish bin packing. CoRR, abs/1202.4080 (2012)

    Google Scholar 

  10. Dubey, P.: Inefficiency of Nash equilibria. Mathematics of Operations Research 11(1), 1–8 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  11. Epstein, L., Kleiman, E.: On the quality and complexity of Pareto equilibria in the job scheduling game. In: Proc. of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), pp. 525–532 (2011)

    Google Scholar 

  12. Epstein, L., Kleiman, E.: Selfish bin packing. Algorithmica 60(2), 368–394 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  13. Epstein, L., Kleiman, E., Mestre, J.: Parametric packing of selfish items and the subset sum algorithm. In: Algorithmica, pp. 67–78 (2014), doi:10.1007/s00453-014-9942-0

    Google Scholar 

  14. Fiat, A., Kaplan, H., Levy, M., Olonetsky, S.: Strong price of anarchy for machine load balancing. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 583–594. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  16. Graham, R.L.: Bounds on multiprocessing anomalies and related packing algorithms. In: Proceedings of the 1972 Spring Joint Computer Conference, pp. 205–217 (1972)

    Google Scholar 

  17. Holzman, R., Law-Yone, N.: Strong equilibrium in congestion games. Games and Economic Behavior 21(1–2), 85–101 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  18. 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 Journal on Computing 3, 256–278 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  19. Kou, L.T., Markowsky, G.: Multidimensional bin packing algorithms. IBM Journal of Research and Development 21(5), 443–448 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  20. Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  21. Lee, S., Panigrahy, R., Prabhakaran, V., Ramasubrahmanian, V., Talwar, K., Uyeda, L., Wieder, U.: Validating heuristics for virtual machine consolidation. Microsoft Research, MSR-TR-2011-9 (2011)

    Google Scholar 

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

    Google Scholar 

  23. Ma, R., Dósa, G., Han, X., Ting, H.F., Ye, D., Zhang, Y.: A note on a selfish bin packing problem. J. Global Optimization 56(4), 1457–1462 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  24. Mavronicolas, M., Spirakis, P.G.: The price of selfish routing. Algorithmica 48(1), 91–126 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  25. Rozenfeld, O., Tennenholtz, M.: Strong and correlated strong equilibria in monotone congestion games. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol. 4286, pp. 74–86. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  26. Ye, D., Chen, J.: Non-cooperative games on multidimensional resource allocation. Future Generation Comp. Syst. 29(6), 1345–1352 (2013)

    Article  MathSciNet  Google Scholar 

  27. Yin, B., Wang, Y., Meng, L., Qiu, X.: A multi-dimensional resource allocation algorithm in cloud computing. Journal of Information & Computational Science 9(11), 3021–3028 (2012)

    Google Scholar 

  28. Yu, G., Zhang, G.: Bin packing of selfish items. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 446–453. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  29. Zhang, Q., Cheng, L., Boutaba, R.: Cloud computing: state-of-the-art and research challenges. Journal of Internet Services and Applications 1(1), 7–18 (2010)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Haifa, Haifa, Israel

    Leah Epstein

  2. Faculty of Industrial Engineering and Management, The Technion, Haifa, Israel

    Elena Kleiman

Authors
  1. Leah Epstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Elena Kleiman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Leah Epstein .

Editor information

Editors and Affiliations

  1. University of Technology, Eindhoven, The Netherlands

    Nikhil Bansal

  2. Sapienza University of Rome, Rome, Italy

    Irene Finocchi

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Epstein, L., Kleiman, E. (2015). Selfish Vector Packing. In: Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015. Lecture Notes in Computer Science(), vol 9294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48350-3_40

Download citation

  • DOI: https://doi.org/10.1007/978-3-662-48350-3_40

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-662-48349-7

  • Online ISBN: 978-3-662-48350-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation