An End-to-end Argument in Mechanism Design (Prior-independent Auctions for Budgeted Agents)
share
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 single-item auctions for agents with budgets and the objectives of welfare and with a natural regularity assumption on the distribution. Our main results show that the all-pay auction (a non-revelation mechanism) is an optimal prior-independent approximation mechanism. The all-pay auction, however, is not a revelation mechanism. We prove that prior-independent approximation of best revelation mechanism is strictly worse than that of the all-pay auction. Thus, the revelation gap is at least a constant. Finally, we show that the clinching auction (a revelation mechanism) is a prior-independent e ≈ 2.714 approximation. Thus the revelation gap is a constant. Many of our analyses extend to the revenue objective, position environments, and irregular distributions.
READ FULL TEXT