AF: Small: Matching in Dynamic Environments

Stanford University, Stanford CA

Investigators

Abstract

The project aims to develop new models and algorithms for online stochastic problems arising in matching markets. The underlying models and algorithms are inspired by and applicable to marketplaces used for the online allocation of goods and services, including online retail markets, ad auctions, ride-hailing, ride-sharing applications, and short-term housing markets. These markets occupy a rapidly increasing fraction of the economy, and their massive size necessitates efficient and scalable algorithms that can match demand and supply in real-time. Decision-making in an uncertain, dynamic environment influenced by one's decisions is universal across various applications and is studied in multiple disciplines, including computer science, economics, statistics, and operations research. The project aims to characterize the complexity of multistage stochastic optimization problems and the tractability of finding approximately optimal decisions for them. This is in contrast to competitive analysis, a popular framework in algorithm design that characterizes the worst-case performance of an online algorithm compared to optimum in hindsight. The project employs a range of techniques including stronger linear programming relaxations, specifically a hierarchy of linear programs, to capture the optimum online. This effort is complemented by a study of the hardness of approximation and specifically PSPACE-hardness results. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.