Envy freedom and prior-free mechanism design

Nikhil R. Devanur, Jason D Hartline*, Qiqi Yan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)103-143
Number of pages41
JournalJournal of Economic Theory
Volume156
DOIs
StatePublished - Mar 1 2015

Keywords

  • Envy freedom
  • Incentive compatibility
  • Mechanism design
  • Myerson
  • Prior-free

ASJC Scopus subject areas

  • Economics and Econometrics

Fingerprint

Dive into the research topics of 'Envy freedom and prior-free mechanism design'. Together they form a unique fingerprint.

Cite this