Derandomization of auctions

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

Games and Economic Behavior, 2011, vol. 72, issue 1, 1-11

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.

Keywords: Auctions; Randomization; Prior-free; Hat; puzzles (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899-8256(10)00128-4
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:72:y:2011:i:1:p:1-11

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().