Derandomization of auctions

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

*Corresponding author for this work

Research output: Contribution to journalConference article

24 Scopus citations

Abstract

We study the problem of designing seller-optimal auctions, i.e. auctions where the objective is to maximize revenue. Prior to this work, the only auctions known to be approximately optimal in the worst case employed randomization. Our main result is the existence of deterministic auctions that approximately match the performance guarantees of these randomized auctions. We give a fairly general derandomization technique for turning any randomized mechanism into an asymmetric deterministic one with approximately the same revenue. In doing so, we bypass the impossibility result for symmetric deterministic auctions and show that asymmetry is nearly as powerful as randomization for solving optimal mechanism design problems. Our general construction involves solving an exponential-sized flow problem and thus is not polynomial-time computable. To complete the picture, we give an explicit polynomial-time construction for derandomizing a specific auction with good worst-case revenue. Our results are based on toy problems that have a flavor similar to the hat problem from [3].

Original languageEnglish (US)
Pages (from-to)619-625
Number of pages7
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Dec 1 2005
Event13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States
Duration: Nov 7 2005Nov 11 2005

Keywords

  • Auctions
  • Derandomization
  • Mechanism design

ASJC Scopus subject areas

  • Software

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

  • Cite this