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 Citation (Scopus)

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

Feng, Y., & Hartline, J. D. (2018). An end-to-end argument in mechanism design (Prior-independent auctions for budgeted agents). In M. Thorup (Ed.), Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 (pp. 404-415). [8555124] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2018-October). IEEE Computer Society. https://doi.org/10.1109/FOCS.2018.00046
Feng, Yiding ; Hartline, Jason D. / An end-to-end argument in mechanism design (Prior-independent auctions for budgeted agents). Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. editor / Mikkel Thorup. IEEE Computer Society, 2018. pp. 404-415 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).
@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}",
year = "2018",
month = "11",
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",

}

Feng, Y & Hartline, JD 2018, An end-to-end argument in mechanism design (Prior-independent auctions for budgeted agents). in M Thorup (ed.), Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018., 8555124, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, vol. 2018-October, IEEE Computer Society, pp. 404-415, 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, 10/7/18. https://doi.org/10.1109/FOCS.2018.00046

An end-to-end argument in mechanism design (Prior-independent auctions for budgeted agents). / Feng, Yiding; Hartline, Jason D.

Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. ed. / Mikkel Thorup. IEEE Computer Society, 2018. p. 404-415 8555124 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2018-October).

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

TY - GEN

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

AU - Feng, Yiding

AU - Hartline, Jason D

PY - 2018/11/30

Y1 - 2018/11/30

N2 - 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.

AB - 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.

KW - Approximation

KW - Budgets

KW - Mechanism design

UR - http://www.scopus.com/inward/record.url?scp=85059817706&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059817706&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2018.00046

DO - 10.1109/FOCS.2018.00046

M3 - Conference contribution

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 404

EP - 415

BT - Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018

A2 - Thorup, Mikkel

PB - IEEE Computer Society

ER -

Feng Y, Hartline JD. An end-to-end argument in mechanism design (Prior-independent auctions for budgeted agents). In Thorup M, editor, Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. IEEE Computer Society. 2018. p. 404-415. 8555124. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2018.00046