Exact price of anarchy for a two-uniform-machine scheduling game under parallel processing

Yong WU; Qi WEI

doi:10.1631/ENG.ITEE.2026.0111

Your Location：

Home >

Browse articles >

Exact price of anarchy for a two-uniform-machine scheduling game under parallel processing

Regular Papers | Updated：2026-11-05

- Exact price of anarchy for a two-uniform-machine scheduling game under parallel processing
- Exact price of anarchy for a two-uniform-machine scheduling game under parallel processing
- ENGINEERING Information Technology & Electronic Engineering Vol. 27, Issue 10, Pages: 1-7(2026)
- Affiliations：
  
  College of Management, Ningbo University of Finance and Economics, Ningbo 315175, China
- Author bio：
  
  ✉ Qi WEI, weiqi@nbufe.edu.cn
- Funds：
- DOI：10.1631/ENG.ITEE.2026.0111
  CLC： TP301.6;O223
- Received：19 April 2026，
  
  Revised：2026-08-19，
  
  Online First：06 October 2026，
  
  Published：01 October 2026
- Accepted：
Scan QR Code
Yong WU, Qi WEI. Exact price of anarchy for a two-uniform-machine scheduling game under parallel processing[J]. ENGINEERING Information Technology & Electronic Engineering, 2026, 27(10): 1-7.
DOI：

Yong WU, Qi WEI. Exact price of anarchy for a two-uniform-machine scheduling game under parallel processing[J]. ENGINEERING Information Technology & Electronic Engineering, 2026, 27(10): 1-7. DOI： 10.1631/ENG.ITEE.2026.0111.

摘要

Abstract

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.

关键词

Keywords

references

Azar Y , Fleischer L , Jain K , et al. , 2015 . Optimal coordination mechanisms for unrelated machine scheduling . Oper Res , 63 ( 3 ): 489 - 500 . https://doi.org/10.1287/opre.2015.1363 https://doi.org/10.1287/opre.2015.1363

Bar-Noy A , Freund A , Naor J , 2001 . On-line load balancing in a hierarchical server topology . SIAM J Comput , 31 ( 2 ): 527 - 549 . https://doi.org/10.1137/s0097539798346135 https://doi.org/10.1137/s0097539798346135

Chen C , Xu YF , 2020 . Coordination mechanisms for scheduling selfish jobs with favorite machines . J Comb Optim , 40 ( 2 ): 333 - 365 . https://doi.org/10.1007/s10878-020-00592-2 https://doi.org/10.1007/s10878-020-00592-2

Chen QQ , Tan ZY , 2021 . Mixed coordination mechanisms for scheduling games on hierarchical machines . Int Trans Oper Res , 28 ( 1 ): 419 - 437 . https://doi.org/10.1111/itor.12558 https://doi.org/10.1111/itor.12558

Christodoulou G , Koutsoupias E , Nanavati A , 2004 . Coordination mechanisms . Proc 31 st Int Colloquium on Automata, Languages and Programming , p. 345 - 357 . https://doi.org/10.1007/978-3-540-27836-8_31 https://doi.org/10.1007/978-3-540-27836-8_31

Cohen J , Dürr C , Kim TN , 2011 . Non-clairvoyant scheduling games . Theor Comput Syst , 49 ( 1 ): 3 - 23 . https://doi.org/10.1007/s00224-011-9316-9 https://doi.org/10.1007/s00224-011-9316-9

Cole R , Dodis Y , Roughgarden T , 2006 . How much can taxes help selfish routing ? J Comput Syst Sci , 72 ( 3 ): 444 - 467 . https://doi.org/10.1016/j.jcss.2005.09.010 https://doi.org/10.1016/j.jcss.2005.09.010

Czumaj A , Vöcking B , 2007 . Tight bounds for worst‑case equilibria . ACM Trans Algorithms , 3 ( 1 ): 4 . https://doi.org/10.1145/1186810.1186814 https://doi.org/10.1145/1186810.1186814

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 . https://doi.org/10.1007/s00236‑010‑0124‑5 https://doi.org/10.1007/s00236‑010‑0124‑5

Finn G , Horowitz E , 1979 . A linear time approximation algorithm for multiprocessor scheduling . BIT Numer Math , 19 ( 3 ): 312 ‑ 320 . https://doi.org/10.1007/bf01930985 https://doi.org/10.1007/bf01930985

Guan L , Li JP , 2013 . Coordination mechanism for selfish scheduling under a grade of service provision . Inform Process Lett , 113 ( 8 ): 251 ‑ 254 . https://doi.org/10.1016/j.ipl.2013.01.014 https://doi.org/10.1016/j.ipl.2013.01.014

He CY , Tan ZY , 2026 . Random coordination mechanism for scheduling games with machine modification . Discrete Appl Math , 382 : 108 ‑ 123 . https://doi.org/10.1016/j.dam.2025.11.038 https://doi.org/10.1016/j.dam.2025.11.038

Immorlica N , Li L , Mirrokni VS , et al. , 2009 . Coordination mechanisms for selfish scheduling . Theor Comput Sci , 410 ( 17 ): 1589 ‑ 1598 . https://doi.org/10.1016/j.tcs.2008.12.032 https://doi.org/10.1016/j.tcs.2008.12.032

Koutsoupias E , Papadimitriou C , 1999 . Worst‑case equilibria . Proc 16 th Symp on Theoretical Aspects of Computer Science , p. 404 ‑ 413 . https://doi.org/10.1007/3‑540‑49116‑3_38 https://doi.org/10.1007/3‑540‑49116‑3_38

Kress D , Meiswinkel S , Pesch E , 2018 . Mechanism design for machine scheduling problems: classification and literature overview . OR Spectrum , 40 ( 3 ): 583 ‑ 611 . https://doi.org/10.1007/s00291‑018‑0512‑8 https://doi.org/10.1007/s00291‑018‑0512‑8

Lin L , Tan ZY , 2014 . Inefficiency of Nash equilibrium for scheduling games with constrained jobs: a parametric analysis . Theor Comput Sci , 521 : 123 ‑ 134 . https://doi.org/10.1016/j.tcs.2013.11.012 https://doi.org/10.1016/j.tcs.2013.11.012

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 . https://doi.org/10.1142/S0217595924500106 https://doi.org/10.1142/S0217595924500106

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 . https://doi.org/10.3390/math12142223 https://doi.org/10.3390/math12142223

Roughgarden T , 2001 . Stackelberg scheduling strategies . Proc 33 rd Annual ACM Symp on Theory of Computing , p. 104 ‑ 113 . https://doi.org/10.1145/380752.380783 https://doi.org/10.1145/380752.380783

Wan L , Deng XF , Tan ZY , 2013 . Inefficiency of Nash equilibria with parallel processing policy . Inform Process Lett , 113 ( 13 ): 465 ‑ 469 . https://doi.org/10.1016/j.ipl.2013.03.006 https://doi.org/10.1016/j.ipl.2013.03.006

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 . https://doi.org/10.1016/j.ipl.2015.06.005 https://doi.org/10.1016/j.ipl.2015.06.005

Yu LF , She K , Gong HG , et al. , 2010 . Price of anarchy in parallel processing . Inform Process Lett , 110 ( 8‑9 ): 288 ‑ 293 . https://doi.org/10.1016/j.ipl.2010.02.003 https://doi.org/10.1016/j.ipl.2010.02.003

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

A projected gradient based game theoretic approach for multi-user power control in cognitive radio network

Social radar Doppler: multi-scenario validation ofsocial media-based crisis early warning

Adaptive practical fixed-time tracking control with prescribed performance for robotic manipulators

SigmaGait: silhouette-guided motion-augmentation module for depth-based gait recognition

Stacked intelligent metasurface-aided multi-static sensing and cooperative communication

Related Author

Yun-zheng TAO

Chun-yan WU

Yu-zhen HUANG

Ping ZHANG

Related Institution

State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications

College of Communications Engineering, PLA University of Science and Technology

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰