AF: Small: Matching in Dynamic Environments

该项目旨在为匹配市场中出现的在线随机问题开发新的模型和算法。底层模型和算法受到用于在线分配商品和服务的市场的启发，并适用于这些市场，包括在线零售市场、广告拍卖、网约车、拼车应用和短期住房市场。这些市场在经济中所占的比例迅速增加，其庞大的规模需要有效和可扩展的算法，可以实时匹配需求和供应。在一个不确定的、动态的环境中，决策受到一个人的决策的影响，这在各种应用中是普遍的，并且在多个学科中进行研究，包括计算机科学、经济学、统计学和运筹学。该项目旨在描述多阶段随机优化问题的复杂性和为它们找到近似最优决策的可追踪性。这与竞争分析形成对比，竞争分析是算法设计中的一种流行框架，它将在线算法的最坏情况性能与后见之明的最佳性能进行比较。该项目采用了一系列技术，包括更强的线性规划松弛，特别是线性规划的层次结构，以获取最佳在线。这项工作是通过研究近似硬度，特别是pspace硬度结果来补充的。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.