Poster
On Infinite Separations Between Simple and Optimal Mechanisms
Alexandros Psomas · Ariel Schvartzman Cohenca · S. Weinberg
Hall J (level 1) #825
Keywords: [ revenue maximization ] [ mechanism design ] [ correlated distributions ]
Abstract:
We consider a revenue-maximizing seller with kk heterogeneous items for sale to a single additive buyer, whose values are drawn from a known, possibly correlated prior DD. It is known that there exist priors DD such that simple mechanisms --- those with bounded menu complexity --- extract an arbitrarily small fraction of the optimal revenue~(Briest et al. 2015, Hart and Nisan 2019). This paper considers the opposite direction: given a correlated distribution DD witnessing an infinite separation between simple and optimal mechanisms, what can be said about DD?\citet{hart2019selling} provides a framework for constructing such DD: it takes as input a sequence of kk-dimensional vectors satisfying some geometric property, and produces a DD witnessing an infinite gap. Our first main result establishes that this framework is without loss: every DD witnessing an infinite separation could have resulted from this framework. An earlier version of their work provided a more streamlined framework (Hart and Nisan 2013). Our second main result establishes that this restrictive framework is not tight. That is, we provide an instance DD 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.
Chat is not available.