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 v i : 2 M → R + . 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 MIR SubMod (m, k) denote the best approximation guarantee achievable by an MIR mechanism using 2 k communication between bidders with submodular valuations over m items. Then

this improves the previous best lower bound for polynomial communication maximal-inrange mechanisms from Ω(m 1/3 / log 2/3 (m)) [DSS15] to Ω( √ m/ log(m)).

• For all k = Ω(log(m)), MIR SubMod (m, k) = O( m/k). Moreover, our mechanism can be implemented with 2 k 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) [DNS10] to O( m/ log(m)).

Let also MIR Gen (m, k) denote the best approximation guarantee achievable by an MIR mechanism using 2 k communication between bidders with general valuations over m items. Then

• For all k = Ω(log(m)), MIR Gen (m, k) = Ω(m/k). When k = Θ(log(m)), this improves the previous best lower bound for polynomial communication maximal-in-range mechanisms from Ω(m/ log 2 (m)) [DSS15] to Ω(m/ log(m)).

• For all k = Ω(log(m)), MIR Gen (m, k) = O(m/k). Moreover, our mechanism can be implemented with 2 k 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)) [HKMT04] to O(m/ log(m)).