Derandomizing Auctions

We study the problem of designing seller optimal auctions. Prior to this work, the only previously known auctions that are approximately optimal in worst case employ randomization. Our main result is the existence of deterministic auctions that approximately match the performance guarantees of these randomized auction. We give a fairly general derandomization technique for turning a randomized mechanism into an asymmetric deterministic one with approximately the same properties. In doing so, we bypass an impossibility result for symmetric deterministric aucyions by using asymmetry, i.e., the order in which bids appear in the input.

Our derandominazion technique uses an auxillary graph of exponential size and takes exponential time even if the corresponding randomized auction is polynomial time. We leave as an open question the existence of a polynomial-time computable deterministic auction that is approximately optimal.

Our work shows an interesting relationship between mechanism design and several areas of computer science, including competitive algorithms, computational learning, and coding theory.

Joint work with Gagan Aggarwal, Amos Fiat, Nicole Immorica, Jason Jason Hartline, and Madu Sudan.