On Simple Mechanisms for Dependent Items

We study the problem of selling n heterogeneous items to a single buyer, whose values for different items are dependent. Under arbitrary dependence, others show that no simple mechanism can achieve a nonnegligible fraction of the optimal revenue even with only two items. We consider the setting where the buyer’s type is drawn from a correlated distribution that can be captured by a Markov random field (MRF), one of the most prominent frameworks for modeling high-dimensional distributions with structure. We show how the performance of simple mechanisms depends on some natural parameters of the MRF for several fundamental classes of the buyer’s valuations. Our results are based on the duality framework by of others and a new concentration inequality for XOR-of-OR-of-Singletons functions over dependent random variables.

Funding: This research was supported by a Sloan Foundation Research Fellowship and the National Science Foundation [Award CCF-1942583 (CAREER)].