Equilibrium Joining Strategies for Queues in Two-Phase Random Environment⋆ Konstantin Avrachenkov1 and Uri Yechiali2
arXiv:2609.32345v1 [math.PR] 26 Sep 2026
1
Inria Sophia Antipolis, France [email protected] 2 Tel Aviv University, Israel [email protected]
Abstract. We study equilibrium joining strategies in an M/M/1-type queueing system with strategic customers operating in a two-phase random environment described as a continuous-time Markov process. Strategic customers, upon arrival, choose whether to join or to balk based on available information and anticipated utility, considering the trade-off between reward from service and waiting cost. Four observation scenarios are analysed: fully observable (both queue length and environment phase are disclosed to a customer upon arrival), queue-only observable, environment-only observable, and fully unobservable. In each case, equilibrium joining strategies are analysed. In the environment-only observable and fully unobservable cases, explicit solutions and equilibrium conditions are derived under rapid oscillations and under very slow transitions between environment phases. Keywords: Strategic Queueing · Joining Strategies · Random Environment · Partial Observations
1
Introduction
We consider an M/M/1-type queue in a random environment modeled by a twophase continuous-time Markov chain. Specifically, when the environment is in phase i = 1, 2 the arrival rate is λi , the service rate is µi , and the environment remains in that phase for an exponential time with parameter ηi , after which it switches to the other phase. This queueing system has been extensively analysed (see e.g., [25, 23, 19, 3, 10] and follow-up publications). The focus of our work is on the analysis of equilibrium joining strategies of individual customers. We assume that all the parameters of the model constitute common knowledge. We consider various cases of available information regarding the environment phase and the queue length for arriving customers. The following four cases will be investigated: (a) fully observable (FO) case, when both the environment phase and the queue length are known upon arrival; (b) the case when only the queue ⋆
This paper has been accepted at the 29th International Conference on Analytical and Stochastic Modelling Techniques and Applications (ASMTA 2026) with proceedings published in Springer LNCS.
2
K. Avrachenkov and U. Yechiali
length is observable (QO) upon arrival; (c) the case when only the environment phase is observable (EO) upon arrival and, finally, (d) no observation (NO) case when neither the environment phase nor the queue length are observable. Inspired by the seminal article of Naor [18] (see also [26, 27, 9]), we would like to analyse equilibrium joining strategies in an evolving environment. Upon arrival, a customer can decide whether to join or to balk. If a customer balks, they leave the system forever. If a customer joins, they gain an eventual reward R for the service and accumulate waiting cost at a rate cw per unit of time. Customers who join cannot subsequently renege. Reneging may be beneficial when the environment switches from a fast to a slow service phase. Its value in queueing systems with server vacations or failures is studied in [8]. In [6] equilibrium joining strategies have been studied in a system with random environment when the server removes all present customers at the completion epochs of exponential catastrophe cycles. See also [21] and [22], where related models of M/M/∞ and M/M/1, respectively, with disasters have been analysed. In [7], strategic queueing has been studied for fluid queues in random environment. In [13] strategic queueing with arrival process with an i.i.d. random rate has been analysed. The special case λ1 = λ2 and µ1 = 0 corresponds to an M/M/1 queue with an unreliable server. Equilibrium balking in this setting is studied in [5]. A model related to this special case arises in the dedicated-vsfree spectrum choice in wireless networks, as studied in [14]. For background on strategic queueing we recommend the books [11, 12].
2
FO case: fully observable system
We start our analysis with the fully observable (FO) case. Let Si (n) denote the sojourn time of a customer joining a queue of length n, when the environment is in phase i = 1, 2. Let si (n) be its expected value. In particular, Si (0) is the customer’s service time given the service starts in environment i = 1, 2. Using the memoryless property of the exponential distribution, we can write the following equation: si (0) =
ηi 1 + sj (0), µi + ηi µi + ηi
i ̸= j,
i, j ∈ {1, 2}.
(1)
That is, 1/(µi + ηi ) is the expected time until either the service is concluded or the environment changes phase, and then, with probability ηi /(µi + ηi ) the environment switches to phase j, and the remaining expected service time is sj (0). Solving the system (1), we obtain si (0) =
µj + η1 + η2 , µ1 µ2 + µ1 η2 + µ2 η1
i ̸= j,
i, j ∈ {1, 2}.
(2)
We also define the probability that a service initiated in environment i is completed in environment j: qij = P[service completion occurs in environment j | service has started in i].
Equilibrium Joining Strategies for Queues in Random Environment
3
Reasoning as in the derivation of (1) gives: qii =
µi ηi + qji , µi + ηi µi + ηi
i ̸= j,
i, j ∈ {1, 2},
The solution of the above linear system results in qii =
µi (µj + ηj ) , µ1 µ2 + µ1 η2 + µ2 η1
i ̸= j,
i, j ∈ {1, 2},
(3)
and we have qij = 1 − qii for j ̸= i. Equation (3) can be interpreted as follows: qii =
∞ X k=0
η1 η2 (µ1 + η1 )(µ2 + η2 )
k
µi , µi + ηi
i = 1, 2,
that is, the underlying process performs k phase transitions back and forth, and then the service completion occurs before the phase transition. When a customer arrives and sees n customers ahead, the first service (of the customer in service) will take an expected time si (0) if the environment is in phase i. At the end of this service, the environment is in phase i with probability qii and in phase j with probability qij (where j ̸= i). Hence, the recursion for the conditional expected sojourn time is: si (n) = si (0) + qii si (n − 1) + qij sj (n − 1), Define the vectors
s(n) =
and the matrix
Q=
s1 (n) , s2 (n)
i ̸= j.
n = 0, 1, ...
q11 q12 q11 1 − q11 = . q21 q22 1 − q22 q22
Then, the recurrence becomes s(n) = s(0) + Q s(n − 1).
(4)
This recurrence leads to closed-form expressions for s(n). Proposition 1. The vector of the expected conditional sojourn times has the following closed-form expressions: s(n) =
n X
Qk s(0)
(5)
k=0
and (6) s(n) = [(n + 1)1π + H(I − Qn+1 )]s(0), h i η2 µ 2 η1 where π = µ1 ηµ21+µ µ1 η2 +µ2 η1 is the invariant probability measure of Q and 2 η1 H is the deviation matrix.
4
K. Avrachenkov and U. Yechiali
Proof: By iterating the recurrence (4), we obtain the closed-form expression (5). The other expression can be obtained using the deviation matrix [15] H = (I − 1π)(I − Q + 1π)−1 , where π is the invariant probability measure of Q, i.e., π = πQ with π1 = 1. Note that π is a row vector and 1 is a column vector of 1s. We can write (I − Q)
n X
Qk = I − Qn+1 .
k=0
Premultiplying the above equality by the matrix H and using the property of the deviation matrix H(I − Q) = I − 1π (see e.g., the Appendix in [15]), we obtain n X (I − 1π) Qk = H(I − Qn+1 ). k=0
Then, using π = πQ yields n X
Qk = [(n + 1)1π + H(I − Qn+1 )].
k=0
Postmultiplication of the above equation by s(0) leads to (6).
□
We can also establish the following monotonicity result. Lemma 1. The following inequality holds si (n + 1) > si (n),
i ∈ {1, 2}.
(7)
Proof: From (5), we have s(n + 1) − s(n) = Qn+1 s(0). Since Q is stochastic and s(0) has strictly positive components, the inequality (7) follows. □ When an arriving customer sees the environment in phase i and n customers in the queue, the customer does not incur a loss and joins the queue if R ≥ cw si (n),
i = 1, 2.
(8)
Recall that R is the reward for the service and cw is the rate of the waiting cost. We assume that for someone who has already arrived at the system, it makes sense to join the queue even if the expected utility is zero. Thus, by Lemma 1, the equilibrium strategy has phase-dependent threshold structure with the thresholds R n̄i = min n ∈ N0 : si (n) > , i = 1, 2, cw i.e., the first queue length at which the customer balks.
Equilibrium Joining Strategies for Queues in Random Environment
3
5
QO case: only the queue length is observable
Now we consider the QO case when the queue length is observable upon arrival but not the phase of the environment. An arriving customer joins the queue if their expected utility is non-negative. In the QO case, the expected utility is given by UL=n = R − cw E0 [S|L = n], where S is the sojourn time, L is the queue length observed upon arrival, and E0 [·] denotes Palm expectation, i.e., the expectation given an arrival event (for more background on Palm expectation and probability, see e.g. [4]). Then, conditioning on the environment phase E, we can write UL=n = R−cw (E0 [S|E = 1, L = n]P0 [E = 1|L = n]+E0 [S|E = 2, L = n]P0 [E = 2|L = n]) where the operations with zero superscript correspond to Palm versions. Specifically, the Palm probabilities are given by P0 [E = i, L = n] =
λi pin , λ1 p1• + λ2 p2•
i = 1, 2,
n = 0, 1, ...
where pin = P[E = i, L = n] are the stationary probabilities and pi• = ηj /(η1 + η2 ), i = 1, 2, j ̸= i. Hence, P0 [E = i|L = n] =
λi pin , λ1 p1n + λ2 p2n
i = 1, 2,
(9) P∞
n=0 pin =
n = 0, 1, ...
Thus, the expected utility can be written as follows: UL=n = R − cw
1 (λ1 p1n s1 (n) + λ2 p2n s2 (n)). λ1 p1n + λ2 p2n
(10)
In general, a symmetric equilibrium in the QO case can have the form of an infinite vector of joining probabilities, i.e., a∗ = (a∗0 , a∗1 , ...). Next, we show that under natural conditions the equilibrium strategy has a threshold structure. Proposition 2. Suppose that µ1 ≤ µ2 (without loss of generality). Fix a stationary joining strategy a = (an )n≥0 , and let pain denote the corresponding stationary probabilities. Assume that pa1,n+1 pa2n ≥ pa1n pa2,n+1
(11)
whenever both n and n + 1 have positive Palm probability. Then, the utility Una to join when seeing the queue length n and everyone else follows strategy a is strictly decreasing in n on the support of the Palm distribution.
6
K. Avrachenkov and U. Yechiali
Proof: First note that from (2) we have s1 (0) − s2 (0) =
µ2 − µ1 ≥ 0. µ1 µ2 + µ1 η2 + µ2 η1
(12)
Also note that from (3) for every x = (x1 , x2 )⊤ , (Qx)1 − (Qx)2 = δ(x1 − x2 ), where δ := q11 + q22 − 1 =
(13)
µ1 µ2 ∈ (0, 1). µ1 µ2 + µ1 η2 + µ2 η1
It follows from (5), (12) and (13) that n X s1 (n) − s2 (n) = s1 (0) − s2 (0) δ k ≥ 0.
(14)
k=0
For every n of positive Palm probability, set αna := P0a (E = 1|L = n) =
λ1 pa1n . a λ1 p1n + λ2 pa2n
Condition (11) implies a αn+1 ≥ αna .
(15)
Indeed, after cross-multiplication, (15) is equivalent to λ1 λ2 pa1,n+1 pa2n − pa1n pa2,n+1 ≥ 0. For notational convenience, denote σa (n) := E0a [S|L = n] = αna s1 (n) + (1 − αna )s2 (n). Then, we can write a σa (n + 1) − σa (n) = αn+1 s1 (n + 1) − s1 (n) a + (1 − αn+1 ) s2 (n + 1) − s2 (n) a + (αn+1 − αna ) s1 (n) − s2 (n) . The first two terms are strictly positive by Lemma 1, whereas the last term is nonnegative by (14) and (15). Thus σa (n + 1) > σa (n). Since Una = R − cw σa (n), the sequence Una is strictly decreasing.
□
If a stationary strategy a induces a stationary distribution satisfying (11), then its joining utility is decreasing in n. In particular, if an equilibrium strategy
Equilibrium Joining Strategies for Queues in Random Environment
7
a∗ induces a distribution satisfying (11), then, on the support of the Palm distribution, a∗ has a threshold form. Yet, there may be non-threshold equilibrium strategies. The condition (11) has a probabilistic interpretation in terms of the likelihood ratio stochastic order [17]: L | E = 1 ≥lr L | E = 2. This means that the likelihood ratio P(L = n|E = 1) P(L = n|E = 2) is nondecreasing in n. Hence, observing a larger queue provides increasingly stronger evidence that the system is in the slower phase 1. We have an explicit expression for si (n), equation (6). However, it is unfortunate that there is no explicit expression for the stationary probability pin . Therefore, as in [25], we consider two limiting cases: the case of rapid oscillations of the environment (Case C in [25]) and the case of very slow transitions between the environment phases (Case D in [25]). In these cases, the stationary distribution has an explicit product-form. 3.1
QO case: rapid oscillations of the environment
Here, as in [25], we assume that the environment oscillates rapidly between two phases 1 and 2. Specifically, η1 and η2 tend to infinity simultaneously and their ratio η1 /η2 tends to a finite constant C. In the limit, as the rates go to infinity, the stationary probabilities converge to pin = pi•
1 − ρ̄ n ρ̄ , 1 − ρ̄n̄+1
n = 0, ..., n̄,
(16)
where n̄ is the equilibrium threshold and ρ̄ = λ̄/µ̄ with λ̄ = p1• λ1 + p2• λ2 ,
µ̄ = p1• µ1 + p2• µ2 ,
and p1• = 1/(1 + C), p2• = C/(1 + C). The product-form (16) can be formally justified in the framework of singularly perturbed Markov chains [1, 2]. Using (2), we conclude that si (0) →
1+C 1 = , µ1 + Cµ2 µ̄
i = 1, 2,
as η1 , η2 → ∞. And hence, s(n) =
n X k=0
Qk s(0) =
n X k=0
Qk
(n + 1) 1 1 1 = . 1 µ̄ 1 µ̄
(17)
Substituting (16) and (17) into (10), yields UL=n = R − cw
n+1 , µ̄
which means that this case corresponds to the Naor’s classical model with the averaged service rate µ̄.
8
3.2
K. Avrachenkov and U. Yechiali
QO case: very slow transitions between the environment phases
Now, let us consider the opposite situation when the transition rates between the phases of the environment are very slow. Technically, this means to let the rates η1 and η2 go to zero assuming that their ratio η1 /η2 goes to a finite constant C. In this case, as η1 and η2 go to zero, the stationary distribution converges to the product-form (the justification again follows from the theory of singularly perturbed Markov chains [1, 2]), i.e., pin (a) ∝ pi• ρni
n−1 Y
ak .
k=0
so pa1,n+1 pa2n − pa1n pa2,n+1 has the sign of ρ1 − ρ2 . Thus, in this limiting case, Proposition 2 gives the primitive sufficient condition (µ1 − µ2 )(ρ1 − ρ2 ) ≤ 0 for equilibrium threshold structure. Thus, the threshold structure is guaranteed when the slower service environment has the larger traffic intensity. In this case, the informational and congestion effects act in the same direction. Specifically, using [1], for a threshold strategy n̄ we can write pin = pi•
1 − ρi n ρi , 1 − ρn̄+1 i
n = 0, ..., n̄,
(18)
where ρi = λi /µi , i = 1, 2. From the expression (2), we conclude that si (0) →
1 , µi
i = 1, 2,
as η1 , η2 → 0. From (3), we conclude that Q → I (identity matrix), as η1 , η2 → 0. Hence, using (5), n X 1/µ1 k s(n) = Q s(0) = (n + 1) . (19) 1/µ2 k=0
Thus, by (10), the utility against everyone following a threshold policy is n̄ 1 − αnn̄ αn (n̄) + , UL=n = R − cw (n + 1) µ1 µ2 (n̄)
where αn = Pn̄0 (E = 1|L = n) is the conditional Palm probability when everyone follows the threshold strategy n̄. Thus, the threshold strategy n̄ is an equilibrium when ! (n̄) (n̄) αn̄−1 1 − αn̄−1 R n̄ + ≤ , µ1 µ2 cw and
(n̄)
(n̄ + 1)
(n̄)
αn̄ 1 − αn̄ + µ1 µ2
! >
R . cw
Equilibrium Joining Strategies for Queues in Random Environment
9
If µ1 = µ2 , then we again retrieve Naor’s model. Another interesting particular case is when ρ1 = ρ2 and we have UL=n = R − cw
λ1 p1• /µ1 + λ2 p2• /µ2 (n + 1) ≥ 0, λ1 p1• + λ2 p2•
which corresponds to the Naor’s model with a modified mean service time, where the expectation is conditioned on an arrival event.
4
EO case: only the environment is observable
Now, we consider the EO case when an arriving customer observes the current phase of the environment but does not see the queue length. Then, the customers’ equilibrium strategy can be described by two probabilities a1 and a2 . It is a randomized strategy [9, 11]. A customer decides to join the queue with probability ai , if they observe the environment in phase i = 1, 2. Under this strategy, the dynamics of the system is a random walk in random environment (for the state transitions see Fig. 1).
a1 λ1 0
Env. 1
a1 λ1 1
µ1 η2
η1
η1
a2 λ2 Env. 2
3
µ1 η2
0
η1
a2 λ2
µ1 η2
η1 a2 λ2
a2 λ2 2
µ2
···
µ1 η2
1 µ2
a1 λ1
a1 λ1 2
3
···
µ2
µ2
Fig. 1. Transition diagram when only the environment is observable.
The expected utility can be written in the following form: UE=i = R − cw
∞ X
E0 [S|L = n, E = i]P0 [L = n|E = i]
n=0
= R − cw
∞ X
∞ X p0 pin si (n) in = R − c si (n) , w 0 p pi• i• n=0 n=0
i = 1, 2.
(20)
We observe that, in this case, the factors involving the arrival rates cancel in (20), so that we can use the stationary probabilities rather than their Palm counterparts. This is consistent with the literature [24, 16], where it was established that the PASTA property holds conditionally on the environment.
10
K. Avrachenkov and U. Yechiali
The equilibrium probabilities a∗i , i = 1, 2, are solutions of the best-response conditions UE=i (a∗1 , a∗2 ) ≤ 0, a∗i = 0, UE=i (a∗1 , a∗2 ) = 0, 0 < a∗i < 1, (21) UE=i (a∗1 , a∗2 ) ≥ 0, a∗i = 1. Again, we have an explicit expression for si (n) but not for the stationary probabilities pin . Therefore, as in the QO case, we consider two limiting cases: the case of rapid oscillations of the environment and the case of very slow transitions between the environment phases. In these cases, the stationary distribution has an explicit product-form. 4.1
EO case: rapid oscillations of the environment
Here we assume that the environment oscillates rapidly between two phases 1 and 2. Specifically, η1 and η2 tend to infinity simultaneously and their ratio η1 /η2 tends to a finite constant C. In the limit, as the rates go to infinity, the stationary probabilities converge to pin = pi• (1 − λ̄/µ̄)(λ̄/µ̄)n ,
(22)
where λ̄ = p1• a1 λ1 + p2• a2 λ2
µ̄ = p1• µ1 + p2• µ2 ,
and p1• = 1/(1 + C), p2• = C/(1 + C). In addition to the justification in [25], this can also be justified in the framework of singularly perturbed Markov chains [1, 2]. Using (17), we conclude that for i = 1, 2 cw UE=i (a1 , a2 ) = R − µ̄
λ̄ 1− µ̄
X ∞
n λ̄ cw (n + 1) =R− µ̄ µ̄ − λ̄ n=0
and the utility is independent of the phase when a customer arrives. Intuitively, this follows from the fact that the environment oscillates very rapidly. The system as a whole resembles an M/M/1 queue with arrival rate λ̄, service rate µ̄, whose mean sojourn time is 1/(µ̄ − λ̄). Define λmax = p1• λ1 + p2• λ2 . Similarly to Chapter 3 of [11], we can classify the equilibrium strategies into three cases: 1. If λmax ≤ µ̄ − cw /R, then a∗1 = a∗2 = 1; 2. If 0 ≤ µ̄ − cw /R < λ̄max , choose a∗1 , a∗2 such that p1• λ1 a1 + p2• λ2 a2 = µ̄ − cw /R;
(23)
3. If µ̄ − cw /R < 0 (i.e., R < cw /µ̄), then a∗1 = a∗2 = 0. We note that there is freedom in the choice of a∗1 and a∗2 in case 2. One natural option is to choose the same a∗ = (µ̄ − cw /R)/λ̄max for the two phases of the environment.
Equilibrium Joining Strategies for Queues in Random Environment
4.2
11
EO case: very slow transitions between the environment phases
Now, let us consider the opposite situation when the transition rates between the phases of the environment are very slow. Technically, this means to let the rates η1 and η2 go to zero assuming that their ratio η1 /η2 goes to a finite constant C. In this case, as η1 and η2 go to zero, the stationary distribution converges to the product-form [25]: pin = pi• (1 − ai λi /µi )(ai λi /µi )n ,
i = 1, 2.
(24)
Due to strategic customers, we can assume that ai λi < µi , i = 1, 2, which implies that the system is stable in equilibrium. (The justification of the product form can be provided using the theory of singularly perturbed Markov chains [1, 2].) Combining (20) with (19) and (24), we obtain UE=i = R −
cw . µi − ai λi
Thus, in the case of very slow transitions between the environment phases, we have a combination of two models from [9], and the equilibrium strategies are given by µi − cw /R ∗ ai = , i = 1, 2, (25) λi [0,1] where [x][0,1] := min{1, max{0, x}}.
5
NO case: fully unobservable system
Finally, let us consider the NO case when no information is available to an arriving customer except the knowledge of the system parameters. In this case, the equilibrium strategy is again randomized [11], given by the joining probability a. Under this strategy, the dynamics of the system is again a random walk in random environment (for the state transitions see Fig. 2).
aλ1
aλ1
0
Env. 1
2
µ1 η2
η1
η1
aλ2 Env. 2
0
η1
aλ2
µ1 η2
η1 aλ2
aλ2 2
µ2
···
µ1 η2
1 µ2
3
µ1 η2
aλ1
aλ1
1
3 µ2
··· µ2
Fig. 2. Transition diagram for the fully unobservable case.
12
K. Avrachenkov and U. Yechiali
The expected utility is given by U = R − cw
∞ X X
E0 [S|E = i, L = n]P0 [E = i, L = n],
(26)
n=0 i=1,2
where the Palm distribution is given by P0 [E = i, L = n] = p0in =
λi pin . λ1 p1• + λ2 p2•
(27)
Thus, we have U = R − cw
∞ X λ2 p2n λ1 p1n + s2 (n) s1 (n) λ p + λ p λ p 1 1• 2 2• 1 1• + λ2 p2• n=0 n=0 ∞ X
! .
(28)
Since in general we do not have an explicit expression for the stationary distribution, we proceed to the analysis of the two limiting cases.
5.1
NO case: rapid oscillations of the environment
As in the EO scenario, in the limit as the rates go to infinity, the stationary probabilities converge to [25] pin = pi• (1 − λ̄/µ̄)(λ̄/µ̄)n ,
(29)
where λ̄ = a(p1• λ1 + p2• λ2 ) p1• =
1 1+C
and µ̄ = p1• µ1 + p2• µ2 , and
p2• =
C . 1+C
Combining (28) with (29) and (17), we obtain U =R−
cw . µ̄ − λ̄
Hence this case is equivalent to the model [9] with the arrival and service rates averaged with respect to the rapidly oscillating environment. Consequently, we have the following classification of the equilibrium strategies: 1. If λ̄max ≤ µ̄ − cw /R, then a∗ = 1; 2. If 0 ≤ µ̄ − cw /R < λ̄max , then a∗ = (µ̄ − cw /R)/λ̄max ; 3. If µ̄ − cw /R < 0 (i.e., R < cw /µ̄), then a∗ = 0; +Cλ2 where λ̄max = p1• λ1 + p2• λ2 = λ11+C .
Equilibrium Joining Strategies for Queues in Random Environment
5.2
13
NO case: very slow transitions between the environment phases
As in the EO case (see Section 4.2), in the limit as the rates go to zero, the stationary probabilities converge to [25] pin = pi• (1 − aλi /µi )(aλi /µi )n ,
i = 1, 2.
(30)
Combining (28) with (30), (27) and (19), we can write U = R − cw
p01• p02• + µ1 − aλ1 µ2 − aλ2
= R − cw
p01• /µ1 p0 /µ2 + 2• 1 − aρ1 1 − aρ2
,
(31)
with ρi = λi /µi , i = 1, 2. Without loss of generality, assume that ρ1 < ρ2 . Then, it is easy to see that the function f (a) =
p01• /µ1 p0 /µ2 + 2• 1 − aρ1 1 − aρ2
has two vertical asymptotes at a = 1/ρ2 and a = 1/ρ1 and, except at these two points, it has positive derivative. We need to consider only the interval [0, 1/ρ2 ). Note also that p0 p0 f (0) = 1• + 2• . µ1 µ2 Thus, we have the following classification of the equilibrium strategies: p0
p0
1. If cRw ≤ µ1•1 + µ2•2 , then a∗ = 0; 2. If ρ2 < 1, there are two sub-cases: p01• /µ1 p02• /µ2 ∗ 1−ρ1 + 1−ρ2 , then a = 1; 0 0 p1• /µ1 p2• /µ2 If cRw ≤ 1−ρ + 1−ρ , then 1 2
(a) If cRw > (b)
(ρ1 + ρ2 )R/cw − ρ2 p01• /µ1 − ρ1 p02• /µ2 − a = 2ρ1 ρ2 R/cw ∗
√
D
,
(32)
where 2 ρ2 p01• ρ1 p02• R R p01• p02• R − − − 4ρ1 ρ2 − − . D = (ρ1 + ρ2 ) cw µ1 µ2 cw cw µ1 µ2 p0
p0
3. If ρ2 ≥ 1 and cRw > µ1•1 + µ2•2 , then a∗ is given by (32). It is interesting to observe that in comparison with the EO case with slow transitions between the environment phases, in the NO case we do not have a straightforward modification of the basic model in [9].
14
6
K. Avrachenkov and U. Yechiali
Numerical example
We further investigate numerically the EO case described in Section 4. As noted there, for finite values of η1 and η2 , we do not have a closed-form expression for the stationary distribution. However, for fixed joining probabilities a1 and a2 , the process is a quasi-birth-and-death (QBD) process with 2 × 2 matrix blocks describing transitions between and within levels. Thus, the stationary distribution has the matrix-geometric form pn = p0 Rn ,
n = 1, 2, ...
where pn = [p1n p2n ] and R ∈ R2×2 is the minimal nonnegative solution of a second-order polynomial matrix equation [19, 20]. Let us choose the following set of parameters: λ1 = 0.8, λ2 = 1.2, µ1 = 1.0, µ2 = 1.4 and cw = 1, R = 5/3. We take η1 = Cη2 with C = 0.75 and vary η2 . With this value of C, the environment marginal stationary probabilities are p1• = 1/(1 + C) = 4/7, p2• = C/(1 + C) = 3/7. By (25), the slow-transition limit is 1 2 ∗ ∗ , . [a1 , a2 ] −−−→ η2 →0 2 3 We plot the equilibrium joining probabilities a∗1 and a∗2 as functions of η2 in Figure 3. The dashed lines there correspond to the slow-transition limit. In the fast-transition limit, as η1 , η2 → ∞, any pair (a∗1 , a∗2 ) satisfying (23) constitutes an equilibrium. In the present numerical example, this equation takes the form 8a∗1 + 9a∗2 = 10, which is satisfied to good accuracy by a∗1 (100) = 0.395 and a∗2 (100) = 0.759. Note that, for every finite η2 , the two phase-dependent utilities determine a particular pair (a∗1 , a∗2 ), whereas in the rapid-oscillation limit the two utilities coincide and the limiting model admits a continuum of equilibria. The numerical continuation appears to select a point near (0.395, 0.759) from this continuum.
7
Conclusion
We studied equilibrium joining strategies in an M/M/1-type queue operating in a two-phase random environment under four information scenarios: fully observable (FO), queue-length observable (QO), environment observable (EO), and no observation (NO). We derived equilibrium characterizations in each case and obtained explicit results in the limiting regimes of rapid and very slow oscillations of the environment. Several interesting questions remain open. For example, we would like to understand equilibrium selection in singular limits, for example whether the equilibrium selected by continuation from finite transition rates can be characterized analytically or justified by another selection principle. We would also like to investigate monotonicity results for the EO case.
Equilibrium Joining Strategies for Queues in Random Environment
15
Fig. 3. EO case: Equilibrium joining probabilities a∗1 and a∗2 as functions of η2 . The dashed lines correspond to the limits of the joining probabilities as η2 → 0.
Acknowledgments. We would like to thank Jake Clarkson and Refael Hassin for their helpful remarks. U. Yechiali is supported by the Israel Science Foundation, Grant No.1968/23.
References 1. Altman, E., Avrachenkov, K.E., Núnez-Queija, R.: Perturbation analysis for denumerable Markov chains with application to queueing models. Advances in Applied Probability 36(3), 839–853 (2004) 2. Avrachenkov, K.E., Filar, J.A., Howlett, P.G.: Analytic Perturbation Theory and its Applications. SIAM (2013) 3. Baccelli, F., Makowski, A.M.: Stability and bounds for single server queues in random environment. Stochastic Models 2(2), 281–291 (1986) 4. Baccelli, F., Brémaud, P.: Palm Probabilities and Stationary Queues. Springer (1987) 5. Economou, A., Kanta, S.: Equilibrium balking strategies in the observable singleserver queue with breakdowns and repairs. Operations Research Letters 36(6), 696–699 (2008) 6. Economou, A., Manou, A.: Equilibrium balking strategies for a clearing queueing system in alternating environment. Annals of Operations Research 208, 489–514 (2013) 7. Economou, A., Manou, A.: Strategic behavior in an observable fluid queue with an alternating service process. European Journal of Operational Research 254(1), 148–160 (2016)
16
K. Avrachenkov and U. Yechiali
8. Economou, A., Logothetis, D., Manou, A.: The value of reneging for strategic customers in queueing systems with server vacations/failures. European Journal of Operational Research 299(3), 960–976 (2022) 9. Edelson, N.M., Hilderbrand, D.K.: Congestion tolls for Poisson queuing processes. Econometrica 43, 81–92 (1975) 10. Gupta, V., Harchol-Balter, M., Wolf, A.S., Yechiali, U.: Fundamental characteristics of queues with fluctuating load. In: Proceedings of ACM SIGMETRICS, pp. 203–215 (2006) 11. Hassin, R., Haviv, M.: To Queue or Not to Queue: Equilibrium Behavior in Queueing Systems. Springer (2003) 12. Hassin, R.: Rational Queueing. CRC Press (2016) 13. Hassin, R., Haviv, M., Oz, B.: Strategic behavior in queues with arrival rate uncertainty. European Journal of Operational Research 309(1), 217–224 (2023) 14. Jagannathan, K., Menache, I., Modiano, E., Zussman, G.: Non-cooperative spectrum access: The dedicated vs. free spectrum choice. IEEE Journal on Selected Areas in Communications 30(11), 2251–2261 (2012) 15. Kemeny, J.G., Snell, J.L.: Finite Markov Chains. 2nd edn. Springer (1976) 16. Melamed, B., Whitt, W.: On arrivals that see time averages: A martingale approach. Journal of Applied Probability 27(2), 376–384 (1990) 17. Müller, A., Stoyan, D.: Comparison Methods for Stochastic Models and Risks. Wiley (2002) 18. Naor, P.: The regulation of queue size by levying tolls. Econometrica 37(1), 15–24 (1969) 19. Neuts, M.F.: The M/M/1 queue with randomly varying arrival and service rates. Opsearch 15, 139–157 (1978) 20. Neuts, M.F.: Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Johns Hopkins University Press (1981) 21. Paz, N., Yechiali, U.: A note on the M/M/∞ queue in random environment. Technical report (2007). https://www.math.tau.ac.il/ uriy/Publications.html 22. Paz, N., Yechiali, U.: An M/M/1 queue in random environment with disasters. Asia-Pacific Journal of Operational Research 31(3), 1450016 (2014) 23. Purdue, P.: The M/M/1 queue in a Markovian environment. Operations Research 22(3), 562–569 (1974) 24. Van Doorn, E.A., Regterschot, G.J.K.: Conditional PASTA. Operations Research Letters 7(5), 229–232 (1988) 25. Yechiali, U., Naor, P.: Queuing problems with heterogeneous arrivals and service. Operations Research 19(3), 722–734 (1971) 26. Yechiali, U.: On optimal balking rules and toll charges in the GI/M/1 queuing process. Operations Research 19(2), 349–370 (1971) 27. Yechiali, U.: Customers’ optimal joining rules for the GI/M/s queue. Management Science 18(7), 434–443 (1972)