Near-optimal online auctions

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. 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.