TITLE: Online Resource Allocation
Algorithmic mechanism design deals with the optimization of economic systems where many parties with conflicting objectives compete for possession of resources. Insights from this area play an increasingly important role in the design of new electronic marketplaces such as online advertising, the cloud market, rideshare industry, crowdsourcing marketplaces, etc. These new marketplaces display rich combinatorial structure as well as a previously unseen scale of microtransactions necessitating an algorithmic approach towards designing solutions. A fundamental objective in these settings is to partition a set of resources among multiple participants so that the collective happiness of all participants, a.k.a. social welfare, is maximized. This classical objective from economics is very well understood in “one-shot” settings. In this talk we consider the online version of the problem, where participants arrive one by one and grab resources. I will describe some recent work showing that simple pricings can achieve near-optimal solutions to this problem. This talk is based on joint work with Nikhil Devanur, Alexander Holroyd, Anna Karlin, James Martin, J. Benjamin Miller, Balasubramanian Sivan, and Yifeng Teng.
Shuchi Chawla received a B.Tech. in computer science from the Indian Institute of Technology, Delhi, and a Ph.D. in computer science from Carnegie Mellon University. After postdocs at Stanford University and Microsoft Research Silicon Valley, she joined the University of Wisconsin-Madison, where she is now professor of computer sciences. Chawla’s research interests include the design and analysis of approximation algorithms, online algorithms, algorithmic game theory and mechanism design, and combinatorial and stochastic optimization. Shuchi is the recipient of an NSF Career award, a Sloan Foundation fellowship, UW-Madison’s Carolyn Rosner Award in Teaching, and Chancellor’s Teaching Innovation Award. She currently serves on the editorial boards of the ACM Transactions on Algorithms and the ACM Transactions on Economics and Computation. She is an elected member of the ACM SIGACT executive committee and currently serves as chair of the SIGACT Committee for the Advancement of Theoretical Computer Science.