4/27/23 | 4:15pm | E25-111

Shuchi Chawla

Professor
University of Texas

Abstract: Multi-item mechanisms can be very complex offering many different bundles to the buyer that could even be randomized. Such complexity is thought to be necessary as the revenue gaps between randomized and deterministic mechanisms, or deterministic and simple mechanisms are huge even for simple classes of valuations. We challenge this conventional belief by showing that these large gaps can only happen in situations where buyers' actions are severely restricted. These are situations where the mechanism sells a bundle of items at a higher price than the sum of the prices of the constituent items and buyers wanting to purchase such a bundle must pay this premium as they are not allowed to purchase the constituents separately.

We accordingly propose a new class of mechanisms that we call buy-many mechanisms wherein the buyer is allowed to interact with the mechanism multiple times and purchase as many (randomized) bundles as he pleases. Most real-world mechanisms are buy-many. We show that optimal buy-many mechanisms satisfy many nice properties that general mechanisms do not: they are approximable by simple mechanisms; their revenue is a smooth function of the buyer's value distribution; and they have bounded description complexity.

Bio: Shuchi Chawla holds an Endowed Professorship in Computer Science at UT-Austin and is an Amazon Scholar. Shuchi is a theoretical computer scientist specializing in the areas of algorithm design, and economics and computation. Shuchi received a Ph.D. from Carnegie Mellon University and a B.Tech. from the Indian Institute of Technology, Delhi. 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. Shuchi is the recipient of an NSF Career award, a Sloan Foundation fellowship, and several awards for her research and teaching at UW-Madison. Shuchi recently served as the PC Chair of SODA'20 and EC'21, and currently serves on the editorial boards of the ACM Transactions on Algorithms and the ACM Transactions on Economics and Computation.