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 vi : 2M → R_+. Among truthful mechanisms, maximal-in-range (MIR) mechanisms achieve the best-known approximation guarantees among all poly-communication deterministic truthful mechanisms in all previously-studied settings. Our work settles the communication 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 = Omega(log(m)), MIRsubmod(m,k) = Omega(√m/(klog(m/k))). When k = Theta(log(m)), this improves the previous best lower bound for poly-comm. MIR mechanisms from Omega(m1/3/log2/3(m)) to Omega(√m/log(m)). We also have MIRsubmod(m,k) = O(√m/k). Moreover, our mechanism is optimal w.r.t. the value query and succinct representation models. When k = Theta(log(m)), this improves the previous best approximation guarantee for poly-comm. MIR 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 = Omega(log(m)), MIRgen(m,k) = Omega(m/k). When k = Theta(log(m)), this improves the previous best lower bound for poly-comm. MIR mechanisms from Omega(m/log2(m)) to Omega(m/log(m)). We also have MIRgen(m,k) = O(m/k). Moreover, our mechanism is optimal w.r.t. the value query and succinct representation models. When k = Theta(log(m)), this improves the previous best approximation guarantee for poly-comm. MIR mechanisms from O(m/√log(m)) to O(m/log(m)).