• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Non-clairvoyant Scheduling Games

Nguyen Kim, Thang; Dürr, Christoph; Cohen, Johanne (2011), Non-clairvoyant Scheduling Games, Theory of Computing Systems, 49, 1, p. 3-23. http://dx.doi.org/10.1007/s00224-011-9316-9

View/Open
non-clairvoyant.PDF (236.7Kb)
Type
Article accepté pour publication ou publié
Date
2011
Journal name
Theory of Computing Systems
Volume
49
Number
1
Publisher
Springer
Pages
3-23
Publication identifier
http://dx.doi.org/10.1007/s00224-011-9316-9
Metadata
Show full item record
Author(s)
Nguyen Kim, Thang
Dürr, Christoph cc
Cohen, Johanne
Abstract (EN)
In 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.
Subjects / Keywords
Nash equilibria; Coordination mechanisms; Scheduling games; Algorithmic game theory

Related items

Showing items related by title and author.

  • Thumbnail
    Online scheduling of bounded length jobs to maximize throughput 
    Nguyen Kim, Thang; Lukasz, Jez; Dürr, Christoph (2012) Article accepté pour publication ou publié
  • Thumbnail
    Online Non-preemptive Scheduling on Unrelated Machines with Rejections 
    Lucarelli, Giorgio; Moseley, Benjamin; Thang, Nguyen Kim; Srivastav, Abhinav; Trystram, Denis (2018) Communication / Conférence
  • Thumbnail
    Improved Online Scheduling in Maximizing Throughput of Equal Length Jobs 
    Nguyen Kim, Thang (2011) Communication / Conférence
  • Thumbnail
    Tile-Packing Tomography Is NP-hard 
    Chrobak, Marek; Dürr, Christoph; Guinez, Flavio; Lozano, Antoni; Thang, Nguyen Kim (2012) Article accepté pour publication ou publié
  • Thumbnail
    Congestion Games with Capacitated Resources 
    Gourvès, Laurent; Monnot, Jérôme; Moretti, Stefano; Kim Thang, Nguyen (2012) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo