Non-clairvoyant scheduling games

DOI10.1007/s00224-011-9316-9zbMath1232.91081arXiv1101.1256MaRDI QIDQ647492

Johanne Cohen, Christoph Dürr, Thang Nguyen Kim

Publication date: 23 November 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1101.1256

zbMATH Keywords

Nash equilibria; algorithmic game theory; coordination mechanisms; scheduling games

Mathematics Subject Classification ID

91A80: Applications of game theory

90B35: Deterministic scheduling theory in operations research

91A40: Other game-theoretic models

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Related Items

Congestion games with priority-based scheduling, Coordination mechanisms for scheduling games with machine modification, Partition equilibrium always exists in resource selection games, \(\mathcal{NP}\)-hardness of pure Nash equilibrium in scheduling and network design games, A coordination mechanism for a scheduling game with parallel-batching machines, On the price of anarchy of two-stage machine scheduling games, Multistage interval scheduling games, Coordinating oligopolistic players in unrelated machine scheduling, Optimal Coordination Mechanisms for Unrelated Machine Scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Worst-case equilibria
• Truthful algorithms for scheduling selfish tasks on parallel machines
• Coordination mechanisms for selfish scheduling
• Potential games
• Tradeoffs in worst-case equilibria
• Non-cooperative games
• Performance Guarantees of Local Search for Multiprocessor Scheduling
• A linear time approximation algorithm for multiprocessor scheduling
• Scheduling Independent Tasks on Uniform Processors
• Convergence time to Nash equilibrium in load balancing
• On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
• Tighter Bounds for LPT Scheduling on Uniform Processors
• Bounds for List Schedules on Uniform Processors
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
• The Competitiveness of On-Line Assignments
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Strong Price of Anarchy for Machine Load Balancing
• Automata, Languages and Programming
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Scheduling in the dark
• Computing Nash equilibria for scheduling on restricted parallel links