Communication Complexity of Combinatorial Auctions

CMSA EVENTS, CMSA EVENTS: CMSA MEMBER SEMINAR

When: September 20, 2024
12:00 pm - 2:00 pm
Where: CMSA, 20 Garden St, Common Room
Address: 20 Garden Street, Cambridge 02138, United States
Speaker: Tomer Ezra (CMSA)

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.

Friday, September 20 at 12pm, with lunch, lounge at CMSA (20 Garden Street).

Zoom ID 965 2902 1352
Passcode 322891
https://harvard.zoom.us/j/96529021352?pwd=ehXEylANVrstFfISgNJhjaPwcIuCby.1