TRUTHFUL APPROXIMATION SCHEMES FOR SINGLE- PARAMETER AGENTS
We present the first monotone randomized polynomial-time approximation scheme (PTAS) for minimizing the makespan of parallel related machines (Q parallel to C(max)), the paradigmatic problem in single-parameter algorithmic mechanism design. This result immediately gives a polynomialtime, truthful (in expectation) mechanism whose approximation guarantee attains the best-possible one for all polynomial-time algorithms (assuming P not equal NP). Our algorithmic techniques are flexible and also yield a monotone deterministic quasi-PTAS for Q parallel to C(max) and a monotone randomized PTAS for max-min scheduling on related machines.
algorithmic mechanism design scheduling algorithm game theory