Selling to a no-regret buyer

Mark Braverman, Jieming Mao, Jon Schneider, Matt Weinberg

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

5 Scopus citations

Abstract

We consider the problem of a single seller repeatedly selling a single item to a single buyer (specifically, the buyer has a value drawn fresh from known distribution D in every round). Prior work assumes that the buyer is fully rational and will perfectly reason about how their bids today affect the seller's decisions tomorrow. In this work we initiate a different direction: the buyer simply runs a no-regret learning algorithm over possible bids. We provide a fairly complete characterization of optimal auctions for the seller in this domain. Specifically: • If the buyer bids according to EXP3 (or any “mean-based” learning algorithm), then the seller can extract expected revenue arbitrarily close to the expected welfare. This auction is independent of the buyer's valuation D, but somewhat unnatural as it is sometimes in the buyer's interest to overbid. • There exists a learning algorithm A such that if the buyer bids according to A then the optimal strategy for the seller is simply to post the Myerson reserve for D every round. • If the buyer bids according to EXP3 (or any “mean-based” learning algorithm), but the seller is restricted to “natural” auction formats where overbidding is dominated (e.g. Generalized First-Price or Generalized Second-Price), then the optimal strategy for the seller is a pay-your-bid format with decreasing reserves over time. Moreover, the seller's optimal achievable revenue is characterized by a linear program, and can be unboundedly better than the best truthful auction yet simultaneously unboundedly worse than the expected welfare.

Original languageEnglish (US)
Title of host publicationACM EC 2018 - Proceedings of the 2018 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages523-538
Number of pages16
ISBN (Electronic)9781450358293
DOIs
StatePublished - Jun 11 2018
Event19th ACM Conference on Economics and Computation, EC 2018 - Ithaca, United States
Duration: Jun 18 2018Jun 22 2018

Publication series

NameACM EC 2018 - Proceedings of the 2018 ACM Conference on Economics and Computation

Other

Other19th ACM Conference on Economics and Computation, EC 2018
CountryUnited States
CityIthaca
Period6/18/186/22/18

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Statistics and Probability
  • Computational Mathematics
  • Economics and Econometrics

Keywords

  • Auctions
  • Mechanism design
  • Multi-armed bandits
  • No-regret learning

Fingerprint Dive into the research topics of 'Selling to a no-regret buyer'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Mao, J., Schneider, J., & Weinberg, M. (2018). Selling to a no-regret buyer. In ACM EC 2018 - Proceedings of the 2018 ACM Conference on Economics and Computation (pp. 523-538). (ACM EC 2018 - Proceedings of the 2018 ACM Conference on Economics and Computation). Association for Computing Machinery, Inc. https://doi.org/10.1145/3219166.3219233