Prior-free Dynamic Mechanism Design with Limited Liability

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationEC 2021 - Proceedings of the 22nd ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages204-223
Number of pages20
ISBN (Electronic)9781450385541
DOIs
StatePublished - Jul 18 2021
Event22nd ACM Conference on Economics and Computation, EC 2021 - Virtual, Online, Hungary
Duration: Jul 18 2021Jul 23 2021

Publication series

NameEC 2021 - Proceedings of the 22nd ACM Conference on Economics and Computation

Conference

Conference22nd ACM Conference on Economics and Computation, EC 2021
Country/TerritoryHungary
CityVirtual, Online
Period7/18/217/23/21

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Networks and Communications

Keywords

  • algorithmic mechanism design
  • auctions
  • dynamic mechanisms

Fingerprint

Dive into the research topics of 'Prior-free Dynamic Mechanism Design with Limited Liability'. Together they form a unique fingerprint.

Cite this