Authors Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, Kamesh Munagala,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460
www.theoryofcomputing.org
S PECIAL ISSUE IN HONOR OF R AJEEV M OTWANI
Budget-Constrained Auctions with
Heterogeneous Items∗
Sayan Bhattacharya† Gagan Goel Sreenivas Gollapudi
Kamesh Munagala‡
Received: August 18, 2010; published: September 4, 2012.
Abstract: We present the first approximation algorithms for designing revenue-optimal
incentive-compatible mechanisms in the following setting: There are multiple (hetero-
geneous) 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
∗ A preliminary version of this paper appeared in STOC 2010.
† Supported by NSF grants CCF-0745761 and CCF-1008065.
‡ Supported by an Alfred P. Sloan Research Fellowship, a gift from Cisco, and by NSF grants CCF-0745761, CCF-1008065,
and IIS-0964560.
ACM Classification: G.1.6, J.4
AMS Classification: 68W25
Key words and phrases: mechanism design, approximation algorithms
2012 Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, and Kamesh Munagala
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2012.v008a020
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
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 truth-
ful 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.
1 Introduction
In several scenarios, such as the Google TV ad mechanism [31] and the FCC spectrum mechanisms [11],
where mechanisms have been applied in the recent past, bidders are constrained by the amount of money
they can spend. This leads to the study of mechanisms with budget-constrained bidders, which is the
focus of this paper. The key difficulty with budgets is that the utility of a bidder is equal to her valuation
minus price if and only if the price is below the budget constraint, and the utility is −∞ whenever the price
exceeds her budget. As a consequence, well-known mechanisms such as the VCG mechanism [17, 23, 34]
are no longer directly applicable. Before proceeding further, we formally define our model.
1.1 Our model
There are n bidders and m heterogeneous items. The type of a bidder, which is her private knowledge, is
an m-tuple representing her valuations for each item. Every bidder i has two publicly known constraints:
A demand constraint di on the maximum number of items she is willing to buy, and a budget constraint
Bi on the maximum total price she can afford to pay. In a mechanism, the bidders report their types to
the auctioneer, and based on the reported types, the auctioneer computes an allocation of the items and
payments. The utility of bidder i is defined as follows: Suppose that she gets a subset A of items where
|A| ≤ di , and pays a total price Pi . Let vi j denote the valuation of bidder i for item j. If Pi ≤ Bi , then the
utility of bidder i is equal to ∑ j∈A vi j − Pi . In contrast, if Pi > Bi , then her utility is −∞. The revenue of
the auctioneer is given by ∑i Pi . The mechanism should be incentive compatible in that no bidder gains in
utility by misreporting her type, and individually rational, meaning that a bidder gets nonnegative utility
if she reports her true type.
There are two well-established ways of proceeding from here. In the adversarial setting, no assump-
tions are made on the types of the bidders, while in the Bayesian setting, it is assumed that the bidders’
private types are drawn from mutually independent (but not necessarily identical) publicly known prior
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 430
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
distributions. We take the latter Bayesian approach, and our goal is to design an incentive-compatible and
individually-rational mechanism that (approximately) maximizes the expected revenue of the auctioneer.
This line of research was pioneered by Myerson [30].
1.2 Preliminaries
We first distinguish between four kinds of mechanisms that satisfy the incentive-compatibility (and
individual-rationality) constraints.
Dominant-strategy incentive-compatible (DSIC) Fix any bidder i. Suppose that her true type is ti .
• In a universally truthful DSIC mechanism, the utility of bidder i is maximized (at a nonnegative
value) when she reveals her true type ti , regardless of the types reported by other bidders and the
random choices made by the mechanism.
• In a truthful-in-expectation DSIC mechanism, the expected utility of bidder i (the expectation is
over the random choices made by the mechanism) is maximized (at a nonnegative value) when she
reveals her true type ti , regardless of the types reported by other bidders.
Bayesian incentive-compatible (BIC) Fix any bidder i and suppose that her true type is ti .
• In a universally truthful BIC mechanism, the expected utility of bidder i (the expectation is over the
prior distributions of the types of the other bidders) is maximized (at a nonnegative value) when
she reveals her true type ti , regardless of the random choices made by the mechanism.
• In a truthful-in-expectation BIC mechanism, the expected utility of bidder i (the expectation is
over the prior distributions of the types of the other bidders and the random choices made by the
mechanism) is maximized (at a nonnegative value) when she reveals her true type ti .
Note that if a mechanism is universally truthful DSIC, then the same mechanism satisfies all of the other
three notions of incentive compatibility. On the other hand, the union of all the universally truthful
DSIC, truthful-in-expectation DSIC, and universally truthful BIC mechanisms is a subset of the set of all
truthful-in-expectation BIC mechanisms. Hence, among the four notions described above, universally
truthful DSIC (respectively, truthful-in-expectation BIC) is the strongest (respectively, weakest) notion of
incentive compatibility.
A standard assumption in Economics is that a bidder’s valuation for an item is drawn from a
distribution satisfying some useful properties. Specifically, we will be interested in the following classes
of distributions.
Definition 1.1. Suppose that the valuation of a bidder i for item j is a discrete random variable vi j with
integral support {1, . . . , Li j }. The distribution of vi j is regular if and only if
Pr[vi j > r]
r−
Pr[vi j = r]
is a non-decreasing function of r ∈ {1, . . . , Li j }.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 431
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
Definition 1.2. Suppose that the valuation of a bidder i for item j is a discrete random variable vi j with
integral support {1, . . . , Li j }. The distribution of vi j is monotone hazard rate if and only if
Pr[vi j > r]
Pr[vi j = r]
is a non-increasing function of r ∈ {1, . . . , Li j }.
Note that if a distribution is monotone hazard rate, then it is regular. Examples of monotone hazard-
rate distributions include geometric distributions and uniform distributions. In contrast, if we have
Pr[vi j ≥ r] = 1/r for r = 1, 2, . . . , Li j , then the distribution of vi j is regular but not monotone hazard rate.
Finally, if we have a bimodal distribution, such as Pr[vi j = 1] = Pr[vi j = 3] = 4/9 and Pr[vi j = 2] = 1/9,
then it is easy to check that the random variable vi j does not follow a regular distribution.
1.3 Our results
Recall that the type of a bidder is an m-tuple representing her valuations for each item, and the types of
different bidders follow mutually independent public distributions. From the type-distribution of a bidder
i, we can determine the distribution of the random variable vi j , which denotes the valuation of bidder i
for item j. Our results depend on whether the random variables {vi j } j (denoting the valuations of the
same bidder for different items) are correlated or mutually independent. All our results can be viewed as
presenting simple characterizations of approximately revenue-optimal mechanisms in these contexts.
1.3.1 Our result in Section 2
We consider the following scenario in Section 2: For every bidder i, the random variables {vi j } j (denoting
the valuations of bidder i for different items) can be arbitrarily correlated. However, the type of bidder i is
drawn from a discrete distribution with polynomially bounded support size.
Truthful-in-expectation BIC mechanism We present a simple all-pay mechanism whose outcome
is computable in time polynomial in the input size. The mechanism charges each bidder a fixed price
that depends only on her revealed type, while the allocation made to the bidder depends on the reported
types of other bidders and the random choices made by the mechanism. The resulting scheme is truthful-
in-expectation BIC, and we show that its revenue is a 4-approximation to the revenue of the optimal
truthful-in-expectation BIC mechanism (Theorem 2.2).
Inapproximability of the optimal universally truthful DSIC mechanism An all-pay mechanism is
unrealistic in several situations, since a bidder is forced to participate even if she obtains a negative utility
when the mechanism concludes. A natural question to ask is whether we can compute a universally
truthful DSIC mechanism with good revenue properties. We can show that this problem generalizes the
problem of unlimited supply unit-demand profit-maximizing envy-free pricing [24], as described below.
Consider a single bidder and m items, and suppose that the bidder’s type is drawn from a uniform
distribution over the discrete set T = {t(1) , . . . , t(n) } of size n, and that the bidder has unit demand and
infinite budget. In this setting, the optimal universally truthful DSIC mechanism will post a price for each
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 432
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
item, and it will allow the bidder to pick the item that gives her maximum (nonnegative) utility. This
is exactly equivalent to the following instance of the unlimited supply unit-demand envy-free pricing
problem [24]: We have m items and n agents, and the valuation profile of each agent i ∈ {1, . . . , n} (which
gives her valuations for each item) is specified by the type t(i) .
For the unlimited supply unit-demand envy-free pricing problem, the best known polynomial-time
algorithm gives a logarithmic approximation, and there is strong evidence that a better polynomial-time
approximation is not possible [9]. Consequently, it is highly unlikely that we will be able to design a
polynomial-time computable and universally truthful DSIC mechanism with good revenue properties. In
Section 3, we impose further restrictions on the type-distributions to circumvent this negative result.
1.3.2 Our results in Section 3
We make the following assumption throughout Section 3: For every bidder i, the random variables {vi j } j
(denoting the valuations of bidder i for different items) are mutually independent. However, in contrast to
Section 2, we no longer require that the type-distribution of a bidder should have polynomial support.
The assumption mentioned above has been used previously in the literature. The work of Chawla
et al. [12] considers the special case of a single bidder with unit-demand and infinite budget, whose
valuations for different items are drawn from mutually independent public distributions. For this problem,
Chawla et al. give a constant factor approximation to the revenue maximizing universally truthful DSIC
mechanism, by deriving an elegant connection to Myerson’s mechanism [30]. Independently of our work,
Chawla et al. [13] extend the previous result to a setting with multiple bidders. However, this result also
crucially requires the unit-demand assumption.
Monotone hazard rates and universally truthful DSIC mechanism In Section 3.2, we further as-
sume that for every bidder i and item j, the random variable vi j (denoting the valuation of bidder i for
item j) is drawn from a distribution that satisfies the monotone hazard-rate (Definition 1.2) condition.
We give a universally truthful DSIC mechanism, whose outcome is computable in polynomial time, and
whose revenue is a constant-factor approximation to the revenue of the optimal truthful-in-expectation
BIC mechanism. Our mechanism is a Sequential Posted Price scheme. Any sequential posted-price
scheme has the following simple structure: The auctioneer considers the bidders sequentially in arbitrary
order, and each bidder is offered a subset of the available items, so that each item in the subset has to be
purchased at a pre-computed price, and the bidder herself picks the items she wants to buy under these
prices. Hence, we get a constant-factor gap between the revenues of the optimal truthful-in-expectation
BIC mechanism and the optimal universally truthful DSIC mechanism (Theorem 3.14), which is in sharp
contrast with the corresponding negative result [10] when the valuations of a bidder for different items
are drawn from correlated distributions.
Regular distributions and adaptive posted-price mechanisms In Section 3.3, we show that the
monotone hazard-rate condition is indeed necessary if we want to design a sequential posted-price
mechanism with good revenue properties. Suppose that the monotone hazard-rate condition is slightly
relaxed, and we consider the scenario where there is a single bidder and her valuations for different items
are drawn from mutually independent regular distributions (Definition 1.1). In this case, the optimal
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 433
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
universally truthful DSIC mechanism will have a logarithmic gap against the revenue of the optimal
sequential posted-price scheme. We prove that this gap is tight by showing the existence of a sequential
posted-price mechanism achieving this approximation ratio (Theorem 3.16). On a positive note, we prove
that for regular distributions, if the space of feasible mechanisms is restricted to those that consider the
bidders in some adaptive order and post prices for the items that may depend on the outcomes so far, then
there is a O(1)-approximation within this space that considers the bidders in an arbitrary but fixed order,
and pre-computes the posted prices (Theorem 3.21).
1.4 Related work
The Bayesian setting is widely studied in the economics literature [5, 11, 14, 15, 27, 29, 32, 33, 35]. In
this setting, the optimal mechanism can always be computed by encoding the incentive-compatibility
constraints in an integer program and maximizing expected revenue. However, the number of variables
(and constraints) in this IP is exponential in the number of bidders, as there are variables for the allocations
and prices for each scenario of revealed types. Therefore, the key difficulty in the Bayesian mechanism
design case is computational: Can the optimal (or approximately optimal) mechanism be efficiently
computed and implemented?
Much of the literature in economics considers the case where the auctioneer has one item (or multiple
copies of one item). In the absence of budget constraints, Myerson [30] presents the characterization of
any BIC mechanism in terms of expected allocation made to a bidder: This allocation must be monotone
in the revealed valuation of the bidder. This yields a linear-time computable optimal revenue-maximizing
mechanism that is both BIC and DSIC. The key issue with budget constraints is that the allocations need
to be thresholded in order for the prices to be below the budgets [14, 27, 32]. However, even in this
case, the optimal BIC mechanism follows from a polymatroid characterization that can be solved by the
Ellipsoid algorithm and an all-pay condition [7, 32]. By all-pay, we mean that the bidder pays a fixed
amount given his revealed type, regardless of the allocation made. This also yields a DSIC mechanism
that is an O(1)-approximation to the optimal BIC revenue [6], but the result holds only for homogeneous
items.
An alternative line of work deals with the adversarial setting, where no distributional assumption
is made on the bidders’ private valuations. In this setting, the budget-constrained mechanism problem
is notorious, mainly because standard mechanism concepts such as VCG, efficiency, and competitive
equilibria do not directly carry over [31]. Most previous results deal with the case of multiple units
of a homogeneous good. In this setting, based on the random partitioning framework of Goldberg et
al. [22, 21], Borgs et al. [8] presented an incentive-compatible mechanism whose revenue is asymptotically
within a constant factor of the optimal revenue (see also [1]). Furthermore, Borgs et al. showed that no
incentive-compatible mechanism can (approximately) maximize social welfare [8]. Consequently, the
focus has been on weaker notions than efficiency, such as Pareto-optimality, where no pair of agents
(including the auctioneer) can simultaneously improve their utilities by trading with each other. Dobzinski
et al. [18] present an ascending price mechanism based on the clinching mechanism of Ausubel [3],
which they show to be the only Pareto-optimal mechanism in the public budget setting. This result was
extended to the private budget setting by Bhattacharya et al. [6]; see [25] for a related result.
Finally, several researchers have considered restricted scenarios. The first type of restriction is on the
type of mechanism; examples include mechanisms that are sequential by item and second price within
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 434
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
each item [5, 20], and ascending price mechanisms [4, 11]. The goal here is to analyze the improvement
in revenue (or social welfare) by optimal sequencing, or to study incentive compatibility of commonly
used ascending price mechanisms. However, analyzing the performance of sequential or ascending price
mechanisms is difficult in general, and there is little known in terms of optimal mechanisms (or even
approximately optimal mechanisms) in these settings. A different type of restriction is on the valuations
of each bidder. The most well-known instance is keyword search mechanisms [19], where the items are
ad slots, and the bidder valuations are typically single-dimensional, with the valuations for each slot being
scaled down by a publicly known value. However, these mechanisms have typically been considered
without budget constraints, and the goal here has been to analyze mechanisms used in practice, such as
the generalized second-price mechanism [19].
1.5 Our techniques
If, for every bidder, the valuations for different items are drawn from correlated distributions (Section 2),
then the optimal truthful-in-expectation BIC revenue can be bounded from above by a linear program
(LP1) that requires the incentive-compatibility, individual-rationality, supply, and demand constraints
to hold only in expectation. We construct a truthful-in-expectation BIC all-pay mechanism (Figure 1)
that basically implements a rounding scheme on the optimal solution to LP1, losing a constant factor in
revenue (Theorem 2.2). This approach is based on the techniques used in [6].
As mentioned before, Chawla et al. [12] consider the Bayesian unit-demand pricing problem. There
are m heterogeneous items, a single bidder with unit demand, and her valuations (v j for item j ∈ [1, . . . , m])
are drawn from independent distributions. They present an elegant pricing scheme that is a constant
approximation to the optimal revenue by upper bounding it using the revenue of Myerson’s mechanism in
the following setting: There is a single item, m bidders, and the valuation of each bidder j follows the
same distribution as that of v j . However, this technique cannot be applied if the unit demand assumption
is removed.
In contrast, our approach in Section 3 (where the valuations of a bidder for different items are drawn
from mutually independent distributions) does not require the unit-demand assumption, and is based on
a novel LP relaxation (LPR EV) for the problem (Lemma 3.3). Unlike the LP relaxation of Section 2,
and perhaps surprisingly, LPR EV does not encode any incentive-compatibility constraints, and our
universally truthful DSIC mechanism (Figure 2), which competes against this LP, is in fact a constant
approximation to the optimal truthful-in-expectation BIC revenue. One limitation of our approach is
that we have to (necessarily) assume that the bidders’ valuations are drawn from montone hazard rate
distributions (Definition 1.2). In the process of proving our main result (Theorem 3.14), we describe a
crucial property of monotone hazard rate distributions (Lemma 3.9) that can be used to extend the type of
results shown in [26]. For example, in multi-item settings with only demand constraints, posted-price
schemes generate revenue that is a constant factor of the optimal social welfare, assuming monotone
hazard rate distributions (Corollary 3.15). The LP formulations also generalize the stochastic matching
setting in Chen et al. [16].
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 435
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
2 Truthful-in-expectation BIC mechanism
In this section, we consider the problem of approximating the optimal Bayesian incentive-compatible
mechanism. We show an all-pay mechanism that is a 4-approximation to optimal revenue. Our solution
techniques are inspired by the LP relaxation and rounding scheme in [6] for multi-unit mechanisms.
2.1 Notations
There is a set I of n bidders, and a set J of m indivisible items. A type t is an m-tuple ht(1), t(2), . . . , t(m)i.
If a bidder i ∈ I has type ti , then her valuation for item j ∈ J is given by vi j = ti ( j). Every bidder i ∈ I
has a demand di ≥ 1, which upper bounds the number of items that can be allocated to her, and a budget
Bi , which specifies the maximum total payment she can make. Both her demand and budget are publicly
known. Suppose that she gets a subset A ⊆ J of items, where |A| ≤ di , and is charged a price of P. Her
utility ui (A, P) is given by the following expression.
(
−∞ if P > Bi ,
ui (A, P) =
∑ j∈A vi j − P if P ≤ Bi .
The type of a bidder i ∈ I is private knowledge. Furthermore, it is drawn from a discrete probability
distribution fi (·) with support Ti ⊆ Rm . For all ti ∈ Ti , we have fi (ti ) = Pr[type of bidder i = ti ], and
∑ti ∈Ti fi (ti ) = 1. The distributions f1 (·), . . . , fn (·) are mutually independent and publicly known. The
notation fi j (·) denotes the marginal distribution of the valuation of bidder i ∈ I for item j ∈ J:
fi j (v) = Pr[vi j = v] = ∑ fi (ti ) .
ti ∈Ti : ti ( j)=v
The distribution fi j (·) has support Ti j , that is, Ti j = {v ∈ R : fi j (v) > 0}. Note that a bidder’s valuations
for different items can be correlated. Specifically, we may have
Pr[vi j = v | vi j0 = v0 ] 6= fi j (v) for some bidder i, items j 6= j, and v ∈ Ti j , v0 ∈ Ti j0 .
In a mechanism, the bidders first report their types. Based on these reported types, the auctioneer
computes an allocation of items and payments. The price charged to a bidder i should not exceed her
budget Bi , and the number of items allocated to bidder i should be at most di .
2.2 The problem and the LP-relaxation
We want to find an mechanism that is incentive compatible (and individually rational) in the following
sense: Fix any bidder i and suppose that her (private) type is ti . Her expected utility, where the expectation
is over the distributions of types of other bidders and the random choices made by the mechanism, is
maximized (at a nonnegative value) if she reveals her true type ti . We are interested in a mechanism
that (approximately) maximizes the expected revenue, and can be computed in time polynomial in the
input size, i. e., in n, m, and maxi∈I {|Ti |}. Throughout the rest of Section 2, we will make the following
assumption.
Assumption 2.1. The distributions f1 (·), . . . , fn (·) have polynomial supports.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 436
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
Linear programming relaxation For any feasible mechanism, let xi j (ti ) denote the probability that
bidder i obtains item j if her reported type is ti . Let Pi (ti ) denote the expected price paid by bidder i when
she reports type ti . We have the following LP.
Maximize ∑ ∑ fi (ti )Pi (ti ) (LP1)
i∈I ti ∈Ti
∑i∈I ∑ti ∈Ti fi (ti )xi j (ti ) ≤ 1 ∀j ∈ J
∑ j∈J xi j (ti ) ≤ di ∀i ∈ I, ti ∈ Ti
∑ j∈J ti ( j)xi j (ti ) − Pi (ti ) ≥ ∑ j∈J ti ( j)xi j (t0i ) − Pi (t0i ) ∀i ∈ I, ti , t0i ∈ Ti
∑ j∈J ti ( j)xi j (ti ) − Pi (ti ) ≥ 0 ∀i ∈ I, ti ∈ Ti
xi j (ti ) ∈ [0, 1] ∀i ∈ I, j ∈ J,t ∈ Ti
Pi (ti ) ∈ [0, Bi ] ∀i ∈ I, ti ∈ Ti
The optimal truthful-in-expectation BIC mechanism is feasible for the above constraints. The first
constraint encodes the fact that, in expectation, each item is assigned at most once. Now fix any bidder
i ∈ I, and suppose that her true type is ti ∈ Ti . The second constraint encodes the demand: Bidder i can
get at most di items in expectation. The third constraint encodes Bayesian incentive-compatibility: The
expected utility of bidder i, when she reports any false type t0i , cannot be greater than her expected utility
when she reports her true type ti . The fourth constraint encodes individual rationality: If bidder i reports
her true type ti , then her expected utility is nonnegative. Therefore, the LP1 value is an upper bound on
the expected revenue.
Remark Fix any bidder i ∈ I. Note that the first constraint in LP1 holds in expectation over both her
own type and the types of other bidders. In contrast, the next three constraints are enforced for every
possible type ti ∈ Ti , and in these constraints the expectations are taken only over the types of other
bidders.
2.3 The all-pay mechanism
Suppose that the optimal solution to LP1 assigns a value of xi∗j (ti ) (respectively, Pi∗ (ti )) to each variable
xi j (ti ) (respectively, Pi (ti )). We design an all-pay mechanism (Figure 1). The key observation is that
the mechanism satisfies the following property: Fix any bidder i ∈ I and her reported type t∗i ∈ Ti .
Furthermore, suppose that every other bidder i0 ∈ I \ {i} reveals her true type. In this case, the probability
that bidder i gets any item j ∈ J, over the randomness introduced by the mechanism and the distributions
of types of other bidders, is equal to xi∗j (t∗i )/4; bidder i is charged a fixed payment of Pi∗j (t∗i )/4. Since
both the expected allocation and the payment are scaled down by exactly the same factor [2, 28], this
scheme preserves the Bayesian incentive-compatibility and individual-rationality conditions enforced by
the constraints in LP1. Finally, note that the auctioneer’s expected revenue is given by the expression
fi (ti ) · Pi∗ (ti )
∑∑ ,
i∈I ti ∈Ti 4
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 437
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
All-Pay Mechanism
1. Collect the reported types of all bidders. Denote the reported type of bidder i by t∗i .
2. Find the optimal solution to LP1, and denote the variable values by {xi∗j (ti ), Pi∗ (ti )}.
3. Choose an arbitrary but fixed ordering of all bidders and denote it by 1, 2, . . . , n.
4. For all bidders i = 1, 2, . . . , n, items j ∈ J and types ti ∈ Ti , let
x̃i j (ti ) = xi∗j (ti )/2 , Xi j = ∑ti ∈Ti fi (ti )x̃i j (ti ) , Zi j = ∏ii−1
0 =1 (1 − Xi0 j ) .
5. F OR all bidders i and types ti ∈ Ti ,
Partition the set of items J into di disjoint groups such that
in each group G(i, ti , k), we have ∑ j∈G(i,ti ,k) x̃i j (ti ) ≤ 1.
6. F OR i = 1, 2, . . . n,
Initialize Wi , Si ← 0; /
F OR k = 1 to di
Pick a single item j ∈ G(i, t∗i , k) with probability x̃i j (t∗i );
Si ← Si ∪ { j};
Qi ← Si \ ∪i−1 i0 =1 Si ;
0
F OR A LL items j ∈ Qi
Wi ← Wi ∪ { j} with probability 1/(2Zi j );
Bidder i gets the (random) set Wi , and pays a (fixed) price Pi∗ (t∗i )/4.
Figure 1: BIC Mechanism for correlated valuations
which is 1/4 times the optimal objective value of LP1. Hence, the mechanism gives a 4-approximation
to optimal revenue.
In Step 1 of the All-Pay Mechanism (Figure 1), we ask the bidders to reveal their types. The reported
type of bidder i ∈ I is denoted by t∗i . In Step 2, we solve (LP1). In Step 3, we order the bidders as
1, 2, . . . , n. In Step 4, we scale down the values of the allocation variables by a factor of 2, and introduce
the notations x̃i j (ti ), Xi j and Zi j . Applying the second constraint in LP1, we get ∑ j∈J x̃i j (ti ) ≤ di /2, for
all bidders i ∈ I and types ti ∈ Ti . In Step 5, we exploit this property while partitioning the set of items J
into di disjoint groups. Specifically, we employ the following greedy strategy.
• Initialize V ← J and k ← 1.
• R EPEAT UNTIL V = 0/
– Pack maximal number of items from V into the group G(i, ti , k), so that we have
1/2 ≤ ∑ x̃i j (ti ) ≤ 1 .
j∈G(i,ti ,k)
– Set V ← V \ G(i, ti , k) and k ← k + 1.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 438
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
In Step 6, we visit the bidders according to the ordering 1, 2, . . . , n. While visiting bidder i, the notation
Si denotes the tentative allocation to bidder i, whereas her actual allocation is denoted by Wi . Each
item j ∈ J is included in Si with probability x̃i j (t∗i ). Since the set Si contains at most one item from
each group G(i, t∗i , k) and there are di such groups, we get |Si | ≤ di , and hence at most di items can be
allocated to bidder i. The notation Qi denotes a subset of Si , consisting of all the items in Si that were
not included in the tentative allocation of any bidder i0 < i. Each item j ∈ Qi is included in Wi with
probability 1/(2Zi j ). Bidder i gets the (random) set of items Wi and pays a (fixed) price Pi∗ (t∗i )/4. Note
that the subsets Q1 , . . . , Qm are mutually disjoint by definition, and furthermore we have Wi ⊆ Qi for all
bidders i = 1, . . . , n. Hence, the subsets of items W1 , . . . ,Wn allocated to the different bidders are also
mutually disjoint.
Theorem 2.2. The All-Pay Mechanism (Figure 1) is truthful-in-expectation BIC, and its revenue is a
4-approximation to the revenue of the optimal truthful-in-expectation BIC mechanism.
Proof. Applying the first constraint in LP1, we get ∑i Xi j ≤ 1/2 for all items j. The inequality holds
since we scaled down the LP variables by a factor of 2. Consequently, we have
1
Zi j = ∏(1 − Xi j ) ≥ 1 − ∑ Xi j ≥ .
i0 <i i0 <i 2
This implies 1/(2Zi j ) ≤ 1.
Fix a bidder i, her reported type t∗i , an item j, and suppose that every other bidder i0 6= i reveals her
true type. In other words, the reported type of any bidder i0 6= i follows the distribution fi0 (·). Hence, for
all bidders i0 6= i, we have
Pr[ j ∈
/ Si0 ] = 1 − Pr[ j ∈ Si0 ] = 1 − ∑ fi0 (ti0 )x̃i0 j (ti0 ) = 1 − Xi0 j .
ti0 ∈Ti0
We now show that bidder i gets item j with probability xi∗j (t∗i )/4:
Pr[ j ∈ Wi ] = Pr[ j ∈ Wi | j ∈ Qi ] · Pr[ j ∈ Qi ]
h i−1
[ i
= Pr[ j ∈ Wi | j ∈ Qi ] · Pr j ∈ Si \ Si0
i0 =1
i−1
= Pr[ j ∈ Wi | j ∈ Qi ] · Pr[ j ∈ Si ] · ∏ Pr[ j ∈
/ Si0 ] (2.1)
i0 =1
i−1
1
= · x̃i j (t∗i ) · ∏ (1 − Xi0 j )
2Zi j i0 =1
1
= · x̃i j (t∗i ) · Zi j
2Zi j
xi∗j (t∗i )
= .
4
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 439
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
Equality (2.1) holds since the distributions of types of all the bidders are mutually independent, and we
have assumed that every bidder i0 6= i reveals her true type.
By linearity of expectation, the expected welfare of items allocated to bidder i is given by the
expression
1
ti ( j) · xi∗j (t∗i ) ,
4∑j∈J
when her true type is ti . Since bidder i pays a fixed price Pi∗ (t∗i )/4, both the expected welfare and expected
price are scaled down by a factor exactly 4 relative to the LP values regardless of her revealed type. This
preserves the incentive-compatibility constraints in the LP, and makes the scheme be incentive compatible
and satisfy individual rationality in expectation over the types of other bidders and the randomness
introduced by the mechanism. The theorem follows.
Remark We note that if the objective function is replaced with
∑ ∑ ∑ fi (ti )ti ( j)xi j (ti ) ,
i∈I j∈J ti ∈Ti
then the resulting scheme gives a 4-approximation to the optimal expected social welfare.
3 Universally truthful DSIC mechanisms
We described an all-pay mechanism (Figure 1) in Section 2 that gives constant approximation to optimal
revenue. This mechanism, however, is truthful-in-expectation BIC; for example, a bidder has to pay a
fixed price even if she does not get any item in a random allocation. In contrast, it is more desirable in
practice to implement mechanisms that are universally truthful DSIC and have good revenue properties.
Unfortunately, we cannot achieve this goal unless we make additional assumptions on the input, for the
following reason: The setting considered in Section 2 allows a bidder’s valuations for different items to
be drawn from correlated distributions, and it is computationally hard to approximate the revenue-optimal
universally truthful DSIC mechanism [9] under such settings (see Section 1.3.1). We now formally state
the assumptions that will be used throughout the rest of Section 3 to circumvent this hardness. We use the
same notations as in Section 2.1.
Assumption 3.1. We assume that the marginal distributions { fi j (·)}i∈I, j∈J are mutually independent (see
Section 2.1), and any distribution fi j (·) has a support Ti j = {1, . . . , Li j }, where Li j is a positive integer. In
other words, the valuation of bidder i for item j is a positive integer-valued random variable vi j ∈ [1, Li j ]
with probability mass function fi j (·), and the random variables {vi j }i∈I, j∈J are mutually independent.
Note that, in contrast to Section 2.2, we no longer require the distributions f1 (·), . . . , fn (·) to have
polynomial supports. Furthermore, the assumption that the distributions fi j (·) are defined at positive
integer values is made without any loss of generality, since we can discretize continuous distributions in
powers of (1 + ε) and apply the same arguments. This also holds when the values taken by the random
variables are not polynomially bounded.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 440
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
Sequential posted-price mechanisms In this section, our main results are sequential posted-price
mechanisms that give good approximations to optimal revenue. Such a mechanism considers the bidders
sequentially in arbitrary order, and for each bidder, posts a certain price for each item, and lets the bidder
select the subset of items she wants to buy under these prices. Note that any sequential posted-price
mechanism is universally truthful DSIC by definition.
Our results We first consider the scenario where the random variables vi j satisfy the monotone hazard-
rate condition (Section 3.2). In this case, we present a sequential posted-price mechanism, and show
that it is a O(1)-approximation to the optimal truthful-in-expectation BIC mechanism (Theorem 3.14).
One of the interesting aspects of this result is that although our mechanism is universally truthful DSIC
(which is the strongest notion of incentive compatibility), it still approximates the revenue of the optimal
truthful-in-expectation BIC mechanism.
In Section 3.3, we relax the monotone hazard rate assumption, and consider the scenario where
the random variables vi j are arbitrary integer-valued variables over the domain [1, L], that is, Li j = L
for all i ∈ I, j ∈ J. In this case, we present a sequential posted-price mechanism that gives O(log L)-
approximation to the revenue of the optimal universally truthful DSIC mechanism, and we also prove that
no other sequential posted-price mechanism can achieve an asymptotically better approximation ratio
(Theorem 3.16).
3.1 Linear programming relaxation
We start with a simple definition.
Definition 3.2. For all i ∈ I, j ∈ J: Define Vi j = min(vi j , Bi /4), let its probability mass function be gi j (·),
and let Ri j = {1, . . . , |Ri j |} be the range of values the random variable Vi j can possibly take. Since the
random variable vi j takes integer values in the range {1, . . . , Li j }, we get
fi j (r) if r < Bi /4 ,
Li j
Pr[Vi j = r] = gi j (r) = ∑v=r fi j (v) if r = Bi /4 ,
0 otherwise.
We now describe an LP-relaxation in order to upper bound the revenue of the optimal truthful-in-
expectation BIC mechanism.
Maximize ∑ ∑ ∑ r · gi j (r) · xi j (r) (LPR EV)
i∈I j∈J r∈Ri j
∑ j∈J ∑r∈Ri j gi j (r) · xi j (r) ≤ ni ∀i ∈ I (1)
∑ j∈J ∑r∈Ri j r · gi j (r) · xi j (r) ≤ Bi ∀i ∈ I (2)
∑i∈I ∑r∈Ri j gi j (r) · xi j (r) ≤ 1 ∀j ∈ J (3)
xi j (r) ∈ [0, 1] ∀i ∈ I, j ∈ J, r ∈ Ri j (4)
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 441
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
Lemma 3.3. The optimal value of the linear program (LPR EV) is at least 1/4 times the revenue of the
optimal truthful-in-expectation BIC mechanism. Furthermore, in the LP solution, xi j (r) is a monotonically
non-decreasing function of r, for all bidders i ∈ I and items j ∈ J.
Proof. Without any loss of generality, we assume that whenever a bidder is allocated a subset of items,
the total price she has to pay is distributed amongst the individual items obtained. It is easy to ensure that
the expected price on a single item is never greater than the valuation for the item or the overall budget.
Given that Vi j = r ∈ Ri j , let xi j (r) denote the probability that item j ∈ J is allocated to bidder i ∈ I, and
let pi j (r) denote the expected price paid conditioned on obtaining the item. Since Vi j = min(vi j , Bi /4), it
is easy to see that
pi j (r) ≤ min(vi j , Bi ) ≤ 4 · min(vi j , Bi /4) = 4 · r .
Hence, the revenue of the optimal truthful-in-expectation BIC mechanism can be relaxed as:
Maximize ∑ ∑ ∑ pi j (r) · gi j (r) · xi j (r)
i∈I j∈J r∈Ri j
∑ j∈J ∑r∈Ri j gi j (r) · xi j (r) ≤ ni ∀i ∈ I (1)
∑ j∈J ∑r∈Ri j pi j (r) · gi j (r) · xi j (r) ≤ Bi ∀i ∈ I (2)
∑i∈I ∑r∈Ri j gi j (r) · xi j (r) ≤ 1 ∀j ∈ J (3)
xi j (r) ∈ [0, 1] ∀i ∈ I, j ∈ J, r ∈ Ri j (4)
pi j (r) ∈ [0, 4r] ∀i ∈ I, j ∈ J, r ∈ Ri j (5)
The above program is nonlinear. Scale pi j (r) down by a factor of 4 so that pi j (r) ≤ r. This preserves
the constraints and loses a factor of 4 in the objective. Now, for all i, j, if pi j (r) < r, increase pi j (r)
and decrease xi j (r) while preserving their product until pi j (r) becomes equal to r. This yields the
constraints of (LPR EV ), and preserves the value of the objective function; but now, the objective becomes
∑i, j ∑r rgi j (r)xi j (r). This shows that (LPR EV) is a 4-approximation to the revenue of the optimal
truthful-in-expectation BIC mechanism.
To show that the objective is maximized when the xi j (r) are monotonically non-decreasing in r, for
any (i, j), preserve ∑r rgi j (r)xi j (r) by increasing xi j (r2 ) and decreasing xi j (r1 ) for r1 < r2 . In this process,
∑r gi j (r)xi j (r) can never increase (see Corollary 3.4), preserving all the constraints, which implies the
monotonicity.
Corollary 3.4. Fix any bidder i ∈ I, item j ∈ J, and r1 , r2 ∈ Ri j such that r1 < r2 . Furthermore, let
φi j (r) be any positive non-decreasing function of r ∈ Ri j . If we have 0 < xi j (r1 ), xi j (r2 ) < 1, and we
preserve ∑r∈Ri j φi j (r)gi j (r)xi j (r) while increasing xi j (r2 ) and decreasing xi j (r1 ), then the expression
∑r∈Ri j gi j (r)xi j (r) can never increase.
Proof. Suppose that we increase xi j (r2 ) by an amount δ2 > 0, and we decrease xi j (r1 ) by an amount
δ1 < 0. Since xi j (r) remains unchanged for every r ∈ / {r1 , r2 }, and the sum ∑r∈Ri j φi j (r)gi j (r)xi j (r) is
preserved, we must have
φi j (r1 ) · gi j (r1 ) · δ1 = φi j (r2 ) · gi j (r2 ) · δ2 .
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 442
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
Since φi j (r) is a positive non-decreasing function of r, we have φi j (r1 ) ≤ φi j (r2 ). It follows that
gi j (r1 )δ1 ≥ gi j (r2 )δ2 . Hence, we get
gi j (r1 ) · (xi j (r1 ) − δ1 ) + gi j (r2 ) · (xi j (r2 ) + δ2 ) ≤ gi j (r1 ) · xi j (r1 ) + gi j (r2 ) · xi j (r2 ) .
Since the value of xi j (r) remains unchanged for all r ∈
/ {r1 , r2 }, the expression ∑r∈Ri j gi j (r)xi j (r) can
never increase.
Remark Due to the presence of budget constraints, (LPR EV ) bounds only the expected revenue of any
truthful-in-expectation BIC mechanism and not the expected social welfare, which can be larger by an
unbounded amount. However, if the budget constraints are removed, the resulting LP also bounds the
optimal social welfare.
3.2 Monotone hazard rates
We will present a constant-factor approximation to the optimal truthful-in-expectation BIC mechanism via
sequential posted-price schemes, assuming that the random variables vi j satisfy the monotone hazard-rate
condition (Definition 1.2). Formally, we will make the following assumption throughout Section 3.2.
Assumption 3.5. For all i ∈ I and j ∈ J, the random variable vi j (which denotes the valuation of bidder
i for item j) satisfies the monotone hazard rate (MHR) condition.
Claim 3.6. If X is a positive-integer-valued random variable satisfying the monotone hazard-rate
condition, then the random variable min(X, a) also satisfies the MHR condition, for any integer a ≥ 1.
Proof. Suppose that the random variable X is drawn from an MHR distribution with support {1, . . . , k}. If
a ≥ k, then clearly the random variable min(X, a) also satisfies the MHR condition, since it has a support
of {1, . . . , k} and we have
Pr[min(X, a) = r] = Pr[X = r] for all r ∈ {1, . . . , k} .
Hence, we will assume that a < k throughout the rest of the proof. In this case, the random variable
min(X, a) follows a distribution with support {1, . . . , a}, and we have
Pr[min(X, a) = r] = Pr[X = r] for all r ∈ {1, . . . , a − 1} , (3.1)
Pr[min(X, a) > r] = Pr[X > r] for all r ∈ {1, . . . , a − 1} , (3.2)
k
Pr[min(X, a) = a] = ∑ Pr[X = r] , (3.3)
r=a
Pr[min(X, a) > a] = 0 . (3.4)
From equations (3.1), (3.2), (3.3) and (3.4), it follows that
Pr[min(X, a) > r] Pr[min(X, a) > r0 ]
≥ for all r, r0 ∈ {1, . . . , a} such that r < r0 . (3.5)
Pr[min(X, a) = r] Pr[min(X, a) = r0 ]
Hence, the random variable min(X, a) satisfies the MHR condition.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 443
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
Since the random variables vi j satisfy the MHR condition (Assumption 3.5), we get the following
corollary.
Corollary 3.7. For all i ∈ I and j ∈ J, the random variable Vi j = min(vi j , Bi /4) satisfies the MHR
condition.
The next definition is due to Myerson [30]. First, recall that the random variable Vi j has a probability
mass function gi j (·) with support Ri j (Definition 3.2).
Definition 3.8. For all r ∈ Ri j , let Gi j (r) = Pr[Vi j > r]. Define the virtual valuation as
Gi j (r)
ϕi j (r) = r − for all i ∈ I, j ∈ J, r ∈ Ri j .
gi j (r)
The distribution gi j (·) is said to be regular if and only if we have
ϕi j (r) ≤ ϕi j (r0 ) for all r, r0 ∈ Ri j such that r < r0 .
Clearly, monotone hazard-rate distributions are regular. We now present a crucial lemma for monotone
hazard-rate distributions.
Lemma 3.9. If the random variable Vi j satisfies the MHR condition, then we have
Vi j
1
Pr ϕi j (Vi j ) > ≥ 2.
2 e
Proof. Recall that for all r ∈ Ri j , we have gi j (r) = Pr[Vi j = r] and Gi j (r) = Pr[Vi j > r]. Let the support
of the distribution gi j (·) be given by Ri j = {1, . . . , k}, where k is a positive integer. Before proceeding any
further, note that if k = 1, then Gi j (1) = 0, ϕi j (1) = 1, and the lemma holds since Pr[ϕi j (Vi j ) > Vi j /2] =
1 ≥ 1/e2 . Thus, throughout the rest of the proof, we assume that k ≥ 2.
Define
gi j (r)
hi j (r) = for all r ∈ {1, . . . , k} .
Gi j (r)
It is easy to see that ϕi j (r) = r − 1/hi j (r). Hence, we have ϕi j (r) ≥ r/2 if and only if hi j (r) ≥ 2/r. As
the random variable Vi j satisfies the MHR condition, we infer that hi j (r) is a non-decreasing function of r.
Finally, we note that 2/r is a non-increasing function of r, and that hi j (k) = ∞ > 2/k. These observations
lead us to conclude the following:
There is an integer k∗ ∈ {1, . . . , k} such that ϕi j (r) > r/2 if and only if r ≥ k∗ ,
and hi j (r) ≤ hi j (k∗ − 1) ≤ 2/(k∗ − 1) for all r ∈ {1, . . . , k∗ − 1}.
Therefore, we have
Pr[ϕi j (Vi j ) > Vi j /2] = Pr[Vi j ≥ k∗ ] .
If k∗ = 1, then Pr[Vi j ≥ k∗ ] = 1 > 1/e2 , and the lemma holds. Consequently, throughout the rest of the
proof, we assume that k∗ ≥ 2.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 444
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
We construct a continuous probability distribution with probability density function ĝi j (·) and support
[0, k] such that
Z r
gi j (r) = ĝi j (t) dt for all r ∈ {1, . . . , k} .
t=(r−1)
Next, for every real number 0 ≤ t ≤ k, we define
Z t
ĝi j (t)
Ĝi j (t) = 1 − ĝi j (t) dt and ĥi j (t) = .
q=0 Ĝi j (t)
Since dtd (Ĝi j (t)) = −ĝi j (t), it follows that
Z
ĥi j (t) dt = − log(Ĝi j (t)) .
Hence, we have
Z (k∗ −1) Ĝ (k∗ − 1)
ij
exp − ĥi j (t) dt = = Ĝi j (k∗ − 1) . (3.6)
t=0 Ĝi j (0)
Note that Ĝi j (t) is a non-increasing function of t. Thus, for all r ∈ {1, . . . , (k∗ − 1)}, we have
Z r Z r
1 gi j (r) 2
− ĥi j (t) dt ≥ − ĝi j (t) dt = − = −hi j (r) ≥ − ∗ .
t=(r−1) Ĝi j (r) t=(r−1) Gi j (r) (k − 1)
Summing over r = 1, . . . , (k∗ − 1), we get
Z (k∗ −1) (k∗ −1) Z r (k∗ −1)
2
− ĥi j (t) dt = − ∑ ĥi j (t) dt ≥ − ∑ ≥ −2 . (3.7)
t=0 r=1 t=(r−1) r=1 (k∗ − 1)
To conclude the proof of the lemma, we deduce that
Pr[ϕi j (Vi j ) > Vi j /2] = Pr[Vi j ≥ k∗ ]
(k∗ −1)
= 1− ∑ gi j (r)
r=1
Z (k∗ −1)
= 1− ĝi j (t) dt
t=0
∗
= Ĝi j (k − 1)
R (k∗ −1)
= e− t=0 ĥi j (t) dt
(by equation (3.6))
−2
≥e (by equation (3.7)).
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 445
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
Note that the bound established is Lemma 3.9 is tight for exponential distributions. Suppose that X is
a continuous random variable drawn from an exponential distribution with rate parameter µ, and let ϕ(X)
denote the virtual valuation function of X. We get
e−µX
X 2 1
Pr ϕ(X) > = Pr X − > X/2 = Pr X > = 2.
2 µ · e−µX µ e
Recall Definition 3.2 and Definition 3.8. The next observation follows from Corollary 3.7 and Lemma 3.9.
Observation 3.10. For all bidders i ∈ I and items j ∈ J, there exists an integer v∗i j ∈ Ri j such that
Pr[Vi j ≥ v∗i j ] ≥ e−2 and ϕi j (Vi j ) > Vi j /2 whenever Vi j ≥ v∗i j .
3.2.1 Incorporating virtual valuations
First, we state a characterization of virtual valuations that was proved by Myerson [30]. We will invoke
Lemma 3.11 multiple times throughout the rest of the paper.
Lemma 3.11. For all bidders i ∈ I and items j ∈ J, suppose that the random variable Vi j = min(vi j , Bi /4)
follows a discrete distribution gi j (·) with support Ri j , and 0 ≤ xi j (r) ≤ 1 for all r ∈ Ri j . We have
!
∑ gi j (r) · ϕi j (r) · xi j (r) = ∑ gi j (r) r · xi j (r) − ∑ xi j (s) .
r∈Ri j r∈Ri j s∈Ri j : s<r
Proof. Recall that ϕi j (r) = r − Gi j (r)/gi j (r), where Gi j (r) = ∑s∈Ri j : s>r gi j (s). Hence, we get
!
∑ gi j (r) · ϕi j (r) · xi j (r) = ∑ r · gi j (r) − ∑ gi j (s) · xi j (r)
r∈Ri j r∈Ri j s∈Ri j : s>r
= ∑ r · gi j (r) · xi j (r) − ∑ ∑ gi j (s) · xi j (r)
r∈Ri j r∈Ri j s∈Ri j : s>r
= ∑ r · gi j (r) · xi j (r) − ∑ ∑ gi j (r) · xi j (s)
r∈Ri j r∈Ri j s∈Ri j : s<r
!
= ∑ gi j (r) r · xi j (r) − ∑ xi j (s) .
r∈Ri j s∈Ri j : s<r
This concludes the proof.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 446
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
Now consider the following linear program obtained from (LPR EV).
Maximize ∑ ∑ ∑ gi j (r) · ϕi j (r) · xi j (r) (LP2)
i∈I j∈J r∈Ri j
∑ j∈J ∑r∈Ri j gi j (r) · xi j (r) ≤ ni ∀i ∈ I (1)
∑ j∈J ∑r∈Ri j gi j (r) · ϕi j (r) · xi j (r) ≤ Bi ∀i ∈ I (2)
∑i∈I ∑r∈Ri j gi j (r) · xi j (r) ≤ 1 ∀j ∈ J (3)
xi j (r) ∈ [0, 1] ∀i ∈ I, j ∈ J, r ∈ Ri j (4)
Lemma 3.12. The value of (LP2) is at least 1/(2e2 ) times the value of (LPR EV ).
Proof. Let {xi∗j (r)} denote the values taken by the xi j (r) variables in the optimal solution to (LPR EV ).
For all i ∈ I, j ∈ J, r ∈ Ri j , define:
(
0 if r < v∗i j ,
x̃i j (r) = ∗ (3.8)
xi j (r) if r ≥ v∗i j .
The optimal objective of (LPR EV ) is given by
∑ EV ∼g (·) [Vi j · xi∗j (Vi j )] .
ij ij
i, j
Lemma 3.3 implies that the function Vi j · xi∗j (Vi j ) is monotonically non-decreasing in Vi j . Hence, we get
EVi j [Vi j · xi∗j (Vi j )] ≤ EVi j [Vi j · xi∗j (Vi j ) | Vi j ≥ v∗i j ]
≤ EVi j [2 · ϕi j (Vi j ) · xi∗j (Vi j ) | Vi j ≥ v∗i j ] (Observation 3.10)
2 · EVi j [ϕi j (Vi j ) · x̃i j (Vi j )]
= (by equation (3.8))
Pr[Vi j ≥ v∗i j ]
≤ 2e2 · EVi j [ϕi j (Vi j ) · x̃i j (Vi j )] (Observation 3.10)
= 2e2 · ∑ gi j (r) · ϕi j (r) · x̃i j (r) .
r∈Ri j
Summing over all bidders i ∈ I and items j ∈ J, we infer:
∑ ∑ ∑ r · gi j (r) · xi∗j (r) ≤ 2e2 · ∑ ∑ ∑ gi j (r) · ϕi j (r) · x̃i j (r) . (3.9)
i∈I j∈J r∈Ri j i∈I j∈J r∈Ri j
Furthermore, we note the following inequalities.
0 ≤ x̃i j (r) ≤ xi∗j (r) for all i ∈ I, j ∈ J, r ∈ Ri j , (3.10)
ϕi j (r) · x̃i j (r) ≤ r · xi∗j (r) for all i ∈ I, j ∈ J, r ∈ Ri j . (3.11)
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 447
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
Equation (3.10) holds by definition, and equation (3.11) holds since ϕi j (r) ≤ r (Definition 3.8). Recall
that the xi∗j (r) values constitute an optimal solution to (LPR EV ). Hence, equations (3.9), (3.10), and (3.11)
imply that the x̃i j (r) values constitute a feasible solution to (LP2), having an objective that is within a
factor of 2e2 of the optimal objective of (LPR EV ). The lemma follows.
Lemma 3.13. Let xi∗j (r) denote the values assigned to the variables in the optimal solution to (LP2).
For all i ∈ I, j ∈ J, we can express the corresponding {xi∗j (r)}r∈Ri j values as a convex combination of two
solutions. The first (respectively, second) solution has variable values γi∗j (r) (respectively,λi∗j (r)), and an
integer ri∗j ∈ Ri j (respectively, s∗i j = ri∗j + 1 ∈ Ri j ) so that
( (
0 if r < r ∗ ,r ∈ R , 0 if r < s∗i j , r ∈ Ri j ,
ij
γi∗j (r) = ij
and λ ∗
ij (r) =
1 if r ≥ ri∗j , r ∈ Ri j , 1 if r ≥ s∗i j , r ∈ Ri j .
Suppose that in the convex combination, the first solution has weight 0 ≤ wi j ≤ 1 and the second solution
has weight 1 − wi j . In this case, we have xi∗j (r) = wi j · γi∗j (r) + (1 − wi j ) · λi∗j (r), and furthermore
∑ gi j (r) · ϕi j (r) · xi∗j (r) = wi j · ri∗j · Pr[Vi j ≥ ri∗j ] + (1 − wi j ) · s∗i j · Pr[Vi j ≥ s∗i j ] . (3.12)
r∈Ri j
Proof. Since the variable values {xi∗j (r)} constitute an optimal solution to (LP2), we have xi∗j (r) = 0
whenever ϕi j (r) ≤ 0. Furthermore, the virtual valuation ϕi j (r) is a non-decreasing function of r ∈ Ri j
(Corollary 3.7). We now apply Corollary 3.4 and infer the following: There exists an integer r∗ ∈ Ri j
such that
(
0 if r < r∗ , r ∈ Ri j ,
xi∗j (r) =
1 if r > r∗ , r ∈ Ri j .
This implies that the optimal solution to (LP2) can be written in the fashion implied by the lemma, with
ri∗j = r∗ and wi j = xi∗j (r∗ ). To prove equation (3.12), we first note that
∑ gi j (r)ϕi j (r)xi∗j (r) = wi j ∑ gi j (r)ϕi j (r)γi∗j (r) + (1 − wi j ) ∑ gi j (r)ϕi j (r)λi∗j (r) . (3.13)
r∈Ri j r∈Ri j r∈Ri j
Let the range of values of the random variable Vi j be given by Ri j = {1, . . . , k}. Recall that γi∗j (r) = 0 if
1 ≤ r < ri∗j and γi∗j (r) = 1 if ri∗j ≤ r ≤ k. Hence, we have
!
∑ gi j (r) · ϕi j (r) · γi∗j (r) = ∑ gi j (r) r · γi∗j (r) − ∑ γi∗j (s) (Lemma 3.11)
r∈Ri j r∈Ri j s∈Ri j : s<r
k
= ∑ gi j (r) r − (r − ri∗j )
r=ri∗j
= ri∗j · Pr[Vi j ≥ ri∗j ] .
Similarly, we can show that
∑ gi j (r) · ϕi j (r) · λi∗j (r) = s∗i j · Pr[Vi j ≥ s∗i j ] .
r∈Ri j
Now, the lemma follows from equation (3.13).
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 448
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
3.2.2 Posted-price mechanism and analysis
The posted-price mechanism is described in Figure 2. In Step 1, we select an arbitrary ordering of the
bidders. In Step 2, we find the optimal solution to (LP2). To explain Step 3 and Step 4, we first recall
Lemma 3.13, which has the following simple interpretation. For all bidders i ∈ I and items j ∈ J, the
optimal solution to (LP2) treats the pair (i, j) as a separate entity who is interested only in item j, and
who is willing to pay at most Vi j (Definition 3.2) for item j. Furthermore, the pair (i, j) is offered item j
at a posted price that is chosen randomly from the set {ri∗j , s∗i j }. Note that this is not a feasible mechanism:
Since each pair (i, j) is considered separately, an item may be allocated more than once, or a bidder
may exhaust her budget or demand. The LP solution, however, is extremely useful, as it allows us to
“uncouple" all the (i, j) pairs and find the prices {ri∗j , s∗i j } for each of them.
Motivated by the above interpretation, in Steps 3 and 4, we set r̃i j = ri∗j with probability wi j , and with
the remaining probability (1 − wi j ), we set r̃i j = s∗i j . Furthermore, we ensure that these random events
corresponding to all possible (bidder, item) pairs are mutually independent. Under the assumption that
every (i, j) pair behaves as a separate entity who is willing to pay at most Vi j for an item, let X̃i j be the
indicator random variable that is set to 1 if she is allocated the item, and let P̃i j denote her payment. Note
that P̃i j = r̃i j if X̃i j = 1, and P̃i j = 0 if X̃i j = 0. It follows that
E[X̃i j ] = wi j · Pr[Vi j ≥ ri∗j ] + (1 − wi j ) · Pr[Vi j ≥ s∗i j ]
= wi j · ∑ gi j (r) · γi∗j (r) + (1 − wi j ) · ∑ gi j (r) · λi∗j (r)
r∈Ri j r∈Ri j
= ∑ gi j (r) · xi∗j (r) .
r∈Ri j
We can also write:
E[P̃i j ] = wi j · ri∗j · Pr[Vi j ≥ ri∗j ] + (1 − wi j ) · s∗i j · Pr[Vi j ≥ s∗i j ] = ∑ gi j (r) · ϕi j (r) · xi∗j (r) .
r∈Ri j
The last equality follows from equation (3.12). Hence, the optimal objective value of (LP2) is given by
∑i, j E[P̃i j ]. Furthermore, Constraints 1, 2 and 3 of (LP2) imply that
∑ E[X̃i j ] ≤ ni , ∑ E[P̃i j ] ≤ Bi , and ∑ E[X̃i j ] ≤ 1 . (3.14)
j∈J j∈J i∈I
To summarize, if every pair (i, j) were behaving as a separate entity and we posted the (random) price r̃i j
for the pair (i, j), then the total expected revenue will be equal to the optimal objective of (LP2), and the
demand, budget, and supply constraints will hold in expectation.
There are two difficulties in implementing the above scheme: (1.) In reality, the pairs (i, j) do not
behave as separate entities. (2.) Since the budget, demand and supply constraints hold only in expectation,
there may be occasions where one or more of these constraints are violated.
Step 5 circumvents these difficulties. We visit the bidders according to the pre-determined ordering.
While visiting bidder i, if an item j is available (i. e., has not been purchased by any bidder i0 < i), then we
offer item j to bidder i with probability 1/4, at a (random) posted price r̃i j . Intuitively, this step ensures
that with constant probability, each pair (i, j) behaves as a separate agent (see the proof of Theorem 3.14),
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 449
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
Posted-Price Mechanism
1. Choose an arbitrary but fixed ordering of all bidders and denote it by 1, . . . , n.
2. Solve LP2, and let xi∗j denote the value assigned to variable xi j , for all i ∈ I, j ∈ J.
3. F OR each (i, j)
Independently pick one of the two solutions in the convex combination (see Lemma 3.13)
with probability equal to its weight in the combination.
4. Let r̃i j ∈ {ri∗j , s∗i j } denote the threshold in the chosen solution where the allocation function γ̃i j
jumps from zero to one.
5. Let {Yi j }i∈I, j∈J be a set of mn mutually independent 0/1 random variables such that
Pr[Yi j = 1] = 1/4 and Pr[Yi j = 0], for all i ∈ I, j ∈ J.
Q ← J (Initialize Q to be the set of all items).
F OR i = 1, 2, . . . , n
Initialize Wi ← 0;/
F OR each item j ∈ Q
Wi ← Wi ∪ { j} iff Yi j = 1;
Only the set of items Wi is offered to bidder i;
Each j ∈ Wi is offered at a price r̃i j ;
Bidder i buys a subset of items Si ⊆ Wi ;
Q ← Q \ Si .
Figure 2: DSIC Mechanism for independent valuations
so that the expected revenue remains within a constant factor of the optimal objective of (LP2). Applying
Lemma 3.3 and Lemma 3.12, we infer that the revenue of the sequential posted-price mechanism is a
O(1)-approximation to the revenue of the optimal Bayesian incentive-compatible mechanism.
Note that since an item is offered to a bidder only if it has not been purchased by anyone else, and
since the bidder herself decides the subset of items she wants to buy at the posted prices, this mechanism
is clearly feasible (i. e., satisfy the demand, budget and supply constraints), and universally truthful DSIC.
Theorem 3.14. The posted-price mechanism in Figure 2 is a universally truthful DSIC mechanism and
its revenue is a O(1)-approximation to the revenue of the optimal truthful-in-expectation BIC mechanism,
when the valuations of a bidder follow product distributions that satisfy the monotone hazard-rate
condition.
Proof. For all bidders i ∈ I and items j ∈ J, let Xi j be the 0/1 random variable denoting whether item j
is taken by bidder i, and let Pi j denote the price at which it is taken (which is 0 if the item is not taken by
the bidder). Recall equation (3.14), where X̃i j (respectively, P̃i j ) is the random variable for the allocation
(respectively, payment) corresponding to the pair (i, j), under the assumption that every (bidder, item)
pair behaves as a separate entity. Since the probability that any pair (i, j) is considered at all is 1/4 (see
Step 5, Figure 2), we infer that Xi j ≤ X̃i j /4 and Pi j ≤ P̃i j /4. By linearity of expectation, the inequalities
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 450
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
of equation (3.14) imply that
E ∑ Pik ≤ Bi /4 , E ∑ Xik ≤ di /4 , and E ∑ Xk j ≤ 1/4 for all i ∈ I, j ∈ J .
k6= j k6= j k6=i
Since the valuation vi j is independent of other valuations, this implies the above statements hold regardless
of vi j . Now applying Markov’s inequality, we have for all i, j:
Pr ∑ Pik ≥ 3Bi /4 ≤ 1/3 , Pr ∑ Xik ≥ di ≤ 1/4 , and Pr ∑ Xk j ≥ 1 ≤ 1/4 .
k6= j k6= j k6=i
By union bounds, this implies that with probability at least 1/6, we have
3Bi
∑ Pik < 4 , ∑ Xik < di , and ∑ Xk j = 0 .
k6= j k6= j k6=i
In this event, item j is offered to bidder i with probability 1/4 (using one of two random choices of the
posted price from Lemma 3.13). Furthermore, in this event, the bidder will take the item if vi j ≥ r̃i j , since
r̃i j ≤ Bi /4 (so that the bidder has sufficient budget to purchase this item), and the bidder has not exhausted
his demand di . Since the valuation vi j itself is independent of the event that the item j is offered to
bidder i, this implies that with probability at least 1/6 × 1/4, the posted-price mechanism obtains revenue
∑r gi j (r)ϕi j (r)xi∗j (r) along each (i, j) (using the definition of the latter quantity from equation (3.12)).
By linearity of expectation over all (i, j), we have a O(1)-approximation to the objective of (LP2). The
theorem follows from Lemma 3.3 and Lemma 3.12.
Corollary 3.15. Under the assumptions of Theorem 3.14, if there are no budget constraints, then the
revenue of the sequential posted-price mechanism is a constant-factor approximation to the optimal
social welfare.
Proof. If the Budget Constraint (2) is removed from (LPR EV ), it is an upper bound on the optimal social
welfare that can be obtained by any mechanism. The rest of the analysis remains the same.
One issue with mechanisms where bidders have budget and demand constraints is that given posted
prices for the items, the bidder needs to solve a two-dimensional K NAPSACK problem to determine
her optimal bundle, and this is NP-hard in general. However, this does not change our results, for the
following reasons. First, the analysis of the algorithm in Figure 2 simply shows that with constant
probability, the bidder solves a trivial K NAPSACK instance where all items fit into the K NAPSACK.
Another interesting aspect of our mechanism is that the LP relaxations (both (LPR EV ) and (LP2)) do not
encode any incentive-compatibility constraint. Furthermore, in a sequential posted-price mechanism, a
bidder i ∈ I does not have to report her valuations to the auctioneer. Depending on the publicly known
valuation distributions, the choices made by the bidders i0 < i, and the randomness of the mechanism,
bidder i is offered a subset Wi of available items, and she has to pay a posted price r̃i j for buying any
item j ∈ Wi . The subset of items Wi and the posted prices {r̃i j } do not depend on the valuations of bidder
i. Hence, the scheme remains incentive compatible regardless of the K NAPSACK heuristic used by the
bidder. Therefore, our results hold as long as the bidder uses any reasonable K NAPSACK heuristic that is
maximal, in the sense that the bidder goes on buying more and more items until she exhausts her demand
or budget constraints.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 451
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
3.3 General distributions
The key point shown by Theorem 3.14 is that the revenue of the optimal truthful-in-expectation BIC
mechanism is approximated to a constant factor by a simple sequential posted-price mechanism, where the
prices are posted for each item and each bidder. This crucially used the monotone hazard-rate condition.
The natural question to ask is whether such a simple mechanism is a good approximation for more general
classes of distributions. Note that even for one bidder, the optimal universally truthful DSIC mechanism
may not be a sequential posted-price scheme. We show below that the optimal universally truthful DSIC
mechanism has a logarithmic advantage over sequential posted pricing even for regular distributions (see
Definition 3.8), and that this gap is tight.
Theorem 3.16. Suppose that vi j ∈ [1, L], are independent for different (i, j) but do not necessarily satisfy
the monotone hazard-rate condition. Then, there is a Θ(log L) gap between the revenues of the optimal
sequential posted-price scheme and the optimal universally truthful DSIC mechanism. The lower bound
holds for regular distributions and one bidder.
Proof. To show the lower bound, consider the following scenario: There is only one bidder, m items,
and no budget or demand constraints. The valuations are i. i. d. for each item j, and follow the common
distribution with Pr[v ≥ r] = 1/r, for r = 1, 2, . . . , m, so that m = L. This distribution is regular, since
ϕ(r) = 0 for r < m, and ϕ(m) = m. We have E[v1 j ] = ∑m r=1 (1/r) = Hm for every item j, and by Chernoff
bounds, " #
m −mHm ε 2
Pr ∑ v1 j ≤ (1 − ε)mHm ≤ e 2m = o(1) .
j=1
Therefore, a scheme that sets a price of mHm (1 − ε) for the bundle of m items sells the bundle with
probability 1 − o(1), so that the expected revenue is Ω(m log m). Any sequential posted-price scheme
can extract a revenue of maxr r · Pr[v ≥ r] = 1 from each item, so that the total expected revenue from m
items is at most m × 1 = m. This shows a gap of Ω(log m) = Ω(log L).
The upper bound follows from a standard scaling argument. We start with (LPR EV ) which upper
bounds the optimal achievable revenue. For each (i, j), we group the r values in powers of 2 so that there
are (log L) groups. Let group Gk denote the interval [2k , 2k+1 ). We find a group Gki∗j that contributes at
least (1/ log L) fraction to the sum ∑r r gi j (r)xi j (r). Specifically, we require that
∑ r · gi j (r) · xi j (r) ≥ (1/ log L) ∑ r · gi j (r) · xi j (r) .
r∈Gk∗ r∈Ri j
ij
∗
Note that if we use the price 2ki j for the pair (i, j), and every (bidder, item) pair behaves as a separate
entity, then our expected revenue will be at least (1/2 log L) times the optimal objective value of (LPR EV ).
Suppose that we modify the Steps 2, 3, and 4 of the algorithm in Figure 2: Instead of solving (LP2) and
∗
randomly selecting r̃i j ∈ {ri∗j , s∗i j }, we solve (LPR EV ) and deterministically set r̃i j = 2ki j . Step 5 of the
algorithm is left unchanged. Using similar arguments as in the proof of Theorem 3.14, it is now easy to
see that the resulting sequential posted-price mechanism will give a Ω(1/ log L)-approximation to the
optimal revenue.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 452
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
3.3.1 Adaptive posted-price schemes
The above implies that we cannot generalize the result in Section 3.2 even to the class of regular
distributions (see Definition 1.1). This is because an ω(1) gap is introduced in going from (LPR EV )
to (LP2). However, we can show that if the space of mechanisms is restricted, (LP2) itself is a good
relaxation to the optimal revenue in this space.
In particular, suppose that we restrict the space of mechanisms to be those that are posted price,
and sequential by bidder: Depending on the subset of items and bidders left, the mechanism adaptively
chooses the next bidder and posts prices for a subset of the remaining items. The bidder, being a utility
maximizer, solves a knapsack problem to choose the optimal subset of items. Once this bidder is dealt
with, the mechanism again adaptively chooses the next bidder depending on the acceptance strategy of
this bidder. Since the optimization problem the bidders need to solve is a two-dimensional K NAPSACK
problem, which is NP-hard, we assume that the bidders are monotone optimizers in the following sense.
Assumption 3.17. Suppose that we are given some adaptive posted-price scheme. Consider any pair (i, j),
where i ∈ I, j ∈ J. Fix the valuations vi0 j0 corresponding to all other (bidder, item) pairs (i0 , j0 ) 6= (i, j).
Also fix the K NAPSACK heuristics used by all the other bidders i0 6= i. It follows that we can uniquely
determine the subset of items that will be offered to bidder i, and the prices at which those items will be
offered to bidder i. Under these circumstances, we assume that the quantity of item j taken by bidder i is
a monotonically non-decreasing function of vi j .
The above assumption holds if the bidder solves K NAPSACK optimally. Similar to the posted-price
scheme in Section 3.2.2, our algorithm itself will allow arbitrary K NAPSACK heuristics, as long as it
satisfies Assumption 3.17 and the bidder buys all the items if she is not constrained by either demand or
budget. Next, we state another assumption that will be used throughout the rest of Section 3.3.1.
Assumption 3.18. The valuations of different bidders for different items follow independent distributions,
that is, the random variables {vi j }i∈I, j∈J are mutually independent. Furthermore, the distribution fi j (·),
from which the random variable vi j is drawn, is regular for all i ∈ I, j ∈ J.
Under Assumptions 3.17 and 3.18, we will show a O(1)-approximation to the revenue maximizing
adaptive posted-price mechanism. First, we consider the following nonlinear program.
Maximize ∑ ∑ ∑ gi j (r) · 4 · p̃i j (r) · xi j (r) (S EQ)
i∈I j∈J r∈Ri j
∑ j∈J ∑r∈Ri j gi j (r) · xi j (r) ≤ di ∀i ∈ I (1)
∑ j∈J ∑r∈Ri j gi j (r) · p̃i j (r) · xi j (r) ≤ Bi ∀i ∈ I (2)
∑i∈I ∑r∈Ri j gi j (r) · xi j (r) ≤ 1 ∀j ∈ J (3)
p̃i j (r) · xi j (r) ≤ r · xi j (r) − ∑r−1
s=1 xi j (s) ∀i ∈ I, j ∈ J, r ∈ Ri j (4)
xi j (r) ∈ [0, 1] ∀i ∈ I, j ∈ J, r ∈ Ri j (5)
p̃i j (r) ∈ [0, r] ∀i ∈ I, j ∈ J, r ∈ Ri j (6)
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 453
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
Lemma 3.19. If the bidders are monotone optimizers, then the objective of the nonlinear program (S EQ)
upper bounds the revenue of the optimal adaptive posted-price mechanism.
Proof. Fix any adaptive posted-price mechanism, and let xi j (r) denote the probability that bidder i ∈ I
obtains item j ∈ J when Vi j = r ∈ Ri j (Definition 3.2). Similarly, let pi j (r) denote the expected price
paid by bidder i for item j, conditioned on the events that Vi j = r and bidder i obtains item j. Define
p̃i j (r) = pi j (r)/4. It follows that the auctioneer’s revenue is equal to the objective of (S EQ). Constraint 1
of (S EQ) holds since no bidder i buys more than di items, constraint 2 holds since no bidder pays more
than her budget, and constraint 3 holds since no item is allocated more than once.
To interpret constraint 4, fix a bidder i ∈ J, an item j ∈ J, and also fix all the valuations vi0 j0
corresponding to all other (bidder, item) pairs (i0 , j0 ) 6= (i, j), and the K NAPSACK heuristics used by
every bidder i0 6= i. This uniquely determines the subset of items (and their prices) that will be offered to
bidder i. If the adaptive posted-price mechanism offers item j to bidder i, then it posts a unique price p∗
for the item. Given these conditions, let Xi j (r) ∈ [0, 1] denote the probability that bidder i takes item j
when Vi j = r ∈ Ri j , and let Pi j (r) = p∗ · Xi j (r) denote the expected price paid by bidder i for item j when
Vi j = r ∈ Ri j . We will show:
∗ r−1
Pi j (r) p
= · Xi j (r) ≤ r · Xi j (r) − ∑ Xi j (s) for all r ∈ Ri j . (3.15)
4 4 s=1
To verify equation (3.15), we consider two possible cases.
Case 1: p∗ /4 > Bi /4.
In this case, bidder i never takes item j since the price exceeds her budget, implying that Xi j (r) = Pi j (r) = 0
for all r ∈ Ri j . Hence, equation (3.15) holds.
Case 2: p∗ /4 ≤ Bi /4.
To analyze this case, first recall that we have already fixed both the valuations of bidder i for every
item j0 6= j, and the subset of items (and their prices) offered to bidder i. Next, note that if Vi j =
min(vi j , Bi /4) < Bi /4, then vi j is also uniquely determined. Hence, we see that Xi j (r) is either 0 or 1 for
all r < Bi /4. However, at r = Bi /4, the valuation vi j is not unique and Xi j (r) can take a fractional value.
Since the bidder is a monotone utility maximizer (Assumption 3.17), we infer that Xi j (r) is a monotone
step function of r, and this step function has at most one jump. If the step function has no jump at all,
then Xi j (r) = 0 for all r ∈ Ri j , and equation (3.15) holds. Consequently, we assume that the step function
jumps at r∗ ≤ Bi /4, that is, Xi j (r) = 0 for all r < r∗ , and Xi j (r) = Xi j (r∗ ) > 0 for all r ≥ r∗ . It is easy to
see that equation (3.15) holds for all r < r∗ .
Recall that p∗ /4 ≤ Bi /4. As a consequence, if Vi j = min(vi j , Bi /4) < p∗ /4, then vi j < p∗ /4 < p∗ .
Since bidder i never takes item j when vi j < p∗ , and since Xi j (r∗ ) > 0, it follows that p∗ /4 ≤ r∗ . To
summarize, it remains to verify equation (3.15) only if p∗ /4 ≤ r∗ ≤ r ≤ Bi /4. In this situation, we get
∗ ∗
p p
· Xi j (r) = · Xi j (r∗ ) ≤ r∗ · Xi j (r∗ ) . (3.16)
4 4
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 454
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
Furthermore, we have
r−1
r · Xi j (r) − ∑ Xi j (s) = r · Xi j (r∗ ) − (r − r∗ )Xi j (r∗ ) = r∗ · Xi j (r∗ ) . (3.17)
s=1
Equation (3.15) follows from equations (3.16) and (3.17). Having verified equation (3.15), we proceed
with the proof of the lemma.
Taking expectation over all the remaining valuations {vi0 j0 }, where (i0 , j0 ) 6= (i, j), and recalling
the definitions of xi j (r), pi j (r), we see that xi j (r) = E[Xi j (r)] and pi j (r)xi j (r) = E[Pi j (r)]. Hence, equa-
tion (3.15) implies:
r−1
pi j (r) Pi j (r)
p̃i j (r) · xi j (r) = · xi j (r) = E ≤ r · xi j (r) − ∑ xi j (s) . (3.18)
4 4 s=1
Thus, constraint 4 of (S EQ) holds, and the revenue maximizing adaptive posted-price mechanism is a
feasible solution to the nonlinear program (S EQ).
Lemma 3.20. If the bidders are monotone optimizers, then (LP2) is a 4-approximation to the revenue of
the optimal adaptive posted-price scheme.
Proof. First, we take the optimal solution to the non-linear program (S EQ). Next, for all i ∈ I, j ∈ J, let
the range of Vi j be given by Ri j = {1, . . . , |Ri j |}. We do the following:
F OR all i ∈ I, j ∈ J
F OR r = 1, 2, . . . , |Ri j |
Increase the value of p̃i j (r) and decrease the value of xi j (r), ensuring that their prod-
uct p̃i j (r) · xi j (r) remains the same, and continue doing this until the corresponding
constraint 4 (defined by the tripe (i, j, r)) of the non-linear program (S EQ) becomes tight.
This preserves the objective of (S EQ) and all the other constraints. When this process terminates, we get
an optimal solution to (S EQ) where the constraint 4 is tight for all i ∈ I, j ∈ J, r ∈ Ri j . Hence, we can
replace p̃i j (r) · xi j (r) by the right hand side of constraint 4, and rewrite the non-linear program (S EQ) as a
linear program (LP3).
!
r−1
Maximize ∑ ∑ ∑ gi j (r) · 4 · r · xi j (r) − ∑ xi j (s) (LP3)
i∈I j∈J r∈Ri j s=1
∑ j∈J ∑r∈Ri j gi j (r) · xi j (r) ≤ di ∀i ∈ I
∑ j∈J ∑r∈Ri j gi j (r) · rxi j (r) − ∑r−1 ∀i ∈ I
s=1 xi j (s) ≤ Bi
∑i∈I ∑r∈Ri j gi j (r) · xi j (r) ≤ 1 ∀j ∈ J
xi j (r) ∈ [0, 1] ∀i ∈ I, j ∈ J, r ∈ Ri j
Now, we invoke Lemma 3.11 and deduce that (LP3) is equivalent to the following linear program.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 455
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
Maximize ∑ ∑ ∑ 4 · gi j (r) · ϕi j (r) · xi j (r) (LP4)
i∈I j∈J r∈Ri j
∑ j∈J ∑r∈Ri j gi j (r) · xi j (r) ≤ di ∀i ∈ I
∑ j∈J ∑r∈Ri j gi j (r) · ϕi j (r) · xi j (r) ≤ Bi ∀i ∈ I
∑i∈I ∑r∈Ri j gi j (r) · xi j (r) ≤ 1 ∀j ∈ J
xi j (r) ∈ [0, 1] ∀i ∈ I, j ∈ J, r ∈ Ri j
Hence, the objective of (LP4) upper bounds the revenue of the optimal adaptive posted-price scheme
when the bidders are monotone optimizers. The lemma follows from comparing (LP4) with (LP2).
The final mechanism and analysis are the same as in Section 3.2: Solve (LP2), and making use of
Assumption 3.18, decompose the LP solution into a convex combination of posted prices per edge, and
sequentially post these prices for every bidder. To complete the analysis, note that Lemma 3.13 only
requires that the distribution gi j (·) be regular. This shows the following theorem:
Theorem 3.21. There is a polynomial time O(1)-approximation to the revenue of the optimal adaptive
posted-price scheme, when the bidders are monotone optimizers, and the valuations of different bidders
for different items are drawn from mutually independent regular distributions.
Acknowledgments: We thank Shuchi Chawla, Vincent Conitzer, and Peng Shi for helpful discussions,
and the anonymous reviewers for detailed reviews.
References
[1] Z OË A BRAMS: Revenue maximization when bidders have budgets. In Proc. 17th Ann.
ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 1074–1082. ACM Press, 2006.
[doi:10.1145/1109557.1109676] 434
[2] A ARON A RCHER , C HRISTOS PAPADIMITRIOU , K UNAL TALWAR , AND É VA TARDOS:
An approximate truthful mechanism for combinatorial auctions with single parameter
agents. Internet Mathematics, 1(2):129–150, 2004. Preliminary version in SODA’03.
[doi:10.1080/15427951.2004.10129086] 437
[3] L AWRENCE M. AUSUBEL: An efficient ascending-bid auction for multiple objects. American
Economic Review, 94(5):1452 – 1475, 2004. [doi:10.1257/0002828043052330] 434
[4] L AWRENCE M. AUSUBEL AND PAUL R. M ILGROM: Ascending auctions with package bidding.
Frontiers of Theoretical Economics, 1(1):1, 2002. de Gruyter. 435
[5] J EAN -P IERRE B ENOÎT AND V IJAY K RISHNA: Multiple-object auctions with budget constrained
bidders. Review of Economic Studies, 68(1):155 – 179, 2001. [doi:10.1111/1467-937X.00164] 434,
435
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 456
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
[6] S AYAN B HATTACHARYA , V INCENT C ONITZER , K AMESH M UNAGALA , AND L IRONG X IA:
Incentive compatible budget elicitation in multi-unit auctions. In Proc. 21st Ann. ACM-SIAM Symp.
on Discrete Algorithms (SODA’10), pp. 554–572. ACM Press, 2010. [ACM:1873648] 434, 435,
436
[7] K IM C. B ORDER: Reduced form auctions revisited. Economic Theory, 31(1):167–181, 2007.
[doi:10.1007/s00199-006-0080-z] 434
[8] C HRISTIAN B ORGS , J ENNIFER C HAYES , N ICOLE I MMORLICA , M OHAMMAD M AHDIAN , AND
A MIN S ABERI: Multi-unit auctions with budget-constrained bidders. In Proc. 6th ACM Conf.
Electronic Commerce (ACM-EC’05), pp. 44–51. ACM Press, 2005. [doi:10.1145/1064009.1064014]
434
[9] PATRICK B RIEST: Uniform budgets and the envy-free pricing problem. In Proc. 35th Internat.
Colloq. on Automata, Languages and Programming (ICALP’08), pp. 808–819. Springer, 2008.
[doi:10.1007/978-3-540-70575-8_66] 433, 440
[10] PATRICK B RIEST, S HUCHI C HAWLA , ROBERT K LEINBERG , AND S. M ATTHEW W EINBERG:
Pricing randomized allocations. In Proc. 21st Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA’10), pp. 585–597. ACM Press, 2010. [ACM:1873601.1873650] 433
[11] S ANDRO B RUSCO AND G IUSEPPE L OPOMO: Budget constraints and demand reduction in si-
multaneous ascending-bid auctions. Journal of Industrial Economics, 56(1):113–142, 2008.
[doi:10.1111/j.1467-6451.2008.00335.x] 430, 434, 435
[12] S HUCHI C HAWLA , JASON D. H ARTLINE , AND ROBERT K LEINBERG: Algorithmic pricing via
virtual valuations. In Proc. 8th ACM Conf. Electronic Commerce (ACM-EC’07), pp. 243–251. ACM
Press, 2007. [doi:10.1145/1250910.1250946] 433, 435
[13] S HUCHI C HAWLA , JASON D. H ARTLINE , DAVID L. M ALEC , AND BALASUBRAMANIAN S IVAN:
Multi-parameter mechanism design and sequential posted pricing. In Proc. 42nd STOC, pp. 311–320.
ACM Press, 2010. [doi:10.1145/1806689.1806733] 433
[14] Y EON -KOO C HE AND I AN G ALE: Expected revenue of all-pay auctions and first-price sealed-bid
auctions with budget constraints. Economics Letters, 50:373–379, 1996. [doi:10.1016/0165-
1765(95)00766-0] 434
[15] Y EON -KOO C HE AND I AN G ALE: The optimal mechanism for selling to a budget-constrained
buyer. J. Economic Theory, 92(2):198–233, 2000. [doi:10.1006/jeth.1999.2639] 434
[16] N ING C HEN , N ICOLE I MMORLICA , A NNA R. K ARLIN , M OHAMMAD M AHDIAN , AND ATRI
RUDRA: Approximating matches made in heaven. In Proc. 36th Internat. Colloq. on Automata,
Languages and Programming (ICALP’09), pp. 266–278. Springer, 2009. [doi:10.1007/978-3-642-
02927-1_23] 435
[17] E DWARD H. C LARKE: Multipart pricing of public goods. Public Choice, 11(1):17–33, 1971.
[doi:10.1007/BF01726210] 430
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 457
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
[18] S HAHAR D OBZINSKI , RON L AVI , AND N OAM N ISAN: Multi-unit auctions with budget lim-
its. Games and Economic Behavior, 74(2):486–503, 2012. Preliminary version in FOCS’08.
[doi:10.1016/j.geb.2011.08.003] 434
[19] B ENJAMIN E DELMAN , M ICHAEL O STROVSKY, AND M ICHAEL S CHWARZ: Internet advertising
and the generalized second price auction: Selling billions of dollars worth of keywords. American
Economic Review, 97(1):242–259, 2007. [doi:10.1257/aer.97.1.242] 435
[20] E DITH E LKIND AND S HAHEEN FATIMA: Maximizing revenue in sequential auctions. In Proc. 3rd
Internat. Workshop on Internet and Network Economics (WINE’07), pp. 491–502. Springer, 2007.
[doi:10.1007/978-3-540-77105-0_53] 435
[21] A NDREW V. G OLDBERG , JASON D. H ARTLINE , A NNA R. K ARLIN , M ICHAEL S AKS , AND
A NDREW W RIGHT: Competitive auctions. Games and Economic Behavior, 55(2):242–269, 2006.
[doi:10.1016/j.geb.2006.02.003] 434
[22] A NDREW V. G OLDBERG , JASON D. H ARTLINE , AND A NDREW W RIGHT: Competitive auctions
and digital goods. In Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’01), pp.
735–744. ACM Press, 2001. [ACM:365411.365768] 434
[23] T HEODORE G ROVES: Incentives in teams. Econometrica, 41(4):617–631, 1973. JSTOR. 430
[24] V ENKATESAN G URUSWAMI , JASON D. H ARTLINE , A NNA R. K ARLIN , DAVID K EMPE , C LAIRE
K ENYON , AND F RANK M C S HERRY: On profit-maximizing envy-free pricing. In Proc. 16th
Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’05), pp. 1164–1173. ACM Press, 2005.
[ACM:1070432.1070598] 432, 433
[25] I SA E MIN H AFALIR , R. R AVI , AND A MIN S AYEDI: Sort-cut: A pareto optimal and semi-
truthful mechanism for multi-unit auctions with budget-constrained bidders. Technical report,
2009. [arXiv:0903.1450v1] 434
[26] JASON D. H ARTLINE AND T IM ROUGHGARDEN: Simple versus optimal mechanisms. In
Proc. 10th ACM Conf. on Electronic Commerce (ACM-EC’09), pp. 225–234. ACM Press, 2009.
[doi:10.1145/1566374.1566407] 435
[27] J EAN -JACQUES L AFFONT AND JACQUES ROBERT: Optimal auction with financially constrained
buyers. Economics Letters, 52(2):181–186, 1996. [doi:10.1016/S0165-1765(96)00849-X] 434
[28] RON L AVI AND C HAITANYA S WAMY: Truthful and near-optimal mechanism design via
linear programming. J. ACM, 58(6/25):1–24, 2011. Preliminary version in FOCS’05.
[doi:10.1145/2049697.2049699] 437
[29] A LEJANDRO M. M ANELLIA AND DANIEL R. V INCENT: Multidimensional mechanism design:
Revenue maximization and the multiple-good monopoly. J. Economic Theory, 137(1):153–185,
2007. [doi:10.1016/j.jet.2006.12.007] 434
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 458
B UDGET-C ONSTRAINED AUCTIONS WITH H ETEROGENEOUS I TEMS
[30] ROGER B. M YERSON: Optimal auction design. Math. Oper. Res., 6(1):58–73, 1981.
[doi:10.1287/moor.6.1.58] 431, 433, 434, 444, 446
[31] N OAM N ISAN , JASON BAYER , D EEPAK C HANDRA , TAL F RANJI , ROBERT G ARDNER , YOSSI
M ATIAS , N EIL R HODES , M ISHA S ELTZER , DANNY T OM , H AL VARIAN , AND DAN Z IGMOND:
Google’s auction for TV ads. In Proc. 36th Internat. Colloq. on Automata, Languages and Program-
ming (ICALP’09), pp. 309–327. Springer, 2009. See also ESA’09 and SODA’10. [doi:10.1007/978-
3-642-02930-1_26] 430, 434
[32] M ALLESH M. PAI AND R AKESH VOHRA: Optimal auctions with financially constrained bidders.
Working Paper, 2008. CiteSeerX. 434
[33] J OHN T HANASSOULIS: Haggling over substitutes. J. Economic Theory, 117(2):217–245, 2004.
[doi:10.1016/j.jet.2003.09.002] 434
[34] W ILLIAM V ICKREY: Counterspeculation, auctions and competitive sealed tenders. J. Finance,
16(1):8–37, 1961. [doi:10.1111/j.1540-6261.1961.tb02789.x] 430
[35] ROBERT B. W ILSON: Nonlinear Pricing. Oxford University Press, 1997. 434
AUTHORS
Sayan Bhattacharya
Graduate Student
Department of Computer Science
Duke University, Durham, NC 27708
bsayan cs duke edu
http://www.cs.duke.edu/~bsayan
Gagan Goel
Research Scientist
Google Inc.
New York, NY
gagangoel google com
http://research.google.com/pubs/GaganGoel.html
Sreenivas Gollapudi
Senior Researcher
Microsoft Search Labs
Mountain View, CA 94043
sreenig microsoft com
http://research.microsoft.com/en-us/people/sreenig/
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 459
S AYAN B HATTACHARYA , G AGAN G OEL , S REENIVAS G OLLAPUDI , AND K AMESH M UNAGALA
Kamesh Munagala
Associate Professor
Department of Computer Science
Duke University, Durham, NC 27708
kamesh cs duke edu
http://www.cs.duke.edu/~kamesh
ABOUT THE AUTHORS
S AYAN B HATTACHARYA is a Ph. D. student in the Department of Computer Science at Duke
University. His adviser is Kamesh Munagala. He obtained his B. E. in Computer Science
and Engineering from Jadavpur University, Kolkata in July 2008. He is interested in
Approximation Algorithms and Computational Microeconomics.
G AGAN G OEL is a research scientist at Google. His research interests lie in the design and
analysis of algorithms and its applications to optimization, market design, and game
theory. He received his Ph. D. in Algorithms, Combinatorics, and Optimization from
Georgia Tech in August 2009 under the supervision of Vijay Vazirani. Before that he
received his B. Tech. in Computer Science and Engineering from the Indian Institute of
Technology, Delhi in August 2004.
S REENIVAS G OLLAPUDI is a Senior Researcher at Microsoft Search Labs which he joined in
July 2006. Prior to moving to Search Labs, he held senior engineering roles at Ebrary in
their Advanced Technologies Group and in the distributed database group at Oracle. He
obtained his B. Tech. from IIT Bombay, and his Ph. D., in 2004, from the State University
of New York at Buffalo where his advisor was Aidong Zhang. He is a holder of twenty-
nine US patents. His current research interests include web algorithms, algorithms for
large data sets, and game theoretic approaches to social network analysis.
K AMESH M UNAGALA is Associate Professor of Computer Science Science at Duke Univer-
sity, where he has been employed since 2004. He received his M. S. degree in 2002 and
his Ph. D. in 2003, both from Stanford University. His advisor was Serge Plotkin. He
received his B. Tech. degree in 1998 from the Indian Institute of Technology, Bombay
where his advisor was Abhiram Ranade. He spent a year as a post-doctoral scholar
in Pat Brown’s Lab doing computational biology at the Department of Biochemistry,
Stanford University School of Medicine. His research interests are in approximation
algorithms, combinatorial optimization, computational economics, scheduling theory,
social networks, and data mining. He received an NSF CAREER award in 2008 and an
Alfred P. Sloan research fellowship in 2009.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 429–460 460