×

Mean-field game approach to admission control of an \(M/M/\infty \) queue with shared service cost. (English) Zbl 1391.91033

Summary: We study a mean-field approximation of the \(M/M/\infty \) queueing system. The problem we deal is quite different from standard games of congestion as we consider the case in which higher congestion results in smaller costs per user. This is motivated by a situation in which some TV show is broadcast so that the same cost is needed no matter how many users follow the show. Using a mean-field approximation, we show that this results in multiple equilibria of threshold type which we explicitly compute. We further derive the social optimal policy and compute the price of anarchy. We then study the game with partial information and show that by appropriate limitation of the queue-state information obtained by the players, we can obtain the same performance as when all the information is available to the players. We show that the mean-field approximation becomes tight as the workload increases, thus the results obtained for the mean-field model well approximate the discrete one.

MSC:

91A15 Stochastic games, stochastic differential games
60K25 Queueing theory (aspects of probability theory)
90C22 Semidefinite programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aghassi M, Bertsimas D (2006) Robust game theory. Math Program 107:231-273 · Zbl 1134.91309 · doi:10.1007/s10107-005-0686-0
[2] Altman E, Gaujal B, Hordijk A (2000) Admission control in stochastic event graphs. IEEE Autom Control 45(5):854-867 · Zbl 0980.93046 · doi:10.1109/9.855547
[3] Altman E, Jiménez T (2013) Admission control to an M/M/1 queue with partial information. In: Dudin A, De Turck K (eds) Analytical and stochastic modeling techniques and applications. 20th International Conference, ASMTA 2013, Ghent, Belgium, July 8-10, 2013. Proceedings, vol 7984, Springer, Berlin Heidelberg, pp. 12-21 · Zbl 1395.90112
[4] Altman E, Shimkin N (1998) Individual equilibrium and learning in processor sharing systems. Oper Res 46:776-784 · Zbl 0987.90020 · doi:10.1287/opre.46.6.776
[5] Anshelevich E, Dasgupta A, Kleinberg J, Tardos E, Wexler T, Roughgarden T (2004) The price of stability for network design with fair cost allocation. In: Annual IEEE symposium on foundations of computer science · Zbl 1173.91321
[6] Darroch JN, Seneta E (1965) On quasi-stationary distributions in absorbing discrete-time finite Markov chains. J Appl Probab 2:88-100 · Zbl 0134.34704 · doi:10.1017/S0021900200031600
[7] Hayashi S, Yamashita N, Fukushima M (2005) Robust Nash equilibria and second-order cone complementarity problems. J Nonlinear Convex Anal 6:283-296 · Zbl 1137.91310
[8] Hordijk A, Spieksma F (1989) Constrained admission control to a queueing system. Ann Appl Probab 21:409-431 · Zbl 0674.60086 · doi:10.1017/S0001867800018619
[9] Hsiao MT, Lazar AA (1991) Optimal decentralized flow control of Markovian queueing networks with multiple controllers. Perform Eval 13:181-204 · Zbl 0746.90022 · doi:10.1016/0166-5316(91)90054-7
[10] Korilis YA, Lazar A (1995) On the existence of equilibria in noncooperative optimal flow control. J ACM 42(3):584-613 · Zbl 0885.68015 · doi:10.1145/210346.210415
[11] Koutsoupias E, Papadimitriou CH (1999) Worst-case equilibria. In 16th annual symposium on theoretical aspects of computer science, Trier, Germany, 4-6 March 1999, pp 404-413 · Zbl 1099.91501
[12] Maynard, Smith J.; Maynard, Smith J. (ed.), Game theory and the evolution of fighting, 8-28 (1972), Edinburgh
[13] Naor P (1969) On the regulation of queueing size by levying tolls. Econometrica 37:15-24 · Zbl 0172.21801 · doi:10.2307/1909200
[14] Singh C, Altman E (2011) The multicast coalition and the non-cooperative subscription problem. IEEE INFOCOM, April, 2011, Shanghai · Zbl 0674.90029
[15] Schwartz A, Weiss A (1995) Large deviations for performance analysis. Chapman & Hall, London · Zbl 0871.60021
[16] Stidham S (1985) Optimal control of admission to a queueing system. IEEE Trans Autom Control 30:705-713 · Zbl 0563.90044 · doi:10.1109/TAC.1985.1104054
[17] Stidham S, Rajagopal S, Kulkarni VG (1995) Optimal flow control of a stochastic fluid-flow system. IEEE J Sel Areas Commun 13:1219-1228 · doi:10.1109/49.414641
[18] Stidham S, Weber RR (1989) Monotonic and insensitive optimal policies for control of queues with undiscounted costs. Oper Res 37:611-625 · Zbl 0674.90029 · doi:10.1287/opre.37.4.611
[19] Tembine H, Le Boudec JY, El Azouzi R, Altman E (2009) From mean field interaction to evolutionary game dynamics. WiOpt 2009
[20] Wiecek P, Altman E, Ghosh A (2014) Mean-field game approach to admission control of an M/M/\[ \infty \]∞ queue with decreasing congestion cost. In: 7th international conference on network games control and optimization (NETGCOOP 2014), Oct 2014, Trento, Italy · Zbl 1410.91053
[21] Yechiali U (1971) On optimal balking rules and toll charges in a \[GI|M|1\] GI|M|1 queueing process. Oper Res 19:349-370 · Zbl 0227.60054 · doi:10.1287/opre.19.2.349
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.