The price of anarchy on uniformly related machines revisited

DOI10.1016/j.ic.2012.01.005zbMath1238.90063OpenAlexW2005432425MaRDI QIDQ418148

Leah Epstein, Rob van Stee

Publication date: 24 May 2012

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.01.005

zbMATH Keywords

schedulingprice of anarchyrelated machines

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Other game-theoretic models (91A40) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (7)

Inefficiency of Nash equilibrium for scheduling games with constrained jobs: a parametric analysis ⋮ Inefficiency of equilibria for scheduling game with machine activation costs ⋮ Price of anarchy in a linear-state stochastic dynamic game ⋮ Inefficiency of equilibria for the machine covering game on uniform machines ⋮ Multistage interval scheduling games ⋮ On the price of anarchy of two-stage machine scheduling games ⋮ Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• The price of selfish routing
• Strong price of anarchy
• Coordination mechanisms for selfish scheduling
• Tighter approximation bounds for LPT scheduling in two special cases
• Strong equilibrium in congestion games
• Approximate equilibria and ball fusion
• Non-cooperative games
• Performance Guarantees of Local Search for Multiprocessor Scheduling
• Tight bounds for worst-case equilibria
• A linear time approximation algorithm for multiprocessor scheduling
• How bad is selfish routing?
• Convergence time to Nash equilibrium in load balancing
• Bounds for List Schedules on Uniform Processors
• Bounds for LPT Schedules on Uniform Processors
• An On-Line Algorithm for Some Uniform Processor Scheduling
• Algorithms, games, and the internet
• Strong Price of Anarchy for Machine Load Balancing
• Algorithmic mechanism design

This page was built for publication: The price of anarchy on uniformly related machines revisited