1. INTRODUCTION
It often takes a long time to find a taxi at an airport, ferry terminal or railway station during peak hours. In some very touristy areas, this problem is worse given the increased numbers of passengers and visitors. As Anwar et al. (2013) noted, when too many taxis wait in a taxi queue, it reduces the number of taxis available to service the rest of the city and it also reduces the revenue of taxi drivers waiting in such queues because they forgo the opportunity to earn fares elsewhere. In contrast, when too few taxis are available, passengers are likely to endure long waits. As such, this type of matching issue between passengers and taxis has been an interesting and an important issue in the area of urban transport over the decades. How many taxis do we need at a taxi station so that waiting times are not too long? How much space should the taxi station have? How much should the taxi fare be to maximize social welfare? In this paper, we model this passengertaxi matching problem as a matching queueing system. Our purpose is to answer the above questions and provide passengers with equilibrium and optimal joining strategies in order to coordinate passengers and taxis while also improving the performance of the system in terms of social welfare.
A matching queue, also known as a doubleended queue, was initially proposed by Kendall (1951), who introduced the matching problem between passengers and taxis. On one side is a queue of taxis and on the other a queue of passengers. A short taxi queue may inconvenience passengers in some cases, but a long taxi queue clearly does while also wasting valuable and expensive space. Moreover, both short and long queues can never coexist. In everyday life, many arrangements in a variety of fields, including communication networks, production inventory systems, and service systems, can be modelled as matching queues. According to Kendall (1951), the size of the queue is caused by the difference between the arrivals of passengers and taxis. The authors also pointed out that the mean queue length approaches zero when the two arrival rates are identical and the variance of the queue length increases infinitely. Dobbie (1961) and Giveen (1963) extended this topic to a matching queue with nonhomogeneous Poisson arrivals of passengers and taxis. Jain (1962) discussed the matching problem under the assumption that the interarrival time of taxis is distributed as a general distribution and only a finite capacity of taxis is available. Kashyap (1966) investigated a matching queue while assuming that there is limited waiting space both for customers and taxis, with taxis serving the passengers in bulk. An early discussion with references is given in Srivastava and Kashyap (1982). More recently, the matching queue has been applied to assembly facilities producing multipart components. Parts arrive independently according to a renewal process, but the component can only be assembled when all of the parts are present. Papers that discuss these assemblylike matching queues include those by Som et al. (1994) and Takahashi et al. (2000). Conolly et al. (2002) studied the transient behavior of a doubleended queueing system with statedependent impatience, also known as reneging or abandonment. The taxi queue is shortened by either passenger arrival or taxi reneging events, and vice versa for a passenger queue. Based on the twodimensional Markov chain, the authors presented a momentgenerating function and firstpassage times. Wong et al. (2005) adopted an absorbing Markov chain to model the search process of taxi movements and proposed a useful formulation for describing taxi urban services in a network. Crescenzo et al. (2012) dealt with a matching queue with system failures and repairs, assigning transient and steadystate probability distributions for passenger and taxi queue lengths, respectively. Afèche et al. (2014) studied the matching queue with batch arrivals and abandonment. There are two types of customers, patient ones who queue but may later abandon, and impatient ones who depart immediately if their order is not filled. The authors first established the closedform results for the doublesided queueing model with batch arrivals and abandonment. More information on the matching queue and actual applications is available in several published studies (Perry and Stadje, 1999;Zenios, 1999;Yang et al., 2010;Yang and Yang, 2011;Wong et al., 2014;Gurvich and Ward, 2014) and the references therein.
Most of the above works focus on determining system performance measures such as queue lengths and waiting times. Although some discussed optimal control schemes, they did not consider strategic joining behaviors between passengers and taxi drivers. Because passengers and taxi drivers are both sensitive to delays, they typically decide whether or not to join a queue based on welldefined joining strategies. This can therefore be modeled as a game among arriving passengers and taxis, and the fundamental problem is to identify the Nash equilibrium. Naor (1969) was the first to show that tolls can be levied to encourage strategic customers to adopt socially optimal behavior that may not be optimal for them personally. Since then, a number of studies of strategic joining/balking behavior by customers in queueing systems have been conducted. The monograph of Hassin and Haviv (2003) summarize the main approaches and several results on various observable and unobservable queueing systems with extensive bibliographical references. Recently, equilibrium joining/balking strategies in matching queues have been the subject of growing attention. Li et al. (2016) considered a maketostock production system with setup costs and delaysensitive customers. They modeled the production system as a matching M/M/1 maketostock queue with a twocriticalnumber policy. Under this policy, production starts when N customer orders have accumulated and stops immediately when the inventory level reaches S. Li et al. (2016) derived the equilibrium customer purchasing strategies and system performance metrics. Those authors also obtained the optimal values of two control variables. Shi and Lian (2016a) analyzed the strategic joining behavior of passengers in both the observable and the unobservable cases. In the observable case, those authors provided the individual equilibrium and the socially optimal joining strategies of threshold type. On the other hand, in the unobservable case, they discussed those of probability type. Further, the optimal taxi buffer size which maximizes the overall social welfare was determined from the perspective of a government (or a social planner). Shi and Lian (2016b) extended their work to the equilibrium strategies and optimal control method in a matching queue where there is limited waiting space both for passengers and taxis. They considered a centralized system and a decentralized system. In the centralized system, the government sets thresholds for both passengers and taxis to maximize social welfare. On the other hand, in the decentralized system, passengers and taxis determine whether to join a queue or not based on their individual utility functions. More recently, Wang et al. (2017) analyzed the strategic behavior and social optimization in a doubleended queue with gated policy. In Wang et al. (2017)’s model, taxis are not allowed to enter if the number of taxis reaches an upper limit (no waiting passengers) and are allowed to enter again when the number of waiting taxis is reduced to a lower limit.
Motivated by the above excellent works, this paper explores equilibrium joining strategies and social welfare maximization in passengertaxi matching queues under a discretetime setting. For decades, the discretetime queue has received much attention due to its actual use in timeslotted digital communication systems and other synchronous systems (Lee, 2016), as the discretetime queue is more suitable than the continuoustime queue for modeling systems in which the basic operational units are bits, packets and cells. The practical interest in discretetime matching queues is not confined to taxis and passengers. The lack of radio spectrum resources has limited the sustainable development of wireless communication technologies and mobile application networks. The cognitive radio network (CRN) is the most promising candidate solution to address such spectrum shortages and inefficiencies. The main principle of a CRN is that the secondary user is intelligently aware of the environment and opportunistically occupies the ‘spectral hole’ of the privileged user. Comparing a CRN with a matching queue, the packet and the channel can be regarded as the passenger and the taxi, respectively. In a CRN, the buffer capacity of arriving packets and the number of available channels should be optimized so that spectrum allocation is realized dynamically and the overall operational profit (the energy consumption) is maximized (minimized). Due to its synchronized features, many studies have assumed discretetime geometric distributions for packet arrival, packet transmission, packet dropping, packet retrial, channel occupation and other packet processes. By doing so, the discretetime queue can describe coincidence events and provide the more precise performance measures of various communication systems, including CRNs (Jin et al., 2013;Jin et al., 2016;Jin and Sun, 2017;Zhao and Bai, 2017). To the best of our knowledge, no works thus far have analyzed strategic behaviors in a discretetime matching queue. In this paper, we extend the work of Shi and Lian (2016a) to a discretetime matching queue and depict the equilibrium joining/balking strategies of passengers as well as the optimal strategies which maximize social welfare.
The remainder of the paper proceeds as follows. In section 2, we describe the mathematical model and associated assumptions. In section 3, we derive the stationary distribution and the important performance measures. In section 4, we discuss equilibrium joining strategies used by individual and socially concerned passengers in observable and unobservable cases. We also determine the optimal buffer size from a governmental perspective. Section 5 describes the various numerical experiments conducted here and provides an insightful operational control strategy.
2. MATHEMATICAL MODEL AND ASSUMPTIONS
The queueing system examined under this study has the following features. Passengers arrive in groups according to a Bernoulli process with a probability of λ (0 < λ < 1). Meanwhile, taxis arrive sequentially according to a Bernoulli process with a probability of μ (0 < μ < 1). For the system to be stable, the inequality λ < μ should hold. In a discretetime queueing system, arrivals by a taxi and a passenger can occur at the same time at the boundary of the time axis, making it necessary to determine the order of their arrivals. If a taxi and a passenger arrive at the taxi station simultaneously, it is assumed that the taxi arrives instantaneously first. Each group of passengers consists of one to five persons who can be precisely taken to their destinations by a taxi. For convenience, we regard groups of passengers as a single passenger. The passengers and taxis are queued on a firstin firstout basis. The waiting space for taxis is finite. We define K (K ≥ 1) as the maximum number of taxis that can be accommodated at the taxi station. Because the space occupied by passengers is much smaller than a taxi, the waiting space for passengers is assumed to be infinite.
We assume that a passenger pays a taxi fare of p_{1} (p_{1} > 0) on average and receives a reward of R (R > 0) per unit time for taking a taxi. Moreover, taxis and passengers accrue waiting costs while they remain at the taxi station. Here, we define C_{1} (C_{1} > 0) and C_{2} (C_{2} > 0) as the passenger’s waiting cost per unit of time and the taxi’s waiting cost per unit of time, respectively. Each taxi spends an average of C_{f} (C_{f} > 0) on maintenance and fuel costs. Finally, to improve the quality of the taxi service and to reduce traffic congestion, the government can adjust the taxi arrival rate by imposing a tax or granting a subsidy to each taxi. We define p_{2} as the tax or subsidy affecting the taxi during each trip. p_{2} > 0 indicates a government grants subsidy to each taxi, while p_{2} < 0 denotes a government levy on each taxi.
3. QUEUEING ANALYSIS
Define $\leftN(t)\right$ as the number of the passengers or the taxis at the taxi station at time t, where N(t) > 0 indicates that the passengers are waiting for the taxis, N(t) < 0 denotes that the taxis are waiting for the passengers, and N(t) = 0 means that the taxi station is empty. Because the maximum number of taxis in the system is equal to K and the waiting space for passengers is assumed to be infinite, a stochastic process {N(t), t = 0, 1, 2, ⋯} becomes a onedimensional discretetime Markov chain with the state space expressed as Ω ={−K, −K + 1, ⋯, −1, 0, 1, ⋯} and its nonzero onestep transition probabilities are given by
where $\overline{\lambda}=1\lambda \hspace{0.33em}\text{and}\hspace{0.33em}\overline{\mu}=1\mu $. The corresponding transition diagram is shown in Figure 1.
Let π_{n} be the stationary probability of N(t), which means that ${\pi}_{n}={\mathrm{lim}}_{t\to \infty}\mathrm{Pr}\{N(t)=n\}$, with $n\ge K$. Then, the local balance equations governing the system are then given by
Solving these equations recursively, we have
where $\omega =\rho \overline{\mu}/\overline{\lambda}\hspace{0.33em}\text{and}\hspace{0.33em}\rho =\lambda /\mu $. From (3) and (4), we calculate the mean passenger queue length L_{1} and the mean passenger waiting time W_{1}:
From the BASTA property (Takagi, 1993), the blocking probability of an arriving taxi is ${\pi}_{K}$; thus, the effective arrival probability of a taxi μ_{eff} is given by ${\mu}_{eff}=\mu (1{\pi}_{K})=\lambda $. Therefore, we calculate the mean taxi queue length L_{2} and the mean taxi waiting time W_{2}:
4. OPTIMIZATION
In this section, we discuss passenger’s equilibrium joining strategies and find the optimal taxi buffer size to maximize overall social welfare. From (6) and (8), the (expected) utility functions of a passenger and a taxi are
4.1 Passenger Strategies
Upon arrival, every passenger decides whether to join the queue or balk. In the rest of paper, it is assumed that $R\ge {p}_{1}+{C}_{1}/\mu $, which ensures that the reward exceeds the total cost for an arriving passenger who finds the empty system. We denote Λ as the arrival rate of passengers
4.1.1 Observable Case4.1.1 Observable Case
In the observable case, an arriving passenger is informed about the passenger queue length; hence there exist the equilibrium joining strategy of threshold type. A pure threshold strategy is specified by n_{e}, and the joining/balking strategy has the form of ‘While arriving, observe the passenger queue length; join if the passenger queue length is smaller than or equal to n_{e} and balk otherwise.’ Based on the rewardcost structure, for an arriving passenger who decides to join the queue, his/her utility is expressed as ${U}_{1}^{ob}(n)=R{p}_{1}{C}_{1}T(n)$, where T(n) is the mean waiting time of the passenger who joins the queue, given that he/she encounters n passengers who are already existing. For T(n), it is clearly equal to the n+1 interarrival times of taxis; that is, $T(n)=(n+1)/\mu $. The passenger’s utility after taking a taxi in equilibrium then equals to 0; i.e., ${U}_{1}^{ob}(n)=R{p}_{1}{C}_{1}(n+1)/\mu =0$. Solving ${U}_{1}^{ob}(n)=0$ with respect to n, we obtain
where the symbol $\lfloor \rfloor $ is a floor function.
Next, we consider that the passengers are socially concerned individuals. Socially concerned passengers who care about society will set an optimal buffer (the socially optimal threshold) for themselves to maximize social welfare. In order to maximize social welfare, we derive a stationary queue length distribution, where we define n_{s} as the social joining strategy to be used. Therefore, the state space of the discretetime Markov chain $\{N(t),\text{}t=0,\text{}1,\text{}2,\text{}\cdots \}$ is ${\Omega}_{s}=\left\{K,\text{}K+1,\text{}\cdots ,\text{}1,\text{}0,\text{}1,\text{}\cdots ,\text{}{n}_{s}\right\}$. The related transition diagram is depicted in Figure 2
Define the stationary probability as ${\phi}_{n}={\mathrm{lim}}_{t\to \infty}\mathrm{Pr}\{N(t)=n\}$ for $n\in {\Omega}_{s}$. Then, the local balance equations governing the system are given by
where $\overline{\Lambda}=1\Lambda $. Solving (12) and (13) recursively using the conventional BirthDeath process (Ross, 1996), we have
where $\sigma =\Lambda /\mu $ and $\gamma =\sigma \overline{\mu}/\overline{\Lambda}$ . Let b_{p} be the blocking probability of an arriving passenger. According to our assumption with regard to the arrival order of passengers and taxis in section 2, we have ${b}_{p}=\overline{\mu}{\phi}_{{n}_{s}}$; thus, the effective arrival probability of a passenger α is given by
Let b_{t} be the blocking probability of an arriving taxi. According to the BASTA property, we have ${b}_{t}={\phi}_{K}$; thus, the effective arrival probability of a taxi β is given by
With (14) and (15), the mean queue lengths for a passenger and a taxi are respectively expressed as
It follows that the social welfare function is equal to
Define ${n}_{s}^{*}$ as the socially optimal threshold strategy which maximizes the social welfare:
where ${\mathbb{Z}}_{+}$ is the positive integer set. Hence, the optimization problem in (21) becomes a nonlinear integer programming (NLIP) problem. The maximum solution ${n}_{s}^{*}$ should satisfy the following inequalities:
or equivalently,
where $M=\Lambda \overline{\mu}{(1\gamma )}^{2}(R+{p}_{2}{C}_{f})+{C}_{2}\gamma [K\overline{\mu}{(1\gamma )}^{2}\gamma (1K+K\gamma {\gamma}^{K})]$. From (23), it is clear that, when $\Lambda =\mu \left(\text{or}\hspace{0.33em}\gamma =1\right)$, there is no socially optimal threshold. Define δ(n) as a function of n such that $\delta (n)=n(1\gamma )\sigma {\gamma}^{K}(1{\gamma}^{n})\hspace{0.33em}\forall n\in \left\{0\right\}\cup {\mathbb{Z}}_{+}$. Because
the function δ(n) is the increasing in n. If $\delta (0)\le M/{C}_{1}\gamma \le \delta (1),\hspace{0.33em}{n}_{s}=0$ but it is not optimal because ${n}_{s}\in {\mathbb{Z}}_{+}$. Therefore, if $M/{C}_{1}\gamma \ge \delta (1)$, there exist a unique ${n}_{s}^{*}$ which satisfies inequalities in (22) or (23). In addition, it is easy to show that, if $M/{C}_{1}\gamma \le \delta ({n}_{e}),$ then ${n}_{s}^{*}\le {n}_{e}$; otherwise, ${n}_{s}^{*}>{n}_{e}$. Finally, as ${n}_{s}\to \infty $, we have
Thus, we can set the upper bound of ${n}_{s}^{*}$ as follows:
where ε is a sufficiently small real number.
To solve (21), we introduce a simulated annealing (SA) algorithm. SA is a probabilistic search method that was introduced by Metropolis et al. (1953). Later, this method was successfully applied to solve optimization problems by Kirkpatrick et al. (1983). For more information about SA, readers may refer to Aarts and Korst (1997) and Cercignani (1998).
In Pseudocode 1, we present our SA algorithm for finding ${n}_{s}^{*}$ which maximizes the social welfare. From lines 1 to 5, we set the input parameters and generate the initial state within the search space ${\mathcal{S}}_{ob}={\mathbb{Z}}_{+}\cap [1,\text{}{n}_{s}^{\text{upper}}]$. The explanation of the input parameters and the states are given below.

T : temperature

κ : cooling coefficient

Itr : maximum number of iteration

s_{best} : best stat

s_{current} : current state

s_{new} : neighbor state
From lines 6 to 19, the SA algorithm execution procedure is described. In line 7, the cooling schedule is shown to be ${\left(1\kappa \right)}^{t}$, where t is an iterative index. In practice, the cooling coefficient κ usually falls within 0 < κ < 0.3. In this paper, κ is set to 0.01. After the random neighbor state is generated and its social welfare value is calculated in line 8, we update the current state and its social welfare value from line 9 to line 12 based on the Metropolis criterion. We also check if the current state is the best from lines 13 to 16. Finishing the loop lines 6 to 17, we finally obtain ${n}_{s}^{*}$ and $S{W}^{ob}({n}_{s}^{*})$. When we assume that $R=100,\hspace{0.33em}{p}_{1}={p}_{2}=10,\hspace{0.33em}{C}_{1}={C}_{2}=5,{C}_{f}=30,$ $\Lambda =0.5,\hspace{0.33em}\mu =0.55,\hspace{0.33em}\text{and}\hspace{0.33em}K=10$, we obtain the socially optimal threshold strategy ${n}_{s}^{*}=6$ with the individual equilibrium threshold strategy n_{e} = 8. We observe that ${n}_{s}^{*}\ne {n}_{e}$, which indicates that the individual threshold strategy does not always match the socially optimal threshold strategy.
4.1.2 Unobservable Case
In the unobservable case, an arriving passenger does not have any information about the passenger queue length when they decide to join or balk. The optimal decision of an arriving passenger must consider the strategies of the other passengers. Because all passengers are assumed to be indistinguishable, we consider the situation as a symmetric game among them. In the present model, there are only two pure strategies: to join or to balk. The strategy is specified by the joining probability of an arriving passenger. In the unobservable case, our goal is to identify the Nash equilibrium joining strategy of the probability type.
Suppose that all passengers follow a joining strategy Λ_{1}. Then, the system behaves as the original, but with arrival probability is Λ_{1} instead of λ. For the system to be stable, we assume that ${\Lambda}_{1}<\mu $. The corresponding transition diagram is given in Figure 3.
We consider individual passengers. From (6), the mean passenger waiting time is expressed as
where ${\omega}_{1}={\rho}_{1}\overline{\mu}/{\overline{\Lambda}}_{1}\hspace{0.33em}\text{and}\hspace{0.33em}{\rho}_{1}={\Lambda}_{1}/\mu .$ Based on the rewardcost structure, for an arriving passenger who decides to join the queue, his/her utility is
According to (28), ${U}_{1}^{un}({\Lambda}_{1})$ depends on Λ_{1}. We can determine the Nash equilibrium strategy of an arriving passenger Λ_{e}. To do this, we establish the three cases below.

Case 1:$R\le {p}_{1}+{C}_{1}{W}_{1}(0)$. In this case, even if no other passengers join, the utility of a passenger who joins the queue is nonpositive. Therefore, the joining strategy with probability Λ_{e} = 0 is an equilibrium strategy, and no other equilibrium is possible. Moreover, in this case, not joining is the dominant strategy.

Case 2:$R\ge {p}_{1}+{C}_{1}{W}_{1}({\Lambda}_{1})$. In this case, even if all potential passengers join, they all enjoy a nonnegative benefit. Therefore, the strategy of joining with probability ${\Lambda}_{e}={\Lambda}_{1}$ is an equilibrium strategy, and no other equilibrium is possible. Moreover, in this case, joining is the dominant strategy.

Case 3:${p}_{1}+{C}_{1}{W}_{1}(0)<R<{p}_{1}+{C}_{1}{W}_{1}({\Lambda}_{1})$. In this case, if ${\Lambda}_{e}={\Lambda}_{1}$, then a passenger who joins suffers a negative benefit. Hence, this cannot be an equilibrium strategy. Likewise, if Λ_{e} = 0, a customer who joins obtains a positive benefit, more than by balking. Hence, this cannot be an equilibrium strategy. Therefore, there exists unique equilibrium joining probability Λ_{e} satisfying ${\Lambda}_{e}=\left\{{\Lambda}_{1}\rightR{p}_{1}{C}_{1}{W}_{1}({\Lambda}_{1})=0,\text{}0{\Lambda}_{1}\mu \},$ for which customers are indifferent with regard to whether they join or balk.
Next, we consider the case in which passengers are socially concerned. From (9) and (10), the social welfare function can be given by
Where ${\mu}_{eff}=\mu (1{\pi}_{K})={\Lambda}_{1}$ according to the BASTA property. Define ${\Lambda}_{1}^{*}$ as the socially optimal joining strategy which maximizes the social welfare:
Therefore, equation (30) becomes a nonlinear programming problem. The objective function in (30) is differentiable with respect to Λ_{1}. Its secondorder derivative is
Investigating equation (31), it is possible that ${\partial}^{2}S{W}^{un}({\Lambda}_{1})/\partial {\Lambda}_{1}^{2}<0\hspace{0.33em}\text{or}\hspace{0.33em}{\partial}^{2}S{W}^{un}({\Lambda}_{1})/\partial {\Lambda}_{1}^{2}>0$ or depending on the value of ${\omega}_{1}^{K}({C}_{1}+{C}_{2}){C}_{2}.$ For example, when $R=1000,\hspace{0.33em}{p}_{2}=10,\hspace{0.33em}{C}_{1}=1,\hspace{0.33em}{C}_{2}=50,\hspace{0.33em}{C}_{f}=10,\hspace{0.33em}\mu =0.5,$ and $K=10,\hspace{0.33em}{\left.{\partial}^{2}S{W}^{un}({\Lambda}_{1})/\partial {\Lambda}_{1}^{2}\right}_{{\Lambda}_{1}=0.4}=19030>0$ and ${\partial}^{2}S{W}^{un}\hspace{0.33em}({\Lambda}_{1}){\left./\partial {\Lambda}_{1}^{2}\right}_{{\Lambda}_{1}=0.49}=299812<0$. Therefore, we cannot determine the convexity/concavity of $S{W}^{un}({\Lambda}_{1})$. To solve (30), we also use the SA algorithm. The SA algorithm to maximize $S{W}^{un}({\Lambda}_{1})$ is described in Pseudocode 2; it is fairly similar to Pseudocode 1 apart from several lines. Hence, we omit the details of Pseudocode 2 here. When we assume that $R=100,\hspace{0.33em}{p}_{1}={p}_{2}=10,\hspace{0.33em}{C}_{1}={C}_{2}=5,\hspace{0.33em}{C}_{f}=30,\hspace{0.33em}\mu =0.55,$ and $K=10,$ we obtain the socially optimal joining strategy of ${\Lambda}_{1}^{*}=0.5118,$ with the individual equilibrium joining strategy of ${\Lambda}_{e}=\mathrm{0.5356.}$ We observe that ${\Lambda}_{1}^{*}\ne {\Lambda}_{e}$, which indicates that the individual joining strategy is not always consistent with the socially optimal joining strategy.
4.2 Government Strategies
We will study the problem of finding an optimal taxi buffer size to maximize the social welfare and guarantee nonnegative passenger/taxi utility. Following (9) and (10), the social welfare function is as follows:
At this point, we can establish the following NLIP problem to maximize the social welfare with respect to K:
In equation (33), we want to maximize the government’s social welfare. The first and second constraints guarantee the nonnegative passenger and taxi utility outcomes, respectively.
Next, we address the feasibility of (33). It is easy to show that U_{1}(K) means an increase in because $0<\omega <\rho <1$ and
Thus, if we assume that ${U}_{1}(1)\ge 0,$ the first constraint in (33) is always satisfied. Simplifying ${U}_{2}(K+1){U}_{2}(K)$, we have
Therefore, U_{1}(K) is a decreasing function of K and there exists an upper bound K^{upper} which satisfies the following inequality:
Assuming that ${U}_{2}(1)\ge 0$, the second constraint in (33) is always satisfied within the interval of $[1,\text{}{K}^{\text{upper}}]$. Summarizing the above analysis, the inequalities $[1,\text{}{K}^{\text{upper}}]\hspace{0.33em}\text{and}\hspace{0.33em}{U}_{2}(1)\ge 0$ should hold for the NLIP problem in (33) to be feasible, and we can rewrite (33) as
where K^{*} is the socially optimal buffer size which maximizes the social welfare and S_{g} is the search space ${\mathbb{Z}}_{+}\cap [1,\text{}{K}^{\text{upper}}]$. To solve (37), we suggest the SA algorithm in Pseudocode 3. Because it is similar to Pseudocodes 1 and 2, we also omit the details of Pseudocode 3 here for brevity. Setting $R=150,\hspace{0.33em}{p}_{1}=30,\hspace{0.33em}{p}_{2}=10,\hspace{0.33em}{C}_{1}={C}_{2}=5,\hspace{0.33em}{C}_{f}=5,\hspace{0.33em}{C}_{f}=10,\hspace{0.33em}\lambda =0.6,$ and $\mu =0.62$, we obtain the socially optimal buffer size K^{*} = 8. Additionally, the passenger and taxi utility values are ${U}_{1}(8)=68.97\hspace{0.33em}\text{and}\hspace{0.33em}{U}_{2}(8)=12.30$, which are both nonnegative numbers.
5. NUMERICAL EXAMPLES
In this section, we present several numerical examples with which to explore the equilibrium and the optimal behavior of passengers in the observable and the unobservable cases and the optimal taxi buffer size from a governmental perspective.

Example 1. This example deals with the equilibrium joining strategy of an individual passenger and the optimal joining strategy of a socially concerned passenger in the observable case. Initially, we conduct a sensitivity analysis of the taxi arrival probability μ while assuming that $R=100,\hspace{0.33em}{p}_{1}={p}_{2}=10,\hspace{0.33em}{C}_{1}={C}_{2}=5,\hspace{0.33em}{C}_{f}=30,\hspace{0.33em}\Lambda =0.5,$ and $K=10$. Varying the value of μ from 0.4 to 0.6, we determine the equilibrium joining strategy n_{e} and the optimal joining strategy ${n}_{s}^{*}$, as shown in Figure 4. We observe that both n_{e} and ${n}_{s}^{*}$ increase monotonically as μ increases. Therefore, as taxis arrive more frequently, it is desirable to raise the passenger joining threshold in terms of both the individual utility of passengers and the overall welfare of society. We also find that ${n}_{s}^{*}\le {n}_{e}$ because the inequality $M/{C}_{1}\gamma <\delta ({n}_{e})$ holds within the interval $\mu \in [0.4,\text{}0.5)\cup (0.5,\text{}0.65]$.
Next, we consider the passenger arrival probability Λ. Here, we assume that R = 100, p_{1} = p_{2} = 10, C_{1} = C_{2} = 5, C_{f} = 30, μ = 0.5, and K = 10. Varying the value of from 0.4 to 0.6, we determine ${n}_{e}$ and ${n}_{s}^{*}$ , as presented in Figure 5. According to equation (11), is not a function of ; thus, ${n}_{e}$ is always equal to $\lfloor 0.5\times (10010)/5\rfloor 1=8$ . On the other hand, ${n}_{s}^{*}$ decreases monotonically as increases, which implies that as passengers arrive more frequently, the passenger joining threshold should decrease to maximize social welfare overall.

Example 2. In this example, we investigate the equilibrium joining strategy of individual passengers and the optimal joining strategy of socially concerned passengers in the unobservable case. Initially, we conduct a sensitivity analysis of the taxi arrival probability $\mu $ , where we assume that $R=300,$ ${p}_{1}={p}_{2}=10,$ ${C}_{1}={C}_{2}=5,$ ${C}_{f}=30,$ and $K=5.$ Varying the value of from 0.1 to 0.9, we determine the equilibrium joining strategy ${\Lambda}_{e}$ and the optimal joining strategy ${\Lambda}_{1}^{*}$ , as indicated in Figure 6. We find that both Λ_{e} and ${\Lambda}_{1}^{*}$ increase as μ increases. Therefore, it is advantageous for passengers to arrive at the taxi station frequently in order to increase the overall social welfare as well as the utility of individual passengers when a taxi arrives frequently at the taxi station. We also find that ${\Lambda}_{1}^{*}<{\Lambda}_{e}$, which means that the socially optimal joining probability is lower than the individual equilibrium joining probability. Finally, we note that ${\Lambda}_{1}^{*}<\mu \hspace{0.33em}\text{and}\hspace{0.33em}{\Lambda}_{e}<\mu $ because the system should remain stable.
Next, we examine the effect of the taxi buffer size K on the passenger joining probabilities. We set $R=300,\hspace{0.33em}{p}_{1}={p}_{2}=10,\hspace{0.33em}{C}_{1}={C}_{2}=5,\hspace{0.33em}{C}_{f}=30,\hspace{0.33em}\text{and}\hspace{0.33em}\mu =0.5$ Varying the value of Λ from 0.4 to 0.6, we define the values of Λ_{e} and ${\Lambda}_{1}^{*}$, as indicated in Figure 7. This outcome shows that both Λ_{e} and ${\Lambda}_{1}^{*}$ increase as K increases. If the taxi station can accommodate more taxis, more passengers will join the queue to use the taxi service, which benefits not only passengers but also social welfare overall. Figure 7 also confirms that ${\Lambda}_{1}^{*}<{\Lambda}_{e}$, but as the taxi buffer size increases, ${\Lambda}_{1}^{*}$ gradually approaches Λ_{e}.

Example 3. In this example, we analyze the relationship between the optimal taxi buffer size the passenger/ taxi arrival probabilities. Here, we assume that $R=100,{p}_{1}=30,{p}_{2}=10,{C}_{1}={C}_{2}=5,{C}_{f}=10,\hspace{0.33em}\text{and}\hspace{0.33em}\lambda =0.48$. Varying the value of μ from 0.5 to 0.8, we obtain the optimal taxi buffer size K^{*} and the maximum social welfare passenger $S{W}^{g}({K}^{*})$ , as presented in Figure 8. When μ increases, K^{*} decreases but $S{W}^{g}({K}^{*})$ increases. This phenomenon can be explained as follows. As taxis arrive frequently, there are many taxis available at the taxi station; hence, the government does not need to reserve a large number of waiting spaces for taxis. This causes the overall social welfare to increase because the mean taxi waiting time decreases. In addition, when taxis arrive frequently, the mean passenger waiting time is reduced, which has a positive effect on social welfare.
Next, we consider the impact of the passenger arrival on the taxi buffer size, where we set R = 100, p_{1} = 30, p_{2} = 10, C_{1} = C_{2} = 5, C_{f} = 10, and μ = 0.81. Varying the value of λ from 0.65 to 0.8, we determine the values of K^{*} and $S{W}^{g}({K}^{*}),$ as shown in Figure 9. As expected, K^{*} increases when λ increases because, as passengers arrive more frequently, more of a taxi buffer must be provided at the taxi station to reduce passenger waiting times. It is interesting to note that $S{W}^{g}({K}^{*})$ initially increase and then sharply decreases after reaching its peak value. When λ = 0.7375, $S{W}^{g}({K}^{*})$ reaches its highest value of 65.5042. This can be explained as follows. As passengers arrive frequently, the taxi buffer size should increase, which leads to an increase in the mean taxi waiting time. Therefore, for a large taxi buffer size, social welfare decreases.
6. CONCLUSION
In this work, we studied equilibrium joining strategies and the social welfare maximization problem in the discretetime passengertaxi matching queues. We analyzed passenger strategic joining behaviors in observable and unobservable cases. In the observable case, we provided an equilibrium thresholdtype joining strategy for individual passengers and the optimal joining strategy for socially concerned passengers. On the other hand, in the unobservable case, the probability type of strategy was determined and presented. From a governmental perspective, we established the optimal taxi buffer size which maximizes the overall social welfare while also guaranteeing nonnegative passenger/taxi utility values. For all social welfare maximization problems, as the taxi fare p_{1} represents the transfer between passengers and taxi drivers, the objective function does not contain the terms of p_{1}. We also conducted various numerical experiments to offer an insightful operational control strategy.
This paper analyzes passenger equilibrium and optimality issues. There are various avenues for future research. One can conceive of the strategic and optimal joining behaviors of taxis in both observable and unobservable cases. Given that taxi drivers are also an important aspect of this system, studying this topic would be a worthy endeavor. Another interesting extension would be to extend our model to the system failurerepair mechanism and to statedependent passenger/taxi arrivals.
An unrealistic assumption made in this study is the instantaneous service time. In reality, the loading time of the passenger to the taxi cannot be equal to zero. Therefore, the twodimensional Markov chain considering two passenger’s states; i) waiting state in the queue and ii) loading state to a taxi, has to be analyzed and, as the result, much more complex formulas for the stationary queue length distributions and the performance measures will be derived, which also remains the future study.