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.
Titolo: | Deterministic Truthful Mechanism for Scheduling on Selfish Machines |
Autori: | |
Data di pubblicazione: | 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. |
Handle: | http://hdl.handle.net/11386/1067374 |
ISBN: | 3540212361 |
Appare nelle tipologie: | 4.1.2 Proceedings con ISBN |