On Black-Box Transformations in Downward-Closed Environments
arXiv:1707.00230 · doi:10.1007/s00224-018-9898-6
Abstract
Black-box transformations have been extensively studied in algorithmic mechanism design as a generic tool for converting algorithms into truthful mechanisms without degrading the approximation guarantees. While such transformations have been designed for a variety of settings, Chawla et al. showed that no fully general black-box transformation exists for single-parameter environments. In this paper, we investigate the potentials and limits of black-box transformations in the prior-free (i.e., non-Bayesian) setting in \emph{downward-closed} single-parameter environments, a large and important class of environments in mechanism design. On the positive side, we show that such a transformation can preserve a constant fraction of the welfare at every input if the private valuations of the agents take on a constant number of values that are far apart, while on the negative side, we show that this task is not possible for general private valuations.
To appear in the 10th International Symposium on Algorithmic Game Theory (SAGT), 2017