Title: Derandomization of Auctions

Speaker: Nicole Immorlica, MIT

Abstract: In this talk, I will discuss a framework introduced by Goldberg
et al. for maximizing revenue in auctions for a good of unlimited supply.
Earlier work of Goldberg et al. introduced randomized auction mechanisms
that, in the worst case, achieve close to the optimal revenue. We
investigate the feasibility of high revenue deterministic auctions.  In
the process, we give an exponential-space construction for converting any
randomized auction to a deterministic one with approximately the same
revenue properties.  We do so by first proving the existence of a
deterministic solution to a related problem, the "hat coloring problem",
in which everyone at a party attempts to guess the color of his own hat by
just observing the colors of his friends' hats. Our proof draws upon a
seemingly unrelated set of techniques from the literature on network
flows. We also present a polynomial-time deterministic construction of an
auction with good revenue properties, using parity arguments.  Our work
bypasses an impossibility result of Goldberg et al. for deterministic
symmetric auctions by introducing asymmetry into the allocation and
pricing scheme, suggesting that in this setting asymmetry is essentially
as powerful as randomness.

This talk is based on joint work with Gaggan Aggarwal, Amos Fiat, Andrew
Goldberg, Jason Hartline, and Madhu Sudan