Paper Info
Title
Scheduling selfish tasks: about the performance of truthful algorithms
Abstract
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.
Year
DOI
Venue
2007
10.1007/978-3-540-73545-8_20
COCOON
Keywords
Field
DocType
selfish task,paper deal,central question,selfish scheduling,maximal completion time,completion time,erroneous information,selfish agent,efficient algorithm,truthful algorithm,distributed system,game theory,scheduling algorithm
Scheduling (computing),Computer science,Lying,Algorithm,Algorithmic game theory,Payment
Conference
Volume
ISSN
ISBN
4598
0302-9743
3-540-73544-5
Citations 
PageRank 
References 
16
0.93
12
Authors
3
Name
Order
Citations
PageRank
George Christodoulou133218.59
Laurent Gourvès224130.97
Fanny Pascual39714.48