To refer to this page use:
|Abstract:||We study the communication complexity of welfare maximization in combinatorial auctions with m items and two players with subadditive valuations. We show that outperforming the trivial 1/2-approximation requires exponential communication, settling an open problem of Dobzinski, Nisan and Schapira [STOC'05, MOR'10] and Feige [STOC'06, SICOMP '09]. To derive our results, we introduce a new class of subadditive functions that are “far from” fractionally subadditive (XOS) functions, and establish randomized communication lower bounds for a new “near-EQUALITY” problem, both of which may be of independent interest.|
|Citation:||Ezra, Tomer, Michal Feldman, Eric Neyman, Inbal Talgam-Cohen, and Matt Weinberg. "Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers." In Annual Symposium on Foundations of Computer Science (FOCS) (2019): pp. 249-272. doi:10.1109/FOCS.2019.00025|
|Pages:||249 - 272|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||Annual Symposium on Foundations of Computer Science (FOCS)|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.