TY - GEN
T1 - Bayesian Auctions with Efficient Queries (Extended Abstract)
AU - Chen, Jing
AU - Li, Bo
AU - Li, Yingkai
AU - Lu, Pinyan
N1 - Funding Information:
We thank the editor and several anonymous reviewers for their helpful comments. Jing Chen is supported by NSF CAREER Award (No. 1553385). Bo Li is supported by RGC of HKSAR (No. PolyU 25211321), NSFC (No. 62102333) and The Hong Kong Polytechnic University (No. P0034420). Pinyan Lu is supported by Science and Technology Innovation 2030 –“New Generation of Artificial Intelligence” Major Project No.(2018AAA0100903), NSFC grant 61922052 and 61932002, Innovation Program of Shanghai Municipal Education Commission, Program for Innovative Research Team of Shanghai University of Finance and Economics, and the Fundamental Research Funds for the Central Universities. Part of this work was done when the first three authors were visiting Shanghai University of Finance and Economics.
Publisher Copyright:
© 2022 International Joint Conferences on Artificial Intelligence. All rights reserved.
PY - 2022/7
Y1 - 2022/7
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85137938002&partnerID=8YFLogxK
M3 - Conference article published in proceeding or book
AN - SCOPUS:85137938002
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 5708
EP - 5712
BT - Proceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022
A2 - De Raedt, Luc
A2 - De Raedt, Luc
PB - International Joint Conferences on Artificial Intelligence
T2 - 31st International Joint Conference on Artificial Intelligence, IJCAI 2022
Y2 - 23 July 2022 through 29 July 2022
ER -