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

28 Scopus citations

Abstract

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
Pages175-182
Number of pages8
DOIs
StatePublished - Dec 1 2005
EventEC'05: 6th ACM Conference on Electronic Commerce - Vancouver, Canada
Duration: Jun 5 2005Jun 8 2005

Other

OtherEC'05: 6th ACM Conference on Electronic Commerce
CountryCanada
CityVancouver
Period6/5/056/8/05

Keywords

  • Auctions
  • Competitive Analysis
  • Mechanism Design

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications

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

Cite this