Communication Complexity of Combinatorial Auctions
CMSA Room G10 CMSA, 20 Garden Street, Cambridge, MA, United StatesMember 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 […]