On the competitive ratio of the random sampling auction

Uriel Feige*, Abraham Flaxman, Jason D. Hartline, Robert Kleinberg

*Corresponding author for this work

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

18 Scopus citations

Abstract

We give a. simple analysis of the competitive ratio of the random sampling auction from [10]. The random sampling auction was first shown to be worst-case competitive in [9] (with a bound of 7600 on its competitive ratio); our analysis improves the bound to, 15. In support of the conjecture that random sampling auction is in fact 4-competitive, we show that on the equal revenue input, where any sale price gives the same revenue, random sampling is exactly a factor of four from optimal.

Original languageEnglish (US)
Title of host publicationInternet and Network Economics - First International Workshop, WINE 2005, Proceedings
Pages878-886
Number of pages9
DOIs
StatePublished - 2005
Event1st International Workshop on Internet and Network Economics, WINE 2005 - Hong Kong, China
Duration: Dec 15 2005Dec 17 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3828 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other1st International Workshop on Internet and Network Economics, WINE 2005
CountryChina
CityHong Kong
Period12/15/0512/17/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the competitive ratio of the random sampling auction'. Together they form a unique fingerprint.

Cite this