Scheduling selfish tasks: about the performance of truthful algorithms
Christodoulou, George; Gourvès, Laurent; Pascual, Fanny (2007), Scheduling selfish tasks: about the performance of truthful algorithms, in Lin, Guohui, Computing and Combinatorics 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings, Springer : Berlin, p. 187-197. http://dx.doi.org/10.1007/978-3-540-73545-8_20
TypeCommunication / Conférence
Conference title13th Annual International Conference on Computing and Combinatorics (COCOON 2007)
Book titleComputing and Combinatorics 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings
Book authorLin, Guohui
Series titleLecture Notes in Computer Science
Number of pages570
MetadataShow full item record
Abstract (EN)This paper deals with problems which fall into the domain of selfish scheduling: a protocol is in charge of building a schedule for a set of tasks without directly knowing their length. The protocol gets these informations from agents who control the tasks. The aim of each agent is to minimize the completion time of her task while the protocol tries to minimize the maximal completion time. When an agent reports the length of her task, she is aware of what the others bid and also of the protocol’s algorithm. Then, an agent can bid a false value in order to optimize her individual objective function. With erroneous information, even the most efficient algorithm may produce unreasonable solutions. An algorithm is truthful if it prevents the selfish agents from lying about the length of their task. The central question in this paper is: “How efficient a truthful algorithm can be? We study the problem of scheduling selfish tasks on parallel identical machines. This question has been raised by Christodoulou et al  in a distributed system, but it is also relevant in centrally controlled systems. Without considering side payments, our goal is to give a picture of the performance under the condition of truthfulness.
Subjects / Keywordsscheduling; algorithmic game theory; truthful algorithms
Showing items related by title and author.
Spanjaard, Olivier; Pascual, Fanny; Nguyen Kim, Thang; Gourvès, Laurent; Escoffier, Bruno (2011) Communication / Conférence