×

zbMATH — the first resource for mathematics

Rate control under heavy traffic with strategic servers. (English) Zbl 1409.60131
Summary: We consider a large queueing system that consists of many strategic servers that are weakly interacting. Each server processes jobs from its unique critically loaded buffer and controls the rate of arrivals and departures associated with its queue to minimize its expected cost. The rates and the cost functions in addition to depending on the control action, can depend, in a symmetric fashion, on the size of the individual queue and the empirical measure of the states of all queues in the system. In order to determine an approximate Nash equilibrium for this finite player game, we construct a Lasry-Lions-type mean-field game (MFG) for certain reflected diffusions that governs the limiting behavior. Under conditions, we establish the convergence of the Nash-equilibrium value for the finite size queuing system to the value of the MFG.

MSC:
60K25 Queueing theory (aspects of probability theory)
91A13 Games with infinitely many players (MSC2010)
60K35 Interacting random processes; statistical mechanics type models; percolation theory
93E20 Optimal stochastic control
60H30 Applications of stochastic analysis (to PDEs, etc.)
60F17 Functional limit theorems; invariance principles
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Achdou, Y., Camilli, F. and Capuzzo-Dolcetta, I. (2013). Mean field games: Convergence of a finite difference method. SIAM J. Numer. Anal.51 2585–2612. · Zbl 1286.91022
[2] Achdou, Y. and Capuzzo-Dolcetta, I. (2010). Mean field games: Numerical methods. SIAM J. Numer. Anal.48 1136–1162. · Zbl 1217.91019
[3] Achdou, Y. and Porretta, A. (2016). Convergence of a finite difference scheme to weak solutions of the system of partial differential equations arising in mean field games. SIAM J. Numer. Anal.54 161–186. · Zbl 1382.65273
[4] Aliprantis, C. D. and Border, K. C. (2006). Infinite Dimensional Analysis: A Hitchhiker’s Guide, 3rd ed. Springer, Berlin. · Zbl 1156.46001
[5] Antunes, N., Fricker, C., Robert, P. and Tibi, D. (2008). Stochastic networks with multiple stable points. Ann. Probab.36 255–278. · Zbl 1130.60086
[6] Ata, B., Harrison, J. M. and Shepp, L. A. (2005). Drift rate control of a Brownian processing system. Ann. Appl. Probab.15 1145–1160. · Zbl 1069.60074
[7] Baccelli, F., Karpelevich, F., Kelbert, M. Y., Puhalskii, A., Rybko, A. and Suhov, Y. M. (1992). A mean-field limit for a class of queueing networks. J. Stat. Phys.66 803–825. · Zbl 0925.60115
[8] Bayraktar, E., Budhiraja, A. and Cohen, A. (2017). A numerical scheme for a mean field game in some queuing systems based on Markov chain approximation method. SIAM J. Control Optim. To appear. · Zbl 1425.91043
[9] Bayraktar, E., Horst, U. and Sircar, R. (2006). A limit theorem for financial markets with inert investors. Math. Oper. Res.31 789–810. · Zbl 1276.91055
[10] Bayraktar, E., Horst, U. and Sircar, R. (2007). Queuing theoretic approaches to financial price fluctuations. Handbooks Oper. Res. Management Sci.15 637–677.
[11] Bayraktar, E. and Ludkovski, M. (2011). Optimal trade execution in illiquid markets. Math. Finance21 681–701. · Zbl 1233.91335
[12] Bayraktar, E. and Ludkovski, M. (2014). Liquidation in limit order books with controlled intensity. Math. Finance24 627–650. · Zbl 1314.91247
[13] Bayraktar, E. and Zhang, Y. (2016). A rank-based mean field game in the strong formulation. Electron. Commun. Probab.21 Paper No. 72. · Zbl 1415.91050
[14] Benaim, M. and Le Boudec, J.-Y. (2008). A class of mean field interaction models for computer and communication systems. Perform. Eval.65 823–838.
[15] Benamou, J.-D. and Carlier, G. (2015). Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations. J. Optim. Theory Appl.167 1–26. · Zbl 1326.49074
[16] Billingsley, P. (1999). Convergence of Probability Measures, 2nd ed. Wiley, New York. · Zbl 0944.60003
[17] Blair, J., Johnson, P. and Duck, P. (2015). Analysis of optimal liquidation in limit order books. Preprint. Available at http://eprints.ma.man.ac.uk/2299/01/covered/MIMS_ep2014_23.pdf.
[18] Bobbio, A., Gribaudo, M. and Telek, M. (2008). Analysis of large scale interacting systems by mean field method. In Fifth International Conference on Quantitative Evaluation of Systems (QEST’08) 215–224. IEEE, New York.
[19] Borkar, V. S. (1989). Optimal Control of Diffusion Processes. Pitman Research Notes in Mathematics Series203. Longman Scientific & Technical, Harlow. · Zbl 0669.93065
[20] Borovkov, K. A. (1998). Propagation of chaos for queueing networks. Theory Probab. Appl.42 385–394.
[21] Budhiraja, A. and Friedlander, E. (2018). Diffusion approximations for controlled weakly interacting large finite state systems with simultaneous jumps. Ann. Appl. Probab.28 204–249. · Zbl 1391.60232
[22] Budhiraja, A., Ghosh, A. P. and Lee, C. (2011). Ergodic rate control problem for single class queueing networks. SIAM J. Control Optim.49 1570–1606. · Zbl 1226.93138
[23] Cardaliaguet, P. (2013). Notes on mean field games. Available at https://www.ceremade.dauphine.fr/ cardalia/MFG20130420.pdf/. · Zbl 1314.91043
[24] Carlini, E. and Silva, F. J. (2014). A fully discrete semi-Lagrangian scheme for a first order mean field game problem. SIAM J. Numer. Anal.52 45–67. · Zbl 1300.65064
[25] Carlini, E. and Silva, F. J. (2015). A semi-Lagrangian scheme for a degenerate second order mean field game system. Discrete Contin. Dyn. Syst.35 4269–4292. · Zbl 1332.65138
[26] Carmona, R. and Delarue, F. (2013). Probabilistic analysis of mean-field games. SIAM J. Control Optim.51 2705–2734. · Zbl 1275.93065
[27] Carmona, R. and Lacker, D. (2015). A probabilistic weak formulation of mean field games and applications. Ann. Appl. Probab.25 1189–1231. · Zbl 1332.60100
[28] Chassagneux, J.-F., Crisan, D. and Delarue, F. (2017). Numerical method for FBSDEs of McKean–Vlasov type. Available at arXiv:1703.02007 [math.PR].
[29] Chen, H. and Yao, D. D. (2001). Fundamentals of Queuing Networks: Performance, Asymptotics, and Optimization. Springer, Berlin. · Zbl 0992.60003
[30] Dai, J. G. and Villiams, R. J. (1995). Existence and uniqueness of semimartingale reflecting Brownian motions in convex polyhedra. Theory Probab. Appl.40 1–40.
[31] El Karoui, N., Hu̇u̇ Nguyen, D. and Jeanblanc-Picqué, M. (1987). Compactification methods in the control of degenerate diffusions: Existence of an optimal control. Stochastics20 169–219. · Zbl 0613.60051
[32] Fendick, K. W. and Rodrigues, M. A. (1994). Asymptotic analysis of adaptive rate control for diverse sources with delayed feedback. IEEE Trans. Inform. Theory40 2008–2025. · Zbl 0833.90040
[33] Fischer, M. (2017). On the connection between symmetric \(n\)-player games and mean field games. Ann. Appl. Probab.27 757–810. · Zbl 1375.91009
[34] Föllmer, H. and Horst, U. (2001). Convergence of locally and globally interacting Markov chains. Stochastic Process. Appl.96 99–121. · Zbl 1058.60087
[35] Gibbens, R. J., Hunt, P. J. and Kelly, F. P. (1990). Bistability in communication networks. In Disorder in Physical Systems 113–127. Oxford Univ. Press, New York. · Zbl 0721.60103
[36] Gomes, D. A., Mohr, J. and Souza, R. R. (2013). Continuous time finite state mean field games. Appl. Math. Optim.68 99–143. · Zbl 1283.91016
[37] Gopalakrishnan, R., Doroudi, S., Ward, A. R. and Wierman, A. (2017). Routing and staffing when servers are strategic. Oper. Res.64 1033–1050. · Zbl 1348.90197
[38] Graham, C. (2000). Chaoticity on path space for a queueing network with selection of the shortest queue among several. J. Appl. Probab.37 198–211. · Zbl 0961.60091
[39] Graham, C. and Robert, P. (2009). Interacting multi-class transmissions in large stochastic networks. Ann. Appl. Probab.19 2334–2361. · Zbl 1179.60067
[40] Guéant, O. (2012). New numerical methods for mean field games with quadratic costs. Netw. Heterog. Media7 315–336. · Zbl 1270.35020
[41] Guéant, O., Lasry, J.-M. and Lions, P.-L. (2011). Mean field games and applications. In Paris–Princeton Lectures on Mathematical Finance 2010. Lecture Notes in Math.2003 205–266. Springer, Berlin.
[42] Guéant, O. and Lehalle, C.-A. (2015). General intensity shapes in optimal liquidation. Math. Finance25 457–495. · Zbl 1331.91165
[43] Hu, Y. and Peng, S. (1997). A stability theorem of backward stochastic differential equations and its application. C. R. Acad. Sci. Paris Sér. I Math.324 1059–1064. · Zbl 0882.60053
[44] Huang, M., Caines, P. E. and Malhamé, R. P. (2007). The Nash certainty equivalence principle and Mckean–Vlasov systems: An invariance principle and entry adaptation. In 46th IEEE Conference on Decision and Control 121–126. IEEE, New York.
[45] Huang, M., Malhamé, R. P. and Caines, P. E. (2006). Large population stochastic dynamic games: Closed-loop McKean–Vlasov systems and the Nash certainty equivalence principle. Commun. Inf. Syst.6 221–251. · Zbl 1136.91349
[46] Hunt, P. J. and Kurtz, T. G. (1994). Large loss networks. Stochastic Process. Appl.53 363–378. · Zbl 0810.60087
[47] Joffe, A. and Métivier, M. (1986). Weak convergence of sequences of semimartingales with applications to multitype branching processes. Adv. in Appl. Probab. 20–65. · Zbl 0595.60008
[48] Kotelenez, P. M. and Kurtz, T. G. (2010). Macroscopic limits for stochastic partial differential equations of McKean–Vlasov type. Probab. Theory Related Fields146 189–222. · Zbl 1189.60123
[49] Kruk, L., Lehoczky, J., Ramanan, K. and Shreve, S. (2007). An explicit formula for the Skorokhod map on \([0,a]\). Ann. Probab.35 1740–1768. · Zbl 1139.60017
[50] Kushner, H. J. (2001). Heavy Traffic Analysis of Controlled Queueing and Communication Networks. In Stochastic Modelling and Applied Probability. Applications of Mathematics (New York) 47. Springer, New York. · Zbl 0988.90004
[51] Kushner, H. J. and Dupuis, P. G. (1992). Numerical Methods for Stochastic Control Problems in Continuous Time. Applications of Mathematics (New York) 24. Springer, New York. · Zbl 0754.65068
[52] Lachapelle, A., Lasry, J., Lehalle, C. and Lions, P. (2015). Efficiency of the price formation process in presence of high frequency participants: A mean field game analysis. Available at http://arxiv.org/abs/1305.6323. · Zbl 1404.91245
[53] Lachapelle, A., Salomon, J. and Turinici, G. (2010). Computation of mean field equilibria in economics. Math. Models Methods Appl. Sci.20 567–588. · Zbl 1193.91018
[54] Lacker, D. (2015). A general characterization of the mean field limit for stochastic differential games. Probab. Theory Related Fields 1–68. · Zbl 1344.60065
[55] Lacker, D. (2015). Mean field games via controlled martingale problems: Existence of Markovian equilibria. Stochastic Process. Appl.125 2856–2894. · Zbl 1346.60083
[56] Lasry, J.-M. and Lions, P.-L. (2006). Jeux à champ moyen. I. Le cas stationnaire. C. R. Math. Acad. Sci. Paris343 619–625. · Zbl 1153.91009
[57] Lasry, J.-M. and Lions, P.-L. (2006). Jeux à champ moyen. II. Horizon fini et contrôle optimal. C. R. Math. Acad. Sci. Paris343 679–684. · Zbl 1153.91010
[58] Lasry, J.-M. and Lions, P.-L. (2007). Mean field games. Jpn. J. Math.2 229–260. · Zbl 1156.91321
[59] Li, J., Bhattacharyya, R., Paul, S., Shakkottai, S. and Subramanian, V. (2015). Incentivizing sharing in realtime d2d streaming networks: A mean field game perspective. In IEEE Conference on Computer Communications (INFOCOM 2015) 2119–2127. IEEE, New York.
[60] Lieberman, G. M. (1996). Second Order Parabolic Differential Equations. World Scientific, River Edge, NJ. · Zbl 0884.35001
[61] Manjrekar, M., Ramaswamy, V. and Shakkottai, S. (2014). A mean field game approach to scheduling in cellular systems. In INFOCOM, 2014 Proceedings IEEE 1554–1562. IEEE, New York.
[62] Schauder, J. P. (1930). Der fixpunktsatz in funktionalräumen. Studia Math.2 171–180. · JFM 56.0355.01
[63] Smart, D. R. (1974). Fixed Point Theorems. Cambridge Tracts in Mathematics66. Cambridge Univ. Press, London. · Zbl 0297.47042
[64] Sznitman, A.-S. (1991). Topics in propagation of chaos. In École D’Été de Probabilités de Saint-Flour XIX—1989. Lecture Notes in Math.1464 165–251. Springer, Berlin.
[65] Tsybakov, A. B. (2009). Introduction to Nonparametric Estimation. Springer, New York. Revised and extended from the 2004 French original. Translated by Vladimir Zaiats.
[66] Villani, C. (2009). Optimal Transport. Old and New. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 338. Springer, Berlin.
[67] Vvedenskaya, N. D. and Suhov, Y. M. (1997). Dobrushin’s mean-field approximation for a queue with dynamic routing. Research Report RR-3328, Projet MEVAL, INRIA. · Zbl 0907.60072
[68] Wiecek, P., Altman, E. and Ghosh, A. (2016). Mean-field game approach to admission control of an \(M/M/∞\) queue with shared service cost. Dyn. Games Appl.6 538–566. · Zbl 1391.91033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.