Strategic bidding in an accumulating priority queue: equilibrium analysis. (English) Zbl 1357.90034
Summary: We study the strategic purchasing of priorities in a time-dependent accumulating priority M/G/1 queue. We formulate a non-cooperative game in which customers purchase priority coefficients with the goal of reducing waiting costs in exchange. The priority of each customer in the queue is a linear function of the individual waiting time, with the purchased coefficient being the slope. The unique pure Nash equilibrium is solved explicitly for the case with homogeneous customers. A general characterisation of the Nash equilibrium is provided for the heterogeneous case. It is shown that both avoid the crowd and follow the crowd behaviors are prevalent, within class types and between them. We further present a pricing mechanism that ensures the order of the accumulating priority rates in equilibrium follows a \(C\mu\) type rule and improves overall efficiency.
MSC:
| 90B22 | Queues and service in operations research |
| 91A07 | Games with infinitely many players |
| 60K25 | Queueing theory (aspects of probability theory) |
References:
| [1] | Afèche, P., & Mendelson, H. (2004). Pricing and priority auctions in queueing systems with a generalized delay cost structure. Management Science, 50(7), 869-882. · Zbl 1232.90134 · doi:10.1287/mnsc.1030.0156 |
| [2] | Balachandran, K. (1972). Purchasing priorities in queues. Management Science, 18(5-1), 319-326. · Zbl 0231.60084 · doi:10.1287/mnsc.18.5.319 |
| [3] | Durrett, R. (2010). Probability: Theory and examples. Cambridge: Cambridge University Press. · Zbl 1202.60001 · doi:10.1017/CBO9780511779398 |
| [4] | Glazer, A., & Hassin, R. (1986). Stable priority purchasing in queues. Operations Research Letters, 4(6), 285-288. · Zbl 0603.60088 · doi:10.1016/0167-6377(86)90030-1 |
| [5] | Goldberg, H. M. (1977). Analysis of the earliest due date scheduling rule in queueing systems. Mathematics of Operations Research, 2(2), 145-154. · Zbl 0389.60075 · doi:10.1287/moor.2.2.145 |
| [6] | Hassin, R. (1995). Decentralized regulation of a queue. Management Science, 41(1), 163-173. · Zbl 0829.90062 · doi:10.1287/mnsc.41.1.163 |
| [7] | Hassin, R., & Haviv, M. (2003). To queue or not to queue: Equilibrium behaviour in queueing systems (Vol. 59). Berlin: Springer. · Zbl 1064.60002 |
| [8] | Haviv, M. (2013). Queues: A course in queueing theory. International series in operations research & management science (Vol. 191). Berlin: Springer. · Zbl 1267.90002 |
| [9] | Haviv, M., & van der Wal, J. (1997). Equilibrium strategies for processor sharing and random queues with relative priorities. Probability in The Engineering and Informational Sciences, 11, 403-412. · Zbl 1096.60521 · doi:10.1017/S0269964800004940 |
| [10] | Kanet, J. J. (1982). A mixed delay dependent queue discipline. Operations Research, 30(1), 93-96. · Zbl 0481.90027 · doi:10.1287/opre.30.1.93 |
| [11] | Kleinrock, L. (1964). A delay dependent queue discipline. Naval Research Logistics Quarterly, 11(3-4), 329-341. · Zbl 0137.11906 · doi:10.1002/nav.3800110306 |
| [12] | Kleinrock, L., Queueing systems, No. II (1976), Hoboken · Zbl 0361.60082 |
| [13] | Kleinrock, L., & Finkelstein, R. P. (1967). Time dependent priority queues. Operations Research, 15(1), 104-116. · Zbl 0155.24804 · doi:10.1287/opre.15.1.104 |
| [14] | Mendelson, H., & Whang, S. (1990). Optimal incentive-compatible priority pricing for the \[M/M/1\] M/M/1 queue. Operations Research, 38(5), 870-883. · Zbl 0723.90023 · doi:10.1287/opre.38.5.870 |
| [15] | Netterman, A., & Adiri, I. (1979). A dynamic priority queue with general concave priority functions. Operations Research, 27(6), 1088-1100. · Zbl 0442.90026 · doi:10.1287/opre.27.6.1088 |
| [16] | Osborne, M. J., & Rubinstein, A. (1994). A Course in Game Theory. Cambridge: MIT Press. · Zbl 1194.91003 |
| [17] | Rosen, J. B. (1965). Existence and uniqueness of equilibrium points for concave n-person games. Econometrica, 33(3), 520-534. · Zbl 0142.17603 · doi:10.2307/1911749 |
| [18] | Sharif, A. B., Stanford, D. A., Taylor, P., & Ziedins, I. (2014). A multi-class multi-server accumulating priority queue with application to health care. Operations Research for Health Care, 3(2), 73-79. · doi:10.1016/j.orhc.2014.01.002 |
| [19] | Stanford, D. A., Taylor, P., & Ziedins, I. (2014). Waiting time distributions in the accumulating priority queue. Queueing Systems, 77(3), 297-330. · Zbl 1307.60136 · doi:10.1007/s11134-013-9382-6 |
| [20] | Topkis, D. M. (1979). Equilibrium points in nonzero-sum n-person submodular games. SIAM Journal on Control and Optimization, 17(6), 773-787. · Zbl 0433.90091 · doi:10.1137/0317054 |
| [21] | van Mieghem, J. A. (1995). Dynamic scheduling with convex delay costs: The generalized \[c\mu\] cμ rule. The Annals of Applied Probability, 5(3), 809-833. · Zbl 0843.90047 |
| [22] | Yao, D. D. (1995). S-modular games, with queueing applications. Queueing Systems, 21(3-4), 449-475. · Zbl 0858.90142 · doi:10.1007/BF01149170 |
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.
