Budget-Constrained Auctions with Heterogeneous Items
Venue
Theory of Computing, vol. 8 (2012), pp. 429-460
Publication Year
2012
Authors
Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, Kamesh Munagala
BibTeX
Abstract
We present the first approximation algorithms for designing revenue-optimal
incentive-compatible mechanisms in the following setting: There are multiple
(heterogeneous) items, and bidders have arbitrary demand and budget constraints
(and additive valuations). Furthermore, the type of a bidder (which specifies her
valuations for each item) is private knowledge, and the types of different bidders
are drawn from publicly known mutually independent distributions. Our mechanisms
are surprisingly simple. First, we assume that the type of each bidder is drawn
from a discrete distribution with polynomially bounded support size. This
restriction on the type-distribution, however, allows the random variables
corresponding to a bidder’s valuations for different items to be arbitrarily
correlated. In this model, we describe a sequential all-pay mechanism that is
truthful in expectation and Bayesian incentive compatible. The outcome of our
all-pay mechanism can be computed in polynomial time, and its revenue is a
4-approximation to the revenue of the optimal truthful-in-expectation Bayesian
incentive-compatible mechanism. Next, we assume that the valuations of each bidder
for different items are drawn from mutually independent discrete distributions
satisfying the monotone hazard-rate condition. In this model, we present a
sequential posted-price mechanism that is universally truthful and incentive
compatible in dominant strategies. The outcome of the mechanism is computable in
polynomial time, and its revenue is a O(1)-approximation to the revenue of the
optimal truthful-in-expectation Bayesian incentive-compatible mechanism. If the
monotone hazard-rate condition is removed, then we show a logarithmic
approximation, and we complete the picture by proving that no sequential
posted-price scheme can achieve a sub-logarithmic approximation. Finally, if the
distributions are regular, and if the space of mechanisms is restricted to
sequential posted-price schemes, then we show that there is a O(1)-approximation
within this space. Our results are based on formulating novel LP relaxations for
these problems, and developing generic rounding schemes from first principles.
