The Cost of Impatience in Dynamic Matching: Scaling Laws and Operating Regimes

References

• Adan I, Kleiner I, Righter R, Weiss G (2018) FCFS parallel service systems and matching models. Performance Evaluation 127–128:253–272.Crossref, Google Scholar
• Afèche P, Caldentey R, Gupta V (2022) On the optimal design of a bipartite matching queueing system. Oper. Res. 70(1):363–401.Link, Google Scholar
• Afèche P, Diamant A, Milner J (2014) Double-sided batch queues with abandonment: Modeling crossing networks. Oper. Res. 62(5):1179–1201.Link, Google Scholar
• Allon G, Van Mieghem JA (2010) Global dual sourcing: Tailored base-surge allocation to near-and offshore production. Management Sci. 56(1):110–124.Link, Google Scholar
• Aouad A, Saritaç Ö (2022) Dynamic stochastic matching under limited time. Oper. Res. 70(4):2349–2383.Link, Google Scholar
• Ashlagi I, Bingaman A, Burq M, Manshadi V, Gamarnik D, Murphey C, Roth AE, Melcher ML, Rees MA (2018) Effect of match-run frequencies on the number of transplants and waiting times in kidney exchange. Amer. J. Transplantation 18(5):1177–1186.Crossref, Google Scholar
• Atar R (2005) Scheduling control for queueing systems with many servers: Asymptotic optimality in heavy traffic. Ann. Appl. Probab. 15(4):2606–2650.Crossref, Google Scholar
• Atar R, Gurvich I (2014) Scheduling parallel servers in the nondegenerate slowdown diffusion regime: Asymptotic optimality results. Ann. Appl. Probab. 24(2):760–810.Crossref, Google Scholar
• Aveklouris A, DeValve L, Stock M, Ward A (2024) Matching impatient and heterogeneous demand and supply. Oper. Res., ePub ahead of print May 15, https://doi.org/10.1287/opre.2022.0005.Google Scholar
• Bar-Lev SK, Boxma O, Mathijsen B, Perry D (2017) A blood bank model with perishable blood and demand impatience. Stochastic Systems 7(2):237–263.Link, Google Scholar
• Borst S, Mandelbaum A, Reiman MI (2004) Dimensioning large call centers. Oper. Res. 52(1):17–34.Link, Google Scholar
• Boxma OJ, David I, Perry D, Stadje W (2011) A new look at organ transplantation models and double matching queues. Probab. Engrg. Inform. Sci. 25(2):135–155.Crossref, Google Scholar
• Büke B, Chen H (2017) Fluid and diffusion approximations of probabilistic matching systems. Queueing Systems 86:1–33.Crossref, Google Scholar
• Caldentey R, Kaplan EH, Weiss G (2009) FCFS infinite bipartite matching of servers and customers. Advances Appl. Probab. 41(3):695–730.Crossref, Google Scholar
• Castro F, Nazerzadeh H, Yan C (2020a) Matching queues with reneging: A product form solution. Queueing Systems 96(3–4):359–385.Crossref, Google Scholar
• Castro F, Frazier P, Ma H, Nazerzadeh H, Yan C (2020b) Matching queues, flexibility and incentives. Preprint, submitted July 17, http://dx.doi.org/10.2139/ssrn.3627920.Google Scholar
• Chen Y, Hu M (2020) Pricing and matching with forward-looking buyers and sellers. Manufacturing Service Oper. Management 22(4):717–734.Link, Google Scholar
• Collina N, Immorlica N, Leyton-Brown K, Lucier B, Newman N (2020) Dynamic weighted matching with heterogeneous arrival and departure rates. Chen X, Gravin N, Hoefer M, Mehta R, eds. Web and Internet Economics. WINE 2020, Lecture Notes in Computer Science, vol. 12495 (Springer, Cham, Switzerland).Crossref, Google Scholar
• Conolly B, Parthasarathy P, Selvaraju N (2002) Double-ended queues with impatience. Comput. Oper. Res. 29(14):2053–2072.Crossref, Google Scholar
• Diamant A, Baron O (2019) Double-sided matching queues: Priority and impatient customers. Oper. Res. Lett. 47(3):219–224.Crossref, Google Scholar
• Elalouf A, Perlman Y, Yechiali U (2018) A double-ended queueing model for dynamic allocation of live organs based on a best-fit criterion. Appl. Math. Modeling 60:179–191.Crossref, Google Scholar
• Graves SC (1982) The application of queueing theory to continuous perishable inventory systems. Management Sci. 28(4):400–406.Link, Google Scholar
• Gurvich I, Ward A (2014) On the dynamic control of matching queues. Stochastic Systems 4(2):479–523.Link, Google Scholar
• Kaplan EH (1986) Tenant assignment models. Oper. Res. 34(6):832–843.Link, Google Scholar
• Kashyap BRK (1966) The double-ended queue with bulk service and limited waiting space. Oper. Res. 14(5):822–834.Link, Google Scholar
• Kendall DG (1951) Some problems in the theory of queues. J. Royal Statist. Soc. Ser. B Methodological 13(2):151–173.Crossref, Google Scholar
• Kerimov S, Ashlagi I, Gurvich I (2021) Dynamic matching: Characterizing and achieving constant regret. Management Sci. 70(5):2799–2822.Link, Google Scholar
• Kerimov S, Ashlagi I, Gurvich I (2023) On the optimality of greedy policies in dynamic matching. Oper. Res., ePub ahead of print September 12, https://doi.org/10.1287/opre.2021.0596.Link, Google Scholar
• Lee C, Ward AR (2019) Pricing and capacity sizing of a service facility: Customer abandonment effects. Prod. Oper. Management 28(8):2031–2043.Crossref, Google Scholar
• Liu X, Gong Q, Kulkarni VG (2015) Diffusion models for double-ended queues with renewal arrival processes. Stochastic Systems 5(1):1–61.Link, Google Scholar
• Nguyen LM, Stolyar AL (2018) A queueing system with on-demand servers: Local stability of fluid limits. Queueing Systems 89:243–268.Crossref, Google Scholar
• Özkan E, Ward AR (2020) Dynamic matching for real-time ride sharing. Stochastic Systems 10(1):29–70.Link, Google Scholar
• Pang G, Talreja R, Whitt W (2007) Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probab. Surveys 4:193–267.Crossref, Google Scholar
• Perry D, Stadje W (1999) Perishable inventory systems with impatient demands. Math. Methods Oper. Res. 50(1):77–79.Crossref, Google Scholar
• Prendergast C (2017) How food banks use markets to feed the poor. J. Econom. Perspect. 31(4):145–162.Crossref, Google Scholar
• Varma SM, Maguluri ST (2021) A heavy traffic theory of two-sided queues. Performance Evaluation Rev. 49(3):43–44.Crossref, Google Scholar
• Varma SM, Bumpensanti P, Maguluri ST, Wang H (2022) Dynamic pricing and matching for two-sided queues. Oper. Res. 71(1):83–100.Link, Google Scholar
• Vaze R, Nair J (2022) Non-asymptotic near optimal algorithms for two sided matchings. 2022 20th Internat. Sympos. Modeling Optim. Mobile Ad hoc Wireless Networks (WiOpt) (IEEE, Piscataway, NJ), 17–24.Google Scholar
• Wang G, Zhang H, Zhang J (2022) On-demand ride-matching in a spatial model with abandonment and cancellation. Oper. Res. 72(3):1278–1297.Link, Google Scholar
• Ward AR (2012) Asymptotic analysis of queueing systems with reneging: A survey of results for FIFO, single class models. Surveys Oper. Res. Management Sci. 17(1):1–14.Crossref, Google Scholar
• Ward AR, Glynn PW (2003) A diffusion approximation for a Markovian queue with reneging. Queueing Systems 43(1):103–128.Crossref, Google Scholar
• Yu Q, Zhang Y, Zhou YP (2022) Delay information in virtual queues: A large-scale field experiment on a major ride-sharing platform. Management Sci. 68(8):5745–5757.Link, Google Scholar
• Zenios SA (1999) Modeling the transplant waiting list: A queueing model with reneging. Queueing Systems 31:239–251.Crossref, Google Scholar
• Zubeldia M, Jhunjhunwala PR, Maguluri ST (2022) Matching queues with abandonments in quantum switches: Stability and throughput analysis. Preprint, submitted September 25, https://arxiv.org/abs/2209.12324.Google Scholar