Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders

Sepehr Assadi, Sahil Singla

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

3 Scopus citations

Abstract

A longstanding open problem in Algorithmic Mechanism Design is to design computationally-efficient truthful mechanisms for (approximately) maximizing welfare in combinatorial auctions with submodular bidders. The first such mechanism was obtained by Dobzinski, Nisan, and Schapira [STOC'06] who gave an O(log2m)-Approximation where m is number of items. This problem has been studied extensively since, culminating in an O(√log m)-Approximation mechanism by Dobzinski~[STOC'16]. We present a computationally-efficient truthful mechanism with approximation ratio that improves upon the state-of-The-Art by an exponential factor. In particular, our mechanism achieves an O((log logm)3)-Approximation in expectation, uses only O(n) demand queries, and has universal truthfulness guarantee. This settles an open question of Dobzinski on whether Θ(√log m) is the best approximation ratio in this setting in negative.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
PublisherIEEE Computer Society
Pages233-248
Number of pages16
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
CountryUnited States
CityBaltimore
Period11/9/1911/12/19

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Combinatorial Auctions
  • Submodular Bidders
  • Truthful Mechanisms

Cite this