Two-sided Queues and Networked Matching Platforms

依靠为客户和服务牵线搭桥的在线市场已成为美国经济的重要组成部分。这些匹配平台严重依赖算法来快速高效地匹配可用供需，两者都是随着时间的推移随机到达的。该奖项通过提出联网匹配平台的基本理论来为国家的经济繁荣做出贡献，该理论能够支持在这些环境中分配稀缺资源的决策，并特别强调现代在线支付渠道网络和隐私保护通信中出现的量子比特匹配问题。该奖项有助于研究生和本科生的教育和培训，以及在当地高中开展外联活动，以扩大STEM的兴趣。结果将通过出版物、纳入课程和为研究界提供的教程来传播。该项目将为双向队列和两方匹配平台开发大流量理论，其中要匹配的实体涉及网络。与经典排队不同的是，在繁忙的交通中，双边排队表现出相变。这一行为的条件和过渡的收敛速度将被描述。该项目超越了简单的单一服务器-客户两方范式，进一步考虑了网络匹配平台，例如那些出现在支付渠道网络中的平台，将单个双边队列的结果推广到通过网络连接的容量有限的双边队列的情况。这一理论将被用来为支付渠道网络开发实用的路由算法，并将在公开可用的数据集上进行评估。最后，该项目将研究在量子交换机中出现的物理网络匹配平台，该平台采用了非常通用的基于超图的匹配平台。该项目将开发分析工具来研究这些平台，并使用它们来开发可证明是最优的匹配算法，这些算法将使用量子模拟器的痕迹进行评估。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Online marketplaces that rely on matching customers with services have become an important sector of the US economy. These matching platforms rely critically on algorithms to quickly and efficiently match available supply and demand, where both arrive randomly over time. This award contributes to the the Nation's economic prosperity by advancing a fundamental theory of networked matching platforms capable of supporting decisions regarding allocation of scarce resources in these environments, with particular emphasis on modern online payment channel networks and quantum bit-matching problems arising in privacy-preserving communications. The award contributes to the education and training of graduate and undergraduate students as well as to outreach activities at local high schools to broaden STEM interest. Results will be disseminated through publications, incorporation into curriculum, and tutorials for the research community. This project will develop heavy-traffic theory for two-sided queues and bipartite matching platforms where the entities to be matched involve networks. Unlike a classical queue, a two-sided queue exhibits a phase transition in heavy-traffic. Conditions for this behavior and the rate of convergence of the transition will be characterized. Going beyond the simple single server-customer bipartite paradigm, the project further considers networked matching platforms, such as those arising in payment channel networks, generalizing the results for a single two-sided queue to the case of capacitated two-sided queues connected through a network. This theory will be used to develop practical routing algorithms for payment channel networks that will be evaluated on publicly available data sets. Finally, the project will examine a physical networked matching platform that arises in a quantum switch employing a very general hypergraph-based matching platform. The project will develop analytical tools to study such platforms and use them to develop provably optimal matching algorithms that will be evaluated using traces from quantum simulators.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.