Abstract follows below.
Combinatorial auctions are a paradigmatic problem at the intersection of Economics and Computation. However, it is still quite poorly understood how well one can approximate the optimal social welfare via truthful mechanisms. In most settings, it remains unknown whether there should be any separation between truthful mechanisms and non-truthful protocols at all.
In this work, 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 SubAdd∪SingleM. We show that for three bidders with valuations in SubAdd∪SingleM, any deterministic truthful mechanism which achieves at least a 0.366-approximation requires exp(m) communication. In contrast, a natural extension of [Feige09] yields a non-truthful poly(m)-communication protocol that achieves a 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 [Dobzinski16], 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 1/2-approximation for two players).