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

arXiv: https://arxiv.org/abs/2404.00831 · HTML: https://mlsanity.com/paper/2404.00831/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Mar 2024.

## Built on by (most cited first, 1 of 1)

- [Latency-Aware Resource Allocation over Heterogeneous Networks: A Lorentz-Invariant Market Mechanism](https://mlsanity.com/paper/2604.03897/) (2026)

## Abstract (arXiv)

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)).