
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
View/ Open
Type
Communication / ConférenceDate
2007Conference title
13th Annual International Conference on Computing and Combinatorics (COCOON 2007)Conference date
2007-07Conference city
BanffConference country
CanadaBook title
Computing and Combinatorics 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, ProceedingsBook author
Lin, GuohuiPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
4598Published in
Berlin
ISBN
978-3-540-73544-1
Number of pages
570Pages
187-197
Publication identifier
Metadata
Show full item recordAbstract (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 [8] 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 / Keywords
scheduling; algorithmic game theory; truthful algorithmsRelated items
Showing items related by title and author.
-
Spanjaard, Olivier; Pascual, Fanny; Nguyen Kim, Thang; Gourvès, Laurent; Escoffier, Bruno (2011) Communication / Conférence
-
Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny; Vanderpooten, Daniel (2017) Article accepté pour publication ou publié
-
Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny (2013) Article accepté pour publication ou publié
-
Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny (2012) Communication / Conférence
-
Ferraioli, Diodato; Gourvès, Laurent; Moretti, Stefano; Pascual, Fanny; Spanjaard, Olivier (2014) Chapitre d'ouvrage