Improved truthful mechanisms for subadditive combinatorial auctions: Breaking the logarithmic barrier

Sepehr Assadi, Thomas Kesselheim, Sahil Singla

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

Abstract

We present a computationally-efficient truthful mechanism for combinatorial auctions with subadditive bidders that achieves an O((loglog m)3)-approximation to the maximum welfare in expectation using O(n) demand queries; here m and n are the number of items and bidders, respectively. This breaks the longstanding logarithmic barrier for the problem dating back to the O(log m · loglog m)-approximation mechanism of Dobzinski from 2007. Along the way, we also improve and considerably simplify the state-of-the-art mechanisms for submodular bidders.

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
PublisherAssociation for Computing Machinery
Pages653-661
Number of pages9
ISBN (Electronic)9781611976465
StatePublished - 2021
Event32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States
Duration: Jan 10 2021Jan 13 2021

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
CountryUnited States
CityAlexandria, Virtual
Period1/10/211/13/21

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Improved truthful mechanisms for subadditive combinatorial auctions: Breaking the logarithmic barrier'. Together they form a unique fingerprint.

Cite this