On truthfulness and approximation for scheduling selfish tasks

DOI10.1007/S10951-009-0118-8MaRDI QIDQ1041343zbMATH OpenOpenAlexFDO

Authors Eric Angel, Evripidis Bampis, Fanny Pascual, Alex-Ariel Tchetgnia

Publication date 2 December 2009

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10951-009-0118-8

zbMATH Keywords

approximation algorithmsgame theoryschedulingtruthfulness

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Other game-theoretic models (91A40)

Recommendations

• Truthful algorithms for scheduling selfish tasks on parallel machines
• Randomized truthful algorithms for scheduling selfish tasks on parallel machines
• Randomized truthful algorithms for scheduling selfish tasks on parallel machines
• Truthful approximation mechanisms for scheduling selfish related machines
• STACS 2005

Cites work

• Algorithmic mechanism design
• Automata, Languages and Programming
• Bounds on Multiprocessing Timing Anomalies
• Incentives in Teams
• Scheduling Parallel Machines On-Line
• Scheduling Selfish Tasks: About the Performance of Truthful Algorithms
• Setting lower bounds on truthfulness (extended abstract)
• STACS 2004
• STACS 2005
• Truthful algorithms for scheduling selfish tasks on parallel machines
• Worst-case equilibria

Cited in

(26)

• Maximizing the minimum load for selfish agents
• Scheduling without payments
• Incentive compatible mechanisms for scheduling two-parameter job agents on parallel identical machines to minimize the weighted number of late jobs
• The anarchy of scheduling without money
• Truthful approximation mechanisms for scheduling selfish related machines
• Truthfulness for the sum of weighted completion times
• The anarchy of scheduling without money
• Recent developments in the mechanism design problem for scheduling
• Scheduling without payments
• Private Capacities in Mechanism Design
• A Characterization of 2-Player Mechanisms for Scheduling
• Randomized truthful algorithms for scheduling selfish tasks on parallel machines
• Scheduling Selfish Tasks: About the Performance of Truthful Algorithms
• Reducing price of anarchy of selfish task allocation with more selfishness
• Fair resource allocation for different scenarios of demands
• Truthful prompt scheduling for minimizing sum of completion times
• Truthful Mechanisms for Allocating a Single Processor to Sporadic Tasks in Competitive Real-Time Environments
• Mechanism design with uncertain inputs, (to err is human, to forgive divine)
• Preemptive Scheduling on Selfish Machines
• Prior-independent mechanisms for scheduling
• Structural Information and Communication Complexity
• STACS 2005
• Randomized truthful algorithms for scheduling selfish tasks on parallel machines
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity
• On designing truthful mechanisms for online scheduling
• Truthful algorithms for scheduling selfish tasks on parallel machines

This page was built for publication: On truthfulness and approximation for scheduling selfish tasks

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