Truthful algorithms for scheduling selfish tasks on parallel machines

DOI10.1016/J.TCS.2006.07.057MaRDI QIDQ861258zbMATH OpenOpenAlexFDO

Authors Eric Angel, Fanny Pascual, Evripidis Bampis

Publication date 9 January 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.07.057

zbMATH Keywords

schedulingmechanism designalgorithmic game theorycoordination mechanismtruthful algorithm

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Games involving graphs (91A43)

Recommendations

• On truthfulness and approximation for scheduling selfish tasks
• Randomized truthful algorithms for scheduling selfish tasks on parallel machines
• Randomized truthful algorithms for scheduling selfish tasks on parallel machines
• Scheduling Selfish Tasks: About the Performance of Truthful Algorithms
• Truthful approximation mechanisms for scheduling selfish related machines

Cites work

• Algorithmic mechanism design (extended abstract)
• Algorithms – ESA 2005
• Approximation and Online Algorithms
• Automata, Languages and Programming
• Automata, Languages and Programming
• Bounds on Multiprocessing Timing Anomalies
• Coordination mechanisms for selfish scheduling
• Incentives in Teams
• STACS 2004
• STACS 2005
• Structural Information and Communication Complexity

Cited in

(24)

• A parallel machine schedule updating game with compensations and clients averse to uncertain loss
• Scheduling selfish jobs on multidimensional parallel machines
• Scheduling tasks from selfish multi-tasks agents
• Reducing price of anarchy of selfish task allocation with more selfishness
• Strategic scheduling games: equilibria and efficiency
• Asynchronous congestion games
• Coordination mechanisms
• Randomized truthful algorithms for scheduling selfish tasks on parallel machines
• Truthful Mechanisms for Allocating a Single Processor to Sporadic Tasks in Competitive Real-Time Environments
• Non-clairvoyant scheduling games
• The anarchy of scheduling without money
• The price of multi-organization constraint in unrelated parallel machine scheduling
• Nonpreemptive coordination mechanisms for identical machines
• Randomized truthful algorithms for scheduling selfish tasks on parallel machines
• On truthfulness and approximation for scheduling selfish tasks
• Decentralization and Mechanism Design for Online Machine Scheduling
• Two agent scheduling with a central selection mechanism
• Competitive multi-agent scheduling with an iterative selection rule
• Preemptive Scheduling on Selfish Machines
• Incentive compatible mechanisms for scheduling two-parameter job agents on parallel identical machines to minimize the weighted number of late jobs
• Distributed algorithmic mechanism design for scheduling on unrelated machines
• Truthfulness for the sum of weighted completion times
• Scheduling Selfish Tasks: About the Performance of Truthful Algorithms
• The anarchy of scheduling without money

This page was built for publication: Truthful algorithms for scheduling selfish tasks on parallel machines

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