Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Complement-Free Couples Must Communicate: A Hardness Result for Two-Player Combinatorial Auctions
event speaker icon
Tomer Ezra (Tel-Aviv University)
event date icon
Wednesday, 01.05.2019, 12:30
event location icon
Taub 201
We study the communication complexity of welfare maximization in combinatorial auctions with m items and two subadditive bidders. A 12-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 (12+6log2m)-approximation requires communication exponential in m. This is tight even up to lower-order terms: we further present a (12+1O(logm))-approximation in poly(m) communication.

To derive our results, we introduce a new class of subadditive functions that are "far from" fractionally subadditive functions, and may be of independent interest for future works. Beyond our main result, we consider the spectrum of valuations between fractionally-subadditive and subadditive via the MPH hierarchy. Finally, we discuss the implications of our results towards combinatorial auctions with strategic bidders.