The price of anarchy in an exponential multi-server
Introduction
We consider a single multi-server service station with a number of not necessarily identical servers. We assume that customers’ costs are their expected waiting times, and that the time in service is part of the waiting time. Each customer selects a server, and no further information (such as the queue lengths upon arrival) is given. We assume a never-ending stream of arrivals which follows a Poisson process, and exponentially distributed (server-dependent) service times. We assume that steady-state conditions have been reached, and in particular that the arrival rate is smaller than the total service rate.
Selfish customers choose a server to minimize their own mean waiting times, ignoring the social consequences of their actions. As a point of comparison, we also consider the outcome that directs customers to servers to minimize the average mean waiting time. Naturally, the outcome reached by selfish customers—a (Nash) equilibrium—need not coincide with the socially optimal one. We measure this inefficiency via the price of anarchy (PoA) [7], [8], defined as the ratio between the average mean waiting times of the (unique) equilibrium and of the socially optimal outcome. The PoA is by definition at least 1. A PoA close to 1 indicates that the equilibrium is approximately socially optimal, and thus the consequences of selfish behavior are relatively benign.
Our goal is to understand when the PoA in a multi-server exponential service station is reasonably small. On the negative side, previous work by Friedman [5] shows that if the number of servers can be arbitrarily large, then the PoA can also be arbitrarily large. On the positive side, the PoA is 1 when servers are homogeneous; this is implicit in [3]. Also, Roughgarden [9] showed that the PoA is upper bounded by a small constant in stations in which the equilibrium outcome leaves a constant fraction of the capacity of each server unused.
Our main result is that the PoA is small in exponential service stations with a bounded number of servers, even when service times are heterogeneous and an arbitrarily large fraction of the server capacities are used. Specifically, we show that the PoA in such stations is upper bounded by the number of servers used in the socially optimal outcome. We also give a family of examples achieving a matching lower bound.
We conclude with brief comments on additional related work. Our model can be viewed as a special case of the traffic routing model that is often referred to as “traffic equilibria” (see e.g. [11]) or “selfish routing” (see e.g. [10]). While the PoA in this general model has been extensively studied, the only results on the PoA in exponential multi-server stations are those discussed above. Also, although different terminology is used, Koutsoupias and Papadimitriou [7] study a multi-server system. However, they consider a finite number of players, each controlling a non-negligible fraction of the arriving traffic. They also define the social cost to be the maximum individual cost, whereas we consider the average player cost. For surveys of more recent work in this model, see [2], [4].
Section snippets
The model and preliminaries
Suppose there are n exponential servers who man a single service station. Let be the service rate of server i, . Assume without loss of generality that . For convenience assume that . Denote by . There is a single Poisson arrival process with rate . To guarantee stability, we assume that .
Main results
Our main results are that the PoA in every multi-server exponential service station is upper bounded by the number of servers, and that no better upper bound is possible. The following lemma, which considers the special case of service stations in which the socially optimal and equilibrium outcomes use the same set of servers, is crucial for our upper bound proof. Lemma 3.1 In a multi-server exponential service station in which both the socially optimal and the equilibrium outcomes use the same number m
Acknowledgments
Thanks to Yoav Kerner for helpful comments. The first author conducted research leading to this paper in the School of Mathematics, Statistics and Computer Science at Victoria University of Wellington, New Zealand and at the School of Economics and Political Science at the University of Sydney, Sydney, NSW, Australia, and was supported in part by The Israel Science Foundation Grant no. 237/02. The second author was supported in part by ONR grant N00014-04-1-0725, DARPA grant W911NF-05-1-0224,
References (11)
The price of anarchy is independent of the network topology
J. Comput. Syst. Sci.
(2003)- et al.
Individual versus social optimization in the allocation of customers to alternative servers
Manage. Sci.
(1983) Selfish routing on the Internet
- et al.
The traffic assignment problem for a general network
J. Res. Nat. Bur. Stand. Ser. B
(1969) - et al.
Selfish routing in non-cooperative networks: a survey
Cited by (59)
Price of Anarchy with multiple information sources under competition
2023, Operations Research LettersInefficiency in stochastic queueing systems with strategic customers
2021, European Journal of Operational ResearchProvisioning of ad-supported cloud services: The role of competition
2018, Performance EvaluationCitation Excerpt :Note that both the above models capture the impact of congestion on the latency experienced by a user. The use of the M/M/1 latency function is standard in the literature (see, for example, [20,25,11]). Our load-based latency models are novel to the best of our knowledge (though more general models have been considered for worst-case analysis in network economics; see, for example, [26]).
Price of anarchy in a linear-state stochastic dynamic game
2017, European Journal of Operational ResearchCustomer equilibrium and optimal strategies in an M/M/1 queue with dynamic service control
2016, European Journal of Operational ResearchA packet dropping mechanism for efficient operation of M/M/1 queues with selfish users
2016, Computer NetworksCitation Excerpt :There have been also several other papers related to queueing games, albeit with different formulations. Haviv and Roughgarden [17] considered a system with multiple servers with heterogeneous service rates. Arrivals from customers are routed to one of the servers, and the routing decisions are analyzed based on NE or social optimization schemes.