Member Seminar

Speaker: Tomer Ezra (CMSA)

Title: Communication Complexity of Combinatorial Auctions

Abstract: We study the communication complexity of welfare maximization in combinatorial auctions with m items and two subadditive bidders. A 2-approximation can be guaranteed by a trivial randomized protocol with zero communication, or a trivial deterministic protocol with O(1) communication. We show that outperforming these trivial protocols requires exponential communication, settling an open question of [DobzinskiNS10, Feige09].

Specifically, we show that any (randomized) protocol guaranteeing a o(logm)-approximation requires communication exponential in m. We complement it by presenting an O(logm)-approximation in poly(m) communication.