The price of anarchy on uniformly related machines revisited

DOI10.1016/J.IC.2012.01.005MaRDI QIDQ418148zbMATH OpenOpenAlexFDO

Authors 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) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Other game-theoretic models (91A40)

Recommendations

• The Price of Anarchy on Uniformly Related Machines Revisited
• The Price of Anarchy for Minsum Related Machine Scheduling
• The price of anarchy for utilitarian scheduling games on related machines
• The cost of selfishness for maximizing the minimum load on uniformly related machines
• Selfish jobs with favorite machines: price of anarchy vs. strong price of anarchy

Cites work

• scientific article; zbMATH DE number 3139273 (Why is no real title available?)
• scientific article; zbMATH DE number 3466528 (Why is no real title available?)
• scientific article; zbMATH DE number 2038735 (Why is no real title available?)
• scientific article; zbMATH DE number 2109192 (Why is no real title available?)
• A linear time approximation algorithm for multiprocessor scheduling
• Algorithmic mechanism design
• Algorithms, games, and the internet
• An On-Line Algorithm for Some Uniform Processor Scheduling
• Approximate equilibria and ball fusion
• Bounds for LPT Schedules on Uniform Processors
• Bounds for List Schedules on Uniform Processors
• Convergence time to Nash equilibrium in load balancing
• Coordination mechanisms for selfish scheduling
• Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy
• How bad is selfish routing?
• Non-cooperative games
• Performance guarantees of local search for multiprocessor scheduling
• Strong Price of Anarchy for Machine Load Balancing
• Strong equilibrium in congestion games
• Strong equilibrium in cost sharing connection games
• Strong price of anarchy
• The price of selfish routing
• The structure and complexity of Nash equilibria for a selfish routing game
• Tight bounds for worst-case equilibria
• Tighter approximation bounds for LPT scheduling in two special cases
• Worst-case equilibria
• Worst-case equilibria

Cited in

(14)

• Allocation game on \(m\)-uniform parallel machines
• The price of anarchy for utilitarian scheduling games on related machines
• Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines
• Inefficiency of equilibria for the machine covering game on uniform machines
• Price of anarchy for machine load balancing game with 3 machines
• The Price of Anarchy for Minsum Related Machine Scheduling
• Multistage interval scheduling games
• Inefficiency of equilibria for scheduling game with machine activation costs
• Selfish jobs with favorite machines: price of anarchy vs. strong price of anarchy
• On the price of anarchy of two-stage machine scheduling games
• The cost of selfishness for maximizing the minimum load on uniformly related machines
• Inefficiency of Nash equilibrium for scheduling games with constrained jobs: a parametric analysis
• The Price of Anarchy on Uniformly Related Machines Revisited
• Price of anarchy in a linear-state stochastic dynamic game

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q418148)