Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers

Tomer Ezra, Michal Feldman, Eric Neyman, Inbal Talgam-Cohen, Matt Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
PublisherIEEE Computer Society
Pages249-272
Number of pages24
ISBN (Electronic)9781728149523
DOIs
StatePublished - Nov 2019
Event60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 - Baltimore, United States
Duration: Nov 9 2019Nov 12 2019

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2019-November
ISSN (Print)0272-5428

Conference

Conference60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019
Country/TerritoryUnited States
CityBaltimore
Period11/9/1911/12/19

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • combinatorial auctions
  • communication complexity
  • subadditive functions

Fingerprint

Dive into the research topics of 'Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers'. Together they form a unique fingerprint.

Cite this