Portal de Periódicos da CAPES

Truthful Approximation Mechanisms for Scheduling Selfish Related Machines

2007; Springer Science+Business Media; Volume: 40; Issue: 4 Linguagem: Inglês

10.1007/s00224-006-1316-9

1433-0490

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. We provide a 5-approximation deterministic truthful mechanism, the first deterministic truthful result for the problem. Previously, Archer and Tardos showed a 2-approximation randomized mechanism which is truthful in expectation only (a weaker notion of truthfulness). In case the number of machines is constant, we provide a deterministic Fully Polynomial-Time Approximation Scheme (FPTAS) 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.