Budget constrained auctions with heterogeneous items

Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, and Kamesh Munagala

Abstract

In this paper, we present the first approximation algorithms for the problem of designing revenue optimal Bayesian incentive compatible auctions when there are multiple(heterogeneous) items and when bidders have arbitrary demand and budget constraints (and additive valuations). Our mechanisms are surprisingly simple: We show that a sequential all-pay mechanism is a 4 approximation to the revenue of the optimal ex-interim truthful mechanism with a discrete type space for each bidder, where her valuations for different items can be correlated. We also show that a sequential posted price mechanism is a O(1) approximation to the revenue of the optimal ex-post truthful mechanism when the

type space of each bidder is a product distribution that satisfies the standard hazard rate condition. We further show a logarithmic approximation when the hazard rate condition

is removed, and complete the picture by showing that achieving a sub-logarithmic approximation, even for regular distributions and one bidder, requires pricing bundles of

items. Our results are based on formulating novel LP relaxations for these problems, and developing generic rounding schemes from first principles.

Details

Publication typeInproceedings
Published inProc. of ACM Symposium on Theory of Computing (STOC) 2010
PublisherAssociation for Computing Machinery, Inc.
> Publications > Budget constrained auctions with heterogeneous items