Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders

DOI10.1137/16M1088594zbMath1467.91056arXiv1602.05914OpenAlexW2275395982MaRDI QIDQ4997307

Shahar Dobzinski

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

zbMATH Keywords

auctionsapproximation algorithmscombinatorial auctionstruthful mechanismssubmodular valuations

Mathematics Subject Classification ID

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 (7)

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

This page was built for publication: Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders