Skip to main content

2017 | OriginalPaper | Buchkapitel

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

verfasst von : Cong Chen, Paolo Penna, Yinfeng Xu

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

We consider the well-studied game-theoretic version of machine scheduling in which jobs correspond to self-interested users and machines correspond to resources. Here each user chooses a machine trying to minimize her own cost, and such selfish behavior typically results in some equilibrium which is not globally optimal: An equilibrium is an allocation where no user can reduce her own cost by moving to another machine, which in general need not minimize the makespan, i.e., the maximum load over the machines.
We provide tight bounds on two well-studied notions in algorithmic game theory, namely, the price of anarchy and the strong price of anarchy on machine scheduling setting which lies in between the related and the unrelated machine case. Both notions study the social cost (makespan) of the worst equilibrium compared to the optimum, with the strong price of anarchy restricting to a stronger form of equilibria. Our results extend a prior study comparing the price of anarchy to the strong price of anarchy for two related machines (Epstein [13], Acta Informatica 2010), thus providing further insights on the relation between these concepts. Our exact bounds give a qualitative and quantitative comparison between the two models. The bounds also show that the setting is indeed easier than the two unrelated machines: In the latter, the strong price of anarchy is 2, while in ours it is strictly smaller.

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!

Literatur
2.
Zurück zum Zitat Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008)CrossRefMATHMathSciNet Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008)CrossRefMATHMathSciNet
3.
Zurück zum Zitat Auletta, V., Christodoulou, G., Penna, P.: Mechanisms for scheduling with single-bit private values. Theor. Comput. Syst. 57(3), 523–548 (2015)CrossRefMATHMathSciNet Auletta, V., Christodoulou, G., Penna, P.: Mechanisms for scheduling with single-bit private values. Theor. Comput. Syst. 57(3), 523–548 (2015)CrossRefMATHMathSciNet
4.
Zurück zum Zitat Aumann, R.J.: Acceptable Points in General Cooperative n-Person Games, pp. 287–324. Princeton University Press, Princeton (1959) Aumann, R.J.: Acceptable Points in General Cooperative n-Person Games, pp. 287–324. Princeton University Press, Princeton (1959)
5.
Zurück zum Zitat Awerbuch, B., Azar, Y., Richter, Y., Tsur, D.: Tradeoffs in worst-case equilibria. Theor. Comput. Sci. 361(2), 200–209 (2006)CrossRefMATHMathSciNet Awerbuch, B., Azar, Y., Richter, Y., Tsur, D.: Tradeoffs in worst-case equilibria. Theor. Comput. Sci. 361(2), 200–209 (2006)CrossRefMATHMathSciNet
6.
Zurück zum Zitat Bilò, V., Flammini, M., Monaco, G., Moscardelli, L.: Some anomalies of farsighted strategic behavior. Theor. Comput. Syst. 56(1), 156–180 (2015)CrossRefMATHMathSciNet Bilò, V., Flammini, M., Monaco, G., Moscardelli, L.: Some anomalies of farsighted strategic behavior. Theor. Comput. Syst. 56(1), 156–180 (2015)CrossRefMATHMathSciNet
7.
Zurück zum Zitat Chen, C., Penna, P., Xu, Y.: Online Scheduling of Jobs with Favorite Machines (2017, submitted) Chen, C., Penna, P., Xu, Y.: Online Scheduling of Jobs with Favorite Machines (2017, submitted)
8.
Zurück zum Zitat Chen, C., Penna, P., Xu, Y.: Selfish jobs with favorite machines: price of anarchy vs. strong price of anarchy. arXiv e-prints, CoRR, abs/1709.06367 (2017) Chen, C., Penna, P., Xu, Y.: Selfish jobs with favorite machines: price of anarchy vs. strong price of anarchy. arXiv e-prints, CoRR, abs/1709.06367 (2017)
10.
Zurück zum Zitat Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the 37th annual ACM Symposium on Theory of Computing (STOC), pp. 67–73 (2005) Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the 37th annual ACM Symposium on Theory of Computing (STOC), pp. 67–73 (2005)
13.
Zurück zum Zitat Epstein, L.: Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy. Acta Informatica 47(7), 375–389 (2010)CrossRefMATHMathSciNet Epstein, L.: Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy. Acta Informatica 47(7), 375–389 (2010)CrossRefMATHMathSciNet
14.
Zurück zum Zitat Feldman, M., Tamir, T.: Approximate strong equilibrium in job scheduling games. J. Artif. Intell. Res. 36, 387–414 (2009)MATHMathSciNet Feldman, M., Tamir, T.: Approximate strong equilibrium in job scheduling games. J. Artif. Intell. Res. 36, 387–414 (2009)MATHMathSciNet
15.
Zurück zum Zitat Feldmann, R., Gairing, M., Lücking, T., Monien, B., Rode, M.: Nashification and the coordination ratio for a selfish routing game. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 514–526. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45061-0_42 CrossRef Feldmann, R., Gairing, M., Lücking, T., Monien, B., Rode, M.: Nashification and the coordination ratio for a selfish routing game. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 514–526. Springer, Heidelberg (2003). https://​doi.​org/​10.​1007/​3-540-45061-0_​42 CrossRef
17.
Zurück zum Zitat Finn, G., Horowitz, E.: A linear time approximation algorithm for multiprocessor scheduling. BIT Numer. Math. 19(3), 312–320 (1979)CrossRefMATHMathSciNet Finn, G., Horowitz, E.: A linear time approximation algorithm for multiprocessor scheduling. BIT Numer. Math. 19(3), 312–320 (1979)CrossRefMATHMathSciNet
18.
Zurück zum Zitat Gairing, M., Lücking, T., Mavronicolas, M., Monien, B.: The price of anarchy for restricted parallel links. Parallel Process. Lett. 16(01), 117–131 (2006)CrossRefMATHMathSciNet Gairing, M., Lücking, T., Mavronicolas, M., Monien, B.: The price of anarchy for restricted parallel links. Parallel Process. Lett. 16(01), 117–131 (2006)CrossRefMATHMathSciNet
19.
Zurück zum Zitat Giessler, P., Mamageishvili, A., Mihalák, M., Penna, P.: Sequential solutions in machine scheduling games. CoRR abs/1611.04159 (2016) Giessler, P., Mamageishvili, A., Mihalák, M., Penna, P.: Sequential solutions in machine scheduling games. CoRR abs/1611.04159 (2016)
21.
Zurück zum Zitat Kleinberg, R., Piliouras, G., Tardos, É.: Multiplicative updates outperform generic no-regret learning in congestion games. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 533–542 (2009) Kleinberg, R., Piliouras, G., Tardos, É.: Multiplicative updates outperform generic no-regret learning in congestion games. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 533–542 (2009)
22.
Zurück zum Zitat Koutsoupias, E., Mavronicolas, M., Spirakis, P.: Approximate equilibria and ball fusion. Theor. Comput. Syst. 36(6), 683–693 (2003)CrossRefMATHMathSciNet Koutsoupias, E., Mavronicolas, M., Spirakis, P.: Approximate equilibria and ball fusion. Theor. Comput. Syst. 36(6), 683–693 (2003)CrossRefMATHMathSciNet
24.
Zurück zum Zitat Lavi, R., Swamy, C.: Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity. Games Econ. Beh. 67(1), 99–124 (2009)CrossRefMATH Lavi, R., Swamy, C.: Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity. Games Econ. Beh. 67(1), 99–124 (2009)CrossRefMATH
25.
Zurück zum Zitat Leme, R.P., Syrgkanis, V., Tardos, É.: The curse of simultaneity. In: Proceedings of Innovations in Theoretical Computer Science (ITCS), pp. 60–67 (2012) Leme, R.P., Syrgkanis, V., Tardos, É.: The curse of simultaneity. In: Proceedings of Innovations in Theoretical Computer Science (ITCS), pp. 60–67 (2012)
26.
Zurück zum Zitat Roughgarden, T.: Intrinsic robustness of the price of anarchy. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 513–522 (2009) Roughgarden, T.: Intrinsic robustness of the price of anarchy. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 513–522 (2009)
27.
Zurück zum Zitat Schuurman, P., Vredeveld, T.: Performance guarantees of local search for multiprocessor scheduling. INFORMS J. Comput. 19(1), 52–63 (2007)CrossRefMATHMathSciNet Schuurman, P., Vredeveld, T.: Performance guarantees of local search for multiprocessor scheduling. INFORMS J. Comput. 19(1), 52–63 (2007)CrossRefMATHMathSciNet
Metadaten
Titel
Selfish Jobs with Favorite Machines: Price of Anarchy vs. Strong Price of Anarchy
verfasst von
Cong Chen
Paolo Penna
Yinfeng Xu
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-71147-8_16