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