Dynamic Bipartite Matching Markets with Stochastic Arrivals and Departures
Mathematics of Operations Research · 28.05.2026
DOI: 10.1287/moor.2023.0333 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics of Operations Research, online erschienen am 28.05.2026. Verfasst von Naonori Kakimura und 1 weiteren Autor:innen. Die Arbeit nennt 42 Literaturangaben.
Abstract (Originalsprache)
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. Funding: This work was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) [Grant GRK2201/277991500], by a JSPS Grant-in-Aid for Transformative Research Areas (A) [Grant 22H05106], by JSPS KAKENHI [Grants JP22H05001 and JP23K21646], and by JST ERATO [Grant JPMJER2301]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2023.0333 .
Zitieren
APA
Kakimura, N., & Zhu, D. (2026). Dynamic Bipartite Matching Markets with Stochastic Arrivals and Departures. Mathematics of Operations Research. https://doi.org/10.1287/moor.2023.0333
Vancouver
Kakimura N, Zhu D. Dynamic Bipartite Matching Markets with Stochastic Arrivals and Departures. Mathematics of Operations Research. 2026. doi:10.1287/moor.2023.0333
BibTeX
@article{Kakimura2026,
author = {Kakimura, Naonori and Zhu, Donghao},
title = {Dynamic Bipartite Matching Markets with Stochastic Arrivals and Departures},
journal = {Mathematics of Operations Research},
year = {2026},
doi = {10.1287/moor.2023.0333}
}
EUVIMED