Truthful Approximation Schemes for Single-Parameter Agents

Abstract

We present the first monotone randomized polynomial-time approximation scheme (PTAS) for minimizing the makespan of parallel related machines (Q||C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">max</sub> ), the paradigmatic problem in single-parameter algorithmic mechanism design. This result immediately gives a polynomial-time, truthful (in expectation) mechanism whose approximation guarantee attains the best-possible one for all polynomial-time algorithms (assuming P not equal to NP). Our algorithmic techniques are flexible and also yield, among other results, a monotone deterministic quasi-PTAS for Q||C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">max</sub> and a monotone randomized PTAS for max-min scheduling on related machines.