Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers

Abstract

For Bayesian combinatorial auctions, we present a general framework for approximately reducing the mechanism design problem for multiple buyers to single buyer sub-problems. Our framework can be applied to any setting which roughly satisfies the following assumptions: (i) buyers' types must be distributed independently (not necessarily identically), (ii) objective function must be linearly separable over the buyers, and (iii) except for the supply constraints, there should be no other inter-buyer constraints. Our framework is general in the sense that it makes no explicit assumption about buyers' valuations, type distributions, and single buyer constraints (e.g., budget, incentive compatibility, etc). We present two generic multi buyer mechanisms which use single buyer mechanisms as black boxes; if an $\alpha$-approximate single buyer mechanism can be constructed for each buyer, and if no buyer requires more than $\frac{1}{k}$ of all units of each item, then our generic multi buyer mechanisms are ${\gamma }_k\alpha$-approximation of the optimal multi buyer mechanism, where ${\gamma }_k$ is a constant which is at least $1-\frac{1}{\sqrt{k+3}}$. Observe that ${\gamma }_k$ is at least 1/2 (for $k=1$) and approaches 1 as $k\to \infty$. As a byproduct of our construction, we present a generalization of prophet inequalities. Furthermore, as applications of our framework, we present multi buyer mechanisms with improved approximation factor for several settings from the literature.

A preliminary version was published in the proceedings of FOCS 2011

References in corpus (1)

• Approximation Schemes for Sequential Posted Pricing in Multi-Unit Auctions

Cited by in corpus (23)

• Beating 1-1/e for Ordered Prophets
• Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization
• Bayesian Optimal Auctions via Multi- to Single-agent Reduction
• Sampling and Representation Complexity of Revenue Maximization
• Mechanism Design for Subadditive Agents via an Ex-Ante Relaxation
• Understanding Incentives: Mechanism Design becomes Algorithm Design
• On Optimal Multi-Dimensional Mechanism Design
• Extreme-Value Theorems for Optimal Multidimensional Pricing
• Learning Multi-item Auctions with (or without) Samples
• Pricing Ad Slots with Consecutive Multi-unit Demand
• The Prophet Inequality Can Be Solved Optimally with a Single Set of Samples
• Polymatroid Prophet Inequalities
• Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods
• Prophet Secretary: Surpassing the $1-1/e$ Barrier
• Prophet Inequalities with Linear Correlations and Augmentations
• A Constructive Approach to Reduced-Form Auctions with Applications to Multi-Item Mechanism Design
• The Simple Economics of Approximately Optimal Auctions
• Prophet Inequalities for Matching with a Single Sample
• On Solutions for the Maximum Revenue Multi-item Auction under Dominant-Strategy and Bayesian Implementations
• Mechanism Design and Risk Aversion
• Matroid Prophet Inequalities
• On Simple Mechanisms for Dependent Items
• Optimal Pricing is Hard