TY - GEN
T1 - Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers
AU - Ezra, Tomer
AU - Feldman, Michal
AU - Neyman, Eric
AU - Talgam-Cohen, Inbal
AU - Weinberg, Matt
N1 - Publisher Copyright:
© 2019 IEEE.
PY - 2019/11
Y1 - 2019/11
N2 - 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.
AB - 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.
KW - combinatorial auctions
KW - communication complexity
KW - subadditive functions
UR - http://www.scopus.com/inward/record.url?scp=85077978047&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85077978047&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2019.00025
DO - 10.1109/FOCS.2019.00025
M3 - Conference contribution
AN - SCOPUS:85077978047
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 249
EP - 272
BT - Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
PB - IEEE Computer Society
T2 - 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019
Y2 - 9 November 2019 through 12 November 2019
ER -