Customer Equilibrium and Optimal Strategies in Markovian Queuing Networks
by Mr. Pantelis Z. Lappas, Doctoral Candidate
A significant part of the queuing literature in recent years has been devoted to the economic analysis of queuing systems with strategic customer behavior. Customer equilibrium models have been analyzed for a wide variety of single-stage systems, under various assumptions on the level of information available to the customers at their decision instants. Edelson and Hildebrand (1975) and Naor (1979) have studied the equilibrium analysis of an M/M/1 queue where customers decide whether to join the system or balk and have no information and full information on the state of the system, respectively. Subsequent works have incorporated multiple customer classes with different priority disciplines, server vacation policies and other features (Hassin and Haviv, 2003).
Equilibrium models of queuing networks are rather scarce in the queuing literature compared to those of single stage systems. The reason is computational complexity. In this framework, the input process to a queue is not exogenously defined, but it rather emerges as the result of the decisions of the individual customers as to whether enter the system or balk, which queue to enter, whether to depart before completing service, etc. The economic factors which are typically involved in a customer's decision process are the value obtained from receiving the service and on the other hand the cost incurred because of the delay in the queue and/or the service station. Each customer makes an independent decision, with the objective of maximizing his total net benefit, which is equal to the value of service minus a cost due to expected delay. A customer's delay, thus also his benefit, depends on the actual input rate to each queue, which in turn depends on the decisions of the other customers. In consequence, customer decision can be formulated as a game in order to identify the unique symmetric Nash equilibrium strategy.
Network models have been studied extensively in telecommunications where it is often assumed that there are several customer classes, each of which moves in the network with given routing probabilities and it is sought to identify pricing policies that include welfare maximizing loads (Kelly et al., 1998). Recently, Burnetas (2013) has considered a series of queues with strategic customers who decide independently which queues to join so as to maximize their net benefit of service value minus costs showing that there exists a unique symmetric Nash equilibrium strategy. However, it would be of interest to consider more general network topologies.
Burnetas, A. (2013). Customer equilibrium and optimal strategies in Markovian queues in series. Annals of Operations Research, 208, 515-529.
Edelson, N.M. and Hildebrand, D. (1975). Congestion tolls for Poisson queuing processes. Econometrica, 43,81-92.
Hassin, R. and Haviv, M. (2003). To queue or not to queue: equilibrium behavior in queuing systems. Berlin: Springer.
Kelly, F., Maulloo, A. and Tan, D. (1998). On the optimal maintenance of systems and control of arrivals in queues. Stochastic Analysis and Applications, 13, 137-164.
Naor, P. (1979). The regulation of queue size by levying tolls. Econometrica, 37,15-24.