2019-02-26 | Yiding Feng:An End-to-end Argument in Mechanism Design

2019-02-26   


Abstract

We consider 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 in single-item 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 e2.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.


Joint work with Jason Hartline.

 

Time

226日(周二)14:00-15:00

 

Speaker

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

 

Venue

信息管理与工程学院602

上海财经大学(第三教学楼西侧)

上海市杨浦区武东路100