Limitations of VCG-based mechanisms

DOI10.1007/S00493-011-2528-4MaRDI QIDQ2454572zbMATHOpenAlexFDO

Authors Shahar Dobzinski, Noam Nisan

Publication date 13 June 2014

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.208.7960

zbMATH Keywords

communication complexitycombinatorial auctionssubmodular biddersVCG payment scheme

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25) Combinatorial games (91A46)

Recommendations

• Limitations of VCG-based mechanisms
• Computationally feasible VCG mechanisms
• Inapproximability for VCG-based combinatorial auctions
• Valuation compressions in VCG-based combinatorial auctions
• Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations

Cites work

• scientific article; zbMATH DE number 5343724 (Why is no real title available?)
• scientific article; zbMATH DE number 2086678 (Why is no real title available?)
• Algorithm for optimal winner determination in combinatorial auctions
• An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents
• An improved approximation algorithm for combinatorial auctions with submodular bidders
• Applications of approximation algorithms to cooperative games
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Bundling equilibrium in combinatorial auctions
• Combinatorial auctions with decreasing marginal utilities
• Competitive analysis of incentive compatible on-line auctions
• Computationally feasible VCG mechanisms
• Incentives in Teams
• Informational limitations of ascending combinatorial auctions
• Limitations of VCG-based mechanisms
• Mechanisms for multi-unit auctions
• On maximizing welfare when utility functions are subadditive
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• The communication requirements of efficient allocations and supporting prices
• Truth revelation in approximately efficient combinatorial auctions
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Truthful approximation mechanisms for restricted combinatorial auctions
• Truthful approximation schemes for single-parameter agents
• Truthful randomized mechanisms for combinatorial auctions

Cited in

(12)

• Computationally feasible VCG mechanisms
• Bounding the payment of approximate truthful mechanisms
• Commodity auctions and frugality ratios
• Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions
• scientific article; zbMATH DE number 7053320 (Why is no real title available?)
• Limitations of the upward separation technique
• Limitations of VCG-based mechanisms
• Limitations of VCG-based mechanisms
• Inapproximability for VCG-based combinatorial auctions
• Truthful mechanism design via correlated tree rounding
• Valuation compressions in VCG-based combinatorial auctions
• Two-player incentive compatible outcome functions are affine maximizers

This page was built for publication: Limitations of VCG-based mechanisms

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