Derandomization of auctions

Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D Hartline*, Nicole Immorlica, Madhu Sudan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We study the role of randomization in seller optimal (i.e., profit maximization) auctions. Bayesian optimal auctions (e.g., Myerson, 1981) assume that the valuations of the agents are random draws from a distribution and prior-free optimal auctions either are randomized (e.g., Goldberg et al., 2006) or assume the valuations are randomized (e.g., Segal, 2003). Is randomization fundamental to profit maximization in auctions? Our main result is a general approach to derandomize single-item multi-unit unit-demand auctions while approximately preserving their performance (i.e., revenue). Our general technique is constructive but not computationally tractable. We complement the general result with the explicit and computationally-simple derandomization of a particular auction. Our results are obtained through analogy to hat puzzles that are interesting in their own right.

Original languageEnglish (US)
Pages (from-to)1-11
Number of pages11
JournalGames and Economic Behavior
Volume72
Issue number1
DOIs
StatePublished - May 1 2011

Keywords

  • Auctions
  • Hat puzzles
  • Prior-free
  • Randomization

ASJC Scopus subject areas

  • Finance
  • Economics and Econometrics

Fingerprint Dive into the research topics of 'Derandomization of auctions'. Together they form a unique fingerprint.

Cite this