Separating the communication complexity of truthful and non-truthful combinatorial auctions

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We prove the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any truthful auction guaranteeing a (34-1240+")-approximation for two buyers with XOS valuations over m items requires exp(ω(ϵ2 · m)) communication whereas a non-truthful auction by Feige [J. Comput. 2009] is already known to achieve a 34-approximation in (m) communication. We obtain our lower bound for truthful auctions by proving that any simultaneous auction (not necessarily truthful) which guarantees a (34-1240+ϵ)-approximation requires communication exp(ω(ϵ2 · m)), and then apply the taxation complexity framework of Dobzinski [FOCS 2016] to extend the lower bound to all truthful auctions (including interactive truthful auctions).

Original languageEnglish (US)
Title of host publicationSTOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
EditorsKonstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
PublisherAssociation for Computing Machinery
Pages1073-1085
Number of pages13
ISBN (Electronic)9781450369794
DOIs
StatePublished - Jun 8 2020
Event52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, United States
Duration: Jun 22 2020Jun 26 2020

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
CountryUnited States
CityChicago
Period6/22/206/26/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Combinatorial Auctions
  • Lower Bounds
  • Simultaneous Communication

Fingerprint Dive into the research topics of 'Separating the communication complexity of truthful and non-truthful combinatorial auctions'. Together they form a unique fingerprint.

Cite this