# On Infinite Separations Between Simple and Optimal Mechanisms

arXiv: https://arxiv.org/abs/2205.13039 · HTML: https://mlsanity.com/paper/2205.13039/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2022.

## Built on by (most cited first, 1 of 1)

- [Refined Mechanism Design for Approximately Structured Priors via Active Regression](https://mlsanity.com/paper/2310.07874/) (2023)

## Abstract (arXiv)

We consider a revenue-maximizing seller with k heterogeneous items for sale to a single additive buyer, whose values are drawn from a known, possibly correlated prior D. It is known that there exist priors D such that simple mechanisms -- those with bounded menu complexity -- extract an arbitrarily small fraction of the optimal revenue. This paper considers the opposite direction: given a correlated distribution D witnessing an infinite separation between simple and optimal mechanisms, what can be said about D? Previous work provides a framework for constructing such D: it takes as input a sequence of k-dimensional vectors satisfying some geometric property, and produces a D witnessing an infinite gap. Our first main result establishes that this framework is without loss: every D witnessing an infinite separation could have resulted from this framework. Even earlier work provided a more streamlined framework. Our second main result establishes that this restrictive framework is not tight. That is, we provide an instance D witnessing an infinite gap, but which provably could not have resulted from the restrictive framework. As a corollary, we discover a new kind of mechanism which can witness these infinite separations on instances where the previous ''aligned'' mechanisms do not.