On Infinite Separations Between Simple and Optimal Mechanisms

05/25/2022
βˆ™
by   C. Alexandros Psomas, et al.
βˆ™
0
βˆ™

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 π’Ÿ. It is known that there exist priors π’Ÿ 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 π’Ÿ witnessing an infinite separation between simple and optimal mechanisms, what can be said about π’Ÿ? Previous work provides a framework for constructing such π’Ÿ: it takes as input a sequence of k-dimensional vectors satisfying some geometric property, and produces a π’Ÿ witnessing an infinite gap. Our first main result establishes that this framework is without loss: every π’Ÿ 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 π’Ÿ 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset