## Abstract

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

Original language | English (US) |
---|---|

Journal | SIAM Journal on Computing |

Volume | 51 |

Issue number | 3 |

DOIs | |

State | Published - 2022 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- General Mathematics

## Keywords

- combinatorial auctions
- communication complexity
- fractionally subadditive
- simultaneous communication