Inefficiency of Nash equilibrium for scheduling games with constrained jobs: a parametric analysis

DOI10.1016/j.tcs.2013.11.012zbMath1307.91014OpenAlexW2044696947MaRDI QIDQ389954

Ling Lin, Zhiyi Tan

Publication date: 22 January 2014

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

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

zbMATH Keywords

Nash equilibriumprice of anarchyscheduling game

Mathematics Subject Classification ID

Noncooperative games (91A10) Deterministic scheduling theory in operations research (90B35)

Related Items (4)

Efficiency analysis with respect to the unit cost objectives in scheduling games ⋮ Inefficiency analysis of the scheduling game on limited identical machines with activation costs ⋮ On the price of anarchy of two-stage machine scheduling games ⋮ Tighter price of anarchy for selfish task allocation on selfish machines

Cites Work

• Unnamed Item
• Maximizing the minimum load: the cost of selfishness
• 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
• Inefficiency of equilibria for the machine covering game on uniform machines
• The structure and complexity of Nash equilibria for a selfish routing game
• Utilitarian resource assignment
• The cost of selfishness for maximizing the minimum load on uniformly related machines
• Efficiency analysis of load balancing games with and without activation costs
• Performance Guarantees of Local Search for Multiprocessor Scheduling
• Tight bounds for worst-case equilibria
• A linear time approximation algorithm for multiprocessor scheduling

This page was built for publication: Inefficiency of Nash equilibrium for scheduling games with constrained jobs: a parametric analysis