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

Frederick V. Qiu, S. Matthew Weinberg

We consider truthful combinatorial auctions with items $M=[m]$ for sale to $n$ bidders, where each bidder $i$ has a private monotone valuation $v_i:2^M\to R_{+}$. Among truthful…