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 $v_i:2^M\to 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 $2^k$ communication between bidders with submodular valuations over $m$ items. Then for all $k=\Omega (\log (m))$, MIRsubmod$(m,k)=\Omega (\sqrt{m/(k\log (m/k))})$. When $k=\Theta (\log (m))$, this improves the previous best lower bound for poly-comm. MIR mechanisms from $\Omega (m^{1/3}/{\log }^{2/3}(m))$ to $\Omega (\sqrt{m}/\log (m))$. We also have MIRsubmod$(m,k)=O(\sqrt{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(\sqrt{m})$ to $O(\sqrt{m/\log (m)})$. Let also MIRgen$(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=\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/{\log }^2(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/\sqrt{\log (m)})$ to $O(m/\log (m))$.

40 pages, 2 figures, to appear in STOC 2024