Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions

Authors: Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh Saxena, Matt Weinberg
Conference: The 52nd ACM Symposium on Theory of Computing (STOC 2020)
Abstract: We prove the first separation in the approximation guarantees achievable by truthful versus non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any deterministic, truthful protocol which guarantees a 3/4 − 1/240 + ε approximation for two buyers with XOS valuations over m items requires exp(Ω(ε2 · m)) communication whereas a deterministic, non-truthful protocol by Feige [STOC 2006] is already known to achieve a 3/4-approximation in poly(m) communication.

We obtain our result by proving that any deterministic simultaneous protocol (not neces- sarily truthful) which guarantees a 3/4 − 1/240 + ε approximation for two XOS buyers requires communication exp(Ω(ε2 · m)), and then apply the taxation complexity framework of Dobzinski [FOCS 2016] to extend the lower bound to all deterministic truthful protocols (including truthful interactive protocols).
Conference version: [PDF]
Streaming Video: [YouTube] (Raghuvansh's presentation at STOC)
BibTex: [DBLP]