Bayesian auctions with efficient queries

Designing dominant-strategy incentive compatible (DSIC) mechanisms for a seller to generate (approximately) optimal revenue by selling items to players is a fundamental problem in Bayesian mechanism design. However, most existing studies assume that the seller knows the entire distribution from which the players' values are drawn. Unfortunately, this assumption may not hold in reality: for example, when the 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. The seller only has limited oracle accesses to the players' distributions, via quantile queries and value queries. For single-item auctions, we design mechanisms with logarithmic number of value or quantile queries which achieve almost optimal revenue. We then prove logarithmic lower-bounds, i. e. , logarithmic number of queries are necessary for any constant approximation DSIC mechanisms, even when randomized and adaptive queries are allowed. Thus our mechanisms are almost optimal regarding query complexity. Our lower-bounds can be extended to multi-item auctions with monotone subadditive valuations, and we complement this part with constant approximation mechanisms for unit-demand or additive valuation functions. Our results are robust even if the answers to the queries contain noises. Thus, in those settings the seller needs to access much less than the entire distribution to achieve approximately optimal revenue.

Authors

• Jing Chen
• Bo Li Department of Computing, The Hong Kong Polytechnic University
• Yingkai Li Department of Economics, National University of Singapore, Singapore
• Pinyan Lu

Keywords

• Mechanism design
• The complexity of Bayesian mechanisms
• Query complexity
• Quantile queries
• Value queries