The Complexity of Simplicity in Mechanism Design

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?