Show simple item record

dc.contributor.authorNguyen Kim, Thang
dc.contributor.authorDürr, Christoph
HAL ID: 5030
ORCID: 0000-0001-8103-5333
dc.contributor.authorCohen, Johanne
HAL ID: 7467
dc.date.accessioned2011-04-26T14:30:58Z
dc.date.available2011-04-26T14:30:58Z
dc.date.issued2011
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6050
dc.language.isoenen
dc.subjectNash equilibriaen
dc.subjectCoordination mechanismsen
dc.subjectScheduling gamesen
dc.subjectAlgorithmic game theoryen
dc.subject.ddc003en
dc.titleNon-clairvoyant Scheduling Gamesen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn a scheduling game, each player owns a job and chooses a machine to execute it. While the social cost is the maximal load over all machines (makespan), the cost (disutility) of each player is the completion time of its own job. In the game, players may follow selfish strategies to optimize their cost and therefore their behaviors do not necessarily lead the game to an equilibrium. Even in the case there is an equilibrium, its makespan might be much larger than the social optimum, and this inefficiency is measured by the price of anarchy—the worst ratio between the makespan of an equilibrium and the optimum. Coordination mechanisms aim to reduce the price of anarchy by designing scheduling policies that specify how jobs assigned to a same machine are to be scheduled. Typically these policies define the schedule according to the processing times as announced by the jobs. One could wonder if there are policies that do not require this knowledge, and still provide a good price of anarchy. This would make the processing times be private information and avoid the problem of truthfulness. In this paper we study these so-called non-clairvoyant policies. In particular, we study the RANDOM policy that schedules the jobs in a random order without preemption, and the EQUI policy that schedules the jobs in parallel using time-multiplexing, assigning each job an equal fraction of CPU time. For these models we study two important questions, the existence of Nash equilibria and the price of anarchy. We show that the game under RANDOM policy is a potential game for uniform machines or for two unrelated machines. However, it is not a potential game for three or more unrelated machines. Moreover, we prove that the game under the EQUI policy is a potential game. Next, we analyze the inefficiency of EQUI policy. Interestingly, the (strong) price of anarchy of EQUI, a non-clairvoyant policy, is asymptotically the same as that of the best strongly local policy—policies in which a machine may look at the processing time of jobs assigned to it. The result also indicates that knowledge of jobs’ characteristics is not necessarily needed.en
dc.relation.isversionofjnlnameTheory of Computing Systems
dc.relation.isversionofjnlvol49
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2011
dc.relation.isversionofjnlpages3-23
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s00224-011-9316-9en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record