Abstract:
We prove the first separation in the approximation guarantees achievable by truthful versus non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any deterministic, truthful protocol which guarantees a 3/4 − 1/240 + ε approximation for two buyers with XOS valuations over m items requires exp(Ω(ε2 · m)) communication whereas a deterministic, non-truthful protocol by Feige [STOC 2006] is already known to achieve a 3/4-approximation in poly(m) communication.
We obtain our result by proving that any deterministic simultaneous protocol (not neces- sarily truthful) which guarantees a 3/4 − 1/240 + ε approximation for two XOS buyers requires communication exp(Ω(ε2 · m)), and then apply the taxation complexity framework of Dobzinski [FOCS 2016] to extend the lower bound to all deterministic truthful protocols (including truthful interactive protocols).
Conference version:
[PDF]
Streaming Video:
[YouTube] (Raghuvansh@STOC'20)