Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers

Explore the intricacies of combinatorial auctions with two subadditive buyers in this 21-minute IEEE conference talk. Delve into the problem statement and motivation behind settling the communication complexity of these auctions. Learn about trivial protocols and the barriers to showing hardness. Discover a new definition of truncated set cover valuation and its construction. Examine the extension to randomized protocols and the modification of equality through EXIST-FAR-SETS. Gain insights into this complex topic as presented by Tomer Ezra, Michal Feldman, Eric Neyman, Inbal Talgam-Cohen, and S. Matthew Weinberg, and consider the potential for future work in this area.

Intro
What Are Combinatorial Auctions?
Our Problem: Statement
Our Problem: Motivation
Three Trivial Protocols
Barrier to Showing Hardness
New Definition: Truncated Set Cover Valuation
Constructing A and
Extension to Randomized Protocols
Modification of Equality: EXIST-FAR-SETS
Recap and Future Work