Envy freedom and 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.