A Heavy Traffic Theory of Matching Queues

References

• [1] Adan I, Weiss G (2012) Exact FCFS matching rates for two infinite multitype sequences. Oper. Res. 60(2):475–489.Link, Google Scholar
• [2] Adan I, Bušić A, Mairesse J, Weiss G (2018) Reversibility and further properties of FCFS infinite bipartite matching. Math. Oper. Res. 43(2):598–621.Link, Google Scholar
• [3] Akbarpour M, Li S, Oveis Gharan S (2020) Thickness and information in dynamic matching markets. J. Political Econom. 128(3):783–815. Crossref, Google Scholar
• [4] Anderson R, Ashlagi I, Gamarnik D, Kanoria Y (2017) Efficient dynamic barter exchange. Oper. Res. 65(6):1446–1459.Link, Google Scholar
• [5] Aveklouris A, DeValve L, Ward AR, Wu X (2021) Matching impatient and heterogeneous demand and supply. Matching impatient and heterogeneous demand and supply. Oper. Res. 73(3):1637–1658.Google Scholar
• [6] Baccelli F, Boyer P, Hebuterne G (1984) Single-server queues with impatient customers. Adv. Appl. Probab. 16(4):887–905.Crossref, Google Scholar
• [7] Banerjee S, Freund D, Lykouris T (2017) Pricing and optimization in shared vehicle systems: An approximation framework. Babaioff M, Moulin H, Daskalakis C, eds. Proc. 2017 ACM Conf. Econom. Comput. (ACM, New York), 517–517.Google Scholar
• [8] Banerjee S, Kanoria Y, Qian P (2018) State dependent control of closed queueing networks. ACM SIGMETRICS Performance Evaluation Rev. 46(1):2–4.Crossref, Google Scholar
• [9] Besbes O, Castro F, Lobel I (2021) Surge pricing and its spatial supply response. Management Sci. 67(3):1350–1367.Link, Google Scholar
• [10] Billingsley P (1999) Convergence of Probability Measures, 2nd ed. (John Wiley & Sons, New York).Crossref, Google Scholar
• [11] Bimpikis K, Candogan O, Saban D (2019) Spatial pricing in ride-sharing networks. Oper. Res. 67(3):744–769.Link, Google Scholar
• [12] Blanchet JH, Reiman MI, Shah V, Wein LM, Wu L (2022) Asymptotically optimal control of a centralized dynamic matching market with general utilities. Oper. Res., ePub ahead of print January 21, https://doi.org/10.1287/opre.2021.2186.Google Scholar
• [13] Braverman A, Dai J, Miyazawa M (2017) Heavy traffic approximation for the stationary distribution of a generalized Jackson network: The BAR approach. Stochastic Systems 7(1):143–196.Link, Google Scholar
• [14] Braverman A, Dai JG, Liu X, Ying L (2019) Empty-car routing in ridesharing systems. Oper. Res. 67(5):1437–1452.Link, Google Scholar
• [15] Cachon GP, Daniels KM, Lobel R (2017) The role of surge pricing on a service platform with self-scheduling capacity. Manufacturing Service Oper. Management 19(3):368–384.Link, Google Scholar
• [16] Cadas A, Doncel J, Fourneau JM, Bušić A (2020) Flexibility can hurt dynamic matching system performance. ACM SIGMETRICS Performance Evaluation Rev. 49(3):37–42.Google Scholar
• [17] Caldentey R, Kaplan EH, Weiss G (2009) FCFS infinite bipartite matching of servers and customers. Adv. Appl. Probab. 41(3):695–730.Crossref, Google Scholar
• [18] Castillo JC, Knoepfle D, Weyl G (2017) Surge pricing solves the wild goose chase. Babaioff M, Moulin H, Daskalakis C, eds. Proc. 2017 ACM Conf. Econom. Comput. (ACM, New York), 241–242.Google Scholar
• [19] Castro F, Nazerzadeh H, Yan C (2020) Matching queues with reneging: A product form solution. Queueing Systems 96(3):359–385.Crossref, Google Scholar
• [20] hen H, Frank MZ (2001) State dependent pricing with a queue. IIE Trans. 33(10):847–860.Crossref, Google Scholar
• [21] Curtiss JH (1942) A note on the theory of moment generating functions. Ann. Math. Statist. 13(4):430–433.Google Scholar
• [22] oğru MK, Reiman MI, Wang Q (2010) A stochastic programming based inventory policy for assemble-to-order systems with application to the w model. Oper. Res. 58(4):849–864.Google Scholar
• [23] Erlang AK (1909) The theory of probabilities and telephone conversations. Nyt Tidsskrift Matematik B 20:33–39.Google Scholar
• [24] Eryilmaz A, Srikant R (2012) Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Systems 72(3–4):311–359.Crossref, Google Scholar
• [25] Gamarnik D, Zeevi A (2006) Validity of heavy traffic steady-state approximations in generalized Jackson networks. Ann. Appl. Probab. 16(1):56–90.Google Scholar
• [26] Gates LD Jr (1952) Differential equations in the distributions of Schwartz. Unpublished PhD thesis, Iowa State University, Ames.Google Scholar
• [27] Gates LD (1956) Linear differential equations in distributions. Proc. Amer. Math. Soc. 7(5):933–939.Crossref, Google Scholar
• [28] Gaunt R, Walton N (2020) Stein’s method for the single server queue in heavy traffic. Statist. Probab. Lett. 156:108566.Crossref, Google Scholar
• [29] Guda H, Subramanian U (2019) Your Uber is arriving: Managing on-demand workers through surge pricing, forecast communication, and worker incentives. Management Sci. 65(5):1995–2014.Abstract, Google Scholar
• [30] Gurvich I (2014) Diffusion models and steady-state approximations for exponentially ergodic Markovian queues. Ann. Appl. Probab. 24(6):2527–2559.Crossref, Google Scholar
• [31] Gurvich I, Ward A (2014) On the dynamic control of matching queues. Stochastic Systems 4(2):479–523.Link, Google Scholar
• [32] Hajek B (2015) Random Processes for Engineers (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [33] Halfin S, Whitt W (1981) Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29(3):567–588.Link, Google Scholar
• [34] Halperin I, Schwartz L (1952) Introduction to the Theory of Distributions (University of Toronto Press, Toronto).Crossref, Google Scholar
• [35] Harrison J (1988) Brownian models of queueing networks with heterogeneous customer populations. Fleming W, Lions P-L, eds. Stochastic Differential Systems, Stochastic Control Theory and Applications (Springer, Berlin, Heidelberg), 147–186.Crossref, Google Scholar
• [36] Harrison JM (1998) Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies. Ann. Appl. Probab. 8(3):822–848.Google Scholar
• [37] He S (2013) A one-dimensional diffusion model for overloaded queues with customer abandonment. Preprint, submitted December 16, https://arxiv.org/abs/1312.4244.Google Scholar
• [38] Hosseini M, Milner J, Romero G (2025) Dynamic relocations in car-sharing networks. Oper. Res. 73(4):2010–2025.Google Scholar
• [39] Hu M, Zhou Y (2018) Dynamic type matching. Manufacturing Service Oper. Management 24(1):125–142.Google Scholar
• [40] Huang J, Gurvich I (2018) Beyond heavy-traffic regimes: Universal bounds and controls for the single-server queue. Oper. Res. 66(4):1168–1188.Link, Google Scholar
• [41] Hunter JK, Nachtergaele B (2001) Applied Analysis (World Scientific Publishing Company, Singapore).Crossref, Google Scholar
• [42] Hurtado-Lange D, Maguluri ST (2019) Heavy-traffic analysis of the generalized switch under multidimensional state space collapse. SIGMETRICS Performance Evaluation Rev. 47(2):36–38.Crossref, Google Scholar
• [43] Hurtado-Lange D, Maguluri ST (2022) A load balancing system in the many-server heavy-traffic asymptotics. Queueing Systems 101(3):353–391.Google Scholar
• [44] Hurtado-Lange D, Maguluri ST (2020) Transform methods for heavy-traffic analysis. Stochastic Systems 10(4):275–309.Link, Google Scholar
• [45] Kanoria Y, Qian P (2020) Blind dynamic resource allocation in closed networks via mirror backpressure. Ostrovsky M, Procaccia A, Biró P, Hartline J, eds. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 503.Crossref, Google Scholar
• [46] Kim J, Randhawa RS (2017) The value of dynamic pricing in large queueing systems. Oper. Res. 66(2):409–425.Link, Google Scholar
• [47] Kingman J (1962) Some inequalities for the queue GI/G/1. Biometrika 49(3/4):315–324.Crossref, Google Scholar
• [48] Krishnan KSA, Singh C, Maguluri ST, Parag P (2020) Optimal pricing in finite server systems. Huang L, Koutsopoulos I, Subramanian V, eds. 2020 18th Internat. Sympos. Model. Optim. Mobile Ad Hoc Wireless Networks (IEEE, Piscataway, NJ), 1–8.Google Scholar
• [49] Lee C, Ward AR, Ye HQ (2020) Stationary distribution convergence of the offered waiting processes for GI/GI/1+ GI queues in heavy traffic. Queueing Systems 94(1):147–173.Crossref, Google Scholar
• [50] Liu X, Ying L (2019) On universal scaling of distributed queues under load balancing. Preprint, submitted December 26, https://arxiv.org/abs/1912.11904.Google Scholar
• [51] Low DW (1974) Optimal pricing for an unbounded queue. IBM J. Res. Development 18(4):290–302.Crossref, Google Scholar
• [52] Maguluri ST, Srikant R (2016) Heavy traffic queue length behavior in a switch under the MaxWeight algorithm. Stochastic Systems 6(1):211–250.Link, Google Scholar
• [53] Mandelbaum A, Stolyar A (2004) Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cμ-rule. Oper. Res. 52(6):836–855.Link, Google Scholar
• [54] Nguyen LM, Stolyar AL (2018) A queueing system with on-demand servers: Local stability of fluid limits. Queueing Systems 89(3–4):243–268.Crossref, Google Scholar
• [55] Özkan E (2020) Joint pricing and matching in ride-sharing systems. Eur. J. Oper. Res. 287(3):1149–1160.Google Scholar
• [56] Özkan E, Ward AR (2020) Dynamic matching for real-time ride sharing. Stochastic Systems 10(1):29–70.Google Scholar
• [57] Paschalidis IC, Tsitsiklis JN (2000) Congestion-dependent pricing of network services. IEEE/ACM Trans. Networking 8(2):171–184.Crossref, Google Scholar
• [58] Plambeck EL, Ward AR (2006) Optimal control of a high-volume assemble-to-order system. Math. Oper. Res. 31(3):453–477.Link, Google Scholar
• [59] Reiman MI, Wang Q (2015) Asymptotically optimal inventory control for assemble-to-order systems with identical lead times. Oper. Res. 63(3):716–732.Link, Google Scholar
• [60] Rudin W (1991) Gurley L, Wallis R, Luhrs M, eds. Functional Analysis, vol. 45 (McGrawHill Inc., New York), 46.Google Scholar
• [61] Sivaraman V, Venkatakrishnan SB, Ruan K, Negi P, Yang L, Mittal R, Fanti G, Alizadeh M (2020) High throughput cryptocurrency routing in payment channel networks. Bhagwan R, Porter G, eds. 17th Sympos. Networked Systems Design Implementation (USENIX Association, Berkeley), 777–796.Google Scholar
• [62] Song JS (1998) On the order fill rate in a multi-item, base-stock inventory system. Oper. Res. 46(6):831–845.Link, Google Scholar
• [63] Song JS, Yao DD (2002) Performance analysis and optimization of assemble-to-order systems with random lead times. Oper. Res. 50(5):889–903.Link, Google Scholar
• [64] Stolyar A (2004) MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Ann. Appl. Probab. 14(1):1–53.Crossref, Google Scholar
• [65] Talluri KT, Van Ryzin GJ (2006) The Theory and Practice of Revenue Management (Springer Science & Business Media, Boston).Google Scholar
• [66] Van der Vaart AW (2000) Asymptotic Statistics, vol. 3 (Cambridge University Press, Cambridge, UK).Google Scholar
• [67] Vardoyan G, Guha S, Nain P, Towsley D (2023) On the capacity region of bipartite and tripartite entanglement switching. ACM Trans. Model. Perform. Eval. Comput. Syst. 8(1–2):1–18. Google Scholar
• [68] Vardoyan G, Guha S, Nain P, Towsley D (2021) On the capacity region of bipartite and tripartite entanglement switching. ACM SIGMETRICS Performance Evaluation Rev. 48(3):45–50.Crossref, Google Scholar
• [69] Varma SM, Maguluri ST (2021) Throughput optimal routing in blockchain based payment systems. IEEE Trans. Control Network Systems 8(4):1859–1868.Crossref, Google Scholar
• [70] Varma SM, Castro F, Maguluri ST (2021) Dynamic pricing and matching for two-sided markets with strategic servers. Abstract Proc. 2021 ACM SIGMETRICS/Internat. Conf. Measurement Model. Comput. Systems (Association for Computing Machinery, New York), 61–62.Google Scholar
• [71] Varma SM, Castro F, Maguluri ST (2021) Near optimal control in ride hailing platforms with strategic servers. Preprint, submitted August 9, 2020, https://arxiv.org/abs/2008.03762.Google Scholar
• [72] Varma SM, Bumpensanti P, Maguluri ST, Wang H (2020) Dynamic pricing and matching for two-sided queues. Abstracts 2020 SIGMETRICS/Performance Joint Internat. Conf. Measurement Model. Comput. Systems (Association for Computing Machinery), 105–106.Google Scholar
• [73] Varma SM, Bumpensanti P, Maguluri ST, Wang H (2023) Dynamic pricing and matching for two-sided queues. Oper. Res. 71(1):83–100.Link, Google Scholar
• [74] Ward AR, Glynn PW (2005) A diffusion approximation for a GI/GI/1 queue with balking or reneging. Queueing Systems 50(4):371–400.Crossref, Google Scholar
• [75] Weiss G (2020) Directed FCFS infinite bipartite matching. Queueing Systems 96(3):387–418.Crossref, Google Scholar
• [76] Williams D (1991) Probability with Martingales (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [77] Zhou X, Tan J, Shroff N (2018) Flexible load balancing with multi-dimensional state-space collapse: Throughput and heavy-traffic delay optimality. Performance Evaluation 127:176–193.Crossref, Google Scholar