SEPARATING THE COMMUNICATION COMPLEXITY OF TRUTHFUL AND NONTRUTHFUL ALGORITHMS FOR COMBINATORIAL AUCTIONS

We provide the first separation in the approximation guarantee achievable by truthful and nontruthful algorithms for combinatorial auctions with polynomial communication. Specifically, we prove that any truthful mechanism guaranteeing a (³/4 - ¹/240 + ε)-approximation for two buyers with XOS valuations over m items requires exp(Ω(ε² · m)) communication, whereas a nontruthful algorithm by Dobzinski and Schapira [Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2006, pp. 1064-1073] and Feige [SIAM J. Comput., 39 (2009), pp. 122-142] is already known to achieve a ³/4-approximation in poly(m) communication. We obtain our separation by proving that any simultaneous protocol (not necessarily truthful) which guarantees a (³/4 - ¹/240 + ε)-approximation requires communication exp(Ω(ε² · m)). The taxation complexity framework of Dobzinski [Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2016, pp. 209-218] extends this lower bound to all truthful mechanisms (including interactive truthful mechanisms).