Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions

Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena +1

We provide the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove…