[Colloq] Hiring Talk, Monday, March 12, 10:30am - Nicole Immorlica

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents a Hiring Talk By:
Nicole Immorlica
Microsoft Research

Who will speak on:
Algorithmic Game Theory with Applications to Online Auctions

Monday, March 12, 2007
10:30 am
366 West Village H
Northeastern University

Abstract:
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.

Bio:
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.

Host: Professor Jay Aslam