  Generating good revenue is one of the most important problems in Bayesian
auction design, and many (approximately) optimal dominant-strategy incentive
compatible (DSIC) Bayesian mechanisms have been constructed for various auction
settings. However, most existing studies do not consider the complexity for the
seller to carry out the mechanism. It is assumed that the seller knows "each
single bit" of the distributions and is able to optimize perfectly based on the
entire distributions. Unfortunately, this is a strong assumption and may not
hold in reality: for example, when the value distributions have exponentially
large supports or do not have succinct representations.
  In this work we consider, for the first time, the query complexity of
Bayesian mechanisms. We only allow the seller to have limited oracle accesses
to the players' value distributions, via quantile queries and value queries.
For a large class of auction settings, we prove logarithmic lower-bounds for
the query complexity for any DSIC Bayesian mechanism to be of any constant
approximation to the optimal revenue. For single-item auctions and multi-item
auctions with unit-demand or additive valuation functions, we prove tight
upper-bounds via efficient query schemes, without requiring the distributions
to be regular or have monotone hazard rate. Thus, in those auction settings the
seller needs to access much less than the full distributions in order to
achieve approximately optimal revenue.
