Envy freedom and prior-free mechanism design

• 成果类型: Article
• 署名作者: Devanur, Nikhil R.; Hartline, Jason D.; Yan, Qiqi
• 署名单位: Microsoft; Northwestern University; Alphabet Inc.; Google Incorporated
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2014.08.001
• 发表日期: 2015
• 页码: 103-143
• 关键词: Envy freedom; incentive compatibility; Myerson; Prior-free; mechanism design

摘要

We consider the provision of an abstract service to single-dimensional agents. Our model includes position auctions, single-minded combinatorial auctions, and constrained matching markets. When the agents' values are drawn independently from a distribution, the Bayesian optimal mechanism is given by Myerson [1] as a virtual-surplus optimizer. We develop a framework for prior-free mechanism design and analysis. A good mechanism in our framework approximates the optimal mechanism for the distribution if there is a distribution; moreover, when there is no distribution this mechanism still provably performs well. We define and characterize optimal envy-free outcomes in symmetric single-dimensional environments. Our characterization mirrors Myerson's theory. Furthermore, unlike in mechanism design where there is no point-wise optimal mechanism, there is always a point-wise optimal envy-free outcome. Envy-free outcomes and incentive-compatible mechanisms are similar in structure and performance. We therefore use the optimal envy-free revenue as a benchmark for measuring the performance of a prior-free mechanism. A good mechanism is one that approximates the envy-free benchmark on any profile of agent values. We show that good mechanisms exist, and in particular, a natural generalization of the random sampling auction of Goldberg et al. [2] is a constant approximation. (C) 2014 Elsevier Inc. All rights reserved.