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

Yiding Feng, Jason D Hartline

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

1 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
EditorsMikkel Thorup
PublisherIEEE Computer Society
Pages404-415
Number of pages12
ISBN (Electronic)9781538642306
DOIs
StatePublished - Nov 30 2018
Event59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France
Duration: Oct 7 2018Oct 9 2018

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2018-October
ISSN (Print)0272-5428

Other

Other59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
CountryFrance
CityParis
Period10/7/1810/9/18

Keywords

  • Approximation
  • Budgets
  • Mechanism design

ASJC Scopus subject areas

  • Computer Science(all)

Cite this