Complement-Free Couples Must Communicate: A Hardness Result for Two-Player Combinatorial Auctions

Tomer Ezra, Michal Feldman, Eric Neyman +2

We study the communication complexity of welfare maximization in combinatorial auctions with $m$ items and two subadditive bidders. A $\frac{1}{2}$-approximation can be guaranteed…