Answers are grounded in this paper and cite their sources.
Examines matching strategies in dynamic bipartite markets, suggesting optimal algorithms for minimizing unmatched agents.
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 .
No takes yet. Share an insight, caveat, or question.
Kakimura et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: