An end-to-end argument in mechanism design (prior-independent auctions for budgeted agents)

Yiding Feng, Jason D. Hartline

Research output: Contribution to journalArticlepeer-review

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 priorindependent 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 in single-item auctions for agents with budgets and a natural regularity assumption on their distribution of values. The all-pay auction (a nonrevelation 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 e ~ 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.

Original languageEnglish (US)
JournalUnknown Journal
StatePublished - Apr 5 2018

ASJC Scopus subject areas

  • General

Fingerprint Dive into the research topics of 'An end-to-end argument in mechanism design (prior-independent auctions for budgeted agents)'. Together they form a unique fingerprint.

Cite this