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 -