Equilibrium Behavior in Bipartite Queueing Networks

摘要

The earliest result in analysis of queueing systems with rational customers showed that rational customers choose to join a single server queue more often that is socially optimal. This result is extended here to the class of bipartite closed queueing networks. In these systems, a pool of customers can choose to join a network in which the customers repeatedly cycle between two sets of queues, earning a reward for each cycle and incurring a cost per unit time. This paper shows that customers will likewise continue to join bipartite closed queueing networks beyond the overall social optimum. The toll range which induces overall socially optimal behavior is derived. Further, this paper shows that the toll which maximizes the earnings of the toll collector is the maximum of this overall optimal toll range. Bounds on the ratio of two performance measures between the selfish and overall socially optimal cases are proved. Computational results, directions for future work, and implications for practice are also presented.