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 language | English (US) |
|---|---|
| Title of host publication | Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |
| Editors | Mikkel Thorup |
| Publisher | IEEE Computer Society |
| Pages | 404-415 |
| Number of pages | 12 |
| ISBN (Electronic) | 9781538642306 |
| DOIs | |
| State | Published - Nov 30 2018 |
| Event | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France Duration: Oct 7 2018 → Oct 9 2018 |
Publication series
| Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
|---|---|
| Volume | 2018-October |
| ISSN (Print) | 0272-5428 |
Other
| Other | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |
|---|---|
| Country | France |
| City | Paris |
| Period | 10/7/18 → 10/9/18 |
Keywords
- Approximation
- Budgets
- Mechanism design
ASJC Scopus subject areas
- Computer Science(all)
Cite this
}
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 proceeding › Conference 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 -