1. Publications
  2. A $1+\phi$ lower bound for truthful scheduling mechanisms. Elias Koutsoupias and Angelina Vidali, 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS '07).

A $1+\phi$ lower bound for truthful scheduling mechanisms. Elias Koutsoupias and Angelina Vidali, 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS '07).

Elias Koutsoupias and Angelina Vidali, MFCS '07

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.