Near-optimal online auctions

Avrim Blum*, Jason D. Hartline

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

101 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationProceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Number of pages8
StatePublished - Jul 1 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005


OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityVancouver, BC

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'Near-optimal online auctions'. Together they form a unique fingerprint.

Cite this