Skip to main content
Log in

Abstract

Following recent interest in the study of computer science problems in a game theoretic setting, we consider the well known bin packing problem where the items are controlled by selfish agents. Each agent is charged with a cost according to the fraction of the used bin space its item requires. That is, the cost of the bin is split among the agents, proportionally to their sizes. Thus, the selfish agents prefer their items to be packed in a bin that is as full as possible. The social goal is to minimize the number of the bins used. The social cost in this case is therefore the number of bins used in the packing.

A pure Nash equilibrium is a packing where no agent can obtain a smaller cost by unilaterally moving his item to a different bin, while other items remain in their original positions. A Strong Nash equilibrium is a packing where there exists no subset of agents, all agents in which can profit from jointly moving their items to different bins. We say that all agents in a subset profit from moving their items to different bins if all of them have a strictly smaller cost as a result of moving, while the other items remain in their positions.

We measure the quality of the equilibria using the standard measures PoA and PoS that are defined as the worst case worst/best asymptotic ratio between the social cost of a (pure) Nash equilibrium and the cost of an optimal packing, respectively. We also consider the recently introduced measures SPoA and SPoS, that are defined similarly to the PoA and the PoS, but consider only Strong Nash equilibria.

We give nearly tight lower and upper bounds of 1.6416 and 1.6428, respectively, on the PoA of the bin packing game, improving upon previous result by Bilò. We study the Strong Nash equilibria of the bin packing game, and show that a packing is a Strong Nash equilibrium iff it is produced by the Subset Sum algorithm for bin packing. This characterization implies that the SPoA of the bin packing game equals the approximation ratio of the Subset Sum algorithm, for which an almost tight bound is known. Moreover, the fact that any lower bound instance for the Subset Sum algorithm can be converted by a small modification of the item sizes to a lower bound instance on the SPoS, implies that in the bin packing game SPoA=SPoS. Finally, we address the issue of complexity of computing a Strong Nash packing and show that no polynomial time algorithm exists for finding Strong Nash equilibria, unless P=NP.

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

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

References

  1. Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. In: Proc. of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pp. 189–198 (2007)

  2. Anshelevich, E., Dasgupta, A., Tardos, É., Wexler, T.: Near-optimal network design with selfish agents. In: Proc. of the 35th Annual ACM Symposium on Theory of Computing, STOC 2003, pp. 511–520 (2003)

  3. Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: Proc. of the 45th Symposium on Foundations of Computer Science FOCS 2004, pp. 295–304 (2004)

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

    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, New York (2006)

    Google Scholar 

  6. Caprara, A., Pferschy, U.: Worst-case analysis of the subset sum algorithm for bin packing. Oper. Res. Lett. 32(2), 159–166 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  7. Coffman, E. Jr., Csirik, J.: Performance guarantees for one-dimensional bin packing. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics, Chap. 32. pp. 1–18. Chapman & Hall, London (2007)

    Google Scholar 

  8. Coffman, E. Jr., Garey, M., Johnson, D.: Approximation algorithms for bin-packing: an updated survey. In: Ausiello, G., Lucertini, M., Serafini, P. (eds.) Algorithm Design for Computer Systems Design. Springer, New York (1984)

    Google Scholar 

  9. Coffman, E Jr., Galambos, G., Martello, S., Vigo, D.: Bin packing approximation algorithms: combinatorial analysis. In: Handbook of Combinatorial Optimization. Kluwer Academic, Amsterdam (1998)

    Google Scholar 

  10. Czumaj, A.: Selfish routing on the Internet. In: Leung, J. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chap. 42. CRC, Boca Raton (2004)

    Google Scholar 

  11. Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. ACM Trans. Algorithms 3(1), 2007

  12. Epstein, L., Kleiman, E.: Selfish bin packing. In: Proc. of the 16th Annual European Symposium on Algorithms, ESA 2008, September 2008, pp. 368–380

  13. Fiat, A., Kaplan, H., Levy, M., Olonetsky, S.: Strong price of anarchy for machine load balancing. In Proc. of the 34th International Colloquium on Automata, Languages and Programming, ICALP 2007, pp. 583–594 (2007)

  14. Fotakis, D., Kontogiannis, S.C., Koutsoupias, E., Mavronicolas, M., Spirakis, P.G.: The structure and complexity of Nash equilibria for a selfish routing game. In: Proc. of the 29th International Colloquium on Automata, Languages and Programming, ICALP 2002, pp. 123–134 (2002)

  15. Fotakis, D., Kontogiannis, S.C., Spirakis, P.G.: Atomic congestion games among coalitions. In: Proc. of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, Part I, pp. 572–583 (2006)

  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)

  17. Hayrapetyan, A., Tardos, É., Wexler, T.: The effect of collusion in congestion games. In: Proc. of the 38th Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 89–98 (2006)

  18. Holzman, R., Law-Yone, N.: Strong equilibrium in congestion games. Games Econ. Behav. 2(1–2), 85–101 (1997)

    Article  MathSciNet  Google Scholar 

  19. Karp, R.M., Koutsoupias, E., Papadimitriou, C.H., Shenker, S.: Optimization problems in congestion control. In: Proc. of the 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, pp. 66–74 (2000)

  20. Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. In: Proc. of the 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1999, pp. 404–413 (1999)

  21. Koutsoupias, E., Mavronicolas, M., Spirakis, P.G.: Approximate equilibria and ball fusion. Theory Comput. Syst. 36(6), 683–693 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  22. Lee, C.C., Lee, D.T.: A simple online bin packing algorithm. J. ACM 32, 562–572 (1985)

    Article  MATH  Google Scholar 

  23. Lücking, T., Mavronicolas, M., Monien, B., Rode, M.: A new model for selfish routing. In: Proc. of the 21st Annual Symposium on Theoretical Aspects of Computer Science, STACS 2004, pp. 547–558 (2004)

  24. Mavronicolas, M., Spirakis, P.G.: The price of selfish routing. In: Proc. of the 33rd Annual Symposium on Theory of Computing, STOC 2001, pp. 510–519 (2001)

  25. Nash, J.: Non-cooperative games. Ann. Math. 54(2), 286–295 (1951)

    Article  MathSciNet  Google Scholar 

  26. Papadimitriou, C.H.: Algorithms, games, and the Internet. In: Proc. of the 33rd Annual Symposium on Theory of Computing, STOC 2001, pp. 749–753 (2001)

  27. Roughgarden, T.: Designing networks for selfish users is hard. In: Proc. of the 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, pp. 472–481 (2001)

  28. Roughgarden, T., É., Tardos.: How bad is selfish routing? In: Proc. of the 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, pp. 93–102 (2000)

  29. Tennenholtz, M., Rozenfeld, O.: Strong and correlated strong equilibria in monotone congestion games. In: Proc. of the 2nd International Workshop on Internet and Network Economics, WINE 2006, pp. 74–86 (2006)

  30. Whinston, M., Bernheim, B., Peleg, B.: Coalition-proof Nash equilibria: I concepts. J. Econ. Theory 42, 1–12 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  31. Yaïche, H., Mazumdar, R., Rosenberg, C.: A game theoretic framework for bandwidth allocation and pricing in broadband networks. IEEE/ACM Trans. Netw. 8(5), 667–678 (2000)

    Article  Google Scholar 

  32. Yu, G., Zhang, G.: Bin packing of selfish items. In: Proc. of the 4th International Workshop on Internet and Network Economics, WINE 2008, December 2008, pp. 446–453

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Leah Epstein.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Epstein, L., Kleiman, E. Selfish Bin Packing. Algorithmica 60, 368–394 (2011). https://doi.org/10.1007/s00453-009-9348-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-009-9348-6

Keywords

Navigation