This study analyzes the price of anarchy (PoA) for a scheduling game on two hierarchical uniform machines under the parallel processing policy, a coordination mechanism that combines the well-studied ShortestFirst and makespan policies. This scheduling game corresponds to the round-robin scheduling mechanism widely adopted in time-sharing operating systems and network packet processors. This study focuses on makespan minimization. We derive the PoA as a function of the ratio of the speeds of the two machines. We demonstrate that all derived bounds are tight for any ratio, thereby characterizing the inefficiency of Nash equilibria in scheduling games on two uniform machines under parallel processing.
| [1] |
Azar Y , Fleischer L , Jain K , et al., 2015. Optimal coordination mechanisms for unrelated machine scheduling. Oper Res, 63 (3): 489- 500.
|
| [2] |
Bar-Noy A , Freund A , Naor J , 2001. On-line load balancing in a hierarchical server topology. SIAM J Comput, 31 (2): 527- 549.
|
| [3] |
Chen C , Xu YF , 2020. Coordination mechanisms for scheduling selfish jobs with favorite machines. J Comb Optim, 40 (2): 333- 365.
|
| [4] |
Chen QQ , Tan ZY , 2021. Mixed coordination mechanisms for scheduling games on hierarchical machines. Int Trans Oper Res, 28 (1): 419- 437.
|
| [5] |
Christodoulou G , Koutsoupias E , Nanavati A , 2004. Coordination mechanisms. Proc 31st Int Colloquium on Automata, Languages and Programming, p.345- 357.
|
| [6] |
Cohen J , Dürr C , Kim TN , 2011. Non-clairvoyant scheduling games. Theor Comput Syst, 49 (1): 3- 23.
|
| [7] |
Cole R , Dodis Y , Roughgarden T , 2006. How much can taxes help selfish routing? J Comput Syst Sci, 72 (3): 444- 467.
|
| [8] |
Czumaj A , Vöcking B , 2007. Tight bounds for worst-case equilibria. ACM Trans Algorithms, 3 (1): 4.
|
| [9] |
Epstein L , 2010. Equilibria for two parallel links:the strong price of anarchy versus the price of anarchy. Acta Inform, 47 (7-8): 375- 389.
|
| [10] |
Finn G , Horowitz E , 1979. A linear time approximation algorithm for multiprocessor scheduling. BIT Numer Math, 19 (3): 312- 320.
|
| [11] |
Guan L , Li JP , 2013. Coordination mechanism for selfish scheduling under a grade of service provision. Inform Process Lett, 113 (8): 251- 254.
|
| [12] |
He CY , Tan ZY , 2026. Random coordination mechanism for scheduling games with machine modification. Discrete Appl Math, 382: 108- 123.
|
| [13] |
Immorlica N , Li L , Mirrokni VS , et al., 2009. Coordination mechanisms for selfish scheduling. Theor Comput Sci, 410 (17): 1589- 1598.
|
| [14] |
Koutsoupias E , Papadimitriou C , 1999. Worst-case equilibria. Proc 16th Symp on Theoretical Aspects of Computer Science, p.404- 413.
|
| [15] |
Kress D , Meiswinkel S , Pesch E , 2018. Mechanism design for machine scheduling problems:classification and literature overview. OR Spectrum, 40 (3): 583- 611.
|
| [16] |
Lin L , Tan ZY , 2014. Inefficiency of Nash equilibrium for scheduling games with constrained jobs:a parametric analysis. Theor Comput Sci, 521: 123- 134.
|
| [17] |
Lin L , Tan ZY , 2025. Price of anarchy of scheduling games on hierarchical machines with quadratic social cost. Asia Pac J Oper Res, 42 (2): 2450010.
|
| [18] |
Muñoz FT , Linfati R , 2024. Bounding the price of anarchy of weighted shortest processing time policy on uniform parallel machines. Mathematics, 12 (14): 2223.
|
| [19] |
Roughgarden T , 2001. Stackelberg scheduling strategies. Proc 33rd Annual ACM Symp on Theory of Computing, p.104- 113.
|
| [20] |
Wan L , Deng XF , Tan ZY , 2013. Inefficiency of Nash equilibria with parallel processing policy. Inform Process Lett, 113 (13): 465- 469.
|
| [21] |
Wu Y , Cheng TCE , Ji M , 2015. Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines. Inform Process Lett, 115 (11): 838- 844.
|
| [22] |
Yu LF , She K , Gong HG , et al., 2010. Price of anarchy in parallel processing. Inform Process Lett, 110 (8-9): 288- 293.
|
Rights & permissions
The Authors. Published by Zhejiang University Press Co., Ltd.
PDF
(519KB)
