Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier
<|reference_start|>Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier: We study the communication complexity of truthful combinatorial auctions, and in particular the case where valuations are either subadditive or single-minded, which we denote with $\mathsf{SubAdd}\cup\mathsf{SingleM}$. We show that for three bidders with valuations in $\mathsf{SubAdd}\cup\mathsf{SingleM}$, any deterministic truthful mechanism that achieves at least a $0.366$-approximation requires $\exp(m)$ communication. In contrast, a natural extension of [Fei09] yields a non-truthful $\mathrm{poly}(m)$-communication protocol that achieves a $\frac{1}{2}$-approximation, demonstrating a gap between the power of truthful mechanisms and non-truthful protocols for this problem.   Our approach follows the taxation complexity framework laid out in [Dob16b], but applies this framework in a setting not encompassed by the techniques used in past work. In particular, the only successful prior application of this framework uses a reduction to simultaneous protocols which only applies for two bidders [AKSW20], whereas our three-player lower bounds are stronger than what can possibly arise from a two-player construction (since a trivial truthful auction guarantees a $\frac{1}{2}$-approximation for two players).<|reference_end|>
@article{ron2024communication,
    title={Communication Separations for Truthful Auctions: Breaking the Two-Player
  Barrier},
    author={Shiri Ron, Clayton Thomas, S. Matthew Weinberg, Qianfan Zhang},
    journal={arXiv preprint arXiv:2409.08241},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.08241},
    primaryClass={cs.GT cs.CC}
}