Bayesian Auctions with Efficient Queries (Extended Abstract)

Jing Chen, Bo Li, Yingkai Li, Pinyan Lu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

Designing dominant-strategy incentive compatible (DSIC) mechanisms for a seller to generate 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, which may not hold in reality. In this work we consider, for the first time, the query complexity of Bayesian mechanisms. The seller 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.

Original languageEnglish
Title of host publicationProceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022
EditorsLuc De Raedt, Luc De Raedt
PublisherInternational Joint Conferences on Artificial Intelligence
Pages5708-5712
Number of pages5
ISBN (Electronic)9781956792003
Publication statusPublished - Jul 2022
Event31st International Joint Conference on Artificial Intelligence, IJCAI 2022 - Vienna, Austria
Duration: 23 Jul 202229 Jul 2022

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)1045-0823

Conference

Conference31st International Joint Conference on Artificial Intelligence, IJCAI 2022
Country/TerritoryAustria
CityVienna
Period23/07/2229/07/22

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Bayesian Auctions with Efficient Queries (Extended Abstract)'. Together they form a unique fingerprint.

Cite this