A Lower Bound of 1+phi for Truthful Scheduling Mechanisms
We study the mechanism design version of the unrelated machines scheduling problem, which is at the core of Algorithmic Game Theory and was first proposed and studied in a seminal paper of Nisan and Ronen. We give an improved lower bound of 1+phi a parts per thousand 2.618 on the approximation ratio of deterministic truthful mechanisms for the makespan. The proof is based on a recursive preprocessing argument which yields a strictly increasing series of new lower bounds for each fixed number of machines na parts per thousand yen4.
lower bound truthful mechanism design algorithmic game theory scheduling unrelated machines dominant strategies multiparameter mechanism design