On designing truthful mechanisms for online scheduling

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.