Portal de Periódicos da CAPES

Truthful Approximation Mechanisms for Scheduling Selfish Related Machines

2005; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-540-31856-9_6

1611-3349

Nir Andelman, Yossi Azar, Motti Sorani,

Game Theory and Voting Systems

We consider the problem of scheduling jobs on related machines owned by selfish agents. Previously, Archer and Tardos showed a 2-approximation randomized mechanism which is truthful in expectation only (a weaker notion of truthfulness). We provide a 5-approximation deterministic truthful mechanism, the first deterministic truthful result for the problem. In case the number of machines is constant, we provide a deterministic Fully Polynomial Time Approximation Scheme (FPTAS) algorithm, and a suitable payment scheme that yields a truthful mechanism for the problem. This result, which is based on converting FPTAS to monotone FPTAS, improves a previous result of Auletta et al, who showed a (4+ε)-approximation truthful mechanism.