Top

Published in:

2017 | OriginalPaper | Chapter

An Improved Mechanism for Selfish Bin Packing

Authors : Xin Chen, Qingqin Nong, Qizhi Fang

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Selfish bin packing can be viewed as the non-cooperative version of bin packing problem, where every item is a selfish agent and want to minimize his sharing cost with the other items packing in the same bin. In this paper, we focus on designing a new mechanism (a payoff rule) for selfish bin packing, called modified Dutch treatment mechanism. We first show that the pure Nash equilibrium exists and it can be obtained in polynomial time. We then prove that under the new mechanism, the price of anarchy (PoA) is between 1.47407 and 1.4748, improving the known results.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Selfish Jobs with Favorite Machines: Price of Anarchy vs. Strong Price of Anarchy

next chapter Hamiltonian Cycles in Covering Graphs of Trees

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

Coffman, J.E.G., Csirik, J.: Performance guarantees for one-dimensional bin packing. In: Handbook of Approximation Algorithms and Metaheuristics, p. 32-1 (2007)

Coffman, J.E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Approximation Algorithms for NP-Hard Problems, pp. 46–93. PWS Publishing Co. (1996)

Dósa, G., Epstein, L.: Generalized selfish bin packing. arXiv preprint arXiv:1202.4080 (2012)

Dósa, G., Sgall, J.: First Fit bin packing: a tight analysis. LIPIcs-Leibniz International Proceedings in Informatics. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2013)

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

Epstein, L., Kleiman, E., Mestre, J.: Parametric packing of selfish items and the subset sum algorithm. Algorithmica 74(1), 177–207 (2016)CrossRefMATHMathSciNet

Garey, M.R., Graham, R.L., Ullman, J.D.: Worst-case analysis of memory allocation algorithms. In: Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, pp. 143–150. ACM (1972)

Johnson, D.S., Demers, A., Ullman, J.D., et al.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3(4), 299–325 (1974)CrossRefMATHMathSciNet

10.

Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-49116-3_38 CrossRef

11.

Li, W., Fang, Q., Liu, W.: An incentive mechanism for selfish bin covering. In: Chan, T.-H.H., Li, M., Wang, L. (eds.) COCOA 2016. LNCS, vol. 10043, pp. 641–654. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48749-6_46 CrossRef

12.

Ma, R., Dósa, G., Han, X., et al.: A note on a selfish bin packing problem. J. Global Optim. 56(4), 1457–1462 (2013)CrossRefMATHMathSciNet

13.

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

14.

Neumann, L.J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton (1947)MATH

15.

Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)CrossRefMATH

16.

Wang, Z., Han, X., Dósa, G., Tuza, Z.: Bin packing game with an interest matrix. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 57–69. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21398-9_5 CrossRef

17.

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). https://doi.org/10.1007/978-3-540-92185-1_50 CrossRef

Title: An Improved Mechanism for Selfish Bin Packing
Authors: Xin Chen
Qingqin Nong
Qizhi Fang
Publisher: Springer International Publishing
Book: Combinatorial Optimization and Applications
Print ISBN: 978-3-319-71146-1

Electronic ISBN: 978-3-319-71147-8

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-71147-8_17

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner