The price of anarchy in an exponential multi-server

doi:10.1016/j.orl.2006.09.005

Operations Research Letters

Volume 35, Issue 4, July 2007, Pages 421-426

https://doi.org/10.1016/j.orl.2006.09.005 Get rights and content

Abstract

We consider two criteria for routing selection in a multi-server service station: the equilibrium and social optimization. The ratio between the average mean waiting times in these two routings is called the price of anarchy (PoA). We show that the worst-case PoA is precisely the number of servers.

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 $μ_{i}$ be the service rate of server i, $1 ⩽ i ⩽ n$ . Assume without loss of generality that $μ_{1} ⩾ μ_{2} ⩾ \dots ⩾ μ_{n} > 0$ . For convenience assume that $μ_{n + 1} = 0$ . Denote $\sum_{j = 1}^{i} μ_{j}$ by $μ_{(i)}$ . There is a single Poisson arrival process with rate $λ$ . To guarantee stability, we assume that $λ < μ_{(n)}$ .

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)

T. Roughgarden
The price of anarchy is independent of the network topology
J. Comput. Syst. Sci.
(2003)
C.H. Bell et al.
Individual versus social optimization in the allocation of customers to alternative servers
Manage. Sci.
(1983)
A. Czumaj
Selfish routing on the Internet
S.C. Dafermos et al.
The traffic assignment problem for a general network
J. Res. Nat. Bur. Stand. Ser. B
(1969)
R. Feldmann et al.
Selfish routing in non-cooperative networks: a survey

There are more references available in the full text version of this article.

Cited by (59)

Price of Anarchy with multiple information sources under competition
2023, Operations Research Letters
We characterize the Price of Anarchy (PoA) in a single channel under the presence of K competing sources. As performance metric we consider the Age of Information, which measures the freshness of information in a remote system. In our main results we show that when the service times of all sources are equal the PoA is $2 - \frac{1}{K}$ , and that otherwise the PoA is unbounded from above. Numerical computations show that the PoA increases with the disparity of the service rates.
Inefficiency in stochastic queueing systems with strategic customers
2021, European Journal of Operational Research
Provisioning of ad-supported cloud services: The role of competition
2018, Performance Evaluation
Citation 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]).
Motivated by cloud services, we consider the interplay of network effects, congestion, and competition in ad-supported services. We study the strategic interactions between competing service providers and a user base, modeling congestion sensitivity and two forms of positive network effects: network effects that are either “firm-specific” or “industry-wide.” Our analysis reveals that users are generally no better off due to the competition in a marketplace of ad-supported services. Further, our analysis highlights an important contrast between firm-specific and industry-wide network effects: Firms can coexist in a marketplace with industry-wide network effects, but near-monopolies tend to emerge in marketplaces with firm-specific network effects.
Price of anarchy in a linear-state stochastic dynamic game
2017, European Journal of Operational Research
We consider a linear-state dynamic game played over an event tree and determine analytically the price of anarchy (PoA), which is given by the ratio of player’s outcome in the cooperative game to her outcome in the noncooperative game. Next, we illustrate our findings in the context of a pollution control problem. We conduct a sensitivity analysis to assess the impact on PoA, and its lower and upper bounds, of varying the different parameter values.
Customer equilibrium and optimal strategies in an M/M/1 queue with dynamic service control
2016, European Journal of Operational Research
We consider the problem of customer equilibrium strategies in an M/M/1 queue under dynamic service control. The service rate switches between a low and a high value depending on system congestion. Arriving customers do not observe the system state at the moment of arrival. We show that due to service rate variation, the customer equilibrium strategy is not generally unique, and derive an upper bound on the number of possible equilibria. For the problem of social welfare optimization, we numerically analyze the relationship between the optimal and equilibrium arrival rates as a function of various parameter values, and assess the level of inefficiency via the price of anarchy measure. We finally derive analytic solutions for the special case where the service rate switch occurs when the queue ceases to be empty.
A packet dropping mechanism for efficient operation of M/M/1 queues with selfish users
2016, Computer Networks
Citation 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.
We consider a fundamental game theoretic problem concerning selfish users contributing packets to an M/M/1 queue. In this game, each user controls its own input rate so as to optimize a desired tradeoff between throughput and delay. We first show that the original game has an inefficient Nash Equilibrium (NE), with a Price of Anarchy (PoA) that scales linearly or worse in the number of users. In order to improve the outcome efficiency, we propose an easily implementable mechanism design whereby the server randomly drops packets with a probability that is a function of the total arrival rate. We show that this results in a modified M/M/1 queueing game that is an ordinal potential game with at least one NE. In particular, for a linear packet dropping function, which is similar to the Random Early Detection (RED) algorithm used in Internet Congestion Control, we prove that there is a unique NE. We also show that the simple best response dynamic converges to this unique equilibrium. Finally, for this scheme, we prove that the social welfare (expressed either as the summation of utilities of all players, or as the summation of the logarithm of utilities of all players) at the equilibrium point can be arbitrarily close to the social welfare at the global optimal point, i.e. the PoA can be made arbitrarily close to 1. We also study the impact of arrival rate estimation error on the PoA through simulations.

View all citing articles on Scopus

View full text

The price of anarchy in an exponential multi-server

Abstract

Introduction

Section snippets

The model and preliminaries

Main results

Acknowledgments

J. Comput. Syst. Sci.

Individual versus social optimization in the allocation of customers to alternative servers

Manage. Sci.

Selfish routing on the Internet

The traffic assignment problem for a general network

J. Res. Nat. Bur. Stand. Ser. B

Selfish routing in non-cooperative networks: a survey