Computing on Strategic Inputs

摘要

Abstract Algorithmic mechanism design centers around the following question: How much harder is optimizing an objective over inputs that are furnished by strategic agents compared to when the inputs to the optimization are known? The challenge is that, when agents controlling the inputs care about the output of the optimization, they may misreport them to influence the output How does one take into account strategic behavior in optimization? We present computationally efficient, approximation-preserving reductions from mechanism design (i.e.optimizing over strategic inputs) to algorithm design (i.e. optimizing over known inputs) in general Bayesian settings. We also explore whether structural properties about optimal mechanisms can be inferred from these reductions. As an application, we present extensions of Myerson's celebrated single-item auction to multi-item settings.