Computing with Selfish Agents


January 28, 2005


Nicole Immorlica




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.


Nicole Immorlica

Nicole Immorlica is an assistant professor in the theoretical computer science group at Northwestern University. She joined Northwestern in September 2008 after postdoctoral positions at Microsoft Research in Redmond, WA, and Centruum voor Wiskunde en Informatica (CWI) in Amsterdam, Netherlands. She received her Ph.D. from MIT 2005. Her work focuses on applying economic and computer science techniques to problems at the forefront of computer science research, including models of diffusion on social networks, the design and analysis of ad auction markets, and the development of general auction mechanisms.