The Communication Complexity of Truthful vs Non-Truthful Combinatorial Auctions

Explore the intricacies of combinatorial auctions in this 22-minute ACM conference talk, focusing on the communication complexity differences between truthful and non-truthful mechanisms. Delve into two-bidder scenarios, examine various auction types, and review prior research before diving into the main result. Follow the step-by-step proof, including the innovative "two copies" concept and solutions for handling cross terms. Gain valuable insights into this complex topic, concluding with a comprehensive understanding of the communication complexity landscape in combinatorial auctions.

Intro
Two Bidder Combinatorial Auctions
Two Types of Combinatorial Auctions
Prior Work
Main Result
Steps in the Proof
Two Copies: A Proof of Concept
The Problem of Cross Terms
Handling the Cross Terms
Conclusion