Sample complexity for non-truthful mechanisms?

Jason D Hartline, Samuel Taggart

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

21 Scopus citations

Abstract

This paper considers the design of non-truthful mechanisms from samples. We identify a parameterized family of mechanisms with strategically simple winner-pays-bid, all-pay, and truthful payment formats. In general (not necessarily downward-closed) single-parameter feasibility environments we prove that the family has low representation and generalization error. Specifically, polynomially many bid samples suffice to identify and run a mechanism that is ∈-close in Bayes-Nash equilibrium revenue or welfare to that of the optimal truthful mechanism.

Original languageEnglish (US)
Title of host publicationACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages399-416
Number of pages18
ISBN (Electronic)9781450367929
DOIs
StatePublished - Jun 17 2019
Event20th ACM Conference on Economics and Computation, EC 2019 - Phoenix, United States
Duration: Jun 24 2019Jun 28 2019

Publication series

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

Conference

Conference20th ACM Conference on Economics and Computation, EC 2019
Country/TerritoryUnited States
CityPhoenix
Period6/24/196/28/19

Keywords

  • All-pay auctions
  • Firstprice auctions
  • Mechanism design
  • Non-truthful mechanisms
  • Position auctions
  • Sample complexity

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Sample complexity for non-truthful mechanisms?'. Together they form a unique fingerprint.

Cite this