We study the online version of the scheduling problem View the MathML source involving selfish agents, considered by Archer and Tardos in [A. Archer, E. Tardos, Truthful mechanisms for one-parameter agents, in: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), 2001, pp. 482–491], where jobs must be scheduled on m related machines, each of them owned by a different selfish agent. We present a general technique for transforming competitive online algorithms for View the MathML source into truthful online mechanisms with a small loss of competitiveness. We also investigate the issue of designing new online algorithms from scratch so as to obtain efficient competitive mechanisms, and prove some lower bounds on a class of “natural” algorithms. A “direct” use of such natural algorithms to construct truthful mechanisms yields only trivial upper bounds for the case of two machines. Finally, we consider mechanisms with verification, introduced by Nisan and Ronen [N. Nisan, A. Ronen, Algorithmic mechanism design, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, STOC, 1999, pp. 129–140], for offline scheduling problems. We present the first constant-competitive online truthful mechanism with verification for any number of machines.
On designing truthful mechanisms for online scheduling
AULETTA, Vincenzo;DE PRISCO, Roberto;PENNA, Paolo;
2009-01-01
Abstract
We study the online version of the scheduling problem View the MathML source involving selfish agents, considered by Archer and Tardos in [A. Archer, E. Tardos, Truthful mechanisms for one-parameter agents, in: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), 2001, pp. 482–491], where jobs must be scheduled on m related machines, each of them owned by a different selfish agent. We present a general technique for transforming competitive online algorithms for View the MathML source into truthful online mechanisms with a small loss of competitiveness. We also investigate the issue of designing new online algorithms from scratch so as to obtain efficient competitive mechanisms, and prove some lower bounds on a class of “natural” algorithms. A “direct” use of such natural algorithms to construct truthful mechanisms yields only trivial upper bounds for the case of two machines. Finally, we consider mechanisms with verification, introduced by Nisan and Ronen [N. Nisan, A. Ronen, Algorithmic mechanism design, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, STOC, 1999, pp. 129–140], for offline scheduling problems. We present the first constant-competitive online truthful mechanism with verification for any number of machines.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
