We study black-box reductions from mechanism design to algorithm design for welfare maximization in settings of incomplete information. Given oracle access to an algorithm for an underlying optimization problem, the goal is to simulate an incentive compatible mechanism. The mechanism will be evaluated on its expected welfare, relative to the algorithm provided, and its complexity is measured by the time (and queries) needed to simulate the mechanism on any input. While it is known that black-box reductions are not possible in many prior-free settings, settings with priors appear more promising: there are known reductions for Bayesian incentive compatible (BIC) mechanism design for general classes of welfare maximization problems. This dichotomy begs the question: which mechanism design problems admit black-box reductions, and which do not? Our main result is that black-box mechanism design is impossible under two of the simplest settings not captured by known positive results. First, for the problem of allocating @math goods to a single buyer whose valuation is additive and independent across the goods, subject to a downward-closed constraint on feasible allocations, we show that there is no polytime (in @math ) BIC black-box reduction for expected welfare maximization. Second, for the setting of multiple single-parameter agents---where polytime BIC reductions are known---we show that no polytime reductions exist when the incentive requirement is tightened to Max-In-Distributional-Range. In each case, we show that achieving a sub-polynomial approximation to the expected welfare requires exponentially many queries, even when the set of feasible allocations is known to be downward-closed.
We focus primarily on black-box reductions with priors. For the setting without priors, Pass and Seth @cite_9 build upon the impossibility result of Chawla, Immorlica, and Lucier to show that even if the transformation is given access to the underlying problem's feasibility constraint, black-box transformations are still impossible under standard cryptographic assumptions. Suksompong @cite_11 considers the case of downward-closed single-parameter environments, and likewise shows limits on the power of black-box reductions.
@cite_9 @cite_11
310430555 2963986735
A fundamental question in algorithmic mechanism design is whether any approximation algorithm for a single-parameter social-welfare maximization problem can be turned into a dominant-strategy truthful mechanism for the same problem (while preserving the approximation ratio up to a constant factor). A particularly desirable type of transformations—called black-box transformations—achieve the above goal by only accessing the approximation algorithm as a black box. 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, 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 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.