1.INTRODUCTION
Thanks to recent advances in computer and telecommunication technology, the importance of the discrete time queueing system has been increased. This is because the conventional continuoustime queueing system cannot accurately give the performance measures of computer and telecommunication systems where basic operational units are bits, packets and cells, although they have been used in the past to approximately evaluate some performance measures of these systems. Hence, the discretetime queueing system is potentially more suitable for application to the digital computer and communication networks. For detailed information on the discretetime queueing system, readers may refer to Meisling (1958), Hunter (1983), Bruneel and Kim (1993), and Takagi (1993).
Recently, Ma and Liu (2015) studied the discretetime Geo/Geo/1 queue from an economic point of view. Ma and Liu (2015) analyzed the equilibrium strategies under two types of pricing structures. In the first structure, the server charges a fee that is proportional to the sojourn time (waiting time plus service time), called expost payment (EPP) scheme. In the second structure, however, the server charges a fixed fee for the service, which means the server implements an exante payment (EAP) scheme. Under these two pricing schemes, Ma and Liu (2015) analyzed customer’s equilibrium joining behaviors and server’s expected profit maximization strategies. By the way, in Section 2 of their work, the expected sojourn time of the discretetime Geo/Geo/1 queue was presented as 1/ (μ − pq) , where μ is server’s service rate and pq is customers’ effective arrival rate, but this is not correct. Actually, 1/ (μ − pq) is the expected sojourn time of the continuoustime M/M/1 queueing system. It is thought that Ma and Liu (2015) analyzed pricing models of not the discretetime Geo/Geo/1 queue but the continuoustime M/M/1 queue. The purpose of this work is to correct the work of Ma and Liu (2015) and to present the exact pricing strategies in the discretetime Geo/Geo/1 queue.
The paper structured as follows. In section 2, we first derive the exact expected sojourn time in the discretetime Geo/Geo1 queue. In section 3 and 4, we analyze customer’s equilibrium joining behaviors and server’s profit maximization strategies under EPP and EAP schemes, respectively. Section 5 deals with numerical experiments where we investigate trends of the optimal prices of EPP and EAP schemes according to various input values.
2.PRELIMINARIES
This study considers a queueing system with following features. We adopt a late arrival systemdelayed access (LASDA) (Takagi, 1993). Let the time axis be marked by t = 0, 1, 2, ⋯. According to the LASDA model, a customer arrival occurs during the interval (t^{−}, t) and a service completion occurs during the interval (t, t^{+}) , where t^{−} and t^{+} represent ${\text{lim}}_{\Delta t\to 0}\left(t\left\Delta t\right\right)$ and ${\text{lim}}_{\Delta t\to 0}\left(t+\left\Delta t\right\right)$ respectively. The arrival process of potential customers is the Bernoulli process with a rate of p (0 < p < 1). Whenever each potential customer arrives at the system, they decide whether to join or balk the system depending on the specific joining probability, denoted by q (0 < q ≤ 1). It is well known that the decomposition property holds in the Bernoulli process; therefore, the effective arrival process follows the Bernoulli process with a rate of pq. Service times are independent and identically distributed random variables (RVs) following the geometric distribution with a parameter μ ( 0 < μ < 1). For analytical simplicity, we assume followings: i) All RVs defined above are mutually independent; ii) Services are provided on a firstinfirstout basis; iii) The decision whether to join or balk the system is irrevocable, which means that customers are not allowed to neither abandon services nor retry to join the system; iv) The stable system should satisfy pq < μ.
The queueing system under our study is represented by a discretetime Markov chain. Let N(t^{+} ) be the number of customers in the system at t^{+} . Then, {N(t^{+} ), t = 0, 1, ⋯} becomes the discretetime Markov chain with the state space expressed as Ω = {n : n ≥ 0}. Let π_{n} be the stationary queue length distribution: ${\pi}_{n}{\text{=lim}}_{\Delta t\to 0}\text{Pr}\left\{N\left({t}^{+}\right)=n\right\},\text{\hspace{0.17em}}n\text{\hspace{0.17em}}\ge 0$. Then, we now have the following the local balance equations of our Markov chain (see Figure 1):
where δ_{i, j} is the Kronecker delta. From the normalizing condition ${\sum}_{n=0}^{\infty}{\pi}_{n}=1$, we can solve (1) and the queue length distribution has the form of(2)
Let L and ω respectively denote the expected queue length and the expected sojourn time. L is then given by $L={\displaystyle {\sum}_{n=1}^{\infty}n{\pi}_{n}=pq\left(1pq\right)/\left(\mu pq\right)}$. By Little’s formula, ω = (1− pq) / (μ − pq) . Due to the fact that μ < 1 , we have ω > 1 .
After the completion of a service, a customer receives a reward R (R > 0). This may reflect his/her satisfaction or the added value of being served. In addition, there exists a waiting cost C (C > 0) per unit time when the customer stays in the system. To make the model nontrivial, we assume that Rμ > C, which ensures that the reward exceeds the cost for an arriving customer finding the empty system.
3.EPP SCHEME
We first investigate the EPP scheme, where the sever charges a price that is proportional to customer’s sojourn time. Let K_{t} (K_{t} ≥ 0) and P_{t} denote the price charged by the server and the expected server profit per unit time, respectively. Then, the expected utility U_{t} has the following relation: U_{t} = R−K_{t}ω − Cω. If U_{t} equals zero at customer’s equilibrium, we have R = (K_{t} + C)(1pq)/(μ − pq). Therefore, customer’s joining probability is equal to
Substituting (3) into P_{t} = pqK_{t}ω, we have(4)
Now we verify the following facts: ${\text{lim}}_{{K}_{t}\to {\left(RC\right)}^{}}{P}_{t}=\infty $ and ${\text{lim}}_{{K}_{t}\to {\left(RC\right)}^{+}}{P}_{t}=\infty $. Therefore, P_{t} is not a continuous function and it is impossible to differentiate P_{t} when K_{t} = R − C. Unlike Ma and Liu (2015), we establish the following nonlinear programming (NLP) problem to maximize P_{t} with respect to K_{t}:
In (5), we want to maximize the expected server profit per unit time. The first constraint shows that the joining probability should be bounded between 0 and 1, and the second one guarantees the system to be stable. Actually, pq < μ in (5) can be simplified to ; K_{t} > −C therefore, we can neglect the second constraint due to the fact that K_{t} ≥ 0. Using (3), we rewrite (5) as

Lemma 1: The optimization problem in (6) is a convex maximization problem (CMP).
The proof of Lemma 1 is given in Appendix A. Since the optimization problem in (6) is a CMP, Lagrange multiplier method can be used to find the optimal solution. Observing (6), we can find that all constraints are inequality constraints. Thus, KarushKuhnTucker (KKT) conditions can be used to generalize the method of Lagrange multiplier. The Lagrange function can be formulated as
where λ_{1} and λ_{2} are Lagrange multipliers. According to KKT conditions, the optimal solution ${K}_{t}^{*}$ exists the following conditions can be satisfied simultaneously.
By solving the above equations group, we obtain the optimal price under the EPP scheme as follows:
If q > 1 , the preferred joining probability pq cannot be reached since p poses an effective limitation. In this case, the server may increase its price without having impact on pq, up to the point where R = K_{f} + C(1p)/(μ − p)) . Therefore, the optimal price and its maximum profit for the server in this case are ${K}_{t}^{\ast}=R\left(\mu p\right)/\left(1p\right)C$ and ${P}_{t}=pR\left(1p\right)/\left(1p\right)C)$ , respectively. Based on the above analysis, we could give the following theorem.

Theorem 1: In the EPP scheme, denoting ${q}_{t}=\left(R\mu {K}_{t}^{*}C\right)/\left(p\left(R{K}_{t}^{*}C\right)\right)$, one has the following:

(1) if q_{t} ≤ 1, there exists a unique equilibrium where customers join the queue with probability pq_{t}, and${K}_{t}^{*}$is given in (7) and${P}_{t}={K}_{t}^{*}R(R\mu {K}_{t}^{*}C)/((R{K}_{t}^{*}C)\text{\hspace{0.17em}}({K}_{t}^{*}+C))$ ;

(2) if q_{t} > 1, there exists a unique equilibrium where customers join the queue with probability p, and${K}_{t}^{*}=R\left(\mu p\right)/\left(1p\right)C$ and ${P}_{t}=pR\left(1p\right)/\left(\left(1p\right)C\right)$.
4.EAP SCHEME
Next, we consider the EAP scheme model, where the server charges a flat price for services. Define K_{f} as the fixed price charged by the server and P_{f} as the server expected profit per unit time. Since the expected utility for a customer is expressed as U_{f} = R  K_{f}  Cω and it equals zero an customers’ equilibrium, we obtain R = K_{f} + C(1pq)/(μ − pq). Hence, customer’s joining probability is equal to
Substituting (8) into P_{f} = pqK_{f}, we have
P_{f} in (9) is neither continuous nor differentiable when K_{f} = R − C due to the fact that ${\text{lim}}_{{K}_{f}\to {\left(RC\right)}^{}}{P}_{f}=\infty $ and ${\text{lim}}_{{K}_{f}\to {\left(RC\right)}^{+}}{P}_{f}=\infty $. Similar to the EPP scheme model, we establish the following NLP problem to maximize P_{f} with respect to K_{f}:
In (10), we also want to maximize the expected server profit per unit time. The first constraint shows that the joining probability should be bounded between 0 and 1, and the second one guarantees the system to be stable. Actually, pq < μ in (10) can be simplified to μ < 1 ; therefore, we neglect the second constraint by the model assumption in Section 2. Using (8), we rewrite (10) as

Lemma 2: The optimization problem in (11) is a CMP.
The proof of Lemma 2 is given in Appendix B. Since the optimization problem in (11) is a CMP, Lagrange multiplier method can be used to find the optimal solution. Observing (11), we can find that all constraints are inequality constraints. Thus, KKT conditions can be used to generalize the method of Lagrange multiplier. The Lagrange function can be formulated as
where γ_{1} and γ_{2} are Lagrange multipliers. According to KKT conditions, the optimal solution ${K}_{f}^{*}$ exists the following conditions can be satisfied simultaneously.
By solving the above equations group, we obtain the optimal price under the EAP scheme as follows:
If q >1 , the preferred joining probability pq cannot be reached since p poses an effective limitation. In this case, the server may increase its price without having impact on pq , up to the point where $R={K}_{f}+C\left(1p\right)/\left(\mu p\right)$. Therefore, the optimal price and its maximum profit for the server in this case are ${K}_{f}^{*}=RC\left(1p\right)/\left(\mu p\right)$ and P_{f} = p(R  C(1p) / (μp) respectively. Based on the above analysis, we could give the following theorem.

Theorem 2: In the EAP scheme, denoting${q}_{f}=\left(R\mu {K}_{f}^{*}\mu C\right)/\left(p\left(R{K}_{f}^{*}C\right)\right)$, one has the following:

(1) if q_{f} ≤ 1, there exists a unique equilibrium where customers join the queue with probability pq_{f}, and ${K}_{f}^{*}$is given in (12) and${P}_{f}={K}_{f}^{*}\left(R\mu {K}_{f}^{*}\mu C\right)/\left(R{K}_{f}^{*}C\right)$;

(2) if q_{f} > 1, there exists a unique equilibrium where customers join the queue with probability p, and${K}_{f}^{*}=RC\left(1p\right)/\left(\mu p\right)$and${P}_{f}=p\left(RC\left(1p\right)/\left(\mu p\right)\right)$.

5.NUMERICAL ANALYSIS
It is interesting to note that the two different pricing models (EPP and EAP) do not affect customer’s equilibrium joining probability and the server’s maximum profits. Although ${K}_{t}^{*}\ne {K}_{f}^{*}$, after some calculations, we can show that q_{t} = q_{f} and P_{t} = P_{f} if q_{t} = q_{f} < 1. In other words, customer’s equilibrium joining strategies and the expected server profits are identical in the two different pricing models in case of not only the continuoustime M/M/1 queue (see Proposition 3 in Ma and Liu, 2015) and but also the discretetime Geo/Geo/1 queue.
Based on our results, we present some numerical analyses. Figure 2 records the optimal price, the optimal joining probability, the maximum server profit of the EPP scheme and those of the EAP scheme according to the service rate. From Figure 2(a), we observe that EAP scheme generally sets a higher price than EPP scheme. Since P_{t} = P_{f} and EAP charges a flat price for a service, ${K}_{f}^{*}$ should be relatively higher than ${K}_{t}^{*}$. We also observe that ${K}_{f}^{*}\left({K}_{t}^{*}\right)$ sharply increases when the service rate μ is low (high). This means that, in EAP (EPP) scheme, the server can maximize its profit by a small increase in the service rate when μ is low (high). Finally, as μ goes to C / R or 1, ${K}_{t}^{*}$ and ${K}_{f}^{*}$ tend to have the same value. From Figure 2(b), we observe that as μ increases, the optimal joining probability q_{t}(=q_{f}) first increases and then stays stable at the top point of 1. This means that, within a certain range, more customers join the system with a faster service. Accordingly, the maximum server profit P_{t}(=P_{f}) increases as the joining probability and the price increases. We also observe that the increasing rate of P_{t}(=P_{f} becomes lower after q_{t}(=q_{f}) reaches 1.
Figure 3 records the optimal price, the optimal joining probability, the maximum server profit of the EPP scheme and those of the EAP scheme according to the reward. Figure 3(a) shows that both ${K}_{f}^{*}$ and ${K}_{t}^{*}$ are increasing functions of the reward R. As R increases, customer’s utilities U_{t} and U_{f} also increase in both EPP and EAP schemes. Hence, in order to maintain customer’s equilibrium, both ${K}_{f}^{*}$ and ${K}_{t}^{*}$ should increase when R increases. We also see that ${K}_{f}^{*}$ is generally higher than ${K}_{t}^{*}$. At customer’s equilibrium, both U_{t} and U_{f} are equal to zero; therefore, ${K}_{f}^{*}={K}_{t}^{*}\omega $. In other words, EAP should set a higher price than EPP at the same values of R. From Figure 3(b), we observe that as R increases, q_{t}(=q_{f}) first increases and then stays stable at the top point of 1. This also means that more customers join the system with a higher reward. Accordingly, P_{t}(=P_{f}) increases as the joining probability and the price increases.
6.CONCLUSIONS
This study investigated customer’s equilibrium joining behaviors and server’s optimal pricing strategies in the Geo/Geo/1 queue. We first introduced the two different pricing models, namely EPP and EAP. Under the EPP scheme, the server charges a price that is proportional to customer’s sojourn time. Meanwhile, under the EAP scheme, the server charges a flat price for services. We established the convex maximization problem and decided the optimal price that maximizes the server’s expected profits for each pricing model. We also found that customer’s equilibrium joining strategies and server’s maximum profits under two different pricing schemes are the same.
This work could provide queue managers with useful information for making the pricing decisions and instruct customers to take optimal strategies. Future studies include the extension of this work to other queueing systems considering multipleserver system, vacation policy and server failure phenomena.