Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers
| Autor: | Inbal Talgam-Cohen, Tomer Ezra, Michal Feldman, Eric Neyman, Matt Weinberg |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Computer science
Open problem TheoryofComputation_GENERAL 020206 networking & telecommunications 02 engineering and technology Maximization Exponential function Combinatorial auction TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Subadditivity 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Communication complexity Mathematical economics |
| Zdroj: | FOCS |
| DOI: | 10.1109/focs.2019.00025 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|