Performance of an online auction can be improved by an algorithm that learns from the set of bids already made. An online auction receives bids, and deals with each individually, deciding whether to accept a bid or wait for a higher one. This paper sets bounds on the performance of a learning algorithm, and shows that, for moderately long auctions, the performance is better than that of an existing algorithm.

The proofs use formal mathematics, which are difficult to summarize. The flavor of the paper may be given by a simplification of one result: For any function f(h) = o(h log log h), where h is the ratio between the highest and lowest bids, if the sequences of bids made is greater than or equal to f(h), then the revenue generated is comparable to that of an optimal offline auction. The paper seems to be intended for those mathematically inclined, and does not focus on the mechanics of the algorithm.