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 SubAddUSingleM. We show that for three bidders with valuations in SubAddUSingleM, any deterministic truthful mechanism that achieves at least a 0.366-approximation requires <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\exp(m)$</tex> communication. In contrast, a natural extension of [Fei09] yields a non-truthful <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\text{poly}(m)-\mathbf{communication}$</tex> protocol that achieves a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\frac{1}{2}-\mathbf{approximation}$</tex>, 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\frac{1}{2}- \mathbf{approximation}$</tex> for two players).