Dynamic Bipartite Matching Markets with Stochastic Arrivals and Departures

• 成果类型: Article; Early Access
• 署名作者: Kakimura, Naonori; Zhu, Donghao
• 署名单位: Keio University; University of Tsukuba
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2023.0333
• 发表日期: 2026-05-28
• 关键词: bipartite matching market; dynamic model; Markov chain; online algorithm

摘要

We study a dynamic bipartite matching market model where agents arrive and depart randomly through Poisson processes. Our proposed mechanisms are for minimizing unmatched agents by determining whom and when to match. Our main contribution is establishing performance bounds for different local mechanisms with varying timing strategies. We find that the Patient algorithm, which delays matching to increase market thickness, outperforms the Greedy algorithm by an exponential factor. Notably, the Patient algorithm requires the planner to identify departing agents, making it an optimal algorithm. Without this requirement, the Greedy algorithm is nearly optimal. We also examine a one-sided market, such as labor or freight exchange markets, where only one side can make decisions. In this scenario, we show that the Greedy and Patient algorithms have similar performance, suggesting that delaying matching time may not be advantageous. This finding contrasts with the bipartite and nonbipartite cases explored in recent literature.