An Algorithmic Characterization of Multi-Dimensional Mechanisms

Details An Algorithmic Characterization of Multi-Dimensional Mechanisms An Algorithmic Characterization of Multi-Dimensional Mechanisms

2011-12-20

arxiv.org/abs/1112.4572v1

Computer Science

Computer Science and Game Theory

Scientific paper

We obtain a characterization of feasible, Bayesian, multi-item multi-bidder auctions with independent, additive bidders as distributions over hierarchical mechanisms. Combined with cyclic-monotonicity our results provide a complete characterization of feasible, Bayesian Incentive Compatible (BIC) auctions for this setting. Our characterization is enabled by a novel, constructive proof of Border's theorem, and a new generalization of this theorem to independent (but not necessarily iid) bidders. For one item and independent bidders, we show that any feasible reduced form auction can be implemented as a distribution over hierarchical mechanisms. We also give a polytime algorithm for determining feasibility of a reduced form, or finding a separation hyperplane from feasible reduced forms. Finally, we provide polytime algorithms to find and exactly sample from a distribution over hierarchical mechanisms consistent with a given feasible reduced form. Our results generalize to multi-item reduced forms for independent, additive bidders. For multiple items, additive bidders with hard demand constraints, and arbitrary value correlation across items or bidders, we give a proper generalization of Border's theorem, and characterize feasible reduced forms as multicommodity flows in related multicommodity flow instances. We show that our generalization holds for a broader class of feasibility constraints, including intersections of any two matroids. As a corollary we obtain revenue-optimal, BIC mechanisms in multi-item multi-bidder settings, when each bidder has arbitrarily correlated values over the items and additive valuations over bundles, and bidders are independent. Their runtime is polynomial in the total number of bidder types (instead of type profiles), and is improved to poly(#items, #bidders) using recent structural results on optimal BIC auctions in item-symmetric settings.

Affiliated with

Also associated with

No associations

Rating

An Algorithmic Characterization of Multi-Dimensional Mechanisms 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 An Algorithmic Characterization of Multi-Dimensional Mechanisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Algorithmic Characterization of Multi-Dimensional Mechanisms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-54636