Maximizing the minimum load: the cost of selfishness

DOI10.1016/j.tcs.2013.02.033zbMath1291.90090OpenAlexW4206158564MaRDI QIDQ390908

Rob van Stee, Leah Epstein, Elena Kleiman, Xu-jin Chen

Publication date: 9 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.02.033

zbMATH Keywords

schedulingprice of anarchymachine coveringenvy-ratio

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (9)

Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy ⋮ Inefficiency of Nash equilibrium for scheduling games with constrained jobs: a parametric analysis ⋮ Maximizing the minimum load: the cost of selfishness ⋮ Coordination mechanisms for scheduling games with proportional deterioration ⋮ Symmetry exploitation for online machine covering with bounded migration ⋮ Inefficiency of equilibria for the machine covering game on uniform machines ⋮ 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 ⋮ On the sequential price of anarchy of isolation games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximizing the minimum load: the cost of selfishness
• Inefficiency of equilibria for the machine covering game on uniform machines
• A performance guarantee for the greedy set-partitioning algorithm
• The structure and complexity of Nash equilibria for a selfish routing game
• The price of selfish routing
• Maximizing the minimum load for selfish agents
• The cost of selfishness for maximizing the minimum load on uniformly related machines
• Non-cooperative games
• A Unified Approach to Truthful Scheduling on Related Machines
• Performance Guarantees of Local Search for Multiprocessor Scheduling
• The Santa Claus problem
• Tight bounds for worst-case equilibria
• A linear time approximation algorithm for multiprocessor scheduling
• Truthful Approximation Schemes for Single-Parameter Agents
• How bad is selfish routing?
• The Price of Stability for Network Design with Fair Cost Allocation
• Convergence time to Nash equilibrium in load balancing
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Bounds on Multiprocessing Timing Anomalies
• Approximation and Online Algorithms
• Algorithmic mechanism design

This page was built for publication: Maximizing the minimum load: the cost of selfishness