Abstract

We study the communication complexity of welfare maximization in combinatorial auctions with m items and two subadditive bidders. A 1/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 (1/2+6/logm)-approximation requires communication exponential in m. This is tight even up to lower-order terms: we further present a (1/2+1\O(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.  

Time

12月17日  14:00--15:00

Speaker

Tomer Ezra completed his B.Sc. in Computer Science at The Open University - Israel, in 2010, and his M.Sc. in Computer Science at Tel Aviv University, in 2016. Currently Tomer is pursuing his Computer Science Ph.D. Degree at Tel Aviv University, under the supervision of Prof. Michal Feldman.

His research topic lies in the border of Computer Science and Economics, focusing on the analysis and design of simple mechanisms and algorithms in limited information settings.

Venue

信息管理与工程学院602室

上海财经大学（第三教学楼）

上海市杨浦区武东路100号