file.pdf (201.1 kB)

Near-Optimal Online Auctions

Download (201.1 kB)
journal contribution
posted on 01.01.1981 by Avrim Blum, Jason D. Hartline
We consider the online auction problem proposed by Bar-Yossef, Hildrum, and Wu [4] 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 [5] 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.

History

Publisher Statement

All Rights Reserved

Date

01/01/1981

Exports

Exports