Abstract:

We give an improved lower bound for the approximation ratio of truthful mechanisms for the unrelated machines scheduling problem. The mechanism design version of the problem which was proposed and studied in the seminal paper of Nisan and Ronen is at the core of the emerging area of Algorithmic Game Theory. The new lower bound is a step towards the final resolution of this important problem.

Postscript

Pdf

BibTeX