An impossibility result for truthful combinatorial auctions with submodular valuations

DOI10.1145/1993636.1993656zbMath1288.91081arXiv1011.1830OpenAlexW2078273056MaRDI QIDQ5419083

Shahar Dobzinski

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.1830

zbMATH Keywords

incentive compatibilitycombinatorial auctions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Auctions, bargaining, bidding and selling, and other market models (91B26) Welfare economics (91B15)

Related Items (12)

Combinatorial Walrasian Equilibrium ⋮ Learning in auctions: regret is hard, envy is easy ⋮ Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions ⋮ Combinatorial reallocation mechanisms ⋮ Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik--Chervonenkis Dimension ⋮ Equilibria of Greedy Combinatorial Auctions ⋮ Simple combinatorial auctions with budget constraints ⋮ Economic efficiency requires interaction ⋮ Limitations of randomized mechanisms for combinatorial auctions ⋮ Mechanism design for perturbation stable combinatorial auctions ⋮ Selling multiple correlated goods: revenue maximization and menu-size complexity ⋮ Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders

This page was built for publication: An impossibility result for truthful combinatorial auctions with submodular valuations