@inproceedings{f7ac9421aea949e18819ec4ab8dacbe9,
title = "Sample complexity for non-truthful mechanisms?",
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.",
keywords = "All-pay auctions, Firstprice auctions, Mechanism design, Non-truthful mechanisms, Position auctions, Sample complexity",
author = "Hartline, {Jason D} and Samuel Taggart",
year = "2019",
month = jun,
day = "17",
doi = "10.1145/3328526.3329632",
language = "English (US)",
series = "ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation",
publisher = "Association for Computing Machinery, Inc",
pages = "399--416",
booktitle = "ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation",
note = "20th ACM Conference on Economics and Computation, EC 2019 ; Conference date: 24-06-2019 Through 28-06-2019",
}