Strategic Scheduling Games: Equilibria and Efficiency

Laurent Gourvès (), Jérôme Monnot () and Orestis A. Telelis ()
Additional contact information
Laurent Gourvès: Université de Paris-Dauphine
Jérôme Monnot: Université de Paris-Dauphine
Orestis A. Telelis: Center for Mathematics and Computer Science (CWI)

Chapter Chapter 10 in Just-in-Time Systems, 2012, pp 209-244 from Springer

Abstract: Abstract Motivated by today’s decentralized operation of interconnected computing platforms, classical task scheduling models are revisited under a game theoretic perspective. Instead of being designed by a central entity which aims at optimizing an aggregate efficiency measure, task allocations emerge through aggregated localized decisions taken by a group of autonomous self-interested agents. The outcome is sought as an equilibrium whose overall social efficiency typically diverges from the optimal group’s choice. This divergence, captured by a measure that came to be known as the Price of Anarchy, can be alleviated by local scheduling policies called Coordination Mechanisms. This chapter reviews standard task scheduling models, dedicated coordination mechanisms and their influence on the price of anarchy. It also exemplifies the design and analysis of coordination mechanisms on a particular scheduling model with setup times, and discusses open research questions.

Keywords: Nash Equilibrium; Completion Time; Coordination Mechanism; Strategy Profile; Strategic Game (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-1-4614-1123-9_10

Ordering information: This item can be ordered from
http://www.springer.com/9781461411239

DOI: 10.1007/978-1-4614-1123-9_10

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().