Approximation Algorithms and Online Mechanisms for Item Pricing

Authors Maria-Florina Balcan, Avrim Blum,

Plaintext

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195
http://theoryofcomputing.org

Approximation Algorithms and Online
Mechanisms for Item Pricing∗
Maria-Florina Balcan† Avrim Blum†
Received: March 29, 2007; published: October 3, 2007.

Abstract: We present approximation and online algorithms for problems of pricing a
collection of items for sale so as to maximize the seller’s revenue in an unlimited supply
setting. Our first result is an O(k)-approximation algorithm for pricing items to single-
minded bidders who each want at most k items. This improves over work of Briest and
Krysta (2006) who achieve an O(k2 ) bound. For the case k = 2, where we obtain a 4-
approximation, this can be viewed as the following graph vertex pricing problem: given
a (multi) graph G with valuations wi j on the edges, find prices pi ≥ 0 for the vertices to
maximize
∑ (pi + p j ) .
{(i, j):wi j ≥pi +p j }

We also improve the approximation of Guruswami et al. (2005) for the “highway problem”
in which all desired subsets are intervals on a line, from O(log m + log n) to O(log n), where
m is the number of bidders and n is the number of items. Our approximation algorithms can
be fed into the generic reduction of Balcan et al. (2005) to yield an incentive-compatible
∗ A preliminary version of this paper appeared in Proc. 7th ACM Conf. on Electronic Commerce (EC’06), pp.29-35, 2006.
† Supported in part by NSF grants CCF-0514922, CCR-0122581, and IIS-0121678.

ACM Classification: F.2, J.4
AMS Classification: 68W25, 68W20, 68Q32, 91B26
Key words and phrases: Combinatorial Auctions, Pricing Problems, Revenue Maximization, Approx-
imation Algorithms, Online Optimization

Authors retain copyright to their work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work is permitted as
long as the author(s) and the journal are properly acknowledged. For the detailed
copyright statement, see http://theoryofcomputing.org/copyright.html.

c 2007 Maria-Florina Balcan and Avrim Blum DOI: 10.4086/toc.2007.v003a009
M.-F. BALCAN AND A. B LUM

auction with nearly the same performance guarantees so long as the number of bidders is
sufficiently large. In addition, we show how our algorithms can be combined with results
of Blum and Hartline (2005) and Kalai and Vempala (2003) to achieve good performance
in the online setting, where customers arrive one at a time and each must be presented a set
of item prices based only on knowledge of the customers seen so far.

1 Introduction
Consider the problem of a retailer trying to price its products to make the most profit. If customers had
valuations over individual items only, then the problem of setting prices would be relatively easy: for
each product i, the optimal price for that product is such that the profit margin pi per item sold, times
the number of customers who would buy at that price, is maximized. So, each item can be considered
separately, and assuming the company knows its market well, the computational problem of setting
prices is fairly trivial.
However, suppose that customers have valuations over pairs of items (e.g., a computer and a monitor,
or a tank of gas and a cup of coffee), and will only purchase if the combined price of the items in their
pair is below their value. In this case, we can model the problem as a (multi) graph, where each edge e
has some valuation we , and our goal is to set prices pi ≥ 0 on the vertices of the graph to maximize total
profit: that is,1
Profit(p) = ∑ price(e) ,
e:we ≥price(e)

where price(e) = ∑i∈e pi , and p is the vector of individual prices.
We call this the graph vertex pricing problem. More generally, if customers have valuations over
larger subsets, we can model our computational problem as one of pricing vertices in a hypergraph,
or in more standard terminology, the problem of pricing items in an unlimited-supply combinatorial
auction with single-minded bidders. Guruswami et al. [15] show an O(log m + log n)-approximation
for the general problem, where n is the number of items (vertices) and m is the number of customers
(hyperedges). They also show that even the graph vertex pricing problem is APX-hard — and this is true
even when all valuations are identical (if customers wanting just one item are allowed) or all valuations
are either 1 or 2 (if such customers are not allowed). In related work, Hartline and Koltun [16] give
a (1 + ε)-approximation that runs in time exponential in the number of vertices, but that is near-linear
time when the total number of vertices in the hypergraph is constant. Recently, Demaine et al. [10] have
shown that it is hard to approximate the hypergraph vertex pricing problem within a factor of logδ n, for
n ε
some δ > 0, assuming that NP 6⊆ BPTIME 2 for some ε > 0.
In this paper, we give a 4-approximation for the graph vertex pricing problem, and more generally
we present an O(k)-approximation for the case of hypergraphs in which each edge has size at most k
1 This formula corresponds to a model in which items have zero marginal cost to the retailer (digital goods) so that an item

sold at price pi generates profit pi . Alternatively, if products have a fixed marginal cost, and we cannot sell them below cost
(say, due to the presence of resellers), then we can think of pi as the profit margin on item i and simply subtract our costs for
the endpoints from each valuation we .

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 180
A PPROXIMATION A LGORITHMS AND O NLINE M ECHANISMS FOR I TEM P RICING

(i. e., all customers’ valuations are over subsets of size at most k). The latter result improves over the
work of Briest and Krysta [7] who give a bound of O(k2 ).
We also consider the highway problem studied in [15]. This problem is the special case of the
hypergraph pricing problem where vertices are numbered 1, . . . , n and each customer wants an interval
[i, j].2 For this problem, we give an O(log n)-approximation, improving slightly over the O(log m+log n)
approximation of [15], and also give an O(1)-approximation for the case that all users want the same
number of items up to a constant factor. In addition, we give a fully polynomial time approximation
scheme (FPTAS) for the case that the desired subsets of different customers form a hierarchy (this is
defined more precisely in Section 7).
Finally, we consider the question of what happens if we are allowed to price some items below their
cost, and give an example in the context of graph vertex pricing in which such pricing can produce an
Ω(log n) factor more profit than possible if all items must be priced above cost. However, we do not
have any good (o(log n)) approximation algorithms for that setting.

Incentive-compatibility Our results described above assume the seller “understands the market”: how
many customers will buy different sets of items and at what prices. Thus, we are simply left with a
computational problem. If we do not understand the market and are in the setting of an unlimited-
supply combinatorial auction, we would instead want an algorithm that is incentive-compatible, meaning
that it is in the bidders’ self-interest to reveal their true valuations. Fortunately, a generic reduction of
[3] shows that if there are sufficiently many bidders, then for problems of this type one can convert
any approximation to the computational problem into a nearly-as-good approximation to the incentive-
compatible auction problem. In particular, Õ hn/ε 2 bidders are sufficient for this reduction to produce
only a factor (1 + ε) loss in approximation ratio when all valuations lie in the range [1, h]. Essentially,
the idea of the reduction is to randomly partitions bidders into two sets S1 and S2 , run the approximation
algorithm separately on each set, and then use the prices found for S1 on S2 and vice-versa (making
the process incentive-compatible); the results in [3] then show that Õ hn/ε 2 bidders are sufficient to
ensure that the resulting profit is nearly as large as if one had used prices determined on each Si on
that set itself. Related results of [14, 13] give bounds of this form for the case of a single digital good.
Thus, if one has sufficiently many bidders, one can focus attention on the computational approximation
problem.
The above results assume a one-shot mechanism (sealed-bid auction) in which all bidders are present
at the same time. We also consider the more demanding case that bidders arrive online, and one must
present to each bidder a set of item prices that depend only on bidders seen in the past. We show how
methods of [5, 6] for the online digital-good auction can be applied to our algorithms for graph (or k-
hypergraph) vertex pricing to achieve good performance for these problems in the online setting as well.
For the highway problem, we need a somewhat more involved argument using an algorithm of Kalai and
Vempala [18].

2 Previous work [16, 15] uses “m” to denote the number of items and “n” to denote the number of customers, viewing the

items as edges in some network. Since we are viewing items as vertices and customers as (hyper)edges, we have reversed this
notation.

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 181
M.-F. BALCAN AND A. B LUM

Organization The rest of this paper is organized as follows. We begin with basic definitions in Sec-
tion 2. We then present our 4-approximation algorithm for the graph vertex problem in Section 3 and our
O(k)-approximation algorithm for the k-Hypergraph Vertex Pricing problem in Section 4. We discuss
pricing below cost in Section 5, and present an O(log n) approximation for the highway problem in Sec-
tion 6. We present a fully polynomial time approximation scheme (FPTAS) for the case that the desired
subsets of different customers form a hierarchy in Section 7, and we show how our algorithms can be
adapted to achieve good performance in the online setting in Section 8. We finish with a discussion of
open questions in Section 9.

2 Notation and Definitions
We consider the following model introduced by Guruswami et al. [15]. We assume we have m customers
(or “bidders”) and n items (or “products”). We are in an unlimited supply setting, which means that the
seller is able to sell any number of units of each item, and they each have zero marginal cost to the seller
(or if they have some fixed marginal cost, we have subtracted that from all valuations and the seller may
not sell any item below cost). We consider single-minded bidders, which means that each customer is
interested in only a single bundle of items and has valuation 0 for all other bundles. Therefore, valuations
can be summarized by a set of pairs (e, we ) indicating that a customer is interested in bundle (hyperedge)
e and values it at we . Given the hyperedges e and valuations we , we wish to compute a pricing of the
items that maximizes the seller’s profit. We assume that if the total price of the items in e is at most we ,
then the customer (e, we ) will purchase all of the items in e, and otherwise the customer will purchase
nothing. That is, we want the price vector p = (p1 , . . . , pn ) with pi ≥ 0 for all i that maximizes

Profit(p) = ∑ price(e), where price(e) = ∑ pi .
e:we ≥price(e) i∈e

Let p∗ be the price vector with the maximum profit and let OPT = Profit(p∗ ).
Let us denote by E the set of customers, and V the set of items, and let h = maxe∈E we . Let G = (V, E)
be the induced hypergraph, whose vertices represent the set of items, and whose hyperedges represent
the customers. Notice that G might contain multi-edges since several customers might want the same
subset of items. In the special case that all customers want at most two items, so G is a multi-graph
(possibly with self-loops), we call this the graph vertex pricing problem. As mentioned in Section 1,
this pricing problem was shown to be APX-hard in [15]. If all customers want at most k items, we call
this the k-hypergraph vertex pricing problem. Guruswami et al. [15] present a simple O(log m + log n)
approximation algorithm for the general hypergraph vertex pricing problem.3 Our goal is to achieve
better guarantees for the graph or k-hypergraph case when k = o(log n).

3 Graph Vertex Pricing
We begin by considering the Graph Vertex Pricing problem, and show a factor 4 approximation.
3 In fact, it has been shown recently in [4] that one can achieve an O(log m + log n) approximation for bidders with general

valuation functions (not only single-minded bidders).

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 182
A PPROXIMATION A LGORITHMS AND O NLINE M ECHANISMS FOR I TEM P RICING

Theorem 3.1. There is a 4-approximation for the Graph Vertex Pricing problem.
Proof. First notice that if G is bipartite (with self-loops allowed as well), then there is a simple 2-
approximation algorithm. Specifically, consider the optimal price-vector p∗ and let OPTL be the amount
of profit it makes from selling nodes on the left, and OPTR be the amount it makes from selling nodes on
the right (so OPT = OPTL + OPTR ). Notice that if one takes p∗ and zeroes out all prices for nodes on the
right, then this has profit at least OPTL since all previous buyers still buy (and some new ones may too).4
Therefore, we can algorithmically make profit at least OPTL by setting all prices on the right to 0, and
then separately fixing prices for each node on the left so as to make the most profit possible from each
node. That is, for each node i, we simply order the buyers who want i by valuation we1 ≥ we2 ≥ we3 . . .,
and choose the price pi = we j maximizing jwe j . (Since the graph is bipartite, the profit made from some
node i on the left does not effect the optimal price for some other node i0 on the left.) Similarly we can
make at least OPTR by setting prices on the left to 0 and optimizing prices of nodes on the right. So,
taking the best of both options, we make
OPT
max (OPTL , OPTR ) ≥ .
2
Now consider the general (non-bipartite) case. Define opte to be the amount of profit that OPT
makes from edge e. We will think of opte as the weight of edge e, though it is unknown to our algorithm.
Let E2 be the set of edges that have two distinct endpoints, and let E1 be the set of self-loops. Let
OPT1 be the profit made by p∗ on edges in E1 and let OPT2 be the profit made by p∗ on edges in E2 ,
so ∑e∈Ei opte = OPTi for i = 1, 2 and OPT1 + OPT2 = OPT. Now, randomly partition the vertices into
two sets L and R. Since each edge e ∈ E2 has a 50% chance of having its endpoints on different sides, in
expectation 21 OPT2 weight is on edges with one endpoint in L and one endpoint in R. Thus, if we simply
ignore edges in E2 whose endpoints are on the same side and run the algorithm for the bipartite case, the
profit we make in expectation is at least

1 OPT2 OPT
OPT1 + ≥ .
2 2 4
This proves the desired result.

Derandomization If desired, the above algorithm can be derandomized using the fact that our analysis
only needs the partitioning distribution to be pairwise-independent. In particular, pairwise-independent
distributions can be realized using small (polynomial-size) sample spaces [20, 22]. Thus, given a prob-
lem instance, one can simply try each possibility in the sample space and then choose the one that
produces the highest profit.

4 k-Hypergraph Vertex Pricing
We now show how to extend the algorithm in Theorem 3.1 to get an O(k)-approximation when each
customer wants at most k items. This improves over the O(k2 ) bound of [7].
4 Note that it is essential in this argument that p∗ ≥ 0 for all i.
i

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 183
M.-F. BALCAN AND A. B LUM

Theorem 4.1. There is an O(k)-approximation algorithm for the k-Hypergraph Vertex Pricing problem.

Proof. We can use the following procedure.

Step 1 Randomly partition V into VL and Vrest by placing each node into VL with probability 1k .

Step 2 Let E 0 be the set of edges with exactly one endpoint in VL . Ignore all edges in E − E 0 .

Step 3 Set prices in Vrest to 0 and set prices in VL optimally with respect to edges in E 0 .

To analyze this algorithm, let OPTi,e denote the profit made by p∗ selling item i to bidder e. (So
OPTi,e ∈ {0, p∗i } and OPT = ∑i∈V,e∈E OPTi,e .) Notice that the total profit made in Step 3 is at least
∑i∈VL ,e∈E 0 OPTi,e because setting prices in Vrest to 0 can only increase the number of sales made by p∗ to
bidders in E 0 . Thus, we simply need to analyze the quantity E ∑i∈VL ,e∈E 0 OPTi,e .

Define indicator random variable Xi,e = 1 if i ∈ VL and e ∈ E 0 , and Xi,e = 0 otherwise. We have:

1 k−1

1 0
E[Xi,e ] = Pr[i ∈ VL and e ∈ E ] ≥ 1− . (4.1)
k k

Therefore,
" # " #
E ∑ OPTi,e = E ∑ Xi,e OPTi,e
i∈VL ,e∈E 0 i∈V,e∈E

= ∑ E [Xi,e ] OPTi,e
i∈V,e∈E

1 k−1

1
≥ 1− OPT
k k
OPT
≥ .
ke

Derandomization As with the algorithm of Theorem 3.1, the above algorithm for k-hypergraph vertex
pricing can also be derandomized if desired, but in this case we need the tools of Even et al. [12]. First,
note that we are only interested in the case that k is o(log n + log m), since for larger values of k we can
switch to the generic algorithm of Guruswami et al. [15]. Thus, we can allow for a blowup of 2O(k) in
our running time. Now, consider the algorithm in Theorem 4.1 and define indicator random variables
Xi = 1 if i ∈ VL and Xi = 0 otherwise. So, each Xi = 1 with probability 1/k, and notice that we need
only k-wise independence among the Xi to calculate E[Xi,e ] in Equation (4.1). Even et al. [12] give a
construction of small sample spaces that is especially well-suited to our needs. Their construction runs
in time polynomial in 2k , n, and 1/ε, and produces an explicit sample space with the following property:
for any k-tuple (Xi1 , . . . , Xik ) of the random variables Xi and any assignment (v1 , . . . , vk ) to their values,
the fraction of points in their sample space under which these variables all take on those values is within
±ε of the probability of this event under our product distribution. In particular, the k-tuples we care

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 184
A PPROXIMATION A LGORITHMS AND O NLINE M ECHANISMS FOR I TEM P RICING

about are those corresponding to edges e ∈ E, with values of the form (1, 0, . . . , 0) corresponding to the
event that Xi,e = 1. Setting ε = o (1/k), we get that under the uniform distribution over their sample
space, Equation (4.1) holds up to 1 − o(1), which suffices for our bounds. Thus, we simply run the
construction of Even al. [12] using such a value of ε, and try each partitioning in their explicit sample
space, choosing the one that produces the highest profit.

5 Pricing below Cost
Following prior work [15] we have so far required solutions to satisfy pi ≥ 0 for all i. In fact, for the case
of digital goods, it does not make sense to allow negative prices since even customers e for whom i 6∈ e
would purchase item i if pi < 0 (and moreover purchase infinitely many copies). However, in the case
of products of nonzero marginal cost, where we view pi as a profit margin (the difference between sales
price and the retailer’s cost) it could make sense to allow pi to be negative. In fact, a retailer might wish
to do so in order to induce more purchases of bundles containing both those and other more expensive
products. For example, consider four items A, B, C, and D, and three customers: one who values {A, B}
at $10 above their combined cost, one who values {B,C} at $40 above their cost, and one who values
{C, D} at $10 above their cost. If no item can be priced at a loss, then it is not possible to have all three
customers buy at their valuations. On the other hand, by pricing A and D at $10 below cost, and B and C
at $20 above cost, the seller could extract full profit (assuming all costs are at least $10). More generally,
we present an Ω(log n) “positivity gap”: a (bipartite) graph in which there is an Ω(log n) gap between
the optimal profit achievable without any items priced at a loss and the optimal profit if such pricing is
allowed. Specifically:

Theorem 5.1. For the graph vertex pricing problem, there exists an Ω(log n) gap between the profit
achievable when pricing below cost is allowed and the profit achievable when pricing below cost is not
allowed.

Proof. Consider a bipartite graph with vertices `1 , . . . , `n on the left and r1 , . . . , rn on the right, where
for convenience let n be a power of 2. A set S1 of bidders each want bundles of the form {`i , ri+1 } at
$1 above cost, a set S2 of bidders each want bundles of the form {`i , ri+2 } at $2 above cost, a set S4
of bidders each want bundles of the form {`i , ri+4 } at $4 above cost, and so forth, up to Sn/2 . Suppose
there are (n − 1)n bidders in S1 (n for each value of i ∈ {1, . . . , n − 1}), there are (n − 2)n/2 bidders in
S2 (n/2 for each value of i ∈ {1, . . . , n − 2}), there are (n − 4)n/4 bidders in S4 (n/4 for each value of
i ∈ {1, . . . , n − 4}) and so on, down to (n/2)2 bidders in Sn/2 (2 for each i ∈ {1, . . . , n/2}). In this case,
if negative profit margins are allowed, then one can price each `i at profit −i and each ri at profit i and
have all bidders buy at exactly their valuations, extracting full profit Θ(n2 log n). On the other hand,
the structure of bidders is such that the set of bidders who want any given item form an “equal revenue
distribution.” In particular, for any pricing in which all items on one side (say on the right) are priced at
zero, any pricing of items on the other can produce at most Θ(n) profit per item, or Θ(n2 ) total. This in
turn implies that it is not possible to get more than Θ(n2 ) profit using only non-negative profit margins,
since we know the optimal profit achievable using non-negative profit margins is within a factor of 2 of
the profit achievable when setting all items on one side of the graph to 0.

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 185
M.-F. BALCAN AND A. B LUM

Notice that our approximation algorithms in Sections 3 and 4 only provide good guarantees with
respect to the best profit achievable when pricing below cost is not allowed. We do not know whether it
is possible to achieve a o(log n) approximation when pricing below cost is allowed, even for the case of
bipartite graphs.
For the rest of the paper, we resume considering only the case that all prices must be nonnegative.

6 The Highway Problem
A particular interesting case of the hypergraph pricing problem considered in [15] is the highway prob-
lem. In this problem we think of the items 1, 2, . . . , n as segments of a highway, and each desired subset
e is an interval [i, j] of the highway. A special case of this problem shown in [15] to be solvable in poly-
nomial time is the case when all path requests share one common end-point r. For this case, Guruswami
et al. [15] give an O(m2 ) exact dynamic programming algorithm, which we will call A. They also give
pseudo-polynomial dynamic programming algorithms for two particular cases: an O(hh+2 mh+3 )-time
exact dynamic programming algorithm for the case when all valuations are integral, and an O(hk+1 m)
time exact dynamic programming algorithm for the case that furthermore all requests have path lengths
bounded by some constant k. The highway problem was recently shown to be weakly NP-hard by Briest
and Krysta [7].
We present below (Theorem 6.1) an O(log n) approximation algorithm for the highway problem,
improving over the O(log n + log m) approximation guarantee of Guruswami et al. [15].
Theorem 6.1. There is an O(log n)-approximation algorithm for the highway problem.
Proof. For convenience we assume n is a power of 2 (which we can always achieve by padding). We
begin by partitioning the customers into log2 n groups. Specifically, let S1 be the set of all customers
who want item n/2. Let S2 be the set of all customers not in S1 who want either item n/4 or item 3/4.
More generally, let Si be the set of customers not in S1 ∪ · · · ∪ Si−1 who want some item in

(2i − 1)n

n 3n
, ,..., .
2i 2i 2i
Now, for each set Si we can use algorithm A from [15] to get a 2-approximation to the optimal profit over
Si . Specifically, for each j ∈ {1, . . . , 2i − 1} let Si j be the subset of customers in Si who want item jn/2i .
Notice that by design, customers in set Si j do not have any desired item in common with customers
in Si j0 for j0 6= j, which means we can consider each of them separately. Now, for each Si j we get a
2-approximation to OPT(Si j ) by running A twice, first zeroing out all prices for items z < jn/2i and
then again zeroing out all prices for items z > jn/2i and taking the best of the two cases. Since there are
only log2 n groups Si , we simply use the algorithm A from [15] to get a 2-approximation to the optimal
profit over Si , and then take the best of all options, thus obtaining a 2 log2 n approximation overall.

6.1 Special cases
Using algorithm A we can also get a constant-factor approximation in the special case that everyone
wants exactly k items, for any (not necessarily constant) k. To see this, split the items into groups

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 186
A PPROXIMATION A LGORITHMS AND O NLINE M ECHANISMS FOR I TEM P RICING

G1 , G2 , . . . , Gn/k of size k, where G1 consists of the first k items, G2 consists of the next k items and
so on, and let OPTeven and OPTodd be the amount of money that OPT makes from the even-numbered
groups and from the odd-numbered groups respectively. We can make at least OPTeven /2 as follows. We
first set all the prices on items in the odd groups to zero. Now notice that each customer wants items in
at most one even-numbered group: let us associate that customer with that group. We can now partition
the customers in each even group into two types: those who want the leftmost item in the group and
those who want the rightmost item in the group (customers who want both can be assigned arbitrarily).
We then run the dynamic program separately over each type, and take the best outcome. In a similar
way, we can make at least OPTodd /2 by setting prices for items in the even groups to 0. So we try both
and take the best, thus obtaining a factor of 4 algorithm.
Similarly we can get a factor of 4c approximation algorithm if for some value of k, all customers
want between k/c and k elements.

7 When bidders form a hierarchy
We present a fully polynomial time approximation scheme for the case that the desired subsets of differ-
ent (single-minded) customers form a hierarchy, also known as a laminar family of sets.5 Specifically,
we consider the case of a hypergraph where for any two edges e, e0 , we have e ⊆ e0 or e ⊇ e0 or e ∩ e0 = 0.
/
This means that the edges themselves can be viewed as forming a tree structure (actually, a forest) or-
dered by containment. Let Te be the set of all bidders whose desired subset is contained in e. Note that
we can assume for simplicity that we have a binary hierarchy (if the hierarchy is not binary, then we can
transform it into a binary hierarchy by adding fake edges e, increasing the size of the hypergraph by at
most a constant factor).
We start by presenting a pseudopolynomial algorithm for the case that the bidders have integral
valuations (between 0 and h). In this case, by the integrality lemma in [15] there exists an integral
optimal solution. For each e ∈ E and nonnegative integer s ≤ h, let us denote by nes the number of
bidders with desired set e whose valuations are at least s. Now, for each e ∈ E and nonnegative integer
s ≤ nh, let A[s, e] represent the maximum possible profit we get from bidders in Te when the total sum of
the prices on items in e is exactly s. Our dynamic programming algorithm for computing the quantities
A[s, e] can be now specified as follows.

Step 1 For each “leaf” e in the hierarchy (an edge e that does not contain any other edges e0 ) initialize
A[s, e] = s · nes .

Step 2 Consider any edge e with children e1 and e2 whose A-values have been computed. Compute

A[s, e] = max (A[s1 , e1 ] + A[s2 , e2 ]) + snes .
s1 +s2 =s

Step 3 Return max A[s, r]. (Here r is the root of the hierarchy).
s≤nh

5 Independently, Briest and Krysta [7] show a similar result. They also show that this problem in NP-hard.

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 187
M.-F. BALCAN AND A. B LUM

After computing the A-values, we can then easily determine the optimal pricing vector by backtracking.
Clearly, the overall procedure above runs in time polynomial in n, m and h.
If we do not want to have a polynomial dependence on h, we can instead use the above pseudopoly-
nomial algorithm to obtain an FPTAS in a fairly standard way as follows.
εh
Step 1 Given ε > 0, let ` = nm .

Step 2 Define w0e = w`e , for each hyperedge e ∈ E.

Step 3 Run the dynamic programming algorithm on the instance specified by G = (V, E) and valuations
w0e , and let p0 be the returned price vector.

Step 4 Output the price vector p̃ defined as p̃i = ` · p0i , for i ∈ V .

Theorem 7.1. The above algorithm is an FPTAS, achieving profit at least (1−ε)OPT in time polynomial
in n, m, and ε1 .
Proof. In the following discussion, let Profitw0 (p) denote the profit made by using the price vector p
in the rounded instance specified by G = (V, E) and valuations w0e . In order to prove that the profit we
obtain by using p̃ in the original instance (given by G = (V, E) and valuations we ) is at least (1 − ε)OPT,
we first make some observations.
Let p be a price vector and let W be the set of winners under the pricing scheme p in the original in-
stance. If p00 is the pricing vector defined as p00i = bpi /`c for i ∈ V , then Profitw0 (p00 ) ≥ (1/`) · Profit(p) −
nm. To see why this is true, notice first that W ⊆ W 00 , where W 00 is the set of winners under the pricing
scheme p00 in the rounded instance (specified by G = (V, E) and the valuations w0e ). This follows from
the fact that ∑ pi ≤ we implies ∑ p00i = ∑ bpi /`c ≤ bwe /`c = w0e . This implies
i∈e i∈e i∈e
p 1
Profitw0 (p00 ) = ∑ ∑ p00i ≥ ∑ ∑
i
− 1 ≥ · Profit(p) − nm ,
e∈W 00 i∈e e∈W i∈e ` `

as desired.
Let p0 be a pricing vector and let W 0 be the set of winners under the pricing scheme p0 in the rounded
instance. If p̃ is the pricing vector defined as p̃i = ` · p0i for i ∈ V , then Profit(p̃) ≥ ` · Profitw0 (p0 ). To see
why this is true, notice first that W 0 ⊆ W , where W is the set of winners under p̃ in the original instance.
This follows from the fact that ∑i∈e p0i ≤ w0e implies ∑i∈e p̃i = ` · ∑i∈e p0i ≤ ` · w0e = l bwe /`c ≤ we . This
implies
Profit(p̃) = ∑ ∑ p̃i = ∑ ∑ ` · p0i ≥ ∑ ∑ ` · p0i = ` · Profitw0 (p0 ) ,
e∈W i∈e e∈W i∈e e∈W 0 i∈e
as desired.
We are now ready to show that Profit(p̃) ≥ (1 − ε)OPT. Let p∗ and p0 be the price vectors with
the maximum profit in the original and rounded instances respectively, and let W ∗ and W be the cor-
responding set of winners. Let p̃ be the price vector defined as p̃i = ` · p0i for i ∈ V and let p00 is the
pricing vector defined as p00i = bp∗i /`c for i ∈ V . According to the previous observations we have
Profit(p̃) ≥ ` · Profitw0 (p0 ). Since p0 is the price vector with the maximum profit in the rounded in-
stance we have Profitw0 (p0 ) ≥ Profitw0 (p00 ). Combining these together with the fact that Profitw0 (p00 ) ≥

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 188
A PPROXIMATION A LGORITHMS AND O NLINE M ECHANISMS FOR I TEM P RICING

(1/`) · Profit(p∗ ) − nm, we get Profit(p̃) ≥ Profit(p∗ ) − `nm, which implies Profit(p̃) ≥ (1 − ε)OPT, as
desired.
Since w0e ≤ nm/ε for all e ∈ E, we also have that our procedure runs in polynomial time in n, m, and
1/ε, thus being an FPTAS for the hierarchy case.

8 Online Pricing
As mentioned in Section 1, results of Balcan et al. [3] can be used to convert our algorithms into
incentive-compatible mechanisms in the offline “batch” setting (i. e., a sealed-bid auction). In this sec-
tion we consider a natural, more demanding online setting in which customers arrive one at a time, and
we must assign prices to the items for customer t based only on information about customers 1, . . . ,t − 1.

8.1 The model
We assume customers arrive one at a time. Each customer will be shown a set of item prices, and
will then decide whether to purchase or not at those prices. We assume customers cannot return and
cannot control their time of arrival, so any take-it-or-leave-it set of prices for customer t based only
on information received from customers 1, . . . ,t − 1 is incentive-compatible. In addition, we assume
an oblivious adversary model: that is, our objective is to achieve good expected performance for any
sequence of customers, but this sequence cannot depend on the outcome of any probabilistic choices
made by our algorithm. As before, we use m to denote the total number of customers.
We consider two information models. In the full information model, we assume that after the tth
customer departs, we learn his desired set et and valuation vt . In the more difficult posted-price model,
we assume we only find out whether and what the customer purchased but not his actual valuations.
That is, if he purchases a subset at the current prices, we do not know if he still would have purchased
at higher prices, and if he does not purchase at the current prices, we do not know if (or what) he would
have purchased at lower prices. In both models, we will be interested in algorithms that perform well
compared to the best fixed setting of prices for the entire sequence. Thus, we are comparing to the same
notion of OPT as in the offline case.

8.2 The Online Graph and k-Hypergraph Pricing Problems
Our 4-approximation for graph vertex-pricing, and our O(k)-approximation for k-hypergraph vertex
pricing, can be directly adapted to the online setting by using the results of [5, 6] for the online digital-
good auction. In particular, for the full-information setting, Blum and Hartline [5] show the following:
Theorem 8.1 ([5]). Consider the online pricing problem for a single item (n = 1) in the full-information
setting. There exists an online algorithm such that for any given ε > 0, its expected profit on any input
sequence of maximum valuation h is at least

nh 1
(1 − ε)OPT − O log .
ε ε

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 189
M.-F. BALCAN AND A. B LUM

We can now use this to prove the following result.

Theorem 8.2. Consider the online hypergraph vertex pricing problem in the full-information setting.
There exists an online algorithm such that for any given ε > 0, its expected profit on any input sequence
is at least
nh 1
(1 − ε)ALG − O log ,
ε ε
where ALG is is the profit of the offline approximation algorithm in Section 4 on that input.

Proof. Note that our algorithms in Sections 3 and 4 begin by selecting a subset VL of items to have
non-zero prices, and then achieve their approximation guarantees considering only profit made from
customers who want exactly one item in VL . Thus, we can view these algorithms as effectively perform-
ing |VL | separate digital-good auctions, ignoring customers who want zero, or more than one, item from
VL . In particular, to apply these algorithms to the full-information online setting, we begin by randomly
choosing the set VL as described in the algorithms, setting prices for items in V −VL to 0. We then instan-
tiate a separate copy of the online digital-good auction from [5] for each item i ∈ VL . When a customer
arrives, if the customer wants exactly one item i from VL , then his valuation is given to the associated
online auction algorithm. Let OPTi denote the optimal profit achievable using a fixed price for item i
from customers whose bundles contain item i but no other item in VL . By Theorem 8.1, the expected
profit of the online auction for item i will therefore be at least (1 − ε)OPTi − O((h/ε) log 1/ε). Thus,
overall, we achieve profit at least

nh 1
(1 − ε) ∑ OPTi − O log ,
i∈VL ε ε

where ∑i∈VL OPTi is the profit of the offline approximation algorithm. Note that we need the assumption
of an oblivious adversary for the approximation ratios proved in Sections 3 and 4 to apply.

In particular, so long as the offline algorithm’s profit is Ω((nh/ε 2 ) log 1/ε), we lose only a (1+O(ε))
factor in the conversion to the online setting. In the posted-price setting, we can obtain a similar result:
we only need to apply the associated posted-price algorithms of [5, 6]. The only tricky issue is that a
customer who chooses not to buy anything must be fed in as a non-buyer to all of the online algorithms,
in order to ensure that the sequence of customers fed into algorithm i is a superset of the true customers
for that item (so that the value of OPT for the sequence fed to the algorithm is at least as large as the true
OPT for that item). In addition, the algorithms for the posted-price scenario require that the upper-bound
h on the maximum valuation be known in advance.

8.3 The Online Highway Problem
For the highway problem, we cannot decompose our solution into a collection of independent digital-
good auctions, so the reduction in Section 8.2 does not apply. However, we can convert to the online
setting by placing this problem in the framework of online geometric optimization studied by Kalai and
Vempala [18] as extended to the case of approximation algorithms by Kakade et al. [17]. In particular,
[17] gives a method to convert any efficient approximation algorithm for offline optimization into an

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 190
A PPROXIMATION A LGORITHMS AND O NLINE M ECHANISMS FOR I TEM P RICING

efficient algorithm for online optimization with asymptotically the same approximation ratio, for any
problem of the following type:

1. There is a set S ⊆ Rd of feasible points. At each time step t we must pick some point pt ∈ S; we
are then given an objective function vt ∈ Rd , and we obtain profit pt · vt .

2. Our goal is to perform nearly as well as the best point p ∈ S in hindsight. That is, we want ∑ pt · vt
t
to be nearly as large as max ∑ p · vt .
p∈S t

3. We have an efficient α-approximation algorithm for the offline optimization problem: given ob-
jective function v ∈ Rd , find the point p ∈ S that maximizes p · v.

Kalai and Vempala [18] (for the case of exact offline algorithms) and Kakade et al. [17] (for the
case of approximation algorithms) give a procedure for choosing points pt online for any problem of the
above type such that the total profit obtained, ∑t pt · vt , is within a (1 − ε)/α factor of the profit of the
best p ∈ S in hindsight, minus an additive term that is polynomial in the diameter of S and the maximum
L1 magnitude of any vt .
We can place the highway problem into the above setting as follows. First, for simplicity of exposi-
tion, let us assume all bidders have integral valuations between 0 and h, and that we are willing to have
an algorithm that runs in time polynomial in h as opposed to log h (the general case can be handled by
rounding and scaling as in Section 7). Now, let S be the set of all possible item prices represented in
the following way. Given a pricing of the n items, let qi j denote the total cost of the bundle [i, j]. We
represent qi j as a vector of length h consisting of qi j − 1 zeros followed by h − qi j + 1 entries at value
qi j . To represent the entire pricing of the n items, we just concatenate these n2 vectors together to create
a point in Rd for d = n2 h. A bidder who desires bundle [i, j] at value w is represented as a vector of all
zero entries except for a 1 in the w-th coordinate of the block corresponding to qi j . By design, the dot
product of this vector with a vector p ∈ S is exactly the profit that would be obtained from this bidder
by the item-pricing corresponding to p. Finally, we can use the optimization algorithm from Section 6
or from [15] as our offline optimization oracle. Since the diameter of S is polynomial in n and h, and the
maximum L1 magnitude of any vt is at most 1, the total profit obtained will be within a 1 + ε factor of
the approximation ratio guaranteed by the optimization algorithm, minus an additive loss term which is
polynomial in n and h.
Note that for the posted-price version, we just need to apply known extensions of the Kalai-Vempala
algorithm to the bandit setting [1, 21, 9, 17] in which only the profit pt · vt and not the actual vector vt is
revealed to the algorithm.

9 Conclusions
We present approximation and online algorithms for a number of problems of pricing items to consumers
so as to maximize seller’s revenue in an unlimited supply setting. We achieve an O(k)-approximation
algorithm for the case of single-minded bidders where each consumer wants at most k items, an O(log n)
approximation for the highway problem from [15], and a constant factor approximation to the highway

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 191
M.-F. BALCAN AND A. B LUM

problem when all bidders want approximately (up to a constant factor) the same number of items. We
also show how some of our approximation algorithms can be adapted to the more demanding online
setting in which customers arrive one at a time, in both the full-information and posted-price settings.

9.1 Subsequent Work
Following the initial publication of our work, Krauthgamer, Mehta and Rudra [19] have provided im-
proved approximation guarantees for the graph vertex pricing problem in the special case when the range
of bidders’ valuations is small. Briest and Krysta observe [8] that our algorithms in Sections 3 and 4
can be adapted to obtain similar guarantees for the case of unlimited supply unit-demand combinatorial
auctions. Balcan et al. [2] further study how pricing certain items below their marginal cost can lead to
an improvement in overall profit. In particular, they develop the rebate and coupon models for analyzing
this issue and examine “profitability gaps” (to what extent can pricing below cost help to improve profit)
as well as algorithms for pricing. Elbassioni et al. [11] give a quasi-polynomial time approximation
scheme for the highway problem.

9.2 Open Questions
There are several natural open problems left by this work.
First, can one improve on the factor of 4 for the graph vertex-pricing problem? Any method able to
reduce the factor of 2 for the bipartite case would immediately result in an improved bound. Alterna-
tively, perhaps the reduction to the bipartite case can be improved. Second, can one achieve o(k) for the
hypergraph vertex-pricing problem? Even for the general case there remains a gap between the known
upper bounds and the lower bound of [10].
Finally, an intriguing question related to this work is: what kind of approximation guarantees are
achievable if one allows the seller to price some items below cost (i. e., to have “loss leaders”)? Some
progress on this direction has been made in [2]; however, we still do not know if there exists a constant-
factor approximation for the graph vertex pricing problem (even the bipartite case) when negative profit
margins on some items are allowed.

Acknowledgements
We would like to thank Jason Hartline for posing the graph vertex-pricing problem to us and for helpful
discussions. We would also like to thank the referees for their helpful comments and suggestions.

References
[1] * B. AWERBUCH AND R. K LEINBERG: Adaptive routing with end-to-end feedback: Dis-
tributed learning and geometric approaches. In Proc. 36th STOC, pp. 45–53. ACM Press, 2004.
[STOC:1007352.1007367]. 8.3

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 192
A PPROXIMATION A LGORITHMS AND O NLINE M ECHANISMS FOR I TEM P RICING

[2] * M.-F. BALCAN , A. B LUM , H. C HAN , AND M.T. H AJIAGHAYI: A theory of loss-leaders:
Making money by pricing below cost. In Proc. 3rd Intern. Workshop on Internet and Network
Economics, Lecture Notes in Computer Science. Springer, 2007. 9.1, 9.2

[3] * M.-F. BALCAN , A. B LUM , J. H ARTLINE , AND Y. M ANSOUR: Mechanism design
via machine learning. In Proc. 46th FOCS, pp. 605–614. IEEE Computer Soc., 2005.
[FOCS:10.1109/SFCS.2005.50]. 1, 8

[4] * M.-F. BALCAN , A. B LUM , AND Y. M ANSOUR: Single price mechanisms for revenue maxi-
mization in unlimited supply combinatorial auctions. Technical Report CMU-CS-07-111, Carnegie
Mellon University, 2007. 3

[5] * A. B LUM AND J. H ARTLINE: Near-optimal online auctions. In Proc. 16th Ann.
ACM-SIAM Symp. on Discrete Algorithms (SODA’05), pp. 1156–1163. SIAM, 2005.
[SODA:1070432.1070597]. 1, 8.2, 8.1, 8.2

[6] * A. B LUM , V. K UMAR , A. RUDRA , AND F. W U: Online learning in online auctions. In
Proc. 14th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’03), pp. 202–204. SIAM, 2003.
[SODA:644108.644143]. 1, 8.2, 8.2

[7] * P. B RIEST AND P. K RYSTA: Single-minded unlimited supply pricing on sparse instances. In
Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 1093–1102. SIAM,
2006. [SODA:1109557.1109678]. 1, 4, 6, 5

[8] * P. B RIEST AND P. K RYSTA: Buying cheap is expensive: Hardness of non-parametric multi-
product pricing. In Proc. 18th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’07), pp.
716–725. SIAM, 2007. [SODA:1283383.1283460]. 9.1

[9] * V. DANI AND T. P. H AYES: Robbing the bandit: Less regret in online geometric optimiza-
tion against an adaptive adversary. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA’06), pp. 937–943. SIAM, 2006. [SODA:1109557.1109660]. 8.3

[10] * E. D. D EMAINE , U. F EIGE , M. H AJIAGHAYI , AND M. R. S ALAVATIPOUR: Combination can
be hard: Approximability of the unique coverage problem. In Proc. 17th Ann. ACM-SIAM Symp.
on Discrete Algorithms (SODA’06), pp. 162–171. SIAM, 2006. [SODA:1109557.1109577]. 1,
9.2

[11] * K. E LBASSIONI , R. S ITTERS , AND Y. Z HANG: A quasi-PTAS for profit-maximizing pricing
on line graphs. In Proc. 15th Ann. European Symp. on Algorithms (ESA’07), Lecture Notes in
Computer Science. Springer, 2007. 9.1

[12] * G. E VEN , O. G OLDREICH , M. L UBY, N. N ISAN , AND B. V ELICKOVIC: Efficient ap-
proximation of product distributions. Random Structures and Algorithms, 13(1):1–16, 1998.
[Wiley:10.1002/(SICI)1098-2418(199808)13:1¡1::AID-RSA1¿3.0.CO;2-W]. 4

[13] * A. G OLDBERG , J. H ARTLINE , A. K ARLIN , M. S AKS , AND A. W RIGHT: Competitive auctions.
Games and Economic Behavior, 55(2):242–269, 2006. [Elsevier:10.1016/j.geb.2006.02.003]. 1

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 193
M.-F. BALCAN AND A. B LUM

[14] * A. G OLDBERG , J. H ARTLINE , AND A. W RIGHT: Competitive auctions and digital goods. In
Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’01), pp. 735–744. SIAM, 2001.
[SODA:365411.365768]. 1

[15] * V. G URUSWAMI , J. H ARTLINE , A. K ARLIN , D. K EMPE , C. K ENYON , AND F. M C S HERRY:
On profit-maximizing envy-free pricing. In Proc. 16th Ann. ACM-SIAM Symp. on Discrete Algo-
rithms (SODA’05), pp. 1164–1173. SIAM, 2005. [SODA:1070432.1070598]. 1, 2, 2, 4, 5, 6, 6, 7,
8.3, 9

[16] * J. H ARTLINE AND V. KOLTUN: Near-optimal pricing in near-linear time. In 9th Workshop on
Algorithms and Data Structures (WADS’05), number 3608 in Lecture Notes in Computer Science,
pp. 422–431. Springer, 2005. [WADS:al2ke8gd23a44atp]. 1, 2

[17] * S. K AKADE , A. K ALAI , AND K. L IGETT: Playing games with approximation algorithms. In
Proc. 39th STOC, pp. 546–555. ACM Press, 2007. [STOC:1250790.1250870]. 8.3, 8.3

[18] * A. K ALAI AND S. V EMPALA: Efficient algorithms for online decision problems. Journal of
Computer and System Sciences, 71(3):291–307, 2005. An earlier version appears in COLT 2003.
[JCSS:10.1016/j.jcss.2004.10.016, Springer:fbx1n68j5ubyv706]. 1, 8.3, 8.3

[19] * R. K RAUTHGAMER , A. M EHTA , AND A. RUDRA: Pricing commodities, or how to sell when
buyers have restricted valuations. In 5th Workshop on Approximation and Online Algorithms.
Springer, 2007. 9.1

[20] * M. L UBY AND A. W IGDERSON: Pairwise independence and derandomization. Technical Report
CSD-95-880, U.C. Berkeley, 1995. 3

[21] * H. B. M C M AHAN AND A. B LUM: Online geometric optimization in the bandit set-
ting against an adaptive adversary. In Proc. 17th Conf. on Computational Learning Theory
(COLT’04), number 3120 in Lecture Notes in Computer Science, pp. 109–123. Springer, 2004.
[Springer:38p3f4h61cgy7gg7]. 8.3

[22] * R. M OTWANI AND P. R AGHAVAN: Randomized Algorithms. Cambridge University Press, 1995.
3

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 194
A PPROXIMATION A LGORITHMS AND O NLINE M ECHANISMS FOR I TEM P RICING

AUTHORS

Maria-Florina Balcan [About the author]
Computer Science Department
Carnegie Mellon University
Pittsburgh, PA 15213
ninamf cs cmu edu
www.cs.cmu.edu/~ninamf/

Avrim Blum [About the author]
Computer Science Department
Carnegie Mellon University
Pittsburgh, PA 15213
avrim cs cmu edu
www.cs.cmu.edu/~avrim/

ABOUT THE AUTHORS

M ARIA -F LORINA BALCAN is a Ph. D. candidate at Carnegie Mellon University under the
supervision of Avrim Blum. Everyone who knows her calls her “Nina,” a tradition
originally started by her brother Marius when he was too young to appreciate longer
names. Nina received B. S. and M. S. degrees from the University of Bucharest, Faculty
of Mathematics and Informatics, Romania. Her primary research interests are Com-
putational and Statistical Machine Learning, computational aspects of Economics and
Game Theory, and Algorithms. She owes much of her interest in Computer Science to
Professors Luminita State, her undergraduate mentor, and Florentina Hristea, her role
model at the time, who offered Nina the opportunity of her first textbook co-authorship.

AVRIM B LUM grew up in Berkeley, California, and then went to MIT for undergraduate
and graduate school. He received his Ph. D. in Computer Science under supervision of
Ron Rivest, and is now Professor of Computer Science at Carnegie Mellon University.
His research interests include Approximation Algorithms, Algorithmic Game Theory,
and Machine Learning Theory. He has two children, Alex and Aaron, who may or may
not go into the family business.

T HEORY OF C OMPUTING, Volume 3 (2007), pp. 179–195 195