Estimation and Extraction: An Approach to Prior-Free Mechanism Design.
详细信息
文摘
We study prior-free mechanism design, which focuses on designing auctions that can perform well without any distributional knowledge of the preferences. The key strength of prior-free mechanism design compared to the classic Bayesian approach in economic theory is its robustness. A well designed prior-free mechanism would have good performance guarantees on any input, even adversarial. This is akin to the worst-case scenario approach in computer science. We are particularly interested in complex environments where there are combinatoric constraints imposed on the set of agents who can be served simultaneously. One of the most well known mechanisms for complex environments, the VCG auction Vickrey, 1961； Clarke, 1971； Groves, 1973), is prior-free and welfare optimizing. For other objectives such as revenue, mechanisms for the most general environments prior to our work are variants of only one technique, the random sampling auction. This auction partitions the agents into two groups, and uses empirical information from one to run an optimal mechanism on the other. When bidders have budgets, there has been no mechanism with quantifiable performance guarantees with respect to these objectives. Based on the techniques of some elegant mechanisms within the digital good setting, the simplest environment among those of interest, we propose a new approach for designing prior-free mechanisms for complex environments. Our framework for designing a prior-free mechanism consists of three major steps. First, we need to find a reasonable estimate of the preferences. Then, if such an estimate exists, we need to design a mechanism that can approximate the objective that is associated with this estimate. Finally, these two steps need to be composed to produce outcomes that satisfy the constraints of the setting. Using this framework, we obtain several mechanisms that approximate the optimal revenue for various complex environments. As an important building block in our framework, we completely characterize the outcome of the clinching auction Goel et. al., 2012), which was previously described as an ascending auction process. We show that clinching auction is a prior-free mechanism that can approximate the optimal welfare benchmark when agents have a publicly known common budget, and our approximation is tight.