Limitations of randomized mechanisms for combinatorial auctions
From MaRDI portal
Abstract: Recently, a randomized mechanism has been discovered [Dughmi, Roughgarden and Yan; STOC'11] for combinatorial auctions that is truthful in expectation and guarantees a (1-1/e)-approximation to the optimal social welfare when players have coverage valuations. This approximation ratio is the best possible even for non-truthful algorithms, assuming . Given the recent sequence of negative results for combinatorial auctions under more restrictive notions of incentive compatibility, this development raises a natural question: Are truthful-in-expectation mechanisms compatible with polynomial-time approximation in a way that deterministic or universally truthful mechanisms are not? In particular, can polynomial-time truthful-in-expectation mechanisms guarantee a near-optimal approximation ratio for more general variants of combinatorial auctions? We prove that this is not the case. Specifically, the result of Dughmi, Roughgarden and Yan cannot be extended to combinatorial auctions with submodular valuations in the value oracle model. (Absent strategic considerations, a (1-1/e)-approximation is still achievable in this setting.) More precisely, we prove that there is a constant gamma>0 such that there is no randomized mechanism that is truthful-in-expectation--- or even approximately truthful-in-expectation --- and guarantees an m^{-gamma}-approximation to the optimal social welfare for combinatorial auctions with submodular valuations in the value oracle model. We also prove an analogous result for the flexible combinatorial public projects (CPP) problem. Both our results present an unexpected separation between coverage functions and submodular functions, which does not occur for these problems without strategic considerations.
Recommendations
- Limitations of randomized mechanisms for combinatorial auctions
- An impossibility result for truthful combinatorial auctions with submodular valuations
- Truthful randomized mechanisms for combinatorial auctions
- Truthful randomized mechanisms for combinatorial auctions
- Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations
Cites work
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- scientific article; zbMATH DE number 5343724 (Why is no real title available?)
- scientific article; zbMATH DE number 5547873 (Why is no real title available?)
- A threshold of ln n for approximating set cover
- An analysis of approximations for maximizing submodular set functions—I
- An impossibility result for truthful combinatorial auctions with submodular valuations
- An improved approximation algorithm for combinatorial auctions with submodular bidders
- Combinatorial auctions. Foreword by Vernon L. Smith.
- From convex optimization to randomized mechanisms, toward optimal combinatorial auctions
- From query complexity to computational complexity
- Inapproximability for VCG-based combinatorial auctions
- Inapproximability results for combinatorial auctions with submodular utility functions
- Informational limitations of ascending combinatorial auctions
- Limitations of VCG-based mechanisms
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Maximizing submodular set functions subject to multiple linear constraints
- On maximizing welfare when utility functions are subadditive
- On the Power of Randomization in Algorithmic Mechanism Design
- Optimal approximation for the submodular welfare problem in the value oracle model
- Submodular maximization by simulated annealing
- Symmetry and Approximability of Submodular Maximization Problems
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Truthful randomized mechanisms for combinatorial auctions
- Two Randomized Mechanisms for Combinatorial Auctions
Cited in
(19)- Introduction to the special issue -- Algorithmic game theory -- STOC/FOCS/SODA 2011
- On the power of randomization in algorithmic mechanism design
- Better approximation for interdependent SOS valuations
- Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions
- Mechanisms for combinatorial auctions with budget constraints
- The Limitations of Optimization from Samples
- Limitations of Deterministic Auction Design for Correlated Bidders
- Learning in auctions: regret is hard, envy is easy
- Equilibria of greedy combinatorial auctions
- FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
- Welfare maximization with production costs: a primal dual approach
- Two Randomized Mechanisms for Combinatorial Auctions
- Auctions with interdependence and SOS: improved approximation
- Limitations of randomized mechanisms for combinatorial auctions
- Truthful randomized mechanisms for combinatorial auctions
- Truthful randomized mechanisms for combinatorial auctions
- An impossibility result for truthful combinatorial auctions with submodular valuations
- Limitations of VCG-based mechanisms
- Truthful mechanism design via correlated tree rounding
This page was built for publication: Limitations of randomized mechanisms for combinatorial auctions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2516249)
