Theory of Computing
-------------------
Title : Budget-Constrained Auctions with Heterogeneous Items
Authors : Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, and Kamesh Munagala
Volume : 8
Number : 20
Pages : 429-460
URL : http://www.theoryofcomputing.org/articles/v008a020
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.
A preliminary version of this paper appeared in STOC 2010.