Computer Science

The Query Complexity of Bayesian Auctions

TitleThe Query Complexity of Bayesian Auctions
Publication TypeReport
Year of Publication *Required2017
AuthorsChen, J, Li, B, Li, Y, Lu, P
InstitutionStony Brook University
Keywordsmechanism design, quantile queries, query complexity, the complexity of Bayesian mechanisms, value queries

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 assumption is very strong and may not hold in reality. For example, when the value distributions have exponentially large supports or do not have succinct representations, it is unclear how to find the optimal allocation and prices in many existing mechanisms.

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 a constant approximation to the optimal revenue. For single-item auctions, unit-demand auctions and additive auctions, we prove tight upper-bounds for the query complexity by constructing efficient DSIC Bayesian mechanisms. Finally, we show how to use our results to construct sampling mechanisms that use polynomially many samples from the distributions. Indeed, we provide the first constructive sampling mechanisms for unit-demand auctions and additive auctions.

ID prefix: 
TR Document: 
Unique ID: