Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784
Greece

phone: +30 210 7275122
fax: +30 210 7275114

Elias Koutsoupias and George Pierrakos: On the Competitive Ratio of Online Sampling Auctions. WINE 2010: 327-338.

### Abstract

We study online profit-maximizing auctions for digital goods with adversarial bid selection and uniformly random arrivals. Our goal is to design auctions that are constant competitive with $\mathcal{F}^{(2)}$; in this sense our model lies at the intersection of prior-free mechanism design and secretary problems. We first give a generic reduction that transforms any offline auction to an online one, with only a loss of a factor of 2 in the competitive ratio; we then present some natural auctions, both randomized and deterministic, and study their competitive ratio; our analysis reveals some interesting connections of one of these auctions with RSOP, which we further investigate in our final section.

### Bib

@inproceedings{kp10,
author    = {Elias Koutsoupias and
George Pierrakos},
title     = {On the Competitive Ratio of Online Sampling Auctions},
booktitle = {WINE},
year      = {2010},
month     = dec,
pages     = {327-338},
ee        = {http://dx.doi.org/10.1007/978-3-642-17572-5_27},
}