Communication complexity of combinatorial auctions with submodular valuations

Abstract

We prove the first communication complexity lower bound for constant-factor approximation of the sub-modular welfare problem. More precisely, we show that a (1-1/2e+ε)-approximation (≃ 0.816) for welfare maximization in combinatorial auctions with sub-modular valuations would require exponential communication. We also show NP-hardness of (1-1/2e+ε)-approximation in a computational model where each valuation is given explicitly by a table of constant size. Both results rule out better than (1-1/2e)-approximations in every oracle model with a separate oracle for each player, such as the demand oracle model. Our main tool is a new construction of monotone submodular functions that we call multi-peak submodular functions. Roughly speaking, given a family of sets F, we construct a monotone submodular function f with a high value f(S) for every set S ∈ F (a "peak"), and a low value on every set that does not intersect significantly any set in F. We also study two other related problems: max-min allocation (for which we also get hardness of (1-1/2e+ε)-approximation, in both models), and combinatorial public projects (for which we prove hardness of (3/4+ε)-approximation in the communication model, and hardness of (1-1/e+ε)-approximation in the computational model, using constant size valuations). Copyright © SIAM.