Decentralized utilitarian mechanisms for scheduling games

DOI10.1016/j.geb.2013.03.011zbMath1356.91006OpenAlexW2057938496WikidataQ65553894 ScholiaQ65553894MaRDI QIDQ2516246

Vasilis Gkatzelis, Neil Olver, José R. Correa, Richard John Cole, Vahab S. Mirrokni

Publication date: 12 August 2015

Published in: Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.geb.2013.03.011

zbMATH Keywords

schedulingprice of anarchycoordination mechanisms

Mathematics Subject Classification ID

Noncooperative games (91A10) Applications of game theory (91A80) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

A selfish allocation heuristic in scheduling: equilibrium and inefficiency bound analysis, Implementation of optimal schedules in outsourcing with identical suppliers, The price of anarchy for utilitarian scheduling games on related machines, Optimal Cost-Sharing in General Resource Selection Games, Integer programming methods to identify Nash equilibrium solutions for platform-based scheduling games, An almost ideal coordination mechanism for unrelated machine scheduling, Scheduling games with machine-dependent priority lists, The price of anarchy of affine congestion games with similar strategies, Introduction to the special issue -- Algorithmic game theory -- STOC/FOCS/SODA 2011, Cost-sharing games in real-time scheduling systems, On the Price of Anarchy of cost-sharing in real-time scheduling systems, Performance guarantees of local search for minsum scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Worst-case equilibria
• Convergence to approximate Nash equilibria in congestion games
• Tight bounds for selfish and greedy load balancing
• Nash equilibria and the price of anarchy for flows over time
• Competitive routing over time
• Stackelberg differential games in economic models
• Coordination mechanisms
• Coordination mechanisms for selfish scheduling
• Self-organizing sequential search and Hilbert's inequalities
• (Incremental) priority algorithms
• How much can taxes help selfish routing?
• Tradeoffs in worst-case equilibria
• A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines
• Non-Approximability Results for Scheduling Problems with Minsum Criteria
• Performance Guarantees of Local Search for Multiprocessor Scheduling
• The Price of Anarchy for Minsum Related Machine Scheduling
• Preemptive Coordination Mechanisms for Unrelated Machines
• Tight bounds for worst-case equilibria
• Existence and Uniqueness of Equilibria for Flows over Time
• A linear time approximation algorithm for multiprocessor scheduling
• Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost
• Taxes for linear atomic congestion games
• Convex quadratic and semidefinite programming relaxations in scheduling
• Tricks or Treats with the Hilbert Matrix
• Convergence time to Nash equilibrium in load balancing
• The price of anarchy of finite congestion games
• Multiagent Systems
• Non-clairvoyant Scheduling Games
• Bounds for List Schedules on Uniform Processors
• Exegesis of Self-Organizing Linear Search
• Algorithms for Scheduling Tasks on Unrelated Processors
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
• The Competitiveness of On-Line Assignments
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Stackelberg Scheduling Strategies
• Scheduling independent tasks to reduce mean finishing time
• Scheduling Unrelated Machines by Randomized Rounding
• Intrinsic robustness of the price of anarchy
• Preference-constrained oriented matching
• Technical Note—Minimizing Average Flow Time with Parallel Machines
• Scheduling
• The Price of Routing Unsplittable Flow
• Computing Nash equilibria for scheduling on restricted parallel links