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

algorithmic game theorycoordination mechanismmechanism designschedulingtruthful algorithm

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Deterministic scheduling theory in operations research (90B35) 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

(25)

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

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)