Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers

Details Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers

2011-06-06

arxiv.org/abs/1106.0961v2

Computer Science

Computer Science and Game Theory

To appear in FOCS 2011

Scientific paper

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) the buyers' types must be distributed independently (not necessarily identically), (ii) the objective function must be linearly separable over the set of buyers, and (iii) there should be no constraints involving multiple buyers except for the supply constraints. Our framework is general in the sense that it makes no explicit assumption about any of the following: (i) the buyers' 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 $n$-buyer mechanisms that use 1-buyer mechanisms as black boxes. Assuming that an $\alpha$-approximate 1-buyer mechanism can be constructed for each buyer and assuming that no buyer ever needs more than $\frac{1}{k}$ of all copies of each item for some integer $k \ge 1$, then our generic $n$-buyer mechanisms are $\gamma_k\cdot\alpha$-approximation of the optimal $n$-buyer mechanism, in which $\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 improve several results from the literature.

Affiliated with

Also associated with

No associations

Rating

Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-389051