  We study combinatorial auctions with interdependent valuations. In such
settings, each agent $i$ has a private signal $s_i$ that captures her private
information, and the valuation function of every agent depends on the entire
signal profile, ${\bf s}=(s_1,\ldots,s_n)$. The literature in economics shows
that the interdependent model gives rise to strong impossibility results, and
identifies assumptions under which optimal solutions can be attained. The
computer science literature provides approximation results for simple
single-parameter settings (mostly single item auctions, or matroid feasibility
constraints). Both bodies of literature focus largely on valuations satisfying
a technical condition termed {\em single crossing} (or variants thereof).
  We consider the class of {\em submodular over signals} (SOS) valuations
(without imposing any single-crossing type assumption), and provide the first
welfare approximation guarantees for multi-dimensional combinatorial auctions,
achieved by universally ex-post IC-IR mechanisms. Our main results are: $(i)$
4-approximation for any single-parameter downward-closed setting with
single-dimensional signals and SOS valuations; $(ii)$ 4-approximation for any
combinatorial auction with multi-dimensional signals and {\em separable}-SOS
valuations; and $(iii)$ $(k+3)$- and $(2\log(k)+4)$-approximation for any
combinatorial auction with single-dimensional signals, with $k$-sized signal
space, for SOS and strong-SOS valuations, respectively. All of our results
extend to a parameterized version of SOS, $d$-SOS, while losing a factor that
depends on $d$.
