Skip to main content

2016 | OriginalPaper | Buchkapitel

An Incentive Mechanism for Selfish Bin Covering

verfasst von : Weian Li, Qizhi Fang, Wenjing Liu

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper, we consider the selfish bin covering problems, which can be viewed as the bin covering problems in game theoretic settings. Our main contribution is an incentive mechanism with better price of anarchy. Under this mechanism, for any instance with a Nash equilibrium (NE), we show that price of anarchy is 2/3. For the cases that the NE does not exist, we propose a concept of modified NE, named M-NE, which can be obtained in finite steps from any initial state. We further show that for M-NE, the price of anarchy is 1/2 and the price of stability is 1.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Fußnoten
1
The PoA of selfish bin packing is defined contrary to that of SBC.
 
2
First Fit Decreasing, which is described as follows. First sort the items in non-increasing order of their sizes, then puts the items one by one in this order to a bin until the bin is covered. Open a new bin and repeat the above actions until all the items are assigned.
 
Literatur
2.
Zurück zum Zitat Assmann, S.B.: Problems in discrete applied mathematics. Ph.D. thesis, Department of Mathematics, MIT, Cambridge, MA (1983) Assmann, S.B.: Problems in discrete applied mathematics. Ph.D. thesis, Department of Mathematics, MIT, Cambridge, MA (1983)
3.
Zurück zum Zitat Assmann, S.F., Johnson, D.S., Kleitman, D.J., Leung, J.Y.-T.: On a dual version of the one-dimensional bin packing problem. J. Algorithms 5(4), 502–525 (1984)MathSciNetCrossRefMATH Assmann, S.F., Johnson, D.S., Kleitman, D.J., Leung, J.Y.-T.: On a dual version of the one-dimensional bin packing problem. J. Algorithms 5(4), 502–525 (1984)MathSciNetCrossRefMATH
4.
Zurück zum Zitat Bilò, V.: On the packing of selfish items. In: Proceedings 20th IEEE International Parallel & Distributed Processing Symposium, p. 9. IEEE (2006) Bilò, V.: On the packing of selfish items. In: Proceedings 20th IEEE International Parallel & Distributed Processing Symposium, p. 9. IEEE (2006)
6.
Zurück zum Zitat Csirik, J., Frenk, J.B.G., Labbé, M., Zhang, S.: Two simple algorithms for bin covering. Acta Cybernetica 14(1), 13–25 (1999)MathSciNetMATH Csirik, J., Frenk, J.B.G., Labbé, M., Zhang, S.: Two simple algorithms for bin covering. Acta Cybernetica 14(1), 13–25 (1999)MathSciNetMATH
7.
Zurück zum Zitat Csirik, J., Johnson, D.S., Kenyon, C.: Better approximation algorithms for bin covering. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 557–566. Society for Industrial and Applied Mathematics (2001) Csirik, J., Johnson, D.S., Kenyon, C.: Better approximation algorithms for bin covering. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 557–566. Society for Industrial and Applied Mathematics (2001)
8.
Zurück zum Zitat Coffman, E.G., Csirik, J., Leung, J.Y.-T.: Variants of classical one-dimensional bin packing. In: Handbook of Approximation Algorithms and Metaheuristics, p. 13 (2007). Chap. 33 Coffman, E.G., Csirik, J., Leung, J.Y.-T.: Variants of classical one-dimensional bin packing. In: Handbook of Approximation Algorithms and Metaheuristics, p. 13 (2007). Chap. 33
11.
Zurück zum Zitat Jansen, K., Solis-Oba, R.: An asymptotic fully polynomial time approximation scheme for bin covering. Theoret. Comput. Sci. 306(1), 543–551 (2003)MathSciNetCrossRefMATH Jansen, K., Solis-Oba, R.: An asymptotic fully polynomial time approximation scheme for bin covering. Theoret. Comput. Sci. 306(1), 543–551 (2003)MathSciNetCrossRefMATH
12.
Zurück zum Zitat Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)CrossRef Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)CrossRef
13.
Zurück zum Zitat Ma, R., Dósa, G., Han, X., Ting, H.-F., Ye, D., Zhang, Y.: A note on a selfish bin packing problem. J. Global Optim. 56(4), 1457–1462 (2013)MathSciNetCrossRefMATH Ma, R., Dósa, G., Han, X., Ting, H.-F., Ye, D., Zhang, Y.: A note on a selfish bin packing problem. J. Global Optim. 56(4), 1457–1462 (2013)MathSciNetCrossRefMATH
14.
Zurück zum Zitat Papadimitriou, C.: Algorithms, games, and the internet. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, 749–753. ACM (2001) Papadimitriou, C.: Algorithms, games, and the internet. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, 749–753. ACM (2001)
15.
Zurück zum Zitat 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)CrossRef 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)CrossRef
Metadaten
Titel
An Incentive Mechanism for Selfish Bin Covering
verfasst von
Weian Li
Qizhi Fang
Wenjing Liu
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-48749-6_46