Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
From MaRDI portal
Publication:4997307
DOI10.1137/16M1088594zbMath1467.91056arXiv1602.05914OpenAlexW2275395982MaRDI 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, bargaining, bidding and selling, and other market models (91B26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Mechanism design theory (91B03)
Related Items
Learning in auctions: regret is hard, envy is easy, Best-response dynamics in combinatorial auctions with item bidding, Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions, Optimal item pricing in online combinatorial auctions, Simple combinatorial auctions with budget constraints, Mechanism design for perturbation stable combinatorial auctions, An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Inapproximability results for combinatorial auctions with submodular utility functions
- Combinatorial auctions with decreasing marginal utilities
- On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
- Online Mechanism Design (Randomized Rounding on the Fly)
- Approximation algorithms for combinatorial auctions with complement-free bidders
- Two Randomized Mechanisms for Combinatorial Auctions
- Optimal Auction Design
- Algorithm Theory - SWAT 2004
- An impossibility result for truthful combinatorial auctions with submodular valuations
- From convex optimization to randomized mechanisms
- Limitations of Randomized Mechanisms for Combinatorial Auctions
- Truthful randomized mechanisms for combinatorial auctions
