Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations

DOI10.1145/2786754zbMATH Open1426.68119OpenAlexW2333413293MaRDI QIDQ3177762FDOQ3177762

Jan Vondrák, Shahar Dobzinski

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2786754

zbMATH Keywords

computational complexitysubmodular functionstruthful mechanisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Auctions, bargaining, bidding and selling, and other market models (91B26)

Cited In (5)

• Best-response dynamics in combinatorial auctions with item bidding
• Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
• Setting lower bounds on truthfulness
• Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions
• Truthful mechanism design via correlated tree rounding

Recommendations

• Truthful approximation mechanisms for restricted combinatorial auctions 👍 👎
• Truth revelation in approximately efficient combinatorial auctions 👍 👎
• Truthful randomized mechanisms for combinatorial auctions 👍 👎
• Truthful randomized mechanisms for combinatorial auctions 👍 👎
• On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions 👍 👎
• Inapproximability results for combinatorial auctions with submodular utility functions 👍 👎
• Truthfulness with value-maximizing bidders: on the limits of approximation in combinatorial markets 👍 👎
• Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders 👍 👎
• An impossibility result for truthful combinatorial auctions with submodular valuations 👍 👎

This page was built for publication: Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177762)