Since its inception in the 1980s, the popularity of the Internet has been growing exponentially, resulting in a mass of shared knowledge and fast, cheap communication. Hand-in-hand with these developments, we have seen the birth of a plethora of new systems for facilitating interaction among economic agents from marketplaces like eBay and Google’s AdWords to online networking services like MySpace and Match.com. These systems give rise to numerous opportunities for scientific exploration, and such studies are fundamental to the future economic and social success of these systems.
Algorithmic game theory is a new paradigm for studying such systems. The goal in this field is to understand the behavior of autonomous selfish agents, and to define rules that encourage them to 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 some basic notions of algorithmic game theory and survey some important applications of the field. I will then proceed to showcase some techniques from this field through the problem of online auction design, or auctions for bidders who arrive and depart over time (e.g. Priceline.com). Maximizing welfare in such auctions is complicated by the fact that bids must be accepted or rejected at the moment they are submitted. It is known how the classic secretary problem introduced by Dynkin in 1963 can be used to design approximately welfare-maximizing auctions in a simple multi-unit auction setting. We show how the classic secretary problem can be generalized to a combinatorial setting where acceptable sets form a matroid, and use this generalization to build mechanisms for a class of online combinatorial auctions.
Parts of this talk are based on joint work with Moshe Babaioff and Robert Kleinberg.
Speaker Biography
Nicole Immorlica received her Ph.D. in June 2005 from MIT and has since been a postdoctoral researcher at the Theory Group in Microsoft Research. Her research interests lie in applying techniques from the field of theoretical computer science to problems at the forefront of economics and computer science. Her recent research has focused on auction design, particularly sponsored search auctions; matching markets such as the National Residency Matching Program (NRMP); and the formation and diffusion of information in social networks.