Settling the Communication Complexity of VCG-based Mechanisms for all Approximation Guarantees

Abstract

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 → R+. Among truthful mechanisms, maximal-in-range (MIR) mechanisms (sometimes called VCG-based ) achieve the best-known approximation guarantees among all deterministic truthful mechanisms in all previously-studied settings. Our work settles the communication complexity necessary to achieve any approximation guarantee via a maximal-in-range mechanism.