Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Selfish bin packing under Harmonic mean cost sharing mechanism

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

In this paper, we introduce the selfish bin packing problem under a new version of cost sharing mechanism based on harmonic mean. The items (as agents) are selfish and intelligent to minimize the cost they have to pay, by selecting a proper bin to fit in. The tricky part is that the one with bigger size pays less and vice versa. We present the motivations and prove the existence of pure Nash Equilibrium under this new defined cost sharing mechanism. Then we study the Price of Anarchy, which is the ratio between the objective value of worst Nash Equilibrium and that of the optimum in the case with central decision maker. We prove the upper bound to be approximately 1.722 and show a 5/3 lower bound for this problem. We then include punishment into the model and prove that in this new model, the Price of Anarchy could be decreased to 3/2.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Adara, R., Epstein, L.: Selfish bin packing with cardinality constraints. Theor. Comput. Sci.495, 66–80 (2013)

    Article MathSciNet  Google Scholar 

  2. Avinash, D., Skeath, S., Reiley, D.: Games of Strategy, 3rd edn. Norton Company, New York (2009)

    Google Scholar 

  3. Bilò, V.: On the packing of selfish items. In: Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS2006). IEEE, Rhodes, Greece, pp. 45-54(2006)

  4. Bilò, V., Cellinese, F., Melideo, G., Monaco, G.: Selfish colorful bin packing games. J. Comb. Optim.40(3), 610–635 (2020)

    Article MathSciNet  Google Scholar 

  5. Dòsa, G., Epstein, L.: Generalized selfish bin packing.ArXiv:1202.4080 [cs.GT](2012)

  6. Dòsa, G.: A new lower bound on the price of anarchy of selfish bin packing. Inf. Process. Lett.150, 6–12 (2019a)

    Article MathSciNet  Google Scholar 

  7. Dòsa, G.: Using weight decision for decreasing the price of anarchy in selfish bin packing games. Eur. J. Oper. Res.278(1), 160–169 (2019c)

    Article MathSciNet  Google Scholar 

  8. Koutsoupias, E., Papadimitriou, C.: Worst-case Equilibria. Comput. Sci. Rev.3(2), 65–69 (2009)

    Article  Google Scholar 

  9. Epstein, L., Kleiman, E.: Selfish bin packing. Algorithmica60(2), 368–394 (2011)

    Article MathSciNet  Google Scholar 

  10. Epstein, L.: Selfish Bin Packing Problems. In: Kao, M.Y. (eds) Encyclopedia of Algorithms. LNCS, pp. 1927-1930, Springer, Boston, MA (2016)

  11. Han, X., Dòsa, G.: A note on a selfish bin packing problem. J. Glob. Optim.56(4), 1457–1462 (2013)

    Article MathSciNet  Google Scholar 

  12. Yu, G., Zhang, G.: Bin Packing of Selfish Items. In: Papadimitriou, C., Zhang, S. (eds.) WINE, vol. 5385, pp. 446–453. Berlin, Springer (2008)

    Google Scholar 

  13. Koutsoupias, E., Papadimitriou, C., Meinel, C., Tison, S.: Worst-case equilibria, pp. 404–413. Springer, Heidelberg (1999)

    MATH  Google Scholar 

  14. Game, G.B.P., Wang, Z., Han, X., Dòsa, G.: Interest taken into account. Algorithmica80, 1534–1555 (2018)

    Article MathSciNet  Google Scholar 

  15. Zhang, W., Gao, A., Gai, L.: Selfish Bin Packing with Parameterized Punishment. In: Zhang, Z., Li, W., Du, DZ. (eds.) Algorithmic Aspects in Information and Management. AAIM 2020. Lecture Notes in Computer Science, vol. 12290. Springer, Cham.https://doi.org/10.1007/978-3-030-57602-8_22(2020)

  16. Zhang, C., Zhang, G.: From packing rules to cost-sharing mechanisms. J. Comb. Optim.1–16, 26985 (2020)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Glorious Sun School of Business & Management, Donghua University, Shanghai, 200051, People’s Republic of China

    Ling Gai

  2. College of Science, Tianjin University of Technology, Tianjin, 300384, People’s Republic of China

    Chenchen Wu

  3. Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing, 100124, People’s Republic of China

    Dachuan Xu

  4. School of Management, Shanghai University, Shanghai, 201444, People’s Republic of China

    Weiwei Zhang

Authors
  1. Ling Gai

    You can also search for this author inPubMed Google Scholar

  2. Chenchen Wu

    You can also search for this author inPubMed Google Scholar

  3. Dachuan Xu

    You can also search for this author inPubMed Google Scholar

  4. Weiwei Zhang

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toWeiwei Zhang.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The work of Ling Gai was supported in part by National Natural Science Foundation of China 11201333. The work of Chenchen Wu was supported in part by National Natural Science Foundation of China 11971349. The work of Dachuan Xu was supported in part by National Natural Science Foundation of China 11871081.

Rights and permissions

About this article

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp