# User equilibria in heterogeneous discriminatory processor sharing queues

Dieter Fiems, Balakrishna Prabhu

► To cite this version:

Dieter Fiems, Balakrishna Prabhu. User equilibria in heterogeneous discriminatory processor sharing queues. Performance Evaluation, 2025, 170, pp.102510. 10.1016/j.peva.2025.102510. hal-05333820

HAL Id: hal-05333820

https://hal.science/hal-05333820v1

Submitted on 28 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# User equilibria in Heterogeneous Discriminatory Processor Sharing Queues*

Dieter Fiems¹ and Balakrishna J. Prabhu²

¹Ghent University, Departement TELIN, Gent, Belgium

²LAAS CNRS, University of Toulouse, CNRS, Toulouse, France.

email: dieter.fiems@UGent.be, balakrishna.prabhu@laas.fr

October 28, 2025

## Abstract

We consider a strategic routing game for a two-class discriminatory processor-sharing queue with an additional cost for joining the premium class. We show that, depending on the specific parameters of the system, various equilibria can coexist, including equilibria where the queueing system is not ergodic for the equilibrium traffic split. We also investigate how the server can select the priority of the classes and the fees charged to the customers to maximise its revenue. We then investigate learning strategies that converge to particular equilibria. Finally, we study how the elasticity of the traffic demand affects the equilibrium solutions.

## 1 Introduction

By introducing service differentiation, customers are offered a choice between different service levels at distinct price points. Customers then trade between the cost of the different service levels and the benefits they bring, for example, in terms of reductions in sojourn times. This trade-off determines the willingness of customers to pay for these services and, therefore, also the revenue of the service provider. Queueing theory provides various options to achieve service differentiation, including preemptive and non-preemptive priority disciplines [1], parallelised services and discriminatory processor sharing [2, 3].

In this paper, we explore strategic routing within the context of coupled resources in which the capacity available at one resource depends upon the demand at all the resources in the network. In particular, we consider two resources coupled by the discriminatory processor-sharing (DPS) mechanism [4]. Processor-sharing queueing systems, including both discriminatory and generalised processor-sharing variants, serve as useful models for resource sharing

<footnote>*This is an extended version of the paper "Strategic Routing in Heterogeneous Discriminatory Process Sharing Queues" that appeared at NETGCOOP 2024.</footnote>
in networking and computer systems. Notably, processor-sharing queues have been effectively utilised to analyse flow-level resource sharing on the Internet, as demonstrated in studies by Massoulié and Roberts [5, 6, 7]. The body of research on processor-sharing queueing systems is extensive. For an in-depth review of the theory and its applications, we recommend the surveys by Yashkov and Yashkova [8] on processor sharing and by Altman et al. [9] on discriminatory processor sharing. In the following discussion, we will specifically concentrate on discriminatory processor sharing and the game-theoretic analysis of processor-sharing queueing systems. Note that the uncoupled-resource model is a special case of the coupled-resource one and has a larger body of literature due to its ease of analysis.

The analysis of routing games with uncoupled resources started with the seminal work of Orda et al. [10], who gave conditions for the existence and uniqueness of the Nash equilibrium. Since then, a large body of literature has appeared on different variants of this game. Altman and Shimkin [11] examine an observable processor-sharing game in which customers decide whether to join the processor-sharing queue after observing the number of customers already present. A similar model is studied by Ben-Shahar et al. [12] under the assumption that customers have heterogeneous preferences. Heterogeneity means that one customer may join after observing a certain number of customers while another customer may not join after observing the same number of customers. In a concert queueing game, customers choose their arrival time to minimise a cost that depends on the arrival times of other customers. In [13], customers select their arrival times in a processor-sharing queue, where the cost is influenced by both the sojourn time and the deviation from their preferred departure time. Processor-sharing games are also analysed as models for distributed non-cooperative load balancing. In these load-balancing scenarios, customers either choose a server from a set of servers [14] or are directed to a server by a limited number of dispatchers [14, 15]. Finally, a time- and load-dependent fluid processor-sharing queue is used to model the use of park-and-ride systems during rush hour [16].

In comparison, the coupled-resource game has received less attention. Hayel and Tuffin [2] study a DPS queueing game where the utility of joining different classes is a non-negative, decreasing function of the sojourn time. They demonstrate the existence of a unique Wardrop equilibrium for DPS using these utility functions. Fiems [3] investigates revenue management for DPS queues, where the utility decreases linearly with sojourn times. The study shows that a DPS implementation is preferred over a strict priority discipline if customers are allowed to balk. If balking is not allowed, the optimal DPS discipline degenerates to a strict priority discipline, even if customers have heterogeneous evaluations of sojourn times. The work closest to the model of this paper is the one in [17] (see Section 3 in there), in which customers choose the probability of going to the higher-priority class in exchange for a payment. It is shown that the equilibrium is either a pure equilibrium or a mixed equilibrium, depending upon the cost. The former corresponds to all the customers going to one of the two classes while, in the latter, customers split non-trivially over the two classes.
The model and the results of [17] assume equal service rates for the two classes.

We conclude the literature review with some recent contributions on DPS queues. Vis *et al.* [18] investigate the DPS queue with joint batch arrivals in heavy traffic. They show that when the load tends to 1, the distribution of the DPS queue size vector tends to the product of a deterministic vector and a single exponentially distributed random variable. The authors in [19] derive approximations for the conditional mean sojourn time of the multiclass DPS queue with generally distributed service times. Finally, Kim [20] obtains an approximate expression for the conditional sojourn time distribution of the two-class M/M/1 DPS system with impatient customers. Some recent work investigates algorithmic approaches to assess the performance of DPS. Chis and Harrison [21] provide an approach to recursively calculate the higher-order moments for the M/M/1 DPS queue. The authors in [22] study state-space truncation techniques for solving multidimensional Markov chains. The authors obtain truncation bounds for the moments of the Markov chain and apply their technique to a DPS queue with multiple classes. Finally, Kim [23] discusses some results on the monotonicity properties of the weights in multiclass DPS queues and summarises various conjectures and counterexamples.

## 1.1 Contributions

We investigate a Markovian DPS queue where both classes have different service rates, and there is a fixed cost for joining the premium class. The players want to minimise their mean sojourn time and may want to pay a cost to get better service. The fact that the service rates are heterogeneous gives rise to types of equilibria that are different from the ones in [17]. We show that given the parameters of the DPS queue, multiple equilibria can coexist, including multiple “stable” equilibria (in the sense that customers converge to these equilibria if they start from a nearby strategy and selfishly minimise their cost). Further, there may even be a non-ergodic equilibrium (there is an incentive to converge to a traffic split where the queueing system is not ergodic). At this non-ergodic equilibrium, the queue is unstable, and the mean sojourn time of both the classes goes to infinity. This type of equilibrium appears to be specific to the coupled-resource model, and in particular to ones with different service rates. The closest result in the uncoupled-resource model that has a similar flavour is the one in [15], in which the Price of Anarchy goes to infinity when the cost of a resource goes to zero. However, for finite costs (as in our paper), instability does not seem to happen in the uncoupled-resource model.

We then restrict the parameter space of the DPS model to typical scenarios where the premium tier offers faster service as well as higher DPS weight factors and discuss how the service provider can optimise its revenue. We also study various extensions of the model. First, we study various approaches to how players learn their strategies, both learning in discrete time and continuous time. Finally, we study how traffic elasticity affects the equilibrium solutions. While elasticity does not rule out the presence of multiple equilibria, it does rule out non-ergodic equilibria.
<figure><img src="image_2.png" /><figcaption>Figure 1: Representation of the DPS queueing model</figcaption></figure>

## 1.2 Overview

The remainder of this paper is organised as follows. In the next section, we introduce the modelling assumptions and notation and recall the formulas for the sojourn times in a DPS queueing system. We then discuss the existence of multiple equilibria through numerical examples in Section 3. Discrete-time and continuous-time learning is studied in Section 4, while Section 5 introduces elastic demand. Finally, we conclude Section 6.

# 2 DPS queueing model

We consider a discriminatory processor-sharing queueing system with two classes as depicted in Figure 1. Non-strategic class 1 and class 2 customers arrive at the queues following Poisson processes with rates $κ_1$ and $κ_2$, respectively. In addition, strategic customers arrive at the queue following a Poisson process with rate $λ$ and select a class without observing the state of the queueing system. Let $λ_i$ denote the arrival rate of strategic customers that opt for class $i \in \{1, 2\}$, with $λ_1 + λ_2 = λ$. The class 1 and class 2 service times constitute a sequence of independent and identically exponentially distributed random variables with rates $μ_1$ and $μ_2$, respectively. Without loss of generality, we fix the DPS weight of class 1 and 2 to $γ$ and $1-γ$, respectively, for $γ \in [0, 1]$. For $γ = 0.5$, there is no differentiation between the classes, while for $γ = 1$ ($γ = 0$), the DPS discipline degenerates to a strict preemptive priority discipline for class 1 (class 2). This Markovian DPS queueing system admits a stationary solution provided that the load does not exceed the service capacity,

$$ \frac{1}{\mu_1}(\kappa_1 + \lambda_1) + \frac{1}{\mu_2}(\kappa_2 + \lambda_2) < 1. $$

If this is the case, the expected sojourn times $\bar{T}_1$ and $\bar{T}_2$ of class 1 and 2 equal [9],

$$ \bar{T}_1 = \frac{1}{\mu_1(1-\rho)} \left( 1 + \frac{\mu_1\rho_2(1-2\gamma)}{\mu_1\gamma(1-\rho_1) + \mu_2(1-\gamma)(1-\rho_2)} \right), \quad (1) $$

$$ \bar{T}_2 = \frac{1}{\mu_2(1-\rho)} \left( 1 - \frac{\mu_2\rho_1(1-2\gamma)}{\mu_1\gamma(1-\rho_1) + \mu_2(1-\gamma)(1-\rho_2)} \right), \quad (2) $$
with

$$ \rho_i = \frac{1}{\mu_i}(\lambda_i + \kappa_i), \quad \rho = \rho_1 + \rho_2. $$

We now study the fractions of strategic customers that opt for class 1 and class 2, respectively. To this end, we impose that there exist fractions $\lambda_1$ and $\lambda_2$ with $\lambda_1 + \lambda_2 = \lambda$ such that the queueing process is stationary ergodic. This is the case provided that

$$ \frac{\kappa_1}{\mu_1} + \frac{\kappa_2}{\mu_2} + \frac{\lambda}{\max(\mu_1, \mu_2)} < 1. $$

The rates $\lambda_1$ and $\lambda_2$ are now chosen such that none of the customers in these flows has an incentive to change to the other flow. Customers prefer class 1 over class 2 if $\bar{T}_1 + \delta < \bar{T}_2$. Here, $\delta$ represents a cost for accessing class 1. In other words, we study the rational split of the flows in Wardrop equilibrium. This notion is expressed mathematically as follows,

$$ \begin{cases} \bar{T}_1 + \delta \ge \bar{T}_2 & \text{if } \lambda_2 > 0, \\ \bar{T}_1 + \delta \le \bar{T}_2 & \text{if } \lambda_1 > 0. \end{cases} \qquad (3) $$

## 2.1 Ergodicity

To simplify notation, we can rewrite the expected sojourn times as follows,

$$ \bar{T}_1 = \frac{\beta_0 - (\mu_1 - \mu_2)(2\gamma - 1)\lambda_1}{(\beta_2 - (\mu_1 - \mu_2)\lambda_1)(\beta_3 - (2\gamma - 1)\lambda_1)}, \qquad (4) $$

$$ \bar{T}_2 = \frac{\beta_1 + (\mu_1 - \mu_2)(2\gamma - 1)\lambda_1}{(\beta_2 - (\mu_1 - \mu_2)\lambda_1)(\beta_3 - (2\gamma - 1)\lambda_1)}, \qquad (5) $$

with

$$ \beta_0 = \gamma(\kappa_1\mu_2 + 2\kappa_2\mu_1 - \kappa_2\mu_2 + 2\lambda\mu_1 - \lambda\mu_2 - \mu_1\mu_2 + \mu_2^2) \\ - \mu_1\kappa_2 + \kappa_2\mu_2 - \mu_1\lambda + \lambda\mu_2 - \mu_2^2, $$

$$ \beta_1 = \gamma(\kappa_1\mu_1 - 2\kappa_1\mu_2 - \kappa_2\mu_1 - \lambda\mu_1 - \mu_1^2 + \mu_1\mu_2) \\ + \mu_2\kappa_1 + \mu_1\kappa_2 + \mu_1\lambda - \mu_1\mu_2, $$

$$ \beta_2 = \mu_2\kappa_1 + \mu_1\kappa_2 + \mu_1\lambda - \mu_1\mu_2, $$

$$ \beta_3 = \gamma(\kappa_2 - \kappa_1 + \lambda + \mu_1 - \mu_2) - \kappa_2 - \lambda + \mu_2. $$

Using the notation above, we specify the range $\Omega$ of $\lambda_1$ for which the queueing process is stationary ergodic,

$$ \Omega = \begin{cases} (\beta_2/(\mu_1 - \mu_2), \lambda] \cap [0, \lambda], & \text{for } \mu_1 > \mu_2, \\ [0, \lambda], & \text{for } \mu_1 = \mu_2, \\ [0, \beta_2/(\mu_1 - \mu_2)) \cap [0, \lambda], & \text{for } \mu_1 < \mu_2. \end{cases} \qquad (6) $$
Note that for $\beta_2/(\mu_1 - \mu_2) = 0$ or $\beta_2/(\mu_1 - \mu_2) = \lambda$, the queueing process is not ergodic for $\lambda_1 = \beta_2/(\mu_1 - \mu_2)$. However, the queueing process is ergodic for $\lambda_1 = 0$ if $\beta_2/(\mu_1 - \mu_2) < 0$. A similar remark applies to the case $\lambda_1 = \lambda$.

In the remainder, we exclude the symmetric case $\gamma = 0.5$ and $\mu_1 = \mu_2$. In this case, there is neither fee nor service differentiation. We then have that all $\lambda_1 \in \Omega$ are Wardrop equilibria for $\delta = 0$, while $\lambda_1 = 0$ is an equilibrium for $\delta > 0$, and $\lambda_1 = \lambda$ is an equilibrium for $\delta < 0$.

## 2.2 Mixed equilibrium

We now focus on the existence of a mixed equilibrium. A mixed equilibrium lies either in the interior of $\Omega$ or at the non-zero boundary of $\Omega$ in case this boundary is not equal to $\lambda$. We refer to these types of equilibria as ergodic and non-ergodic equilibria. We discuss ergodic equilibria first.

Solving $\bar{T}_1 + \delta = \bar{T}_2$ leads to the following quadratic equation,

$$ \delta(2\gamma-1)(\mu_1-\mu_2)\lambda_1^2 - ((2\gamma-1)\delta\beta_2 + (\mu_1 - \mu_2)(\delta\beta_3 + 4\gamma - 2))\lambda_1 + \delta\beta_2\beta_3 + \beta_0 - \beta_1 = 0. $$

In the absence of an additional cost ($\delta = 0$), for equal service time ($\mu_1 = \mu_2$) or in the absence of service differentiation ($\gamma = \frac{1}{2}$), the quadratic equation simplifies to a linear equation. In this case, we have a single ergodic equilibrium at most.

In general, the quadratic equation may, however, possess two distinct solutions or possess no real-valued solutions in the interior of $\Omega$. Not every solution is stable, though, in the sense that if one slightly deviates from the equilibrium, there is no incentive to drift back towards the equilibrium. A mixed equilibrium is stable provided that

$$ \frac{\partial \bar{T}_1}{\partial \lambda_1} > \frac{\partial \bar{T}_2}{\partial \lambda_1}. \qquad (7) $$

If this inequality holds, an increase of $\lambda_1$ translates in longer sojourn times for the first queue, and hence, there is an incentive to join the second queue and drift towards the equilibrium.

The condition for stable equilibria considerably simplifies for specific instances. For $\gamma = 0.5$ and $\mu_1 \neq \mu_2$, some elementary calculations show that

$$ \frac{\partial \bar{T}_1}{\partial \lambda_1} / \frac{\partial \bar{T}_2}{\partial \lambda_1} = \frac{\mu_2}{\mu_1}. $$

Hence, any equilibrium with $\bar{T}_1 + \delta = \bar{T}_2$ is stable for $\mu_1 < \mu_2$ and unstable for $\mu_1 > \mu_2$. Moreover, for any $\gamma$ and for $\mu_1 = \mu_2$ we have by means on some elementary calculations,

$$ \frac{\partial \bar{T}_1}{\partial \lambda_1} / \frac{\partial \bar{T}_2}{\partial \lambda_1} = \frac{\bar{T}_1}{\bar{T}_2}. $$

In the equilibrium, we have $\bar{T}_1 + \delta = \bar{T}_2$. Hence, positive $\delta$ implies $\bar{T}_1 < \bar{T}_2$ and the equilibrium is not stable. Analogously, for negative $\delta$, we have a stable equilibrium.
## 2.3 Pure equilibria

First, consider the case $\mu_1 > \mu_2$. We have pure equilibrium for $\lambda_1 = \lambda$ provided that $\bar{T}_1 + \delta \le \bar{T}_2$. If $\beta_2/(\mu_1 - \mu_2) < 0$, we have a pure equilibrium at $\lambda_1 = 0$ provided that $\bar{T}_1 + \delta \ge \bar{T}_2$. Analogously, for $\mu_1 < \mu_2$, we have pure equilibrium for $\lambda_1 = 0$ provided that $\bar{T}_1 + \delta \ge \bar{T}_2$. If $\beta_2/(\mu_1 - \mu_2) > \lambda$, we have a pure equilibrium at $\lambda_1 = \lambda$ provided that $\bar{T}_1 + \delta \le \bar{T}_2$. Finally, for $\mu_1 = \mu_2$, the queues are stable for $\lambda_1 = 0$ and $\lambda_1 = \lambda$, and we have two pure equilibria.

A pure equilibrium is stable provided we do not have equality at the equilibrium. If the latter is the case, stability again requires that the customers have an incentive to drift towards the equilibrium; that is, the equilibrium is stable provided (7) holds.

## 2.4 Non-ergodic equilibria

Customers may have an incentive to drift towards a traffic mix such that the queueing process becomes non-ergodic. Now assume $\mu_1 \ne \mu_2$ and $\beta_2/(\mu_1 - \mu_2) \in [0, \lambda]$. Comparing the sojourn times for $\lambda_1 = \beta_2/(\mu_1 - \mu_2)$, we find

$$ \frac{\bar{T}_1}{\bar{T}_2} = \frac{\beta_0 - (\mu_1 - \mu_2)(2\gamma - 1)\lambda_1}{\beta_1 + (\mu_1 - \mu_2)(2\gamma - 1)\lambda_1}, $$

which simplifies into the surprisingly simple expression,

$$ \lim_{\lambda_1 \to \beta_2/(\mu_1 - \mu_2)} \frac{\bar{T}_1 + \delta}{\bar{T}_2} = \frac{(1 - \gamma)\mu_2}{\gamma\mu_1}. $$

Note that the limiting value does not depend on $\delta$ as both $\bar{T}_1$ and $\bar{T}_2$ grow to $\infty$ while $\delta$ remains finite. For $\mu_1 > \mu_2$, there is an incentive to drift towards the non-ergodic traffic mix if the right-hand side exceeds 1. Similarly, for $\mu_1 < \mu_2$, there is an incentive to drift towards the non-ergodic mix if the right-hand side is smaller than 1. Both non-ergodic equilibria are stable. If the right-hand side equals 1, we again have an equilibrium, and stability follows from evaluating

$$ \frac{\partial \bar{T}_1}{\partial \lambda_1} / \frac{\partial \bar{T}_2}{\partial \lambda_1}. $$

As one would most likely want to avoid non-ergodic equilibria, the former conditions easily translate into conditions for the DPS parameter $\gamma$. For $\mu_1 > \mu_2$, we impose $\gamma > \mu_2/(\mu_1 + \mu_2)$, while for $\mu_1 < \mu_2$, we need $\gamma < \mu_2/(\mu_1 + \mu_2)$. These conditions mean that there are bounds on prioritising the slower server.

## 2.5 Summary

From the discussion above, we may have up to two equilibria in the interior of $\Omega$ as well as up to two equilibria at the boundary. As both $\bar{T}_1$ and $\bar{T}_2$ are continuous functions of $\lambda_1$, we easily see that stable and unstable equilibria alternate when ordered (accounting for the multiplicity of the solutions of the
<figure><img src="image_3.png" /><figcaption>Figure 2: Different types of equilibria in the DPS game with additional cost</figcaption></figure>

quadratic equation). Moreover, by listing all possible combinations of pure, mixed and non-ergodic equilibria, we find that the total number of equilibria is at most three.

**3 Discussion**

From the results above, we have identified multiple different types of equilibrium scenarios. Figure 2 illustrates the different possibilities. For fig. 2a, we set $\gamma = 0.7$, $\kappa_1 = \kappa_2 = 0.2$, $\lambda = 1$, $\mu_1 = 2$, $\mu_2 = 1$ and $\delta = 20$. There is a single mixed stable equilibrium. The same arrival rates and service parameters are used in fig. 2b, but we now prioritise the second queue: $\gamma = 0.2$. In this case, the only (stable) equilibrium is obtained for $\lambda_1 = 0.6$, for which both queues grow. Customers have an incentive to opt for the slower queue. Note that the faster queue grows as well as the service share of the slower queue grows with the slower queue size. In fig. 2c, we retained all parameters apart from the constant cost $\delta$, which equals $-10$ in this figure. We now have a single mixed equilibrium, which is not stable. Just below and above the equilibrium solution, customers have an incentive to drift away from the equilibrium solution. Both $\lambda_1 = 0.6$ and $\lambda_1 = 1$ are equilibrium solutions, the former again corresponding to a non-ergodic queueing system as in figure 2(b). Finally, fig. 2d shows a scenario
with two mixed equilibria. The parameters are here chosen as follows: $\gamma = 0.78$, $\mu_1 = 2$, $\mu_2 = 1.82$, $\kappa_1 = \kappa_2 = 0.2$, $\lambda = 1.34$, and $\delta = 6$. We have two mixed equilibria and a pure equilibrium at $\lambda_1 = \lambda$. The leftmost mixed equilibrium and the pure equilibrium are stable, while the other mixed equilibrium is not.

<figure><img src="image_4.png" /><figcaption>Figure 3: Number and value of equilibria as a function of $\gamma$</figcaption></figure>

In Figure 3, we show how the number and the value of the equilibria vary with the priority $\gamma$. Figure 3a is plotted for the same parameters as figs 2a and 2b but with $\delta = 1$. There is only one stable equilibrium, which increases as $\gamma$ increases. Fig. 3b and 3c (resp.) are for parameters of fig. 2c and fig. 2d(resp.). In fig. 3b, there are initially three equilibria, of which the mixed one is unstable. Further, $\lambda_1 = 1$ is an equilibrium for all values of $\gamma$. As priority increases, the mixed equilibrium merges with the pure one at $\lambda_1 = 0.6$. On the other hand, in fig. 3c, there are two mixed equilibria, one of which is stable and increases towards $\lambda_1 = 1$ as $\gamma$ increases. The mixed unstable equilibrium again merges with the pure one at $\lambda_1 = 0$.

The former figures show that the number of equilibria varies with the pa- rameters. To further investigate parameter dependence, fig. 4 shows the regions with an equal number of stable and unstable equilibria in the $(\gamma, \delta)$ (a) and $(\gamma, \lambda)$ planes. We chose the following parameters in fig. 4a: $\kappa_1 = \kappa_2 = 0.2$, $\mu_1 = 1.8$, $\mu_2 = 2$, $\lambda = 1.3$. In fig. 4b, we set $\kappa_1 = \kappa_2 = 0$, $\mu_1 = 1$, $\mu_2 = 2$, and $\delta = 2$. For both figures, there is just one stable equilibrium and no unstable equilibria in region 1. In region 2, there are 2 stable equilibria as well as an unstable equilibrium.

## 3.1 Server-side optimisation

Finally, we investigate how the server should choose $\gamma$ (the priority) and $\delta$ (payment by the customers) so as to maximise its revenue.

Let $\lambda_m$ be the minimum value of $\lambda_1$ for which the system is stable. This value is given by (assuming $\mu_1 > \mu_2$): $\lambda_m = \max(0, \beta_2(\mu_1 - \mu_2)^{-1})$. Note that at least a rate $\lambda_m$ of customers have to go to queue 1 to keep the system stable. This means the server is guaranteed a revenue of $\lambda_m\delta$, and it can maximise revenue by setting an arbitrarily large $\delta$ since balking is not allowed in our
<figure><img src="image_5.png" /><figcaption>Figure 4: Number of stable and unstable equilibria for different $(\gamma, \delta)$ (a) and different $(\gamma, \lambda)$ pairs.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 5: Server-side optimization</figcaption></figure>

model. In practice, faced with a high price, customers will either balk or go to another service provider. Since our model has only one server (a monopoly) and customers cannot balk, we impose a tax (or a penalty) of $\lambda_m \delta$ on the server. This tax (or penalty) is paid by the server to the society in order to keep its monopoly. Every customer choosing queue 1 pays $\delta$, but the server gets to keep only a fraction $(\lambda_1 - \lambda_m)/\lambda_1$ of this amount. The revenue of the server is then

$$(\lambda_1 - \lambda_m)\delta.$$

With this definition of the revenue, the server does not generate revenue when the customers that choose queue 1 are only those that are forced to make this choice in order to stabilise the system. The server can no longer take advantage of its monopoly and set arbitrarily high prices as seen in the example below.

We assume that the server can orient the Wardrop equilibrium chosen by
the customers to the stable equilibrium of its choice. In figure 5a, the revenue is plotted as a heat map (the darker, the higher) for different values of $\gamma$ and $\delta$. The other parameters are: $\kappa_1 = \kappa_2 = 0.2$, $\lambda = 1$, $\mu_1 = 2$, $\mu_2 = 1$. We observe that it is best for the server to give priority to class 1 (the faster class) by taking the largest $\gamma$. However, for $\gamma = 0.99$ (that is, full priority to class 1), there is an optimal value of $\delta$ that is in the interior, as is shown in figure 5b.

# 4 Learning dynamics

We now investigate the behaviour of two learning dynamics — one in discrete time and the other in continuous time — to see how quickly and whether an equilibrium can be attained starting from an arbitrary routing probability. These learning dynamics can be useful when the players are not aware of the underlying parameters ($\lambda, \mu_1, \mu_2$, etc.) that are needed to compute the equilibria. The players can, however, observe the mean sojourn times of the servers corresponding to a given strategy profile (or the routing probabilities). The question then is whether they can reach an equilibrium purely by observing the mean sojourn times and adapting their routing strategies based on these observations. Learning dynamics are usually designed to attain a stable equilibrium. In our problem, there can be two stable equilibria (one non-ergodic and one ergodic), which have their distinct regions of attraction. Thus, one interesting question we could ask is how to set the parameters of the learning algorithm to arrive at one or the other equilibrium.

Since the focus of this paper is more on the characterisation of the equilibria (cf. the previous sections), the learning dynamics considered here are in a very simple setting: it will be assumed that the players are symmetric and have exactly the same information. The asymmetric case, along with other variations like incomplete and/or imperfect information, are out of the scope of this work.

Before going further, we make precise the terminology used in this section. First, note that depending upon the parameters, it can happen that not all the players are involved in the choice of routing probabilities (see (6) that gives the fraction that actually plays). In this case, the learning updates will be performed only by the fraction of the population that plays the game. For example, for the parameter choice of Fig 2(a), the game is played only by a 0.4 fraction of players. The learning updates are performed only by this 0.4 fraction of the population. Due to the possibility of two types of players, the total routing probability to a server is made up of two components: the fraction of players who are forced to choose this server and the fraction of players to whom this server is prescribed by their learning algorithm based on its routing probability updates. When we say “routing probability”, we mean the routing probability of the learning algorithm. We will use the term “total routing probability” whenever needed to distinguish these two quantities. Second, a player will refer to the one who actually plays and not to the ones who make a forced choice. Third, since the players are symmetric, the whole population is performing the same updates. Thus, in the rest of the section, we shall use the term “the player” to refer to
the population. Finally, since there are only two servers, it is sufficient to learn the probability of routing to server 1. So, we will keep track of this probability only. Finally, if the players choose server 1 with probability y, then y is also the fraction of the population that chooses server 1. We shall use these two equivalent definitions interchangeably.

## 4.1 Learning in discrete-time

In the discrete-time setting, at decision epoch n, the player chooses server 1 with probability y_n and observes both T_1 and T_2 based on which it updates the routing probability for epoch n + 1.

First, we investigate the dynamics of the Exponential-Weight (EW) algorithm, which is a widely used earning algorithm in sequential learning [25]. It updates the routing probability as:

$$y_{n+1} = \frac{y_n \exp(-\eta \bar{T}_1(y_n))}{y_n \exp(-\eta \bar{T}_1(y_n)) + (1 - y_n) \exp(-\eta \bar{T}_2(y_n))}, \quad (8)$$

where we have used the notations $\bar{T}_1(y_n)$ and $\bar{T}_2(y_n)$ to emphasise the dependence of the mean sojourn times on the routing probability. The parameter $\eta > 0$ is called the learning rate. It determines the size of the updates: a higher learning rate means a larger change in the updates for the same set of observations. This parameter is a design choice which can have a large influence on the dynamics, as we see below.

The EW algorithm can be seen as a discrete-time one-dimensional non-linear dynamical system

$$y_{n+1} = F(y_n; \eta) \quad (9)$$

with F as defined from (8). We note that, if it exists, the stable mixed equilibrium computed in Subsection 2.2 is a fixed point of these iterations. Thus, if the iterates behave well, the E-W algorithm will converge to this equilibrium if the initial point is sufficiently close to it. However, the stability of a fixed point of the iterative map F (which is different from the stability of the equilibrium), and hence the convergence of the iterates of F to this fixed point, depends upon the parameter $\eta$. In non-linear maps like ours, if $\eta$ is not chosen appropriately, the instability can lead to the appearance of cycles in the iterations and even chaos, as in the logistic map.

In fig. 6, we show the limiting behaviour of the iterates. The parameters for a subfigure are the same as for the corresponding subfigure in fig. 2. Recall that there is a mixed stable equilibrium in only scenarios (a) and (d). Unsurprisingly, the iterates become unstable after a certain value of $\eta$ (which depends upon the other parameters), leading to doubling and chaos. If $\eta$ is taken to be sufficiently small, the limit point is, indeed, a stable equilibrium (either the non-ergodic one or the mixed one). Such cycles and chaotic behaviour were shown to exist for the algorithm EW in a specific type of a 2 × 2 bimatrix symmetric game played by a large population [26]. Our map is a non-linear one, but the bifurcation phenomenon is similar.
<figure><img src="image_7.png" /><figcaption>Figure 6: Bifurcation diagram of the EW map</figcaption></figure>

For the specific game considered in [26], they showed that another dynamics known as the linear multiplicative weights (LMW) update (see the remark following Theorem 2 in [27]) does not exhibit bifurcation. The LMW algorithm updates the probability as

$$y_{n+1} = \frac{y_n(1 + \eta \bar{T}_2(y_n))}{y_n(1 + \eta \bar{T}_2(y_n)) + (1 - y_n)(1 + \eta \bar{T}_1(y_n))} \quad (10)$$

Note that in the coefficient of $y_n$ is weighted by $(1 + \eta \bar{T}_2(y_n))$ because we want to increase $y_n$ when $\bar{T}_2(y_n) > \bar{T}_1(y_n)$.

In fig. 7, we plot the dynamics of the LMW algorithms for different initial points spread over the range of possible values of $\lambda_1$ and for $\eta = 10$. The left (resp. right) pane is for the parameters of fig. 2a (resp. fig 2d). Each curve corresponds to a different initial point which are spread over the range of $\lambda_1$. In fig. 8a all the trajectories go to the only equilibrium (which is mixed and stable). For the scenario in fig. 2b, there are three equilibria: one pure, one unstable mixed and one stable mixed. In fig. 7b, the dotted line shows the unstable mixed equilibrium which separates the range of initial $\lambda_1$ into two regions. The dynamics starting in the lower region go to the pure equilibrium at 0 while those starting in the upper one converge to the stable mixed equilibrium.

We checked over a large range of $\eta$ but did not find any bifurcation for the LWM algorithm. While we do not have a formal proof for the non-existence of this phenomenon, it appears that LMW does not have bifurcation for our problem and is thus a better choice for learning.

## 4.2 Learning in continuous-time

For the continuous-time case, we use the replicator dynamics, which was initially proposed as a model for the evolutionary dynamics of the fraction of gene pools of competing species [28]. It can also be seen as the limiting case of the EW as well as the LMW algorithm when the learning rate $\eta$ and the time steps go to 0 proportionally (see [26] for an explanation).
<figure><img src="image_8.png" /><figcaption>Figure 7: Trajectories of $\lambda_1$ for the LMW algorithm different initial points</figcaption></figure>

The replicator equation for our problem is given by:

$$ \frac{d}{dt}y = y(y\bar{T}_1(y) + (1-y)\bar{T}_2(y) - \bar{T}_1(y)) = y(1-y)(\bar{T}_2(y) - \bar{T}_1(y)) \quad (11) $$

$$ =: F_{rep}(y) \quad (12) $$

The one-dimensional replicator dynamics above do not have the same instability phenomenon as the EW algorithm above. The solution of this equation, starting from a point sufficiently close, will converge to the stable mixed equilibrium. This can be explained in two different ways. First, an intuitive explanation. The replicator dynamics can be obtained as the limit $\eta$ of the EW and LMW algorithms. Since the latter converges to the mixed equilibrium for $\eta$ sufficiently small, one expects that the replicator dynamics will always be convergent to it. The second explanation is more formal. A rest point, $z$, of $F_{rep}$ satisfying $F_{rep}(z) = z$ is asymptotically stable if

$$ \left. \frac{d}{dy} F_{rep} \right|_{y=z} < 0 $$

which is equivalent

$$ z(1-z)(\bar{T}_2(z) - \bar{T}_1(z)) < 0. $$

From (7), at the stable mixed equilibrium $\bar{T}_2(y) - \bar{T}_1(y) < 0$. Since the stable mixed equilibrium is also a rest point, and it satisfies the above inequality, it is asymptotically stable.

The trajectories of $\lambda_1$ obtained from numerically solving the replicator ODE are shown in fig. 8 for the same scenarios and the same initial points as in fig. 7. These trajectories are quite similar to those of the LMW updates but on different time scales.
<figure><img src="image_9.png" /><figcaption>Figure 8: Trajectories of $\lambda_1$ for the replicator dynamics with different initial points</figcaption></figure>

# 5 Elastic demand

So far, the DPS model in the preceding sections assumes a constant arrival rate independent of the experienced sojourn times. We found that this assumption allows for the existence of non-ergodic equilibria. However, one expects that customers would not opt for such equilibria, and this should be reflected in the modelling assumptions. We now extend our assumptions by introducing elastic demand. The elasticity of the demand means that the arrival rate adapts to the expected sojourn times. If the expected sojourn time is high, fewer customers join the queueing system. The elasticity is described by a continuous and strictly decreasing function $\Lambda(t)$, which represents the arrival rate when the cost $\min(\bar{T}_1 + \delta, \bar{T}_2)$ equals $t$. Let $\lambda^*$ denote the minimal arrival rate such that the queues are not stable, independent of the traffic split,

$$ \lambda_* = \min(\mu_1, \mu_2) \left( 1 - \frac{\kappa_1}{\mu_1} - \frac{\kappa_2}{\mu_2} \right). $$

We assume that $\lim_{t \to \infty} \Lambda(t) < \lambda^*$ is the remainder. Without this assumption, the queues with elastic traffic cannot be stable. We further assume $\kappa_1 > 0$ and $\kappa_2 > 0$ which implies that $\bar{T}_1 \to \infty$ whenever $\bar{T}_2 \to \infty$ and vice versa. An equilibrium solution again satisfies (3), where $\lambda$ is no longer a fixed parameter, but satisfies,

$$ \lambda = \Lambda(\min(\bar{T}_1 + \delta, \bar{T}_2)). $$

We first show that the presence of elasticity ensures that there are no non-ergodic equilibria. As $\lim_{t \to \infty} \Lambda(t) < \lambda^*$, there exists an $\epsilon_1 > 0$ and $T^*$ such that $\Lambda(T^*) < \lambda^* - \epsilon_1$. Moreover, as $\bar{T}_1 \to \infty$ and $\bar{T}_2 \to \infty$ for $\rho \to 1$, there exist an $\epsilon_2$ such that $\bar{T}_1 + \delta > T^*$ and $\bar{T}_2 > T^*$ for $\rho > 1 - \epsilon_2$. Now choose $\lambda_1$ and $\lambda_2$ such that $\rho > 1 - \epsilon$ with $\epsilon = \min(\epsilon_1, \epsilon_2/\min(\mu_1, \mu_2)) > 0$. On one hand, we have $\bar{T}_1 + \delta > T^*$ and $\bar{T}_2 > T^*$ which implies $\lambda_1 + \lambda_2 < \lambda^* - \epsilon$. On the other
hand, we have

$$ \frac{\lambda_1 + \lambda_2}{\min(\mu_1, \mu_2)} + \frac{\kappa_1}{\mu_1} + \frac{\kappa_2}{\mu_2} > \frac{\lambda_1}{\mu_1} + \frac{\lambda_2}{\mu_2} + \frac{\kappa_1}{\mu_1} + \frac{\kappa_2}{\mu_2} = \rho > 1 - \epsilon > 1 - \frac{\epsilon_2}{\min(\mu_1, \mu_2)}, $$

which implies $\lambda_1 + \lambda_2 > \lambda^* + \epsilon$, a contradiction. We conclude that any equilibrium solution satisfies $\rho < 1 - \epsilon$. This implies that the cost remains finite. Having finite costs, we can follow Nagurney's exposition of Wardrop equilibrium with elastic demand, which is based on a variational inequality problem formulation [24]. In particular, the formulation implies that at least one equilibrium solution exists, which can be solved by standard iterative methods for solving variational inequality problems, including projection and relaxation methods.

We now illustrate the existence of multiple equilibria by means of a numerical example. Figures 9a and 9b depict the equilibrium cost $\bar{T}$ and the equilibrium class 1 arrival rate $\lambda_1$ versus the total arrival rate $\lambda$. We assume the following model parameters: the background traffic intensity equals $\kappa_1 = \kappa_2 = 0.2$. The service rates are $\mu_1 = 2$ and $\mu_2 = 1.8$, with a cost $\delta = 6$ for accessing class 1 service. Finally, we assume different values for the DPS parameter $\gamma$ as depicted. The figure clearly demonstrates the presence of multiple equilibria for a given arrival rate, in line with the findings of section 2. The shape of the curve for $\gamma = 0.8$ is somewhat unexpected. Starting from the left, the first part if the curve corresponds to the equilibrium solution $\lambda = \lambda_1$. The curve then circles back to a lower $\lambda$, this part of the curve corresponding to mixed equilibria. The last part of the curve then corresponds to the equilibrium solution $\lambda_1 = 0$. The corresponding evolution of $\lambda_1$ is shown in figure 9b.

To determine the equilibrium solutions with elastic demand, Figure 9a also depicts to linearly decreasing demand functions: $\Lambda_1(\bar{T}) = 1.4 - \bar{T}/100$ and $\Lambda_2(\bar{T}) = 1.4 - \bar{T}/200$. We have an equilibrium with elastic demand where the demand functions and cost functions intersect. The figure clearly demonstrates the presence of multiple equilibria. This is most obvious for the cost function for $\gamma = 0.7$ and the demand function $\Lambda_2$. Some scenarios also admit a single equilibrium solution. For example, for $\gamma = 0.6$ and both demand functions, there is but a single equilibrium.

# 6 Conclusion

We demonstrated that in a two-class discriminatory processor queue with an additional cost for joining the premium class, various equilibria can coexist depending on the system parameters. Notably, we found that certain conditions lead to non-ergodic behaviour, where the equilibrium traffic mix corresponds to a non-ergodic queueing system. This highlights the complexity of customer equilibria in the non-symmetric DPS queue. Additionally, we showed that the server can maximise revenue by adjusting the payment level of the higher priority class, thereby influencing the fraction of customers choosing the higher priority class.
<figure><img src="image_10.png" /><figcaption>Figure 9: Equilibrium cost (a) and equilibrium class 1 arrival rate (b) vs. the total arrival rate. Two elastic demand functions are also shown in (a). We have an equilibrium solution with elastic demand where the cost and demand curves intersect.</figcaption></figure>

When the parameters (such as the total arrival rate and service rates) for computing the equilibria are unknown to the players, we investigated three learning algorithms: two in discrete time and one in continuous time. It was observed that the Exponential-Weight algorithm exhibits bifurcation while the Linear Multiplicative Weights and the replicator dynamics converge to one of the equilibria.

Finally, we also considered the setting of elastic demand when the arrival rate itself changes as a function of the equilibrium mean sojourn times. If demand is a continuously decreasing function, then we argued that there can be no non-ergodic equilibrium in this case. However, as in the non-elastic case there can be still be multiple equilibria.

## Acknowledgment

This work was partly done during a visit of DF to LAAS, which was partially supported by ANR grant ANR-11-LABX-0040 within the French State Programme "Investissements d'Avenir".

## References

[1] I. Gurvich, M. A. Lariviere, and C. Ozkan. Coverage, coarseness, and classification: Determinants of social efficiency in priority queues. *Management Science*, 65(3):1061—1075, 2019.

[2] Y. Hayel and B. Tuffin. Pricing for heterogeneous services at a discriminatory processor sharing queue. In *Proceedings of Networking*, 2005.
[3] D. Fiems. Strategic revenue management for discriminatory processor shar-
ing queues. In *Computer Performance Engineering and Stochastic Mod-
elling (LNCS, volume 14231)*, pages 3–17. Springer, 2023.

[4] G. Fayolle, I. Mitrani, and R. Iasnogorodski. Sharing a processor among many job classes. *Journal of the ACM*, 27(3):519–532, 1980.

[5] L. Massoulié and J. Roberts. Bandwidth sharing: objectives and algo-
rithms. *IEEE/ACM Transactions on Networking*, 10(3):320–328, 2002.

[6] L. Massoulié and J. Roberts. Bandwidth sharing and admission control for elastic traffic. *Telecommunication Systems*, 15(1-2):185–201, 2000.

[7] J. W. Roberts. A survey on statistical bandwidth sharing. *Comput. Net-
works*, 45(3):319–332, 2004.

[8] S. F. Yashkov and A. S. Yashkova. Processor sharing: A survey of the mathematical theory. *Automation and Remote Control*, 68(9):1662–1731, 2007.

[9] E. Altman, K. Avrachenkov, and U. Ayesta. A survey on discriminatory processor sharing. *Queueing Systems*, 53(1-2):53–63, 2006.

[10] A. Orda, R. Rom, and N. Shimkin. Competitive routing in multiuser com-
munication networks. *IEEE/ACM Transactions on Networking*, 1(5):510–
521, 1993.

[11] E. Altman and N. Shimkin. Individual equilibrium and learning in processor sharing systems. *Operations Research*, 46(6):776–784, 1998.

[12] I. Ben-Shahar, A. Orda, and N Shimkin. Dynamic service sharing with heterogeneous preferences. *Queueing Systems*, 35(1-4):83–103, 2000.

[13] L. Ravner, M. Haviv, and H. L. Vu. A strategic timing of arrivals to a linear slowdown processor sharing system. *European Journal of Operational Research*, 255:496–504, 2015.

[14] E. Altman, U. Ayesta, and B. J. Prabhu. Load balancing in processor sharing systems. *Telecommunication Systems*, 47(1-2):35–48, 2011.

[15] U. Ayesta, O. Brun, and B. J. Prabhu. Price of anarchy in non-cooperative load balancing games. *Performance Evaluation*, 68(12):1312–1332, 2011.

[16] D. Fiems and B. J. Prabhu. Macroscopic modelling and analysis of flows during rush-hour congestion. *Performance Evaluation*, 149–150, 2021.

[17] R. Hassin and M. Haviv. *To Queue or Not to Queue: Equilibrium Behavior in Queueing Systems*. Kluwer Academic, 2003.

[18] P. Vis, R. Bekker, R. D. van der Mei, and R. Núñez-Queija. Heavy-traffic limits for discriminatory processor sharing models with joint batch arrivals. *Operations Research Letters*, 48:136–141, 2020.
[19] A. Izagirre, U. Ayesta, and I. M. Verloop. Sojourn time approximations for a discriminatory processor sharing queue. *ACM Transactions on Modeling and Performance Evaluation of Computing Systems*, 1(1):5, 2016.

[20] S. Kim. Approximate sojourn time distribution of a discriminatory processor sharing queue with impatient customers. *Mathematical Methods of Operations Research*, 87:411–430, 2018.

[21] T Chis and P. Harrison. Higher response time moments for $M/M/1$ discriminatory processor sharing queues. In *Proceedings of the 9th EAI International Conference on Performance Evaluation Methodologies and Tools*, page 145–148, 2016.

[22] G. Somashekar, M. Delasay, and A. Gandhi. Efficient and accurate Lyapunov function-based truncation technique for multi-dimensional markov chains with applications to discriminatory processor sharing and priority queues. *Performance Evaluation*, 162:102356, 2023.

[23] B. Kim. Monotonicity of the mean queue size in DPS systems. *Queueing Systems*, 100:209–211, 2022.

[24] A. Nagurney. *Network Economics. A Variational Inequality Approach*. Kluwer Academic Publishers, New York, 1993.

[25] Nicolo Cesa-Bianchi and Gabor Lugosi. *Prediction, Learning, and Games*. Cambridge University Press, 2006.

[26] Fryderyk Falniowski and Panayotis Mertikopoulos. On the discrete-time origins of the replicator dynamics: From convergence to instability and chaos, 2024.

[27] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. *Theory of Computing*, 8(6):121–164, 2012.

[28] Peter D. Taylor and Leo B. Jonker. Evolutionary stable strategies and game dynamics. *Mathematical Biosciences*, 40(1):145–156, 1978.