  We study the power of item-pricing as a tool for approximately optimizing
social welfare in a combinatorial market. We consider markets with $m$
indivisible items and $n$ buyers. The goal is to set prices to the items so
that, when agents purchase their most demanded sets simultaneously, no
conflicts arise and the obtained allocation has nearly optimal welfare. For
gross substitutes valuations, it is well known that it is possible to achieve
optimal welfare in this manner. We ask: can one achieve approximately efficient
outcomes for valuations beyond gross substitutes? We show that even for
submodular valuations, and even with only two buyers, one cannot guarantee an
approximation better than $\Omega(\sqrt{m})$. The same lower bound holds for
the class of single-minded buyers as well. Beyond the negative results on
welfare approximation, our results have daunting implications on revenue
approximation for these valuation classes: in order to obtain good
approximation to the collected revenue, one would necessarily need to abandon
the common approach of comparing the revenue to the optimal welfare; a
fundamentally new approach would be required.
