Received: March 29, 2007
Published: October 3, 2007
DOI: 10.4086/toc.2007.v003a009
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(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 wij on the edges, find prices pi ≥ 0 for the vertices to maximize
| ∑ | (pi + pj). |
| {(i,j): wij ≥ pi+pj} |
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.