Dynamic control of stochastic matching systems in heavy traffic: An effective computational method for high-dimensional problems

Abstract

Bipartite matching systems arise in many settings where agents or tasks from two distinct sets must be paired dynamically under compatibility constraints. We consider a high-dimensional bipartite matching system under uncertainty and seek an effective dynamic control policy that maximizes the expected discounted total value generated by the matches minus the congestion-related costs. To derive a tractable approximation, we focus attention on balanced, high-volume systems, i.e., the heavy-traffic regime, and derive an approximating Brownian control problem. We then develop a computational method that relies on deep neural network technology for solving this problem. To show the effectiveness of the policy derived from our computational method, we compare it to the benchmark policies available in the extant literature in the context of the original matching problem. In the test problems attempted thus far, our proposed policy outperforms the benchmarks, and its derivation is computationally feasible for dimensions up to 100 or more.