Bayesian auctions with efficient queries

Jing Chen, Bo Li (Corresponding Author), Yingkai Li, Pinyan Lu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

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.

Original languageEnglish
Article number103630
JournalArtificial Intelligence
Volume303
DOIs
Publication statusPublished - Feb 2022

Keywords

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

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence

Cite this