  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 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. 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.
