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 - Funding Information:
\ast Received by the editors September 28, 2020; accepted for publication (in revised form) January 26, 2022; published electronically April 7, 2022. https://doi.org/10.1137/20M1370021 \bfF \bfu \bfn \bfd \bfi \bfn \bfg : The first author was supported in part by National Science Foundation (NSF) CAREER award CCF-2047061 and a gift from Google Research. Part of this work was done while the first author was a postdoctoral researcher at Princeton University and was supported in part by the Simons Collaboration on Algorithms and Geometry. The third author was supported by NSF CAREER award CCF-1750443. The fourth author was supported by NSF grant CCF-1717899. \dagger Department of Computer Science, Rutgers University, Piscataway, NJ 08854 USA (sepehr. assadi@rutgers.edu). \ddagger Department of Computer Science, Princeton University, Princeton, NJ 08540 USA (hrishikesh. khandeparkar@gmail.com, rrsaxena@cs.princeton.edu, smweinberg@princeton.edu).
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 -