  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 $n$ 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 $n$) 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.
