Mika Sumida — Network Revenue Management with Performance Guarantees: An Approximate Dynamic Programming Approach
January 24 @ 11:00 am - 12:30 pm
Abstract: In network revenue management problems, we have a collection of resources with limited capacities to satisfy the requests for products arriving randomly over time. If we accept a request for a product, then we generate a product-specific revenue and consume the capacities of a combination of resources used by that product. The goal is to maximize the total expected revenue from the accepted product requests. Dynamic programming formulations to compute the optimal policy suffer from the curse of dimensionality. Instead, we provide an approximate policy with a performance guarantee. Our approximate policy is based on constructing approximations to the value functions by using a linear combination of basis functions. If each product uses at most L resources, then the total expected revenue obtained by our approximate policy is at least 1/(1+L) of the optimal total expected revenue. In many network revenue management settings, although the total number of resources and products can become large, the number of resources used by a product remains bounded. In this case, our approximate policy provides a constant-factor performance guarantee. We extend our work to the case with reusable products, where a product can be used multiple times by different customers, but each product uses a single resource. These problems are applicable to emerging sharing economy industries that focus on renting out computing capacity, fashion items, and physical storage space. We develop an approximate policy that is guaranteed to obtain at least 50% of the optimal expected revenue. Using parking transaction data from the city of Seattle, we conduct a large-scale computational experiment to test our policy in order to understand the value of dynamic pricing for metered street parking. This is based on joint work with Yuhang Ma, Paat Rusmevichientong, and Huseyin Topaloglu.
Bio: Mika Sumida is a Ph.D. Candidate in the School of Operations Research and Information Engineering at Cornell University where she is advised by Huseyin Topaloglu. Her research focuses on developing efficient, provably-good policies for revenue management and resource allocation problems. She is particularly interested in applications in online marketplaces and the sharing economy. She graduated from Yale University with a B.A. in mathematics and spent the following two years working in operations and management consulting. She is a recipient of an NSF Graduate Research Fellowship.