The complexity of simplicity in mechanism design

Aviad Rubinstein

Abstract

Optimal mechanisms are often prohibitively complicated, leading to serious obstacles both in theory and in bridging theory and practice. Consider the problem of a monopolist seller facing a single additive buyer with independent valuations over n heterogeneous items. Even in this simple setting, it is known that optimal (revenue-maximizing) mechanisms may require randomization [Hart and Reny 2012], use menus of infinite size [Daskalakis et al. 2015], and may be computationally intractable [Daskalakis et al. 2014]. In a letter here last year, Babiaoff et al. [Babaioff et al. 2014a] described their attempt to alleviate the problem by showing that a constant fraction of the optimal revenue can be obtained by a simple mechanism. In this letter we argue in favor of a related research direction: finding the optimal simple mechanism. We survey our recent results in this setting [Rubinstein 2016] and draw attention to the question of what is a "simple" mechanism?
BibTeX
@article{rubinstein2015complexity,
  author = {Aviad Rubinstein},
  title = {{The complexity of simplicity in mechanism design}},
  journal = {SIGecom Exch.},
  year = {2015},
  doi = {10.1145/2904104.2904110},
}

Loading related content...

Figure