Near-Optimal Online Auctions
journal contributionposted on 01.01.1981, 00:00 by Avrim Blum, Jason D. Hartline
We consider the online auction problem proposed by Bar-Yossef, Hildrum, and Wu  in which an auctioneer is selling identical items to bidders arriving one at a time. 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 answers open questions from [4, 5]. We further improve on the results from  for the online posted-price problem by reducing 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 indistinguishable. We apply our online auction solution to achieve good bounds for the attribute auction problem with 1-dimensional attributes.