Inapproximability for VCG-based combinatorial auctions

MaRDI QIDQ5417646zbMATH OpenFDO

Authors Dave Buchfuhrer, Shaddin Dughmi, Hu Fu, Elchanan Mossel, Michael Schapira, Y. Singer, Chris Umans, Robert D. Kleinberg, Christos Papadimitriou

Publication date 22 May 2014

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Auctions, bargaining, bidding and selling, and other market models (91B26)

Recommendations

• Computationally feasible VCG mechanisms
• Inapproximability of truthful mechanisms via generalizations of the Vapnik-Chervonenkis dimension
• Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
• Limitations of VCG-based mechanisms
• Limitations of VCG-based mechanisms

Cited in

(16)

• Incentive compatible mulit-unit combinatorial auctions: a primal dual approach
• Limitations of VCG-based mechanisms
• Combinatorial auctions with verification are tractable
• Limitations of randomized mechanisms for combinatorial auctions
• Valuation compressions in VCG-based combinatorial auctions
• Black-box reductions in mechanism design
• Single-parameter combinatorial auctions with partially public valuations
• Computationally efficient approximation mechanisms
• Limitations of VCG-based mechanisms
• Computationally feasible VCG mechanisms
• Truthful optimization using mechanisms with verification
• Inapproximability of truthful mechanisms via generalizations of the Vapnik-Chervonenkis dimension
• Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions
• Truthful mechanism design via correlated tree rounding
• An algorithmic framework for black-box reductions from Bayesian mechanism design to algorithm design
• Fairness and incentive compatibility via percentage fees

This page was built for publication: Inapproximability for VCG-based combinatorial auctions

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