Near-optimal online auctions

Abstract We consider the online auction problem proposed byBar-Yossef, Hildrum, and Wu 4 in which an auctioneer is selling identical items to bidders arriving one at atime. We give an auction that achieves a constant factor of the optimal profit less an O(h) additive loss term,where h is the value of the highest bid. Furthermore,this auction does not require foreknowledge of the range of bidders valuations. On both counts, this answersopen questions from 4, 5. We further improve on the results from 5 for the online posted-price problem by re-ducing their additive loss term from O(h log h log log h)to O(h log log h). Finally, we define the notion of an(offline) attribute auction for modeling the problem of auctioning items to consumers who are not a-priori in-distinguishable. We apply our online auction solution to achieve good bounds for the attribute auction problemwith 1-dimensional attributes.