Many complex systems of our day involve autonomous participants who act in their own self-interest and therefore might lie if it benefits them to do so. The goal in the field of mechanism design is to define rules in the system such that participants acting in their own self-interest will collectively act in a way that optimizes some system objective such as social welfare or revenue. In this talk, I will first present an overview of the basic notions mechanism design and survey some of my recent results in the field.
The focus of the talk will be based on 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.