Qiqi Yan: Prior-Independent Mechanisms via Resource Augmentation
Channel: Stanford Computer Science Theory
Date: 2011-10-16

Videos from the Beyond Worst Case Analysis Workshop 
Stanford, CA 
Sept. 19-21, 2011


Qiqi Yan: Prior-Independent Mechanisms via Resource Augmentation

A prior-independent mechanism has no knowledge about the underlying input prior distribution, yet its expected revenue approximates that of the optimal mechanism tailored for the distribution. This prior-independent approach aims to be a balanced mix of computer science's worst-case analysis approach, and economics' distribution-based average case analysis approach.

We show that a general approach to obtain prior-independent mechanisms is via a reduction to statements about "resource augmentation". Such a statement (like the classic Bulow-Klemperer theorem) says that running the VCG mechanism over an expanded environment with more bidders approximates the optimal mechanism in the original environment. Using this reduction, we show that a simple supply-limiting strategy gives prior-independent mechanisms for several single-parameter and multi-parameter settings.

Based on joint work with Inbal Talgam-Cohen and Tim Roughgarden.