We consider the problem of scheduling jobs on related machines owned by selfish agents and provide the first deterministic mechanisms with constant approximation that are truthful; that is, truth-telling is a dominant strategy for all agents. More precisely, we present deterministic polynomial-time (2 + epsilon)-approximation algorithms and suitable payment functions that yield truthful mechanisms for several NP-hard restrictions of this problem. Our result also yields a family of deterministic polynomial-time truthful (4+epsilon)-approximation mechanisms for any fixed number of machines. The only previously-known mechanism for this problem (proposed by Archer and Tardos [FOCS 2001]) is 3-approximated, randomized and truthful under a weaker notion of truthfulness. Up to our knowledge, our mechanisms are the first non-trivial polynomial-time deterministic truthful mechanisms for this NP-hard problem. To obtain our results we introduce a technique to transform the PTAS by Graham into a deterministic truthful mechanism.

Deterministic Truthful Mechanism for Scheduling on Selfish Machines

AULETTA, Vincenzo;DE PRISCO, Roberto;PENNA, Paolo;PERSIANO, Giuseppe
2004

Abstract

We consider the problem of scheduling jobs on related machines owned by selfish agents and provide the first deterministic mechanisms with constant approximation that are truthful; that is, truth-telling is a dominant strategy for all agents. More precisely, we present deterministic polynomial-time (2 + epsilon)-approximation algorithms and suitable payment functions that yield truthful mechanisms for several NP-hard restrictions of this problem. Our result also yields a family of deterministic polynomial-time truthful (4+epsilon)-approximation mechanisms for any fixed number of machines. The only previously-known mechanism for this problem (proposed by Archer and Tardos [FOCS 2001]) is 3-approximated, randomized and truthful under a weaker notion of truthfulness. Up to our knowledge, our mechanisms are the first non-trivial polynomial-time deterministic truthful mechanisms for this NP-hard problem. To obtain our results we introduce a technique to transform the PTAS by Graham into a deterministic truthful mechanism.
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/1067374
 Attenzione

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

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