From optimal limited to unlimited supply auctions

Jason D. Hartline*, Robert McGrew

*Corresponding author for this work

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

33 Scopus citations


We investigate the class of single-round, sealed-bid auctions for a set of identical items to bidders who each desire one unit. We adopt the worst-case competitive framework defined by [9, 5] that compares the profit of an auction to that of an optimal single-price sale of least two items. In this paper, we first derive an optimal auction for three items, answering an open question from [8]. Second, we show that the form of this auction is independent of the competitive framework used. Third, we propose a schema for converting a given limited-supply auction into an unlimited supply auction. Applying this technique to our optimal auction for three items, we achieve an auction with a competitive ratio of 3.25, which improves upon the previously best-known competitive ratio of 3.39 from [7]. Finally, we generalize a result from [8] and extend our understanding of the nature of the optimal competitive auction by showing that the optimal competitive auction occasionally offers prices that are higher than all bid values.

Original languageEnglish (US)
Title of host publicationEC'05
Subtitle of host publicationProceedings of the 6th ACM Conference on Electronic Commerce
Number of pages8
StatePublished - Dec 1 2005
EventEC'05: 6th ACM Conference on Electronic Commerce - Vancouver, Canada
Duration: Jun 5 2005Jun 8 2005


OtherEC'05: 6th ACM Conference on Electronic Commerce


  • Auctions
  • Competitive Analysis
  • Mechanism Design

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications


Dive into the research topics of 'From optimal limited to unlimited supply auctions'. Together they form a unique fingerprint.

Cite this