AF: Small: Matching in Dynamic Environments

该项目旨在为配对市场中出现的在线随机问题开发新的模型和算法。基础模型和算法的灵感来自于并适用于用于在线分配商品和服务的市场，包括在线零售市场、广告拍卖、叫车、拼车应用和短期住房市场。这些市场在经济中占据着迅速增长的份额，它们的巨大规模要求高效且可扩展的算法能够实时匹配需求和供应。在不确定的、动态的环境中，受个人决策的影响，决策在各种应用中是普遍的，并在多个学科中进行研究，包括计算机科学、经济学、统计学和运筹学。该项目旨在刻画多阶段随机优化问题的复杂性，以及为它们找到近似最优决策的易操作性。这与竞争分析形成对比，竞争分析是算法设计中的一个流行框架，其特征是在线算法的最差性能与事后最优的性能相比。该项目采用了一系列技术，包括更强的线性规划松弛，特别是线性规划的层次结构，以在线获取最优。这一努力得到了对近似难度，特别是PSPACE-硬度结果的研究的补充。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.