TY - GEN
T1 - Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
AU - Assadi, Sepehr
AU - Singla, Sahil
N1 - Publisher Copyright:
© 2019 IEEE.
PY - 2019/11
Y1 - 2019/11
N2 - 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.
AB - 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.
KW - Combinatorial Auctions
KW - Submodular Bidders
KW - Truthful Mechanisms
UR - http://www.scopus.com/inward/record.url?scp=85078503396&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85078503396&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2019.00024
DO - 10.1109/FOCS.2019.00024
M3 - Conference contribution
AN - SCOPUS:85078503396
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 233
EP - 248
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 -