Settling the Communication Complexity of VCG-Based Mechanisms for All Approximation Guarantees

We consider truthful combinatorial auctions with items M = m for sale to n bidders, where each bidder i has a private monotone valuation function vi: 2M → ℝ+. Among truthful mechanisms, maximal-in-range (MIR) mechanisms (sometimes called VCG-based) achieve the best-known approximation guarantees among all poly-communication deterministic truthful mechanisms in all previously-studied settings. Our work settles the communication complexity necessary to achieve any approximation guarantee via an MIR mechanism. Specifically: Let MIRSubMod(m, k) denote the best approximation guarantee achievable by an MIR mechanism using 2k communication between bidders with submodular valuations over m items. Then for all k = Ω(log(m)), MIRSubMod(m,k) = Ω(√m/(klog(m/k))). When we set k = Θ(log(m)), this improves the previous best lower bound for polynomial communication maximal-in-range mechanisms from Ω(m1/3/log2/3(m)) to Ω(√m/log(m)). Additionally, MIRSubMod(m, k) = O(√m/k). Moreover, our mechanism can be implemented with 2k simultaneous value queries and computation, and is optimal with respect to the value query and computational/succinct representation models. The mechanism also works for bidders with subadditive valuations. When k = Θ(log(m)), this improves the previous best approximation guarantee for polynomial communication maximal-in-range mechanisms from O(√m) to O(√m/log(m)). Let also MIRGen(m,k) denote the best approximation guarantee achievable by an MIR mechanism using 2k communication between bidders with general valuations over m items. Then for all k = Ω(log(m)), MIRGen(m, k) = Ω(m/k). When k = Θ(log(m)), this improves the previous best lower bound for polynomial communication maximal-in-range mechanisms from Ω(m/log2(m)) to Ω(m/log(m)). Additionally, MIRGen(m, k) = O(m/k). Moreover, our mechanism can be implemented with 2k simultaneous value queries and computation, and is optimal with respect to the value query and computational/succinct representation models. When k = Θ(log(m)), this improves the previous best approximation guarantee for polynomial communication maximal-in-range mechanisms from O(m/√log(m)) to O(m/log(m)).