Abstract
We study the problem of sellingnheterogeneous items to a single buyer, whose values fordifferent items aredependent. Under arbitrary dependence, Hart and Nisan [30] show that nosimple mechanism can achieve a non-negligible fraction of the optimal revenue even with onlytwo items. We consider the setting where the buyer’s type is drawn from a correlated distributionthat can be captured by a Markov Random Field, one of the most prominent frameworks formodeling high-dimensional distributions with structure. If the buyer’s valuation is additive or unit-demand, we extend the result to all MRFs andshow that max{SRev,BRev} can achieve an $\Omega(\frac{1}{e^{O(\Delta)}})$-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 beinfluenced 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 anyapproach. When the buyer has a XOS valuation, we show that max{SRev,BRev}achievesat least an $\Omega\left(\frac{1}{e^{O(\Delta)}+\frac{1}{\sqrt{n\gamma}}}\right)$-fraction of the optimal revenue, whereγis the spectral gap of theGlauber dynamics of the MRF. Note that in the special case of independently distributed items, $\Delta=0$ and $\frac{1}{n\gamma}\leq 1$, and our results recover the known constant factor approximations for a XOS buyer [41]. We further extend our parametric approximation to several other well-studieddependency measures such as theDobrushin coefficient[27] and theinverse temperature. Inparticular, we show that if the MRF is in thehigh temperature regime, max{SRev,BRev}isstill a constant factor approximation to the optimal revenue even for a XOS buyer. Our resultsare based on the Duality-Framework by Cai et al. [14] and a new concentration inequality forXOS functions over dependent random variables.
