Dynamic Bipartite Matching Markets with Stochastic Arrivals and Departures

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.