Abstract
Motivated by a service platform, we study a two-sided network where heterogeneous demand (customers) and heterogeneous supply (workers) arrive randomly over time to get matched. Customers and workers arrive with a randomly sampled patience time (also known as reneging time in the literature) and are lost if forced to wait longer than that time to be matched. The system dynamics depend on the matching policy, which determines when to match a particular customer class with a particular worker class. Matches between classes use the head-of-line customer and worker from each class. Since customer and worker arrival processes can be very general counting processes, and the reneging times can be sampled from any finite mean distribution that is absolutely continuous, the state descriptor must track the age-in-system for every customer and worker waiting in order to be Markovian, as well as the time elapsed since the last arrival for every class. We develop a measure-valued fluid model that approximates the evolution of the discrete-event stochastic matching model and prove its solution is unique under a fixed matching policy. For a sequence of matching models, we establish a tightness result for the associated sequence of fluid-scaled state descriptors and show that any distributional limit point is a fluid model solution almost surely. When arrival rates are constant, we characterize the invariant states of the fluid model solution and show convergence to these invariant states as time becomes large. Finally, again when arrival rates are constant, we establish another tightness result for the sequence of fluid-scaled state descriptors distributed according to a stationary distribution and show that any subsequence converges to an invariant state. As a consequence, the fluid and time limits can be interchanged, which justifies regarding invariant states as first order approximations to stationary distributions.
Similar content being viewed by others
References
Afèche, P., Diamont, A., Milner, J.: Double-sided batch queues with abandonments: modeling crossing networks. Probab. Eng. Inf. Sci. 25(2), 135–155 (2011)
Agarwal, P., Ramanan, K.: Invariant states of hydrodynamic limits of randomized load balancing networks. arXiv:2008.08510 (2020)
Aghajani, R., Ramanan, K.: The hydrodynamic limit of a randomized load balancing network. Ann. Appl. Probab. 29(4), 2114–2174 (2019)
Arnosti, N., Johari, R., Kanoria, Y.: Managing congestion in matching markets. Manufact. Serv. Oper. Manag. 23(3), 620–636 (2021)
Atar, R., Kaspi, H., Shimkin, N.: Fluid limits for many-server systems with reneging under a priority policy. Math. Oper. Res. 39(3), 672–696 (2014)
Aveklouris, A., DeValve, L., Ward, A.R.: Matching impatient and heterogeneous demand and supply. arXiv:2102.02710 (2021)
Banerjee, S., Budhiraja, A., Puha, A.L.: Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributions. Ann. Appl. Probab. 32(4), 2587–2651 (2022)
Banerjee, S., Kanoria, Y., Qian, P.: State dependent control of closed queueing networks with application to ride-hailing. arXiv:1803.04959 (2018)
Benjaafar, S., Hu, M.: Operations management in the age of the sharing economy: what is old and what is new? Manufact. Serv. Oper. Manag. 22(1), 93–101 (2020)
Billingsley, P.: Probability and Measure. Wiley Series in Probability and Mathematical Statistics, 3rd edn. Wiley, New York (1995)
Billingsley, P.: Convergence of Probability Measures, 2nd edn. Wiley, New York (1999)
Blanchet, J.H., Reiman, M.I., Shah, V., Wein, L.M., Wu, L.: Asymptotically optimal control of a centralized dynamic matching market with general utilities. Oper. Res. 70(6), 3355–3370 (2022)
Boxma, O.J., David, I., Perry, D., Stadje, W.: A new look at organ transplantation models and double matching queues. Probab. Eng. Inf. Sci. 25(2), 135–155 (2011)
Büke, B., Chen, H.: Fluid and diffusion approximations of probabilistic matching systems. Queueing Syst. 86(1–2), 1–33 (2017)
Castro, F., Nazerzadeh, H., Yan, C.: Matching queues with reneging: a product form solution. Queueing Syst. 96(3–4), 359–385 (2020)
Chen, Y.-J., Dai, T., Korpeoglu, C.G., Körpeoğlu, E., Sahin, O., Tang, C.S., Xiao, S.: OM forum-innovative online platforms: research opportunities. Manufact. Serv. Oper. Manag. 22(3), 430–445 (2020)
Da Prato, G., Zabczyk, J., Zabczyk, J.: Ergodicity for infinite dimensional systems, vol. 229. Cambridge University Press, Cambridge (1996)
Ding, Y., McCormick, S.T., Nagarajan, M.: A fluid model for one-sided bipartite matching queues with match-dependent rewards. Oper. Res. 69(4), 1256–1281 (2021)
Down, D., Gromoll, H.C., Puha, A.L.: Fluid limits for shortest remaining processing time queues. Math. Oper. Res. 34, 880–911 (2009)
Ethier, S.N., Kurtz, T.G.: Markov Processes: Characterization and Convergence. Wiley, New York (1986)
Gromoll, C., Robert, P., Zwart, B.: Fluid limits for processor-sharing queues with impatience. Math. Oper. Res. 33(2), 375–402 (2008)
Gromoll, C., Williams, R.: Fluid limits for networks with bandwidth sharing and general document size distributions. Ann. Appl. Probab. 19(1), 243–280 (2009)
Gromoll, H.C., Kruk, L., Puha, A.L.: The diffusion limit of an SRPT queue. Stoch. Syst. 1, 1–16 (2011)
Hu, M. (ed.): Sharing Economy: Making Supply Meet Demand. Springer Series in Supply Chain Management (2019)
Hu, M.: From the classics to new tunes: a neoclassical view on sharing economy and innovative marketplaces. Prod. Oper. Manag. 30(6), 1668–1685 (2021)
Jakubowski, A.: On the Skorokhod topology. Ann. Inst. H. Poincare Probab. Stat. 22(3), 263–285 (1986)
Jonckheere, M., Moyal, P., Ramírez, C., Soprano-Loto, N.: Generalized max-weight policies in stochastic matching. Stoch. Syst. 13(1), 40–58 (2023)
Kang, W.: Fluid limits of many-server retrial queues with nonpersistent customers. Queueing Syst. 79(2), 183–219 (2015)
Kang, W., Ramanan, K.: Fluid limits of many-server queues with reneging. Ann. Appl. Probab. 20(6), 2204–2260 (2010)
Kang, W., Ramanan, K.: Asymptotic approximations for stationary distributions of many-server queues with abandonment. Ann. Appl. Probab. 22(2), 477–521 (2012)
Kanoria, Y., Saban, D.: Facilitating the search for partners on matching platforms. Manag. Sci. 67(10), 5990–6029 (2021)
Kaspi, H., Ramanan, K.: Law of large numbers limits for many-server queues. Ann. Appl. Probab. 21(1), 33–114 (2011)
Khademi, A., Liu, X.: Asymptotically optimal allocation policies for transplant queueing systems. SIAM J. Appl. Math. 81(3), 1116–1140 (2021)
Kohlenberg, A., Gurvich, I.: The cost of impatience in dynamic matching: scaling laws and operating regimes, (2023). Available at SSRN 4453900
Limic, V.: A LIFO queue in heavy traffic. Ann. Appl. Probab. 11(2), 301–331 (2001)
Liu, X.: Diffusion models for double-ended queues with reneging in heavy traffic. Queueing Syst. 91(1–2), 49–87 (2019)
Liu, Y., Whitt, W.: A network of time-varying many-server fluid queues with customer abandonment. Oper. Res. 59(4), 835–846 (2011)
Mandelbaum, A., Momčilović, P.: Personalized queues: the customer view, via a fluid model of serving least-patient first. Queueing Syst. 87(1), 23–53 (2017)
Masanet, T., Moyal, P.: Perfect sampling of stochastic matching models with reneging. arXiv:2202.09341 (2022)
Özkan, E.: Joint pricing and matching in ride-sharing systems. Eur. J. Oper. Res. 287(3), 1149–1160 (2020)
Özkan, E., Ward, A.R.: Dynamic matching for real-time ride sharing. Stoch. Syst. 10(1), 29–70 (2020)
Puha, A.L.: Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling. Ann. Appl. Probab. 25, 3381–3404 (2015)
Puha, A.L., Ward, A.R.: Fluid limits for multiclass many-server queues with general reneging distributions and head-of-the-line scheduling. Math. Oper. Res. 47(2), 1192–1228 (2021)
Puha, A.L., Williams, R.J.: Asymptotic behavior of a critical fluid model for a processor sharing queue via relative entropy. Stoch. Syst. 6(2), 251–300 (2016)
Remerova, M., Reed, J., Zwart, B.: Fluid limits for bandwidth-sharing networks with rate constraints. Math. Oper. Res. 39(3), 746–774 (2014)
Zenios, S.A.: Modeling the transplant waiting list: a queueing model with reneging. Queueing Syst. 31(3–4), 239–251 (1999)
Zhang, J.: Fluid models of many-server queues with abandonment. Queueing Syst. 73(2), 147–193 (2013)
Zhang, J., Dai, J., Zwart, B.: Law of large number limits of limited processor-sharing queues. Math. Oper. Res. 34(4), 937–970 (2009)
Zhong, Y., Puha, A.L., Ward, A.R.: Asymptotically optimal idling in the \(\text{ GI }/\text{GI }/ n +\text{ GI } \) queue. Oper. Res. Lett. 50(3), 362–369 (2022)
Zubeldia, M., Jhunjhunwala, P.J., Maguluri, S.T.: Matching queues with abandonments in quantum switches: stability and throughput analysis. arXiv:2209.12324 (2022)
Zuñiga, A.W.: Fluid limits of many-server queues with abandonments, general service and continuous patience time distributions. Stoch, Process. Their Appl. 124(3), 1436–1468 (2014)
Acknowledgements
We would like to thank Levi DeValve for helpful discussion related to the use of the fluid model invariant states to formulate and solve a matching policy optimization problem, which resulted in the paper [6]. Financial support from the University of Chicago Booth School of Business is gratefully acknowledged.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Aveklouris, A., Puha, A.L. & Ward, A.R. A fluid approximation for a matching model with general reneging distributions. Queueing Syst 106, 199–238 (2024). https://doi.org/10.1007/s11134-023-09892-w
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-023-09892-w
Keywords
- Service platforms
- Two-sided platform
- Reneging
- Fluid approximation
- Functional limit theorems
- Measure-valued process