A Lower Bound on the Competitive Ratio of Truthful Auctions

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

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

Computer Science

Research output: Contribution to journal › Article › peer-review

9 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 language	English (US)
Pages (from-to)	644-655
Number of pages	12
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2996
State	Published - Dec 1 2004

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Cite this

@article{d366355676ee430b84fd38a8b6e4bb8c,

title = "A Lower Bound on the Competitive Ratio of Truthful Auctions",

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].",

author = "Goldberg, {Andrew V.} and Hartline, {Jason D.} and Karlin, {Anna R.} and Michael Saks",

year = "2004",

month = dec,

day = "1",

language = "English (US)",

volume = "2996",

pages = "644--655",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Verlag",

}

TY - JOUR

T1 - A Lower Bound on the Competitive Ratio of Truthful Auctions

AU - Goldberg, Andrew V.

AU - Hartline, Jason D.

AU - Karlin, Anna R.

AU - Saks, Michael

PY - 2004/12/1

Y1 - 2004/12/1

N2 - 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].

AB - 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].

UR - http://www.scopus.com/inward/record.url?scp=35048839750&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35048839750&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:35048839750

SN - 0302-9743

VL - 2996

SP - 644

EP - 655

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

ER -

A Lower Bound on the Competitive Ratio of Truthful Auctions

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this