# Social Optimization and Pricing Strategies in Unobservable Queues with Delayed Multiple Vacations

Authors: Ruiling Tian
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

The paper considers the single-server Markovian queues with delayed multiple vacations. Once the system becomes empty, the server will experience a changeover time to begin the vacation. By using the matrix-geometric solution method, we obtain the stationary probability distribution and the mean queue length under almost unobservable and fully unobservable cases. Based on the system status information and a linear reward-cost structure reflecting the desire of customers for service and their unwillingness for waiting, the social welfare function is determined. We also investigate optimal pricing strategies of the server under the ex-postpayment scheme and the ex-antepayment scheme, and we get the customer’s equilibrium strategy under optimal pricing strategy. Finally, we illustrate the effect of several parameters and information levels on socially optimal strategies and optimal social benefit by numerical examples.


---

## Body

## 1. Introduction

Over the past few decades, more and more people have become keen to study queueing systems from a game-theoretic perspective. This study of queueing models was initiated by Naor [1] and Edelson and Hildebrand [2] who studied the M/M/1 model with a simple linear reward-cost structure. They obtained customers’ equilibrium and socially optimal strategies for observable and unobservable cases. From then on, many authors have investigated the same problem for various queueing systems incorporating diverse characteristics. The monograph written by Hassin and Haviv [3] introduced the main results and solution methodology about these models with extensive bibliographical references.Queueing models with vacations have been developed as useful performance analysis tools for computer systems, communication networks, and flexible manufacturing systems. As to strategic behavior in the vacation queues, Burnetas and Economou [4] first studied a Markovian single-server queueing system with setup times. They derived equilibrium strategies for the customers under different levels of information and analyzed social benefit under these strategies. Then, Economou and Kanta [5] considered equilibrium threshold strategies in the fully observable and almost observable Markovian single-server queue with breakdowns and repairs. Guo and Hassin [6] studied the strategic behavior and social optimization in Markovian queues with N policy. This work was extended by Guo and Hassin [7] to heterogeneous customers. Sun et al. [8, 9] analyzed customers’ equilibrium and socially optimal balking strategies in the observable and unobservable queues with three types of setup/closedown policies, respectively. Liu et al. [10] investigated equilibrium thresholds of customers in observable M/M/1 queueing systems with a single vacation. Zhang et al. [11] and Sun and Li [12] studied almost simultaneously equilibrium balking strategies in M/M/1 queues with multiple working vacations for different cases with respect to the system information. But Sun and Li [12] also observed socially optimal joining strategies and optimal social benefit. Subsequently, Sun et al. [13, 14] considered the customers’ optimal balking behavior in some single-server Markovian queues with two-stage working vacations and double adaptive working vacations, respectively. Wang and Zhang [15] discussed the equilibrium strategies in the Markovian queues with a single working vacation. Then, Tian et al. [16] studied equilibrium and optimal strategies in M/M/1 queues with multiple working vacations and vacation interruptions under three different levels of system information. Doo Ho Lee [17] observed customer’s equilibrium joining/balking behaviors in M/M/1 queues with a single working vacation and vacation interruptions. About comprehensive and excellent study on strategic queueing systems with vacations, readers are referred to chapter 10 in the book of Hassin [18].As for the work studying pricing strategy and server profits in queueing systems, Sun et al. [19] studied price decisions of the two servers in equilibrium under competition in batch-arrival queues with complementary services. They introduced two pricing scheme: ex-postpayment (EPP) scheme and ex-antepayment (EAP) scheme. Under EPP scheme, the server imposes a price proportional to sojourn time after completing service, while under EAP scheme the server charges a fee before offering service. Ma and Liu [20] observed customers’ equilibrium behavior and optimal pricing strategies in a discrete-time queue under EPP and EAP schemes. Doo ho Lee [21] dealt with optimal pricing strategies in almost and fully unobservable queues with negative customers. Moreover, Sun et al. [9] analyzed social optimization and profit maximization and they got optimal price for motivating customers to adopt socially optimal strategies. Wang and Zhang [22] investigated the optimal price that maximized server profits in a retrial queue with delayed vacations.In this paper, we consider almost and fully unobservable queueing models with delayed multiple vacations. As to the almost unobservable case, arriving customer can only observe the state of the server and cannot observe the number of present customers before making decision, while for the fully unobservable case, a customer cannot observe the states of the system. The aim of this paper is to study the socially optimal strategies and optimal pricing strategies in the context of an unobservable M/M/1 queue with delayed multiple vacations.This paper is organized as follows. Descriptions of the model are given in Section2. In Sections 3 and 4, we determine social benefit and optimal pricing strategies in the almost unobservable and fully unobservable cases, respectively. In Section 5, some numerical examples are presented to illustrate the effect of several parameters on socially optimal strategies and optimal social benefit (server profits) in two cases. Finally, conclusions are given in Section 6.


## 2. Model Description

Consider a single-server M/M/1 queue with delayed multiple vacations where customers arrive according to a Poisson process with a rateλ. In a busy period, service times are supposed to be exponentially distributed with a rate μ. Upon the completion of service, if there is no customer in the system, the server will stay in the system for a period of time, called the delayed period or the changeover time. The delayed period follows an exponential distribution with parameter ξ. If a customer arrives during the delayed period, the server starts to serve the customer immediately. Otherwise, after the delayed period, the server will take a vacation immediately at the end of delayed period. If the system is still empty after a vacation, the server will take another vacation; otherwise he begins to server the customers. The vacation times are exponentially distributed with a rate θ.We assume that the interarrival times, the service times, and the vacation times are mutually independent. In addition, the service discipline is first in first out (FIFO).Denote byN(t) the number of customers in the system at time t and let (1)Jt=0,the  server  is  on  vacation  period  at  timet,1,the  server  is  busy  or  in  a  delayed  time  at  timet.Then, the process {(N(t),J(t)),t≥0} is a two-dimensional continuous-time Markov chain with the state space Ω={(n,i)∣n≥0,i=0,1}.Arriving customers are assumed to be identical and they can decide whether to join or balk upon arrival. We assume that every customer receives a reward ofR units after completing service and suffers a waiting cost of C units per time unit that the customer remains in the system. Then, a customer’s utility consists of a reward for receiving service minus a waiting cost based on a linear cost structure. Customers are risk neutral and maximize their expected net benefit. Finally, we assume that there are no retrials of balking customers nor reneging of waiting customers.In the following sections, we consider social benefit and server profit under two different cases.


## 3. Almost Unobservable Queues

In this section, we focus on the almost unobservable case, where arriving customers can only observe the state of the server at their arrival instant and do not know the number of customers present.


### 3.1. Social Optimization

There are four pure strategies available for a customer, i.e., to join the queue or not to join the queue at the statei(i=0,1). A pure or mixed strategy can be described by a fraction qi(0≤q≤1), which is the probability of joining when the server is at the state i(i=0,1), and the effective arrival rate of the arriving customers is λqi. The transition diagram is illustrated in Figure 1.Figure 1
Transition rate diagram for the almost unobservable queue.Using the lexicographical sequence for the states, the transition rate matrixQ can be written as the tri-diagonal block matrix: (2)Q=A0CBACBACBAC⋱⋱⋱,where (3)A0=-λq00ξ-λq1+ξ,B=000μ,A=-λq0+θθ0-λq1+μ,C=λq000λq1.The structure ofQ indicates that {(N(t),J(t)),t≥0} is a quasibirth and death process (see Neuts [23]). To analyze this QBD process, we need to solve the matrix quadratic equation (4)R2B+RA+C=0,for the minimal nonnegative solution and this solution is called the rate matrix and denoted by R.Because the coefficients of (4) are all upper triangular matrices, we can assume that R has the same structure as (5)R=r11r120r22.Substituting R2 and R into (4), we get the following results: (6)R=σ0ρ00ρ1,and (7)Rn=σ0nρ0∑j=0n-1σ0jρ1n-j-10ρ1n,where (8)ρ0=λq0μ,ρ1=λq1μ,σ0=λq0λq0+θ.Denote the stationary distribution as(9)πni=limt→∞⁡PNt=n,Jt=i,n,i∈Ω.πn=πn0,πn1,n≥0,Theorem 1.
Assuming thatρ1<1 and ρ1≠σ0, the stationary probabilities {πni:(n,i)∈Ω} are as follows: (10)πn0=Kσ0n,n≥0,(11)πn1=Kρ0σ0n-ρ1nσ0-ρ1+λq0ξρ1n,n≥0,where (12)K=1-σ01-ρ11-ρ1+ρ0+λq0ξ1-σ0-1.Proof.
Using the matrix-geometric solution method, we have(13)πn=πn0,πn1=π00,π01Rn,n≥1,and (π00,π01) satisfies the set of equations (14)π00,π01BR=0,where B[R]=A0+RB. Solving (14) and letting π00=K, we get (15)π00,π01=K1,λq0ξ,By (13) and (15), we obtain (16)πn0=Kσ0n,n≥0,πn1=Kρ0σ0n-ρ1nσ0-ρ1+λq0ξρ1n,n≥0,Finally, π00=K can be determined by the normalization condition.From (10) and (11), we get the steady-state probability that the server is in state i(i=0,1), denoted by pi, as follows: (17)p0=∑n=0∞πn0=K1-σ0,(18)p1=∑n=0∞πn1=Kρ01-σ01-ρ1+λq0ξ11-ρ1.So the effective arrival rate is (19)λ¯=λp0q0+p1q1=λq0ξ+λq11-σ0ξ1-ρ1+ρ0+λq01-σ0=λq0μξλq0+θ+λq1θξλq0+θμ-λq1+λq0+λq0μθ.The probability generating function of the queue length, denoted byL(z), is as follows: (20)Lz=∑n=0∞znπn0+πn1=K11-σ0z+ρ0z1-σ0z1-ρ1z+λq0ξ11-ρ1z=1-ρ11-ρ1zK1-ρ11-ρ1z1-σ0z+ρ0z1-σ0z+λq0ξ=1-ρ11-ρ1zK1-ρ11-σ01-ρ1z+ρ0z1-σ01-σ0z+λq0ξ1-σ0.By the stochastic decomposition property, we get the mean number of the customers in the system, denoted by L(q0,q1), (21)Lq0,q1=ρ11-ρ1+ξρ0-ρ1+σ01-σ0ξ1-ρ1+ρ0+λq01-σ0=λq1μ-λq1+ξλq0+θλq0-λq1λq0+θ+λq0μθξλq0+θμ-λq1+λq0+λq0μθ.Hence, the mean sojourn time of a customer who decides to enter upon his arrival can be obtained by using Little’s law(22)Wq0,q1=Lq0,q1λ¯=ξσ01-ρ12+ξρ01-σ0ρ1+λq0ρ11-σ02λq01-σ01-ρ1ξ+λq11-σ0.And the social benefit when all customers follow a mixed policy (q0,q1) can now be easily computed as follows: (23)Sauq0,q1=λ¯R-CLq0,q1=λ¯R-CWq0,q1=λ¯R-Cλq1μ-λq1+ξλq0+θλq0-λq1λq0+θ+λq0μθξλq0+θμ-λq1+λq0+λq0μθ.The goal of a social planner is to maximize overall social welfare. Solving the nonlinear programming (NLP) problem maxSau(q0,q1) (of course, 0≤qi≤1, i=0,1), we can obtain the socially optimal strategy (q0∗,q1∗) to maximize social welfare.Let(24)f=fq0,q1=λq0+θλq0-λq1λq0+θ+λq0μ,(25)g=gq0,q1=ξλq0+θμ-λq1+λq0+λq0μθ.Then, we have (26)λ¯=λq0μξλq0+θ+λq1θgq0,q1,(27)Lq0,q1=λq1μ-λq1+ξfq0,q1θgq0,q1.So the social benefit Sau(q0,q1) can be expressed as follows: (28)Sauq0,q1=λq0μξλq0+θ+λq1θgq0,q1R-Cλq1μ-λq1+ξfq0,q1θgq0,q1.The first partial derivative of the function in (26) and (27) can be expressed as (29)∂λ¯∂q0=λμξμ-λq1ξλq0+θ2+λ2q02θ+λq1θ2g2,(30)∂λ¯∂q1=λ2q0μξ2λq0+θ2+θξλq0+θλq0+μ+λq0μξ2g2,(31)∂L∂q0=λξgλq0+θ3λq0+θ+μ-2λq1+λq0μ-fξ2λq0+θ+μ-λq1+μθθg2,(32)∂L∂q1=λξλq0+θξf-gλq0+θθg2.Therefore, the first and two partial derivatives of Sau(q0,q1) are given as (33)∂Sau∂q0=R∂λ¯∂q0-C∂L∂q0,∂Sau∂q1=R∂λ¯∂q1-C∂L∂q1,(34)D1=∂2Sau∂q02=R∂2λ¯∂q02-C∂2L∂q02,(35)D2=∂2Sau∂q0∂q1=∂2Sau∂q1∂q0=R∂2λ¯∂q0∂q1-C∂2L∂q0∂q1.(36)D3=∂2Sau∂q12=R∂2λ¯∂q12-C∂2L∂q12.Since the objective function expression is more complex, we only provide a specific and sufficient condition to ensure convex programming, and in this case we get the best joining probability.Theorem 2.
IfD1<0 and D1D3-D22>0, the optimization problem of Sau(q0,q1) is a convex maximization problem and there exists a unique optimal joining strategy qi∗∈[0,1],i=0,1.Proof.
The optimization problem ofSau(q0,q1) has three constraints: 0≤qi≤1(i=0,1) and λq1<μ, and they are all real-valued linear functions. Therefore, the set of constraints is convex.
LetH(q0,q1) be the Hessian matrix of the objective function, and it has the form of (37)Hq0,q1=∂2Sau∂q02∂2Sau∂q0∂q1∂2Sau∂q1∂q0∂2Sau∂q12=D1D2D2D3.According to the definition of the convex maximization in Boyd and Vandenberghe [24], if D1<0 and D1D3-D22>0, H(q0,q1) is negative definite and the objective function Sau(q0,q1) should be strictly concave in the feasible region, which leads to the optimization problem of Sau(q0,q1) being a convex maximization problem. One property of convex programming is that the local optimal solution is the global optimal solution.
According to the discussion above, we can use Lagrange multiplier method, Karush-Kuhn-Tucker conditions, or Newton method to find the optimal solutions. However, the explicit form of the optimalqi∗∈[0,1](i=0,1) is too long and complicated; we only introduce the method and give numerical results later. Details about two above methods can be found in Boyd and Vandenberghe [24]. This completes the proof.Figure2 shows that social benefit Sau(q0,q1) is strictly concave and takes the maximum. We also obtain (q0∗,q1∗)=(0.8,0.75).Figure 2
Social benefit of almost unobservable queue forR=3,C=1,λ=1.2,μ=1.5,θ=0.8,ξ=1.


### 3.2. Profit Maximization

Now, we consider a monopolistic server that sets a profit-maximizing price under EPP and EAP schemes.( 1 ) EPP scheme model. We first consider the EPP scheme model in which the server sets a fee proportional to the customer’s sojourn time. Let T be the fee charged by the server and Pt be the expected server profit per time unit. In this case, we have the following results regarding the customer’s utility.Lemma 3.
In the almost unobservable queue, the expected utility of an ordinary customer who decides to join the system isUt=R-(C+T)W(q0,q1).Proof.
LetWi be the conditional expected sojourn time of an ordinary customer who decides to join at the state i(i=0,1). Then, we have W(q0,q1)=p0W0+p1W1. And the conditional expected benefit of such a customer who decides to enter the system at the state i is Ui=Ui(q0,q1)=R-(C+T)Wi(q0,q1)(i=0,1).
So for any customer who is willing to enter the system, his expected utility is(38)Ut=p0U0+p1U1=R-C+TWq0,q1.
At customer’s equilibrium, ifUi=0(i=0,1), we also have Ut=0 and obtain R=(C+T)W(q0,q1). Hence, at customer’s equilibrium, we find that the toll is a function of the customer’s joining probabilities, denoted by q0t and q1t(39)T=RWq0t,q1t-C.For the system with delayed multiple vacations, the monopoly’s problem is a nonlinear programming problem to maximize Pt with q0t and q1t: (40)Pt=λ¯TWq0t,q1t=λ¯R-CLq0t,q1t.Here, q0 and q1 in λ¯ are replaced by q0t and q1t. Then the objectives of a monopolistic server and the society are consistent with each other, so we can induce the socially optimal joining probabilities (q0∗,q1∗) by an appropriate price, which also maximizes profit of the server.
Moreover, as mentioned above, if the server chooses the optimal pricing strategy, the expected benefit of the customer equals(41)Ut=R-C+T∗Wq0,q1=R-RWq0∗,q1∗Wq0,q1.Based on the above analysis, we can give the following theorem.Theorem 4.
In the EPP scheme model, ifU0 and U1 have the same sign, there exists a unique equilibrium strategy where customers join the queue with probabilities q0∗ and q1∗ and the optimal price T∗=R/W(q0∗,q1∗)-C, and the server’s maximal profit is Pt∗=Sau(q0∗,q1∗).Proof.
Using the standard methodology of equilibrium analysis, we derive the following equilibria.
IfR≤(C+T∗)W(0,0), that is, Ut≤0: Because U0 and U1 have the same sign, so we have U0≤0 and U1≤0. In this case, even if no other customer joins, the residual utility of a customer who joins is less than or equal to 0. Therefore, q0e=q1e=0 is an equilibrium strategy. Moreover, in this case, balking is a dominant strategy.
IfR≥(C+T∗)W(1,1), that is, Ut≥0, U0≥0 and U1≥0: In this case, for every strategy of the other customers, the tagged customer has a positive expected net benefit if he decides to enter. Hence, the equilibrium strategy q0e=q1e=1.
If(C+T∗)W(0,0)<R<(C+T∗)W(1,1): In this case, if all customers who find the system empty enter the system with probability q0e=q1e=1, then the tagged customer suffers a negative expected benefit if he decides to enter. Hence, q0e=q1e=1 does not lead to an equilibrium. Similarly, if all customers use q0e=q1e=0 then the tagged customer receives a positive benefit from entering; thus q0e=q1e=0 also cannot be part of an equilibrium mixed strategy. Therefore, there exists a unique q0e=q1e satisfying Ut=0, U0=0, and U1=0. From (41), it can be seen that (q0∗,q1∗) is the zero point of the function Ut. In other words, they are also customers’ equilibrium strategy.( 2 ) EAP scheme model. Under the EAP scheme model, the server imposes a flat entry fee F for all those who decide to join. Let Pf be the server’s expected profit per time unit. The expected benefit for a customer is equal to Uf=R-F-CW(q0,q1). We can obtain customers’ equilibrium when Uf=0, and we obtain R=F+CW(q0,q1). At customer’s equilibrium, F is a function of q0f and q1f and has the form of F=R-CW(q0f,q1f).Similar to the EPP scheme, we establish the following NLP problem to maximizePf with respect to q0f and q1f: (42)Pf=λ¯F=λ¯R-CLq0f,q1f.And we also have the following theorem.Theorem 5.
In the EAP scheme model, ifU0 and U1 have the same sign, there exists a unique equilibrium strategy where customers join the queue with probabilities q0∗ and q1∗ and the optimal price F∗=R-W(q0∗,q1∗) and the server’s maximal profit is Pf∗=Sau(q0∗,q1∗).From the above analysis, we can see that the server can make the equilibrium strategy and the socially optimal strategy unified by setting the appropriate price.Figure3 shows that optimal prices T∗ and F∗ first increase when the arrival rate λ is very low and then decrease. Therefore, an increase in demand may result in a reduction in price.Figure 3
Monopoly priceT∗ and F∗ for R=4,C=1,μ=1.5,θ=0.8,ξ=1.


## 3.1. Social Optimization

There are four pure strategies available for a customer, i.e., to join the queue or not to join the queue at the statei(i=0,1). A pure or mixed strategy can be described by a fraction qi(0≤q≤1), which is the probability of joining when the server is at the state i(i=0,1), and the effective arrival rate of the arriving customers is λqi. The transition diagram is illustrated in Figure 1.Figure 1
Transition rate diagram for the almost unobservable queue.Using the lexicographical sequence for the states, the transition rate matrixQ can be written as the tri-diagonal block matrix: (2)Q=A0CBACBACBAC⋱⋱⋱,where (3)A0=-λq00ξ-λq1+ξ,B=000μ,A=-λq0+θθ0-λq1+μ,C=λq000λq1.The structure ofQ indicates that {(N(t),J(t)),t≥0} is a quasibirth and death process (see Neuts [23]). To analyze this QBD process, we need to solve the matrix quadratic equation (4)R2B+RA+C=0,for the minimal nonnegative solution and this solution is called the rate matrix and denoted by R.Because the coefficients of (4) are all upper triangular matrices, we can assume that R has the same structure as (5)R=r11r120r22.Substituting R2 and R into (4), we get the following results: (6)R=σ0ρ00ρ1,and (7)Rn=σ0nρ0∑j=0n-1σ0jρ1n-j-10ρ1n,where (8)ρ0=λq0μ,ρ1=λq1μ,σ0=λq0λq0+θ.Denote the stationary distribution as(9)πni=limt→∞⁡PNt=n,Jt=i,n,i∈Ω.πn=πn0,πn1,n≥0,Theorem 1.
Assuming thatρ1<1 and ρ1≠σ0, the stationary probabilities {πni:(n,i)∈Ω} are as follows: (10)πn0=Kσ0n,n≥0,(11)πn1=Kρ0σ0n-ρ1nσ0-ρ1+λq0ξρ1n,n≥0,where (12)K=1-σ01-ρ11-ρ1+ρ0+λq0ξ1-σ0-1.Proof.
Using the matrix-geometric solution method, we have(13)πn=πn0,πn1=π00,π01Rn,n≥1,and (π00,π01) satisfies the set of equations (14)π00,π01BR=0,where B[R]=A0+RB. Solving (14) and letting π00=K, we get (15)π00,π01=K1,λq0ξ,By (13) and (15), we obtain (16)πn0=Kσ0n,n≥0,πn1=Kρ0σ0n-ρ1nσ0-ρ1+λq0ξρ1n,n≥0,Finally, π00=K can be determined by the normalization condition.From (10) and (11), we get the steady-state probability that the server is in state i(i=0,1), denoted by pi, as follows: (17)p0=∑n=0∞πn0=K1-σ0,(18)p1=∑n=0∞πn1=Kρ01-σ01-ρ1+λq0ξ11-ρ1.So the effective arrival rate is (19)λ¯=λp0q0+p1q1=λq0ξ+λq11-σ0ξ1-ρ1+ρ0+λq01-σ0=λq0μξλq0+θ+λq1θξλq0+θμ-λq1+λq0+λq0μθ.The probability generating function of the queue length, denoted byL(z), is as follows: (20)Lz=∑n=0∞znπn0+πn1=K11-σ0z+ρ0z1-σ0z1-ρ1z+λq0ξ11-ρ1z=1-ρ11-ρ1zK1-ρ11-ρ1z1-σ0z+ρ0z1-σ0z+λq0ξ=1-ρ11-ρ1zK1-ρ11-σ01-ρ1z+ρ0z1-σ01-σ0z+λq0ξ1-σ0.By the stochastic decomposition property, we get the mean number of the customers in the system, denoted by L(q0,q1), (21)Lq0,q1=ρ11-ρ1+ξρ0-ρ1+σ01-σ0ξ1-ρ1+ρ0+λq01-σ0=λq1μ-λq1+ξλq0+θλq0-λq1λq0+θ+λq0μθξλq0+θμ-λq1+λq0+λq0μθ.Hence, the mean sojourn time of a customer who decides to enter upon his arrival can be obtained by using Little’s law(22)Wq0,q1=Lq0,q1λ¯=ξσ01-ρ12+ξρ01-σ0ρ1+λq0ρ11-σ02λq01-σ01-ρ1ξ+λq11-σ0.And the social benefit when all customers follow a mixed policy (q0,q1) can now be easily computed as follows: (23)Sauq0,q1=λ¯R-CLq0,q1=λ¯R-CWq0,q1=λ¯R-Cλq1μ-λq1+ξλq0+θλq0-λq1λq0+θ+λq0μθξλq0+θμ-λq1+λq0+λq0μθ.The goal of a social planner is to maximize overall social welfare. Solving the nonlinear programming (NLP) problem maxSau(q0,q1) (of course, 0≤qi≤1, i=0,1), we can obtain the socially optimal strategy (q0∗,q1∗) to maximize social welfare.Let(24)f=fq0,q1=λq0+θλq0-λq1λq0+θ+λq0μ,(25)g=gq0,q1=ξλq0+θμ-λq1+λq0+λq0μθ.Then, we have (26)λ¯=λq0μξλq0+θ+λq1θgq0,q1,(27)Lq0,q1=λq1μ-λq1+ξfq0,q1θgq0,q1.So the social benefit Sau(q0,q1) can be expressed as follows: (28)Sauq0,q1=λq0μξλq0+θ+λq1θgq0,q1R-Cλq1μ-λq1+ξfq0,q1θgq0,q1.The first partial derivative of the function in (26) and (27) can be expressed as (29)∂λ¯∂q0=λμξμ-λq1ξλq0+θ2+λ2q02θ+λq1θ2g2,(30)∂λ¯∂q1=λ2q0μξ2λq0+θ2+θξλq0+θλq0+μ+λq0μξ2g2,(31)∂L∂q0=λξgλq0+θ3λq0+θ+μ-2λq1+λq0μ-fξ2λq0+θ+μ-λq1+μθθg2,(32)∂L∂q1=λξλq0+θξf-gλq0+θθg2.Therefore, the first and two partial derivatives of Sau(q0,q1) are given as (33)∂Sau∂q0=R∂λ¯∂q0-C∂L∂q0,∂Sau∂q1=R∂λ¯∂q1-C∂L∂q1,(34)D1=∂2Sau∂q02=R∂2λ¯∂q02-C∂2L∂q02,(35)D2=∂2Sau∂q0∂q1=∂2Sau∂q1∂q0=R∂2λ¯∂q0∂q1-C∂2L∂q0∂q1.(36)D3=∂2Sau∂q12=R∂2λ¯∂q12-C∂2L∂q12.Since the objective function expression is more complex, we only provide a specific and sufficient condition to ensure convex programming, and in this case we get the best joining probability.Theorem 2.
IfD1<0 and D1D3-D22>0, the optimization problem of Sau(q0,q1) is a convex maximization problem and there exists a unique optimal joining strategy qi∗∈[0,1],i=0,1.Proof.
The optimization problem ofSau(q0,q1) has three constraints: 0≤qi≤1(i=0,1) and λq1<μ, and they are all real-valued linear functions. Therefore, the set of constraints is convex.
LetH(q0,q1) be the Hessian matrix of the objective function, and it has the form of (37)Hq0,q1=∂2Sau∂q02∂2Sau∂q0∂q1∂2Sau∂q1∂q0∂2Sau∂q12=D1D2D2D3.According to the definition of the convex maximization in Boyd and Vandenberghe [24], if D1<0 and D1D3-D22>0, H(q0,q1) is negative definite and the objective function Sau(q0,q1) should be strictly concave in the feasible region, which leads to the optimization problem of Sau(q0,q1) being a convex maximization problem. One property of convex programming is that the local optimal solution is the global optimal solution.
According to the discussion above, we can use Lagrange multiplier method, Karush-Kuhn-Tucker conditions, or Newton method to find the optimal solutions. However, the explicit form of the optimalqi∗∈[0,1](i=0,1) is too long and complicated; we only introduce the method and give numerical results later. Details about two above methods can be found in Boyd and Vandenberghe [24]. This completes the proof.Figure2 shows that social benefit Sau(q0,q1) is strictly concave and takes the maximum. We also obtain (q0∗,q1∗)=(0.8,0.75).Figure 2
Social benefit of almost unobservable queue forR=3,C=1,λ=1.2,μ=1.5,θ=0.8,ξ=1.


## 3.2. Profit Maximization

Now, we consider a monopolistic server that sets a profit-maximizing price under EPP and EAP schemes.( 1 ) EPP scheme model. We first consider the EPP scheme model in which the server sets a fee proportional to the customer’s sojourn time. Let T be the fee charged by the server and Pt be the expected server profit per time unit. In this case, we have the following results regarding the customer’s utility.Lemma 3.
In the almost unobservable queue, the expected utility of an ordinary customer who decides to join the system isUt=R-(C+T)W(q0,q1).Proof.
LetWi be the conditional expected sojourn time of an ordinary customer who decides to join at the state i(i=0,1). Then, we have W(q0,q1)=p0W0+p1W1. And the conditional expected benefit of such a customer who decides to enter the system at the state i is Ui=Ui(q0,q1)=R-(C+T)Wi(q0,q1)(i=0,1).
So for any customer who is willing to enter the system, his expected utility is(38)Ut=p0U0+p1U1=R-C+TWq0,q1.
At customer’s equilibrium, ifUi=0(i=0,1), we also have Ut=0 and obtain R=(C+T)W(q0,q1). Hence, at customer’s equilibrium, we find that the toll is a function of the customer’s joining probabilities, denoted by q0t and q1t(39)T=RWq0t,q1t-C.For the system with delayed multiple vacations, the monopoly’s problem is a nonlinear programming problem to maximize Pt with q0t and q1t: (40)Pt=λ¯TWq0t,q1t=λ¯R-CLq0t,q1t.Here, q0 and q1 in λ¯ are replaced by q0t and q1t. Then the objectives of a monopolistic server and the society are consistent with each other, so we can induce the socially optimal joining probabilities (q0∗,q1∗) by an appropriate price, which also maximizes profit of the server.
Moreover, as mentioned above, if the server chooses the optimal pricing strategy, the expected benefit of the customer equals(41)Ut=R-C+T∗Wq0,q1=R-RWq0∗,q1∗Wq0,q1.Based on the above analysis, we can give the following theorem.Theorem 4.
In the EPP scheme model, ifU0 and U1 have the same sign, there exists a unique equilibrium strategy where customers join the queue with probabilities q0∗ and q1∗ and the optimal price T∗=R/W(q0∗,q1∗)-C, and the server’s maximal profit is Pt∗=Sau(q0∗,q1∗).Proof.
Using the standard methodology of equilibrium analysis, we derive the following equilibria.
IfR≤(C+T∗)W(0,0), that is, Ut≤0: Because U0 and U1 have the same sign, so we have U0≤0 and U1≤0. In this case, even if no other customer joins, the residual utility of a customer who joins is less than or equal to 0. Therefore, q0e=q1e=0 is an equilibrium strategy. Moreover, in this case, balking is a dominant strategy.
IfR≥(C+T∗)W(1,1), that is, Ut≥0, U0≥0 and U1≥0: In this case, for every strategy of the other customers, the tagged customer has a positive expected net benefit if he decides to enter. Hence, the equilibrium strategy q0e=q1e=1.
If(C+T∗)W(0,0)<R<(C+T∗)W(1,1): In this case, if all customers who find the system empty enter the system with probability q0e=q1e=1, then the tagged customer suffers a negative expected benefit if he decides to enter. Hence, q0e=q1e=1 does not lead to an equilibrium. Similarly, if all customers use q0e=q1e=0 then the tagged customer receives a positive benefit from entering; thus q0e=q1e=0 also cannot be part of an equilibrium mixed strategy. Therefore, there exists a unique q0e=q1e satisfying Ut=0, U0=0, and U1=0. From (41), it can be seen that (q0∗,q1∗) is the zero point of the function Ut. In other words, they are also customers’ equilibrium strategy.( 2 ) EAP scheme model. Under the EAP scheme model, the server imposes a flat entry fee F for all those who decide to join. Let Pf be the server’s expected profit per time unit. The expected benefit for a customer is equal to Uf=R-F-CW(q0,q1). We can obtain customers’ equilibrium when Uf=0, and we obtain R=F+CW(q0,q1). At customer’s equilibrium, F is a function of q0f and q1f and has the form of F=R-CW(q0f,q1f).Similar to the EPP scheme, we establish the following NLP problem to maximizePf with respect to q0f and q1f: (42)Pf=λ¯F=λ¯R-CLq0f,q1f.And we also have the following theorem.Theorem 5.
In the EAP scheme model, ifU0 and U1 have the same sign, there exists a unique equilibrium strategy where customers join the queue with probabilities q0∗ and q1∗ and the optimal price F∗=R-W(q0∗,q1∗) and the server’s maximal profit is Pf∗=Sau(q0∗,q1∗).From the above analysis, we can see that the server can make the equilibrium strategy and the socially optimal strategy unified by setting the appropriate price.Figure3 shows that optimal prices T∗ and F∗ first increase when the arrival rate λ is very low and then decrease. Therefore, an increase in demand may result in a reduction in price.Figure 3
Monopoly priceT∗ and F∗ for R=4,C=1,μ=1.5,θ=0.8,ξ=1.


## 4. Fully Unobservable Queues

In this section, arriving customers can observe neither the state of the server at their arrival instant nor the number of customers present.


### 4.1. Social Optimization

There are two pure strategies available for a customer, i.e., to join the queue or not to join the queue. A strategy can be described by a joining probabilityq(0≤q≤1), and the joining rate is λq. The transition diagram is illustrated in Figure 4.Figure 4
Transition rate diagram for the fully unobservable queues.The stationary distribution of the system when all customers follow a given strategyq can be obtained by taking q0=q1=q in the almost unobservable queue. So we have (43)πn0=Kσn,n≥0,πn1=Kρσn-ρnσ-ρ+λqξρn,n≥0,where (44)ρ=λqμ,σ=λqλq+θ,K=ξ1-ρ1-σξ+λq1-σ.From (43), we get the mean queue length, denoted by L(q), as follows: (45)Lq=λqμ-λq+ξλqλq+θθξλq+θ+λqθ.By using Little’s law, the mean sojourn time of a customer who decides to enter upon his arrival is as follows: (46)Wq=1λqLq=1μ-λq+ξλq+θθξλq+θ+λqθ.So the social benefit per time unit can now be easily computed as (47)Sfuq=λqR-CWq=λqR-Cλqμ-λq+ξλqλq+θθξλq+θ+λqθ.Letq∗ denote the socially optimal joining probability q∗, and let x∗ be the root of the first-order optimal condition Sfu′(q)=0. They have the following relation.Theorem 6.
If0<x∗<1 and Sfu′′(q)≤0, then q∗=x∗; if 0<x∗<1 and Sfu′′(q)>0 or x∗≥1, then q∗=1.In the analysis below, we will provide a specific and sufficient condition to ensure that the function in (47) is unimodal and strictly convex, and under this condition we obtain the optimal joining probability.Theorem 7.
Supposeρ<1. If 0≤q≤1 and λ3q3-μ3+3λqμ(λq+μ)-θ3≥0, then
( 1 ) the social benefit Sfu(q) is unimodal and strictly convex in [q1,q2], where (48)q1,q2=0,1∩q∣λ3q3-μ3+3λqμλq+μ-θ3≥0;
( 2 ) if 0<x∗<1, then q∗=x∗. Otherwise, q∗=1.Proof.
Letλq=λq. The first two derivatives of the mean sojourn time W(λq) are given by (49)W′λq=1μ-λq2-θξλqθ+ξ+θξ2,and (50)W′′λq=2μ-λq3+2θξθ+ξλqθ+ξ+θξ3.
The second-order derivative of the social benefit is(51)Sfu′′λq=-2CW′λq-CλqW′′λq=-2Cμμ-λq3-2Cθ2ξ2θ2+θλq+λq23.Thus, if λ3q3-μ3+3λqμ(λq+μ)-θ3≥0, then Sfu′′(λq)<0, and the social benefit Sfu(q) is unimodal and strictly convex in [q1,q2].In Figure5, we observe that Sfu(q) first increases and then decreases with q and have a maximum value at q=0.755<1. Hence, we have q∗=0.755.Figure 5
Social benefit of unobservable case whenR=5,C=1,λ=1.2,μ1=1.5,ξ=1,θ=0.8.


### 4.2. Profit Maximization

Under the EPP scheme, the price proportional to the customer’s waiting time is charged by the server. Thus, the expected residual utility of a customer isUt=R-(C+T)W(q). If Ut=0, we have R=(C+T)W(q). Hence, at customer’s equilibrium, the price is expressed with the joining probability qt, (52)T=RWqt-C.The monopoly’s problem is a NLP problem to maximize Pt with qt: (53)Pt=λqtTWqt=λqtR-CLqt.This is also a problem of maximizing social benefit. The price that induces social optimization and profit maximization equals T∗=R/W(q∗)-C, and the server’s maximal profit is Pt∗=Sfu(q∗). What is more, under the optimal price, q∗ is also an equilibrium strategy.In the EAP scheme model where the server imposes a flat fee for services, the expected benefit for a customer is equal toUf=R-F-CW(q). When Uf=0, we obtain customers’ equilibrium strategies and R=F+CW(q). At customers’ equilibrium, F is a function of joining probability qf and has the form of F=R-CW(qf). The monopoly’s problem is to maximize Pf=λqfF=λqfR-CL(qf).So the optimal price isF∗=R-W(q∗), and the server’s maximal profit is Pf∗=Sfu(q∗). This price makes customers’ equilibrium strategy consistent with the socially optimal strategy.Figure6 shows the socially optimal and monopolistic price for the unobservable queue.Figure 6
Monopoly priceT∗ and F∗ for R=5,C=1,μ=1.5,θ=0.8,ξ=1.From the above analysis, we can observe that the EPP and EAP mechanisms do not affect the customer equilibrium joining rate and the server’s maximum profits.


## 4.1. Social Optimization

There are two pure strategies available for a customer, i.e., to join the queue or not to join the queue. A strategy can be described by a joining probabilityq(0≤q≤1), and the joining rate is λq. The transition diagram is illustrated in Figure 4.Figure 4
Transition rate diagram for the fully unobservable queues.The stationary distribution of the system when all customers follow a given strategyq can be obtained by taking q0=q1=q in the almost unobservable queue. So we have (43)πn0=Kσn,n≥0,πn1=Kρσn-ρnσ-ρ+λqξρn,n≥0,where (44)ρ=λqμ,σ=λqλq+θ,K=ξ1-ρ1-σξ+λq1-σ.From (43), we get the mean queue length, denoted by L(q), as follows: (45)Lq=λqμ-λq+ξλqλq+θθξλq+θ+λqθ.By using Little’s law, the mean sojourn time of a customer who decides to enter upon his arrival is as follows: (46)Wq=1λqLq=1μ-λq+ξλq+θθξλq+θ+λqθ.So the social benefit per time unit can now be easily computed as (47)Sfuq=λqR-CWq=λqR-Cλqμ-λq+ξλqλq+θθξλq+θ+λqθ.Letq∗ denote the socially optimal joining probability q∗, and let x∗ be the root of the first-order optimal condition Sfu′(q)=0. They have the following relation.Theorem 6.
If0<x∗<1 and Sfu′′(q)≤0, then q∗=x∗; if 0<x∗<1 and Sfu′′(q)>0 or x∗≥1, then q∗=1.In the analysis below, we will provide a specific and sufficient condition to ensure that the function in (47) is unimodal and strictly convex, and under this condition we obtain the optimal joining probability.Theorem 7.
Supposeρ<1. If 0≤q≤1 and λ3q3-μ3+3λqμ(λq+μ)-θ3≥0, then
( 1 ) the social benefit Sfu(q) is unimodal and strictly convex in [q1,q2], where (48)q1,q2=0,1∩q∣λ3q3-μ3+3λqμλq+μ-θ3≥0;
( 2 ) if 0<x∗<1, then q∗=x∗. Otherwise, q∗=1.Proof.
Letλq=λq. The first two derivatives of the mean sojourn time W(λq) are given by (49)W′λq=1μ-λq2-θξλqθ+ξ+θξ2,and (50)W′′λq=2μ-λq3+2θξθ+ξλqθ+ξ+θξ3.
The second-order derivative of the social benefit is(51)Sfu′′λq=-2CW′λq-CλqW′′λq=-2Cμμ-λq3-2Cθ2ξ2θ2+θλq+λq23.Thus, if λ3q3-μ3+3λqμ(λq+μ)-θ3≥0, then Sfu′′(λq)<0, and the social benefit Sfu(q) is unimodal and strictly convex in [q1,q2].In Figure5, we observe that Sfu(q) first increases and then decreases with q and have a maximum value at q=0.755<1. Hence, we have q∗=0.755.Figure 5
Social benefit of unobservable case whenR=5,C=1,λ=1.2,μ1=1.5,ξ=1,θ=0.8.


## 4.2. Profit Maximization

Under the EPP scheme, the price proportional to the customer’s waiting time is charged by the server. Thus, the expected residual utility of a customer isUt=R-(C+T)W(q). If Ut=0, we have R=(C+T)W(q). Hence, at customer’s equilibrium, the price is expressed with the joining probability qt, (52)T=RWqt-C.The monopoly’s problem is a NLP problem to maximize Pt with qt: (53)Pt=λqtTWqt=λqtR-CLqt.This is also a problem of maximizing social benefit. The price that induces social optimization and profit maximization equals T∗=R/W(q∗)-C, and the server’s maximal profit is Pt∗=Sfu(q∗). What is more, under the optimal price, q∗ is also an equilibrium strategy.In the EAP scheme model where the server imposes a flat fee for services, the expected benefit for a customer is equal toUf=R-F-CW(q). When Uf=0, we obtain customers’ equilibrium strategies and R=F+CW(q). At customers’ equilibrium, F is a function of joining probability qf and has the form of F=R-CW(qf). The monopoly’s problem is to maximize Pf=λqfF=λqfR-CL(qf).So the optimal price isF∗=R-W(q∗), and the server’s maximal profit is Pf∗=Sfu(q∗). This price makes customers’ equilibrium strategy consistent with the socially optimal strategy.Figure6 shows the socially optimal and monopolistic price for the unobservable queue.Figure 6
Monopoly priceT∗ and F∗ for R=5,C=1,μ=1.5,θ=0.8,ξ=1.From the above analysis, we can observe that the EPP and EAP mechanisms do not affect the customer equilibrium joining rate and the server’s maximum profits.


## 5. Numerical Examples

In this section, we present some numerical analysis to investigate the sensitivity of socially optimal joining probabilities for customers and optimal social benefit (expected server profits) on system parameters.We first explore the sensitivity of the socially optimal entrance probabilities. From Figures7–10, we can make the following observations of socially optimal joining strategies for the almost and fully unobservable cases. The optimal probability in the fully unobservable queue is always between two optimal joining strategies in the almost unobservable case. However, the relative ordering of q0∗ and q1∗ cannot be determined. Therefore, when customers cannot observe the information about server’s state, they enter the queue with an intermediate strategy between those that the customers use when they are given the server’s state. As for the sensitivity about the system’s parameters, we observe that socially optimal strategies are first increasing with respect to service rate μ in Figure 7, and when μ continues to increase all probabilities are equal to 1. It is intuitive. That is, regardless of whether the customer has status information for the server, an increase in the service rate will reduce the expected waiting time of the customer. Figure 8 shows that optimal strategies decrease with arrival rate λ. This is because the system is more congested and an arriving customer is less willing to join the system when λ increases. In Figures 9 and 10, the behavior of optimal probabilities varies. While for the most part they are all increasing with θ, which is intuitive, there is a range of small values of θ in which q1∗ is decreasing. When the vacation time becomes shorter, the customer will be more willing to enter in vacation, which will lead to system congestion in the busy period. When ξ increases, the server can make the vacation faster. This may result in too many customers entering the system during the vacation period and the customers who arrive on busy period are less willing to enter.Figure 7
Socially optimal strategies whenR=3,C=1,λ=1,θ=0.8,ξ=1.Figure 8
Socially optimal strategies whenR=2,C=1,μ=1.5,θ=0.8,ξ=1.Figure 9
Socially optimal strategies whenR=5,C=1,λ=1,μ=1.5,ξ=1.Figure 10
Socially optimal strategies whenR=4,C=1,λ=1,μ=1.5,θ=0.8.Subsequently, we turn to the social benefit or server profit under optimal strategy for two information levels. In Figure11, the social benefit or server profit first monotonously increases and then keeps stable when λ exceeds the certain value. The reason is that customers’ waiting time is shorter when λ is small, which makes the social welfare improve. And when the arrival rate becomes larger, the customer’s maximum arrival rate tends to be stable. Figures 12 and 13 show that the social benefit or server profit is always increasing with service rate μ and vacation rate θ, which is intuitive. This is because the utility of individual customer becomes larger and the social benefits are also improved. Figure 14 shows that the social benefit or server profit decreases with respect to ξ. This is because shorter delayed time results in too many customers entering the vacation, which leads to system congestion and reduces social benefits. From these figures we find that Sfu(q∗)≤Sau(q0∗,q1∗). In order to get more social benefits, the social planner can appropriately disclose the status information of the server to the customers.Figure 11
Optimal social benefit whenR=4,C=1,μ=1.5,θ=0.8,ξ=1.Figure 12
Optimal social benefit whenR=3,C=1,λ=1,θ=0.8,ξ=1.Figure 13
Optimal social benefit whenR=5,C=1,λ=1,μ=1.5,ξ=1.Figure 14
Optimal social benefit whenR=5,C=1,λ=1,μ=1.5,θ=0.8.Finally, we are concerned with the delayed period which is the special feature of this paper. Taking the fully unobservable queue as an example, comparison work is carried out to show which mechanism, multiple vacations or delayed multiple vacations, is better in controlling the mean queue length and improving the social welfare. Figure15 shows that mean queue length L(q) is increasing with respect to q, and the social benefit Sfu(q) first increases and then decreases with q and has a maximum in Figure 16. On the other hand, Figures 15 and 16 show that the mean queue length for queues with vacations is always larger than that for queues with delayed vacations, and the social benefit for queues with delayed vacations is always greater than that for queues with vacations. Because in queues with vacations, when the system is empty, the server immediately begins to take a vacation and customers suffer a longer waiting time and a greater waiting cost, while in queues with delayed vacations. Some of the customers who arrived after the system was empty are served during the delayed time. All in all, delayed vacation somewhat relieves the system congestion problem and increases social benefits.Figure 15
Mean queue lengthL(q) of unobservable queues with delayed vacations and queues with vacations when R=5,C=1,λ=1.2,μ=1.5,θ=0.8,ξ=1.Figure 16
Social benefit of unobservable queues with delayed vacations and queues with vacations whenR=5,C=1,λ=1.2,μ=1.5,θ=0.8,ξ=1.


## 6. Conclusion

In this paper, we discuss the socially optimal joining probabilities and optimal pricing strategies of the server in the almost and fully unobservable M/M/1 queueing systems with delayed multiple vacations. We first obtain the steady-state performance measures and social benefit in two different cases. Meanwhile, we assume that the server can choose the optimal pricing strategies that maximize the monopoly profit under ex-postpayment (EPP) scheme and ex-antepayment (EAP) scheme. Moreover, the servers’ maximum profits in the two pricing schemes are also identical and have equal optimal social benefit. Finally, we compared socially optimal strategy and optimal social benefit for almost and fully unobservable cases numerically, and we observed that the disclosure of system information had certain benefits for social planner. Furthermore, the direct generalization is the study of the corresponding non-Markovian queues. One can also study the pricing strategies for other queues with sojourn time-dependent reward.



---

*Source: 4684957-2019-03-12.xml*