Near-optimal online auctions

Avrim Blum*, Jason D. Hartline

*Corresponding author for this work

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

79 Scopus citations

Abstract

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
Pages1156-1163
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

Other

OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityVancouver, BC
Period1/23/051/25/05

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

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

Cite this