Theory of Computing
-------------------
Title : Approximation Algorithms and Online Mechanisms for Item Pricing
Authors : Maria-Florina Balcan and Avrim Blum
Volume : 3
Number : 9
Pages : 179-195
URL : http://www.theoryofcomputing.org/articles/v003a009
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(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 w_{ij} on the edges,
find prices p_i \geq 0 for the vertices to maximize
\sum_{(i,j): w_{ij} \geq p_i+p_j} (p_i + 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 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.