דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
תומר עזרא (אונ' תל-אביב)
event date icon
יום רביעי, 01.05.2019, 12:30
event location icon
טאוב 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.