Settling the Communication Complexity of VCG-based Mechanisms for all Approximation Guarantees
<|reference_start|>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 $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))$.<|reference_end|>
@article{qiu2024settling,
    title={Settling the Communication Complexity of VCG-based Mechanisms for all
  Approximation Guarantees},
    author={Frederick V. Qiu, S. Matthew Weinberg},
    journal={arXiv preprint arXiv:2404.00831},
    year={2024},
    doi={10.1145/3618260.3649706},
    archivePrefix={arXiv},
    eprint={2404.00831},
    primaryClass={cs.GT}
}