2021/03/02 by Mark Braverman, Jon Schneider, Braverman, Mark +3
Computer Science · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Economics and business #Theoretical Economics (econ.TH) #cs.GT #econ.TH
paper · pdf · doi:10.48550/arxiv.2103.01868
arxiv created 2021/03/02 · arxiv updated 2021/03/03
We study the problem of repeatedly auctioning off an item to one of k 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/e 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 V but not how their value changes over time? We demonstrate a mechanism that achieves revenue V/e and show that this is tight.