Abstract
A classical problem in economics is to partition a set of resources among multiple agents so that the collective happiness of all agents, a.k.a. social welfare, is maximized. In this talk we consider the online Bayesian version of this problem from an algorithmic perspective: agents arrive online, but their values for different allocations are drawn from known independent distributions. I will survey some recent results on this problem, including its connection to prophet inequalities from optimal stopping theory. A surprising implication of these results is that in many cases of interest, simple static-pricing based allocation mechanisms are near optimal within the class of all online algorithms.
This talk is based on joint work with Nikhil Devanur, Alexander Holroyd, Anna Karlin, James Martin, J. Benjamin Miller, Balasubramanian Sivan, and Yifeng Teng.
Bio
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. Shuchi’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 and a Sloan Foundation fellowship. She currently serves on the editorial boards of the SIAM Journal on Discrete Mathematics, 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.
APPROX CONFERENCE 