Richard M. Karp Distinguished Lecture — Pandora’s Box: Learning to Leverage Costly Information

Many decision-making settings exhibit a trade-off between obtaining extra information to improve the outcome of the process and the cost of obtaining such information. The Pandora’s box problem of Weitzman (1979) is a classical model formalizing this trade-off. The algorithm is presented with a number of boxes containing unknown (stochastic) rewards, and it can select and keep one of the rewards. Boxes can be opened at a fixed cost to reveal their rewards. The problem is to determine which boxes to open, in what order, and which reward to choose, so as to maximize the reward obtained minus the costs paid. Weitzman presented a simple and elegant index-based policy for solving this problem under certain assumptions. In this talk, Shuchi Chawla will examine settings where Weitzman’s assumptions do not hold and his approach fails. She will focus, in particular, on settings where the rewards in boxes are correlated, and will present different ways of formalizing and attacking the problem. En route, she will examine issues that often arise in online decision-making, such as the trade-off between learning and optimization and benchmark choice. 

===================================================================

Shuchi Chawla holds an endowed professorship in computer science at the University of Texas at Austin and is an Amazon Scholar. Shuchi is a theoretical computer scientist specializing in the areas of algorithm design, and economics and computation. Prior to joining UT Austin, she spent 15 years as a professor of CS at the University of Wisconsin-Madison. She has also previously held visiting positions at the University of Washington and Microsoft Research. Chawla has received several awards for her research and teaching, including a Sloan fellowship and the Chancellor’s Teaching Innovation Award at UW-Madison. She recently served as the PC chair of SODA20 and PC co-chair of EC’21, and currently serves on the editorial boards of ACM Transactions on Algorithms and ACM Transactions on Economics and Computation.

The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science, and is geared toward a broad scientific audience. Light refreshments will be available prior to the start of the lecture. This lecture will be viewable thereafter on this page and on our YouTube channel.

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials.