From convex optimization to randomized mechanisms, toward optimal combinatorial auctions

DOI10.1145/1993636.1993657MaRDI QIDQ5419084zbMATH OpenOpenAlexFDO

Authors Shaddin Dughmi, Tim Roughgarden, Qiqi Yan

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://doi.org/10.1145/1993636.1993657

zbMATH Keywords

algorithmic mechanism designcombinatorial auctions

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25) Welfare economics (91B15)

Recommendations

• Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding
• Truthful randomized mechanisms for combinatorial auctions
• Truthful randomized mechanisms for combinatorial auctions
• Limitations of randomized mechanisms for combinatorial auctions
• Two Randomized Mechanisms for Combinatorial Auctions

Cited in

(23)

• A bounded-risk mechanism for the kidney exchange game
• Fast convex decomposition for truthful social welfare approximation
• Mechanism design for perturbation stable combinatorial auctions
• Black-box reductions in mechanism design
• Time bounds for iterative auctions: a unified approach by discrete convex analysis
• Leveraging possibilistic beliefs in unrestricted combinatorial auctions
• A combinatorial auction improves school meals in Chile: a case of OR in developing countries
• Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers
• Recognizing Coverage Functions
• The Limitations of Optimization from Samples
• Limitations of randomized mechanisms for combinatorial auctions
• Learning in auctions: regret is hard, envy is easy
• Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding
• Welfare maximization with production costs: a primal dual approach
• scientific article; zbMATH DE number 5991658 (Why is no real title available?)
• Separating coverage and submodular: maximization subject to a cardinality constraint
• Oblivious rounding and the integrality gap
• Worst-case mechanism design via Bayesian analysis
• Matroid rank functions and discrete concavity
• A formulation of combinatorial auction via reverse convex programming
• Maximize liquid welfare in combinatorial auctions with monotone valuations
• Improved truthful mechanisms for combinatorial auctions with submodular bidders
• Truthful mechanism design via correlated tree rounding

This page was built for publication: From convex optimization to randomized mechanisms, toward optimal combinatorial auctions

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