We study a mean-field approximation of the M/M/\(\infty \) queueing system. The problem we deal is quite different from standard games of congestion as we consider the case in which higher congestion results in smaller costs per user. This is motivated by a situation in which some TV show is broadcast so that the same cost is needed no matter how many users follow the show. Using a mean-field approximation, we show that this results in multiple equilibria of threshold type which we explicitly compute. We further derive the social optimal policy and compute the price of anarchy. We then study the game with partial information and show that by appropriate limitation of the queue-state information obtained by the players, we can obtain the same performance as when all the information is available to the players. We show that the mean-field approximation becomes tight as the workload increases, thus the results obtained for the mean-field model well approximate the discrete one.
Notes
The work of the first author was supported by the NCN Grant No. DEC- 2011/03/B/ST1/00325. The work of the second author was partly supported by the CONGAS European Project FP7-ICT-2011-8-317672, see www.congas-project.eu.
1 Introduction
This paper is devoted to the problem of whether an arrival should queue or not in an M/M/\(\infty \) queue. It is assumed that the cost per customer decreases with the number of customers.
In a wireless context, the M/M/\(\infty \) queue may model the number of calls in a cell with a large capacity. The assumption that the cost per call decreases with the number of calls is typical for a multicast in which the same content is broadcast to all mobiles, so that the cost of the transmission can be shared among the number of calls present (see also [14]).
Advertisement
Our first objective in this paper is to study the structure of both individually and globally optimal policies. Our analysis reveals that there exist threshold type of policies in which an individual is admitted if the number of ongoing calls exceeds some threshold (whose value depends on whether globally or individually optimal policies are considered).
The assumption that the cost decreases with the number of customers distinguish our model from the standard congestion control problems which consider that cost increases with the number of customers. The structure of both globally and individually optimal policies can thus be expected to be quite different than those standard congestion control problems which have been studied for over half a century starting with the seminal paper of Naor [13]. Naor had considered an M/M/1 queue, in which a controller has to decide whether arrivals should enter a queue or not. The objective of his paper was to minimize a weighted difference between the average expected waiting time of those that enter, and the acceptance rate of customers. Naor then considered the individually optimal policy (which can be viewed as a Nash equilibrium in a non-cooperative game among the players) and showed that it is also of a threshold type with a threshold bigger than that of a centralized model. His result revealed that arrivals that join the queue under individual optimal policy wait longer in average compared to the global optimal policy. Finally, he showed that there exists some toll such that if it is imposed on arrivals for joining the queue, then the threshold value of the individually optimal policy can be made to agree with the socially optimal one. Since this seminal work of Naor there has been a huge amount of research that extend the model: more general inter-arrival and service times have been considered, more general networks, other objective functions and other queuing disciplines have also been considered, see e.g., [2, 4, 8‐10, 16‐18, 21] and references therein.
The importance of the fact that a threshold policy is optimal is that in order to control arrivals we only need partial information—in fact we only need a signal to indicate whether the queue length exceeds or not the threshold value \({\varPsi }\). The fact that this much simpler information structure is sufficient for obtaining the same performance as in the full information case motivates us to study the performance of threshold policy and related optimization issues for a non-cooperative game with partial information setting. We first study the full information setting where each individual is only optimizing its own cost and explicitly obtain that there exists a plethora of threshold type of symmetric Nash equilibrium (NE) strategy profiles. Subsequently, we compare the social cost under NE strategy profile with the globally optimal social cost. Then, we consider the individual optimization problem with partial information, where we send a green signal if the queue length exceeds the value \({\varPsi }\) and a red signal otherwise and each individual player will select strategy in order to optimize its own social cost. We note that by using this signaling approach instead of providing full state information, users cannot choose any threshold policy with parameter different than \({\varPsi }\), and so in the individual optimization case, one could hope that by determining the signaling according to the value \({\varPsi }\) that minimizes the social cost, one would obtain the socially optimal performance, i.e., the global optimal cost will be achieved. We show that this is not the case here; in fact, we observe that as in [3], where similar approach was proposed for an M/M/1 queuing system, the performance obtained under the best possible signaling policy (in the partial information case) achieves the same performance as equilibrium under the full information.
We study here a simplified mean-field limit of the M/M/\(\infty \) queuing system rather than the actual discrete model since on one hand it is much simpler to handle and solve than the original discrete problem (we obtain closed-form formulas for all the equilibria) and on the other hand the approximation becomes tight as the workload increases. To show that, in this paper we establish the convergence of the game to its mean-field limit under appropriate conditions.
Advertisement
The model and some results from Sects. 4, 8 and 9 appeared in conference proceedings as [20].
The organization of the paper is as follows: We introduce the discrete model in Sect. 2 and its mean-field approximation in Sect. 3. In Sect. 4, we find equilibria of the mean-field model, while in Sect. 5 its social optimum. In Sect. 6 we study the version of the game with partial information. In Sect. 7, we show that the information can be limited without affecting the performance. In Sect. 8, we establish the convergence of discrete models to the mean-field one as the workload increases. We numerically evaluate the threshold policies in Sect. 9. Finally, we conclude the paper with some remarks in Sect. 10.
2 The Model
2.1 Discrete Model
We consider a service facility in which an arriving customer can observe the length of the queue (\(X_t\)) upon arrival. We interchangeably denote \(X_t\) as system state. The value of service is \(\gamma \), and the cost of spending time in service can be computed as an integral of the cost function \(c(\cdot )\) over the service time with \(c(\cdot )\)—a continuous decreasing function of the number of users in the queue. An arriving customer can either join the queue or leave without being served. The decision is made upon arrival. The situation is modeled as a M/M/\(\infty \) system with incoming rate \({\uplambda }\) and service rate \(\mu \).
A customer k arriving at time \(t_k\) chooses whether to enter the queue (E) or not (N). It follows that the set of pure actions for any customer is \(V=\{E,N\}\). Since the decision that he makes is based on the length of the queue, a policy (or a strategy) of any customer will be a mapping1\(\pi _k{:}\,S\rightarrow {\varDelta }(V)\) (since the set V is only a two-point set, we will identify \(\pi _k\) with a function from \(\mathbb {N}\) to [0, 1], describing the probability it assigns to action E), where \(S\subset \mathbb {R}\) denotes the set of possible system states (in the discrete model \(S=\mathbb {N}\)). In what will follow, we will assume that the users limit their policies to the sets of so-called impulse or threshold policies, defined below.
Definition 1
A policy \(\pi _k\) of a user is called an impulse policy if there are finitely many points \(x_1,\ldots , x_n\in S\), with \(x_0:=\inf S\), \(x_{n+1}:=\sup S\), such that \(\pi _k\) is constant on any interval \((x_k,x_{k+1})\), \(k=0,\ldots ,n\).
A subclass of the set of impulse policies with very simple structure are threshold policies.
Definition 2
A policy \(\pi _k\) of a user is called an \([{\varTheta },q]\)-threshold policy if
At time t, an incoming client who employs this policy joins the system if the queue length, \(X_{t}\), is bigger than \({\varTheta }\), while if \(X_t={\varTheta }\) he does so with probability q. Otherwise he never joins the queue.
The cost of a user k arriving at time \(t_k\) is defined as follows:
For each multi-policy \({\varvec{{\pi }}}=\left( \pi _1,\pi _2,\ldots \right) \), let \([\pi '_k,{\varvec{{\pi }}}^{-k}]\) be the policy which replaces \(\pi _k\) by \(\pi '_k\) in \({\varvec{{\pi }}}\). Now we are ready to define the solution we will be looking for:
Definition 3
A policy \(\pi _k\) is an optimal response for user k against a multi-policy \({\varvec{{\pi }}}\) if
A multi-policy \({{\varvec{{\pi }}}^*}=(\pi ^*_1,\pi ^*_2,\ldots )\) is a Nash equilibrium (NE) if policy of every user k is an optimal response for user k against \({{\varvec{{\pi }}}^*}\), for every k. If inequalities (2) are true up to some \(\varepsilon >0\), we say that \({{\varvec{{\pi }}}^*}\) is an \(\varepsilon \)-NE.
3 Fluid Model
In what follows, we will mostly analyze the fluid approximation, which can be viewed as the weak limit of the system (scaled in a proper way) as the arrival rate of players goes to infinity (see e.g., [19]). Now, we describe the fluid model.
The system state (the length of the queue) \(X_t\in \mathbb {R}^+\). Consequently, the policies of the players are defined on \(\mathbb {R}^+\). The customers arrive at the queue according to a fluid process with rate \({\uplambda }\). As each of them uses some policy \(\pi _k\), the real incoming rate at time t is \(\overline{{\varvec{{\pi }}}}(X_t){\uplambda }\) where \(\overline{{\varvec{{\pi }}}}(X_t)\) is the average strategy of the arriving users. Each of them stays in the queue an exponentially distributed time with parameter \(\mu \), and so the outflow is according to a fluid process with rate \(\mu X_t\). This can be described as the following ODE:
Since there are infinitely many players in the game now, we encounter problems with defining the multi-policies. For that reason, we assume that in multi-policy \({\varvec{{\pi }}}\) all the players use the same policy \(\pi \). If we want to write that only one player, say player k changes his policy to some \(\pi '_k\), we write that players apply policy \([{\varvec{{\pi }}}^{-k},\pi '_k]\), meaning that each player uses policy \(\pi \) except player k. Also note that the game is symmetric since each player has the same payoff function and strategy space, and thus, it is very difficult to implement an asymmetric NE—we elucidate the inherent complications considering only two players: If in an NE \(\pi _{1}^{*}\ne \pi _2^{*}\), then, by the symmetric nature of the game, \((\pi _2^{*},\pi _1^{*})\) is also an NE. If player 2 knows that player 1 selects \(\pi ^{*}\) (\(\pi _2^{*}\), respectively), then the optimal response for player 2 is to select \(\pi _2^{*}\) (\(\pi _1^{*}\), respectively), but player 2 cannot know the selection of player 1 due to the non-cooperation between them. Under symmetric NE, all players select the same strategy and thus the above complication is somewhat alleviated. Moreover, \(\overline{{\varvec{{\pi }}}}\) is not always well defined, but in such a case \(\overline{{\varvec{{\pi }}}}(X_t)\equiv \pi (X_t)\). Also with these assumptions, both the cost and the equilibrium can be defined as in the discrete model.
4 Equilibria of the Fluid Model
In this section, we characterize the equilibrium points of our game. We begin by characterizing the evolution of the system state in case all the users apply the same impulse policy.
Lemma 1
Suppose all the players (except maybe one) apply the same impulse policy \(\pi \). Then if the initial state of the system is \(x_0\), then \(X_t\) is continuous in t for any \(x_0\) and is non-decreasing in \(x_0\).
Proof
It is clear that for \(\overline{{\varvec{{\pi }}}}\equiv \pi \) having finitely many discontinuity points, the (non-classical) solution to the equation (3) is well defined a.e. and continuous in t.
Next, suppose that \(x_0<x_0'\) and there exists a s such that2\(X_s[x_0]>X_s[x_0']\). \(X_t\) is continuous in t, thus by the intermediate value property there exists a \(t^*<s\) such that \(X_{t^*}[x_0]=X_{t^*}[x_0']\). But in both cases and at each time all users apply the same policy \(\pi \), depending only on the current state of the system, thus for any \(t>t^*\)\(X_{t}[x_0]=X_{t}[x_0']\), which is a contradiction, as we assumed that \(X_s[x_0]>X_s[x_0']\). \(\square \)
We have one immediate corollary of the above lemma.
Corollary 1
The expected cost of a player joining the queue at time \(t_k\), when all the other players apply policy \(\pi \)
when \(\sigma _k\sim \,\textit{Exp}\,(\mu )\), is decreasing in \(X_{t_k}\).3
Note that in the above corollary we have replaced \(x_0\) with \(X_{t_k}\). This is justified, as the coefficients of (3) depend on t only through \(X_t\). Corollary 1 has an important consequence which is stated in the lemma below:
Lemma 2
Any best response to a symmetric impulse multi-strategy \({\varvec{{\pi }}}\) is a threshold strategy. Moreover, the best response is unique up to the value of q [see (1)].
Proof
A player k arriving at time \(t_k\) has only two pure actions: to enter the queue (E) or not to enter the queue (N). When he uses the former, his cost is
with \(\sigma _k\sim \,\mathrm{Exp}\,(\mu )\), which is by Corollary 1 decreasing in \(X_{t_k}\). On the other hand, when k uses action N, his cost is 0. Thus, if k prefers to use action E for \(X_{t_k}=x_1\), he will also prefer it for \(X_{t_k}=x_2>x_1\). Similarly, if he prefers to use N for \(X_{t_k}=x_2\), he will also prefer it for \(X_{t_k}=x_1<x_2\). Finally, as the cost of using E is strictly decreasing in \(X_{t_k}\), there may only exist one point where k is indifferent between E and N and so he may choose to randomize. Moreover, in any other point, the best response is uniquely determined. \(\square \)
An immediate, but very important consequence of Lemma 2 is the following:
Corollary 2
In any symmetric4 equilibrium to our queuing game, any player uses a threshold policy.
Remark 1
Note that the equilibrium specifies the action to take at any state, including states that are in practice never reached. If a state x is never visited, then any variation of the equilibrium at states larger than x will not change the performance of any player. Yet since we allow for any initial state, there may be customers that will find the system at states that are transient and will not be visited again. Therefore, specifying the equilibrium in such states is considered to be important in game theory. Equilibria that are specified in all states including transient ones are known as perfect equilibria. It can also be shown that such equilibria are good approximations of those that we obtain in case that there is some sufficiently small constant uncontrolled inflow. This follows from [6].
Assuming that all (except maybe one) users apply the same \([{\varTheta },q]\)-threshold strategy, we may write explicitly the evolution of the system state \(X_t\):
Lemma 3
Suppose the initial state of the system is \(x_0\) and that all the users (except maybe one) apply the \([{\varTheta },q]\)-threshold policy. Then the system state at time t can be explicitly written as:
(a)
If \(x_0>{\varTheta }\) and \({\varTheta }\le \frac{{\uplambda }}{\mu }\) or \(x_0={\varTheta }<\frac{q{\uplambda }}{\mu }\) then
Note that, when \(p=1\), this means that \(X_t\rightarrow \frac{{\uplambda }}{\mu }\) monotonically when \(t\rightarrow \infty \). Thus, if \(x_0>{\varTheta }\) and \(\frac{{\uplambda }}{\mu }>{\varTheta }\), \(X_t\) never leaves the region where policy \(\pi \) prescribes to use action E, and so
Similarly, note that for \(p=0\), \(X_t\) decreases monotonically to 0, thus when \(x_0<{\varTheta }\), \(X_t\) never leaves the region where policy \(\pi \) prescribes to use action N, and so (5) reduces to
Now suppose that \(x_0>{\varTheta }>\frac{{\uplambda }}{\mu }\). Then \(X_t\) starts in the region where \(\pi \) prescribes to use action E with probability one, which implies that its trajectory decreases toward \(\frac{{\uplambda }}{\mu }\) until time \(\overline{t}_{(x_0,{\varTheta })}\) when it reaches the threshold \({\varTheta }\). From then on \(\pi \) prescribes to use action N with probability 1. It is easy to compute that for \(t\le \overline{t}_{(x_0,{\varTheta })}\),
Since by definition \(\overline{t}_{(x_0,{\varTheta })}\) is such that \(X_{\overline{t}_{(x_0,{\varTheta })}}={\varTheta }\), we easily obtain that \(\overline{t}_{(x_0,{\varTheta })}=\frac{1}{\mu }\log \frac{x_0-\frac{{\uplambda }}{\mu }}{{\varTheta }-\frac{{\uplambda }}{\mu }}\). Then, for \(t\ge \overline{t}_{(x_0,{\varTheta })}\), \(X_t\) has to satisfy (5) with \(p=0\) and \(t_0=\overline{t}_{(x_0,{\varTheta })}\) instead of 0, which gives
Finally, when \(x_0={\varTheta }\), \(X_t\) satisfies at \(t=0\) (5) with \(p=q\). If \(x_0=\frac{q{\uplambda }}{\mu }\), by (5) \(X_t\equiv \frac{q{\uplambda }}{\mu }\). Otherwise if \(x_0<\frac{q{\uplambda }}{\mu }\), \(X_t\) moves upwards and for \(t>0\) behaves like when \(x_0>{\varTheta }\), while if \(x_0>\frac{q{\uplambda }}{\mu }\), \(X_t\) moves downwards and for \(t>0\) behaves like when \(x_0<{\varTheta }\). \(\square \)
Now, to simplify the notation, we will make use of the fact that all the players use threshold policies. Let us define
to be the expected service cost for player k if he enters the queue when its state is x and all the players except k apply a \([{\varTheta }_{-k},q_{-k}]\)-threshold policy. \(\widehat{C}_k\) can be written as
Suppose \(x>{\varTheta }_{-k}\) and \({\varTheta }_{-k}\le \frac{{\uplambda }}{\mu }\) or \(x={\varTheta }_{-k}<\frac{q_{-k}{\uplambda }}{\mu }\). Then by (a) of Lemma 3
In next two lemmas, we characterize the best responses to any given threshold strategies.
Lemma 5
\([{\varTheta }_k,q_k]\)-threshold policy is a best response of player k to a \([{\varTheta }_{-k},q_{-k}]\)-threshold policy used by all the others if \({\varTheta }_k\) is obtained by finding the unique solution to the equation
and \(q_k=1\) if the first inequality is satisfied for \(x={\varTheta }_k\), while \(q_k=0\) if the second one is satisfied for \(x={\varTheta }_k\).
Proof
First note that \(\widehat{C}_k\left( x,({\varTheta }_{-k},q_{-k})\right) -\gamma \) is exactly the expected cost of player k if he joins the queue when its state is x, while his cost when he does not join is 0. Moreover, the expected cost of player joining the queue is by Corollary 1 monotone decreasing function of x. Thus, Eq. (6) may have at most one solution, and the cost of joining the queue for \(x>{\varTheta }_k\) is negative, that for \(x<{\varTheta }_k\) is positive, while that for \(x={\varTheta }_k\) is 0, regardless of \(q_k\). Thus \([{\varTheta }_k,q_k]\)-threshold policy always gives player k the smallest cost available.
Similarly, when (6) has no solutions, from the monotonicity of the cost \(\widehat{C}_k\left( x,({\varTheta }_{-k},q_{-k})\right) -\gamma \), there must exist exactly one \({\varTheta }_k\) such that \(\widehat{C}_k\left( x,({\varTheta }_{-k},q_{-k})\right) -\gamma >0\) for \(x<{\varTheta }_k\) and \(\widehat{C}_k\left( x,({\varTheta }_{-k},q_{-k})\right) -\gamma <0\) for \(x>{\varTheta }_k\). Now we can repeat the arguments from the proof of the first part of the lemma, to show that \([{\varTheta }_k,1]\)- or \([{\varTheta }_k,0]\)-threshold policy is the best response to \([{\varTheta }_{-k},q_{-k}]\)-threshold policy of the others in this case. \(\square \)
Lemma 6
Let \([{\varTheta }_k,q_k]\)-threshold policy be a best response of player k to a \([{\varTheta }_{-k},q_{-k}]\)-threshold policy used by all the others and define \(\underline{{\varTheta }}\) and \(\overline{{\varTheta }}\) as the unique solutions to the following equations6:
Then \({\varTheta }_k\) and \(q_k\) satisfy the following:
(a)
If \(\gamma \in \left( 0,\frac{1}{\mu }\lim _{u\rightarrow \infty }c(u)\right] \) then \({\varTheta }_k=\infty \) and \(q_k\) is arbitrary (which means that the best response is a policy never prescribing to enter the queue).
(b)
If \(\gamma \in \left( \frac{1}{\mu }\lim _{u\rightarrow \infty }c(u),\frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u\right) \) then
If \(\gamma \ge \frac{1}{\mu }c(0)\) then \({\varTheta }_k=0\) and \(q_k=1\) (which means that the best response is a policy always prescribing to enter the queue).
Proof
To show (a) first note that any form of \(\widehat{C}_k\) described in Lemma 4 is bounded below by \(\frac{1}{\mu }\inf _{u\ge 0}c(u)\), which equals \(\frac{1}{\mu }\lim _{u\rightarrow \infty }c(u)\), as c is a strictly decreasing function. Thus, in case \(\gamma \le \frac{1}{\mu }\lim _{u\rightarrow \infty }c(u)\), also \(\gamma <\widehat{C}_k\left( x,({\varTheta }_{-k},q_{-k})\right) \) for any value of x, thus (7) is satisfied for \({\varTheta }_k=\infty \). This means that the strategy never prescribing player k to enter the queue is his best response to the \([{\varTheta }_{-k},q_{-k}]\)-threshold policy used by all the others.
Now suppose the assumptions of part (b) of the lemma are satisfied. Note that the function
is continuous on \(\mathbb {R}^+\) and satisfies \(\lim _{x\rightarrow 0^+}\overline{C}(x)=\frac{1}{{\uplambda }}\int _{0}^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u\) and \(\lim _{x\rightarrow \infty }\overline{C}(x)=\frac{1}{\mu }\lim _{u\rightarrow \infty }c(u)\). Thus, by the intermediate value property, and since
is continuous on \(\mathbb {R}^+\) and satisfies \(\underline{C}\left( \frac{{\uplambda }}{\mu }\right) =\frac{1}{{\uplambda }}\int _{0}^{\frac{{\uplambda }}{\mu }}c(u)\; \mathrm{d}u\) and \(\lim _{x\rightarrow \infty }\underline{C}(x)=\lim _{u\rightarrow \infty }c(u)\). Thus, again by the intermediate value property, and since \(\gamma \in \Big ( \frac{1}{\mu }\lim _{u\rightarrow \infty }c(u),\frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\, \mathrm{d}u\Big )\), there exists an x such that \(\underline{C}(x)=\gamma \), which is how \(\underline{{\varTheta }}\) is defined. Moreover, \(\underline{{\varTheta }}\) is always bigger than \(\frac{{\uplambda }}{\mu }\).
Next note that by Lemma 4, \(\widehat{C}_k\left( x,({\varTheta }_{-k},q_{-k})\right) \) equals \(\overline{C}(x)\) if \(x>{\varTheta }_{-k}\) and \({\varTheta }_{-k}\le \frac{{\uplambda }}{\mu }\) or \(x={\varTheta }_{-k}<\frac{q_{-k}{\uplambda }}{\mu }\), and \(\underline{C}(x)\) if \(x<{\varTheta }_{-k}\) or \(x={\varTheta }_{-k}>\frac{q_{-k}{\uplambda }}{\mu }\). Thus by Lemma 5, \({\varTheta }_k=\overline{{\varTheta }}\) for \({\varTheta }_{-k}\le \min \left\{ \overline{{\varTheta }},\frac{{\uplambda }}{\mu }\right\} \), \({\varTheta }_k={\varTheta }_{-k}\) for \(\min \left\{ \overline{{\varTheta }},\frac{{\uplambda }}{\mu }\right\} \le {\varTheta }_{-k}\le \frac{{\uplambda }}{\mu }\), \({\varTheta }_k\ge {\varTheta }_{-k}\) for \(\frac{{\uplambda }}{\mu }<{\varTheta }_{-k}\le \underline{{\varTheta }}\) and \({\varTheta }_k=\underline{{\varTheta }}\) for \({\varTheta }_{-k}\ge \underline{{\varTheta }}\). The values of \(q_k\) for \({\varTheta }_{-k}\le \frac{{\uplambda }}{\mu }\) depend on the relation between \({\varTheta }_{-k}\) and \(\frac{q_{-k}{\uplambda }}{\mu }\): If the former is smaller, for \({\varTheta }_k={\varTheta }_{-k}\) we are in the set where \(\widehat{C}_k\left( {\varTheta }_k,({\varTheta }_{-k},q_{-k})\right) =\overline{C}({\varTheta }_k)<\gamma \), and so \(q_k=1\). If \({\varTheta }_{-k}=\frac{q_{-k}{\uplambda }}{\mu }\), we are in the set where \(\widehat{C}_k\left( {\varTheta }_k,({\varTheta }_{-k},q_{-k})\right) =\frac{1}{\mu }c({\varTheta }_{-k})\), thus according to Lemma 5 the value of \(q_k\) depends on the relation between \(\frac{1}{\mu }c({\varTheta }_{-k})\) and \(\gamma \), exactly as it is written in Lemma 6. Finally if \({\varTheta }_{-k}>\frac{q_{-k}{\uplambda }}{\mu }\), \(\widehat{C}_k\left( {\varTheta }_k,({\varTheta }_{-k},q_{-k})\right) =\underline{C}({\varTheta }_k)>\gamma \), and so \(q_k=0\).
To finish the proof of part (b) of the Lemma, we need to show that for \({\varTheta }_{-k}\in \left( \frac{{\uplambda }}{\mu },\underline{{\varTheta }}\right) \), \({\varTheta }_k>{\varTheta }_{-k}\). To do that, it is enough to prove that for any fixed \({\varTheta }_{-k}\in \left( \frac{{\uplambda }}{\mu },\underline{{\varTheta }}\right) \), \(\widehat{C}_k\left( x,({\varTheta }_{-k},q_{-k})\right) \) is continuous at \(x={\varTheta }_{-k}\) as a function of x. If it is, then from the fact that for \(x={\varTheta }_{-k}\), \(\widehat{C}_k\left( x,({\varTheta }_{-k},q_{-k})\right) =\underline{C}(x)>\gamma \), also \(\widehat{C}_k\left( x+\varepsilon ,({\varTheta }_{-k},q_{-k})\right) >\gamma \) for some \(\varepsilon >0\), and thus \({\varTheta }_k\) defined by Lemma 5 is not smaller than \({\varTheta }_{-k}+\varepsilon \). Thus fix \({\varTheta }_{-k}\in \left( \frac{{\uplambda }}{\mu },\underline{{\varTheta }}\right) \) and take \(x_n\rightarrow {\varTheta }_{-k}^+\). For such \(x_n\),
To prove part (c) of the lemma note that since now \(\gamma \in \left[ \frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\, \mathrm{d}u,\frac{1}{\mu }c(0)\right) \), the equation \(\overline{C}(x)=\gamma \) has no solutions. Moreover, its LHS is always smaller than its RHS. On the other hand, since \(\lim _{x\rightarrow 0^+}\underline{C}(x)=\frac{1}{\mu }c(0)\) and \(\underline{C}\left( \frac{{\uplambda }}{\mu }\right) =\frac{1}{{\uplambda }}\int _{0}^{\frac{{\uplambda }}{\mu }}c(u)\; \mathrm{d}u\), by the intermediate value property the equation \(\underline{C}(x)=\gamma \) has a unique solution \(\underline{{\varTheta }}\in \left( 0,\frac{{\uplambda }}{\gamma }\right) \). Next, again by Lemma 4, \(\widehat{C}_k\left( x,({\varTheta }_{-k},q_{-k})\right) \) equals \(\overline{C}(x)\) if \(x>{\varTheta }_{-k}\) and \({\varTheta }_{-k}\le \frac{{\uplambda }}{\mu }\) or \(x={\varTheta }_{-k}<\frac{q_{-k}{\uplambda }}{\mu }\), and \(\underline{C}(x)\) if \(x<{\varTheta }_{-k}\) or \(x={\varTheta }_{-k}>\frac{q_{-k}{\uplambda }}{\mu }\), and thus by Lemma 5, \({\varTheta }_k={\varTheta }_{-k}\) for \({\varTheta }_{-k}\le \underline{{\varTheta }}\) and \({\varTheta }_k=\underline{{\varTheta }}\) for \({\varTheta }_{-k}>\underline{{\varTheta }}\). The choice of \(q_k\) is made exactly as in part (b) of the lemma.
Finally, suppose that \(\gamma \ge \frac{1}{\mu }c(0)\). Then for any value of x, \(\widehat{C}\left( x,({\varTheta }_{-k},q_{-k})\right) <\gamma \), and thus the optimal response of player k to the \([{\varTheta }_{-k},q_{-k}]\)-threshold strategy of all the others is always to join the queue. \(\square \)
Now we are ready to state the main result of this section.
Theorem 1
The game under consideration always has a symmetric equilibrium where each of the players uses the same \([{\varTheta },q]\)-threshold strategy. Moreover:
(a)
If \(\gamma \in \left( 0,\frac{1}{\mu }\lim _{u\rightarrow \infty }c(u)\right] \) then the equilibrium is unique, with \({\varTheta }=\infty \), which means that the equilibrium policies prescribe every user never to enter the queue.
(b)
If \(\gamma \in \left( \frac{1}{\mu }\lim _{u\rightarrow \infty }c(u),\frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u\right) \) then there are infinitely many equilibria, whose forms depend on the relation between \(\overline{{\varTheta }}\) and \(\frac{{\uplambda }}{\mu }\):
(b1)
If \(\overline{{\varTheta }}<\frac{{\uplambda }}{\mu }\) then there are equilibria of five types: \({\varTheta }=\overline{{\varTheta }}\) and any \(q>\frac{\overline{{\varTheta }}\mu }{{\uplambda }}\); \({\varTheta }={\varTheta }^*\), with \({\varTheta }^*\) satisfying \(c({\varTheta }^*)=\mu \gamma \) and \(q=\frac{{\varTheta }^*\mu }{{\uplambda }}\); \({\varTheta }=\underline{{\varTheta }}\) and any \(q\in [0,1]\); any \({\varTheta }\in \left[ \overline{{\varTheta }},\frac{{\uplambda }}{\mu }\right] \) and \(q=0\); any \({\varTheta }\in \left[ \overline{{\varTheta }},\frac{{\uplambda }}{\mu }\right] \) and \(q=1\).
(b2)
If \(\overline{{\varTheta }}=\frac{{\uplambda }}{\mu }\) then either \({\varTheta }=\overline{{\varTheta }}\) and \(q\in \{ 0,1\}\) or \({\varTheta }=\underline{{\varTheta }}\) and q is any number from [0, 1].
(b3)
If \(\overline{{\varTheta }}>\frac{{\uplambda }}{\mu }\) then either \({\varTheta }=\underline{{\varTheta }}\) and q is an arbitrary number from [0, 1] or \({\varTheta }=\frac{{\uplambda }}{\mu }\) and \(q=0\).
(c)
If \(\gamma \in \left[ \frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u,\frac{1}{\mu }c(0)\right) \) then there are infinitely many equilibria of three types: with \({\varTheta }\in [0,\underline{{\varTheta }}]\) and \(q=0\); with \({\varTheta }\in [0,\underline{{\varTheta }}]\) and \(q=1\); with \({\varTheta }={\varTheta }^*\) satisfying \(c({\varTheta }^*)=\mu \gamma \) and \(q=\frac{{\varTheta }^*\mu }{{\uplambda }}\).
(d)
If \(\gamma \ge \frac{1}{\mu }c(0)\) then the equilibrium is unique, with \({\varTheta }=0\) and \(q=1\), which means that the equilibrium policies prescribe every user to always enter the queue.
Proof
A strategy for any player k will induce a symmetric equilibrium if it is a best response to itself. Below we analyze which strategies may satisfy this condition.
In case (a) it is obvious by (a) of Lemma 6 that the policy prescribing never to join the queue is always the best response to itself, and since this is the only best response to any policy, this is the only possible equilibrium.
In case (b) \({\varTheta }\) has to be either in interval \(\left[ \min \{\overline{{\varTheta }},\frac{{\uplambda }}{\mu }\},\frac{{\uplambda }}{\mu }\right] \) or equal to \(\underline{{\varTheta }}\). In the latter case, it is clear that for any q the \([{\varTheta },q]\)-threshold policy will be the best response to itself. In the former one, q and \({\varTheta }\) must satisfy one of the following conditions:
\(q=0\) and \({\varTheta }>\frac{q{\uplambda }}{\mu }=0\), which is always true for \({\varTheta }\ge \min \left\{ \overline{{\varTheta }},\frac{{\uplambda }}{\mu }\right\} \), so \([{\varTheta },0]\)-threshold policies form equilibria in this case.
\(q=1\) and \({\varTheta }<\frac{q{\uplambda }}{\mu }=\frac{{\uplambda }}{\mu }\), and so \([{\varTheta },1]\)-threshold policies form equilibria for any \({\varTheta }\in \left[ \min \left\{ \overline{{\varTheta }},\frac{{\uplambda }}{\mu }\right\} ,\frac{{\uplambda }}{\mu }\right) \).
\(q=1\) and \({\varTheta }=\frac{q{\uplambda }}{\mu }=\frac{{\uplambda }}{\mu }\) with \(c\left( \frac{{\uplambda }}{\mu }\right) <\gamma \mu \), which is always true as long as \(\overline{{\varTheta }}<\frac{{\uplambda }}{\mu }\).
\({\varTheta }=\overline{{\varTheta }}<\frac{q{\uplambda }}{\mu }\), which implies that \(q>\frac{\overline{{\varTheta }}\mu }{{\uplambda }}\). It can always be satisfied when \(\overline{{\varTheta }}\) is as assumed, so \([\overline{{\varTheta }},q]\)-threshold policies form an equilibrium in this case.
\({\varTheta }=\frac{q{\uplambda }}{\mu }\in \left[ \overline{{\varTheta }},\frac{{\uplambda }}{\mu }\right] \) and \(c({\varTheta })=\mu \gamma \). Note, however, that by the definition of \(\overline{{\varTheta }}\) and continuity of c, if \(\overline{{\varTheta }}<\frac{{\uplambda }}{\mu }\) then there must exist a solution \({\varTheta }^*\) to the equation \(c({\varTheta })=\mu \gamma \) in \(\left[ \overline{{\varTheta }},\frac{{\uplambda }}{\mu }\right] \), so \({\varTheta }^*\) and \(q=\frac{{\varTheta }^*\mu }{{\uplambda }}\) is an equilibrium. In particular, if \(\overline{{\varTheta }}=\frac{{\uplambda }}{\mu }\), then also \({\varTheta }^*=\frac{{\uplambda }}{\mu }\) and \(q=1\) is one.
In case (c) \({\varTheta }\) has to be in interval \([0,\underline{{\varTheta }}]\) and needs to be related to q in one of the following ways:
\(q=0\) and \({\varTheta }>\frac{q{\uplambda }}{\mu }=0\) or \({\varTheta }=0\) with \(c(0)>\mu \gamma \), which is always true in case (c).
\(q=1\) and \({\varTheta }<\frac{q{\uplambda }}{\mu }=\frac{{\uplambda }}{\mu }\), which is always true, as \({\varTheta }\le \underline{{\varTheta }}<\frac{{\uplambda }}{\mu }\) in this case, which was shown in the proof of Lemma 6.
\({\varTheta }=\frac{q{\uplambda }}{\mu }\le \underline{{\varTheta }}\) and \(c({\varTheta })=\mu \gamma \). Note, however, that by the definition of \(\underline{{\varTheta }}\) and continuity of c, there must exist some \({\varTheta }^*\) in the interval \((0,\underline{{\varTheta }})\) such that \(c({\varTheta }^*)=\mu \gamma \), so \({\varTheta }^*\) and \(q=\frac{{\varTheta }^*\mu }{{\uplambda }}\) is the only equilibrium in this case.
Finally, in case (d) by (d) of Lemma 6 it is obvious that the policy always prescribing to join the queue is the best response to itself. Since this is the only best response to any policy in this case, this is the only possible equilibrium. This ends the proof of the theorem. \(\square \)
Remark 2
It should be noted here that there are multiple equilibria in certain situations. In that case, it is normally not clear which one would prevail. Nevertheless, as the cost of being served is a decreasing function of \({\varTheta }\) and of q for a fixed value of \({\varTheta }\), we may assume that the customers will naturally choose the equilibrium strategies with the biggest values of \({\varTheta }\) and q. In Sect. 5 we will, nevertheless, analyze the social outcome of all the possible equilibria, comparing them to the social optimum.
Remark 3
The number of equilibria can be downsized by considering a stronger equilibrium concept. While there are many NE refinements available, the one best suited to a symmetric population game like the one considered here seems to be that of Evolutionary Stable Strategy (ESS) [12]. Roughly speaking, it is a strategy which not only gives a player the highest payoff when everyone else uses the same strategy, but guarantees that a small fraction of players using different strategy receive lower payoff than the majority sticking to the ESS. Technically this means that \(\pi \) is an Evolutionary Stable Strategy if it satisfies (2) and additionally
It turns out that our game always has an ESS but not all the Nash equilibrium strategies are ESS. More precisely, the equilibrium policies of cases (a) and (d) of Theorem 1 are also ESS, while in cases (b) and (c) we have:
If \(\overline{{\varTheta }}<\frac{{\uplambda }}{\mu }\) then there are infinitely many ESS with \({\varTheta }\in \left[ \overline{{\varTheta }},\frac{{\uplambda }}{\mu }\right] \) and \(q\in \{ 0,1\}\).
(b2)
If \(\overline{{\varTheta }}>\frac{{\uplambda }}{\mu }\) then \(\left[ \frac{{\uplambda }}{\mu },0\right] \)-threshold policy is the unique ESS.
(c)
If \(\gamma \in \left[ \frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u,\frac{1}{\mu }c(0)\right) \) then there are infinitely many ESS with \({\varTheta }\in [0,\underline{{\varTheta }}]\) and \(q\in \{ 0,1\}\).
5 Social Optimum
The social cost associated with some symmetric strategy profile \({\varvec{{\pi }}}\) can be computed using equality
where \(x_{\infty }({\varvec{{\pi }}},x_0)\) denotes the stationary state of the queue when the players apply multi-policy \({\varvec{{\pi }}}\) and initial state of the queue is \(x_0\), while \(\pi _{\infty }(x_0)\) is the limit value of strategy \(\pi \) when time goes to infinity (note that it may have three values, depending on whether the trajectory of X approaches \(x_{\infty }({\varvec{{\pi }}},x_0)\) from above, from below, or is from some point constant).
If we assume that \(\pi \) is a \([{\varTheta },q]\)-threshold policy, \(C(x_0,{\varvec{{\pi }}})\) equals:
Note however that, as it can be clearly seen from Lemma 3, when everyone uses the same threshold policy, the only stationary states possible in the game are 0, \(\frac{{\uplambda }}{\mu }\) and \(\frac{q{\uplambda }}{\mu }\). Moreover, they can by easily deduced from the values of \({\varTheta }\), q and \(x_0\), and thus the following lemma is true.
Lemma 7
Suppose all the players in the game apply the same \([{\varTheta },q]\)-threshold policy \(\pi \). Then social cost function in the game can be computed as follows:
(a)
If \(x_0>{\varTheta }\) and \({\varTheta }\le \frac{{\uplambda }}{\mu }\) or \(x_0={\varTheta }<\frac{q{\uplambda }}{\mu }\) then
In any other case \(\widehat{C}(x_0,({\varTheta },q))=0\).
Proof
If \(x_0>{\varTheta }\) and \({\varTheta }\le \frac{{\uplambda }}{\mu }\) or \(x_0={\varTheta }<\frac{q{\uplambda }}{\mu }\) then by parts (a) of Lemmas 3 and 4, \(X_t=\displaystyle {\frac{{\uplambda }}{\mu }}+\left( x_0-\displaystyle {\frac{{\uplambda }}{\mu }}\right) \mathrm{e}^{-\mu t}\rightarrow _{t\rightarrow \infty }\frac{{\uplambda }}{\mu }=x_{\infty }({\varvec{{\pi }}},x_0)\) and \(\widehat{C}_k(x_{\infty }({\varvec{{\pi }}},x_0),({\varTheta },q))=\frac{1}{\mu }c\left( \frac{{\uplambda }}{\mu }\right) \). Finally \(\pi _{\infty }(x_0)=1\), as either \({\varTheta }<\frac{{\uplambda }}{\mu }\), and so \(\pi =1\) in some neighborhood of \(\frac{{\uplambda }}{\mu }\), or \({\varTheta }=\frac{{\uplambda }}{\mu }<x_0\), and then the trajectory of X approaches \(\frac{{\uplambda }}{\mu }\) from above, where \(\pi \) prescribes to take action E with probability 1. Putting all this together, we get that \(\widehat{C}(x_0,({\varTheta },q))=\frac{1}{\mu }c\left( \frac{{\uplambda }}{\mu }\right) -\gamma =\frac{1}{\mu }\left( c\left( \frac{{\uplambda }}{\mu }\right) -\gamma \mu \right) \).
Next, suppose that \(x_0={\varTheta }=\frac{q{\uplambda }}{\mu }\). Then by parts (c) of Lemmas 3 and 4, \(X_t\equiv \frac{q{\uplambda }}{\mu }\), so this is also its stationary state, with \(\widehat{C}_k\left( \frac{q{\uplambda }}{\mu },({\varTheta },q)\right) =\frac{1}{\mu }c\left( \frac{q{\uplambda }}{\mu }\right) \) and \(\pi _{\infty }\left( \frac{q{\uplambda }}{\mu }\right) =q\). Putting all this in the definition of \(\widehat{C}\), we obtain \(\widehat{C}(x_0,({\varTheta },q))=q\left( \frac{1}{\mu }c\left( \frac{q{\uplambda }}{\mu }\right) -\gamma \right) =\frac{q}{\mu }\left( c\left( \frac{q{\uplambda }}{\mu }\right) -\gamma \mu \right) \).
If \(x_0>{\varTheta }>\frac{{\uplambda }}{\mu }\), by (b) of Lemma 3 for t large enough, \(X_t={\varTheta }\mathrm{e}^{\mu (\overline{t}_{(x_0,{\varTheta })}-t)}\rightarrow _{t\rightarrow \infty }0\). Similarly, if \(x_0<{\varTheta }\) or \(x_0={\varTheta }>\frac{q{\uplambda }}{\mu }\) then by (d) of the same lemma, \(X_t=x_0\mathrm{e}^{-\mu t}\rightarrow _{t\rightarrow \infty }0\), and so in both cases \(x_{\infty }({\varvec{{\pi }}},x_0)=0<{\varTheta }\). This implies either \(x_\infty (\pi ,x_0)<{\varTheta }\) if \({\varTheta }>0\) or \(x_\infty (\pi ,x_0)={\varTheta }\) and \(0=\pi _\infty (x_0)\le \pi (x_\infty (\pi ,x_0))\), and therefore \(\widehat{C}(x_0,({\varTheta },q))=0\). \(\square \)
Using this lemma, we can easily find strategies minimizing the social cost for any \(x_0\).
Theorem 2
(a)
If \(c\left( \frac{{\uplambda }}{\mu }\right) <\gamma \mu \) then the social optimum equals \(\frac{1}{\mu }\left( c\left( \frac{{\uplambda }}{\mu }\right) -\gamma \mu \right) \) and is attained for the strategy profile consisting of [0, 1]-threshold strategies of all the players, prescribing to always join the queue.
(b)
If \(c\left( \frac{{\uplambda }}{\mu }\right) =\gamma \mu \) then the social optimum equals 0 and is attained for any symmetric strategy profile consisting of \([{\varTheta },q]\)-threshold strategies such that \({\varTheta }\ne \frac{q{\uplambda }}{\mu }\).
(c)
If \(c\left( \frac{{\uplambda }}{\mu }\right) >\gamma \mu \) then the social optimum equals 0 and is attained for the strategy profile consisting of \([\infty ,0]\)-threshold strategies of all the players, prescribing never to join the queue.
Proof
Suppose \(c\left( \frac{{\uplambda }}{\mu }\right) <\gamma \mu \). Then \(\frac{1}{\mu }\left( c\left( \frac{{\uplambda }}{\mu }\right) -\gamma \mu \right) <0\) and so it is always more profitable to be in case (a) of Lemma 7 than in case (c). As c is a strictly decreasing function, also \(\frac{q}{\mu }\left( c\left( \frac{q{\uplambda }}{\mu }\right) -\gamma \mu \right) <\frac{1}{\mu }\left( c\left( \frac{{\uplambda }}{\mu }\right) -\gamma \mu \right) \). Thus a strategy profile such that the assumptions of case (a) of Lemma 7 are satisfied for any \(x_0\) minimizes the social cost function then. It is straightforward to see that when all the players use [0, 1]-threshold strategies this is the case.
Next assume that \(c\left( \frac{{\uplambda }}{\mu }\right) =\gamma \mu \). Then \(\frac{1}{\mu }\left( c\left( \frac{{\uplambda }}{\mu }\right) -\gamma \mu \right) =0<\frac{q}{\mu }\left( c\left( \frac{q{\uplambda }}{\mu }\right) -\gamma \mu \right) \), so the social cost is minimized in cases (a) and (c) of Lemma 7. Thus any profile of policies guaranteing that case (b) is never possible, which is equivalent to \({\varTheta }\ne \frac{q{\uplambda }}{\mu }\), is optimal in this case.
Finally let \(c\left( \frac{{\uplambda }}{\mu }\right) >\gamma \mu \). Then \(\frac{1}{\mu }\left( c\left( \frac{{\uplambda }}{\mu }\right) -\gamma \mu \right) >0\) and \(\frac{q}{\mu }\left( c\left( \frac{q{\uplambda }}{\mu }\right) -\gamma \mu \right) >0\), so case (c) of Lemma 7 is better than cases (a) and (b). Using \([\infty ,1]\)-threshold policies guarantees satisfying the assumptions of case (c) for any \(x_0\). \(\square \)
5.1 Price of Anarchy and Price of Stability
A commonly used concept for evaluating the equilibria in any given game is that of Price of Anarchy, introduced by Koustoupias and Papadimitrou [11], which is the ratio between the cost of an equilibrium and that of the optimal solution. As in our game there may exist multiple equilibria, each with a different social cost, we would like to adapt here the concept of two quantities describing quality of equilibria [5]: Price of Anarchy, being the ratio between a worst (in terms of its social cost) equilibrium’s cost and the optimal social cost, and Price of Stability, defined as the ratio between the cost of a best equilibrium and that of the optimal solution. The problem in using these quantities in our model could be that here, unlike in network congestion games, the social cost may be both negative and positive (and in fact it often equals zero). Note, however, that in any situation a player can guarantee himself zero cost, so both in social optimum and in equilibrium it is never positive. This suggests defining Price of Anarchy and Price of Stability in the following manner:
Here \(\mathcal {NE}\) denotes the set of Nash equilibria in the game, while \(\pi _{Opt}\) is an optimal policy profile in the game. Also it is important to note that in both definitions we use conventions that \(\frac{0}{0}=1\) and \(\frac{c}{0}=+\infty \) for a negative value of c, so we treat 0 as \(0^-\).
The following theorems characterize PoA and PoS in our model. They are direct consequences of Theorems 1 and 2, and Lemma 7, and thus we state them without proofs.
Theorem 3
The Price of Anarchy:
(a)
is infinite if \(\gamma \in \left( \frac{1}{\mu } c\left( \frac{{\uplambda }}{\mu }\right) ,\frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u\right) \) or if \(\gamma \in \left[ \frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u,\frac{1}{\mu }c(0)\right) \) and \(x_0\le \underline{{\varTheta }}\);
(b)
equals 1 otherwise.
Theorem 4
The Price of Stability:
(a)
is infinite if \(\gamma \in \left( \frac{1}{\mu } c\left( \frac{{\uplambda }}{\mu }\right) ,\frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u\right) \) and \(x_0<\overline{{\varTheta }}\);
(b)
equals 1 otherwise.
As we can see, both PoA and PoS take only two values, 1 and \(\infty \). This is a consequence of the fact that the social cost of equilibrium happens to be greater than that of optimal solution only if the former equals zero while the latter is negative.
6 Fluid Model with Partial Information
In this section, we assume that the knowledge of each user when he decides on entering the queue is limited to the information whether the state of the queue is above some threshold \({\varPsi }\) or not. Thus instead of \(X_t\in \mathbb {R}^+\), the system state perceived by the players will be \(\overline{X}_t\in \{ 0,1\}\), with \(\overline{X}_t=0\) denoting \(X_t<{\varPsi }\) and \(\overline{X}_t=1\) denoting \(X_t\ge {\varPsi }\). Consequently, the strategies of the players will be of one of the forms EE, EN, NE or NN, where the first letter stands for the strategy in state 0, while the second one for the strategy in state 1. Using arguments from Sect. 4, we can argue that strategy EN will be never used, so for the ease of analysis we will only consider the three remaining ones. It is also important to note that these three strategies can also be interpreted as threshold strategies in the original game, only with the set of thresholds available limited to \(\{ 0,{\varPsi },\infty \}\) (for policies EE, NE and NN, respectively).
We assume that the knowledge of each of the players is limited to the value of the threshold \({\varPsi }\) and the partial information about the state \(\overline{X}_t\). We do not assume they have any information about the distribution of the state, and thus the appropriate solution concept here will be that of robust Nash equilibrium [1, 7]. We define it formally below. Let \(U_0=\{ x\in S: 0\le x<{\varPsi }\}\) and \(U_1=\{ x\in S: {\varPsi }\le x\}\).
Definition 5
A policy \(\pi _k\) is a best robust response for user k against a multi-policy \({\varvec{{\pi }}}\) in the game with partial information if \(\pi _k\) is constant on each of the sets \(U_0\) and \(U_1\) and
for \(s=0,1\) and every policy \(\pi '_k\) of player k.
Definition 6
A multi-policy \({{\varvec{{\pi }}}^*}=(\pi ^*_1,\pi ^*_2,\ldots )\) is a robust Nash equilibrium (RNE) if policy of every user k is a robust best response for user k against \({{\varvec{{\pi }}}^*}\), for every k. If inequalities (9) are true up to some \(\varepsilon >0\), we say that \({{\varvec{{\pi }}}^*}\) is an \(\varepsilon \)-RNE.
In other words, the users will minimize their costs assuming that the actual state of the queue at the time they decide on entering the queue is the one for which the cost of joining the queue is the highest. By Corollary 1 this cost is decreasing in \(X_t\), thus the players will assume \(X_t=0\) if \(\overline{X}_t=0\) and \(X_t={\varPsi }\) if \(\overline{X}_t=1\). In the remainder of this section, we will enumerate all the robust Nash equilibria in the partial information model and show how they depend on the value of \({\varPsi }\). Then, in the next section, we will show how appropriate choice of \({\varPsi }\) can maximize the social welfare.
We will need some additional notation to formulate our main results. Let \({L}_\mathrm{EE}\), \({L}_\mathrm{NE}\) and \({L}_\mathrm{NN}\) denote the worst-case service cost for a player i entering the queue with \(\overline{X}_t=0\), when all the other players apply strategy EE, NE or NN, respectively. Similarly, let \({H}_\mathrm{EE}\), \({H}_\mathrm{NE}\) and \({H}_\mathrm{NN}\) denote the worst-case service cost for a player i entering the queue with \(\overline{X}_t=1\), when all the other users play EE, NE or NN, respectively. We can use the interpretation of the policies in our new model as threshold strategies in the original game and Lemma 4 to obtain:
Since the inequality is true both in case \(0<{\varPsi }<\frac{{\uplambda }}{\mu }\) and when \({\varPsi }>\frac{{\uplambda }}{\mu }\); in the degenerate case when \({\varPsi }=\frac{{\uplambda }}{\mu }\) the RHS reduces to \(\frac{1}{\mu }c({\varPsi })\), which is obviously also smaller than the LHS. The equalities in part (i) and part (ii) are direct consequences of the formulas for \({H}_\mathrm{NN}\), \({H}_\mathrm{NE}\) and \({H}_\mathrm{EE}\) written before the lemma. Thus, the part (b) also follows.
Part (c) of the lemma also follows from the monotonicity of c, as:
For any \({\varPsi }\ge 0\) the game with partial information has a pure-strategy RNE. Moreover:
(a)
When \(\gamma >{L}_\mathrm{NN}({\varPsi })\) then all the players use policy EE in equilibrium;
(b)
When \({L}_\mathrm{NN}({\varPsi })\ge \gamma \ge {L}_\mathrm{EE}({\varPsi })\) and \(\gamma >{H}_\mathrm{NN}({\varPsi })\) then strategy profiles where all the players use policy EE and where all the players use policy NE are equilibria;
(c)
When \({H}_\mathrm{NN}({\varPsi })\ge \gamma \ge \max \{ {L}_\mathrm{EE}({\varPsi }),{H}_\mathrm{NE}({\varPsi })\}\) then any strategy profile where all the players use the same policy is an equilibrium;
(d)
When \({H}_\mathrm{NE}({\varPsi })>\gamma \ge {L}_\mathrm{EE}({\varPsi })\) then strategy profiles where all the players use policy EE and where all the players use policy NN are equilibria;
(e)
When \({L}_\mathrm{EE}({\varPsi })>\gamma >{H}_\mathrm{NN}({\varPsi })\) then all the players use policy NE in equilibrium;
(f)
When \(\min \{ {L}_\mathrm{EE}({\varPsi }),{H}_\mathrm{NN}({\varPsi })\}\ge \gamma \ge {H}_\mathrm{NE}({\varPsi })\) then strategy profiles where all the players use policy NE and where all the players use policy NN are equilibria;
(g)
When \(\min \{ {L}_\mathrm{EE}({\varPsi }),{H}_\mathrm{NE}({\varPsi })\}>\gamma \) then all the players use policy NN in equilibrium.
Proof
By Lemma 8 cases (a)–(f) cover all the possible situations in the game. Then each of the cases follows directly from the definition of pure-strategy NE. \(\square \)
The following information about how the functions \({L}_s\) and \({H}_s\) behave when \({\varPsi }\) changes can be immediately derived from their definitions and the monotonicity of c.
Lemma 9
For any \(s\in \{ \mathrm{EE},\mathrm{NE},\mathrm{NN}\}\), \({L}_s({\varPsi })\) is constant, while \({H}_s({\varPsi })\) is non-increasing in \({\varPsi }\). Moreover:
Using this lemma, we can prove how the robust Nash equilibria depend on the value of the threshold \({\varPsi }\).
Theorem 6
Robust Nash equilibria in the game with partial information depend on \({\varPsi }\) in the following way:
(a)
If \(\gamma \le \frac{1}{\mu }\lim _{u\rightarrow \infty }c(u)\) then all the players use strategy NN in the equilibrium, regardless of \({\varPsi }\).
(b)
If \(\gamma \in \left( \frac{1}{\mu }\lim _{u\rightarrow \infty }c(u),\frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u\right) \) then for \({\varPsi }\) small enough all the players use policy NN in the equilibrium, while for \({\varPsi }\) approaching infinity all the players use policy NE in the equilibrium.
(c)
If \(\gamma \in \left[ \frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u,\frac{1}{\mu }c(0)\right) \) then for \({\varPsi }\) small enough there are three equilibria, in which all the players use the same policy, which is any of EE, NE or NN policies, while for \({\varPsi }\) approaching infinity either all the players use policy NE or all the players use policy EE in equilibrium.
(d)
If \(\gamma =\frac{1}{\mu }c(0)\) then there are two equilibria regardless of \({\varPsi }\), where all the players use the same policy, which is either EE or NE.
(e)
If \(\gamma >\frac{1}{\mu }c(0)\) then all the players use strategy EE in the equilibrium, regardless of \({\varPsi }\).
Proof
(a)
If \(\gamma \le \frac{1}{\mu }\lim _{u\rightarrow \infty }c(u)\) then by Lemma 9\({H}_\mathrm{EE}\) is always bigger than \(\gamma \). Consequently, by Lemma 8 also \({H}_\mathrm{NE}>\gamma \) and \({L}_\mathrm{EE}>\gamma \) and thus by Theorem 5 all the players use policy NN in the RNE.
(b)
If \(\gamma \in \left( \frac{1}{\mu }\lim _{u\rightarrow \infty }c(u),\frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u\right) \) then by Lemma 9 for \({\varPsi }\) small enough also \({H}_\mathrm{NE}({\varPsi })>\gamma \). \({L}_\mathrm{EE}({\varPsi })\) is independent of \({\varPsi }\) and always bigger than \(\gamma \), then by Theorem 5 all the players apply policy NN in the RNE for such \({\varPsi }\). On the other hand, if \({\varPsi }\) is big enough, \({H}_\mathrm{NN}({\varPsi })<\gamma \). Since, as already mentioned, also \({L}_\mathrm{EE}({\varPsi })>\gamma \), by Theorem 5 the strategy profile where everybody plays NE is the only RNE for such \({\varPsi }\).
(c)
If \(\gamma \in \left[ \frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u,\frac{1}{\mu }c(0)\right) \) then \({H}_\mathrm{NE}(0)\le \gamma \) and \({H}_\mathrm{NE}({\varPsi })<\gamma \) for any bigger \({\varPsi }\). \({L}_\mathrm{EE}\) is independent of \({\varPsi }\) and by assumption smaller than or equal to \(\gamma \). So, as long as \({\varPsi }\) satisfies \({H}_\mathrm{NN}({\varPsi })>\gamma \), Theorem 5 implies that profiles where everybody uses the same strategy, which is any of EE, NE or NN are equilibria. But for \({\varPsi }\) close to 0, \({H}_\mathrm{NN}({\varPsi })\) is close to \(\frac{1}{\mu }c(0)>\gamma \). Next, if \({\varPsi }\) approaches infinity, \({L}_\mathrm{EE}({\varPsi })\le \gamma <\frac{1}{\mu }c(0)={L}_\mathrm{NN}({\varPsi })\) and \({H}_\mathrm{NN}({\varPsi })\) goes to \(\frac{1}{\mu }\lim _{u\rightarrow \infty }c(u)<\gamma \), thus for \({\varPsi }\) big enough we have two robust Nash equilibria, where either all the players use policy NE or all use policy EE.
(d)
If \(\gamma =\frac{1}{\mu }c(0)\) then for any value of \({\varPsi }\), both \({H}_\mathrm{NN}\) and \({L}_\mathrm{EE}\) are smaller than \(\gamma \). On the other hand, \({L}_\mathrm{NN}\equiv \gamma \) and so by Theorem 5 for any \({\varPsi }\) there are two robust Nash equilibria, where either all the players use policy NE or all use policy EE.
(e)
If \(\gamma >\frac{1}{\mu }c(0)\) then \({L}_\mathrm{NN}\) is always smaller than \(\gamma \), and thus the only RNE for any value of \({\varPsi }\) is when everyone applies policy EE.
\(\square \)
Remark 4
Note that the limits when \({\varPsi }\) is taken to infinity and zero make the signal completely uninformative on the state of the system. Thus, we can easily derive from Theorem 6 the equilibria in our game when the queue is completely unobservable. It is enough to look at the action prescribed to be taken above the threshold when \({\varPsi }\rightarrow 0\) or the one below the threshold when \({\varPsi }\rightarrow \infty \). It turns out that in cases (a) and (b) uninformed players should not enter the queue, in cases (d) and (e) they should enter the queue, while in case (e) there are two equilibria where players either enter or do not enter the queue.
Roughly speaking, Theorem 6 suggests that by increasing \({\varPsi }\) we can increase the set of global states for which the players would enter the queue. Since this will also affect the stationary state of the queue, which, as we can see from Sect. 5, is crucial for the social welfare, it seems that by a proper choice of \({\varPsi }\) we can make the social welfare very close to its optimal value. We study the above idea in the perspective of social cost in Sect. 7 where a hierarchy will be introduced in the game with the social planner choosing \({\varPsi }\) at the first stage, and then the users playing the partial information game from the present section at the second one.
7 Introducing Hierarchy to Boost the Performance of Equilibria
In this section, we assume that the game is played in two stages. In the first stage, the social planner, having all the information about the game, including the actual value of \(x_0\), chooses \({\varPsi }\) and announces it to the players. His goal is to minimize the social cost \(C(x_0,{\varvec{{\pi }}})\) by appropriately limiting the data available to the players. On the second stage, the users play the game considered in Sect. 6 using all the information they have, which only consists of the announced value of \({\varPsi }\), assuming that the state of the queue when they decide about entering is the worst possible. We will analyze what are the equilibria of this game and further show that the Price of Anarchy and the Price of Stability in this model are the same as in the full information case.
We first study how equilibria in the hierarchical model will look like. Toward this end, we consider the pessimistic and the optimistic case. In the pessimistic setting, the social planner chooses \({\varPsi }\) in order to minimize \(\max _{{\varvec{{\pi }}}\in \mathcal {N}\mathcal {E}}C(x_0,{\varvec{{\pi }}})\), so he assumes that whenever the players choose their strategies, they choose the equilibrium which yields the highest social cost. In the optimistic case, the social planner chooses \({\varPsi }\) minimizing \(\min _{{\varvec{{\pi }}}\in \mathcal {N}\mathcal {E}}C(x_0,{\varvec{{\pi }}})\), assuming that the players choose the equilibrium which yields the lowest social cost. \(\mathcal {N}\mathcal {E}\) above denotes the set of Nash equilibria of the game of the second stage. The result is summarized in the following theorem:
Theorem 7
In the hierarchical model:
(a)
If \(\gamma \le \frac{1}{\mu }\lim _{u\rightarrow \infty }c(u)\) then the social planer chooses any \({\varPsi }\), with all the players using strategy NN in the equilibrium.
(b)
If \(\gamma \in \left( \frac{1}{\mu }\lim _{u\rightarrow \infty }c(u),\frac{1}{\mu }c\left( \frac{{\uplambda }}{\mu }\right) \right) \) then the social planner chooses any \({\varPsi }<\underline{{\varTheta }}\) and all the players use policy NN in the equilibrium.
(c)
If \(\gamma \in \left( \frac{1}{\mu }c\left( \frac{{\uplambda }}{\mu }\right) ,\frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u\right) \) then the social planner chooses \({\varPsi }=\overline{{\varTheta }}\) with all the players using policy NE in the equilibrium.
(d)
If \(\gamma \in \left[ \frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u,\frac{1}{\mu }c(0)\right) \) then in pessimistic case the social planner chooses \({\varPsi }=\underline{{\varTheta }}\) and all the players use policy NE in equilibrium; in the optimistic case, the social planner chooses any \({\varPsi }\) and all the players use policy EE in equilibrium.
(e)
If \(\gamma =\frac{1}{\mu }c(0)\) then in the optimistic case the social planner chooses any \({\varPsi }\), while all the players use strategy EE in equilibrium; in pessimistic case, the social planner chooses \({\varPsi }=0\) and all the players use strategy7 EE or NE in the equilibrium.
(f)
If \(\gamma >\frac{1}{\mu }c(0)\) then the social planner chooses any \({\varPsi }\) with all the players using strategy EE in the equilibrium.
Proof
In cases (a) and (b) the social planner wants the players never to enter the queue. In case (a) never entering the queue is the equilibrium, regardless of \({\varPsi }\). In case (b) forcing players to use NN policies requires choosing threshold \({\varPsi }\) such that \({H}_\mathrm{NE}({\varPsi })>\gamma \). If we compare the definition of \({H}_\mathrm{NE}\) with (8), we obtain that \({\varPsi }<\underline{{\varTheta }}\), as for \(\gamma <\frac{1}{\mu }c\left( \frac{{\uplambda }}{\mu }\right) \), \({H}_\mathrm{NE}({\varPsi })\) can only obtain the \(\gamma \) value for \({\varPsi }>\frac{{\uplambda }}{\mu }\).
In cases (c)–(f) the social optimum is achieved if players always enter the queue. Thus the social planner forces the players to use EE policies if possible ((f), optimistic scenarios in (d) and (e)). In all of these cases, this means choosing any value of threshold \({\varPsi }\), as EE policies are in equilibrium then regardless of \({\varPsi }\). If forcing the players to use EE policies is impossible, the social planner chooses the lowest possible \({\varPsi }\) such that the players would use NE, and not NN policies in equilibrium. In pessimistic scenario of case (e), players do not use policy NN for any value of \({\varPsi }\), so this means choosing \({\varPsi }=0\). In case (c) this means the smallest \({\varPsi }\) such that \({H}_\mathrm{NE}({\varPsi })=\gamma \), which for \(\gamma \in \left( \frac{1}{\mu }c\left( \frac{{\uplambda }}{\mu }\right) ,\frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\, du\right) \) equals \(\overline{{\varTheta }}\) (in such a case \({H}_\mathrm{NE}({\varPsi })\) obtains the \(\gamma \) value both for \({\varPsi }<\frac{{\uplambda }}{\mu }\) and \({\varPsi }>\frac{{\uplambda }}{\mu }\)). In the pessimistic variant of case (d), this means choosing \({\varPsi }\) such that \({H}_\mathrm{NN}({\varPsi })=\gamma \), which, by the definition of \({H}_\mathrm{NN}\) and (8) is equivalent to \({\varPsi }=\underline{{\varTheta }}\). \(\square \)
Remark 5
Note that in Theorem 7 we did not consider the case of \(\gamma =\frac{1}{\mu }c\left( \frac{{\uplambda }}{\mu }\right) \). This is because in this case the social cost of any policy (used by all the players) equals 0. Thus the social planner may choose any value of \({\varPsi }\). This, however, may result in different equilibria in the game of the second stage.
We further analyze how this result affects Price of Anarchy and Price of Stability in our model. Both these quantities are computed ex post, that is, we assume that all the users have their knowledge about the state of the queue limited when they make their decisions, but PoA and PoS are computed when all the state information is revealed. This allows us to compare the results obtained in the hierarchical model with the ones obtained for the full information case. The result presented below is an immediate consequence of Theorem 7 and thus presented without proof.
Theorem 8
In hierarchical model:
1.
The Price of Stability is infinite if \(\gamma \in \left( \frac{1}{\mu }c\left( \frac{{\uplambda }}{\mu }\right) ,\frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u\right) \) and \(x_0<\overline{{\varTheta }}\). Otherwise it equals 1.
2.
The Price of Anarchy is infinite if \(\gamma \in \left( \frac{1}{\mu } c\left( \frac{{\uplambda }}{\mu }\right) ,\frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u\right) \) or if \(\gamma \in \left[ \frac{1}{{\uplambda }}\int _0^{\frac{{\uplambda }}{\mu }}c(u)\mathrm{d}u,\frac{1}{\mu }c(0)\right) \) and \(x_0<\underline{{\varTheta }}\). Otherwise it equals 1.
As we can see from Theorem 8, when only information available for the players is an indicator of state being above or below \({\varPsi }\), then both PoA and PoS stay the same as in the model with full information. Thus we can claim that we can reduce the information given to the players without degrading the performance. On the other hand, we cannot improve it by choosing only an appropriate signal to send.
8 Approximation of the Discrete Model
In the section below, we present a result which joins the equilibria of the fluid model with \(\varepsilon \)-equilibria of the discrete model when the incoming rate is sufficiently high. To formulate it, we need to introduce some additional notation, differentiating between the discrete and the fluid model. Let us start with fixing that the function c and parameters \({\uplambda }\) and \(\mu \) define the fluid model, whose state will be denoted by \(X_t\). Then let \(M_n\) be a discrete model with service cost \(c^n(x)=c\left( \frac{x}{n}\right) \), incoming rate \({\uplambda }^n=n{\uplambda }\) and service rate \(\mu \). The state in model \(M_n\) will be denoted by \(X^n_t\), while
will be its normalized state. Using this notation, we can formulate the main result of this section and its proof.
Theorem 9
Suppose that the initial (normalized) state of the queue \(x_0\in [0,x_\mathrm{max}]\) for some fixed \(x_\mathrm{max}\) and that the user k plays against \([{\varTheta },q]\)-threshold policies of all the others (denoted shortly as \(\pi \) policies) in the fluid model with service cost c, incoming rate \({\uplambda }\) and service rate \(\mu \). Then for any \(\varepsilon >0\) there exists an N such that for any \(n\ge N\) his expected cost from entering the queue in the discrete model \(M_n\),
where \(\pi ^n\) denotes a \([n{\varTheta },q]\)-threshold policy (which is a proper rescaling of policy \(\pi \) to fit \(M_n\)), differs from the expected cost \({{\mathbb E}}\left[ {C_k(X_t(\pi ))}\right] \) in the fluid model by at most \(\varepsilon \).
Proof
Let us consider two policies for the discrete model \(M_n\):
These policies differ from \([{\varTheta },q]\)-threshold policy \(\pi \) only on sets \(({\varTheta }-\beta ,{\varTheta })\) or \(({\varTheta },{\varTheta }+\beta )\), respectively. Next, consider Eq. (3) when all the players apply policy \(\overline{\pi }^{\beta }\). It can be directly computed that the solution \(X_t(\overline{\pi }^\beta )\) has the following properties:
1.
\(X_t(\overline{\pi }^\beta )\rightarrow X_t(\pi )\) pointwise as \(\beta \rightarrow 0\).
2.
Whenever \(X_t(\overline{\pi }^\beta )\not \in ({\varTheta }-\beta ,{\varTheta })\), it is of the form \(X_t(\overline{\pi }^\beta )=D_1\mathrm{e}^{-\mu t}+D_2\) for some constants \(D_1, D_2\) with \(|D_1|\le \max \left\{ x_0,\frac{{\uplambda }}{\mu }\right\} \le \max \left\{ x_\mathrm{max},\frac{{\uplambda }}{\mu }\right\} \).
3.
When \(X_t(\overline{\pi }^\beta )\in ({\varTheta }-\beta ,{\varTheta })\), it satisfies equation
Properties (ii) and (iii) clearly imply that \(X_t(\overline{\pi }^\beta )\) is Lipschitz-continuous with constant \(\max \left\{ x_\mathrm{max},\frac{{\uplambda }}{\mu },{\uplambda }+\mu {\varTheta }\right\} \), independent of \(\beta \). Thus all the functions \(X_t(\overline{\pi }^\beta )\) are equicontinuous (as functions of t).
Clearly, as \(X_t(\overline{\pi }^\beta )\) are equicontinuous and converging to \(X_t(\pi )\), by the Arzelà-Ascoli theorem \(X_t(\overline{\pi }^\beta )\) converges to \(X_t(\pi )\) uniformly on interval \([0,T_\varepsilon ]\). On the other hand, c is continuous, decreasing and bounded, and thus it is uniformly continuous, which means that there exists a \(\delta >0\) such that for any x, y such that \(|x-y|<\delta \) we have \(|c(x)-c(y)|<\frac{\varepsilon }{8T_\varepsilon }\). Using uniform convergence of \(X_t(\overline{\pi }^\beta )\), we can further conclude that there exists a \(\beta >0\) such that
for some positive constant D and a function F satisfying \(\lim _{\eta \searrow 0}\frac{F(\eta )}{\eta ^2}\in (0,\infty )\). By this last property, the probability bounded above converges to zero as n goes to infinity at rate of \(\mathrm{e}^{-n }\), so for n large enough this probability is not bigger than \(\frac{\varepsilon }{8T_\varepsilon c(0)}\).
where the last inequality is a consequence of (10), (11), (12) and the bound on the probability that \(\widetilde{X}^n_t(\overline{\pi }^{\beta ,n})\) and \(X_t(\overline{\pi }^{\beta })\) differ by more than \(\delta \) (recall that c(0) is the biggest value of c)
Now we can repeat all the above considerations for policies \(\underline{\pi }^\beta \) and \(\underline{\pi }^{\beta ,n}\), obtaining similiar inequality
To complete the proof, note that \(X_t^n(\underline{\pi }^{\beta ,n})\), \(X_t^n(\pi )\) and \(X_t^n(\overline{\pi }^{\beta ,n})\) are birth–death processes starting at the same \(x_0\), with the same death rate, but with increasing birth rates. As a consequence \(X_t^n(\underline{\pi }^{\beta ,n})\) is for any \(t\ge 0\) stochastically dominated by \(X_t^n(\pi )\), which in turn is stochastically dominated by \(X_t^n(\overline{\pi }^{\beta ,n})\). This, however, implies that
But this, together with (15) and (16), implies the thesis of the theorem. \(\square \)
Using Theorem 9, we can immediately show that all the results proved for the mean-field model can be viewed as good approximations of what happens in the discrete case when service rates go to infinity. This is formulated in three corollaries below.
Corollary 3
Suppose that the initial (normalized) state of the queue \(x_0\in [0,x_\mathrm{max}]\) for some fixed \(x_\mathrm{max}\) and that \([{\varTheta },q]\)-threshold policies of all the players form an equilibrium in the fluid model with service cost c, incoming rate \({\uplambda }\) and service rate \(\mu \). Than for any \(\varepsilon >0\), there exists an N such that for any \(n\ge N\)\([n{\varTheta },q]\)-threshold policies form \(\varepsilon \)-equilibria in discrete models \(M_n\).
Corollary 4
Suppose that for some \({\varPsi }\ge 0\), f policies of all the players (where f is of one of three types: EE, NE, NN) form a RNE in the partial information fluid model with service cost c, incoming rate \({\uplambda }\) and service rate \(\mu \). Than for any \(\varepsilon >0\), there exists an N such that for any \(n\ge N\)f policies form \(\varepsilon \)-robust Nash equilibria in the partial information counterparts of discrete models \(M_n\).
Corollary 5
Suppose that \({\varPsi }\) and f policies of all the players (where f is of one of three types: EE, NE, NN) form an equilibrium in the hierarchical partial information fluid model with service cost c, incoming rate \({\uplambda }\) and service rate \(\mu \). Than for any \(\varepsilon >0\), there exists an N such that for any \(n\ge N\)\(n{\varPsi }\) and f policies for all the players form \(\varepsilon \)-equilibria in hierarchical partial information counterparts of discrete models \(M_n\).
9 Numerical Analysis
Here, we numerically evaluate NE strategy profile in complete and partial information setting for some special class of cost functions \(c(\cdot )\). We consider the following cost function
In this section, we numerically analyze the setting when each player has complete information of the game. First, we numerically evaluate all the possible NE strategy profiles using Theorem 1
1.
\(\gamma \ge \dfrac{1}{a\mu }=0.5\), then \({\varTheta }=0\) and \(q=1\). Thus, players will always enter the queue.
2.
\(\gamma \in [0.2503,0.5)\), then there are infinitely many equilibria which are of the following types:
If \(\bar{{\varTheta }}=\rho \) (which occurs when \(\gamma =\dfrac{1}{7}\)), then either \({\varTheta }=\bar{{\varTheta }}\) and \(q\in \{0,1\}\) or \(\underline{{\varTheta }}\) and \(q\in [0,1]\)8
(c)
If \(\bar{{\varTheta }}>\rho \) (which occurs when \(\gamma <\dfrac{1}{7}\)), then either \({\varTheta }=\underline{{\varTheta }}, q\in [0,1]\) or \({\varTheta }=\rho \) and \(q=0\).
Fig. 1
Variation of \(\underline{{\varTheta }}\) and lower threshold value with \(\gamma \)
×
Figure 1 shows the variation of \(\underline{{\varTheta }}\) and the lowest possible threshold value of NE strategy profile with \(\gamma \). From the above characterization of NE, it is easy to discern that the lower threshold value is \(\max \{\min \{\bar{{\varTheta }},\rho \},0\}\), i.e., there is no NE with the threshold value lower than the above value. The upper threshold is always given by \(\underline{{\varTheta }}\), i.e., there is no NE with the threshold value higher than \(\underline{{\varTheta }}\). Note that lower threshold value goes to 0 at \(\gamma =0.2503\) and the upper threshold value goes to 0 at \(\gamma =0.5\).
Fig. 2
Variation of optimal social cost and the best-case social cost with \(\gamma \) for complete information game
×
For the rest of simulation results, we consider \(x_0=0.2\). First, it is important to note that under our setting, if a user incurs a positive cost when entering the queue, then it does not enter the queue in any equilibrium. Thus, the social optimal cost as well as the equilibrium cost can never be positive.
Note that \(c(\rho )=\gamma \mu \) when \(\gamma =\dfrac{1}{7}\). Figure 2 shows the variation of optimal social cost and the highest possible social cost at an equilibrium with \(\gamma \). Optimal social cost is zero when \(\gamma \le \dfrac{1}{7}\). But when \(\gamma >\dfrac{1}{7}\) the optimal cost increases linearly as it is evident by Theorem 2. From (18) we obtain that when \(\gamma \le 0.1865\), then \(\bar{{\varTheta }}\ge 0.2\) and when \(\gamma >0.1865\), then \(\bar{{\varTheta }}< 0.2\). Thus, when \(\gamma < 0.1865\) social cost under the best equilibrium is zero by Theorem 4. But when \(\gamma \ge 0.1865 \) the social cost under the best equilibrium is exactly the same as optimal social cost.
Fig. 3
Variation of optimal social cost and the worst possible social cost at equilibrium with \(\gamma \) for complete information game
×
Figure 3 shows the variation of optimal social cost and worst-case social cost with \(\gamma \). Note that when \(\gamma \ge 0.3466\), then \(\underline{{\varTheta }}\ge 0.2\) and when \(\gamma < 0.3466\), then \(\underline{{\varTheta }}< 0.2\). Thus, when \(\gamma \le 0.3466\) the worst-case social cost is 0 by Theorem 3. On the other hand when \(\gamma >0.3466\) the worst-case social cost is exactly the same as optimal social cost.
9.2 Partial Information Game
Note from Theorems 4, 3 and 8 that the performance in the best- and worst-case scenario for the partial information case is the same as the full information case. Thus, the numerical results for the full information case will go through this setting.
10 Conclusions
We studied in this paper a congestion game in a fluid queueing network in which customers benefit from congestion, i.e., the cost per customer decreases with the congestion. We showed that this could lead to a large number of symmetric equilibria, all of which with a reverse threshold behavior: Customers get in if and only if the number of queued customers exceeds the threshold. We computed perfect equilibria to this game and the social optimum. Further, we considered a model where the information provided to the players is limited to an indication of whether the state of the queue is above or below some threshold. It turned out that appropriate limitation of the information obtained by the players can draw the outcome of the game toward the social optimum. Finally, we showed that one can use the equilibria policies in the fluid queue to approximate equilibria for discrete queues and provided numerical examples.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
The fact that we have strong monotonicity here, even though we had weak monotonicity in Lemma 1, is a consequence of the continuity of \(X_t\), which implies that a trajectory starting at time \(t_k\) in a bigger \(X_{t_k}\) stays above the one starting in a smaller \(X_{t_k}'\) on some interval, which affects the integral in (4).
The result can be generalized to the asymmetric case, but it would require some technical assumptions to make sure \(\overline{{\varvec{{\pi }}}}\) is well defined.
In the degenerate case when \(x=\frac{{\uplambda }}{\mu }\), \(\widehat{C}_k\left( x,\left( {\varTheta }_{-k},q_{-k}\right) \right) =\frac{1}{\mu }c\left( \frac{{\uplambda }}{\mu }\right) \), which is the limit of the expression in (a) when \(x\rightarrow \frac{{\uplambda }}{\mu }\). We will use similiar convention throughout the paper, putting \(\frac{1}{a-a}\int _a^a f(u)\mathrm{d}u=f(a)\), if needed. This will reduce the number of cases considered in subsequent results, without affecting the validity of any of them.
