# Game of arrivals at a two queue network with heterogeneous customer routes

Agniv Bandyopadhyay
School of Technology and Computer Science
Tata Institute of Fundamental Research
Mumbai, India
&Sandeep Juneja
School of Technology and Computer Science
Tata Institute of Fundamental Research
Mumbai, India

###### Abstract

We consider a queuing network that opens at a specified time, where customers
are non-atomic and belong to different classes. Each class has its own route,
and as is typical in the literature, the costs are a linear function of
waiting and service completion time. We restrict ourselves to a two class, two
queue network: this simplification is well motivated as the diversity in
solution structure as a function of problem parameters is substantial even in
this simple setting (e.g., a specific routing structure involves eight
different regimes), suggesting a combinatorial blow up as the number of
queues, routes and customer classes increase. We identify the unique Nash
equilibrium customer arrival profile when the customer linear cost preferences
are different. This profile is a function of problem parameters including the
size of each class, service rates at each queue, and customer cost
preferences. When customer cost preferences match, under certain parametric
settings, the equilibrium arrival profiles may not be unique and may lie in a
convex set. We further make a surprising observation that in some parametric
settings, customers in one class may arrive in disjoint intervals. Further,
the two classes may arrive in contiguous intervals or in overlapping
intervals, and at varying rates within an interval, depending upon the problem
parameters.

_K_ eywords strategic arrivals $\cdot$ queuing network games $\cdot$
population games.

##  1 Introduction

Queueing games or games where strategic customers, served by a queue or a
queuing network, decide on actions such as which queue to join, whether to
join, when to join, what level of priority to select and so on, are well
studied in the literature (see [6, 7, 9] for surveys). In this paper we focus
on the queuing arrival game where customers decide on when to join a queuing
network. This is in contrast to much of the literature that considers arrival
games to a single queue (see, e.g., [2, 5, 8, 9, 12, 13, 15]). Applications of
such arrival games to multiple queues are many: Customers arriving to a health
facility where they queue up to meet a doctor and then may queue to get tests
done and/or procure medicines; in banks where different customers may need to
go to different and multiple counters; in cafeteria where customers queue up
for different and multiple food items, and so on. In consonance with much of
the existing literature, we model customers as non-atomic ‘infinitesimal’
fluid particles with costs that are linear in waiting time and in time to
service, customers are served in a first-come-first-serve manner and service
facility opens at time zero (see [11, 12, 15]). In [13], uniqueness of
equilibrium solution was proven in a single queue setting with stochastic
service rates and large no of users. Moreover, [13] showed that, the
equilibrium solution with a large no of users is well approximated by the
corresponding fluid system and thus lending support to the fluid analysis.
This fluid setting has resulted in unique and elegant, easily calculable
customer equilibrium profiles for single queues as well as certain symmetric
queuing networks where customers have homogeneous travel routes (see [11,
12]).

To keep the discussion simple we focus on a two queue, two class customer
setting where each class of customers has a distinct route, and customers in
each queue are served in a first-come-first-served manner. While this set-up
may be practically interesting, our main contributions are theoretical: Our
key aim is to test whether the elegance and simplicity of customer equilibrium
behaviour to a single queue extends to more general queuing networks in
presence of heterogeneous routing.

Even in the simple two queue setting, we see that, unlike for the single
queue, here the solution structure and order of arrivals in equilibrium is a
function of all the problem parameters, i.e., linear coefficients of the cost
function, the queue service rates and the population size of each class of
customers. For one set of customer travel routes we observe that depending
upon problem parameters, there exist eight distinct solution structures. This
suggests that as the number of queues increase there may be a rapid blow-up in
the solution structures. This may make the problem of identifying and learning
the correct structure computationally prohibitive. In this paper, we do not
address the issue of customers learning the equilibrium profile by repeatedly
playing the game. Limiting behaviour of players repeatedly updating their
action in a game using a simple rule, often called a ‘no-regret’ policy, are
studied in [1] and we refer the reader to [3] for a comprehensive exposition
of this literature.

Our other broad contributions/observations are: 1) We find that similar to the
single queue setting, the equilibrium profile of arriving customers is unique
for a wide set of parameters. However, interestingly, when customer cost
preferences across classes are identical up to a constant, there may be
multiple equilibrium arrival profiles, all lying in a convex set that we
identify. Although there are many arrival profiles in equilibrium in this
case, they all have identical social cost.
2) In [12], the equilibrium profile is determined for the case when multiple
classes of customers with linear costs are arriving at a single queue again.
They find that different classes of customers arrive in non-overlapping and
contiguous intervals. In our two queue setting we find that depending upon the
problem parameters, in equilibrium, arrivals may come in non-overlapping and
contiguous intervals, in overlapping intervals, or under certain parametric
settings, a class of customers may even arrive in disjoint intervals.
Moreover, we show that whether the classes will arrive over overlapping sets
or not is independent of the population sizes and decided entirely by the
queue service rates and customer preferences.

Related literature: The arrival games to queues were first considered by [5].
The concert queueing game is the fluid setting was introduced in [12]. The
arrival game in a fluid network of bottleneck queues including tandem,
Trellis, and general feed-forward networks was considered in [11], where they
characterized the equilibrium arrival profile in each of these topologies.

Transportation modelling community has extensively studied arrival games.
Vickrey in [16], introduced the morning commute problem. Unlike the concert
queuing game, in these transportation problems, the service facility has no
predetermined opening time. Instead, the customers have a preferred time to
complete service and a cost for arriving too early or too late (see [10]).
This led to a huge literature on arrival games to a bottleneck queue, the
impact of tolls, etc. (see [14] for an extensive list of references). Much of
the transportation literature considers single queue settings. Lindsey, in an
influential work [15], establishes the existence of equilibrium arrival
profile for multiple classes of customers with general non-linear cost
functions arriving at a bottleneck queue with a constant service rate, through
intricate fixed point arguments. Our work differs from transportation
literature in that we consider a two queue network with heterogeneous arrival
routes, linear costs, and in this setting we are able characterize the
equilibrium user arrival profiles in a closed form, and for a large class of
parameters, show that these profiles are unique.

Outline of the paper: In Section 2 we provide the background to the arrival
queueing game and overview the two-class, two queue, two-route networks that
we consider. We emphasize on two heterogeneous routes networks 1) where the
departures of the two classes are through different queues (Heterogeneous
Departure System or HDS) and 2) where the arrivals enter at different queues
(Heterogeneous Arrival System or HAS). In Section 3, we identify the
equilibrium arrival profile for all possible parameters for arriving customers
for HDS. In particular, we see that these parameters can be partitioned into
four distinct regions each having a separate solution structure, when the two
customer classes have unequal preferences. In Section 4 we similarly analyze
HAS. Here we discover that the parameter space can be partitioned into eight
regions based on the solution structure, when the two customer classes have
unequal preferences. Moreover, for both HDS and HAS, when the groups have
identical preference, we identify a parametric regime where unique equilibrium
exists, as well as a parametric regime where the equilibrium is non-unique and
the set of equilibrium profiles is convex. We end with a brief conclusion in
Section 5. In the main body, we have confined our discussion to the main proof
ideas behind our results and have kept the detailed proofs in the appendix.

##  2 Preliminaries

###  2.1 Fluid Model

We consider a fluid model having two classes of customers or users. The size
of each class $i=1,2$ is given by a positive quantity $\Lambda_{i}>0$. In
every class $i=1,2$ individual users are infinitesimal and the set of all
users in class $i$ is given by the points in the interval $[0,\Lambda_{i}]$.

We define functions $F_{i}:\mathbb{R}\to[0,\Lambda_{i}]$ for $i=1,2$ such
that, $F_{i}(t)$ denotes the amount of users of class $i$ that arrive by time
$t$. We call $F_{i}$ the arrival profile of class $i$ users. Therefore, each
$F_{i}$ is non-decreasing and satisfies $F_{i}(-\infty)=0$ and
$F_{i}(+\infty)=\Lambda_{i}$. We consider $F_{i}$ that are right-continuous
and can be expressed as a sum of a non-decreasing absolutely continuous
function and a non-decreasing discrete function. We call the pair
$\mathbf{F}=\\{F_{1},F_{2}\\}$ as the joint arrival profile of the two
classes.

We consider a network comprising of two queues, both starting service at time
$t=0$. Let $\mu_{1}$ and $\mu_{2}$, respectively, denote the deterministic
fixed service rates at the two queues after they start service. We consider
four routes of the two arriving classes to the two queues. These are displayed
in Table 1.

Instance I Instance II Instance III (Heterogeneous Departure System or HDS)
Instance IV (Heterogeneous Arrival System or HAS)

Table 1: Various instances with two groups traveling through two queues
connected in tandem

Instance I is equivalent to two groups of users arriving at a two-layer tandem
network to travel by the same path. By Theorem 5 of [11], the instance is
equivalent to the case where the two groups are arriving at a single queue of
capacity $\min\\{\mu_{1},\mu_{2}\\}$. Instance II is equivalent to the case
where the two queues independently serve the two groups and therefore is
equivalent to two independent instances of a single queue with a single class
customer arrivals. Hence, the first two instances are reducible to instances
with just one queue studied in [12]. In this paper we study the arrival
equilibrium behaviour in the other two instances III and IV. We refer to them
as Heterogeneous Departure (HDS) and Heterogeneous Arrival Systems (HAS),
respectively.

###  2.2 Waiting and Departure Times

To specify the waiting and departure times in a system, first consider a
single queue setting where $A(t)$ denotes the total mass of users of all
classes that have arrived at the queue by time $t$. Let $\mu$ denote the
service rate. Then at time $t$, the length of the waiting queue developed in
that queue will be (see Theorem 6.5 in [4]):

$\displaystyle Q(t)$
$\displaystyle=A(t)-\mu\cdot\max\\{t,0\\}+\sup_{s\in[0,t]}\max\left\\{\mu
s-A(s),0\right\\}.$ (1)

We assume that if there is a jump in the arrival profile $A$ at time $t$, the
arrivals are positioned in the queue at uniformly random order. As a result, a
user arriving at that queue at time $t$ will suffer an expected waiting time
of

$\displaystyle W(t)$
$\displaystyle=\frac{Q(t+)+Q(t-)}{2\mu}+\max\\{0,-t\\},~{}\text{and departs at
time}~{}~{}\tau(t)=W(t)+t,$ (2)

where $Q(t+)$ and $Q(t-)$ respectively denote the right and left limits of $Q$
at time $t$. Note that if the queue length process $Q(\cdot)$ is continuous
(which is the case if $A(\cdot)$ is absolutely continuous), waiting time as a
function of time $t$ will be $W(t)=\frac{Q(t)}{\mu}+\max\\{0,-t\\}$.

If the arrival profile $A(\cdot)$ is absolutely continuous, by (1) and (2),
the departure time as a function of time $t$ will be:
$\tau(t)=\frac{A(t)}{\mu}+\sup_{s\in[0,t]}\max\left\\{0,s-\frac{A(s)}{\mu}\right\\}$.
Whenever $Q(t)>0$, the term $\sup_{s\in[0,u]}\max\\{\mu s-A(s),0\\}$ is
independent of the choice of $u\in[t-\delta,t+\delta]$ for $\delta>0$ and
sufficiently small, and when $t<0$, $\tau_{1}(t)=\frac{A(t)}{\mu}$. If
$A(\cdot)$ is absolutely continuous, its derivative $A^{\prime}(\cdot)$ will
exist a.e. As a result,

$\displaystyle\tau^{\prime}(t)$
$\displaystyle=\frac{A^{\prime}(t)}{\mu}~{}~{}\text{a.e. in the closure of the
set of times}~{}\\{s~{}|~{}s<0~{}\text{or}~{}Q(s)>0\\}.$ (3)

The above observation will be useful in our analysis of HDS and HAS in the
later sections.

######  Definition 2.1.

We say the queue is _engaged_ at time $t$ if $t$ lies in the closure of the
set $\\{s~{}|~{}Q(s)>0\\}$.

By (3), after the queue starts serving, users depart at rate $\mu$ whenever
the queue is engaged. We introduce the following notation:

  * •

$A_{i}(t)$ be the total mass of customers of both the groups who have arrived
at queue $i=1,2$ till time $t$ (Note that while $F_{i}$ denotes arrival
profile corresponding to user class $i$, $A_{i}$ denotes overall arrival
profile to queue $i$.).

  * •

$Q_{i}(t)$ and $W_{i}(t)$ be the length of the waiting queue, and the waiting
time that a customer arriving in queue $i$ at time $t$ will observe. Let
$\tau_{i}(t)$ denote the time that customer will depart the system.

  * •

$W_{\mathbf{F}}^{(j)}(t)$ and $\tau_{\mathbf{F}}^{(j)}(t)$ be the waiting and
departure times from the network suffered by a class $j$ user arriving at time
$t$ for $j\in\\{1,2\\}$. Explicit dependence on $\mathbf{F}$ in this notation
is useful to our analysis later.

For both the queues $i=1,2$ upon defining the arrival profile $A_{i}(\cdot)$,
using (1) and (2), $Q_{i}(\cdot)$, $W_{i}(\cdot)$ and $\tau_{i}(\cdot)$ are
well-defined. Now we specify the waiting and departure times of both the
queues in HDS and HAS as functions of time, under the assumption that the
joint arrival profile $\mathbf{F}=\\{F_{1},F_{2}\\}$ is absolutely continuous
(we later argue by Lemma 2.1 that considering absolutely continuous joint
arrival profiles are sufficient for identifying equilibrium behavior).

  1. HDS

: Arrival profiles at individual queues are $A_{1}(t)=F_{1}(t)+F_{2}(t)$ and
$A_{2}(t)=F_{2}(\tau_{1}^{-1}(t))$, where
$\tau_{1}^{-1}(t)=\sup\\{s~{}|~{}\tau_{1}(s)\leq t\\}$. Both $A_{1}(\cdot)$
and $A_{2}(\cdot)$ are absolutely continuous. With this,
$W_{\mathbf{F}}^{(1)}(t)=W_{1}(t)$, $\tau_{\mathbf{F}}^{(1)}(t)=\tau_{1}(t)$,
$W_{\mathbf{F}}^{(2)}(t)=W_{1}(t)+W_{2}(\tau_{1}(t))$, and
$\tau_{\mathbf{F}}^{(2)}(t)=\tau_{1}(t)+W_{2}(\tau_{1}(t))$.

  2. HAS

: Arrival profile at individual queues are $A_{1}(t)=F_{1}(t)$ and
$A_{2}(t)=F_{1}(\tau_{1}^{-1}(t))+F_{2}(t)$ where
$\tau_{1}^{-1}(t)=\sup\\{s~{}|~{}\tau_{1}(s)\leq t\\}$. Both $A_{1}(\cdot)$
and $A_{2}(\cdot)$ are absolutely continuous. With this,
$W_{\mathbf{F}}^{(1)}(t)=W_{1}(t)+W_{2}(\tau_{1}(t))$,
$\tau_{\mathbf{F}}^{(1)}(t)=\tau_{1}(t)+W_{2}(\tau_{1}(t))$,
$W_{\mathbf{F}}^{(2)}(t)=W_{2}(t)$, and
$\tau_{\mathbf{F}}^{(2)}(t)=\tau_{2}(t)$.

###  2.3 Solution Concept

We assume that every user in group $i$ ($i\in\\{1,2\\}$) has a cost function
linear in her waiting and departure times from the network given by:
$C_{\mathbf{F}}^{(i)}(t)=\alpha_{i}\cdot
W_{\mathbf{F}}^{(i)}(t)+\beta_{i}\cdot\tau_{\mathbf{F}}^{(i)}(t)$, where
$\alpha_{i}$ and $\beta_{i}$ are positive constants quantifying the cost
suffered by a class $i$ user for unit waiting time and delay in departure.

######  Definition 2.2 (Support of arrival profile).

Given an arrival profile $t\mapsto B(t)$ such that $B(+\infty)<\infty$, the
support of $B$, denoted by $\mathcal{S}(B)$, is defined as the smallest closed
set having a $B$-measure equal to $B(+\infty)$.

######  Definition 2.3 (Equilibrium Arrival Profile (EAP)).

The joint arrival profile
$\mathbf{F^{\star}}=\\{F^{\star}_{1},F^{\star}_{2}\\}$ is an Equilibrium
Arrival Profile of this game if for both the groups $i\in\\{1,2\\}$:
$t\in\mathcal{S}(F_{i}^{\star})$ and $\tilde{t}\in\mathbb{R}$ implies
$C_{\mathbf{F^{\star}}}^{(i)}(t)\leq C_{\mathbf{F^{\star}}}^{(i)}(\tilde{t})$.
In particular, the arrival profile is iso-cost along its support.

Note that, the EAP doesn’t change upon normalizing the cost function of both
the classes $i=1,2$ by multiplying $1/(\alpha_{i}+\beta_{i})$. For simplicity,
and without loss of generality, we assume both the classes $i=1,2$ have their
normalized cost function, which are:
$C_{\mathbf{F}}^{(i)}(t)=\gamma_{i}W_{\mathbf{F}}^{(i)}(t)+(1-\gamma_{i})\tau_{\mathbf{F}}^{(i)}(t)$
where $\gamma_{i}=\frac{\alpha_{i}}{\alpha_{i}+\beta_{i}}$ quantifies the
preference of every class $i$ user. A value of $\gamma_{i}$ close to $1$
indicates users in group $i$ prefer late departure compared to waiting a long
time in the network and $\gamma_{i}$ close to $0$ implies the opposite. So, we
use $\gamma_{i}$ to quantify the cost preference of every group $i$ user.

######  Remark 1.

_EAP captures the aggregate equilibrium behavior of the group. We can
equivalently define Nash equilibrium at individual level where under it no
individual has unilateral incentive to deviate. As is well known and discussed
in more detail in[12], the two concepts are equivalent._

######  Lemma 2.1.

In every EAP, $\mathbf{F}=\\{F_{1},F_{2}\\}$ of the HDS and HAS, the arrival
profiles $F_{1}$ and $F_{2}$ are absolutely continuous.

Proof of the above lemma is similar to proof of statement (ii) of Lemma 1 in
[12]. On assuming contradiction, if any of the arrival profiles have a jump,
any user arriving in that jump will be strictly better off arriving slightly
early and as a result the arrival profile cannot be an EAP.

We argued before that Instances I and II in Table 1 are reducible to instances
where one or more groups of users having distinct preferences are arriving to
a single queue. [12] show that when two classes of customers having cost
preferences $\gamma_{1}$ and $\gamma_{2}$ arrive at a single queue with
service rate $\mu$, the EAP has a simple structure. The class with smaller
$\gamma_{i}$ comes first at arrival rate
$\mu\cdot\min\\{\gamma_{1},\gamma_{2}\\}$ over an interval, while the next
class arrives at a contiguous but non-overlapping interval, at rate
$\mu\cdot\max\\{\gamma_{1},\gamma_{2}\\}$. Fig 1 illustrates this EAP and the
resulting queue length with the assumption $\gamma_{1}<\gamma_{2}$ and is
useful to contrast with the various EAP structures that we find for HDS and
HAS in Sections 3 and 4 below. The queue length process is constructed
assuming that in the EAP, class 2 users start arriving from a positive time,
which is equivalent to saying, masses of the two classes satisfy
$\Lambda_{1}>\left(\frac{1}{\gamma_{2}}-1\right)\Lambda_{2}$.

Figure 1: EAP structure (left) and resulting queue length process (right) when
two classes of users with cost preferences $\gamma_{1}$ and $\gamma_{2}$
(assuming $\gamma_{1}<\gamma_{2}$) are arriving at a queue of capacity $\mu$.
The support boundaries are
$T_{2,f}=\frac{\Lambda_{1}+\Lambda_{2}}{\mu},~{}T_{2,a}=\frac{\Lambda_{1}}{\mu}-\left(\frac{1}{\gamma_{2}}-1\right)\frac{\Lambda_{2}}{\mu}$
and
$T_{1,a}=-\left(\frac{1}{\gamma_{1}}-1\right)\frac{\Lambda_{1}}{\mu}-\left(\frac{1}{\gamma_{2}}-1\right)\frac{\Lambda_{2}}{\mu}$.
The queue length process is illustrated only for the situation $T_{2,a}>0$, or
equivalently $\Lambda_{1}>\left(\frac{1}{\gamma_{2}}-1\right)\Lambda_{2}$. Red
and blue, respectively, represents class 1 and 2 populations. The black dashed
line represents the total waiting mass of the two classes in the plot for
queue length.

##  3 Heterogeneous Departure Systems (HDS)

In this section, we consider the situation where the two classes arrive at the
first queue and depart from different queues, as illustrated in Table 1. If
$\mu_{1}\leq\mu_{2}$, class 2 users arrive at queue 2 at a maximum rate of
$\mu_{1}$ and as a result, queue 2 remains empty and the cost of class 2 is
unaffected by the second queue. Thus, if $\mu_{1}\leq\mu_{2}$, the instance
becomes equivalent to both the groups arriving at a queue of capacity
$\mu_{1}$. The problem is identical to the two-class, single queue case
studied in [12]. Therefore, in subsequent discussion, we restrict ourselves to
HDS with $\mu_{1}>\mu_{2}$. We further consider the case
$\gamma_{1}\neq\gamma_{2}$ separately from $\gamma_{1}=\gamma_{2}$ since the
latter displays different behaviour.

###  3.1 Unequal Preferences: $\gamma_{1}\neq\gamma_{2}$

Structural properties of EAP. We identify several structural properties that
every EAP of HDS satisfies. We will exploit these properties later to narrow
our search of an EAP. Many of these properties are true even when the two
groups have equal preference, i.e., $\gamma_{1}=\gamma_{2}$, and we use them
later in Section 3.2.

As mentioned earlier, when $\mu_{1}\leq\mu_{2}$, the second queue is not
relevant to equilibrium behaviour, and the two classes arrive in disjoint,
contiguous intervals in the order of increasing $\gamma$’s. Lemma 3.1 shows
that the EAP has a similar arrival pattern up to a threshold for
$\mu_{1}>\mu_{2}$.

######  Lemma 3.1 (Threshold Behavior).

If $\gamma_{1}\neq\gamma_{2}$, in the EAP, the two classes arrive over
contiguous intervals with disjoint interiors if and only if
$\mu_{1}\leq\mu_{2}\cdot\max\left\\{1,\frac{\gamma_{2}}{\gamma_{1}}\right\\}$.

Below we sketch the proof of sufficiency of the condition stated in Lemma 3.1.
Proving the other direction requires exploiting the behavior of the two queues
in EAP and also the structure of $\mathcal{S}(F_{1})$ and
$\mathcal{S}(F_{2})$. So, we prove that after stating Lemma 3.5.

Proof sketch of sufficiency in Lemma 3.1: The detailed proof of sufficiency of
the condition
$\mu_{1}\leq\mu_{2}\cdot\max\left\\{1,\frac{\gamma_{2}}{\gamma_{1}}\right\\}$
is in Lemma A.3 and is similar to the proof sketch we will present here, but
instead uses some other supplementary lemmas and tools. First we show via
contradiction that if
$\mu_{1}\leq\mu_{2}\cdot\max\left\\{1,\frac{\gamma_{2}}{\gamma_{1}}\right\\}$,
$\mathcal{S}(F_{1})$ and $(\mathcal{S}(F_{2}))^{o}$ cannot overlap. We later
argue via Lemma 3.2 (stated later) that in every EAP
$\mathbf{F}=\\{F_{1},F_{2}\\}$, $\mathcal{S}(F_{1})$ and $\mathcal{S}(F_{2})$
are intervals. As a result, by the previous two statements, sufficiency of the
stated condition will follow.

If
$\mu_{1}\leq\mu_{2}\cdot\max\left\\{1,\frac{\gamma_{2}}{\gamma_{1}}\right\\}$,
and $\mathcal{S}(F_{1}),(\mathcal{S}(F_{2}))^{o}$ overlap, we can find
$t_{1},t_{2}\in\mathcal{S}(F_{1})$ such that
$[t_{1},t_{2}]\subseteq\mathcal{S}(F_{2})$. Note that queue 1 must be engaged
in $(t_{1},t_{2})$, otherwise the class 1 user arriving at $t_{2}$ is strictly
better off arriving at the time when queue 1 is empty in $(t_{1},t_{2})$.
Hence using 3,
$(C_{\mathbf{F}}^{(1)})^{\prime}(t)=\tau_{1}^{\prime}(t)-\gamma_{1}=\frac{F_{1}^{\prime}(t)+F_{2}^{\prime}(t)}{\mu_{1}}-\gamma_{1}$
in $[t_{1},t_{2}]$. Now $t_{1},t_{2}\in\mathcal{S}(F_{1})$ implies
$C_{\mathbf{F}}^{(1)}(t_{2})=C_{\mathbf{F}}^{(1)}(t_{1})$, which by
integrating
$(C_{\mathbf{F}}^{(1)})^{\prime}(t)=\frac{F_{1}^{\prime}(t)+F_{2}^{\prime}(t)}{\mu_{1}}-\gamma_{1}$
in $[t_{1},t_{2}]$ gives

$F_{1}(t_{2})+F_{2}(t_{2})-(F_{1}(t_{1})+F_{2}(t_{1}))=\mu_{1}\gamma_{1}(t_{2}-t_{1}).$

Therefore $\mu_{1}\gamma_{1}(t_{2}-t_{1})$ is the total mass of the two groups
that have arrived in $[t_{1},t_{2}]$.

Since $[t_{1},t_{2}]\subseteq\mathcal{S}(F_{2})$, we must have
$(C_{\mathbf{F}}^{(2)})^{\prime}(t)=0$ and hence
$(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)=\gamma_{2}$ in $[t_{1},t_{2}]$. As
$\tau_{\mathbf{F}}^{(2)}(t)=\tau_{2}(\tau_{1}(t))$, we have
$(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)=\tau_{2}^{\prime}(\tau_{1}(t))\tau_{1}^{\prime}(t)$
in $[t_{1},t_{2}]$, assuming the derivatives exist. Later we argue in Lemma
3.3 that, queue 2 must remain engaged at $\tau_{1}(t)$ for every
$t\in[t_{1},t_{2}]$. Therefore, using (3),
$\tau_{2}^{\prime}(\tau_{1}(t))=\frac{A_{2}^{\prime}(\tau_{1}(t))}{\mu_{2}}$,
and hence
$(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)=\frac{A_{2}^{\prime}(\tau_{1}(t))\tau_{1}^{\prime}(t)}{\mu_{2}}$
in $[t_{1},t_{2}]$. Since $A_{2}(\tau_{1}(t))=F_{2}(t)$, the previous
statement implies
$(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)=\frac{F_{2}^{\prime}(t)}{\mu_{2}}$ in
$[t_{1},t_{2}]$. Combining this with the observation that
$(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)=\gamma_{2}$ a.e. in $[t_{1},t_{2}]$, we
have $F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}$ a.e. in $[t_{1},t_{2}]$. Therefore,

$F_{2}(t_{2})-F_{2}(t_{1})=\mu_{2}\gamma_{2}(t_{2}-t_{1}).$

Since a positive mass of both the classes arrive in $[t_{1},t_{2}]$, we must
have
$F_{1}(t_{2})+F_{2}(t_{2})-(F_{1}(t_{1})+F_{2}(t_{1}))>F_{2}(t_{2})-F_{2}(t_{1})$,
which implies $\mu_{1}\gamma_{1}>\mu_{2}\gamma_{2}$ by the previous arguments.
This contradicts our assumption that
$\mu_{1}\leq\mu_{2}\max\left\\{1,\frac{\gamma_{2}}{\gamma_{1}}\right\\}$. ∎

Lemma 3.2 and 3.4 imply EAPs can only be piece-wise linear arrival profiles
with intervals as support. Proof of Lemma 3.2 (in A.1) is done via
contradiction by arguing if there is a gap, we can identify a user who can
improve her cost by arriving at a different time.

######  Lemma 3.2 (Structure of supports).

If $\mu_{1}>\mu_{2}$ and $\mathbf{F}=\\{F_{1},F_{2}\\}$ is an EAP, then
$\mathcal{S}(F_{1})$ and $\mathcal{S}(F_{1})\cup\mathcal{S}(F_{2})$ must be
intervals. Additionally, if $\gamma_{1}\neq\gamma_{2}$, $\mathcal{S}(F_{2})$
must also be an interval.

For a joint arrival profile $\mathbf{F}=\\{F_{1},F_{2}\\}$, we define the
quantities $T_{i,a}\overset{def.}{=}\inf\mathcal{S}(F_{i})$ and
$T_{i,f}\overset{def.}{=}\sup\mathcal{S}(F_{i})$ for the two classes
$i\in\\{1,2\\}$. For every EAP $\mathbf{F}$,
$\mathcal{S}(F_{1}),~{}\mathcal{S}(F_{2})$ must be compact, as cost of the two
classes over their support must be finite. As a result, the support boundaries
$T_{1,a},T_{1,f},T_{2,a},T_{2,f}$ must be finite. By Lemma 3.2, we can further
say, $\mathcal{S}(F_{1})=[T_{1,a},T_{1,f}]$ and
$\mathcal{S}(F_{2})=[T_{2,a},T_{2,f}]$, such that union of the two intervals
is also an interval.

Lemma 3.3 is about the behavior of queue 2 in equilibrium.

######  Lemma 3.3.

If $\mu_{1}>\mu_{2}$ and $\gamma_{1}\neq\gamma_{2}$, then under EAP, for every
$t\in(T_{2,a},T_{2,f})$, $\tau_{1}(t)$ belongs to the closure of the set
$\\{s~{}|~{}Q_{2}(s)>0\\}$.

Proof sketch of Lemma 3.3: We consider two separate cases:

  1. 1.

If $t\in(T_{2,a},T_{2,f})/(T_{1,a},T_{1,f})$, two possibilities are there. If
queue 1 is engaged at $t$, class 2 users arrive from queue 1 to 2 at rate
$\mu_{1}>\mu_{2}$ at $\tau_{1}(t)$, making queue 2 engaged. Otherwise, if
queue 1 is empty at $t$, in EAP, the network cannot be empty at $t$ with a
positive mass of class 2 users arriving in $(t,T_{2,f})$. As a result, queue 2
must be engaged at $t=\tau_{1}(t)$.

  2. 2.

If $t\in(T_{1,a},T_{1,f})\cap(T_{2,a},T_{2,f})$, we assume a contradiction,
i.e., queue 2 is empty in some neighbourhood of $\tau_{1}(t)$. As a result, by
continuity of $\tau_{1}(\cdot)$, only queue 1 will be serving in some
neighbourhood of $t$. Therefore
$\tau_{\mathbf{F}}^{(1)}(\cdot)=\tau_{\mathbf{F}}^{(2)}(\cdot)=\tau_{1}(\cdot)$
in that neighbourhood. Also, for both the classes $i=1,2$ to be iso-cost in
that neighbourhood, we need
$(C_{\mathbf{F}}^{(i)})^{\prime}(s)=\tau_{1}^{\prime}(s)-\gamma_{i}=0$. This
gives us $\tau_{1}^{\prime}(s)=\gamma_{1}=\gamma_{2}$, contradicting
$\gamma_{1}\neq\gamma_{2}$.

∎

Lemma 3.4 states conditions on the arrival rates necessary for the two classes
to have constant cost over their support in any EAP.

######  Lemma 3.4 (Rates of arrival).

If $\mu_{1}>\mu_{2}$, $\gamma_{1}\neq\gamma_{2}$, and
$\mathbf{F}=\\{F_{1},F_{2}\\}$ is an EAP, the following properties must be
true almost everywhere:

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\begin{cases}\mu_{1}\gamma_{1}~{}~{}&\text{if}~{}t\in\mathcal{S}(F_{1})/\mathcal{S}(F_{2}),\\\
\mu_{1}\gamma_{1}-\mu_{2}\gamma_{2}~{}~{}&\text{if}~{}t\in\mathcal{S}(F_{1})\cap\mathcal{S}(F_{2}),\end{cases}~{}~{}\text{and,}~{}F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}~{}~{}\text{if}~{}t\in\mathcal{S}(F_{2}),$

where from Lemma 3.1, $\mathcal{S}(F_{1})\cap\mathcal{S}(F_{2})$ has zero
measure if $\mu_{1}\gamma_{1}\leq\mu_{2}\gamma_{2}$.

In the proof of Lemma 3.4 (in A.1), we first observe that both the classes
$i=1,2$ have $C_{\mathbf{F}}^{(i)}(t)=\tau_{\mathbf{F}}^{(i)}(t)-\gamma_{i}t$
constant in $[T_{i,a},T_{1,f}]$, causing
$(\tau_{\mathbf{F}}^{(i)})^{\prime}(t)=\gamma_{i}$. The rest of the proof
relies on relating $(\tau_{\mathbf{F}}^{(i)})^{\prime}(t)$ with the arrival
rates $F_{1}^{\prime}(t)$ and $F_{2}^{\prime}(t)$ of the two classes. Towards
that, we use (3) and leverage the facts that queue 1 has positive waiting time
in $(T_{1,a},T_{1,f})$, (otherwise, if $Q_{1}(t)=0$ at some
$t\in(T_{1,a},T_{1,f})$, every class 1 user arriving in $(t,T_{1,f}]$ is
strictly better off arriving at time $t$) and queue 2 stays engaged in
$[\tau_{1}(T_{2,a}),\tau_{1}(T_{2,f})]$ (by Lemma 3.3).

Lemma 3.5 is about the state of the two queues at support boundaries $T_{1,f}$
and $T_{2,f}$. Proof of Lemma 3.5 is done via a contradiction by showing that
if the specified properties do not hold, a user can reduce her cost by
arriving at a different time.

######  Lemma 3.5.

If $\mu_{1}>\mu_{2}$ and $\gamma_{1}\neq\gamma_{2}$, then under EAP, queue
length at the second queue is zero at $\tau_{1}(T_{2,f})$. If, in addition, we
have $\mu_{1}\gamma_{1}>\mu_{2}\gamma_{2}$, queue length at the first queue
equals zero at $T_{1,f}$.

Proof of necessity of the condition in Lemma 3.1: We prove via contradiction
that
$\mu_{1}\leq\mu_{2}\cdot\max\left\\{1,\frac{\gamma_{2}}{\gamma_{1}}\right\\}$
is necessary for the intervals $[T_{1,a},T_{1,f}]$ and $[T_{2,a},T_{2,f}]$ to
overlap. This forms the other direction of Lemma 3.1. On assuming a
contradiction, we must have
$\mu_{1}>\mu_{2}\cdot\max\left\\{1,\frac{\gamma_{2}}{\gamma_{1}}\right\\}$ and
interiors of $[T_{1,a},T_{1,f}]$, $[T_{2,a},T_{2,f}]$ are disjoint. Now by
Lemma 3.2, union of $[T_{1,a},T_{1,f}]$ and $[T_{2,a},T_{2,f}]$ must be an
interval. This leaves us two possibilities:

  1. 1.

If $T_{1,f}=T_{2,a}$, by Lemma 3.5, queue 1 will be empty at $T_{1,f}$, making
the whole network empty at $T_{1,f}$. As a result, every class 2 user will be
strictly better off arriving at $T_{1,f}$.

  2. 2.

If $T_{2,f}=T_{1,a}$, queue 1 must have a positive waiting time in
$(T_{2,a},T_{2,f}]$ and as a result, class 2 users arrive at queue 2 at rate
$\mu_{1}>\mu_{2}$ in $[0,\tau_{1}(T_{2,f})]$, causing
$Q_{2}(\tau_{1}(T_{2,f}))=(\mu_{1}-\mu_{2})\cdot\tau_{1}(T_{2,f})>0$,
contradicting Lemma 3.5. ∎

Specification of the EAP. Theorem 3.1 specifies the unique EAP of this regime
and we mention below the support boundaries of the unique EAP, which we will
refer to later in Theorem 3.1.

  1. 1.

If $\gamma_{1}\leq\frac{\mu_{2}}{\mu_{1}}\gamma_{2}$, then

$\displaystyle T_{1,a}$
$\displaystyle=-\left(\frac{1}{\gamma_{1}}-1\right)\frac{\Lambda_{1}}{\mu_{1}}-\left(\frac{1}{\gamma_{2}}-1\right)\frac{\Lambda_{2}}{\mu_{2}},~{}T_{1,f}=T_{2,a}=\frac{\Lambda_{1}}{\mu_{1}}-\left(\frac{1}{\gamma_{2}}-1\right)\frac{\Lambda_{2}}{\mu_{2}},~{}\text{and}~{}T_{2,f}=\frac{\Lambda_{1}}{\mu_{1}}+\frac{\Lambda_{2}}{\mu_{2}}.$
(4)

  2. 2.

If $\gamma_{1}>\frac{\mu_{2}}{\mu_{1}}\gamma_{2}$ and
$\Lambda_{1}\geq\min\left\\{\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right),\frac{\mu_{1}}{\mu_{2}}-1\right\\}\cdot\Lambda_{2}$,
then

    1. a)

if $\gamma_{1}<\gamma_{2}$, then

$\displaystyle\vspace{-0.05in}T_{1,a}$
$\displaystyle=-\frac{1-\gamma_{1}}{\mu_{1}\gamma_{1}}\left[\Lambda_{1}+\frac{1-\gamma_{2}}{1-\gamma_{1}}\Lambda_{2}\right],~{}T_{1,f}=\frac{1}{\mu_{1}}\left[\Lambda_{1}+\frac{1-\gamma_{2}}{1-\gamma_{1}}\Lambda_{2}\right],$
$\displaystyle T_{2,a}$
$\displaystyle=\frac{1}{\mu_{1}}\left[\Lambda_{1}-\frac{\mu_{1}-\mu_{2}\gamma_{2}}{\mu_{2}\gamma_{2}}\frac{1-\gamma_{2}}{1-\gamma_{1}}\Lambda_{2}\right],~{}\text{and}~{}T_{2,f}=\frac{1}{\mu_{1}}\left[\Lambda_{1}+\frac{\mu_{1}(\gamma_{2}-\gamma_{1})+\mu_{2}\gamma_{2}(1-\gamma_{2})}{\mu_{2}\gamma_{2}(1-\gamma_{1})}\Lambda_{2}\right].$
(5)

    2. b)

if $\gamma_{1}>\gamma_{2}$, then

$\displaystyle\vspace{-0.05in}T_{1,a}$
$\displaystyle=\frac{\gamma_{1}-\gamma_{2}}{\gamma_{1}}\frac{\Lambda_{2}}{\mu_{1}\gamma_{1}-\mu_{2}\gamma_{2}}-\frac{1-\gamma_{1}}{\gamma_{1}}\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{1}},~{}T_{1,f}=\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{1}},$
$\displaystyle T_{2,a}$
$\displaystyle=-\frac{1-\gamma_{1}}{\gamma_{1}}\frac{\Lambda_{1}}{\mu_{1}}-\left(\frac{\gamma_{1}}{\gamma_{2}}+(1-\gamma_{1})\frac{\mu_{2}}{\mu_{1}}-1\right)\frac{\Lambda_{2}}{\mu_{2}\gamma_{1}},~{}\text{and}~{}T_{2,f}=-\frac{1-\gamma_{1}}{\gamma_{1}}\frac{\Lambda_{1}}{\mu_{1}}+\left(1-(1-\gamma_{1})\frac{\mu_{2}}{\mu_{1}}\right)\frac{\Lambda_{2}}{\mu_{2}\gamma_{1}}.$
(6)

  3. 3.

If $\gamma_{1}>\frac{\mu_{2}}{\mu_{1}}\gamma_{2}$ and
$\Lambda_{1}<\min\left\\{\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right),\frac{\mu_{1}}{\mu_{2}}-1\right\\}\cdot\Lambda_{2}$,
then

$\displaystyle~{}T_{1,a}$
$\displaystyle=\frac{1-\gamma_{2}}{\mu_{1}-\mu_{2}\gamma_{2}}\left[\Lambda_{2}-\frac{(1-\gamma_{1})\mu_{1}}{(1-\gamma_{2})(\mu_{1}\gamma_{1}-\mu_{2}\gamma_{2})}\Lambda_{1}\right],~{}T_{1,f}=\frac{\Lambda_{1}+(1-\gamma_{2})\Lambda_{2}}{\mu_{1}-\mu_{2}\gamma_{2}}$
$\displaystyle T_{2,a}$
$\displaystyle=-\frac{1-\gamma_{2}}{\gamma_{2}}\frac{\Lambda_{2}}{\mu_{2}},~{}\text{and}~{}T_{2,f}=\frac{\Lambda_{2}}{\mu_{2}}.$
(7)

######  Theorem 3.1.

If $\mu_{1}>\mu_{2}$ and $\gamma_{1}\neq\gamma_{2}$, HDS has a unique EAP. The
arrival rates in the EAP are given below along with the support boundaries:

  1. 1.

If $\gamma_{1}\leq\frac{\mu_{2}}{\mu_{1}}\gamma_{2}$,
$F_{1}^{\prime}(t)=\mu_{1}\gamma_{1}$ for $t\in[T_{1,a},T_{1,f}]$ and
$F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}$ for $t\in[T_{2,a},T_{2,f}]$ where
$T_{1,a},T_{1,f},T_{2,a}$ and $T_{2,f}$ are given in (4).

  2. 2.

If $\frac{\mu_{2}}{\mu_{1}}\gamma_{2}<\gamma_{1}<\gamma_{2}$,

    1. 2a.

when
$\Lambda_{1}\geq\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right)\Lambda_{2}$,

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\begin{cases}\mu_{1}\gamma_{1}~{}~{}&\text{if}~{}t\in[T_{1,a},T_{2,a}],\\\
\mu_{1}\gamma_{1}-\mu_{2}\gamma_{2}~{}~{}&\text{if}~{}t\in[T_{2,a},T_{1,f}],\end{cases}~{}~{}\text{and}~{}F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}~{}~{}\text{if}~{}t\in[T_{2,a},T_{2,f}]$

where $T_{1,a},T_{1,f},T_{2,a}$ and $T_{2,f}$ are given in ( ‣ 2.).

    2. 2b.

when
$\Lambda_{1}<\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right)\Lambda_{2}$,
$F_{1}^{\prime}(t)=\mu_{1}\gamma_{1}-\mu_{2}\gamma_{2}$ for
$t\in[T_{1,a},T_{1,f}]$, and $F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}$ for
$t\in[T_{2,a},T_{2,f}]$, where $T_{1,a},T_{1,f},T_{2,a}$ and $T_{2,f}$ are
given in (3.).

  3. 3.

If $\gamma_{2}<\gamma_{1}$,

    1. 3a.

when $\Lambda_{1}\geq\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\Lambda_{2}$,

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\begin{cases}\mu_{1}\gamma_{1}-\mu_{2}\gamma_{2}~{}~{}&\text{if}~{}t\in[T_{1,a},T_{2,f}],\\\
\mu_{1}\gamma_{1}~{}~{}&\text{if}~{}t\in[T_{2,f},T_{1,f}],\end{cases}~{}~{}\text{and}~{}F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}~{}~{}\text{if}~{}t\in[T_{2,a},T_{2,f}]$

where $T_{1,a},T_{1,f},T_{2,a}$ and $T_{2,f}$ are given in ( ‣ 2.).

    2. 3b.

when $\Lambda_{1}<\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\Lambda_{2}$, the EAP
has a closed form same as case 2b.

######  Remark 2.

_Figures 2, 3, 4, and 5 show the illustrative EAPs and resulting queue length
processes, respectively, for cases 1, 2a, 2b and 3a of Theorem 3.1. EAP
structure in case 3b of Theorem 3.1 is similar to case 2b and is illustrated
in Figure 4. The structure of the queue length processes in certain regimes
depend on the support boundaries and may vary accordingly. In the figures
referred above, we have illustrated only one possible structure of the queue
length process. Moreover, we have mentioned the conditions to be satisfied by
the support boundaries for the attainment of that structure in the caption. In
all these figures, red and blue, respectively, represent class 1 and 2
populations, and the black dashed line represents the total mass of the two
populations waiting in queue 1._

######  Remark 3.

_The illustrative EAPs referred to in the previous remark also displays the
threshold behavior stated in Lemma 3.1. Since
$\mu_{1}\leq\mu_{2}\cdot\max\left\\{1,\frac{\gamma_{2}}{\gamma_{1}}\right\\}$
in case 1 of Theorem 3.1, we can see the support intervals of the two classes
to have disjoint interiors in Figure 2. On the other hand, since cases 2 and 3
of Theorem 3.1 have
$\mu_{1}>\mu_{2}\cdot\left\\{1,\frac{\gamma_{2}}{\gamma_{1}}\right\\}$, two
classes arrive over overlapping intervals, as can be seen in Figure 3, 4, and
5._

The following lemma specifies the arrival order of the two classes in EAP and
is necessary for proving Theorem 3.1.

######  Lemma 3.6.

If $\mu_{1}>\mu_{2}$ and $\gamma_{1}\neq\gamma_{2}$, the support boundaries of
EAP of HDS satisfy:

  1. 1.

$T_{1,f}=T_{2,a}$ if $\gamma_{1}\leq\frac{\mu_{2}}{\mu_{1}}\gamma_{2}$,

  2. 2.

$T_{1,f}\leq T_{2,f}$ if
$\frac{\mu_{2}}{\mu_{1}}\gamma_{2}<\gamma_{1}<\gamma_{2}$, and

  3. 3.

$T_{1,a}>T_{2,a}$ if $\gamma_{1}>\gamma_{2}$.

Proof of Lemma 3.6 (in A.1) is done via contradiction by showing that if the
stated property doesn’t hold, a user can improve her cost by arriving at a
different time.

######  Remark 4.

_The arrival orders anticipated by Lemma 3.6 can be observed in the
illustrative EAPs referred earlier. By Lemma 3.6, in case 2
($\gamma_{2}>\gamma_{1}>\frac{\mu_{2}}{\mu_{1}}\gamma_{2}$) of Theorem 3.1,
class 2 population finishes arrival after class 1, as can be observed in
Figure 3 and 4. Similarly for case 3 ($\gamma_{1}>\gamma_{2}$) of Theorem 3.1,
class 1 population starts arrival after class 2, as can be observed in Figure
5 and 4. The class arriving first in case 2 and finishing late in case 3 is
the one having a population size significantly larger among the two classes.
In case 2 (or case 3): 1) when $\Lambda_{1}>c\Lambda_{2}$, class 1 starts
arriving before class 2 (or finishes arriving after class 2), 2) when
$\Lambda_{1}=c\Lambda_{2}$, both classes start arriving from the same time (or
finishes arriving at the same time), 3) when $\Lambda_{1}<c\Lambda_{2}$, class
1 starts arriving after class 2 starts (or finishes arriving before class 2),
where
$c=\min\left\\{\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right),\frac{\mu_{1}}{\mu_{2}}-1\right\\}$
for both case 2 and 3. _

Key steps in the proof of Theorem 3.1 (details in A.1.1): By Lemma 3.2 we only
consider candidates $\mathbf{F}=\\{F_{1},F_{2}\\}$ which are absolutely
continuous with supports of the form $\mathcal{S}(F_{1})=[T_{1,a},T_{1,f}]$,
$\mathcal{S}(F_{2})=[T_{2,a},T_{2,f}]$, such that their union is an interval
and the arrival rates $F_{1}^{\prime}(\cdot),~{}F_{2}^{\prime}(\cdot)$ satisfy
the property in Lemma 3.4. We eliminate candidates not satisfying structural
properties desired of an EAP and will be eventually left with only one
candidate, which is the only candidate that can qualify as an EAP. We then
prove that the only remaining candidate is indeed an EAP. Thus, existence and
uniqueness of EAP follows.

We follow this agenda for the three cases: 1)
$\gamma_{1}\leq\frac{\mu_{2}}{\mu_{1}}\gamma_{2}$, 2)
$\frac{\mu_{2}}{\mu_{1}}\gamma_{2}<\gamma_{1}<\gamma_{2}$, and 3)
$\gamma_{2}<\gamma_{1}$. The final candidate we get in these cases have their
arrival rates and support boundaries same as the joint arrival profiles
mentioned in Theorem 3.1 under the respective cases.

Case 1 $\mathbf{\gamma_{1}\leq\frac{\mu_{2}}{\mu_{1}}\gamma_{2}}$: By Lemma
3.1, every EAP must have $[T_{1,a},T_{1,f}]$ and $[T_{2,a},T_{2,f}]$ disjoint.
Lemma 3.7 helps us substantially narrow our search for an EAP.

######  Lemma 3.7.

Under case 1 $\gamma_{1}\leq\frac{\mu_{2}}{\mu_{1}}\gamma_{2}$, every EAP has
(4) as support boundaries $T_{1,a},T_{1,f},T_{2,a},T_{2,f}$.

Proof Sketch: By Lemma 3.6, we must have $T_{1,f}=T_{2,a}$. By Lemma 3.4,
$F_{1}^{\prime}(t)=\mu_{1}\gamma_{1}$ in $[T_{1,a},T_{1,f}]$ and
$F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}$ in $[T_{1,f},T_{2,f}]$. Therefore,
$T_{1,a},T_{1,f},T_{2,f}$ must satisfy:

$\displaystyle T_{1,f}$
$\displaystyle=T_{1,a}+\frac{\Lambda_{1}}{\mu_{1}\gamma_{1}}~{}\text{and}~{}T_{2,f}=T_{1,f}+\frac{\Lambda_{2}}{\mu_{2}\gamma_{2}}.$
(8)

Now, queue 2 must be empty at $\tau_{1}(T_{2,f})$ (by Lemma 3.5) and must stay
engaged in the image of $[T_{1,f},T_{2,f}]$ under $\tau_{1}(\cdot)$ (by Lemma
3.3), which is $[\tau_{1}(T_{1,f}),\tau_{1}(T_{2,f})]$. Since, the first and
last class 2 users arrive at queue 2, respectively at times
$\tau_{1}(T_{1,f})$ and $\tau_{1}(T_{2,f})$, the previous statement implies,

$\displaystyle\mu_{2}\cdot(\tau_{1}(T_{2,f})-\tau_{1}(T_{1,f}))$
$\displaystyle=\Lambda_{2}$ (9)

For queue 2 to be empty at $\tau_{1}(T_{2,f})$, queue 1 must also be empty at
$T_{2,f}$. Otherwise if queue 1 has a positive waiting time at $T_{2,f}$,
class 2 users will be arriving at queue 2 from queue 1 at rate
$\mu_{1}>\mu_{2}$ in $[\tau_{1}(T_{2,f}-\delta),\tau_{1}(T_{2,f})]$, where
$\delta>0$ picked sufficiently small such that queue 1 has positive waiting
time in $[T_{2,f}-\delta,T_{2,f}]$. By (3),
$\tau_{1}^{\prime}(t)=\frac{F_{2}^{\prime}(t)}{\mu_{1}}=\frac{\mu_{2}\gamma_{2}}{\mu_{1}}>0$
in $[T_{2,f}-\delta,T_{2,f}]$, giving us
$\tau_{1}(T_{2,f})>\tau_{1}(T_{2,f}-\delta)$. As a result,
$Q_{2}(\tau_{1}(T_{2,f}))\geq(\mu_{1}-\mu_{2})\cdot(\tau_{1}(T_{2,f})-\tau_{1}(T_{2,f}-\delta))>0$,
which contradicts Lemma 3.5. With queue 1 empty at $T_{2,f}$, we have
$\tau_{1}(T_{2,f})=T_{2,f}$.

Note that queue 1 must have a positive waiting time in $(T_{1,a},T_{1,f}]$,
otherwise, every class 2 user arriving after $T_{1,f}$ is strictly better off
arriving at the time queue 1 is empty. Applying (3), we have
$\tau_{1}(T_{1,f})-\tau_{1}(T_{1,a})=\frac{F_{1}(T_{1,f})-F_{1}(T_{1,a})}{\mu_{1}}=\frac{\Lambda_{1}}{\mu_{1}}$.
Since the network cannot be empty at time zero, we have $T_{1,a}<0$. This
gives us $\tau_{1}(T_{1,a})=0$ and hence,
$\tau_{1}(T_{1,f})=\frac{\Lambda_{1}}{\mu_{1}}$. Putting
$\tau_{1}(T_{2,f})=T_{2,f}$ and
$\tau_{1}(T_{1,f})=\frac{\Lambda_{1}}{\mu_{1}}$ in (9), we get
$T_{2,f}=\frac{\Lambda_{1}}{\mu_{1}}+\frac{\Lambda_{2}}{\mu_{2}}$. Using this
in (8) and by the fact $T_{2,a}=T_{1,f}$, we get the values of
$T_{1,a},T_{1,f},T_{2,a},T_{2,f}$ mentioned in (4). ∎

The only candidate having arrival rates satisfying Lemma 3.4 and support
boundaries from Lemma 3.7 is the joint arrival profile under case 1 of Theorem
3.1. Proving that this unique remaining candidate is an EAP requires analyzing
the behavior of the two queues induced by this candidate.s Details of it are
in A.1.

Figure 2: Illustrative EAP (left) and resulting queue length process (right)
of HDS with $\mu_{1}>\mu_{2}$ under case 1:
$\gamma_{1}\leq\frac{\mu_{2}}{\mu_{1}}\cdot\gamma_{2}$ and the condition
$T_{1,f}>0$ in (4). $T\in(T_{1,f},T_{2,f})$ is the time at which queue 1
empties after time zero. In queue 1, since class 1 users stop arriving after
$T_{1,f}$, class 1 waiting mass decreases faster in
$[T_{1,f},\tau_{1}(T_{1,f})]$ than in $[0,T_{1,f}]$.

Case 2 $\frac{\mu_{2}}{\mu_{1}}\cdot\gamma_{2}<\gamma_{1}<\gamma_{2}$: By
Lemma 3.1, $[T_{1,a},T_{1,f}]$ and $[T_{2,a},T_{2,f}]$ must overlap, and by
Lemma 3.6, class 2 shouldn’t finish arriving before class 1, i.e.,
$T_{1,f}\leq T_{2,f}$. Therefore, every EAP must have its support boundaries
$T_{1,a},T_{1,f},T_{2,a},T_{2,f}$ ordered by one of the following two ways:

  1. Type I:

$T_{1,a}\leq T_{2,a}<T_{1,f}\leq T_{2,f}$ with $T_{1,a}<0$, and,

  2. Type II:

$T_{2,a}<T_{1,a}<T_{1,f}\leq T_{2,f}$ with $T_{2,a}<0$.

Note that, we need $\min\\{T_{1,a},T_{2,a}\\}<0$, otherwise, any user will be
strictly better off arriving at time zero when the network is empty. The
following lemma now specifies the necessary and sufficient conditions for
existence of an EAP under these two types. Existence of unique EAP in case 2
of Theorem 3.1 follows trivially from this lemma.

######  Lemma 3.8.

If $\gamma_{2}>\gamma_{1}>\frac{\mu_{2}}{\mu_{1}}\gamma_{2}$, the following
statements are true:

  * •

There exists an EAP under Type I if and only if
$\Lambda_{1}\geq\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right)\Lambda_{2}$
and if it exists, it will be unique with a closed form same as the joint
arrival profile under case 2a of Theorem 3.1.

  * •

There exists an EAP under Type II if and only if
$\Lambda_{1}<\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right)\Lambda_{2}$
and if it exists, it will be unique with a closed form same as the joint
arrival profile under case 2b of Theorem 3.1.

Proof Sketch of Lemma 3.8: Identifying the support boundaries: For every EAP
under Type I, we identify the following system of equations to be satisfied by
its support boundaries $T_{1,a},T_{1,f},T_{2,a},T_{2,f}$:
1) By Lemma 3.4, $F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}$ in $[T_{2,a},T_{2,f}]$,
giving us: $T_{2,f}=T_{2,a}+\frac{\Lambda_{2}}{\mu_{2}\gamma_{2}}$.

2) Since $T_{1,a}<0$, queue 1 starts serving at time zero and must have
positive waiting time in $(0,T_{1,f})$. By Lemma 3.5, queue 1 must be empty at
time $T_{1,f}$. Therefore, $F_{1}(T_{1,f})+F_{2}(T_{1,f})=\mu_{1}T_{1,f}$. Now
$F_{1}(T_{1,f})=\Lambda_{1}$ and
$F_{2}(T_{1,f})=\mu_{2}\gamma_{2}(T_{1,f}-T_{2,a})$ (by Lemma 3.4). Plugging
this in, we get:
$\Lambda_{1}+\mu_{2}\gamma_{2}(T_{1,f}-T_{2,a})=\mu_{1}T_{1,f}$.

3) By definition of EAP,
$C_{\mathbf{F}}^{(1)}(T_{1,a})=C_{\mathbf{F}}^{(1)}(T_{1,f})$. Queue 1 empties
at $T_{1,f}$ (by Lemma 3.5), giving us
$C_{\mathbf{F}}^{(1)}(T_{1,f})=(1-\gamma_{1})T_{1,f}$. The first class 1 user
arriving at time $T_{1,a}$ gets served by queue 1 at time zero and waits for
$-T_{1,a}$ time, giving us $C_{\mathbf{F}}^{(1)}(T_{1,a})=-\gamma_{1}T_{1,a}$.
Equating these two costs, we get:
$T_{1,a}=-\left(\frac{1}{\gamma_{1}}-1\right)T_{1,f}$.

4) By Lemma 3.3, queue 2 stays engaged in
$[\tau_{1}(T_{2,a}),\tau_{1}(T_{2,f})]$ and by Lemma 3.5, queue 2 empties at
$\tau_{1}(T_{2,f})$. In this way, queue 2 serves the class 2 population in
$[\tau_{1}(T_{2,a}),\tau_{1}(T_{2,f})]$, giving us
$\mu_{2}\cdot(\tau_{1}(T_{2,f})-\tau_{1}(T_{2,a}))=\Lambda_{2}$. Queue 1
empties at $T_{1,f}$ (by Lemma 3.5) and after $T_{1,f}$, since class 2 users
arrive at rate $\mu_{2}\gamma_{2}<\mu_{1}\gamma_{1}<\mu_{1}$, queue 1 remains
empty at $T_{2,f}$, giving us $\tau_{1}(T_{2,f})=T_{2,f}$. Since queue 1 has
positive waiting time in $(T_{1,a},T_{2,a}]$, we have
$\tau_{1}(T_{2,a})-\tau_{1}(T_{1,a})=\frac{F_{1}(T_{2,a})-F_{1}(T_{1,a})}{\mu_{1}}=\gamma_{1}(T_{2,a}-T_{1,a})$
(by (3) and Lemma 3.4), which upon putting $\tau_{1}(T_{1,a})=0$ gives us
$\tau_{1}(T_{2,a})=\gamma_{1}(T_{2,a}-T_{1,a})$. Placing the expressions
obtained for $\tau_{1}(T_{2,a})$ and $\tau_{1}(T_{2,f})$ into
$\mu_{2}(\tau_{1}(T_{2,f})-\tau_{1}(T_{2,a}))=\Lambda_{2}$, we get,
$\mu_{2}(T_{2,f}-\gamma_{1}(T_{2,a}-T_{1,a}))=\Lambda_{2}$.

Getting the necessary condition: Solution of the identified system of
equations is ( ‣ 2.) and therefore, every EAP under Type I must have ( ‣ 2.)
as support boundaries. Now ( ‣ 2.) must be ordered by $T_{1,a}\leq
T_{2,a}<T_{1,f}\leq T_{2,f}$ to represent an EAP of Type I. Note that ( ‣ 2.)
satisfies
$T_{2,a}-T_{1,a}=\frac{1}{\mu_{1}\gamma_{1}}\left[\Lambda_{1}-\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right)\Lambda_{2}\right]$.
As a result, for $T_{2,a}\geq T_{1,a}$, we need
$\Lambda_{1}\geq\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right)\Lambda_{2}$
and therefore this is a necessary condition for existence of an EAP under Type
I.

Proving sufficiency of the obtained necessary condition: Now, if
$\Lambda_{1}\geq\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right)\Lambda_{2}$,
it is easy to verify that ( ‣ 2.) satisfies $T_{1,a}\leq T_{2,a}<T_{1,f}\leq
T_{2,f}$. Therefore, with the necessary condition satisfied and upon plugging
in arrival rates using Lemma 3.4, we get a candidate having arrival rates and
support boundaries same as the joint arrival profile mentioned under case 2a
of Theorem 3.1. This candidate satisfies
$F_{1}(T_{1,f})=\Lambda_{1},~{}F_{2}(T_{2,f})=\Lambda_{2}$ and will be the
only candidate under Type I to qualify as an EAP. Proving that this candidate
is an EAP requires analyzing the behavior of the two queues. Details of this
argument is in A.1. Therefore, it follows that the obtained necessary
condition is also sufficient for existence of an EAP under Type I, and once it
is satisfied, there is a unique EAP under Type I which has a closed form same
as the one mentioned under case 2a of Theorem 3.1. Thus the first statement of
the lemma follows.

The second statement is proved via an argument similar to the one used for
proving the first statement via identifying a system of equations satisfied by
the support boundaries and getting the necessary condition by imposing
$T_{2,a}<T_{1,a}$ on the solution to that system. Details of the argument in
A.1.1. ∎

Case 3: $\gamma_{1}>\gamma_{2}$: By Lemma 3.1, $[T_{1,a},T_{1,f}]$ and
$[T_{2,a},T_{2,f}]$ must overlap, and by Lemma 3.6, $T_{1,a}>T_{2,a}$.
Therefore, the support boundaries of any EAP must be ordered by the following
two orderings:

  1. Type I:

$T_{2,a}<T_{1,a}<T_{2,f}\leq T_{1,f}$ , and

  2. Type II:

$T_{2,a}<T_{1,a}<T_{1,f}<T_{2,f}$.

For both the above types, every EAP must have $T_{2,a}<0$. The following lemma
specifies the necessary and sufficient condition for existence of an EAP under
the two types mentioned above. Existence of unique EAP under case 3 of Theorem
3.1 follows trivially from this lemma.

######  Lemma 3.9.

If $\gamma_{1}>\gamma_{2}$, the following statements are true:

  1. 1.

There exists an EAP under Type I if and only if
$\Lambda_{1}\geq\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\Lambda_{2}$ and if it
exists, it has a closed form same as the one mentioned under case 3a of
Theorem 3.1.

  2. 2.

There exists an EAP under Type II if and only if
$\Lambda_{1}<\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\Lambda_{2}$ and if it
exists, it has a closed form same as the one mentioned under case 3b of
Theorem 3.1.

Proof of the above lemma follows an argument similar to the proof of Lemma 3.8
by identifying a system of linear equations to be satisfied by the support
boundaries of any EAP under the two types. Details are in A.1.1. ∎

The proof of the main results in Sections 3.2, 4.1 and 4.2 will follow a
similar sequence of arguments as used in the proof of Theorem 3.1, through
elimination of candidates not satisfying structural properties of every EAP in
that regime.

Figure 3: Illustrative EAP (left) and resulting queue length process (right)
of HDS with $\mu_{1}>\mu_{2}$ under case 2a of Theorem 3.1 with the assumption
$T_{2,a}<0$ in ( ‣ 2.). Queue 1 divides its capacity between the two classes
from $\tau_{1}(T_{2,a})$ proportionally to their arrival rate. As a result,
queue 1 serves class 1 users at a slower rate in $[\tau_{1}(T_{2,a}),T_{1,f}]$
than in $[0,\tau_{1}(T_{2,a})]$, causing class 1 mass in queue 1 to decrease
at a slower rate in the former interval than in the latter one. Figure 4:
Illustrative EAP (left) of HDS with $\mu_{1}>\mu_{2}$ under case 2b and 3b of
Theorem 3.1. The resulting queue length process (right) is for case 2b with
the assumption $T_{2,a}<0$ in (3.). Queue 1 divides its capacity between the
two classes from $\tau_{1}(T_{1,a})$ proportionally to their service rates. As
a result, queue 1 serves class 2 users at a lesser rate in
$[\tau_{1}(T_{1,a}),T_{1,f}]$ than in $[0,\tau_{1}(T_{1,a})]$, causing class 2
waiting mass to decrease at a lesser rate in the former interval than in the
latter one. In queue 2, waiting mass increases in
$[\tau_{1}(T_{1,a}),T_{1,f}]$ because class 2 arrival rate to queue 2 is
$\mu_{2}\gamma_{1}/\gamma_{2}>\mu_{2}$. However the waiting mass increases in
$[\tau_{1}(T_{1,a}),T_{1,f}]$ at a rate slower than in
$[0,\tau_{1}(T_{1,a})]$, since the arrival rate in the formal interval is
$\mu_{2}\gamma_{2}/\gamma_{1}<\mu_{1}=$ arrival rate in the latter interval.
For case 3b of Theorem 3.1, with the assumption $T_{1,a}<0$ on (3.), queue 1
length process has the same structure. Queue 2 length process of case 3b is
also same as case 2b, except for one region: queue 2 length decreases in
$[\tau_{1}(T_{1,a}),T_{1,f}]$, since class 2 arrival rate to queue 2 is
$\mu_{2}\gamma_{2}/\gamma_{1}<\mu_{2}$ in case 3b. Figure 5: Illustrative EAP
(left) and resulting queue length process (right) of HDS with
$\mu_{1}>\mu_{2}$ under case 3a of Theorem 3.1 with the assumption $T_{1,a}<0$
and
$\tau_{1}(T_{1,a})=\frac{\mu_{2}\gamma_{2}}{\mu_{1}}(T_{1,a}-T_{2,a})<T_{2,f}$
in ( ‣ 2.). In $[\tau_{1}(T_{1,a}),T_{1,f}]$, queue 1 divides its capacity
between the two classes proportionally to their arrival rates. As a result,
class 2 mass in queue 1 decreases at a lesser rate in
$[\tau_{1}(T_{1,a}),T_{2,f}]$ than in $[0,\tau_{1}(T_{1,a})]$. After
$T_{2,f}$, as class 2 users stop arriving, the class 2 mass in queue 1
decreases to zero at a higher rate in $[T_{2,f},\tau_{1}(T_{2,f})]$ than in
$[\tau_{1}(T_{1,a}),T_{2,f}]$. Class 1 mass in queue 1 initially decreases in
$[\tau_{1}(T_{1,a}),T_{2,f}]$. Since class 1 users increase their arrival rate
after $T_{2,f}$, slope of the red line increases and the class 1 mass in queue
1 can even increase in $[T_{2,f},\tau_{1}(T_{2,f})]$ if
$\mu_{1}\gamma_{1}>\mu_{1}-\mu_{2}\gamma_{2}/\gamma_{1}$. After
$\tau_{1}(T_{2,f})$, queue 1 allocates the entire capacity to class 1 and the
class 1 mass in queue 1 decreases to zero in $[\tau_{1}(T_{2,f}),T_{1,f}]$.

###  3.2 Equal Preferences: $\gamma_{1}=\gamma_{2}=\gamma$

Structural properties of any EAP. We first identify the structural properties
of any EAP in this regime and later we exploit them to refine our search of
EAP. By Lemma 3.2, we can restrict our search to joint arrival profiles having
supports satisfying $\mathcal{S}(F_{1})=[T_{1,a},T_{1,f}]$ and
$\mathcal{S}(F_{1})\cup\mathcal{S}(F_{2})=[T_{a},T_{f}]$ for some
$T_{f}>T_{a}$ and $T_{1,f}>T_{1,a}$. Lemma 3.10 states the arrival rates of
the two classes in EAP and is proved (in A.2) via an argument similar to the
one used for proving Lemma 3.4. Lemma 3.11 is proved via contradiction, by
showing that, if the stated condition doesn’t hold, users of one of the
classes can improve by arriving at a different time.

######  Lemma 3.10 (Rate of arrival).

If $\mu_{1}>\mu_{2}$ and $\gamma_{1}=\gamma_{2}=\gamma$, the following
properties must be true almost everywhere for every EAP
$\mathbf{F}=\\{F_{1},F_{2}\\}$,

$\displaystyle F_{1}^{\prime}(t)+F_{2}^{\prime}(t)$
$\displaystyle=\mu_{1}\gamma~{}~{}~{}\text{if $t\in\mathcal{S}(F_{1})$, and,}$
$\displaystyle F_{2}^{\prime}(t)$
$\displaystyle\leq\mu_{2}\gamma~{}~{}~{}\text{if $t\in\mathcal{S}(F_{2})$,
with equality when $Q_{2}(\tau_{1}(t))>0$}.$

######  Lemma 3.11.

If $\mu_{1}>\mu_{2}$ and $\gamma_{1}=\gamma_{2}=\gamma$, in the EAP,

  1. 1.

If $\mathcal{S}(F_{2})$ has a gap $(t,t+\delta]$ at $t\in\mathcal{S}(F_{2})$
for some $\delta>0$ sufficiently small, queue 2 must be empty at
$\tau_{1}(t)$.

  2. 2.

Queue 1 must be empty time at $T_{1,f}$.

Specification of the EAP.

######  Theorem 3.2.

If $\mu_{1}>\mu_{2}$ and $\gamma_{1}=\gamma_{2}=\gamma$, EAP of HDS exists
and:

  1. 1.

If $\Lambda_{1}<\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\Lambda_{2}$, the EAP is
unique and its arrival rates and support boundaries are:

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=(\mu_{1}-\mu_{2})\gamma~{}\text{for}~{}t\in[T_{1,a},T_{1,f}]~{}\text{and},~{}F_{2}^{\prime}(t)=\mu_{2}\gamma~{}\text{for}~{}t\in[T_{a},T_{f}],$
$\displaystyle\text{where},~{}T_{1,a}$
$\displaystyle=\frac{1-\gamma}{\mu_{1}-\mu_{2}\gamma}\left[\Lambda_{2}-\frac{\mu_{1}}{(\mu_{1}-\mu_{2})\gamma}\Lambda_{1}\right],~{}T_{1,f}=\frac{\Lambda_{1}+(1-\gamma)\Lambda_{2}}{\mu_{1}-\mu_{2}\gamma},~{}T_{a}=-\frac{1-\gamma}{\gamma}\frac{\Lambda_{2}}{\mu_{2}},~{}\text{and}~{}T_{f}=\frac{\Lambda_{2}}{\mu_{2}}.$

  2. 2.

If $\Lambda_{1}\geq\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\Lambda_{2}$, the set
of EAPs is the convex set of joint arrival profiles
$\mathbf{F}=\\{F_{1},F_{2}\\}$ satisfying: 1)
$\mathcal{S}(F_{1})=[T_{a},T_{f}]$,
$\mathcal{S}(F_{2})\subseteq[T_{a},T_{f}]$, for $i=1,2$
$F_{i}(T_{f})=\Lambda_{i}$, 2)
$F_{1}^{\prime}(t)+F_{2}^{\prime}(t)=\mu_{1}\gamma$, and 3)
$F_{2}^{\prime}(t)\leq\mu_{2}\gamma$ for every $t\in[T_{a},T_{f}]$, where
$T_{a}=-\left(\frac{1}{\gamma}-1\right)\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{1}}$
and $T_{f}=\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{1}}$.

We only provide the key steps of the proof of Theorem 3.2 below. The details
are given in A.2.1. Following two supporting lemmas are necessary for proving
Theorem 3.2.

######  Lemma 3.12.

In every EAP, the cost of the class 2 users remains constant over
$[T_{a},T_{f}]$.

######  Lemma 3.13.

In every EAP, if $t\in\mathcal{S}(F_{1})\cap\mathcal{S}(F_{2})$, then class 2
users will arrive at queue 2 at a maximum rate of $\mu_{2}$ at time
$\tau_{1}(t)$.

Proofs of Lemma 3.12 and Lemma 3.13 are in A.2. Lemma 3.12 is proved via
exploiting Lemma 3.11 and the fact that the two classes have equal cost
preferences. Proof of Lemma 3.13 is based on the observation that
$A_{2}(\tau_{1}(t))=F_{2}(t)$. As a result, at time $\tau_{1}(t)$, class 2
users arrive at queue 2 at rate
$A_{2}^{\prime}(\tau_{1}(t))=\frac{F_{2}^{\prime}(t)}{\tau_{1}^{\prime}(t)}$,
assuming that the derivatives exist. Following this, we use Lemma 3.10 and (3)
to upper bound the rate of arrival.

Key steps of proof of Theorem 3.2: By Lemma 3.2, we consider candidates
$\mathbf{F}=\\{F_{1},F_{2}\\}$ which are absolutely continuous with
$\mathcal{S}(F_{1})=[T_{1,a},T_{1,f}],~{}\mathcal{S}(F_{1})\cup\mathcal{S}(F_{2})=[T_{a},T_{f}]$
and have arrival rates $F_{1}^{\prime}(\cdot),~{}F_{2}^{\prime}(\cdot)$ given
by Lemma 3.10. We eliminate candidates which do not satisfy the structural
properties of any EAP and narrow our search of an EAP to a smaller set of
candidates. We follow this agenda separately over two subsets of candidates
with: 1) $T_{f}>T_{1,f}$ and 2) $T_{f}=T_{1,f}$. Lemma 3.14 and 3.15 provides
the necessary and sufficient condition for existence of EAPs of the mentioned
two types. The statement of Theorem 3.2 follows from these two lemmas.

######  Lemma 3.14.

If $\gamma_{1}=\gamma_{2}=\gamma$, there exists an EAP with $T_{f}>T_{1,f}$ if
and only if $\Lambda_{1}<\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\Lambda_{2}$,
and if it exists, it will be unique with a closed form same as the joint
arrival profile mentioned under case 1 of Theorem 3.2.

######  Lemma 3.15.

If $\gamma_{1}=\gamma_{2}=\gamma$, there exists an EAP with $T_{f}=T_{1,f}$ if
and only if
$\Lambda_{1}\geq\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\Lambda_{2}$, and if it
exists, the set of all EAPs with $T_{1,f}=T_{f}$ is the set of joint arrival
profiles mentioned under case 2 of Theorem 3.2.

Below we sketch the proof of Lemma 3.14 and 3.15. The remaining details are
presented in A.2.1.

Proof sketch of Lemma 3.14: Identifying the support boundaries: First we
identify the support boundaries $T_{a},T_{f}$ of any EAP with $T_{f}>T_{1,f}$:

  1. 1)

Exploiting Lemma 3.13 and 3.11, we argue that queue 2 has a positive waiting
time in $(0,T_{f})$ and empties at $T_{f}$. As a result, queue 2 serves the
whole class 2 population in $(0,T_{f})$, giving us
$T_{f}=\frac{\Lambda_{2}}{\mu_{2}}$.

  2. 2)

Using Lemma 3.12 we have,
$C_{\mathbf{F}}^{(2)}(T_{a})=C_{\mathbf{F}}^{(2)}(T_{f})$. The class 2 user
arriving at $T_{a}$ gets served at time zero causing
$C_{\mathbf{F}}^{(2)}(T_{a})=-\gamma T_{a}$. Since the network is empty at
$T_{f}$, $C_{\mathbf{F}}^{(2)}(T_{f})=(1-\gamma)T_{f}$. Therefore,
$C_{\mathbf{F}}^{(2)}(T_{a})=C_{\mathbf{F}}^{(2)}(T_{f})$ implies
$T_{a}=-\left(\frac{1}{\gamma}-1\right)T_{f}=-\left(\frac{1}{\gamma}-1\right)\frac{\Lambda_{2}}{\mu_{2}}$.

  3. 3)

The class 2 population of mass $\Lambda_{2}$ has to arrive in the interval
$\left[T_{a},T_{f}\right]$ of length $\frac{\Lambda_{2}}{\mu_{2}\gamma_{2}}$
at maximum rate of $\mu_{2}\gamma_{2}$ (by Lemma 3.10). This leaves us with
only one possible arrival rate for class 2 users:
$F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}$ in $[T_{a},T_{f}]$. As a result, by
Lemma 3.10, we must have $F_{1}^{\prime}(t)=(\mu_{1}-\mu_{2})\gamma$ in
$[T_{1,a},T_{1,f}]$, giving us
$T_{1,f}=T_{1,a}+\frac{\Lambda_{1}}{(\mu_{1}-\mu_{2})\gamma}$.

  4. 4)

Since $T_{a}<0$, queue 1 starts serving from time zero and has positive
waiting time in $[0,T_{1,f})$. By Lemma 3.11, queue 1 empties at $T_{1,f}$.
Therefore, $\mu_{1}T_{1,f}=F_{1}(T_{1,f})+F_{2}(T_{1,f})=\Lambda_{1}+\newline
\mu_{2}\gamma\cdot(T_{1,f}-T_{a})$.

Getting the necessary condition: Solving the above system of equations, we get
$T_{a}=-\left(\frac{1}{\gamma}-1\right)\frac{\Lambda_{2}}{\mu_{2}}$,
$T_{f}=\frac{\Lambda_{2}}{\mu_{2}}$,
$T_{1,a}=\frac{1-\gamma}{\mu_{1}-\mu_{2}\gamma}\left[\Lambda_{2}-\frac{\mu_{1}}{(\mu_{1}-\mu_{2})\gamma}\Lambda_{1}\right]$,
$T_{1,f}=\frac{\Lambda_{1}+(1-\gamma)\Lambda_{2}}{\mu_{1}-\mu_{2}\gamma}$ and
as a result, every EAP with $T_{f}>T_{1,f}$ has $T_{a},T_{f},T_{1,a},T_{1,f}$
same as the ones we identified. For $T_{f}>T_{1,f}$, we need
$\Lambda_{1}<\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\Lambda_{2}$ and therefore,
this is a necessary condition for existence of an EAP with $T_{f}>T_{1,f}$.

Identifying the unique EAP: If the necessary condition
$\Lambda_{1}<\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\Lambda_{2}$ is satisfied,
it is easy to verify that, the support boundaries obtained above follow the
ordering $T_{a}<T_{1,a}<T_{1,f}<T_{f}$. With this ordering satisfied, the only
candidate with $T_{f}>T_{1,f}$, which qualifies to be an EAP is:
$F_{1}^{\prime}(t)=(\mu_{1}-\mu_{2})\gamma$ in $[T_{1,a},T_{1,f}]$ and
$F_{2}^{\prime}(t)=\mu_{2}\gamma$ in $[T_{a},T_{f}]$, with
$T_{a},T_{f},T_{1,a},T_{1,f}$ same as we identified before. Moreover, the
candidate obtained is same as the joint arrival profile under case 1 of
Theorem 3.2.

Proving sufficiency of the obtained necessary condition: Another interesting
observation is, if
$\Lambda_{1}<\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\Lambda_{2}$, the obtained
candidate with $T_{f}>T_{1,f}$ is same as the EAPs in cases 2b and 3b of
Theorem 3.1, respectively, upon taking limits
$\gamma_{1}=\gamma,~{}\gamma_{2}\to\gamma+$ and
$\gamma_{2}=\gamma,~{}\gamma_{1}\to\gamma+$. Proving that this candidate is an
EAP follows by the argument used for proving the unique Type II candidate in
Lemma 3.8 is an EAP (in A.1.1), except replacing $T_{2,a},T_{2,f}$ with
$T_{a},T_{f}$ and taking $\gamma_{1}=\gamma_{2}=\gamma$. Therefore, the
statement of Lemma 3.14 stands proved. ∎

Proof sketch of Lemma 3.15: Identifying $\mathbf{T_{a}}$: Since
$[0,T_{f}]\subseteq\mathcal{S}(F_{1})$, queue 1 must have a positive waiting
time in $[0,T_{f})$. By Lemma 3.11, queue 1 empties at time $T_{f}$. Therefore
we get $\mu_{1}T_{f}=F_{1}(T_{f})+F_{2}(T_{f})=\Lambda_{1}+\Lambda_{2}$
implying $T_{f}=\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{1}}$.

Identifying $\mathbf{T_{f}}$: By Lemma 3.12, we have
$C_{\mathbf{F}}^{(2)}(T_{a})=C_{\mathbf{F}}^{(2)}(T_{f})$. Using the argument
used in the proof sketch of Lemma 3.14 for finding $T_{a}$, we get
$T_{a}=-\left(\frac{1}{\gamma}-1\right)T_{f}=-\left(\frac{1}{\gamma}-1\right)\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{1}}$.

Getting the necessary condition: By Lemma 3.10, all class 2 users arrive in
$[T_{a},T_{f}]$ at a maximum rate of $\mu_{2}\gamma$. Therefore for existence
of an EAP with $T_{f}=T_{1,f}$, we need the necessary condition
$\mu_{2}\gamma\cdot(T_{f}-T_{a})\geq\Lambda_{2}$, which after some
manipulation gives us
$\Lambda_{1}\geq\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\Lambda_{2}$.

Identifying the set of EAPs: By Lemma 3.10, $\mu_{1}\gamma$ is the maximum
rate at which the entire population of mass $\Lambda_{1}+\Lambda_{2}$ can
arrive within the time interval $[T_{a},T_{f}]$ of length
$\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{1}\gamma}$. Therefore, we must have
$F_{1}^{\prime}(t)+F_{2}^{\prime}(t)=\mu_{1}\gamma$ in $[T_{a},T_{f}]$. Also
by Lemma 3.10, we have $F_{1}^{\prime}(t)+F_{2}^{\prime}(t)=\mu_{1}\gamma$
only in $\mathcal{S}(F_{1})=[T_{1,a},T_{1,f}]\subseteq[T_{a},T_{f}]$, which
implies $T_{1,a}=T_{a}$. By Lemma 3.13, class 2 users arrive at queue 2 from
queue 1 in $[0,T_{f}]$ at a maximum rate of $\mu_{2}$. Hence queue 2 stays
empty and as a result, by Lemma 3.10, $F_{2}^{\prime}(t)\leq\mu_{2}\gamma$ for
every $t\in[T_{a},T_{f}]$. Therefore, our reduced set of candidates with
$T_{f}=T_{1,f}$ will be the set of all joint arrival profiles
$\mathbf{F}=\\{F_{1},F_{2}\\}$ satisfying: 1)
$\mathcal{S}(F_{1})=[T_{a},T_{f}]$ and
$\mathcal{S}(F_{2})\subseteq[T_{a},T_{f}]$, for $i=1,2$
$F_{i}(T_{f})=\Lambda_{i}$, 2)
$F_{1}^{\prime}(t)+F_{2}^{\prime}(t)=\mu_{1}\gamma$, and 3)
$F_{2}^{\prime}(t)\leq\mu_{2}\gamma$ for every $t\in[T_{a},T_{f}]$ where
$T_{a}=-\frac{1-\gamma}{\gamma}\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{1}}$ and
$T_{f}=\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{1}}$, which is exactly the set
mentioned under the case 2 of Theorem 3.2.

Proving sufficiency of the obtained necessary condition: It is easy to verify
that, if the necessary condition
$\Lambda_{1}\geq\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\Lambda_{2}$ holds, the
set of candidates with $T_{f}=T_{1,f}$ mentioned earlier is non-empty. Two
elements of the set are the limits of the EAPs in cases 2a and 3a of Theorem
3.1, respectively, when $\gamma_{1}=\gamma,~{}\gamma_{2}\to\gamma+$ and
$\gamma_{2}=\gamma,~{}\gamma_{1}\to\gamma+$. After this, we prove that, if
$\Lambda_{1}\geq\left(\frac{\mu_{1}}{\mu_{2}}-1\right)\cdot\Lambda_{2}$, every
joint arrival profile $\mathbf{F}=\\{F_{1},F_{2}\\}$ in the obtained set of
candidates is an EAP. This step requires exploiting Lemma 3.12 and the fact
that queue 2 stays empty when users are arriving by such a candidate and the
details of it are in A.2.1. Hence, the statement of Lemma 3.15 stands proved.
∎

##  4 Heterogeneous Arrival System (HAS)

In this section, we consider the two groups arrive at different queues and
depart from the same queue as illustrated in Table 1. Namely, the $i$-th group
arrive at $i$-th queue and both the groups depart from the 2nd queue. We
consider the case $\gamma_{1}\neq\gamma_{2}$ and $\gamma_{1}=\gamma_{2}$
separately, since the later displays different behaviors.

###  4.1 Unequal Preferences $\gamma_{1}\neq\gamma_{2}$

As for HDS, here too we narrow down our search for EAP by exploiting its
structural properties. The detailed account of these structural properties as
well as detailed proofs of results in this section are given in B.1. The main
results in this section are proved by arguments similar to those used for
proving Theorem 3.1 for HDS, except that we now exploit a different set of
structural properties and the no. of different regimes is significantly larger
and diverse for HAS. In this section, we state the key results and after
Theorem 4.2 in Remark 7, we discuss two interesting cases: 1) where the EAP
corresponds to arrivals in a stream coming in disjoint intervals and 2) where
all the arrivals for class 2 arrive before time zero.

The following lemma identifies an important threshold property of an EAP.
Proof of Lemma 4.1 is in B.1 and follows a sequence of arguments similar to
the one used for proving Lemma 3.1.

######  Lemma 4.1 (Threshold Behavior).

If $\gamma_{1}\neq\gamma_{2}$, in EAP, queue 2 serves the two classes over
disjoint sets of time if and only if $\mu_{1}\geq\mu_{2}\gamma_{2}$.

Proof sketch: Proof of Lemma 4.1 is similar to that of Lemma 3.1. First we
argue via a contradiction that if $\mu_{1}\geq\mu_{2}\gamma_{2}$, then queue 2
cannot serve the two classes together in an EAP. If queue 2 is serving the two
classes together, we argue that, queue 1 must stay engaged in a neighbourhood
of that time for class 1 to be iso cost (by Lemma B.1 in B.1). As a result,
class 1 users arrive from queue 1 to 2 at rate $\mu_{1}$. For class 2 have
constant cost in that neighbourhood, we argue that, users of the two classes
arrive at queue 2 at a combined rate of $\mu_{2}\gamma_{2}$. Since queue 2
serves a positive mass of both the classes together, the combined arrival rate
must be strictly larger than the arrival rate of class 1 to queue 2, implying
$\mu_{2}\gamma_{2}>\mu_{1}$ and contradicting $\mu_{1}\geq\mu_{2}\gamma_{2}$.
The other direction is proved via contradiction by exploiting the structures
of $\mathcal{S}(F_{1}),~{}\mathcal{S}(F_{2})$ in an EAP and showing that, if
$\mu_{1}<\mu_{2}\gamma_{2}$ and queue 2 is serving the two classes over
disjoint sets of times, we can find a user who can decrease her cost by
arriving at a different time. ∎

Specification of the EAP. The two regimes $\mu_{1}<\mu_{2}\gamma_{2}$ and
$\mu_{1}\geq\mu_{2}\gamma_{2}$ exhibit substantially different EAP structures,
owing to the threshold behavior given by Lemma 4.1. For conciseness, we
specify the unique EAP in these two regimes separately in Theorem 4.1 (for
$\mu_{1}<\mu_{2}\gamma_{2}$) and 4.2 (for $\mu_{1}\geq\mu_{2}\gamma_{2}$).
Proofs of these theorems (in B.1) have a structure similar to the proof of
Theorem 3.1.

For the two classes $i=1,2$, we define the quantities
$T_{i,a}=\inf\mathcal{S}(F_{i})$ and $T_{i,f}=\sup\mathcal{S}(F_{i})$. In an
EAP, both the sets $\mathcal{S}(F_{1}),~{}\mathcal{S}(F_{2})$ are compact and
therefore $T_{1,a},T_{1,f},T_{2,a},T_{2,f}$ are all finite.

Regime I $\mu_{1}<\mu_{2}\gamma_{2}$. We mention below the support boundaries
of the unique EAP, which we will refer later in Theorem 4.1:

  1. 1.

If $\mu_{1}<\mu_{2}\gamma_{2}$ and
$\Lambda_{1}\geq\max\left\\{\frac{1-\gamma_{2}}{1-\gamma_{1}},1\right\\}\cdot\frac{\mu_{1}}{\mu_{2}-\mu_{1}}\Lambda_{2}$,
then

$\displaystyle T_{1,a}$
$\displaystyle=-\frac{1-\gamma_{1}}{\gamma_{1}}\frac{\Lambda_{1}}{\mu_{1}}+\frac{1-\gamma_{2}}{\gamma_{1}}\frac{\Lambda_{2}}{\mu_{2}-\mu_{1}},~{}T_{1,f}=\frac{\Lambda_{1}}{\mu_{1}},~{}T_{2,a}=-\frac{1-\gamma_{2}}{\gamma_{2}}\frac{\Lambda_{2}}{\mu_{2}-\mu_{1}},~{}\text{and}~{}T_{2,f}=\frac{\Lambda_{2}}{\mu_{2}-\mu_{1}}.$
(10)

  2. 2.

If $\mu_{1}<\mu_{2}\gamma_{2}$ and
$\Lambda_{1}<\max\left\\{\frac{1-\gamma_{2}}{1-\gamma_{1}},1\right\\}\cdot\frac{\mu_{1}}{\mu_{2}-\mu_{1}}\Lambda_{2}$,
then

    1. a)

if $\gamma_{1}>\gamma_{2}$, then

$\displaystyle T_{1,a}$
$\displaystyle=\frac{1}{\mu_{2}}\left(\Lambda_{2}-\frac{1-\gamma_{1}}{1-\gamma_{2}}\frac{\mu_{2}-\mu_{1}}{\mu_{1}}\Lambda_{1}\right),~{}T_{1,f}=\frac{1}{\mu_{2}}\left(\Lambda_{2}+\frac{(\gamma_{1}-\gamma_{2})\mu_{2}+(1-\gamma_{1})\mu_{1}}{(1-\gamma_{2})\mu_{1}}\Lambda_{1}\right),$
$\displaystyle T_{2,a}$
$\displaystyle=-\frac{1}{\mu_{2}\gamma_{2}}\left((1-\gamma_{1})\Lambda_{1}+(1-\gamma_{2})\Lambda_{2}\right),~{}\text{and}~{}T_{2,f}=\frac{1}{\mu_{2}}\left(\Lambda_{2}+\frac{1-\gamma_{1}}{1-\gamma_{2}}\Lambda_{1}\right).$
(11)

    2. b)

if $\gamma_{1}<\gamma_{2}$, then

$\displaystyle T_{1,a}$
$\displaystyle=-\left(\frac{\gamma_{2}}{\gamma_{1}}-1\right)\frac{\Lambda_{1}}{\mu_{1}},~{}T_{1,f}=\frac{\Lambda_{1}}{\mu_{1}},~{}T_{2,a}=-\frac{1-\gamma_{2}}{\gamma_{2}}\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{2}},~{}\text{and}~{}T_{2,f}=\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{2}}.$
(12)

######  Theorem 4.1.

If $\gamma_{1}\neq\gamma_{2}$ and $\mu_{1}<\mu_{2}\gamma_{2}$, HAS has a
unique EAP which has the following arrival rates and support boundaries:

  1. 1.

If $\gamma_{1}>\gamma_{2}$:

    1. 1a.

when
$\Lambda_{1}\geq\frac{1-\gamma_{2}}{1-\gamma_{1}}\frac{\mu_{1}}{\mu_{2}-\mu_{1}}\Lambda_{2}$:

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\begin{cases}\frac{\mu_{1}\gamma_{1}}{\gamma_{2}}~{}~{}&\text{for}~{}t\in[T_{1,a},\tau_{1}^{-1}(T_{2,f})],\\\
\mu_{1}\gamma_{1}~{}~{}&\text{for}~{}t\in[\tau_{1}^{-1}(T_{2,f}),T_{1,f}],\end{cases}~{}\text{and}~{}F_{2}^{\prime}(t)=\begin{cases}\mu_{2}\gamma_{2}~{}~{}&\text{for}~{}t\in[T_{2,a},0],\\\
\mu_{2}\gamma_{2}-\mu_{1}~{}~{}&\text{for}~{}t\in[0,T_{2,f}],\\\ \end{cases}$

where $T_{1,a},T_{1,f},T_{2,a}$ and $T_{2,f}$ are given by (10).

    2. 1b.

when
$\Lambda_{1}<\frac{1-\gamma_{2}}{1-\gamma_{1}}\frac{\mu_{1}}{\mu_{2}-\mu_{1}}\Lambda_{2}$:

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\begin{cases}\frac{\mu_{1}\gamma_{1}}{\gamma_{2}}~{}~{}&\text{for}~{}t\in[T_{1,a},\tau_{1}^{-1}(T_{2,f})],{}\\\
\mu_{1}\gamma_{1}~{}~{}&\text{for}~{}t\in[\tau_{1}^{-1}(T_{2,f}),T_{1,f}],\\\
\end{cases}~{}\text{and}~{}F_{2}^{\prime}(t)=\begin{cases}\mu_{2}\gamma_{2}~{}~{}&\text{for}~{}t\in[T_{2,a},T_{1,a}],\\\
\mu_{2}\gamma_{2}-\mu_{1}~{}~{}&\text{for}~{}t\in[T_{1,a},T_{2,f}],\\\
\end{cases}$

where $T_{1,a},T_{1,f},T_{2,a}$ and $T_{2,f}$ are given by ( ‣ 2.).

  2. 2.

If $\gamma_{1}<\gamma_{2}$:

    1. 2a.

when $\Lambda_{1}\geq\frac{\mu_{1}}{\mu_{2}-\mu_{1}}\Lambda_{2}$, the EAP has
closed form same as case 1a.

    2. 2b.

when $\Lambda_{1}<\frac{\mu_{1}}{\mu_{2}-\mu_{1}}\Lambda_{2}$:

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\frac{\mu_{1}\gamma_{1}}{\gamma_{2}}~{}~{}\text{for}~{}t\in[T_{1,a},T_{1,f}],~{}\text{and}~{}F_{2}^{\prime}(t)=\begin{cases}\mu_{2}\gamma_{2}~{}~{}&\text{for}~{}t\in[T_{2,a},0]\cup[T_{1,f},T_{2,f}],\\\
\mu_{2}\gamma_{2}-\mu_{1}~{}~{}&\text{for}~{}t\in[0,T_{1,f}],\end{cases}$

where $T_{1,a},T_{1,f},T_{2,a}$ and $T_{2,f}$ are given by (12).

######  Remark 5.

_Illustrative EAPs and resulting queue length processes of cases 1a, 1b, 2a
and 2b of Theorem 4.1 are illustrated, respectively, in Figures 6, 7, 8 and 9.
Structure of the queue length processes in some regimes might vary depending
on the support boundaries and related quantities. We have illustrated only one
possible structure of the queue length process in those regimes and mentioned
the conditions on the support boundaries for the attainment of that structure
in the caption. Red and blue respectively denote class 1 and 2 populations. In
the plot on right-top, the black dashed line represents the total waiting mass
of the two classes in queue 2. The same is true for the illustrative EAPs and
resulting queue length processes referred to in Theorem 4.2._

Figure 6: Illustrative EAP (left) and queue length process (right) for HAS
with $\mu_{1}<\mu_{2}\gamma_{2}$ under case 1a of Theorem 4.1 and the
assumption $T=T_{1,a}+\frac{\gamma_{2}}{\gamma_{1}}T_{2,f}>0$ on (10).
$T\overset{def.}{=}\tau_{1}^{-1}(T_{2,f})$.  Figure 7: Illustrative EAP (left)
and queue length process (right) for HAS with $\mu_{1}<\mu_{2}\gamma_{2}$
under case 1b of Theorem 4.1. $T\overset{def.}{=}\tau_{1}^{-1}(T_{2,f})$.
Figure 8: Illustrative EAP (left) and queue length process (right) for HAS
with $\mu_{1}<\mu_{2}\gamma_{2}$ under case 2a of Theorem 4.2 and the
assumption $T=T_{1,a}+\frac{\gamma_{2}}{\gamma_{1}}T_{2,f}>0$ on (10).
$T\overset{def.}{=}\tau_{1}^{-1}(T_{2,f})$.  Figure 9: Illustrative EAP for
HAS with $\mu_{1}<\mu_{2}\gamma_{2}$ under case 2b of Theorem 4.2 and the
assumption $\tau_{2}(0)=-\gamma_{2}T_{2,a}<T_{1,f}$ on (12). Mass of class 2
waiting in queue 2 can increase in $[T_{1,f},\tau_{2}(T_{1,f})]$ if
$\mu_{2}\gamma_{2}>\mu_{2}-\mu_{1}/\gamma_{2}$.

Regime II $\mu_{1}\geq\mu_{2}\gamma_{2}$. The quantity
$T\overset{def}{=}\inf\\{t>0~{}|~{}Q_{2}(t)=0\\}$, representing the time at
which queue 2 empties for the first time, is necessary to describe the unique
EAP in Theorem 4.2.

We mention below the support boundaries and $T$ of the unique EAP, which we
will refer later in the statement of Theorem 4.2:

  1. 1.

If $\mu_{2}\gamma_{1}>\mu_{1}\geq\mu_{2}\gamma_{2}$ and
$\Lambda_{1}\geq\frac{\mu_{1}}{(1-\gamma_{1})\mu_{2}}\Lambda_{2}$; or
$\mu_{1}\geq\mu_{2}\cdot\max\\{\gamma_{1},\gamma_{2}\\}$ and
$\left(\frac{\mu_{2}}{\mu_{1}}-1\right)\Lambda_{1}>\Lambda_{2}$, then

$\displaystyle T_{1,a}$
$\displaystyle=\frac{\Lambda_{2}}{\mu_{2}\gamma_{1}}-\left(\frac{1}{\gamma_{1}}-1\right)\frac{\Lambda_{1}}{\mu_{1}},~{}T_{1,f}=\frac{\Lambda_{1}}{\mu_{1}},~{}T=\frac{\Lambda_{2}}{\mu_{2}-\mu_{1}},~{}T_{2,a}=-\frac{\Lambda_{2}}{\mu_{2}\gamma_{2}},~{}\text{and}~{}T_{2,f}=0.$
(13)

  2. 2.

If $\mu_{2}\gamma_{1}>\mu_{1}\geq\mu_{2}\gamma_{2}$ and
$\Lambda_{1}<\frac{\mu_{1}}{(1-\gamma_{1})\mu_{2}}\Lambda_{2}$, then

$\displaystyle T_{1,a}=T_{2,f}$
$\displaystyle=\frac{1}{\mu_{2}}\left(\Lambda_{2}-\frac{(1-\gamma_{1})\mu_{2}}{\mu_{1}}\Lambda_{1}\right),~{}T_{1,f}=\gamma_{1}\frac{\Lambda_{1}}{\mu_{1}}+\frac{\Lambda_{2}}{\mu_{2}},$
$\displaystyle T$
$\displaystyle=\frac{\Lambda_{2}}{\mu_{2}}+\frac{(1-\gamma_{1})\Lambda_{1}}{\mu_{2}-\mu_{1}},~{}\text{and}~{}T_{2,a}=-\left(\frac{1}{\gamma_{2}}-1\right)\frac{\Lambda_{2}}{\mu_{2}}-(1-\gamma_{1})\frac{\Lambda_{1}}{\mu_{1}}.$
(14)

  3. 3.

If $\mu_{1}\geq\mu_{2}\cdot\max\\{\gamma_{1},\gamma_{2}\\}$ and
$\left(\frac{\mu_{2}}{\mu_{1}}-1\right)\Lambda_{1}\leq\Lambda_{2}\leq\left(\frac{1}{\max\\{\gamma_{1},\gamma_{2}\\}}-1\right)\Lambda_{1}$:

$\displaystyle T_{1,a}$
$\displaystyle=\frac{1}{\mu_{2}}\left(\Lambda_{2}-\left(\frac{1}{\gamma_{1}}-1\right)\Lambda_{1}\right),~{}T=T_{1,f}=\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{2}},~{}T_{2,a}=-\frac{\Lambda_{2}}{\mu_{2}\gamma_{2}},~{}\text{and}~{}T_{2,f}=0.$
(15)

  4. 4.

If $\mu_{1}\geq\mu_{2}\gamma_{1}>\mu_{2}\gamma_{2}$ and
$\Lambda_{2}>\left(\frac{1}{\gamma_{1}}-1\right)\Lambda_{1}$:

$\displaystyle T_{1,a}=T_{2,f}$
$\displaystyle=-\left(\frac{1}{\gamma_{1}}-1\right)\frac{\Lambda_{1}}{\mu_{2}}+\frac{\Lambda_{2}}{\mu_{2}},~{}T_{1,f}=T=\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{2}},~{}\text{and}$
$\displaystyle T_{2,a}$
$\displaystyle=-\left(\frac{1}{\gamma_{1}}-1\right)\frac{\Lambda_{1}}{\mu_{2}}-\left(\frac{1}{\gamma_{2}}-1\right)\frac{\Lambda_{2}}{\mu_{2}}.$
(16)

  5. 5.

If $\mu_{1}\geq\mu_{2}\gamma_{2}>\mu_{2}\gamma_{1}$ and
$\Lambda_{2}>\left(\frac{1}{\gamma_{2}}-1\right)\Lambda_{1}$:

$\displaystyle T_{1,a}$
$\displaystyle=-\left(\frac{1}{\gamma_{1}}-\frac{1}{\gamma_{2}}\right)\frac{\Lambda_{1}}{\mu_{2}},~{}T_{1,f}=\frac{\Lambda_{1}}{\mu_{2}\gamma_{2}},~{}T=T_{2,f}=\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{2}},~{}\text{and}~{}T_{2,a}=-\frac{1-\gamma_{2}}{\gamma_{2}}\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{2}}.$
(17)

######  Theorem 4.2.

If $\mu_{1}\geq\mu_{2}\gamma_{2}$ and $\gamma_{1}\neq\gamma_{2}$, HAS has a
unique EAP. Moreover, the EAP has the following arrival rates and support
boundaries:

  1. 1.

If $\mu_{2}\gamma_{1}>\mu_{1}\geq\mu_{2}\gamma_{2}$:

    1. 1a.

when $\Lambda_{1}\geq\frac{\mu_{1}}{(1-\gamma_{1})\mu_{2}}\Lambda_{2}$:

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\begin{cases}\mu_{2}\gamma_{1}~{}~{}&\text{for}~{}t\in[T_{1,a},\tau_{1}^{-1}(T)],\\\
\mu_{1}\gamma_{1}~{}~{}&\text{for}~{}t\in[\tau_{1}^{-1}(T),T_{1,f}],\end{cases}~{}\text{and}~{}F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}~{}~{}\text{for}~{}t\in\left[T_{2,a},T_{2,f}\right]$

where $T_{1,a},T_{1,f},T_{2,a},T_{2,f}$ and $T$ are in (13).

    2. 1b.

when $\Lambda_{1}<\frac{\mu_{1}}{(1-\gamma_{1})\mu_{2}}\Lambda_{2}$,

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\begin{cases}\mu_{2}\gamma_{1}~{}~{}&\text{for}~{}t\in[T_{1,a},\tau_{1}^{-1}(T)],\\\
\mu_{1}\gamma_{1}~{}~{}&\text{for}~{}t\in[\tau_{1}^{-1}(T),T_{1,f}],\end{cases}~{}\text{and}~{}F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}~{}~{}~{}\text{for}~{}t\in[T_{2,a},T_{2,f}]$

where $T_{1,a},T_{1,f},T_{2,a},T_{2,f}$ and $T$ are in (2.).

  2. 2.

If $\mu_{1}\geq\mu_{2}\gamma_{1}>\mu_{2}\gamma_{2}$:

    1. 2a.

when $\left(\frac{\mu_{2}}{\mu_{1}}-1\right)\Lambda_{1}>\Lambda_{2}$, the EAP
has a closed form same as case 1a.

    2. 2b.

when
$\left(\frac{1}{\gamma_{1}}-1\right)\Lambda_{1}\geq\Lambda_{2}\geq\left(\frac{\mu_{2}}{\mu_{1}}-1\right)\Lambda_{1}$,

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\mu_{2}\gamma_{1}~{}~{}\text{for}~{}t\in[T_{1,a},T_{1,f}]~{}\text{and}~{}F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}~{}~{}\text{for}~{}t\in\left[T_{2,a},T_{2,f}\right]$

where $T_{1,a},T_{1,f},T_{2,a},T_{2,f}$ and $T$ are in (15).

    3. 2c.

when $\Lambda_{2}>\left(\frac{1}{\gamma_{1}}-1\right)\Lambda_{1}$,

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\mu_{2}\gamma_{1}~{}~{}~{}\text{for}~{}t\in[T_{1,a},T_{1,f}]~{}\text{and}~{}F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}~{}~{}~{}\text{for}~{}t\in[T_{2,a},T_{2,f}]$

where $T_{1,a},T_{1,f},T_{2,a},T_{2,f}$ and $T$ are in (4.).

  3. 3.

If $\mu_{1}\geq\mu_{2}\gamma_{2}>\mu_{2}\gamma_{1}$:

    1. 3a.

when $\left(\frac{\mu_{2}}{\mu_{1}}-1\right)\Lambda_{1}>\Lambda_{2}$, the EAP
has a closed form same as case 1a.

    2. 3b.

when
$\left(\frac{1}{\gamma_{2}}-1\right)\Lambda_{1}\geq\Lambda_{2}\geq\left(\frac{\mu_{2}}{\mu_{1}}-1\right)\Lambda_{1}$,
the EAP has a closed form same as case 2b.

    3. 3c.

when $\Lambda_{2}>\left(\frac{1}{\gamma_{2}}-1\right)\Lambda_{1}$,

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\mu_{2}\gamma_{1}~{}~{}\text{for}~{}t\in[T_{1,a},T_{1,f}]~{}\text{and}~{}F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}~{}~{}\text{for}~{}t\in[T_{2,a},0]\cup[T_{1,f},T_{2,f}]$

where $T_{1,a},T_{1,f},T_{2,a},T_{2,f}$ and $T$ are in (17).

######  Remark 6.

_Illustrative EAPs and resulting queue length processes of cases 1a, 1b, 2a,
2b, 2c, 3a, 3b, and 3c of Theorem 4.2 are illustrated, respectively, in
Figures 10, 11, 12, 13, 14, 15, 16 and 17._

######  Remark 7.

_We show by Lemma B.6 and B.12 in B.1 that in every EAP of HAS under case 3
($\mu_{1}\geq\mu_{2}\gamma_{2}>\mu_{2}\gamma_{1}$) of Theorem 4.2, class 1
users arrive from queue 1 to queue 2 in $[0,T_{1,f}]$ at rate $\mu_{1}$. As a
result, by Lemma 4.1, class 2 users cannot arrive in $[0,T_{1,f}]$. However,
in every EAP, class 2 users start arriving before time zero (otherwise queue 2
stays empty at time zero and every class 2 user can be strictly better off
arriving at time zero). Therefore there are two possible ways in which class 2
users can arrive in any EAP: 1) the whole class 2 population arrives before
time zero, or, 2) a fraction of the class 2 population arrives after $T_{1,f}$
and the rest arrives before time zero. While proving the existence of a unique
EAP in case 3 of Theorem 4.2, we argue that, if $\Lambda_{2}$ is under an
identified threshold of $\left(\frac{1}{\gamma_{2}}-1\right)\Lambda_{1}$, the
whole class 2 population arrives before time zero and waits in queue 2 at time
zero, as can be seen for cases 3a and 3b, respectively, in Figure 15 and 16.
After $\Lambda_{2}$ crosses that threshold, a fraction of the class 2
population of mass
$\gamma_{2}\left[\Lambda_{2}-\left(\frac{1}{\gamma_{2}}-1\right)\Lambda_{1}\right]$
arrives after $T_{1,f}$ and the rest arrives before time zero, as can be seen
for case 3c in Figure 17._

Figure 10: Illustrative EAP (left) and resulting queue length process (right)
of HAS with $\mu_{1}\geq\mu_{2}\gamma_{2}$ under case 1a of Theorem 4.2 with
the assumption $T^{0}>0$, where $T^{0}\overset{def.}{=}\tau_{1}^{-1}(T)$.

Figure 11: Illustrative EAP (left) and resulting queue length process (right)
of HAS with $\mu_{2}\gamma_{1}>\mu_{1}\geq\mu_{2}\gamma_{2}$ under case 1b of
Theorem 4.2. $T^{0}\overset{def.}{=}\tau_{1}^{-1}(T)$.

.

Figure 12: Illustrative EAP (left) and resulting queue length process (right)
of HAS with $\mu_{1}\geq\mu_{2}\gamma_{1}>\mu_{2}\gamma_{2}$ under case 2a of
Theorem 4.2 with the assumption $T^{0}>0$ where
$T^{0}\overset{def.}{=}\tau_{1}^{-1}(T)$.  Figure 13: Illustrative EAP (left)
and queue length process (right) of HAS with
$\mu_{1}\geq\mu_{2}\gamma_{1}>\mu_{2}\gamma_{2}$ under case 2b of Theorem 4.2
with assumption $\tau_{2}(0)<T_{1,idle}$, where $T_{1,idle}$ is the time at
which queue 1 empties after the network starts at time zero. In the
illustration, we assumed $\mu_{1}<\mu_{2}$, causing mass of class 1 users
waiting in queue 2 to decrease in $[\tau_{2}(0),T_{1,idle}]$, but it can be
non-decreasing if $\mu_{1}\geq\mu_{2}$. For the same assumption, the overall
mass of the two classes is decreasing in $[0,T_{1,idle}]$ and can be non-
decreasing if $\mu_{1}\geq\mu_{2}$.  Figure 14: Illustrative EAP (left) and
resulting queue length process (right) of HAS with
$\mu_{1}\geq\mu_{2}\gamma_{1}>\mu_{2}\gamma_{2}$ under case 2c of Theorem 4.2.
Figure 15: Illustrative EAP of HAS (left) and queue length process (right)
with $\mu_{1}\geq\mu_{2}\gamma_{2}>\mu_{2}\gamma_{1}$ under case 3a of Theorem
4.2 with the assumption $T^{0}=\tau_{1}^{-1}(T)>0$.  Figure 16: Illustrative
EAP (left) and resulting queue length process (right) of HAS with
$\mu_{1}\geq\mu_{2}\gamma_{2}>\mu_{2}\gamma_{1}$ under case 3b of Theorem 4.2
with the assumption $\tau_{2}(0)<T_{1,idle}$, where $T_{1,idle}$ is the time
at which queue 1 empties after the network starts at time zero.  Figure 17:
Illustrative EAP (left) and queue length process (right) of HAS with
$\mu_{1}\geq\mu_{2}\gamma_{2}>\mu_{2}\gamma_{1}$ under case 3c of Theorem 4.2
with the assumption $T_{1,f}>\tau_{2}(0)>T_{1,idle}$, where $T_{1,idle}$ is
the time at which queue 1 empties after time zero.

###  4.2 Equal Preferences $\gamma_{1}=\gamma_{2}=\gamma$

We state the main result of this section separately for two regimes as Theorem
4.3 (for $\mu_{1}<\mu_{2}\gamma$), and 4.4 (for $\mu_{1}\geq\mu_{2}\gamma$),
since they have different EAP structures. Proofs of these two theorems (in
B.2) are similar in structure to that of Theorem 3.2.

$T_{1,a},T_{1,f},T_{2,a},T_{2,f}$ are as in the unequal preference case. Let
$T_{a}=\inf\mathcal{S}(F_{1})\cup\mathcal{S}(F_{2})$ and
$T_{f}=\sup\mathcal{S}(F_{1})\cup\mathcal{S}(F_{2})$.

######  Theorem 4.3.

If $\mu_{1}<\mu_{2}\gamma$,

  1. 1.

when $\Lambda_{1}>\frac{\mu_{1}}{\mu_{2}-\mu_{1}}\Lambda_{2}$, the EAP is
unique and has the following arrival rates and support boundaries:

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\begin{cases}\mu_{1}~{}~{}&\text{if}~{}~{}t\in[T_{1,a},\tau_{1}^{-1}(T_{2,f})],\\\
\mu_{1}\gamma~{}~{}&\text{if}~{}~{}t\in[\tau_{1}^{-1}(T_{2,f}),T_{1,f}].\end{cases},~{}\text{and}~{}F_{2}^{\prime}(t)=\begin{cases}\mu_{2}\gamma~{}~{}&\text{if}~{}t\in[T_{2,a},0],\\\
\mu_{2}\gamma-\mu_{1}~{}~{}&\text{if}~{}t\in[0,T_{2,f}],\end{cases}$
$\displaystyle\text{where}~{}T_{1,a}$
$\displaystyle=-\frac{1-\gamma}{\gamma}\left(\frac{\Lambda_{1}}{\mu_{1}}-\frac{\Lambda_{2}}{\mu_{2}-\mu_{1}}\right),~{}T_{1,f}=\frac{\Lambda_{1}}{\mu_{1}},~{}T_{2,a}=-\frac{1-\gamma}{\gamma}\frac{\Lambda_{2}}{\mu_{2}-\mu_{1}},~{}\text{and}~{}T_{2,f}=\frac{\Lambda_{2}}{\mu_{2}-\mu_{1}}.$

  2. 2.

when $\Lambda_{1}\leq\frac{\mu_{1}}{\mu_{2}-\mu_{1}}\Lambda_{2}$, set of EAPs
is given by the convex set of joint customer arrival profiles
$\\{F_{1},F_{2}\\}$ satisfying: 1)
$F_{1}^{\prime}(t)=0,~{}F_{2}^{\prime}(t)=\mu_{2}\gamma$ for all
$t\in[T_{a},0]$, 2)
$F_{1}^{\prime}(t)\leq\mu_{1},~{}F_{1}^{\prime}(t)+F_{2}^{\prime}(t)=\mu_{2}\gamma$
for all $t\in[0,T_{f}]$, and 3)
$F_{1}(T_{f})=\Lambda_{1},~{}F_{2}(T_{f})=\Lambda_{2}$, where
$T_{a}=-\left(\frac{1}{\gamma}-1\right)\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{2}}$
and $T_{f}=\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{2}}$.

######  Remark 8.

_If $\Lambda_{1}>\frac{\mu_{1}}{\mu_{2}-\mu_{1}}\Lambda_{2}$, the EAPs in case
1a and 2a of Theorem 4.1, respectively, upon taking limits
$\gamma_{1}\to\gamma+,~{}\gamma_{2}=\gamma$ and
$\gamma_{1}=\gamma,~{}\gamma_{2}\to\gamma+$ converges to the EAP under case 1
of Theorem 4.3. On the other hand, if
$\Lambda_{1}\leq\frac{\mu_{1}}{\mu_{2}-\mu_{1}}\Lambda_{2}$, the EAPs in case
1b and 2b of Theorem 4.1, respectively, upon taking limits
$\gamma_{1}\to\gamma+,~{}\gamma_{2}=\gamma$ and
$\gamma_{1}=\gamma,~{}\gamma_{2}\to\gamma+$ might converge to different
limits, but both the limits will be contained in the convex set of EAPs under
case 2 of 4.1._

The quantity $T\overset{def.}{=}\inf\left\\{t>0~{}|~{}Q_{2}(t)=0\right\\}$
will be necessary to describe the structure of the EAP in the regime
$\mu_{1}\leq\mu_{2}\gamma$.

######  Theorem 4.4.

If $\mu_{1}\geq\mu_{2}\gamma$,

  1. 1.

when $\left(\frac{\mu_{2}}{\mu_{1}}-1\right)\Lambda_{1}>\Lambda_{2}$, the EAP
is unique and has the following arrival rates and support boundaries:

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\begin{cases}\mu_{2}\gamma~{}~{}&\text{if}~{}t\in[T_{1,a},\tau_{1}^{-1}(T)],\\\
\mu_{1}\gamma~{}~{}&\text{if}~{}t\in[\tau_{1}^{-1}(T),T_{1,f}],\end{cases},~{}\text{and}~{}F_{2}^{\prime}(t)=\mu_{2}\gamma~{}~{}\text{if}~{}t\in\left[-\frac{\Lambda_{2}}{\mu_{2}\gamma},0\right],$
$\displaystyle\text{where}~{}T_{1,a}$
$\displaystyle=\frac{\Lambda_{2}}{\mu_{2}\gamma}-\left(\frac{1}{\gamma}-1\right)\frac{\Lambda_{1}}{\mu_{1}},~{}T=\frac{\Lambda_{2}}{\mu_{2}-\mu_{1}},~{}\text{and}~{}T_{1,f}=\frac{\Lambda_{1}}{\mu_{1}}.$

  2. 2.

when
$\left(\frac{1}{\gamma}-1\right)\Lambda_{1}\geq\Lambda_{2}\geq\left(\frac{\mu_{2}}{\mu_{1}}-1\right)\Lambda_{1}$,
the EAP is unique and has the following arrival rates and support boundaries:

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\mu_{2}\gamma~{}~{}\text{if}~{}t\in[T_{1,a},T_{1,f}],~{}\text{and}~{}F_{2}^{\prime}(t)=\mu_{2}\gamma~{}~{}\text{if}~{}t\in\left[-\frac{\Lambda_{2}}{\mu_{2}\gamma},0\right],$
$\displaystyle\text{where}~{}T_{1,a}$
$\displaystyle=\frac{1}{\mu_{2}}\left(\Lambda_{2}-\left(\frac{1}{\gamma}-1\right)\Lambda_{1}\right),~{}\text{and}~{}T=T_{1,f}=\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{2}}.$

  3. 3.

If $\Lambda_{2}>\left(\frac{1}{\gamma}-1\right)\Lambda_{1}$, set of EAPs is
given by the convex set of joint customer arrival profiles $\\{F_{1},F_{2}\\}$
satisfying: 1) $F_{1}^{\prime}(t)=0$ and $F_{2}^{\prime}(t)=\mu_{2}\gamma$ for
all $t\in[T_{a},0]$, 2) $F_{1}^{\prime}(t)+F_{2}^{\prime}(t)=\mu_{2}\gamma$
for all $t\in[0,T_{f}]$, and 3)
$F_{1}(T_{f})=\Lambda_{1},~{}F_{2}(T_{f})=\Lambda_{2}$, where
$T_{a}=-\left(\frac{1}{\gamma}-1\right)\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{2}}$
and $T_{f}=\frac{\Lambda_{1}+\Lambda_{2}}{\mu_{2}}$.

######  Remark 9.

_If $\left(\frac{\mu_{2}}{\mu_{1}}-1\right)\Lambda_{1}>\Lambda_{2}$, the EAPs
in case 2a and 3a of Theorem 4.2, respectively upon taking limits
$\gamma_{1}\to\gamma+,\gamma_{2}=\gamma$ and
$\gamma_{1}=\gamma,\gamma_{2}\to\gamma+$, converges to the EAP under case 1 of
Theorem 4.4. If
$\left(\frac{1}{\gamma}-1\right)\Lambda_{1}\geq\Lambda_{2}\geq\left(\frac{\mu_{2}}{\mu_{1}}-1\right)\Lambda_{1}$,
upon taking the same limits, the EAPs in case 2b and 3b of Theorem 4.2
converges to the EAP under case 2 of Theorem 4.4. If
$\Lambda_{2}>\left(\frac{1}{\gamma}-1\right)\Lambda_{1}$, upon taking the same
limits, the EAPs in case 2c and 3c of Theorem 4.2 converges to different
limits and both of them are contained in the convex set of EAPs under case 3
of Theorem 4.4._

##  5 Conclusion

Arrival games to a single queue have been well studied in the literature, but
the important area of arrival games to a general queuing network, has limited
literature. As we discovered, this may be because the problem complexity may
increase substantially with the network size. We studied a simple two queue,
two class network with a linear cost structure, where we analyzed in detail
two heterogeneous routing configurations: (1) where the customer classes
arrived at the same queue but departed in different queues, and (2) where the
customer classes arrived at different queues but departed from the same queue.
We discovered non-trivial customer behaviour not apparent in a single queue or
in networks studied thus far in the literature. In a specific setting we found
that the parameter space had to be partitioned into eight distinct regions,
where each region had its own closed form parametric representation of the
arrival equilibrium profile. We found that although for most set of
parameters, the equilibrium profile is unique, there exists settings where the
collection of equilibrium profiles is not unique but a convex set. While in a
single queue, multi-class customers arrive in contiguous, non-overlapping
intervals, in our two queue setting there are regions where, in equilibrium,
different class arrival times may overlap. Further, there exist regions, where
a single class customer may arrive in disjoint intervals. The broad message of
the paper is mixed and motivates further research - it suggests that even for
more complex networks one may expect a unique equilibrium profile for most
parameter settings. It also suggests that the number of different solution
structures may blow up with the network size, so that learning the structure
in any instance may be a difficult task.

## Acknowledgement

Our work is supported by Department of Atomic Energy, Government of India,
under project no. RTI4001.

## References

  * [1] Avrim Blum and Yishay Mansour.  Learning, Regret Minimization, and Equilibria, page 79–102.  Cambridge University Press, 2007.
  * [2] Jesper Breinbjerg.  Equilibrium arrival times to queues with general service times and non-linear utility functions.  European Journal of Operational Research, 261(2):595–605, 2017\.
  * [3] Nicolo Cesa-Bianchi and Gábor Lugosi.  Prediction, learning, and games.  Cambridge university press, 2006.
  * [4] Hong Chen and David D Yao.  Fundamentals of queueing networks: Performance, asymptotics, and optimization, volume 4.  Springer, 2001.
  * [5] Amihai Glazer and Refael Hassin.  ?/m/1: On the equilibrium distribution of customer arrivals.  European Journal of Operational Research, 13(2):146–150, 1983.
  * [6] Refael Hassin.  Rational Queueing.  Chapman and Hall/CRC, 2016.
  * [7] Refael Hassin and Moshe Haviv.  To queue or not to queue: Equilibrium behavior in queueing systems, volume 59.  Springer Science & Business Media, 2003.
  * [8] Moshe Haviv and Binyamin Oz.  A busy period approach to some queueing games.  Queueing Systems, 97:261–277, 2021.
  * [9] Moshe Haviv and Liron Ravner.  A survey of queueing systems with strategic timing of arrivals.  Queueing Systems, 99:163–198, 2021.
  * [10] Chris Hendrickson and George Kocur.  Schedule delay and departure time decisions in a deterministic model.  Transportation Science, 15(1):62–77, 1981.
  * [11] Harsha Honnappa and Rahul Jain.  Strategic arrivals into queueing networks: The network concert queueing game.  Operations Research, 63(1):247–259, 2015.
  * [12] Rahul Jain, Sandeep Juneja, and Nahum Shimkin.  The concert queueing game: to wait or to be late.  Discrete Event Dynamic Systems, 21:103–138, 2011.
  * [13] Sandeep Juneja and Nahum Shimkin.  The concert queueing game: strategic arrivals with waiting and tardiness costs.  Queueing Systems, 74:369–402, 2013.
  * [14] Zhi-Chun Li, Hai-Jun Huang, and Hai Yang.  Fifty years of the bottleneck model: A bibliometric review and future research directions.  Transportation research part B: methodological, 139:311–342, 2020\.
  * [15] Robin Lindsey.  Existence, uniqueness, and trip cost function properties of user equilibrium in the bottleneck model with multiple user classes.  Transportation Science, 38:293–314, 2004.
  * [16] William S. Vickrey.  Congestion theory and transport investment.  The American Economic Review, 59(2):251–260, 1969.

## Appendix

For the ease of analysis, we define the set
$E_{j}\overset{def.}{=}\\{t~{}|~{}t<0~{}\text{or}~{}Q_{j}(t)>0\\}$ to be the
set of all times when queue $j$ has a positive waiting time for $j=1,2$. For
any set $S\subseteq\mathbb{R}$, we use the notations $\overline{S}$ and
$S^{o}$ to respectively denote the closure and interior of $S$.

By Lemma 2.1, we consider only absolutely continuous arrival profiles $F_{1}$
and $F_{2}$ and as a result, $\mathcal{S}(F_{1})$ and $\mathcal{S}(F_{2})$
cannot have isolated points.

##  Appendix A Proofs of Lemmas in Section 3

As argued in Section 3, we assume $\mu_{1}>\mu_{2}$ for the following
discussion.

###  A.1 Proofs of Lemmas in Section 3.1 (HDS with $\gamma_{1}\neq\gamma_{2}$)

Several of the lemmas proved below will extend to the case where
$\gamma_{1}=\gamma_{2}$. So, whenever some lemma is applicable only for the
case of unequal preferences, we mention it explicitly in the lemma statement.

Lemma A.1 specifies the state of queue 2 when users of both classes are
arriving together in queue 1 and is a special case of Lemma 3.3. This lemma
helps us prove Lemma 3.1 and together with Lemma A.2, it will help us
calculate the arrival rate of the two classes in equilibrium.

######  Lemma A.1.

If $\gamma_{1}\neq\gamma_{2}$ and $\mu_{1}>\mu_{2}$, in the EAP,
$t\in(\mathcal{S}(F_{1}))^{o}\cap(\mathcal{S}(F_{2}))^{o}$ implies
$\tau_{1}(t)\in\overline{E_{2}}$.

###### Proof.

Assuming contradiction, i.e., $\tau_{1}(t)\notin\overline{E_{2}}$, there is a
neighbourhood $[\tau_{1}(t)-\delta,\tau_{1}(t)+\delta]$ of $\tau_{1}(t)$,
where queue 2 is empty. Since the arrival profiles $F_{1},~{}F_{2}$ are
absolutely continuous, $\tau_{1}(\cdot)$ will be continuous. As a result, we
have
$[t-\epsilon,t+\epsilon]\subseteq(\mathcal{S}(F_{1}))^{o}\cap(\mathcal{S}(F_{2}))^{o}$
such that, $Q_{2}(\tau_{1}(s))=0$ for all $s\in[t-\epsilon,t+\epsilon]$. Hence
every class 2 user arriving in $[t-\epsilon,t+\epsilon]$ waits only at queue
1. For both the classes $i=1,2$ departure time
$\tau_{\mathbf{F}}^{(i)}(s)=\tau_{1}(s)$ in $[t-\epsilon,t+\epsilon]$ and
hence cost $C_{\mathbf{F}}^{(i)}(s)=\tau_{1}(s)-\gamma_{i}s$. Since,
$[t-\epsilon,t+\epsilon]\subseteq(\mathcal{S}(F_{1}))^{o}\cap(\mathcal{S}(F_{2}))^{o}$,
by definition of EAP, for $i=1,2$ $C_{\mathbf{F}}^{(i)}(\cdot)$ is constant in
$[t-\epsilon,t+\epsilon]$. Therefore,
$(C_{\mathbf{F}}^{(i)})^{\prime}(s)=\tau_{1}^{\prime}(s)-\gamma_{i}=0$ in
$[t-\epsilon,t+\epsilon]$, giving us
$\tau_{1}^{\prime}(s)=\gamma_{1}=\gamma_{2}$, contradicting the assumption
$\gamma_{1}\neq\gamma_{2}$. ∎

Lemma A.2 helps us relate the arrival rate of class 2 users and will be
referred to ubiquitously while proving the structural properties.

######  Lemma A.2.

For every absolutely continuous joint user arrival profile
$\\{F_{1},F_{2}\\}$, $\tau_{\mathbf{F}}^{(2)}(\cdot)$ is differentiable a.e.
in the set of times
$\tau_{1}^{-1}(\overline{E_{2}})\overset{def.}{=}\\{t~{}|~{}\tau_{1}(t)\in\overline{E_{2}}\\}$
with derivative
$(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)=\frac{F_{2}^{\prime}(t)}{\mu_{2}}$ a.e.
As a consequence,
$(C_{\mathbf{F}}^{(2)})^{\prime}(t)=\frac{F_{2}^{\prime}(t)}{\mu_{2}}-\gamma_{2}$
a.e. in $\tau_{1}^{-1}(\overline{E_{2}})$.

###### Proof.

We divide the proof into two separate cases:

  1. 1.

In $\overline{E_{1}}^{c}$, we will have $\tau_{1}(t)=t$ and as a result
$\overline{E_{1}}^{c}\cap\tau_{1}^{-1}(\overline{E_{2}})=\overline{E_{1}}^{c}\cap\overline{E_{2}}$.
Therefore, using (3)
$(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)=\tau_{2}^{\prime}(t)=\frac{F_{2}^{\prime}(t)}{\mu_{2}}$
a.e. in $\overline{E_{1}}^{c}\cap\tau_{1}^{-1}(\overline{E_{2}})$.

  2. 2.

In $\overline{E_{1}}$, by (3), $\tau_{1}^{\prime}(\cdot)$ exists a.e. Again
using (3), since $\tau_{1}(t)\in\overline{E_{2}}$, we have
$\tau_{2}^{\prime}(\tau_{1}(t))=\frac{A_{2}^{\prime}(\tau_{1}(t))}{\mu_{2}}$.
Therefore,
$(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)=\frac{A_{2}^{\prime}(\tau_{1}(t))\tau_{1}^{\prime}(t)}{\mu_{2}}$
a.e. in $\overline{E_{1}}\cap\tau_{1}^{-1}(\overline{E_{2}})$. Since
$A_{2}(\tau_{1}(t))=F_{2}(t)$, by chain rule,
$(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)=\frac{F_{2}^{\prime}(t)}{\mu_{2}}$ a.e.
in $\overline{E_{1}}\cap\tau_{1}^{-1}(\overline{E_{2}})$.

Since $C_{\mathbf{F}}^{(2)}(t)=\tau_{\mathbf{F}}^{(2)}(t)-\gamma_{2}t$, the
second statement of the lemma follows trivially. ∎

Lemma B.5 implies that
$\mu_{1}\leq\mu_{2}\cdot\max\left\\{1,\frac{\gamma_{2}}{\gamma_{1}}\right\\}$
is sufficient for $\mathcal{S}(F_{1})$ and $(\mathcal{S}(F_{2}))^{o}$ to be
disjoint, and is helpful for proving sufficiency of the condition in Lemma
3.1.

######  Lemma A.3.

If $\mu_{1}\gamma_{1}\leq\mu_{2}\gamma_{2}$, in every EAP,
$\mathcal{S}(F_{1})$ and $(\mathcal{S}(F_{2}))^{o}$ are disjoint.

###### Proof.

Proof of Lemma A.3 follows the argument mentioned after Lemma 3.1 for proving
sufficiency of
$\mu_{1}\leq\mu_{2}\cdot\max\left\\{1,\frac{\gamma_{2}}{\gamma_{1}}\right\\}$
for $\mathcal{S}(F_{1}),\mathbf{S}(F_{2})$ to be non-overlapping, except while
proving
$(C_{\mathbf{F}}^{(2)})^{\prime}(t)=\frac{F_{2}^{\prime}(t)}{\mu_{2}}-\gamma_{2}$
in $[t_{1},t_{2}]$, we use Lemma B.1 to argue queue 2 stays engaged at
$\tau_{1}(t)$ and then use Lemma A.2 to have
$(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)=\frac{F_{2}^{\prime}(t)}{\mu_{2}}$ in
$[t_{1},t_{2}]$.

∎

As we stated in the main body, $T_{i,a}=\inf\mathcal{S}(F_{i})$ and
$T_{i,f}=\sup\mathcal{S}(F_{i})$ for the two classes $i=1,2$. Note that
$T_{1,a},T_{1,f},T_{2,a},T_{2,f}$ are all finite if
$\mathbf{F}=\\{F_{1},F_{2}\\}$ is an EAP. Lemma A.4 and A.5 are respectively
the first and second statements of Lemma 3.5.

######  Lemma A.4.

(First statement of Lemma 3.5) In the EAP, if
$\mathcal{S}(F_{2})=[T_{2,a},T_{2,f}]$, then queue 2 will have zero waiting
time at $\tau_{1}(T_{2,f})$.

###### Proof.

Assume contradiction, i.e., $\tau_{1}(T_{2,f})\in E_{2}$. For $\delta>0$
chosen sufficiently small, image of $[T_{2,f},T_{2,f}+\delta]$ under
$\tau_{1}(\cdot)$ is contained in $E_{2}$. Therefore by Lemma A.2,
$(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)=\frac{F_{2}^{\prime}(t)}{\mu_{2}}$ in
$[T_{2,f},T_{2,f}+\delta]$. Since $F_{2}^{\prime}(t)=0$ in
$(T_{2,f},T_{2,f}+\delta]$, we get
$\tau_{\mathbf{F}}^{(2)}(T_{2,f}+\delta)=\tau_{\mathbf{F}}^{(2)}(T_{2,f})$. As
a result, the class 2 user arriving at $T_{2,f}$ will be strictly better off
arriving at $T_{2,f}+\delta$, contradicting that $\\{F_{1},F_{2}\\}$ is an
EAP. ∎

We now prove below Lemma 3.2 about the structure of the supports of the two
classes in EAP.

Proof of Lemma 3.2: (1) On assuming contradiction, there exists
$t_{1},t_{2}\in\mathcal{S}(F_{1})\cup\mathcal{S}(F_{2})$ such that
$t_{2}>t_{1}$ and $F_{1}(t_{1})+F_{2}(t_{1})=F_{1}(t_{2})+F_{2}(t_{2})$. Note
that $t_{2}<\max\\{T_{1,f},T_{2,f}\\}$. Otherwise, $\max\\{T_{1,f},T_{2,f}\\}$
will be an isolated point of $\mathcal{S}(F_{1})\cup\mathcal{S}(F_{2})$,
contradicting absolute continuity of $F_{1}$ and $F_{2}$.

With $t_{2}<\max\\{T_{1,f},T_{2,f}\\}$, a positive mass of users must arrive
after $t_{2}$. Therefore, none of the classes can have zero waiting time in
$[t_{1},t_{2}]$, implying $[t_{1},t_{2}]\subseteq E_{1}\cup E_{2}$. There can
be two situations now:

  * •

If $t_{1}\in E_{1}$: For $\delta>0$ picked sufficiently small,
$[t_{1},t_{1}+\delta]\subseteq E_{1}$. Since $A_{1}^{\prime}(s)=0$ for every
$s\in[t_{1},t_{1}+\delta]$, by (3), $\tau_{1}(t_{1})=\tau_{1}(t_{1}+\delta)$.
As a result, for both classes $i=1,2$
$\tau_{\mathbf{F}}^{(i)}(t_{1})=\tau_{\mathbf{F}}^{(i)}(t_{1}+\delta)$.
Therefore, the user arriving at $t_{1}$ will be strictly better off arriving
at $t_{1}+\delta$.

  * •

If $t_{1}\notin E_{1}$: Since no users arrive in $[t_{1},t_{2}]$, queue 1 has
zero waiting time in $[t_{1},t_{2}]$ (by (3)) implying,
$[t_{1},t_{2}]\subseteq E_{2}$. Therefore some positive mass of class 2 users
must have arrived before $t_{1}$. Let $\tilde{t}=\sup\\{t\leq
t_{1}~{}|~{}t\in\mathcal{S}(F_{2})\\}=$ the last time before $t_{1}$ some
class 2 user has arrived. Since no class 2 users arrives in
$[\tilde{t},t_{2}]$, $Q_{2}(\cdot)$ cannot increase in
$[\tau_{1}(\tilde{t}),\tau_{1}(t_{2})]$. Therefore, $t_{2}=\tau_{1}(t_{2})\in
E_{2}$ implies $[\tau_{1}(\tilde{t}),\tau_{1}(t_{2})]\subseteq E_{2}$. With
this observation, since $F_{2}^{\prime}(s)=0$ in $(\tilde{t},t_{2})$, we
conclude $\tau_{\mathbf{F}}^{(2)}(\tilde{t})=\tau_{\mathbf{F}}^{(2)}(t_{2})$
(by Lemma A.2). Therefore, the class 2 user arriving at $\tilde{t}$ will be
strictly better off arriving at $t_{2}$ instead.

In both cases, $\mathbf{F}=\\{F_{1},F_{2}\\}$ will not be an EAP,
contradicting our assumption.

(2) On assuming contradiction, there exists $t_{1},t_{2}\in\mathcal{S}(F_{2})$
such that $F_{2}(t_{1})=F_{2}(t_{2})$. We must have $t_{2}<T_{2,f}$,
otherwise, $T_{2,f}$ will be an isolated point in $\mathcal{S}(F_{2})$. Since
$\mathcal{S}(F_{1})\cup\mathcal{S}(F_{2})$ is an interval, we must have
$[t_{1},t_{2}]\subseteq\mathcal{S}(F_{1})$. Two situations might arise:

  * •

If $\tau_{1}(t_{1})\in E_{2}$: By continuity of $\tau_{1}(\cdot)$, we can find
$\delta\in(0,t_{2}-t_{1})$ sufficiently small such that image of
$[t_{1},t_{1}+\delta]$ under $\tau_{1}(\cdot)$ is contained in $E_{2}$. Since
$F_{2}^{\prime}(t)=0$ in $[t_{1},t_{2}]$, by Lemma A.2, the previous statement
implies
$\tau_{\mathbf{F}}^{(2)}(t_{1})=\tau_{\mathbf{F}}^{(2)}(t_{1}+\delta)$.
Therefore the class 2 user arriving at $t_{1}$ will be strictly better off
arriving at $t_{1}+\delta$.

  * •

If $\tau_{1}(t_{1})\notin E_{2}$: With no class 2 user arriving at queue 2 in
$[\tau_{1}(t_{1}),\tau_{1}(t_{2})]$, we have
$[\tau_{1}(t_{1}),\tau_{1}(t_{2})]\subseteq E_{2}^{c}$. Therefore for
$t\in[t_{1},t_{2}]$,
$\tau_{\mathbf{F}}^{(1)}(t)=\tau_{\mathbf{F}}^{(2)}(t)=\tau_{1}(t)$. Now
$[t_{1},t_{2}]\subseteq\mathcal{S}(F_{1})$ implies
$C_{\mathbf{F}}^{(1)}(\cdot)$ is constant in $[t_{1},t_{2}]$. Hence
$(C_{\mathbf{F}}^{(1)})^{\prime}(t)=\tau_{1}^{\prime}(t)-\gamma_{1}=0$ in
$(t_{1},t_{2})$, implying $\tau_{1}^{\prime}(t)=\gamma_{1}$. As a result, in
$(t_{1},t_{2})$,
$(C_{\mathbf{F}}^{(2)})^{\prime}(t)=\tau_{1}^{\prime}(t)-\gamma_{2}=\gamma_{1}-\gamma_{2}\neq
0$. Now if $\gamma_{1}>\gamma_{2}$, class 2 user arriving at time $t_{2}$ will
be better off arriving at time $t_{1}$ and vice-versa when
$\gamma_{1}<\gamma_{2}$.

$\\{F_{1},F_{2}\\}$ cannot be an EAP in both the situations.

(3) We consider two separate situations for proving $\mathcal{S}(F_{1})$ is an
interval:

  * •

If $\mu_{1}\gamma_{1}\neq\mu_{2}\gamma_{2}$: On assuming contradiction, there
exists $t_{1},t_{2}\in\mathcal{S}(F_{1})$ such that,
$F_{1}(t_{1})=F_{1}(t_{2})$. We must have $t_{2}<T_{1,f}$, otherwise,
$T_{1,f}$ will be an isolated point in $\mathcal{S}(F_{1})$. Since
$\mathcal{S}(F_{1})\cup\mathcal{S}(F_{2})$ is an interval, we must have
$[t_{1},t_{2}]\subseteq\mathcal{S}(F_{2})$. Also, we must have
$[t_{1},t_{2}]\subseteq E_{1}$, since a positive mass of class 1 users arrive
after $t_{2}$. This implies, class 2 users will be arriving at queue 2 at a
rate $\mu_{1}>\mu_{2}$ in $[\tau_{1}(t_{1}),\tau_{1}(t_{2})]$ and therefore
$[\tau_{1}(t_{1}),\tau_{1}(t_{2})]\subseteq\overline{E_{2}}$. Using Lemma A.2
and the definition of EAP, in $[t_{1},t_{2}]$,
$(C_{\mathbf{F}}^{(2)})^{\prime}(t)=(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)-\gamma_{2}=\frac{F_{2}^{\prime}(t)}{\mu_{2}}-\gamma_{2}=0$
a.e. implying $F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}$ a.e. Since
$[t_{1},t_{2}]\subseteq E_{1}$, by (3),
$\tau_{1}^{\prime}(t)=\frac{F_{2}^{\prime}(t)}{\mu_{1}}=\frac{\mu_{2}\gamma_{2}}{\mu_{1}}$
a.e. in $[t_{1},t_{2}]$. As a result,
$(C_{\mathbf{F}}^{(1)})^{\prime}(t)=\tau_{1}^{\prime}(t)-\gamma_{1}=\frac{\mu_{2}\gamma_{2}}{\mu_{1}}-\gamma_{1}$
a.e. in $[t_{1},t_{2}]$. Now if $\mu_{1}\gamma_{1}>\mu_{2}\gamma_{2}$, class 1
user arriving at time $t_{1}$ will be strictly better off arriving at time
$t_{2}$ and vice-versa if $\mu_{1}\gamma_{1}<\mu_{2}\gamma_{2}$. Therefore
$\\{F_{1},F_{2}\\}$ will not be an EAP.

  * •

If $\mu_{1}\gamma_{1}=\mu_{2}\gamma_{2}$: Since $\mu_{1}>\mu_{2}$,
$\mu_{1}\gamma_{1}=\mu_{2}\gamma_{2}$ implies $\gamma_{1}<\gamma_{2}$. By 2nd
statement of the lemma, $\mathcal{S}(F_{2})$ must be the interval
$[T_{2,a},T_{2,f}]$. By Lemma A.3, $\mathcal{S}(F_{1})$ and
$(T_{2,a},T_{2,f})$ are disjoint and their union is an interval. As a result,
$\mathcal{S}(F_{1})$ is union of two intervals, one ending at $T_{2,a}$ and
the other one starting from $T_{2,f}$. We now show that $\mathcal{S}(F_{1})$
has no element larger than $T_{2,f}$. This implies that $\mathcal{S}(F_{1})$
is an interval ending at $T_{2,a}$. For this, we again assume a contradiction
and suppose that there exists $T>T_{2,f}$ such that
$[T_{2,f},T]\subseteq\mathcal{S}(F_{1})$. By Lemma A.4, queue 2 must be empty
at $\tau_{1}(T_{2,f})$. Therefore for $t\in[T_{2,f},T]$,
$\tau_{\mathbf{F}}^{(1)}(t)=\tau_{\mathbf{F}}^{(2)}(t)=\tau_{1}(t)$. Since
$[T_{2,f},T]\subseteq\mathcal{S}(F_{1})$, we will have
$(C_{\mathbf{F}}^{(1)})^{\prime}(t)=\tau_{1}^{\prime}(t)-\gamma_{1}=0$
implying $\tau_{1}^{\prime}(t)=\gamma_{1}$ in $[T_{2,f},T]$. Using this, in
$[T_{2,f},T]$,
$(C_{\mathbf{F}}^{(2)})^{\prime}(t)=\tau_{1}^{\prime}(t)-\gamma_{2}=\gamma_{1}-\gamma_{2}<0$.
Hence, the class 2 user arriving at $T_{2,f}$ is strictly better off arriving
at $T$, implying that $\\{F_{1},F_{2}\\}$ is not an EAP. ∎

By Lemma 3.2, for every EAP $\\{F_{1},F_{2}\\}$, we must have
$\mathcal{S}(F_{1})=[T_{1,a},T_{1,f}]$, $\mathcal{S}(F_{2})=[T_{2,a},T_{2,f}]$
and their union must be an interval.

Proof of Lemma 3.3: If $t\in(T_{1,a},T_{1,f})\cap(T_{2,a},T_{2,f})$, the
statement follows from Lemma A.1. Otherwise, we can obtain $\delta>0$ such
that either $[t,t+\delta]$ or
$[t-\delta,t]\subseteq(T_{2,a},T_{2,f})/(T_{1,a},T_{1,f})$. Now if $t\in
E_{1}$, we can choose $\delta>0$ small enough such that
$[t-\delta,t+\delta]\subseteq E_{1}$ As a result,
$\tau_{1}(t-\delta)<\tau_{1}(t)<\tau_{1}(t+\delta)$ (by (3)) and class 2 users
arrive in queue 2 at a rate $\mu_{1}>\mu_{2}$ in
$[\tau_{1}(t),\tau_{1}(t+\delta)]$ or $[\tau_{1}(t-\delta),\tau_{1}(t)]$
implying that $\tau_{1}(t)\in\overline{E_{2}}$. Otherwise, if $t\in
E_{1}^{c}$, since a positive mass of class 2 users arrive in $(t,T_{2,f}]$, we
must have $t=\tau_{1}(t)\in E_{2}$. Therefore, the lemma stands proved. ∎

Proof of Lemma 3.4: By Lemma 3.3, if $t\in\mathcal{S}(F_{2})$,
$\tau_{1}(t)\in\overline{E_{2}}$, which by Lemma A.2 implies
$(C_{\mathbf{F}}^{(2)})^{\prime}(t)=\frac{F_{2}^{\prime}(t)}{\mu_{2}}-\gamma_{2}$
a.e. in $\mathcal{S}(F_{2})$. Since $C_{\mathbf{F}}^{(2)}(\cdot)$ is constant
in $\mathcal{S}(F_{2})$, we must have $F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}$
a.e. in $\mathcal{S}(F_{2})$.

Note that $t\in\mathcal{S}(F_{1})=[T_{1,a},T_{1,f}]$ implies
$t\in\overline{E_{1}}$. Therefore, by (3),
$(C_{\mathbf{F}}^{(1)})^{\prime}(t)=(\tau_{\mathbf{F}}^{(1)})^{\prime}(t)-\gamma_{1}=\frac{F_{1}^{\prime}(t)+F_{2}^{\prime}(t)}{\mu_{1}}-\gamma_{1}$
a.e. in $\mathcal{S}(F_{1})$. Since $C_{\mathbf{F}}^{(1)}(\cdot)$ is constant
in $\mathcal{S}(F_{1})$, we must have
$F_{1}^{\prime}(t)+F_{2}^{\prime}(t)=\mu_{1}\gamma_{1}$ a.e. in
$\mathcal{S}(F_{1})$. As $F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}$ a.e. in
$\mathcal{S}(F_{2})$, we must have,

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\begin{cases}\mu_{1}\gamma_{1}~{}~{}&\text{if}~{}t\in\mathcal{S}(F_{1})/\mathcal{S}(F_{2}),~{}\text{and},\\\
\mu_{1}\gamma_{1}-\mu_{2}\gamma_{2}~{}~{}&\text{if}~{}t\in\mathcal{S}(F_{1})\cap\mathcal{S}(F_{2}).\end{cases}$

Note that, the above arrival rates are positive a.e. because, by Lemma A.3 and
3.2, if $\mu_{1}\gamma_{1}\leq\mu_{2}\gamma_{2}$,
$\mathcal{S}(F_{1})\cap\mathcal{S}(F_{2})$ has zero Lebesgue measure. ∎

######  Lemma A.5.

(Second statement of Lemma 3.5) In the EAP, if
$\mu_{1}\gamma_{1}>\mu_{2}\gamma_{2}$ and
$\mathcal{S}(F_{1})=[T_{1,a},T_{1,f}]$, then queue 1 will have zero waiting
time at $T_{1,f}$.

###### Proof.

Assume a contradiction, i.e., $T_{1,f}\in E_{1}$ with
$\mu_{1}\gamma_{1}>\mu_{2}\gamma_{2}$. Two situations are possible:

  * •

If $(T_{1,f},\infty)\cap\mathcal{S}(F_{2})=\emptyset$, by (3),
$\tau_{\mathbf{F}}^{(1)}(T_{1,f})=\tau_{\mathbf{F}}^{(1)}(T_{idle})$, where
$T_{idle}>T_{1,f}$ is the time queue 1 empties after $T_{1,f}$. Hence, the
class 1 user arriving at $T_{1,f}$ is strictly better off arriving at
$T_{idle}$.

  * •

If a positive mass of class 2 users arrive after $T_{1,f}$, by Lemma 3.2 and
3.4, they will arrive over an interval $[T_{1,f},T]$ at rate
$\mu_{2}\gamma_{2}$, where $T>T_{1,f}$. Therefore, picking
$\delta\in(0,T-T_{1,f})$ sufficiently small, we can have
$[T_{1,f},T_{1,f}+\delta]\subseteq E_{1}$. By (3), for
$t\in[T_{1,f},T_{1,f}+\delta]$,
$(C_{\mathbf{F}}^{(1)})^{\prime}(t)=\tau_{1}^{\prime}(t)-\gamma_{1}=\frac{F_{2}^{\prime}(t)}{\mu_{1}}-\gamma_{1}=\frac{\mu_{2}\gamma_{2}}{\mu_{1}}-\gamma_{1}<0$
a.e. Hence the class 1 user arriving at $T_{1,f}$ will be strictly better off
arriving at $T_{1,f}+\delta$.

For both the situations above, we get $\\{F_{1},F_{2}\\}$ will not be an EAP.
∎

Proof of Lemma 3.5: Lemma 3.5 follows from Lemma A.4 and A.5. ∎

Proof of Lemma 3.1: By Lemma A.3 and 3.2, we get
$\mu_{1}\leq\mu_{2}\cdot\max\\{1,\frac{\gamma_{2}}{\gamma_{1}}\\}$ is
sufficient for $[T_{1,a},T_{1,f}]$ and $[T_{2,a},T_{2,f}]$ to have disjoint
interiors. Proving that the condition is necessary follows from the argument
after Lemma 3.5 in Section 3.1. Hence Lemma 3.1 stands proved. ∎

Proof of Lemma 3.6: (1) If $T_{1,f}=T_{2,a}$, queue 1 is empty at $T_{1,f}$
(by Lemma 3.5), making the network empty at $T_{1,f}$. As a result, every
class 2 user will be strictly better off arriving at $T_{1,f}$ and
$\mathbf{F}$ will not be an EAP. Therefore, the only other possibility is
$T_{2,f}=T_{1,a}$.

(2) On assuming a contradiction, if $T_{2,f}<T_{1,f}$, by Lemma 3.1, we must
have $T_{2,f}\in(T_{1,a},T_{1,f})$. Since group 1 users will arrive in
$[T_{2,f},T_{1,f}]$, we must have
$[T_{2,f},T_{1,f}]\subseteq\overline{E_{1}}$. Using Lemma A.4, queue 2 has a
zero waiting time for $t\geq\tau_{1}(T_{2,f})$ and as a consequence
$\tau_{\mathbf{F}}^{(2)}(t)=\tau_{1}(t)$ for $t\geq T_{2,f}$. Therefore, for
$t\in[T_{2,f},T_{1,f}]$,

$\displaystyle(C^{(2)}_{\mathbf{F}})^{\prime}(t)$
$\displaystyle=(\tau_{F}^{(2)})^{\prime}(t)-\gamma_{2}=\tau_{1}^{\prime}(t)-\gamma_{2}$
$\displaystyle=\frac{F_{1}^{\prime}(t)}{\mu_{1}}-\gamma_{2}~{}~{}$ (using (3)
and the fact that $[T_{2,f},T_{1,f}]\in\overline{E_{1}}$)
$\displaystyle=\gamma_{1}-\gamma_{2}<0.~{}~{}$ (using Lemma 3.4).

Thus, the group 2 user arriving at $T_{2,f}$ will be strictly better off by
arriving at $T_{1,f}$. Hence $\mathbf{F}$ will not be an EAP.

(3) Let $T=\min\left\\{T_{1,f},T_{2,f}\right\\}$. By Lemma 3.1,
$\max\\{T_{1,a},T_{2,a}\\}<T$. If we assume contradiction to the statement, we
must have $T_{1,a}\leq T_{2,a}<T$. As a result, class 2 users are arriving in
$[T_{2,a},T]$ alongside class 1 users. Using Lemma 3.4, for every
$t\in[T_{2,a},T]$,

$\displaystyle F_{2}^{\prime}(t)$
$\displaystyle=\mu_{2}\gamma_{2},~{}\text{and},$ $\displaystyle
F_{1}^{\prime}(t)$ $\displaystyle=\mu_{1}\gamma_{1}-\mu_{2}\gamma_{2}.$

Moreover, for $t\in[T_{2,a},T]$, we have $A_{2}(\tau_{1}(t))=F_{2}(t)$. Again
$[T_{2,a},T]\subseteq\mathcal{S}(F_{1})$ implies
$[T_{2,a},T]\subseteq\overline{E_{1}}$ and therefore by (3)
$\tau_{1}^{\prime}(t)=\frac{F_{1}^{\prime}(t)+F_{2}^{\prime}(t)}{\mu_{1}}=\gamma_{1}$
a.e. in $[T_{2,a},T]$. Hence,
$A_{2}^{\prime}(\tau_{1}(t))=\frac{F_{2}^{\prime}(t)}{\tau_{1}^{\prime}(t)}=\mu_{2}\frac{\gamma_{2}}{\gamma_{1}}<\mu_{2}$
a.e. in $[T_{2,a},T]$. This implies that class 2 users are arriving at queue 2
at a rate $<\mu_{2}$ from the time when queue 2 starts serving them, i.e.,
$\tau_{1}(T_{2,a})$. Therefore $Q_{2}(t)=0$ for all
$t\in[\tau_{1}(T_{2,a}),\tau_{1}(T)]$, which contradicts Lemma A.1. ∎

####  A.1.1 Proof of Theorem 3.1

Below we mention those parts of the proof of Theorem 3.1 which were not
covered in the proof sketch mentioned in Section 3.1. Of the skipped portion
is the proof of existence and uniqueness of EAP for case 3,
$\gamma_{1}>\gamma_{2}$, owing to its similarity in arguments with case 2
$\gamma_{2}>\gamma_{1}>\frac{\mu_{2}}{\mu_{1}}\cdot\gamma_{2}$. Here, we cover
those portions of the proof for each of the three cases in which the theorem
statement is divided.

Case 1 $\gamma_{1}\leq\frac{\mu_{2}}{\mu_{1}}\gamma_{2}$: For convenience of
the reader, we mention the unique candidate we obtained by Lemma 3.4 and 3.7:

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\mu_{1}\gamma_{1}~{}\text{if}~{}t\in[T_{1,a},T_{1,f}]~{}\text{and}~{}F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}~{}\text{if}~{}t\in[T_{1,f},T_{2,f}].$
(18)

We first verify that, when the two classes arrive by the unique remaining
candidate profile, for both the classes $i=1,2$ cost derivative satisfies 1)
$(C_{\mathbf{F}}^{(i)})^{\prime}(t)\leq 0$ in $(-\infty,T_{i,a})$, 2)
$(C_{\mathbf{F}}^{(i)})^{\prime}(t)=0$ in $[T_{i,a},T_{i,f}]$, and 3)
$(C_{\mathbf{F}}^{(i)})^{\prime}(t)\geq 0$ in $(T_{i,f},\infty)$. The
preceding statement implies both the classes have their cost constant on the
support interval and higher outside of it, implying the candidate is an EAP.
Following our agenda, we go by the following sequence of arguments.

  * •

In $(-\infty,T_{1,a}]$: $\tau_{\mathbf{F}}^{(i)}(t)=0$ for both classes
$i\in\\{1,2\\}$ in $(-\infty,T_{1,a}]$. As a result,
$(C_{\mathbf{F}}^{(i)})^{\prime}(t)=-\gamma_{i}<0$ in $(-\infty,T_{1,a}]$.

  * •

In $[T_{1,a},T_{1,f}]$: Queue 1 stays engaged in $[T_{1,a},T_{1,f}]$, since
$A_{1}(t)=F_{1}(t)>\mu_{1}\cdot\max\\{t,0\\}$ in $[T_{1,a},T_{1,f}]$. Hence by
(3), for both the classes $i\in\\{1,2\\}$,
$(C_{\mathbf{F}}^{(i)})^{\prime}(t)=\frac{F_{1}^{\prime}(t)}{\mu_{1}}-\gamma_{i}=\gamma_{1}-\gamma_{i}$.
As a result, for $i=1$, $(C_{\mathbf{F}}^{(1)})^{\prime}(t)=0$ and for $i=2$,
$(C_{\mathbf{F}}^{(2)})^{\prime}(t)=\gamma_{1}-\gamma_{2}<0$.

  * •

In $[T_{1,f},T_{2,f}]$: Since $\mu_{1}\cdot
T_{2,f}=\Lambda_{1}+\frac{\mu_{1}}{\mu_{2}}\Lambda_{2}>\Lambda_{1}+\Lambda_{2}=A_{1}(T_{2,f})$,
queue 1 empties at some time $T\in(T_{1,f},T_{2,f}]$. As class 2 users arrive
at a constant rate of $\mu_{2}\gamma_{2}$ in $[T_{1,f},T_{2,f}]$, queue 1
stays engaged in $[T_{1,f},T]$ and empty in $[T,T_{2,f}]$. Therefore, in
$[T_{1,f},T]$, by (3),
$(C_{\mathbf{F}}^{(1)})^{\prime}(t)=\frac{F_{2}^{\prime}(t)}{\mu_{1}}-\gamma_{1}=\frac{\mu_{2}\gamma_{2}-\mu_{1}\gamma_{1}}{\mu_{1}}\geq
0$ and in $(T,T_{2,f}]$, since queue 1 is empty,
$(C_{\mathbf{F}}^{(1)})^{\prime}(t)=1-\gamma_{1}\geq 0$. Now we argue that
queue 2 remains engaged in $[\tau_{1}(T_{1,f}),T_{2,f}]$ by considering two
parts separately:

    * –

In $[\tau_{1}(T_{1,f}),T]$, class 2 users arrive at queue 2 from queue 1 at
rate $\mu_{1}>\mu_{2}$ in that period, making queue 2 engaged.

    * –

In $[T,T_{2,f}]$, since $A_{2}^{\prime}(t)=\mu_{2}\gamma_{2}<\mu_{2}$,
$A_{2}(t)-\mu_{2}\cdot(t-\tau_{1}(T_{1,f}))$ is a decreasing function.
Combining this with the fourth equation
$A_{2}(T_{2,f})=\mu_{2}\cdot(T_{2,f}-\tau_{1}(T_{1,f}))$ in the identified
linear system, we get $A_{2}(t)>\mu_{2}\cdot(t-\tau_{1}(T_{1,f}))$ in
$[T,T_{2,f})$, implying queue 2 stays engaged.

Therefore, by (3), for $t\in[T_{1,f},T_{2,f}]$,
$\tau_{\mathbf{F}}^{(2)}(t)=\tau_{2}(\tau_{1}(t))=\tau_{1}(T_{1,f})+\frac{A_{2}(\tau_{1}(t))}{\mu_{2}}=\frac{\Lambda_{1}}{\mu_{1}}+\frac{F_{2}(t)}{\mu_{2}}$.
Hence,
$(C_{\mathbf{F}}^{(2)})^{\prime}(t)=(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)-\gamma_{2}=\frac{F_{2}^{\prime}(t)}{\mu_{2}}-\gamma_{2}=0$
in $[T_{1,f},T_{2,f}]$. Upon summarizing, for $t\in[T_{1,f},T_{2,f}]$, we get
$(C_{\mathbf{F}}^{(1)})^{\prime}(t)\geq 0$ and
$(C_{\mathbf{F}}^{(2)})^{\prime}(t)=0$.

  * •

In $[T_{2,f},\infty)$: By the last step, both the queues stay empty after
$T_{2,f}$. As a result, for both the classes $i\in\\{1,2\\}$,
$(C_{\mathbf{F}}^{(i)})^{\prime}(t)=1-\gamma_{i}>0$ in $[T_{2,f},\infty)$.

Case 2 $\frac{\mu_{2}}{\mu_{1}}\gamma_{2}<\gamma_{1}<\gamma_{2}$: Skipped
parts of the proof of Lemma 3.8: Identifying the unique candidate for Type II:
For every EAP under Type II, we obtain the following system of equations to be
satisfied by the support boundaries $T_{1,a},T_{1,f},T_{2,a},T_{2,f}$:

  1. 1.

By Lemma 3.4, $F_{1}^{\prime}(t)=\mu_{1}\gamma_{1}-\mu_{2}\gamma_{2}$ in
$[T_{1,a},T_{1,f}]$, giving us:
$T_{1,f}=T_{1,a}+\frac{\Lambda_{1}}{\mu_{1}\gamma_{1}-\mu_{2}\gamma_{2}}$.

  2. 2.

By Lemma 3.4, $F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}$ in $[T_{2,a},T_{2,f}]$,
giving us: $T_{2,f}=T_{2,a}+\frac{\Lambda_{2}}{\mu_{2}\gamma_{2}}$.

  3. 3.

Applying the argument used for getting the third equation of Type I, we must
have $F_{1}(T_{1,f})+F_{2}(T_{1,f})=\mu_{1}T_{1,f}$. Plugging in
$F_{1}(T_{1,f})=\Lambda_{1}$ and
$F_{2}(T_{1,f})=\mu_{2}\gamma_{2}(T_{1,f}-T_{2,a})$ (by Lemma 3.4), we get:
$\Lambda_{1}+\mu_{2}\gamma_{2}(T_{1,f}-T_{2,a})=\mu_{1}T_{1,f}$.

  4. 4.

By an argument similar to the one used for getting the fourth equation of Type
I, we have $\mu_{2}\cdot(\tau_{1}(T_{2,f})-\tau_{1}(T_{2,a}))=\Lambda_{2}$.
Since queue 1 is empty at $T_{1,f}$ (by Lemma 3.5) and class 2 users arrive at
rate $\mu_{2}\gamma_{2}<\mu_{1}$ (by Lemma 3.4), queue 1 stays empty at
$T_{2,f}$, causing $\tau_{1}(T_{2,f})=T_{2,f}$. Queue 1 serves the first class
2 user at time zero, causing $\tau_{1}(T_{2,a})=0$. Plugging these in, we get:
$T_{2,f}=\frac{\Lambda_{2}}{\mu_{2}}$. ∎

The solution to the above system of equations is in (3.). The support
boundaries in (3.) must satisfy $T_{2,a}<T_{1,a}<T_{1,f}\leq T_{2,f}$ to
represent an EAP under Type II. Imposing $T_{1,a}>T_{2,a}$ on (3.), we get the
condition
$\Lambda_{1}<\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right)\Lambda_{2}$.

Moreover, if
$\Lambda_{1}<\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right)\Lambda_{2}$,
(3.) satisfies $T_{2,a}<T_{1,a}<T_{1,f}\leq T_{2,f}$ and upon plugging in
arrival rates from Lemma 3.4, we get a candidate having arrival rates and
support boundaries same as the joint arrival profile mentioned under case 2b
of Theorem 3.1. This candidate satisfies
$F_{1}(T_{1,f})=\Lambda_{1},~{}F_{2}(T_{2,f})=\Lambda_{2}$ and will be the
only Type II candidate to qualify as an EAP. Upon proving that this identified
Type II candidate is an EAP, the second statement of Lemma 3.8 will follow.

Proving that the unique candidate obtained is an EAP: For convenience of the
reader we mention the candidates we were left with for both the types:

  1. 1.

If
$\Lambda_{1}\geq\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right)\Lambda_{2}$,
the unique Type I candidate is:

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\begin{cases}\mu_{1}\gamma_{1}~{}~{}&\text{if}~{}t\in[T_{1,a},T_{2,a}),\\\
\mu_{1}\gamma_{1}-\mu_{2}\gamma_{2}~{}~{}&\text{if}~{}t\in[T_{2,a},T_{1,f}],\end{cases}~{}\text{and}~{}F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}~{}~{}\text{if}~{}t\in[T_{2,a},T_{2,f}]$
(19)

where $T_{1,a},T_{1,f},T_{2,a},T_{2,f}$ are in ( ‣ 2.).

  2. 2.

If
$\Lambda_{1}<\frac{1-\gamma_{2}}{1-\gamma_{1}}\left(\frac{\mu_{1}\gamma_{1}}{\mu_{2}\gamma_{2}}-1\right)\Lambda_{2}$,
the unique Type II candidate is:

$\displaystyle F_{1}^{\prime}(t)$
$\displaystyle=\mu_{1}\gamma_{1}-\mu_{2}\gamma_{2}~{}~{}\text{if}~{}t\in[T_{2,a},T_{1,f}],~{}\text{and}~{}F_{2}^{\prime}(t)=\mu_{2}\gamma_{2}~{}~{}\text{if}~{}t\in[T_{2,a},T_{2,f}]$
(20)

where $T_{1,a},T_{1,f},T_{2,a},T_{2,f}$ are in (3.).

By the following sequence of arguments, for both the types, we argue that if
users of the two classes arrive by the unique remaining candidate, both
classes $i=1,2$ have their cost derivative satisfying:
$(C_{\mathbf{F}}^{(i)})^{\prime}(t)\leq 0$ in $(-\infty,T_{i,a})$,
$(C_{\mathbf{F}}^{(i)})^{\prime}(t)=0$ in $[T_{i,a},T_{i,f}]$, and
$(C_{\mathbf{F}}^{(i)})^{\prime}(t)\geq 0$ in $(T_{i,f},\infty)$. This will
imply, for both the classes, cost is constant in the support interval and
higher outside and hence the candidate is an EAP.

  1. 1.

In $(-\infty,\min\\{T_{1,a},T_{2,a}\\}]$: Note that for
$t\in(-\infty,\min\\{T_{1,a},T_{2,a}\\}]$, $\tau_{\mathbf{F}}^{(i)}(t)=0$ for
both the classes $i\in\\{1,2\\}$. As a result,
$(C_{\mathbf{F}}^{(i)})^{\prime}(t)=-\gamma_{i}<0$ for $i\in\\{1,2\\}$.

  2. 2.

In $[\min\\{T_{1,a},T_{2,a}\\},T_{1,f}]$: Obtained candidates of both the
types satisfy $A_{1}^{\prime}(t)=F_{1}^{\prime}(t)+F_{2}^{\prime}(t)<\mu_{1}$
in $[\min\\{T_{1,a},T_{2,a}\\},T_{1,f}]$, making $A_{1}(t)-\mu_{1}t$
decreasing in $[0,T_{1,f}]$. Since both the types satisfy
$A_{1}(T_{1,f})=\mu_{1}T_{1,f}$, the preceding statement imply
$A_{1}(t)>\mu_{1}t$ in $[0,T_{1,f})$ and therefore, queue 1 is engaged in
$[\min\\{T_{1,a},T_{2,a}\\},T_{1,f}]$ and empty after $T_{1,f}$. Using (3) and
the arrival rates from (19) and (20), we get
$(C_{\mathbf{F}}^{(1)})^{\prime}(t)=\tau_{1}^{\prime}(t)-\gamma_{1}=\frac{F_{1}^{\prime}(t)+F_{2}^{\prime}(t)}{\mu_{1}}-\gamma_{1}=0$
for $t\in[\min\\{T_{1,a},T_{2,a}\\},T_{1,f}]$. For analyzing the cost of the
second class, we consider the two types separately:

     * •

In Type I ($T_{1,a}\leq T_{2,a}<T_{1,f}$): In $[T_{1,a},T_{2,a}]$,
$(C_{\mathbf{F}}^{(2)})^{\prime}(t)=\tau_{1}^{\prime}(t)-\gamma_{2}=\frac{F_{1}^{\prime}(t)+F_{2}^{\prime}(t)}{\mu_{1}}-\gamma_{2}=\gamma_{1}-\gamma_{2}<0$.
Upon observing $A_{2}(\tau_{1}(t))=F_{2}(t)$, we can write using chain rule
that
$A_{2}^{\prime}(\tau_{1}(t))=\frac{(A_{2}\circ\tau_{1})^{\prime}(t)}{\tau_{1}^{\prime}(t)}=\frac{F_{2}^{\prime}(t)}{\tau_{1}^{\prime}(t)}$,
whenever the derivatives exists. Now for $t\in[T_{2,a},T_{1,f}]$, using (3),
rate of arrival of class 2 users in queue 2 at $\tau_{1}(t)$ is
$A_{2}^{\prime}(\tau_{1}(t))=\frac{F_{2}^{\prime}(t)}{\tau_{1}^{\prime}(t)}=\mu_{1}\cdot\frac{F_{2}^{\prime}(t)}{F_{1}^{\prime}(t)+F_{2}^{\prime}(t)}=\frac{\mu_{2}\gamma_{2}}{\gamma_{1}}>\mu_{2}$.
As a result, queue 2 remains engaged in $[\tau_{1}(T_{2,a}),T_{1,f}]$. With
this, the time of service of class 2 users arriving in $[T_{2,a},T_{1,f}]$ is
$\tau_{\mathbf{F}}^{(2)}(t)=\tau_{2}(\tau_{1}(t))=\tau_{1}(T_{2,a})+\frac{A_{2}(\tau_{1}(t))}{\mu_{2}}=\tau_{1}(T_{2,a})+\frac{F_{2}(t)}{\mu_{2}}$.
Using this and the arrival rates from (19),
$(C_{\mathbf{F}}^{(2)})^{\prime}(t)=(\tau_{\mathbf{F}}^{(2)})^{\prime}(t)-\gamma_{2}=\frac{F_{2}^{\prime}(t)}{\mu_{2}}-\gamma_{2}=0$
in $[T_{2,a},T_{1,f}]$.

     * •

In Type II ($T_{2,a}<T_{1,a}<T_{1,f}$): In $[T_{2,a},T_{1,a}]$, rate of
arrival of class 2 users at queue 2 at time $\tau_{1}(t)$ is
$\mu_{1}>\mu_{2}$, and $\tau_{1}(T_{2,a})=0$. As a result, queue 2 has a
positive waiting queue at $\tau_{1}(T_{1,a})$. Following a calculation similar
to the one used in the previous step for Type I, rate of arrival of class 2
users at queue 2 at time $\tau_{1}(t)$ is
$\frac{\mu_{2}\gamma_{2}}{\gamma_{1}}\geq\mu_{2}$ when
$t\in[T_{1,a},T_{1,f}]$. The last two statements imply queue 2 has positive
waiting time in $(0,T_{1,f}]$. Using this, time of service of class 2 users
arriving in $[T_{2,a},T_{1,f}]$ is
$\tau_{\mathbf{F}}^{(2)}(t)=\tau_{2}(\tau_{1}(t))=\tau_{1}(T_{2,a})+\frac{A_{2}(\tau_{1}(t))}{\mu_{2}}=\frac{F_{2}(t)}{\mu_{2}}$
and as a result,
$(C_{\mathbf{F}}^{(2)})^{\prime}(t)=\frac{F_{2}^{\prime}(t)}{\mu_{2}}-\gamma_{2}=0$.

  3. 3.

In $[T_{1,f},T_{2,f}]$: Queue 1 remains empty in this region. On the other
hand, queue 2 remains engaged in $[T_{1,f},T_{2,f}]$, since