Approximations for a Queueing Game Model with Join-the-Shortest-Queue Strategy

doi:10.1007/s40305-021-00382-5

Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (3): 489-504.doi: 10.1007/s40305-021-00382-5

Previous Articles Next Articles

Approximations for a Queueing Game Model with Join-the-Shortest-Queue Strategy

Qi-Hui Bu¹, Li-Wei Liu², Jia-Shan Tang¹, Yi-Qiang Q. Zhao³

1. School of Science, Nanjing University of Posts and Telecommunications, Nanjing, 210023, Jiangsu, China;
2. School of Science, Nanjing University of Science and Technology, Nanjing, 210094, Jiangsu, China;
3. School of Mathematics and Statistics, Carleton University, Ottawa, ON, K1S 5B6, Canada

Received:2020-05-17 Revised:2021-11-14 Online:2023-09-30 Published:2023-09-07
Contact: Qi-Hui Bu, Jia-Shan Tang, Li-Wei Liu, Yi-Qiang Q. Zhao E-mail:buqihui@njupt.edu.cn;tangjs@njupt.edu.cn;lwliu@njust.edu.cn;zhao@math.carleton.ca
Supported by:
This work was supported in part by the National Natural Science Foundation of China (No.61773014), Scientific Research Fund of Nanjing University of Posts and Telecommunications (No.NY220160) and the Natural Sciences and Engineering Research Council of Canada.

Abstract

Abstract: This paper investigates a partially observable queueing system with N nodes in which each node has a dedicated arrival stream. There is an extra arrival stream to balance the load of the system by routing its customers to the shortest queue. In addition, a reward-cost structure is considered to analyse customers' strategic behaviours. The equilibrium and socially optimal strategies are derived for the partially observable mean field limit model. Then, we show that the strategies obtained from the mean field model are good approximations to the model with finite N nodes. Finally, numerical experiments are provided to compare the equilibrium and socially optimal behaviours, including joining probabilities and social benefits for different system parameters.

Key words: Game theory, Queueing systems, Mean field limit, Markov process

CLC Number:

90B22
68M20

Qi-Hui Bu, Li-Wei Liu, Jia-Shan Tang, Yi-Qiang Q. Zhao. Approximations for a Queueing Game Model with Join-the-Shortest-Queue Strategy[J]. Journal of the Operations Research Society of China, 2023, 11(3): 489-504.

TrendMD

References

[1] Haight, F.A.: Two queues in parallel. Biometrika 45(3–4), 401–410(1958)
[2] Kingman, J.F.: Two similar queues in parallel. Annals Math. Stat. 32(4), 1314–1323(1961)
[3] McDonald, D.: Overloading parallel servers when arrivals join the shortest queue. Lecture Notes in Statist., 117, Springer, New York, 1996(1995)
[4] Foley, R.D., McDonald, D.R.: Join the shortest queue: stability and exact asymptotics. Annal Appl. Probab. 11(3), 569–607(2001)
[5] Dawson, D.A., Tang, J., Zhao, Y.Q.: Performance analysis of joining the shortest queue model among a large number of queues. Asia-Pacific J. Oper. Res. 36(4), 1950019(2019)
[6] Gupta, V., Balter, M.H., Sigman, K., Whitt, W.: Analysis of join-the-shortest-queue routing for web server farms. Perform. Eval. 64(9–12), 1062–1081(2007)
[7] Bramson, M., Lu, Y., Prabhakar, B.: Decay of tails at equilibrium for FIFO join the shortest queue networks. Annals Appl. Probab. 23(5), 1841–1878(2013)
[8] Guillemin, F., Olivier, P., Simonian, A., Tanguy, C.: Two parallel queues with infinite servers and join the shortest queue discipline. Stochastic Models 31(4), 636–672(2015)
[9] Eschenfeldt, P., Gamarnik, D.: Join the shortest queue with many servers. The Heavy-Traffic Asymptotics. Math. Oper. Res. 43(3), 867–886(2018)
[10] Naor, P.: The regulation of queue seize by levying tolls. Econometrica 37, 15–24(1969)
[11] Edelson, N.M., Hilderbrand, D.K.: Congestion tolls for Poisson queuing processes. Econom. J. Econom. Soc. 43(1), 81–92(1975)
[12] Chen, P., Zhou, Y.: Equilibrium balking strategies in the single server queue with setup times and breakdowns. Oper. Res. 15(2), 213–231(2015)
[13] Hassin, R., Roet-Green, R.: The impact of inspection cost on equilibrium, revenue, and social welfare in a single-server queue. Oper. Res. 65(3), 804–820(2017)
[14] Do, N.H., Van Do, T., Melikov, A.: Equilibrium customer behavior in the M/M/1 retrial queue with working vacations and a constant retrial rate. Oper. Res. Int. J. (2018). https://doi.org/10.1007/s12351-017-0369-7
[15] Wang, Z., Liu, L., Shao, Y., Chai, X., Chang, B.: Equilibrium joining strategy in a batch transfer queuing system with gated policy. Methodol. Comput. Appl. Probab. (2018). https://doi.org/10.1007/s11009-018-9687-3
[16] Hassin, R.: Rational Queueing. Chapman and Hall/CRC Press, Boca Raton (2016)
[17] Xu, J., Hajek, B.: The supermarket game. Stochastic Syst. 3(2), 405–441(2013)
[18] Wiecek, P., Altman, E., Ghosh, A.: Mean-field game approach to admission control of an M/M/$ \infty $ queue with shared service cost. Dynam. Games Appl. 6(4), 538–566(2016)
[19] Ying, L., Srikant, R., Kang, X.: The power of slightly more than one sample in randomized load balancing. Math. Oper. Res. 42(3), 692–722(2017)
[20] Mitzenmacher, M.: The power of two choices in randomized load balancing. Ph.D. thesis, University of California at Berkeley (1996)
[21] Ethier, S.N., Kurtz, T.G.: Markov Processes: Characterization and Convergence, vol. 282. John Wiley and Sons, New York (2009)

Approximations for a Queueing Game Model with Join-the-Shortest-Queue Strategy

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	Timothy Ganesan, Pandian Vasant, Igor Litvinchev. Chaotic Simulator for Bilevel Optimization of Virtual Machine Placements in Cloud Computing [J]. Journal of the Operations Research Society of China, 2022, 10(4): 703-723.
[2]	Bo-Yu Zhang, Shan Pei. Game Theory and the Evolution of Cooperation [J]. Journal of the Operations Research Society of China, 2022, 10(2): 379-399.
[3]	Yu-Kun Cheng, Zi-Xin Zhou. An Improved Incentive Ratio of the Resource Sharing on Cycles [J]. Journal of the Operations Research Society of China, 2019, 7(3): 409-427.