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

Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg

Research output: Contribution to journalArticlepeer-review

Abstract

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 (3/4 - 1/240 + ε)-approximation for two buyers with XOS valuations over m items requires exp(Ω(ε2 · 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 3/4-approximation in poly(m) communication. We obtain our separation by proving that any simultaneous protocol (not necessarily truthful) which guarantees a (3/4 - 1/240 + ε)-approximation requires communication exp(Ω(ε2 · 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).

Original languageEnglish (US)
JournalSIAM Journal on Computing
Volume51
Issue number3
DOIs
StatePublished - 2022

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics

Keywords

  • combinatorial auctions
  • communication complexity
  • fractionally subadditive
  • simultaneous communication

Fingerprint

Dive into the research topics of 'SEPARATING THE COMMUNICATION COMPLEXITY OF TRUTHFUL AND NONTRUTHFUL ALGORITHMS FOR COMBINATORIAL AUCTIONS'. Together they form a unique fingerprint.

Cite this