Two-sided Queues and Networked Matching Platforms

双边队列和网络化撮合平台

• 批准号: 2140534
• 负责人: Siva Theja Maguluri
• 金额: $ 37.65万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-06-01 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2140534&HistoricalAwards=false
• 关键词: Two; sided; Queues; Networked; Matching

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.

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