Journal of Zhejiang University

ENGINEERING Information Technology & Electronic Engineering 2026 Vol.27 No.10 P.1-7

http://doi.org/10.1631/ENG.ITEE.2026.0111

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

Author(s): Yong WU, Qi WEI
Affiliation(s): 1. College of Management, Ningbo University of Finance and Economics, Ningbo 315175, China
Corresponding email(s): weiqi@nbufe.edu.cn
Key Words: Scheduling game, Hierarchy, Parallel processing, Price of anarchy (PoA), Nash equilibrium

<<< Previous Article \|Next Article >>>

Yong WU, Qi WEI. Exact price of anarchy for a two-uniform-machine scheduling game under parallel processing[J]. Journal of Zhejiang University Science C, 2026, 27(10): 1-7.

@article{title="Exact price of anarchy for a two-uniform-machine scheduling game under parallel processing",
author="Yong WU, Qi WEI",
journal="Journal of Zhejiang University Science C",
volume="27",
number="10",
pages="1-7",
year="2026",
publisher="Zhejiang University Press & Springer",
doi="10.1631/ENG.ITEE.2026.0111"
}

%0 Journal Article
%T Exact price of anarchy for a two-uniform-machine scheduling game under parallel processing
%A Yong WU
%A Qi WEI
%J Frontiers of Information Technology & Electronic Engineering
%V 27
%N 10
%P 1-7
%@ 1869-1951
%D 2026
%I Zhejiang University Press & Springer
%DOI 10.1631/ENG.ITEE.2026.0111

TY - JOUR
T1 - Exact price of anarchy for a two-uniform-machine scheduling game under parallel processing
A1 - Yong WU
A1 - Qi WEI
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 27
IS - 10
SP - 1
EP - 7
%@ 1869-1951
Y1 - 2026
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/ENG.ITEE.2026.0111

Abstract
Chinese Summary
Academic Network
Reviewer Comment

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.

并行处理策略下两台同类机器调度博弈的精确无政府代价

吴用，魏麒
宁波财经学院管理学院，中国宁波市，315175
摘要：本文研究并行处理策略下两台带服务等级的同类机上调度博弈的无政府代价（PoA）。并行处理策略是一种协调机制，融合了经典的最短优先与最大完工时间策略。该调度博弈对应于分时操作系统与网络数据包处理器中广泛采用的轮询调度机制。本文聚焦于最大完工时间最小化问题。推导出PoA作为两台机器速度比值的函数，证明所推导的界对于任意速度比值都是紧界，从而刻画了并行处理策略下两台带服务等级同类机上调度博弈中纳什均衡的低效性。

关键词：调度博弈；服务等级；并行处理；无政府代价（PoA）；纳什均衡

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[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 31^st 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 16^th 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 33^rd 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.

Full Text: <13>