@inproceedings{5af64f0436714e7492d7f948e4eaa1dd,
title = "An end-to-end argument in mechanism design (Prior-independent auctions for budgeted agents)",
abstract = "This paper considers prior-independent mechanism design, namely identifying a single mechanism that has near optimal performance on every prior distribution. We show that mechanisms with truthtelling equilibria, a.k.a., revelation mechanisms, do not always give optimal prior-independent mechanisms and we define the revelation gap to quantify the non-optimality of revelation mechanisms. This study suggests that it is important to develop a theory for the design of non-revelation mechanisms. Our analysis focuses on welfare maximization by singleitem auctions for agents with budgets and a natural regularity assumption on their distribution of values. The all-pay auction (a non-revelation mechanism) is the Bayesian optimal mechanism; as it is prior-independent it is also the prior-independent optimal mechanism (a 1-approximation). We prove a lower bound on the prior-independent approximation of revelation mechanisms of 1.013 and that the clinching auction (a revelation mechanism) is a prior-independent ϵ ≠ 2.714 approximation. Thus the revelation gap for single-item welfare maximization with public budget agents is in [1.013, e]. Some of our analyses extend to the revenue objective, position environments, and irregular distributions.",
keywords = "Approximation, Budgets, Mechanism design",
author = "Yiding Feng and Hartline, {Jason D}",
note = "Funding Information: This work was supported by NSF CCF-1618502. Publisher Copyright: {\textcopyright} 2018 IEEE.; 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 ; Conference date: 07-10-2018 Through 09-10-2018",
year = "2018",
month = nov,
day = "30",
doi = "10.1109/FOCS.2018.00046",
language = "English (US)",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "404--415",
editor = "Mikkel Thorup",
booktitle = "Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018",
address = "United States",
}