Price of Anarchy in uniform parallel machines scheduling game with weighted completion time as social goal

Open Access

Issue		RAIRO-Oper. Res. Volume 58, Number 2, March-April 2024


Page(s)		1093 - 1103
DOI		https://doi.org/10.1051/ro/2024017
Published online		12 March 2024

F. Abed, J.R. Correa and C.-C. Huang, Optimal coordination mechanisms for multi-job scheduling games, in Algorithms-ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, September 8–10, 2014. Proceedings 21. Springer Berlin Heidelberg (2014) 13–24. [Google Scholar]
Y. Azar, L. Fleischer, K. Jain, V. Mirrokni and Z. Svitkina, Optimal coordination mechanisms for unrelated machine scheduling. Oper. Res. 63 (2015) 489–500. [CrossRef] [MathSciNet] [Google Scholar]
S. Bhattacharya, S. Im, J. Kulkarni and K. Munagala, Coordination mechanisms from (almost) all scheduling policies, in Proceedings of the 5th Conference on Innovations in Theoretical Computer Science (ITCS). ACM, NY, USA (2014) 121–134. [Google Scholar]
T. Brueggemann, J.L. Hurink and W. Kern, Quality of move-optimal schedules for minimizing total weighted completion time. Oper. Res. Lett. 34 (2006) 583–590. [CrossRef] [MathSciNet] [Google Scholar]
I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos and L. Moscardelli, Tight bounds for selfish and greedy load balancing. Algorithmica 61 (2011) 606–637. [CrossRef] [MathSciNet] [Google Scholar]
G. Christodoulou, E. Koutsoupias and A. Nanavati, Coordination mechanisms. Theor. Comput. Sci. 410 (2009) 3327–3336. [CrossRef] [Google Scholar]
R. Cole, J.R. Correa, V. Gkatzelis, V. Mirrokni and N. Olver, Decentralized utilitarian mechanisms for scheduling games. Games Econ. Behav. 92 (2015) 306–326. [CrossRef] [Google Scholar]
J.R. Correa and M. Queyranne, Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost. Nav. Res. Logist. 59 (2012) 384–395. [CrossRef] [Google Scholar]
A. Czumaj and B. Vöcking, Tight bounds for worst-case equilibria. ACM Trans. Algorithms 3 (2007) 1–17. [CrossRef] [Google Scholar]
W.L. Eastman, S. Even and I.M. Isaacs, Bounds for the optimal scheduling of n jobs on m processors. Manage. Sci. 11 (1964) 268–279. [CrossRef] [Google Scholar]
R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5 (1979) 287–326. [CrossRef] [MathSciNet] [Google Scholar]
B. Heydenreich, R. Müller and M. Uetz, Games and mechanism design in machine scheduling – an introduction. Prod. Oper. Manage. 16 (2007) 437–454. [CrossRef] [Google Scholar]
R. Hoeksma and M. Uetz, The price of anarchy for utilitarian scheduling games on related machines. Discrete Optim. 31 (2019) 29–39. [CrossRef] [MathSciNet] [Google Scholar]
N. Immorlica, L.E. Li, V.S. Mirrokni and A.S. Schulz, Coordination mechanisms for selfish scheduling. Theor. Comput. Sci. 410 (2009) 1589–1598. [CrossRef] [Google Scholar]
T. Kawaguchi and S. Kyan, Worst case bound of an LRF schedule for the mean weighted flow-time problem. SIAM J. Comput. 15 (1986) 1119–1129. [CrossRef] [MathSciNet] [Google Scholar]
E. Koutsoupias and C.H. Papadimitriou, Worst-case equilibria. Comput. Sci. Rev. 3 (2009) 65–69. [CrossRef] [Google Scholar]
K. Lee, J.Y.-T. Leung and M.L. Pinedo, Coordination mechanisms for parallel machine scheduling. Eur. J. Oper. Res. 220 (2012) 305–313. [CrossRef] [Google Scholar]
F.T. Mu˜noz and A.A. Pinochet, Performance guarantee of the jump neighborhood for scheduling jobs on uniformly related machines. RAIRO: Oper. Res. 56 (2022) 1079–1088. [CrossRef] [EDP Sciences] [MathSciNet] [Google Scholar]
M. Rahn and G. Sch¨afer, Bounding the inefficiency of altruism through social contribution games, in International Conference on Web and Internet Economics. Springer Berlin Heidelberg, Berlin, Heidelberg (2013) 391–404. [CrossRef] [Google Scholar]
O.L. Rivera, Cotas para el precio de la anarquía de juegos de Scheduling. Undergraduate thesis, Universidad de Chile, Chile (2012). https://repositorio.uchile.cl/handle/2250/111965. [Google Scholar]
W.E. Smith, Various optimizers for single-stage production. Nav. Res. Logist. Q. 3 (1956) 59–66. [CrossRef] [Google Scholar]
L. Yu, K. She, H. Gong and C. Yu, Price of anarchy in parallel processing. Inf. Process. Lett. 110 (2010) 288–293. [CrossRef] [Google Scholar]
L. Zhang, Y. Zhang, D. Du and Q. Bai, Improved price of anarchy for machine scheduling games with coordination mechanisms. Optim. Lett. 13 (2019) 949–959. [CrossRef] [MathSciNet] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.