TY - GEN
T1 - Separating the communication complexity of truthful and non-truthful combinatorial auctions
AU - Assadi, Sepehr
AU - Khandeparkar, Hrishikesh
AU - Saxena, Raghuvansh R.
AU - Weinberg, S. Matthew
N1 - Funding Information:
∗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 is supported by the National Science Foundation CAREER award CCF-1750443. The fourth author is supported by the National Science Foundation NSF CCF-1717899.
Publisher Copyright:
© 2020 ACM.
PY - 2020/6/8
Y1 - 2020/6/8
N2 - 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).
AB - 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).
KW - Combinatorial Auctions
KW - Lower Bounds
KW - Simultaneous Communication
UR - http://www.scopus.com/inward/record.url?scp=85086757472&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85086757472&partnerID=8YFLogxK
U2 - 10.1145/3357713.3384267
DO - 10.1145/3357713.3384267
M3 - Conference contribution
AN - SCOPUS:85086757472
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1073
EP - 1085
BT - STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
A2 - Makarychev, Konstantin
A2 - Makarychev, Yury
A2 - Tulsiani, Madhur
A2 - Kamath, Gautam
A2 - Chuzhoy, Julia
PB - Association for Computing Machinery
T2 - 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
Y2 - 22 June 2020 through 26 June 2020
ER -