Revelation Gap in Prior-independent Mechanism Design

Feng, Yiding

doi:https://doi.org/10.21985/n2-79h4-2k96

Work

Revelation Gap in Prior-independent Mechanism Design

Public

Download PDF

Download All Files (.zip)

Motivated by real-world problems in various fields, mechanism design governs the design of protocols for strategic agents and has applications both in computer science and economics. Due to the revelation principle – a seminal observation in mechanism design, a vast number of studies in mechanism design focus on revelation mechanisms (i.e., ones where revealing preferences truthfully forms an equilibrium). However, successful applications (e.g., first-price auction, generalized second-price auction for advertisers in sponsored search) suggest a great practical impact for non-revelation mechanisms. The focus of this thesis is to provide a theoretical understanding of the potential inadequacy of revelation principle and advantages of non-truthful mechanisms. We consider questions from prior-independent mechanism design, namely identifying a single mecha- nism that has near optimal performance on every prior distribution of agents’ preferences. To characterize the loss of the restriction to revelation mechanisms, we propose revelation gap – a quantification of optimal prior-independent approximation ratio among all revelation mechanisms vs. the optimal prior-independent approximation ratio among all (possibly non-revelation) mechanisms. We prove the existence of non-trivial revelation gaps in two canonical environments: (i) welfare maximization for public budgeted agents, and (ii) revenue maximization for a linear agent with a single sample access. Our analysis methods are of broader interest in mechanism design, and the study suggests that it is important to systematically develop a theory for the design of non-revelation mechanisms.

Creator