Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers
- 1 October 2011
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 512-521
- https://doi.org/10.1109/focs.2011.90
Abstract
For Bayesian combinatorial auctions, we present a general framework for approximately reducing the mechanism design problem for multiple buyers to the mechanism design problem for each individual buyer. Our frame- work can be applied to any setting which roughly satisfies the following assumptions: (i) the buyer's types must be distributed independently (not necessarily identically), (ii) the objective function must be linearly separable over the set of buyers, and (iii) the supply constraints must be the only constraints involving more than one buyer. Our framework is general in the sense that it makes no explicit assumption about any of the following: (i) the buyer's valuations (e.g., submodular, additive, etc), (ii) The distribution of types for each buyer, and (iii) the other constraints involving individual buyers (e.g., budget constraints, etc). We present two generic ra-buyer mechanisms that use 1- buyer mechanisms as black boxes. Assuming that we have an α-approximate 1-buyer mechanism for each buyer and assuming that no buyer ever needs more than 1/k of all copies of each item for some integer k ≥ 1, then our generic n- buyer mechanisms are γ k · α-approximation of the optimal n-buyer mechanism, in which γ k is a constant which is at least 1 - 1/√(k+3). Observe that γ k is at least1/2 (for k = 1) and approaches 1 as k increases. As a byproduct of our construction, we improve a generalization of prophet inequalities. Furthermore, as applications of our main theorem, we improve several results from the literature.Keywords
Other Versions
This publication has 15 references indexed in Scilit:
- Bayesian Incentive Compatibility via MatchingsPublished by Society for Industrial & Applied Mathematics (SIAM) ,2011
- Mechanism Design via Correlation GapPublished by Society for Industrial & Applied Mathematics (SIAM) ,2011
- Budget constrained auctions with heterogeneous itemsPublished by Association for Computing Machinery (ACM) ,2010
- Bayesian algorithmic mechanism designPublished by Association for Computing Machinery (ACM) ,2010
- Multi-parameter mechanism design and sequential posted pricingPublished by Association for Computing Machinery (ACM) ,2010
- Simple versus optimal mechanismsPublished by Association for Computing Machinery (ACM) ,2009
- Single-value combinatorial auctions and implementation in undominated strategiesPublished by Association for Computing Machinery (ACM) ,2006
- Dependent rounding in bipartite graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Multiproduct Nonlinear PricingEconometrica, 1996
- A survey of prophet inequalities in optimal stopping theoryContemporary Mathematics, 1992