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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
