Black-Box Randomized Reductions in Algorithmic Mechanism Design

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 “duality´´ between linear perturbations of the objective function of an optimization problem and of its feasible set, and use the “primal´´ and “dual´´ viewpoints to prove the running time bound and the truthfulness guarantee, respectively, for our mechanism.