A Lower Bound on the Competitive Ratio of Truthful Auctions

Andrew V. Goldberg*, Jason D. Hartline, Anna R. Karlin, Michael Saks

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [6,3] that compares the profit of an auction to that of an optimal single price sale to at least two bidders. In this framework, we give a lower bound of 2.42 (an improvement from the bound of 2 given in [3]) on the competitive ratio of any truthful auction, one where each bidders best strategy is to declare the true maximum value an item is worth to them. This result contrasts with the 3.39 competitive ratio of the best known truthful auction [4].

Original languageEnglish (US)
Pages (from-to)644-655
Number of pages12
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2996
StatePublished - Dec 1 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A Lower Bound on the Competitive Ratio of Truthful Auctions'. Together they form a unique fingerprint.

Cite this