Abstract

We consider prior-independentmechanism design, namely identifying a single mechanism that has near optimalperformance on every prior distribution. We show that mechanisms withtruthtelling equilibria, a.k.a., revelation mechanisms, do not always give optimalprior-independent mechanisms and we define the revelation gap to quantify thenon-optimality of revelation mechanisms. This study suggests that it isimportant to develop a theory for the design of non-revelation mechanisms. Ouranalysis focuses on welfare maximization in single-item auctions for agentswith budgets and a natural regularity assumption on their distribution ofvalues. The all-pay auction (a non-revelation mechanism) is the Bayesianoptimal mechanism; as it is prior-independent it is also the prior-independentoptimal mechanism (a 1-approximation). We prove a lower bound on theprior-independent approximation of revelation mechanisms of 1.013 and that theclinching auction (a revelation mechanism) is a prior-independent e≈2.714 approximation. Thus therevelation gap for single-item welfare maximization with public budget agentsis in [1.013,e]. Some of our analyses extend to the revenue objective, positionenvironments, and irregular distributions.

Joint work with JasonHartline.

Time

2月26日（周二）14:00-15:00

Speaker

Yiding Feng isa third year PhD in the CS Theory group at Northwestern, working with JasonHartline. His current research focuses on the algorithmic game theory.

Venue

信息管理与工程学院602室

上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号