TY - GEN
T1 - Improved truthful mechanisms for subadditive combinatorial auctions
T2 - 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
AU - Assadi, Sepehr
AU - Kesselheim, Thomas
AU - Singla, Sahil
N1 - Publisher Copyright:
Copyright © 2021 by SIAM
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85102664097&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85102664097&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85102664097
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 653
EP - 661
BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
A2 - Marx, Daniel
PB - Association for Computing Machinery
Y2 - 10 January 2021 through 13 January 2021
ER -