TY - GEN
T1 - A QPTAS For Up-To-ϵ Revenue Maximization With Multiple Constant-Demand Bidders Over Independent Items
AU - Chakarov, Dimitar
AU - Weinberg, S. Matthew
AU - Xue, Eric
N1 - Publisher Copyright:
© 2025 Copyright held by the owner/author(s).
PY - 2025/7/2
Y1 - 2025/7/2
N2 - We study revenue maximization in multi-dimensional auctions with n bidders and m items. When the bidders are constant-demand and either the number of bidders or the number of items is a constant, we give a quasi-polynomial time algorithm that computes an ϵ-Bayesian Incentive Compatible (ϵ-BIC) mechanism that obtains at least a (1 - ϵ) faction of the expected revenue of the optimal Bayesian Incentive Compatible (BIC) mechanism. We obtain this guarantee even when the value distribution of each bidder is unbounded, extending the main result of [Kothari et al., 2019] from a single bidder to multiple bidders.
AB - We study revenue maximization in multi-dimensional auctions with n bidders and m items. When the bidders are constant-demand and either the number of bidders or the number of items is a constant, we give a quasi-polynomial time algorithm that computes an ϵ-Bayesian Incentive Compatible (ϵ-BIC) mechanism that obtains at least a (1 - ϵ) faction of the expected revenue of the optimal Bayesian Incentive Compatible (BIC) mechanism. We obtain this guarantee even when the value distribution of each bidder is unbounded, extending the main result of [Kothari et al., 2019] from a single bidder to multiple bidders.
KW - approximation schemes
KW - mechanism design
KW - revenue maximization
UR - https://www.scopus.com/pages/publications/105011582970
UR - https://www.scopus.com/pages/publications/105011582970#tab=citedBy
U2 - 10.1145/3736252.3742655
DO - 10.1145/3736252.3742655
M3 - Conference contribution
AN - SCOPUS:105011582970
T3 - EC 2025 - Proceedings of the 26th ACM Conference on Economics and Computation
SP - 946
EP - 974
BT - EC 2025 - Proceedings of the 26th ACM Conference on Economics and Computation
PB - Association for Computing Machinery, Inc
T2 - 26th ACM Conference on Economics and Computation, EC 2025
Y2 - 7 July 2025 through 10 July 2025
ER -