Inefficiency of equilibria for scheduling game with machine activation costs

DOI10.1016/j.tcs.2015.05.035zbMath1333.91010OpenAlexW618543335MaRDI QIDQ897948

Xing He, Ling Lin, Zhiyi Tan, Yujie Yan, Xiaochen Xian

Publication date: 8 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.05.035

zbMATH Keywords

Nash equilibriumprice of anarchyprice of stabilityscheduling game

Mathematics Subject Classification ID

Noncooperative games (91A10) Applications of game theory (91A80) Deterministic scheduling theory in operations research (90B35)

Related Items

Efficiency analysis with respect to the unit cost objectives in scheduling games ⋮ Coordination mechanisms for scheduling games with machine modification ⋮ Integer programming methods to identify Nash equilibrium solutions for platform-based scheduling games ⋮ Coordination mechanisms for scheduling games with proportional deterioration ⋮ Efficiency and inefficiency of Nash equilibrium for scheduling games on batching-machines with activation cost ⋮ Improved price of anarchy for machine scheduling games with coordination mechanisms

Cites Work

• Unnamed Item
• The price of anarchy on uniformly related machines revisited
• Worst-case equilibria
• Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy
• Strong equilibrium in cost sharing connection games
• The structure and complexity of Nash equilibria for a selfish routing game
• Utilitarian resource assignment
• Efficiency analysis of load balancing games with and without activation costs
• Tight bounds for worst-case equilibria
• The Price of Stability for Network Design with Fair Cost Allocation
• Conflicting Congestion Effects in Resource Allocation Games