Truthful algorithms for scheduling selfish tasks on parallel machines

DOI10.1016/J.TCS.2006.07.057zbMath1140.90025OpenAlexW1512811285MaRDI QIDQ861258

Fanny Pascual, Eric Angel, 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

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

Related Items (16)

Coordination mechanisms ⋮ A parallel machine schedule updating game with compensations and clients averse to uncertain loss ⋮ Nonpreemptive coordination mechanisms for identical machines ⋮ Reducing price of anarchy of selfish task allocation with more selfishness ⋮ Strategic Scheduling Games: Equilibria and Efficiency ⋮ Distributed algorithmic mechanism design for scheduling on unrelated machines ⋮ Non-clairvoyant scheduling games ⋮ 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 ⋮ Improving the price of anarchy for selfish routing via coordination mechanisms ⋮ Truthfulness for the Sum of Weighted Completion Times ⋮ Randomized truthful algorithms for scheduling selfish tasks on parallel machines ⋮ Asynchronous Congestion Games ⋮ On truthfulness and approximation for scheduling selfish tasks ⋮ THE PRICE OF MULTI-ORGANIZATION CONSTRAINT IN UNRELATED PARALLEL MACHINE SCHEDULING ⋮ Two agent scheduling with a central selection mechanism

Cites Work

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

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