TY - JOUR

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

AU - Assadi, Sepehr

AU - Khandeparkar, Hrishikesh

AU - Saxena, Raghuvansh R.

AU - Weinberg, S. Matthew

N1 - Publisher Copyright:
© 2022 Society for Industrial and Applied Mathematics.

PY - 2022

Y1 - 2022

N2 - 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).

AB - 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).

KW - combinatorial auctions

KW - communication complexity

KW - fractionally subadditive

KW - simultaneous communication

UR - http://www.scopus.com/inward/record.url?scp=85134871185&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85134871185&partnerID=8YFLogxK

U2 - 10.1137/20M1370021

DO - 10.1137/20M1370021

M3 - Article

AN - SCOPUS:85134871185

SN - 0097-5397

VL - 51

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -