Communication complexity of combinatorial auctions with submodular valuations
Shahar Dobzinski, J. Vondrák · 2013
We prove the first communication complexity lower bound for constant-factor approximation of the submodular welfare problem. More precisely, we show that a (1 − 1 2e +ɛ)-approximation ( ≃ 0.816) for welfare maximization in combinatorial auctions with submodular 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: maxmin allocation (for which we also get hardness of