Combinatorial auctions with interdependent valuations: SOS to the rescue (Q6563009)

In this paper, the authors study combinatorial auctions with interdependent valuations, where 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, \(s=(s_1,\ldots ,s_n)\). More precisely, the authors consider the class of submodular over signals (SOS) valuations (without imposing any single crossing-type assumption) and provide the first welfare approximation guarantees for multidimensional combinatorial auctions achieved by universally ex post incentive compatible, individually rational mechanisms.\N\NThe main author's results are\N\N(i) four approximation for any single-parameter downward-closed setting with single-dimensional signals and SOS valuations;\N\N(ii) four approximation for any combinatorial auction with multidimensional signals and separable-SOS valuations;\N\N(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.\N\NThe results are extended to a parameterized version of SOS, \(d\)-approximate SOS, while losing a factor that depends on \(d\).