Published: October 3, 2007

**Keywords:**Combinatorial Auctions, Pricing Problems, Revenue Maximization, Approximation Algorithms, Online Optimization

**Categories:**short, algorithms, approximation algorithms, online algorithms, electronic commerce, ecommerce

**ACM Classification:**F.2, J.4

**AMS Classification:**68W25, 68W20, 68Q32, 91B26

**Abstract:**
[Plain Text Version]

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(k^2)$
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 $\val_{ij}$ on the edges, find
prices $p_i \geq 0$ for the vertices to maximize
$$\sum\limits_{\{(i,j):\val_{ij} \geq p_i+p_j\}} \left(p_i + p_j \right)\,.$$
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 {\ncust} + \log {\nitems})$ to $O(\log {\nitems})$,
where $\ncust$ is the number of bidders and $\nitems$ 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
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.