TY - GEN
T1 - Prior-free Dynamic Mechanism Design with Limited Liability
AU - Braverman, Mark
AU - Schneider, Jon
AU - Weinberg, S. Matthew
N1 - Funding Information:
M.B. is supported in part by the NSF Alan T. Waterman Award, Grant No. 1933331, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author and do not necessarily reflect the views of the National Science Foundation. S.M.W is supported by NSF CAREER Award CCF-1942497.
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 -