Limitations of randomized mechanisms for combinatorial auctions

DOI10.1016/j.geb.2014.01.007zbMath1318.91090arXiv1109.1055OpenAlexW2571397442MaRDI QIDQ2516249

Jan Vondrák, Shaddin Dughmi

Publication date: 12 August 2015

Published in: Games and Economic Behavior (Search for Journal in Brave)

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

zbMATH Keywords

incentive compatibilityalgorithmic mechanism designcombinatorial auctionssubmodular valuations

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Related Items (9)

The Limitations of Optimization from Samples ⋮ Learning in auctions: regret is hard, envy is easy ⋮ Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Truthful mechanism design via correlated tree rounding ⋮ Equilibria of Greedy Combinatorial Auctions ⋮ Welfare maximization with production costs: a primal dual approach ⋮ Introduction to the special issue -- Algorithmic game theory -- STOC/FOCS/SODA 2011 ⋮ Mechanisms for combinatorial auctions with budget constraints

Cites Work

• Inapproximability results for combinatorial auctions with submodular utility functions
• Informational limitations of ascending combinatorial auctions
• A threshold of ln n for approximating set cover
• An improved approximation algorithm for combinatorial auctions with submodular bidders
• Two Randomized Mechanisms for Combinatorial Auctions
• An analysis of approximations for maximizing submodular set functions—I
• On the Power of Randomization in Algorithmic Mechanism Design
• Symmetry and Approximability of Submodular Maximization Problems
• On Maximizing Welfare When Utility Functions Are Subadditive
• From query complexity to computational complexity
• An impossibility result for truthful combinatorial auctions with submodular valuations
• From convex optimization to randomized mechanisms
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Truthful randomized mechanisms for combinatorial auctions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Limitations of randomized mechanisms for combinatorial auctions