We give the first black-box reduction from arbitrary approximation algorithms to truthful approximation mechanisms for a non-trivial class of multi-parameter problems. Specifically, we prove that every packing problem that admits an FPTAS also admits a truthful-in-expectation randomized mechanism that is an FPTAS. Our reduction makes novel use of smoothed analysis, by employing small perturbations as a tool in algorithmic mechanism design. We develop a ȁC;duality'''' between linear perturbations of the objective function of an optimization problem and of its feasible set, and use the ȁC;primal'''' and ȁC;dual'''' viewpoints to prove the running time bound and the truthfulness guarantee, respectively, for our mechanism.
展开▼
