We reveal a connection between coordination mechanisms for unrelated machine scheduling and cost-sharing protocols. Using this connection, we interpret three coordination mechanisms from the recent literature as Shapley-value-based cost-sharing protocols, thus providing a unifying justification regarding why these mechanisms induce potential games. More importantly, this connection provides a template for designing novel coordination mechanisms, as well as approximation algorithms for the underlying optimization problem. The designer need only decide the total cost to be suffered on each machine, and then the Shapley value can be used to induce games guaranteed to possess a potential function; these games can, in turn, be used to design algorithms. To verify the power of this approach, we design a combinatorial algorithm that achieves an approximation guarantee of 1.81 for the problem of minimizing the total weighted completion time for unrelated machines. To the best of our knowledge, this is the best approximation guarantee among combinatorial polynomial-time algorithms for this problem.

Coordination mechanisms, cost-sharing, and approximation algorithms for scheduling

Vinci C.
2017-01-01

Abstract

We reveal a connection between coordination mechanisms for unrelated machine scheduling and cost-sharing protocols. Using this connection, we interpret three coordination mechanisms from the recent literature as Shapley-value-based cost-sharing protocols, thus providing a unifying justification regarding why these mechanisms induce potential games. More importantly, this connection provides a template for designing novel coordination mechanisms, as well as approximation algorithms for the underlying optimization problem. The designer need only decide the total cost to be suffered on each machine, and then the Shapley value can be used to induce games guaranteed to possess a potential function; these games can, in turn, be used to design algorithms. To verify the power of this approach, we design a combinatorial algorithm that achieves an approximation guarantee of 1.81 for the problem of minimizing the total weighted completion time for unrelated machines. To the best of our knowledge, this is the best approximation guarantee among combinatorial polynomial-time algorithms for this problem.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4785751
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? ND
social impact