Bayesian Optimal Auctions via Multi- to Single-agent Reduction

Details Bayesian Optimal Auctions via Multi- to Single-agent Reduction Bayesian Optimal Auctions via Multi- to Single-agent Reduction

2012-03-22

arxiv.org/abs/1203.5099v1

Computer Science

Computer Science and Game Theory

Scientific paper

We study an abstract optimal auction problem for a single good or service. This problem includes environments where agents have budgets, risk preferences, or multi-dimensional preferences over several possible configurations of the good (furthermore, it allows an agent's budget and risk preference to be known only privately to the agent). These are the main challenge areas for auction theory. A single-agent problem is to optimize a given objective subject to a constraint on the maximum probability with which each type is allocated, a.k.a., an allocation rule. Our approach is a reduction from multi-agent mechanism design problem to collection of single-agent problems. We focus on maximizing revenue, but our results can be applied to other objectives (e.g., welfare). An optimal multi-agent mechanism can be computed by a linear/convex program on interim allocation rules by simultaneously optimizing several single-agent mechanisms subject to joint feasibility of the allocation rules. For single-unit auctions, Border \citeyearpar{B91} showed that the space of all jointly feasible interim allocation rules for $n$ agents is a $\NumTypes$-dimensional convex polytope which can be specified by $2^\NumTypes$ linear constraints, where $\NumTypes$ is the total number of all agents' types. Consequently, efficiently solving the mechanism design problem requires a separation oracle for the feasibility conditions and also an algorithm for ex-post implementation of the interim allocation rules. We show that the polytope of jointly feasible interim allocation rules is the projection of a higher dimensional polytope which can be specified by only $O(\NumTypes^2)$ linear constraints. Furthermore, our proof shows that finding a preimage of the interim allocation rules in the higher dimensional polytope immediately gives an ex-post implementation.

Affiliated with

Also associated with

No associations

Rating

Bayesian Optimal Auctions via Multi- to Single-agent Reduction 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 Optimal Auctions via Multi- to Single-agent Reduction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bayesian Optimal Auctions via Multi- to Single-agent Reduction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-382529