Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


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. To argue that our perturbation schemes are incentive-compatible, we develop a ?duality? between linear perturbations of the objective function of an optimization problem and of its feasible set. Viewed from the dual perspective, our mechanisms are maximal-in-distributional-range and hence truthful in expectation.

Questions and Answers

You need to be logged in to be able to post here.