To refer to this page use:
|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).|
|Citation:||Assadi, Sepehr, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, and S. Matthew Weinberg. "Separating the communication complexity of truthful and non-truthful combinatorial auctions." In Annual ACM SIGACT Symposium on Theory of Computing (2020): pp. 1073-1085. doi:10.1145/3357713.3384267|
|Pages:||1073 - 1085|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||Annual ACM SIGACT Symposium on Theory of Computing|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.