TY - GEN
T1 - Prior-free Dynamic Mechanism Design with Limited Liability
AU - Braverman, Mark
AU - Schneider, Jon
AU - Weinberg, S. Matthew
N1 - Publisher Copyright:
© 2021 ACM.
PY - 2021/7/18
Y1 - 2021/7/18
N2 - We study the problem of repeatedly auctioning off an item to one of bidders where: a) bidders have a per-round individual rationality constraint, b) bidders may leave the mechanism at any point, and c) the bidders' valuations are adversarially chosen (the prior-free setting). Without these constraints, the auctioneer can run a second-price auction to sell the business and receive the second highest total value for the entire stream of items. We show that under these constraints, the auctioneer can attain a constant fraction of the sell the business benchmark, but no more than 2/ of this benchmark. In the course of doing so, we design mechanisms for a single bidder problem of independent interest: how should you repeatedly sell an item to a (per-round IR) buyer with adversarial valuations if you know their total value over all rounds is but not how their value changes over time We demonstrate a mechanism that achieves revenue / and show that this is tight.
AB - We study the problem of repeatedly auctioning off an item to one of bidders where: a) bidders have a per-round individual rationality constraint, b) bidders may leave the mechanism at any point, and c) the bidders' valuations are adversarially chosen (the prior-free setting). Without these constraints, the auctioneer can run a second-price auction to sell the business and receive the second highest total value for the entire stream of items. We show that under these constraints, the auctioneer can attain a constant fraction of the sell the business benchmark, but no more than 2/ of this benchmark. In the course of doing so, we design mechanisms for a single bidder problem of independent interest: how should you repeatedly sell an item to a (per-round IR) buyer with adversarial valuations if you know their total value over all rounds is but not how their value changes over time We demonstrate a mechanism that achieves revenue / and show that this is tight.
KW - algorithmic mechanism design
KW - auctions
KW - dynamic mechanisms
UR - http://www.scopus.com/inward/record.url?scp=85111981300&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85111981300&partnerID=8YFLogxK
U2 - 10.1145/3465456.3467654
DO - 10.1145/3465456.3467654
M3 - Conference contribution
AN - SCOPUS:85111981300
T3 - EC 2021 - Proceedings of the 22nd ACM Conference on Economics and Computation
SP - 204
EP - 223
BT - EC 2021 - Proceedings of the 22nd ACM Conference on Economics and Computation
PB - Association for Computing Machinery, Inc
T2 - 22nd ACM Conference on Economics and Computation, EC 2021
Y2 - 18 July 2021 through 23 July 2021
ER -