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, Hart and Nisan show that no simple mechanism can achieve a non-negligible 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, one of the most prominent frameworks for modeling high-dimensional distributions with structure. If the buyer's valuation is additive or unit-demand, we extend the result to all MRFs and show that max(SRev,BRev) can achieve an $\Omega\left(\frac{1}{e^{O(\Delta)}}\right)$-fraction of the optimal revenue, where $\Delta$ is a parameter of the MRF that is determined by how much the value of an item can be influenced by the values of the other items. We further show that the exponential dependence on $\Delta$ is unavoidable for our approach and a polynomial dependence on $\Delta$ is unavoidable for any approach. When the buyer has a XOS valuation, we show that max(Srev,Brev) achieves at least an $\Omega\left(\frac{1}{e^{O(\Delta)}+\frac{1}{\sqrt{n\gamma}}}\right)$-fraction of the optimal revenue, where $\gamma$ is the spectral gap of the Glauber dynamics of the MRF. Note that the values of $\Delta$ and $\frac{1}{n\gamma}$ increase as the dependence between items strengthens. In the special case of independently distributed items, $\Delta=0$ and $\frac{1}{n\gamma}\geq 1$, and our results recover the known constant factor approximations for a XOS buyer. We further extend our parametric approximation to several other well-studied dependency measures such as the Dobrushin coefficient and the inverse temperature. Our results are based on the Duality-Framework by Cai et al. and a new concentration inequality for XOS functions over dependent random variables.