Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue br

. We study combinatorial auctions with interdependent valuations, where each agent i has a private signal si that captures her private information and the valuation func-tion of every agent depends on the entire signal profile, s(s1,:::,sn). The literature in eco-nomics shows that the interdependent model gives rise to strong impossibility results and identifies assumptions under which optimal solutions can be attained. The computer sci-ence 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 single crossing (or variants thereof). We consider the class of submodular over signals (SOS) valuations (without imposing any single crossing-type assumption) and provide the first welfare approximation guaran-tees for multidimensional combinatorial auctions achieved by universally ex post incentive- compatible, individually rational mechanisms. Our main results are (i) four approximation for any single-parameter downward-closed setting with single-dimensional signals and SOS valuations; (ii) four approximation for any combinatorial auction with multidimen-sional signals and separable-SOS valuations; and (iii) (k+3) and (2log(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-approximate SOS, while losing a factor that depends on d