Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
From MaRDI portal
Publication:4997307
DOI10.1137/16M1088594zbMath1467.91056arXiv1602.05914MaRDI QIDQ4997307
Publication date: 29 June 2021
Published in: SIAM Journal on Computing, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1602.05914
auctions; approximation algorithms; combinatorial auctions; truthful mechanisms; submodular valuations
91B26: Auctions, bargaining, bidding and selling, and other market models
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
91B03: Mechanism design theory