  Computational and economic results suggest that social welfare maximization
and combinatorial auction design are much easier when bidders' valuations
satisfy the "gross substitutes" condition. The goal of this paper is to
evaluate rigorously the folklore belief that the main take-aways from these
results remain valid in settings where the gross substitutes condition holds
only approximately. We show that for valuations that pointwise approximate a
gross substitutes valuation (in fact even a linear valuation), optimal social
welfare cannot be approximated to within a subpolynomial factor and demand
oracles cannot be simulated using a subexponential number of value queries. We
then provide several positive results by imposing additional structure on the
valuations (beyond gross substitutes), using a more stringent notion of
approximation, and/or using more powerful oracle access to the valuations. For
example, we prove that the performance of the greedy algorithm degrades
gracefully for near-linear valuations with approximately decreasing marginal
values, that with demand queries, approximate welfare guarantees for XOS
valuations degrade gracefully for valuations that are pointwise close to XOS,
and that the performance of the Kelso-Crawford auction degrades gracefully for
valuations that are close to various subclasses of gross substitutes
valuations.
