Two-sided Queues and Networked Matching Platforms

点击翻译按钮获取中文摘要

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.