A Closed Queueing Network with Strategic Service Differentiation

Abstract

We consider a service system with a single server, exponentially distributed service time, and two types of service rates – high and low. A customer chooses to obtain a high rate or a low rate service, and then the customer is active for an exponentially distributed period of time with a given high or low rate, respectively, and returns to the queue to be served again. Customers strategically choose a service type in order to maximize their long-run activity time.

We investigate which strategies of the customers are socially optimal and explore conditions for Nash equilibria. We examine symmetric and asymmetric strategies, as well as behavioral strategies. We focus on the game with two customers.

We prove an equivalence of the conditions for the existence of pure and mixed equilibria to those in the behavioral model, though the value of the mixed equilibrium strategy differs from the value of the behavioral equilibrium strategy for the same parameters. We show that a pure asymmetric equilibrium does not exist, a pure asymmetric strategy cannot be socially optimal, and a pure symmetric equilibrium always exists.

This research was supported by the Israel Science Foundation (Grant No. 355/15).

1 Introduction

We consider a system with a single server and N customers. The server supplies two service types - short or long. A served customer is active for a shorter or a longer period corresponding to the type of service he obtained, and when the activity period ends, returns to the queue to be served again. Consider, for example, a closed system of batteries with one charger. A battery can get a long or a short charging time, and will perform accordingly for a longer or a shorter time before recharging.

The motivation for our model is an application server shared by computer processes, described by Courcoubetis and Varaiya [3] and by Cheng and Kohler [1]. Gallay and Hongler [4] consider a variation with electric vehicles with various charging facilities. The same model is described by Xu, Dai, Sykara and Lewis, [8] for a multi-robot control operator in a disaster area. The referred articles search for system optimization while we assume strategic customers and analyse equilibrium strategies.

We focus on the case with two customers and investigate equilibria and optimal solutions for maximum probability to be active. The main technical difficulty in the analysis is that in the closed queueing system there is a dependence between successive service and waiting times.

Our main results: The socially optimal strategy is the pure symmetric strategy with the smaller utilization factor (Theorem 1). When the low-rate service has the smaller utilization factor (activity rate/service rate), choosing the low-rate service is optimal and the unique equilibrium (Theorem 5). We conjecture that there always exists a pure symmetric equilibrium strategy (Conjecture 16). We show that a pure asymmetric strategy cannot be an equilibrium (Corollary 17). We prove that a set of parameters ($\rho _l,\rho _h,\lambda _l,\lambda _h$) induces the same number and types of equilibria in the mixed-strategy model and in the behavioral-strategy model. We supply examples of the different cases.

Courcoubetis and Varaiya [3] describe two customers (processes) served by a single resource. The queueing network is similar to our model, but in their model the ratio between service time and activity time is fixed and they look for maximal utilization of the server.

Cheng and Kohler [1] deal with programs as customers too. They describe web-enabled application services. The customers are programs. A program sends a transaction to be processed by an ASP - Application Service Provider. Process time of a transaction is an exponential random variable, and so is the period of time between transactions. The paper compares the purchase of software for use in-house, with using the ASP’s services, and analyzes the ASP’s pricing scheme. This is a variation of the machine interference model described in [5]. Xu, Dai, Sykara and Lewis [8] describe a multi-robot control operator. There are N robots operated by a single server. The operator interacts with the robot for a period of time (IT - Interaction Time) raising its performance above an upper threshold, after which the robot is neglected for a period of time (NT - Neglect Time) until its performance deteriorates below a lower threshold, when the operator must again interact with the server. Both IT and NT are exponential random variables. In their paper the operator is free to choose between high quality or low quality interaction, or a mixed strategy, i.e. provide high quality interaction with a certain probability. They look for the probability p that maximizes the value of the utility function per cycle, whereas in our paper we look for the maximal utility per unit time.

Chu, Wan and Zhan [2] consider a ride-hailing platform where idle taxi drivers accept or ignore a rider’s request depending on profitability considerations. There are two types of riders with a different profitability (price) but the same service rate. If instead of discriminating between riders by price, the more profitable rider would have a higher service rate, and the utility function would be the proportion of time the taxi is busy, the model will be similar to ours.

Strategic queueing is introduced and surveyed by Hassin and Haviv [7] and Hassin [6]. Hassin [6] §4.7 and §6.3.2 survey the literature on expert systems with duration-dependent service value. In our model customers return to service and are interested in maximizing their long-run utility. Customers act strategically choosing their service rate.

Section 2 formally defines the model and summarises our results. Section 3 analyses the model when each customer sticks to the same service type repeatedly, and Sect. 4 analyses the model when each customer draws a service type with the same probability in each cycle. Section 5 shows that the conditions for equilibria are equivalent in both models, and in Sect. 6 we show that there always exists a pure equilibrium in the first model, and use the equivalence to prove that there always exists a pure equilibrium in the second model. Section 7 elaborates on research continuation of the subject.

2 The Model

We study a closed queueing network with a single server and two customers. A customer who enters service chooses either a low-rate or a high-rate service. After the end of the service the customer leaves for a low-rate or a high-rate activity period, respectively, and then returns to the queue. See Fig. 1.

Fig. 1.

The model.

Service time is exponentially distributed. The service rate is $\mu _l$ or $\mu _h$, corresponding to low and high service rate, $\mu _h > \mu _l$. Activity time is exponentially distributed with rate $\lambda _l$ or $\lambda _h$ corresponding to low and high activity rate, $\lambda _h > \lambda _l$. The service discipline is FCFS. When both customers choose the same service rate the model behaves as the Machine Interference Model (e.g. Gross and Harris [5] Section 2.7).

The utility of a customer is equal to the steady-state probability to be active. The social utility is the average utility of the customers. We denote the utility factor $\rho _\theta =\frac{\lambda _\theta }{\mu _\theta }, \theta \in \{l,h\}$.

2.1 Model Variations

Let customer i draw low service rate with probability $p^i, i=1,2$. We analyse social optima and existence of equilibria using the following strategies:

• pure strategy - customer i draws once a service rate (low service rate with probability $p^i$, $p^i \in \{0,1\}$) and sticks to it.

• mixed strategy - customer i draws once a service rate (low service rate with probability $p^i$, $p^i \in [0,1]$) and sticks to it.

• behavioral strategy - customer i independently draws low service rate with probability $p^i$, $p^i \in (0,1)$ each time he enters service. The customer sticks to the same probability throughout the game.

The utility function for a single customer is the expected fraction of time in activity, or, in other words, the probability to find the customer in the active period. $U(p^1,p^2)$ is the value of the utility function for customer 1, when each customer 2 draws low service rate with probability $p^2$. The social utility is the average utility of the customers.

We discuss pure symmetric strategies separately as they yield the same utilities for the mixed game and for the behavioral game.

3 Mixed Strategies

In the mixed strategy version customer i sticks to low service rate with probability $p^i$, otherwise he sticks to the high service rate. We consider three scenarios:

• The pure symmetric solution where $p^1=p^2, \quad p^i\in \{0,1\}$ - the machine interference model.

• The pure asymmetric solution where $p^1 \ne p^2, \quad p^i\in \{0,1\}$.

• The mixed solution where $p^i \in [0,1]$.

3.1 Steady-State Solution - Pure Strategies

Suppose the customers choose different service types. Let (k, m) define a state of the system, where $k,m \in \{a,s,w\}$ are the states of the first and the second customers, respectively. a - active, s - in service, w - waiting for service.

Fig. 2.

Transition diagram for the asymmetric strategy, $p^1=1, p^2=0$.

Let $U(p^1,p^2)$ denote the utility of customer 1, under the strategy profile $(p^1,p^2)$. Let $\pi _{km}$ denote the steady-state probability for state (k, m) under the asymmetric pure strategy case. We compute $U(1,0) = \pi _{aa}+\pi _{as}$ - the probability that customer 1 is active, and $U(0,1) = \pi _{aa}+\pi _{sa}$ - the probability that customer 2 is active, using Fig. 2.

$$\begin{aligned}&{U(1,0)}=\left( 1 + \rho _l+{\frac{\lambda _l {\rho _h}^2 (\lambda _l+\lambda _h \rho _l+\lambda _l \rho _l)}{(\lambda _l+\lambda _h \rho _l) ( \lambda _h+\lambda _h \rho _h +\lambda _l\rho _h )}}\right) ^{-1} \end{aligned}$$

(1a)

$$\begin{aligned}&{U(0,1)}=\left( 1 + \rho _h +\frac{\lambda _h \rho _l^2 (\lambda _h + \lambda _l \rho _h + \lambda _h \rho _h)}{ (\lambda _h + \lambda _l \rho _h)(\lambda _l + \lambda _l \rho _l + \lambda _h \rho _l)} \right) ^{-1} \end{aligned}$$

(1b)

We compute U(1, 1) and U(0, 0) when both customers choose the same service rate, using (1a) and (1b) respectively: with $\rho _l=\rho _h, \lambda _l=\lambda _h$:

$$\begin{aligned} U(1,1)&)=\left( 1+\rho _l+{\frac{{\rho _l}^{2}}{1+\rho _l}} \right) ^{-1} \end{aligned}$$

(2a)

$$\begin{aligned} U(0,0)&=\left( 1+\rho _h+{\frac{{\rho _h}^{2}}{1+\rho _h}} \right) ^{-1} \end{aligned}$$

(2b)

3.2 Optimal Strategy

There are cases (see Subsect. 3.4 for examples), where the pure symmetric strategy with the larger $\rho$ is an equilibrium, but we now show that the socially optimal strategy is always the pure symmetric strategy with the smaller utilization factor $\rho$.

Theorem 1

The pure symmetric strategy with the smaller $\rho$ is optimal.

Proof

We first note that the function $\frac{1+\rho }{1+2 \rho +2 \rho ^2}$ is monotone decreasing in $\rho$ and therefore among pure symmetric strategies, choosing the service with the smaller $\rho$ is optimal.

We now proceed to show that the optimal pure symmetric strategy is better than the asymmetric pure strategy. When the customers draw different pure strategies, the social utility is the average utility of the customers, i.e. $SU(0,1)=\frac{U(0,1)+U(1,0)}{2}$. By (1):

$$\begin{aligned} SU(0,1)&=\frac{\left( 1 + \rho _l+{\frac{\lambda _l {\rho _h}^2 (\lambda _l+\lambda _h \rho _l+\lambda _l \rho _l)}{(\lambda _l+\lambda _h \rho _l) ( \lambda _h+\lambda _h \rho _h +\lambda _l\rho _h )}}\right) ^{-1}}{2} \\&\qquad +\frac{\left( 1 + \rho _h +\frac{\lambda _h \rho _l^2 (\lambda _h + \lambda _l \rho _h + \lambda _h \rho _h)}{ (\lambda _h + \lambda _l \rho _h)(\lambda _l + \lambda _l \rho _l + \lambda _h \rho _l)} \right) ^{-1}}{2} \nonumber \end{aligned}$$

(3)

Lemma 2

When $\rho _l=\rho _h$, the socially-optimal pure strategy is symmetric.

Proof

Given $\rho$, the value U(0, 0) of the pure symmetric equilibrium is independent of $\lambda _h$ and $\lambda _l$. We show that for any $\lambda _h$ and $\lambda _l$, $SU(0,1) \le U(0,0)$. We first find the parameters that maximize SU(0, 1) by computing $\frac{\partial SU(0,1)}{\partial \lambda _l}$ and $\frac{\partial SU(0,1)}{\partial \lambda _h}$, when $\rho _l = \rho _h$:

$$\begin{aligned} \frac{\partial SU(0,1)}{\partial \lambda _l}&=\lambda _h(\lambda _h^2-\lambda _l^2)D\\ \frac{\partial SU(0,1)}{\partial \lambda _h}&=\lambda _l(\lambda _l^2-\lambda _h^2)D \end{aligned}$$

where $D=\frac{ \rho _h^2 (2 \rho _h+1) }{2\left( \lambda _l^2 \rho _h (\rho _h+1)^2+\lambda _l \lambda _h \left( 2 \rho _h \left( \rho _h^2+\rho _h+1\right) +1\right) +\lambda _h^2 \rho _h (\rho _h+1)^2\right) ^2}>0$.

By equating both derivatives to zero we see that SU(0,1) is extreme when $\lambda _l = \lambda _h$. The second derivatives are negative when we assign $\lambda _l = \lambda _h$, hence $SU(0,1)\le U(0,0)$ is maximized when $\lambda _l = \lambda _h$ in which case it is equal to U(0, 0).    $\square$

Lemma 3

A pure asymmetric strategy is never strictly better than the best pure symmetric strategy.

Proof

For $\rho _l = \rho _h$ the claim follows from Lemma 2. Assume first that $\rho _l > \rho _h$.

By (3):

Given $\rho _h$, SU(0, 1) is decreasing in $\rho _l$ and the maximum in the interval $\rho _l \in [\rho _h,\infty ]$ is achieved when $\rho _l = \rho _h$.

Assume now $\rho _l < \rho _h$, By (3):

Given $\rho _l$, SU(0, 1) is decreasing in $\rho _h$ and the maximum in the interval $\rho _h \in [\rho _l,\infty ]$ is achieved when $\rho _l = \rho _h$.

We showed in Lemma 2 that when $\rho _l=\rho _h$ the maximum is achieved when $\lambda _l = \lambda _h$.    $\square$

Lemma 4

A mixed asymmetric strategy is never optimal

Proof

A mixed strategy is a weighted average of the pure strategies U(0, 0), U(1, 1), U(0, 1), U(1, 0), therefore it cannot be strictly better than all of them.    $\square$

3.3 Equilibria

We use Fig. 3, where $\lambda _h=1.5, \rho _h=0.1, \lambda _l=1$. We draw the utilities on the range $\rho _l \in [0.100,0.110]$.

W.l.o.g. suppose $\lambda _l$, $\rho _h$ and $\lambda _h$ stay fixed. We start with $\rho _l=\rho _h$ (In the example in Fig. 3 $\rho _h=0.100$) and analyse the change in equilibria as $\rho _l$ increases.

Fig. 3.

$\lambda _h=1.5, \rho _h=0.1, \lambda _l=1$, $\rho _l>\rho _h$

Theorem 5

When $\rho _l\le \rho _h$, $p^1=p^2=1$ is the only pure-strategy equilibrium.

Proof

We prove the claim by showing that $U(0,1) < U(1,1)$, and $U(0,0)< U(1,0)$.

By definition $\lambda _h>\lambda _l$. By (1b) and (2a), $U(0,1) < U(1,1)$ is equivalent to

$$\begin{aligned}&1+\rho _h+\frac{\lambda _h \rho _l^2(\lambda _h+\lambda _l\rho _h+\lambda _h\rho _h}{(\lambda _h+\lambda _l\rho _h)(\lambda _l+\lambda _l\rho _h+\lambda _h\rho _l)}>1+\rho _l+\frac{\rho _l^2}{1+\rho _l} \Leftrightarrow \\&\lambda _h(1+\rho _l)(\lambda _h+\lambda _l\rho _h+\lambda _h\rho _h)> (\lambda _h+\lambda _l\rho _h)(\lambda _l+\lambda _l\rho _h+\lambda _h\rho _l)\Leftrightarrow \\&\lambda _h^2+\lambda _h^2\rho _h+\lambda _h^2\rho _l\rho _h>\lambda _h\lambda _l+\lambda _l^2\rho _h +\lambda _l^2\rho _h\rho _l \end{aligned}$$

$\lambda _h^2>\lambda _h\lambda _l$, $\lambda _h^2\rho _h>\lambda _l^2\rho _h$ and $\lambda _h^2\rho _l\rho _h>\lambda _l^2\rho _h\rho _l$ prove the claim.

In the same way, $U(1,0)>U(0,0)$ is equal to

$$\begin{aligned}&1 + \rho _l+{\frac{\lambda _l {\rho _h}^2 (\lambda _l+\lambda _h \rho _l+\lambda _l \rho _l)}{(\lambda _l+\lambda _h \rho _l) ( \lambda _h+\lambda _h \rho _h +\lambda _l\rho _h )}}<1+\rho _h+{\frac{{\rho _h}^{2}}{1+\rho _h}}\Leftrightarrow \\&{\frac{\lambda _l (\lambda _l+\lambda _h \rho _l+\lambda _l \rho _l)}{(\lambda _l+\lambda _h \rho _l) ( \lambda _h+\lambda _h \rho _h +\lambda _l\rho _h )}}<{\frac{1}{1+\rho _h}}\Leftrightarrow \\&{\lambda _l} ({\rho _h}+1) ({\lambda _l} {\rho _l}+{\lambda _l}+{\lambda _h} {\rho _l})<{\lambda _l} ({\rho _h}+1) ({\lambda _l} {\rho _l}+{\lambda _l}+{\lambda _h} {\rho _l})\Leftrightarrow \\&\lambda _l^2 + \lambda _l^2 \rho _l + \lambda _l \lambda _h \rho _l + \lambda _l^2 \rho _h + \lambda _l^2 \rho _l \rho _h + \lambda _l \lambda _h \rho _l \rho _h<\\ {}&\lambda _h^2 + \lambda _l \lambda _h \rho _l + \lambda _h^2 \rho _l + \lambda _l \lambda _h \rho _h + \lambda _l^2 \rho _l \rho _h + \lambda _l \lambda _h \rho _l \rho _h\Leftrightarrow \\&\lambda _l^2+\lambda _l^2 \rho _l + \lambda _l^2 \rho _h<\lambda _h^2 + \lambda _h^2 \rho _l+ \lambda _l \lambda _h \rho _h. \end{aligned}$$

   $\square$

Table 1. Examples of mixed strategies.

3.4 Examples

In Table 1 we show examples of pure and mixed strategies. In all three examples $p^1=p^2=0$ is socially optimal among pure symmetric and asymmetric strategies, but in the first example, Ex1, $U(1,0)<U(0,0)$, hence $p^1=p^2=0$ is an equilibrium. In the second example, Ex2, $U(0,1)<U(1,1)$, hence $p^1=p^2=1$ is an equilibrium. In the third example, Ex3, both $p^1=p^2=0$ and $p^1=p^2=1$ are equilibria, as $U(0,1)<U(1,1)$ and $U(1,0)<U(0,0)$.

Theorem 6

A unique mixed equilibrium $q=\frac{U(0,0)-U(1,0)}{U(0,0)-U(1,0)+U(1,1)-U(0,1)}$ exists iff there exist two pure equilibria, either both symmetric or both asymmetric.

Proof

Suppose both $p^1=p^2=0$ and $p^1=p^2=1$ are equilibria, then q is the probability that enforces, for a given customer, indifference between the strategies, when the other customer sticks to it. It is the solution of the equation $q U(1,1) + (1-q) U(1,0) = q U(0,1)+(1-q) U(0,0)$.

If both pure strategies are equilibria then $U(0,1)<U(1,1)$ and $U(1,0)<U(0,0)$ and therefore $0<q<1$.

Similarly, if the asymmetric strategies are equilibria then $U(0,1)>U(1,1)$ and $U(1,0)>U(0,0)$ so that again $0<q<1$.

If q is a valid mixed strategy, i.e. $0<q<1$, then the numerator and the denominator both have the same sign and either $U(0,0) > U(1,0)$ and $U(1,1) > U(1,0)$ and both pure symmetric strategies are equilibria, or $U(0,0) < U(1,0)$ and $U(1,1) < U(1,0)$ and then both pure asymmetric strategies are equilibria.    $\square$

In example Ex3, $q=\frac{0.4828-0.4723}{0.4828-0.4723+0.4-0.369}=0.2530$.

4 Behavioral Strategies

We now consider symmetric behavioral strategies, where all customers independently draw low service rate with probability p, every time they enter service.

4.1 Social Optimum of the Behavioral-Strategy Game

We are looking for p that maximizes the probability to be active when all customers follow the same strategy p.

Let (k, m) define a state of the system, where, $k,m \in \{a_l,a_h,s_l,s_h,w\}$ are the states of the customers without ordering (as customers are homogeneous). $a_l,a_h$ - low-rate or high-rate activity, $s_l,s_h$ - low-rate or high-rate service, w - waiting for service.

There are nine possible states. The vector $\pi$ provides the stationary probabilities for each state:

$$\begin{aligned} \pi =(\pi _{w,s_l},\pi _{ w,s_h },\pi _{s_l,a_l },\pi _{s_h,a_l },\pi _{s_l,a_h },\pi _{s_h,a_h },\pi _{ a_l,a_l },\pi _{ a_l,a_h },\pi _{ a_h,a_h}). \end{aligned}$$

We compute $\pi$ from the transition-rate diagram of the queueing system (see Fig. 4), and derive the probabilities $P_{i}, i=0,1,2$, for i active customers. U(p, p) is the utility of a customer when both customers select low-service rate with probability p.

$$\begin{aligned} U(p,p)= & {} \frac{P_1}{2}+P_2.\\ P_1= & {} \pi _{s_l,a_l}+\pi _{s_h,a_l}+\pi _{s_l,a_h}+\pi _{s_h,a_h}.\\ P_2= & {} \pi _{ a_l,a_l}+\pi _{ a_l,a_h}+\pi _{ a_h,a_h}. \end{aligned}$$

Fig. 4.

Steady-state transition diagram for U(p, p), $q=1-p$.

In the resulting formula of U(p, p), p appears always as a divisor of $1-p$, hence we simplify the presentation by searching for $r=\frac{1-p}{p}$ that maximizes $V(r)=U(p,p)$, and then $p=\frac{1}{r+1}$.

$$\begin{aligned} V(r)=\frac{a+br+cr^2}{\frac{1+2\rho _l+2\rho _l^2}{1+\rho _l}a+er+\frac{1+2\rho _h+2\rho _h^2}{1+\rho _h}c r^2} \end{aligned}$$

(4)

where

$$\begin{aligned} a= & {} (\lambda _l+\lambda _l\rho _l+\lambda _h \rho _l)(\lambda _h+\rho _h)\lambda _h^2,\\ b= & {} \lambda _l\lambda _h(\lambda _l^2\rho _h(2+\rho _l)+\lambda _h^2\rho _l(2+\rho _h)+\lambda _l\lambda _h(2+\rho _l+\rho _h+2\rho _l\rho _h)),\\ c= & {} (\lambda _h\rho _l+\lambda _l) (\lambda _h+\lambda _l\rho _h+\lambda _h\rho _h),\\ d= & {} 2\lambda _l \lambda _h ((\lambda _h^2 \rho _l+\lambda _l^2\rho _h) (\rho _l+1) (\rho _h+1)+\lambda _l\lambda _h (\rho _l (\rho _h (\rho _l+\rho _h+2)+1)+\rho _h+1)).\\ \end{aligned}$$

In particular, when $p^1=p^2=1$, $U(1,1)=\frac{1+\rho _l}{1+2\rho _l+2\rho _l^2}$ which is equal to the utility computed in (2a). Similarly, for $p=0$, using L’Hôpital’s rule, we obtain $U(0,0)=\frac{1+\rho _h}{1+2\rho _h+2\rho _h^2}$, as in (2b).

Theorem 7

If $\rho _l = \rho _h$ then U(p, p) has two maximum points, namely $p^*=0$ and $p^*=1$.

Proof

By (4), for every $0 \le p \le 1$,

$U(p,p)=V(r)=\frac{a+br+cr^2}{\frac{a}{U(1,1)}+d r+\frac{c}{U(1,1)} r^2}= U(1,1)\frac{a+b r+c r^2}{a+U(1,1) d r+c r^2}$.

$U(1,1)d>b \quad \text {as}\quad \frac{1+\rho }{1+2\rho +2\rho ^2}d-b=\frac{\lambda _l\lambda _h (\lambda _l-\lambda _h)^2\rho ^2}{1+2\rho +2\rho ^2}>0$,

hence $U(p,p)<U(1,1)=U(0,0)$.    $\square$

We now deal with any $\rho _l$ and $\rho _h$, not necessarily $\rho _l = \rho _h$. Figure 5 shows a graphical representation of U(p, p) with two numeric examples. U(p, p) is unimodal with one minimum point in [0, 1].

Fig. 5.

Examples of U(p, p).

Extensive numerical analysis, for virtually all possible parameter values, shows that social optimum cannot be achieved by a behavioral strategy with $0<p<1$.

Conjecture 8

$\arg \max {U(p,p)} \in \{0,1\}$.

4.2 Equilibria of Behavioral Strategies

The mixed behavioral strategy $0<p<1$ is an equilibrium if

$$\begin{aligned} U(1,p)=U(0,p). \end{aligned}$$

(5)

This means that if the other customer follows strategy p, the first customer is indifferent between the two pure selections, therefore p is also a best response. We first compute U(1, p) - the utility of a customer that always takes the low-rate service while the other customer - denoted p chooser- draws the low-rate service with probability p. We build the steady-state transition diagram (see Fig. 6). Let (k, m) define a state of the system, where, $k,m \in \{a_l,a_h,s_l,s_h,w\}$ are the states of the first and the second customer, respectively. $a_l,a_h$ - low-rate or high-rate activity, $s_l,s_h$ - low-rate or high-rate service, w - waiting for service. The vector $\pi$ gives the stationary probabilities for each state. The utility $U(1,p)=\pi _{a_l,s_l}+\pi _{a_l,a_l}+\pi _{a_l,s_h}+\pi _{a_l,a_h}$. In the same way we build the corresponding transition diagram for U(0, p), and compute the utilities:

$$\begin{aligned} U(1,p)&=(1+\rho _l)\frac{a p+b}{c_1p+d_1}\end{aligned}$$

(6a)

$$\begin{aligned} U(0,p)&=(1+\rho _h)\frac{a p+b}{c_0p+d_0}\end{aligned}$$

(6b)

$$\begin{aligned} U(p,1)&=(1+\rho _l)\frac{a p+b -k (1-p)\lambda _l}{c_1p+d_1}=U(1,p)-(1+\rho _l)\lambda _l\frac{(1-p)k}{c_1p+d_1} \end{aligned}$$

(6c)

$$\begin{aligned} U(p,0)&=(1+\rho _h)\frac{a p+b +k p\lambda _h}{c_0p+d_0}=U(0,p)+(1+\rho _h)\lambda _h\frac{pk}{c_0p+d_0} \end{aligned}$$

(6d)

Fig. 6.

Steady-state transition diagram for U(1, p).

where

$$\begin{aligned} a= & {} \lambda _h^3 \rho _l-\lambda _l^3\rho _h+\lambda _l\lambda _h^2-\lambda _l^2\lambda _h\\ b= & {} \lambda _l({\lambda _h} {\rho _l}+\lambda _l) ((\lambda _l+{\lambda _h}) {\rho _h}+{\lambda _h})\\ c_1= & {} \lambda _h^3 \rho _l \left( 2 \rho _l^2+2 \rho _l+1\right) +\lambda _l\lambda _h^2 \left( \rho _l^3 (\rho _h+1)+2 \rho _l^2+2 \rho _l+1\right) \\&+\ \lambda _l^2\lambda _h (\rho _l+1) \left( \rho _l^2 \rho _h-\rho _l \left( \rho _h^2+1\right) -1\right) -\lambda _l^3(\rho _l+1)^2 \rho _h (\rho _h+1)\\ d_1= & {} \lambda _l(\rho _l+1) (\lambda _h^2 \rho _l (\rho _l+1) (\rho _h+1)+\lambda _l\lambda _h (\rho _l (\rho _h (\rho _l+\rho _h+2)+1)+\rho _h+1)\\&+\ \lambda _l^2(\rho _l+1) \rho _h (\rho _h+1))\\ c_0= & {} \lambda _h^3 \rho _l (\rho _l+1) (\rho _h+1)^2-\lambda _l\lambda _h^2 (\rho _h+1) \left( -\left( \rho _l^2+1\right) \rho _h+\rho _l \rho _h^2-1\right) \\&-\ \lambda _l^2\lambda _h \left( (\rho _l+1) \rho _h^3+2 \rho _h^2+2 \rho _h+1\right) -\lambda _l^3\rho _h \left( 2 \rho _h^2+2 \rho _h+1\right) \\ d_0= & {} \lambda _l(2 \rho _h (\rho _h+1)+1) (\lambda _h \rho _l+\lambda _l) (\lambda _h \rho _h+\lambda _h+\lambda _l\rho _h))\\ k= & {} ( \lambda _h^2-\lambda _l^2) \rho _l \rho _h + \lambda _l\lambda _h ( \rho _h-\rho _l)\\ \end{aligned}$$

Theorem 9

A unique mixed behavioral equilibrium $p=\frac{(1+\rho _h)d_1-(1+\rho _l)d_0}{(1+\rho _l)c_0-(1+\rho _h)c_1}$ exists iff there exist two pure equilibria, either both symmetric or both asymmetric.

Proof

According to Theorem 5 more than one pure equilibrium is possible only if $\rho _l>\rho _h$. Recall that we defined $\lambda _h>\lambda _l$, it is easy to see that in that case all the coefficients in the following equations are positive. By (6)

$$\begin{aligned} U(1,0)= & {} (1+\rho _l)\frac{b}{d_1}.\\ U(0,1)= & {} (1+\rho _h)\frac{a+b}{c_0+d_0}.\\ U(1,1)= & {} (1+\rho _l)\frac{a+b}{c_1+d_1}.\\ U(0,0)= & {} (1+\rho _h)\frac{b}{d_0}.\\ U(0,0)-U(1,0)= & {} \frac{b}{d_0 d_1}((1+\rho _h)d_1-(1+\rho _l)d_0).\\ U(1,1)-U(0,1)= & {} \frac{a+b}{(c_0+d_0)(c_1+d_1)}{(1+\rho _l)(c_0+d_0)-(1+\rho _h)(c_1+d1}). \end{aligned}$$

p is a mixed behavioral equilibrium when $U(1,p)=U(0,p)$, which implies, by (6a, 6b) that $(1+\rho _l)\frac{a p+b}{c_1p+d_1}=(1+\rho _h)\frac{a p+b}{c_0p+d_0}$. All the coefficients are positive hence $p=\frac{(1+\rho _h)d_1-(1+\rho _l)d_0}{(1+\rho _l)c_0-(1+\rho _h)c_1}=\frac{\frac{d_0 d_1}{b}(U(0,0)-U(1,0))}{\frac{d_0 d_1}{b}(U(0,0)-U(1,0))+\frac{(c_0+d_0)(c_1+d_1)}{a+b}(U(1,1)-U(0,1))}$. In other words, $0<p<1$ is a valid probability value iff either both pure symmetric strategies are equilibria or both pure asymmetric strategies are equilibria.    $\square$

For example, when $\lambda _l=1, \rho _l=1, \lambda _l=2, \rho _l=1$, $p^1=p^2=1$ is the only behavioral equilibrium and $p<0$. Suppose $\lambda _l=1, \rho _l=1, \lambda _l=3, \rho _l=0.75$, $p=\frac{41}{482}$. In this case, $p^1=p^2=0$, $p^1=p^2=1$ and $p^1=p^2=\frac{41}{482}$ are equilibria. In Fig. 7 we show the functions U(1, p) and U(0, p) intersecting at $p = \frac{41}{482}$. The best-response function BR is FTC - Follow the Crowd, i.e. BR = 0 for $p < \frac{41}{482}$, BR=1 for $p > \frac{41}{482}$, and indifference exists when $p = \frac{41}{482}$.

Note that there is a mixed equilibrium (see Example Ex3 in Subsect. 3.1) for the same parameters, but the value is different - $p=0.2530$. These are two different strategies but the conditions for the strategies to be equilibria are equal, as we prove in the next section.

5 Equilibrium Equivalence

In this section we prove that an equilibrium in the mixed strategy game exists iff there exists an equilibrium in the behavioral game for exactly the same parameters, though the value may be different.

Lemma 10

In the behavioral model the functions U(p, 1), U(p, 0), U(1, p) and U(0, p) are monotone in the interval $0\le p\le 1$.

Fig. 7.

Best response - follow the crowd.

Proof

From (6) all these functions have the form

$$\begin{aligned} U(p)= & {} \frac{Ap+B}{Cp+D}\\ \frac{\partial U(p)}{\partial p}= & {} \frac{AD-BC}{(Cp+D)^2} \end{aligned}$$

where A, B, C, D are constants depending on the parameters $\rho _l,\rho _h,\lambda _l,\lambda _h$ alone. The numerator of the derivative does not contain p hence U(p) is a monotone function of p. If $AD=BC$ then U(p) is constant. Note that the denominator of U(p) cannot be zero in the interval [0, 1] as U(p) is bounded by 1, being a probability value.    $\square$

Theorem 11

A set of parameters ($\rho _l,\rho _h,\lambda _l,\lambda _h$) induces the same number and types of equilibria in the mixed-strategy model and in the behavioral-strategy model.

Proof

We prove for pure symmetric equilibria, for asymmetric pure equilibria and then for a mixed equilibrium.

A pure equilibrium in the behavioral-strategy model is a pure equilibrium in the mixed-strategy model as the condition for behavioral-strategy equilibrium is needed for a repeated draw in every cycle hence stronger than the condition needed for mixed-strategy equilibrium. So it is enough to prove that a pure mixed-strategy equilibrium is also an equilibrium in the behavioral-strategy model.

There are two pure symmetric strategies - $p^1=p^2=0$ and $p^1=p^2=1$. We prove for $p^1=p^2=1$ and the proof for $p^1=p^2=0$ is similar. $p^1=p^2=1$ is an equilibrium in the mixed-strategy model if $U(1,1) \ge U(0,1)$. $p^1=p^2=1$ is an equilibrium in the behavioral-strategy model if $U(1,1) \ge U(p,1) \quad \forall 0 \le p \le 1$. By Lemma 10 U(p, 1) is monotone. When $p^1=p^2=1$ is an equilibrium in the mixed-strategy model $U(1,1) \ge U(0,1)$, hence U(p, 1) is monotone non-decreasing and $U(1,1) \ge U(p,1) \quad \forall 0 \le p \le 1$.

There are two pure asymmetric strategies - $p^1=1,p^2=0$ and $p^1=0,p^2=1$. Either both are equilibria or neither is an equilibrium, as customers are homogeneous. When both pure asymmetric strategies are equilibria, $U(0,1)>U(1,1)$ and $U(1,0)>U(0,0)$ and therefore neither pure symmetric strategy is an equilibrium in either model. We showed in Theorems 6 and 9 that in either model a mixed strategy exists iff there are two pure strategy equilibria, i.e. the formulae that compute q - the mixed equilibrium, and p - the behavioral equilibrium, will yield valid probability values for exactly the same set of parameters, although in general $q \ne p$.    $\square$

Corollary 12

If no pure symmetric strategy is an equilibrium then both asymmetric pure strategies are equilibria.

Proof

If no pure symmetric strategy is an equilibrium then $U(0,1)\ge U(1,1)$ and $U(1,0) \ge U(0,0)$ which defines both asymmetric pure equilibria.

6 Graphical Analysis of Equilibria

In Theorem 11 we showed the equivalence of equilibria in the mixed and the behavioral models, and the following discussion refers to both. We illustrate the region of each equilibrium type by a graph in the $(\rho _l,\rho _h)$ plane, for $\lambda _l=1$ and various $\lambda _h$. The points $(\rho _l,\rho _h)$ on the boundary of the region where $p^1=p^2=1$ is an equilibrium satisfy $U(0,1)=U(1,1)$), and the points $(\rho _l,\rho _h)$ on the boundary of the region where $p^1=p^2=0$ is an equilibrium satisfy $U(1,0)=U(0,0)$). By (6) we get the two equations that define the relation between $(\rho _l,\rho _h)$ on the boundaries:

$$\begin{aligned} (1+\rho _h)(c_1+d_1)=(1+\rho _l)(c_0+d_0). \end{aligned}$$

(7)

$$\begin{aligned} (1+\rho _h)d_1=(1+\rho _l)d_0. \end{aligned}$$

(8)

Suppose $\lambda _h$ is fixed. For every given $\rho _l$ we define

$$\begin{aligned} {\underline{\rho }}_h(\rho _l)= & {} \min \{\rho _h|p_0=p_1=1 \textit{ is an equilibrium}\}.\\ \bar{\rho _h}(\rho _l)= & {} \max \{\rho _h|p_0=p_1=0 \textit{ is an equilibrium}\}. \end{aligned}$$

Figure 8 shows the region of each equilibrium for $(\rho _l,\rho _h) \in [0,1.5]$. Subfigures 8a, b, c and d show that as $\lambda _h$ increases, the region where both pure strategies are equilibria increases as well. We observe in these figures that $\bar{\rho _h}(\rho _l)>{\underline{\rho }}_h(\rho _l)$, implying the existence of a region with both $p^1=p^2=1$ and $p^1=p^2=0$ equilibria, and by Theorem 9 a mixed equilibrium exists as well, for every $\rho _l>0$.

Fig. 8.

$p^1=p^2=1$ is equilibrium in the region marked by vertical lines, $p^1=p^2=0$ is equilibrium in the region marked by horizontal lines.

The next lemma proves the extreme cases. When $\lambda _h=\lambda _l=1$ the region where both equilibria exist reduces to the line $\rho _h = \rho _l$, and when $\lambda _h \rightarrow \infty$ the region where both symmetric pure strategies are equilibria increases gradually with $\lambda _h$ and the boundaries converge, as we show in Fig. 8.

Lemma 13

Suppose $\lambda _h=\lambda _l=1$. Then $p^1=p^2=1$ is an equilibrium when $\rho _h \ge \rho _l$, and $p^1=p^2=0$ is an equilibrium when $\rho _h \le \rho _l$. (See Fig. 8a).

Proof

When $\lambda _h=\lambda _l=1$ choosing the larger $\mu$ (smaller $\rho$) is a dominant strategy as it achieves the same activity time for a smaller service time.

Lemma 14

When $\lambda _h \rightarrow \infty$, $\bar{\rho _h}(\rho _l)=\frac{1}{4}(\rho _l-1+\sqrt{1+6\rho _l+\rho _l^2})$ and ${\underline{\rho }}_h(\rho _l)=\frac{\rho _l^2}{(1+\rho _l)^2}$ (See Figs. 8b, c and d).

Proof

For specific $\rho _l,\rho _h$ and $\lambda _h \rightarrow \infty$, let $\mu _h$ grow accordingly to keep $\rho _h$ fixed and note that the service time of the customer with $p^2=0$ is negligible. $U(1,0)=\frac{1}{1+\rho _l}$ as there is no waiting time for the first customer with $p^1=1$. $U(0,0)=\frac{1+\rho _h}{1+2\rho _h+2\rho _h^2}$ does not change as it depends on $\rho _h$ alone. The upper boundary of the equilibrium region $p_1=p_0=0$ satisfies $U(1,0)=U(0,0)$, i.e.,

$$\begin{aligned} \bar{\rho _h}(\rho _l)=\frac{1}{4}(\rho _l-1+\sqrt{1+6\rho _l+\rho _l^2}) \end{aligned}$$

(9)

In the same way, $U(0,1)=\frac{1}{1+\rho _h}\frac{1}{1+\rho _l}$. $U(1,1)=\frac{1+\rho _l}{1+2\rho _l+2\rho _l^2}$ does not change as it depends on $\rho _l$ alone. The lower boundary of the region of $p_1=p_0=1$ satisfies $U(0,1)=U(1,1)$ i.e.,

$$\begin{aligned} {\underline{\rho }}_h(\rho _l)=\frac{\rho _l^2}{(1+\rho _l)^2}. \end{aligned}$$

(10)

   $\square$

Lemma 15

When $\lambda _h \rightarrow \infty$, $\bar{\rho _h}(\rho _l)>$ ${\underline{\rho }}_h(\rho _l)$.

Proof

For a given $\rho _h$, the inverse function of (9) - $\bar{\rho _l}(\rho _h)=\rho _h(1+\frac{\rho _h}{1+\rho _h})$, gives the value of $\rho _l$ on the boundary of the region where $U(1,0)=U(0,0)$. Then we use (10) to compute ${\underline{\rho }}_h(\bar{\rho _l}(\rho _h))$, which corresponds to $\bar{\rho _l}(\rho _h)$ on the boundary of the region where $U(1,0)=U(1,1)$. The claim follows from the following inequality:

$$\begin{aligned} {\underline{\rho }}_h(\bar{\rho _l}(\rho _h))=\frac{(\rho _h+2\rho _h^2)^2}{(1+2\rho _h+2\rho _h^2)^2}<\rho _h. \end{aligned}$$

(11)

   $\square$

We use Lemmas 13 and 15 to suggest Conjecture 16.

Conjecture 16

Every ($\rho _l,\rho _h$) is covered either by a region where there is one pure equilibrium or a region where there are two pure equilibria and one mixed equilibrium.

We proved the conjecture for when $\lambda _h=\lambda _l$ in Lemma 13. Our numerical results indicate that when $\lambda _h$ increases the equilibrium curves move downwards as shown in Fig. 8, and when $\lambda _h \rightarrow \infty$ we proved the conjecture in Lemma 15.

Corollary 17

Assuming Conjecture 16 is correct, the pure asymmetric strategies $p_1=0,p_0=1$ and $p_1=1,p_0=0$ cannot be equilibria.

Proof

In each point $(\rho _l,\rho _h)$ there is at least one pure equilibrium. If each customer draws a different pure strategy than at least one of them can improve his result by changing to the equilibrium pure strategy. Hence there is no asymmetric equilibrium.    $\square$

7 Concluding Remarks

We propose future research in the following directions: Generalize the model with more service types and more customers. Complete conjectures in this paper.

In the current analysis the decision is taken at the entry, and at that point in time the other customer is always active. If the decision is taken at the entry to the activity period there are two possible states of the other customer - either in service or in activity. We want to determine the conditions for optima and equilibria, and the difference compared to the model discussed in this paper.