An Almost Ideal Coordination Mechanism for Unrelated Machine Scheduling

Ioannis Caragiannis () and Angelo Fanelli ()
Additional contact information
Ioannis Caragiannis: Department of Computer Engineering and Informatics [Patras] - University of Patras
Angelo Fanelli: CREM - Centre de recherche en économie et management - UNICAEN - Université de Caen Normandie - NU - Normandie Université - UR - Université de Rennes - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

Abstract: Coordination mechanisms aim to mitigate the impact of selfishness when scheduling jobs to different machines. Such a mechanism defines a scheduling policy within each machine and naturally induces a game among the selfish job owners. The desirable properties of a coordination mechanism includes simplicity in its definition and efficiency of the outcomes of the induced game. We present a broad class of coordination mechanisms for unrelated machine scheduling that are simple to define and we identify one of its members (mechanism DCOORD) that is superior to all known mechanisms. In particular, DCOORD induces potential games with logarithmic price of anarchy and only constant price of stability. Both bounds are almost optimal.

Keywords: Coordination mechanisms; Potential games; Price of anarchy; Price of stability; Scheduling; Unrelated machines (search for similar items in EconPapers)
Date: 2019-01
References: Add references at CitEc
Citations:

Published in Theory of Computing Systems, 2019, 63 (1), pp.114-127. ⟨10.1007/s00224-018-9857-2⟩

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:hal:journl:hal-02089340

DOI: 10.1007/s00224-018-9857-2

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().