Analysis of a Non-cooperative

Load-balancing Game

Final Degree Dissertation

Degree in Mathematics

Iker Terán de la Torre

Supervisor:
Josu Doncel Vicente

Leioa, 17 February 2021

Contents

Introduction v

1 Introduction to Non-Cooperative Game Theory 1

1.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Useful definitions for a non-cooperative load balancing game . 6

2 Game Formulation 7
2.1 Non-Cooperative Routing Game . . . . . . . . . . . . . . . . 7
2.2 Inefficiency of Nash Equilibrium . . . . . . . . . . . . . . . . 9

3 Inefficiency Analysis 13
3.1 Worst traffic conditions for a fixed total traffic . . . . . . . . 13
3.2 Characterisation of routing strategies . . . . . . . . . . . . . . 15
3.2.1 Centralised routing strategy . . . . . . . . . . . . . . . 15
3.2.2 Decentralised routing strategy . . . . . . . . . . . . . 17
3.3 Characterisation of the inefficiency . . . . . . . . . . . . . . . 19

4 Characterisation of the PoA 33

5 Conclusions 39

A Alternative proof of representing the inefficiency ratio as a

function of α and β 41

Bibliography 45

iii
Introduction

Game Theory as a research field has hugely developed since the mathem-
atician John von Neumann and the economist Oskar Morgenstern published
their book Theory of Games and Economic Behaviour [1] in 1944. This pub-
lication alongside with the work carried out by John Nash (specifically, the
Nash Equilibrium) is considered to be the first step towards setting Game
Theory as an interdisciplinary research field. Nowadays, Game Theory plays
an important role not only in mathematics or economics, but also in politics,
philosophy and, of course, in network systems, which is the field our work
belongs to.
The aim of this dissertation is to analyse deeply a non-cooperative load
balancing game. To begin with, we approach the problem appropriately.
Then, we compare the cost at the Nash Equilibrium, being this the solution
to our problem, to the cost at the optimal routing strategy of the problem,
which is the one which provides the minimum possible cost. To finish, we
present the results and the conclusions reached from them.
This work consists of five main chapters. In the first one, we give a quick
idea about what Game Theory is from a broad point of view. Furthermore,
we provide some basic definitions about non-cooperative Game Theory so
as to familiarise with this research field. In addition, we present a handy
example for the better understanding of those concepts. We also introduce
a few useful ideas we will deepen into during this work.
In the second chapter, we present the non-cooperative routing game we
work on. To begin with, we define the architecture of the system and the
players taking part in it. Besides, we define two possible routing strategies:
the first one consists of the solution of the game we propose whereas the
second one is the best possible routing strategy. In an attempt to compare
the cost functions of both of them, we set a measure called the inefficiency
ratio.
The third chapter consists of the analysis of the strategies introduced
in the previous chapter. For that purpose, we characterise both routing
strategies and we compare them through the inefficiency ratio so as to de-
termine which one is better. Additionally, this chapter contains the main
result of this work, i.e. proposition (3.3.3).

v
vi

In the fourth chapter, based on the results obtained in the third chapter,
we seek for an alternative expression of the inefficiency ratio. Hence, we can
take advantage of this form of the ratio to characterise the Price of Anarchy,
a quite popular concept of measurement, in an easier way.
Finally, in the last chapter, we compile all the results obtained and we
explain and analyse the meaningful conclusions we have reached.
Chapter 1

Introduction to
Non-Cooperative Game
Theory

Unless otherwise indicated, the theory displayed throughout the first chapter
is compiled from [2].

The theory of games is a theory of decision making and it is used, whether

we realize or not, in daily automatic decisions, let alone in those ones in-
volving deep thought. Briefly, it considers how one should make decisions
which are linked to a goal. Thus, Game Theory was designed as a decision
making tool to be used in complex situations in which chance and choice
are not the only factors operating. Certainly, it aims to help us understand
situations in which decision-makers interact. It consists of a collection of
models, which are defined as precise expressions of ideas that can be presen-
ted verbally.
The theory of rational choice is a component of many models in Game
Theory. This theory is based on a model with two components: a set con-
sisting of all the actions that, under some circumstances, are available to
the decision-maker, and a specification of the decision-maker’s preferences.
Shortly, a decision-maker chooses the best action according to her prefer-
ences, among all the actions available to her.
Summing up, a game is put into practise as follows: in a game there are,
at least, two players (participants in the game), and each one picks up a
strategy (that is, a complete plan of action that describes what a player will
do under all possible circumstances). As a result of this joint choice, each
player gets a reward or a punishment: a payoff. A payoff function associates
a number with each action and each player seeks to find her strategy so as
to maximise her utility. This last sentence sums up the aim of a player in a
game: choose the strategy that leads her to a payoff as high as possible.

1
2 1.1. Basic definitions

1.1 Basic definitions

In this chapter, we formally present some definitions regarding Game The-
ory. Particularly, we focus on Non-Cooperative Game Theory and its most
significant concepts, among which is, specially, the Nash Equilibrium. We
also use this section as an introduction to various notions we will use through-
out the work.
Before defining and discussing the Nash Equilibrium, strategic and non-
cooperative games need to be defined. We will also provide a practical
example in order to ease and accompany theoretical explanations.

Definition 1.1.1. A strategic game with ordinal preferences consists of

• a set of players P = {1, ..., n}

• for each player i ∈ P , a set of actions Ai

• for each player i ∈ P , preferences over Ai

It is important to mention that the preferences of an agent, which are the

order a player gives rationally to actions based on their utility, are ordinal.
This means that the overall information we can get from them is which
action is better, not how much better it is. The preferences of an agent over
an action set are represented by a payoff function. As we indicated before,
a payoff function associates a number with each action so that actions with
higher payoff are preferred. Hence, being u the payoff function, the fact that
a decision-maker prefers the action a to b is represented by u(a) > u(b).
Game Theory consists of two main branches: cooperative and non-
cooperative games. Briefly, the main difference between both is that, in
cooperative games, players compete to capture value but they also can
create value by joining coalitions, whereas in non-cooperative games,
players rationally follow a procedure where negotiations are left aside. We
next present a practical non-cooperative game example.

Example 1.1.1. Let us suppose that 2 countries, say A and B, are about
to enter a nuclear war. The players taking part in the game are country A
and country B and each player has 2 possible actions: build nuclear bombs
(Build ) and do not build nuclear bombs (Do Not Build ). Assume that both
countries have enough resources to decide whether to build or not nuclear
weapons and each country’s best case scenario is to have bombs and the other
country not to. Assume also that both countries prefer the scenario where
neither has any bombs rather than the one in which both are armed, since
the process can be tedious and expensive. The problem can be modelled as
follows:

• Players: P = {A, B}
Chapter 1. Introduction to Non-Cooperative Game Theory 3

• Actions: XA = XB = {Build, Do Not Build}

• Preferences:

Player A’s preferences from the best to the worst are presented as
follows: (Build, Do Not Build ), (Do Not Build, Do Not Build ),
(Build, Build ), (Do Not Build, Build ).

Player B’s preferences from the best to the worst are presented as
follows: (Do Not Build, Build ), (Do Not Build, Do Not Build ),
(Build, Build ), (Build, Do Not Build ).

Based on the previous preferences, the payoff functions are the following:

• uA (Build, Do Not Build ) > uA (Do Not Build, Do Not Build ) >
uA (Build, Build ) > uA (Do Not Build, Build )

• uB (Do Not Build, Build ) > uB (Do Not Build, Do Not Build ) >
uB (Build, Build ) > uB (Build, Do Not Build )

We assign a representative natural number to each function regarding the

preferences above.

• uA (Build, Do Not Build ) = 3 = uB (Do Not Build, Build )

• uA (Do Not Build, Do Not Build ) = 2 = uB (Do Not Build, Do Not

Build )

• uA (Build, Build ) = 1 = uB (Build, Build )

• uA (Do Not Build, Build ) = 0 = uB (Build, Do Not Build )

We illustrate our strategic game in the next figure. The cells represent
the different situations the game reaches after each player’s choices. The
first number shows the payoff of player A whereas the second one shows the
payoff of player B.

B
Build Do Not Build
A Build (1,1) (3,0)
Do Not Build (0,3) (2,2)

Table 1.1: This figure captions payoffs for each feasible situation.
4 1.1. Basic definitions

Having a look at the example above, what should each player choose? What
seems to be clear is that each player must make a choice bearing in mind
other player’s choice. We assume that each player’s decision is based on
her previous experience playing the game (that is, she knows what other
players will do because she knows their preferences) and that she will make
a decision according to a rational model.
Definition 1.1.2. An action profile a∗ is a vector containing actions such
that a∗i ∈ a* for every i ∈ P , i.e. a∗ = (a∗1 , a∗2 , . . . , a∗n ).
A Nash Equilibrium point can be seen as a steady state strategy. That
is, if the game reaches a Nash Equilibrium a*, no player finds it beneficial
to deviate from her current action a∗i . We present some useful notation we
will use throughout this chapter in order to make the definition of the Nash
Equilibrium easier.
Let a = (a1 , ..., an ) be an action profile where ai ∈ a is the action chosen
by player i ∈ P . Let a0i be any action (either different or equal to ai ) of
player i. The action profile (a0i , a−i ) = (a1 , ..., a0i , ..., an ) represents that every
player except i adheres to ai ∈ a while player i chooses action a0i . It goes
without saying that, if a0i =ai , then (a0i , a−i ) = (ai , a−i ) = a. With all this,
we can define the Nash Equilibrium of a strategic game.
Definition 1.1.3 (Nash equilibrium of a strategic game with ordinal prefer-
ences). The action profile a* is a Nash Equilibrium (NE) if no player i ∈ P
has any action ai for which she prefers (ai , a∗−i ) to a∗ = (a∗i , a∗−i ). That
is, according to player i’s preferences, a∗ is at least as good as (ai , a∗−i ).
Equivalently, for every player i, being ui her payoff function,
ui (a∗ ) ≥ ui (ai , a∗−i ) for every action ai of player i ∈ P .
Immediately after having defined what the NE is, some significant ques-
tions need to be asked: does it always exist a NE point? In case it does,
how many NE points are there? The answer to those questions lies in the
theorem of the existence of the NE. Before stating it, we need to make a
difference between pure and mixed strategic games.
In mixed strategies each player i assigns a probability to each of her
possible actions in Ai instead of restricting herself to choose a single action.
However, in pure strategies, a player assigns probability 1 to a single
action ai and probability 0 to every other action aj , where j 6= i (what is
equivalent to simply choosing the action ai ). Indeed, a pure strategy can
be seen as a particular mixed strategy case. Bearing all this in mind, the
issue raised before about the existence of the NE, which is a crucial point
in Non-Cooperative Game Theory, can be answered.
Theorem 1.1.1 (Existence of the Nash Equilibrium). In a non-cooperative
game with a finite set of players P and finite strategy set Ai , there exists, at
least, one NE point in mixed strategies.
Chapter 1. Introduction to Non-Cooperative Game Theory 5

Examining our weapon race example, the unique NE consists of both

countries building nuclear weapons, that is (Build, Build ). How do we reach
this conclusion? Let us examine each of the feasible scenarios one by one.
I. If player A chooses Build, player B gets higher payoff by choosing Build
than choosing Do Not Build since

uB (Build, Build) > uB (Build, Do Not Build).

II. If player B chooses Build, player A gets higher payoff by choosing Build
than choosing Do Not Build since

uA (Build, Build) > uA (Do Not Build, Build)

III. If player A chose Do Not Build, player B would get higher payoff by
choosing Build than choosing Do Not Build, which would lead to player
A deviating towards Build (that is, case II).

IV. If player B chose Do Not Build, player A would get higher payoff by
choosing Build than choosing Do Not Build, which would lead to player
B deviating towards Build (that is, case I).
In our example, each player has a few actions to choose among so we can
easily spot the NE by examining whether an action profile satisfies all the re-
quired conditions. However, in more complicated games where the number of
actions for each player is large, it is better off using best response functions.
For a player i ∈ P , giving every other players’ actions, we seek the action for
which she gets the higher payoff. We next define best response functions.
Definition 1.1.4. Denote by Bi (a−i ) the set of player i’s best actions when
every other player adheres to the list a−i .
Bi (a−i ) = ai in Ai : ui (ai , a−i ) ≥ ui a0i , a−i for all a0i in Ai


Bi is called the best response function since any action ai in Bi of player i

is at least as good as every other action a0i in the set of actions Ai considering
that every other players’ actions are given by a−i .
It goes without saying that every member of the set Bi (a−i ) is a best
response of player i to a−i . We can restate the definition of the NE by using
best response functions. Bear in mind that an action profile is a NE if every
player’s action is a best response to the other players’ actions.
Proposition 1.1.2. The strategy profile a∗ is a NE of a strategic game with
ordinal preferences if and only if
a∗i ∈ Bi (a∗−i ), ∀i ∈ P.
That is, the action a∗i is a best action for player i taking into account the
actions of the rest of the players.
6 1.2. Useful definitions for a non-cooperative load balancing game

1.2 Useful definitions for a non-cooperative load

balancing game
In this section, we present some definitions about non-cooperative Game
Theory that will be used throughout the following chapters.
Let us begin with the definition of symmetric games and potential games.
In fact, the main problem of this work, presented in the next chapter, belongs
to this sort of games. Following the definition from [3], a game is symmetric
if all players’ strategy sets are the same and, in addition, the payoff depends
only on the strategies picked up and not on who chooses them. We formally
define symmetric games below.
Definition 1.2.1. A game of n players is called symmetric if the following
two conditions hold.
I. all of them have identical strategy sets, that is, A1 = A2 = . . . = An
II. ui (ai , a−i ) = uj (aj , a−j ), for ai = aj , a−i = a−j and ∀i, j ∈ P
Besides, we give the definition of a potential game,
Qn only after defining
the potential function. Bearing in mind that A = i=1 Ai is the cartesian
product of all sets of actions so that a ∈ A for any strategy profile a, the
potential is a real valued function P : A → R.
Definition 1.2.2. [4] A game is called potential if there exists a potential
function P such that
ui (a00i , a−i ) − ui (a0i , a−i ) = P(a00i , a−i ) − P(a0i , a−i )
Qn
for every player i ∈ P , for every a00i , a0i ∈ Ai and for every a−i ∈ i6=j Aj .

Finally, we introduce the concept of atomic splittable routing games. In

fact, the game we study in the next chapter belongs to this sort of games,
which are used for modelling communication and data networks, among
many other applications. Consider a network where each of the n players
controls a non-negligible amount of flow, which can be freely split to be
routed to the edges of the network. Each player seeks every possible way
of routing her flow, and aims to find the one that minimises her own cost,
which is charged when routing some flow on an edge. It is important to
mention that, since players are selfish, each of them disregards the cost of
other players in her way to achieving an incurred cost as low as possible [5].
The Price of Anarchy (PoA) plays a crucial role in atomic splittable
games. This measure studies the degradation in the performance due to
the selfish behaviour of the agents of the system. It is defined as the ratio
between the performance obtained by the worst NE and the global optimal
solution [6]. In the game we considered above, it studies the worsening of
the performance of the game when the players act greedily routing their
flow. Certainly, this is the issue our work revolves around.
Chapter 2

Game Formulation

One of the most relevant areas reached by Game Theory is the one related
to industrial technology and computing, which is, mainly, the one we are
interested in. The problem we are going to study regards load balancing,
which is a very discussed issue in Computer Science research field. Load
balancing is defined as the process of distributing a set of tasks across mul-
tiple servers (which form a server farm) with the aim of making the overall
processing of the tasks as efficient as possible. A server farm is a collection
of computer servers used to accomplish jobs for which multiple machines are
needed.

2.1 Non-Cooperative Routing Game

In this section, we introduce the problem we will further work on. Firstly,
we describe the game and how we model it, and later on, we discuss and
compare various strategies. In fact, our aim is to study whether the NE is
far from being the best strategy.
Let us consider a server farm with two types of servers. The holding cost
in a server is defined as the cost charged for submitting jobs to that server.
Without loss of generality, we assume that there are:

(i) n1 ≥ 1 cheap servers, with a holding cost equal to c1 per unit of traffic,

(ii) n2 ≥ 1 expensive servers, with a holding cost equal to c2 per unit of

traffic,
where c1 ≤ c2 . In addition, we denote by N the total number of servers so
that n1 + n2 = N . We number them from 1 to N and we define S1 and S2
as the sets of cheap and expensive servers, respectively, to get
j ∈ S1 if and only if j = 1, . . . , n1

j ∈ S2 if and only if j = n1 + 1, . . . , N .

7
8 2.1. Non-Cooperative Routing Game

Figure 2.1: An example of a routing game for K = 2 and N = 3.

We also define a set C = {1, . . . , K} with K dispatchers whose job is to feed

the servers. Each dispatcher i ∈ C receives λi jobs per second and forwards
xij jobs per second to server j ∈ {1, . . . , N }. Therefore,
X
xij = λi , ∀i ∈ C.
j∈S1 ∪S2

Our next step is to set up a feasible routing strategy, that is, a possible
path for the jobs to route. Let us give the following three definitions:

• xi =(xi1 ,..., xiN ) is the routing strategy of dispatcher i.

• Xi is the set of feasible routing strategies of dispatcher i.

• x = (xi )i∈C is the strategy (or action) profile

Nvector of all the
dispatchers. Hence, we have that x ∈ X = i∈C Xi .

The game can be seen as follows: each dispatcher receives a different

type of job (video, email or web page search, to say so) and forwards it to
the server farm.
Denoting by Ti (x) the cost function of dispatcher i, which is the total
cost of the jobs it handles, we define a game in which dispatcher i chooses
the strategy xi in order to minimise its own incurred cost. We next formally
define the cost of dispatcher i for a given vector of strategies x.
X X
Ti (x) = c1 xij (1 + yj ) + c2 xij (1 + yj ) (2.1)
j∈S1 j∈S2
P
where yj = i∈C xij is the total traffic circulation, also known as flow, on
server j. Note that dispatcher i’s incurred cost depends not only on the
amount of flow xij that forwards to server j ∈ {1, . . . N } but also on yj ,
which depends on the routing strategies of other dispatchers.
Chapter 2. Game Formulation 9

This is the reason why this model is defined as a non-cooperative game:

dispatcher i aims to find the strategy xi so as to minimise its incurred cost,
which also regards the routing strategies of the other dispatchers.
Recall that the NE is the set of strategies where no player finds benefit
from deviating unilaterally. Hence, we define xne ∈ X as the strategy profile
at the NE and we get the following:

xne ne ne ne ne
i ∈ arg min Ti (x1 , . . . , xi−1 , z, xi+1 , . . . , xK ), ∀i ∈ C (2.2)
z∈Xi

Remark 2.1.1. The authors in [6] perform the same analysis as in this
work considering a similar model in which the cost function Ti (x) is defined
as X c1 xij X c2 xij
Ti (x) = + . (2.3)
1 − yj 1 − yj
j∈S1 j∈S2

Note that our problem and the one in [6] are very similar. In fact, the cost
function considered in both models is increasing and convex in yj .

2.2 Inefficiency of Nash Equilibrium

How should the system distribute the incoming traffic among its servers?
How efficient is the use of K ≥ 2 dispatchers? In this section, in order
to find the answer to those questions, we compare two different routing
schemes: the decentralised routing scheme, where K ≥ 2 dispatchers are
used to forward the jobs to the servers, and the centralised routing scheme,
where there is a single dispatcher (K = 1) controlling all the traffic of the
system.
Before going deep into the analysis we carry out, we define the following
three vectors:

• p = (n, c), where n = (n1 , n2 ) and c = (c1 , c2 ). This vector describes

the server farm since it gives us the architectural structure of the entire
system. Assume that n and c are fixed and known.

• λ = (λ1 , . . . , λK ) is the vector containing the traffic received by each

dispatcher.

• yne = (y1ne ,P ne ), where y ne is the total flow on server j at the NE,

. . . , yN j
i.e., yj = i∈C xne
ne
ij , where x ne is as defined in (2.2).
ij

In the case of the decentralised routing scheme, K dispatchers seek to

minimise their own incurred cost. Therefore, the overall cost will be defined
as the sum of every dispatcher’s cost function.
10 2.2. Inefficiency of Nash Equilibrium

We recall the result in equation (2.1) and we define the overall cost of
the decentralised routing scheme as follows:
X
DK (λ, p) = Ti (x).
i∈C

Taking into account the definition of Ti (x), we have that

XX XX
DK (λ, p) = c1 xij (1 + yj ) + c2 xij (1 + yj ).
i∈C j∈S1 i∈C j∈S2

It is important to mention again that we are taking on a non-cooperative

game. That being so, the solution for the decentralised routing scheme is the
NE. For this reason, it would be useful to define the cost of the decentralised
setting as a function of yne as follows:
X X
F (yne ) = F1 (yjne ) + F2 (yjne )
j∈S1 j∈S2

where
Fk (y) = ck y(1 + y), k = 1, 2.

We emphasize that we use both DK and F (yne ) to denote the cost of

the decentralised scheme at the NE.
P
Recalling that i∈C xij = yj , we join them all to get that the overall
cost for the decentralised routing scheme at the NE is

X X
DK (λ, p) = F (yne ) = F1 (yjne ) + F2 (yjne )
j∈S1 j∈S2
X X
= c1 yjne (1 + yjne ) + c2 yjne (1 + yjne ) (2.4)
j∈S1 j∈S2

On the other hand, the optimal performance of the system is given by

the routing strategy that minimises the cost F (y), that is,
 
 XN 
F (y∗ ) = min F (y) : y ≥ 0, yj = λ (2.5)
 
j=1

where λ is the total traffic in the system, i.e., λ = λ1 + λ2 + . . . + λK . Note

that we achieve the minimum of F (y) when a single dispatcher (K = 1)
controls all the traffic (we will show this in the next chapter). Consequently,
the optimal routing strategy corresponds to a centralised routing scheme.
Chapter 2. Game Formulation 11

As a consequence of this, the global cost at the optimal routing strategy

is defined as DK (λ, p) = D1 (λ, p) = F (y∗ ).
Once we have defined both routing strategies, it is time to compare them.
A standard measure of the inefficiency of selfish routing, regarding the de-
centralised routing scheme. is the Price of Anarchy (P oA). As we stated
in the previous chapter, it is defined as the ratio between the performance
obtained by the worst NE and the global optimal solution. Thus the P oA,
as its name implies, measures the cost of having no central administrator
controlling the traffic. However, as we mentioned before, the vector that de-
scribes the server farm is assumed to be fixed, that is, we consider a server
farm where n and p are fixed. For this reason, we shall use the concept of
inefficiency, which has been introduced in [6] and we explain next for com-
pleteness. The inefficiency for a fixed architecture (number of servers and
holding costs) of a server farm is defined as the ratio between the perform-
ance obtained at the NE and the global optimal solution under the worst
possible traffic conditions. In the next chapter we will
 discuss worst possible
K
P
traffic conditions. By now, let us define Λ(λ) = λ ∈ R : i∈C λi = λ ,
the set containing all possible vectors for which the sum of their K compon-
ents equals the overall traffic λ. Therefore, the inefficiency of a server farm
with parameters n and c is defined as follows:

DK (λ, p) F (yne )
IK (p) = sup = sup ∗
(2.6)
λ∈Λ(λ) D1 (λ, p) λ∈Λ(λ) F (y )

The rationale for using inefficiency instead of the P oA is that, in practice,

the system administrator controls neither the total incoming traffic λ nor
how it is split between the dispatchers, whereas the number of servers and
holding costs, as we detailed before, are previously fixed. For instance,
Google and Amazon have a server farm with fixed parameters (number of
servers and holding costs). Consequently, the system administrators of those
companies are interested in the inefficiency ratio rather than in the P oA.
In fact, the inefficiency study of this work is the same as characterising the
loss of performance when each kind of job acts selfishly with respect to a
coordination of jobs, for a fixed parameter of the server farm.
Examining the definition of the inefficiency ratio, it goes without saying
that, the further the ratio from 1 is, the bigger the difference between the
optimal solution and the solution achieved at the NE is. The aim of this
work is to compare the performance of the decentralised routing scheme at
the NE with the performance achieved at the optimal routing strategy by
using the definition of inefficiency. In other words, by using the inefficiency
ratio, we seek to show that the solution obtained at the NE is not an efficient
solution.
Chapter 3

Inefficiency Analysis

3.1 Worst traffic conditions for a fixed total traffic

In the previous chapter, we defined the inefficiency ratio and we mentioned
that the worst possible traffic conditions of the system play an important
role in it. But what do we refer to when we speak about worst possible
traffic conditions?
The worst-case scenario is taken over all possible traffic profiles that the
routing agents can be asked to route. As it is shown in [7], for a fixed total
traffic λ in this model, DK (λ, p) reaches its maximum at the symmetric
game, that is, when the overall traffic
 λ is equally distributed among all K
λ λ
dispatchers so that λ = K , . . . , K .
 
λ λ
Consequently, we find the supremum of λ ∈ Λ(λ) at λ = K ,..., K so
that the global cost of the decentralised routing scheme DK (λ, p) becomes
the following:
 
λ
sup DK (λ, p) = DK 1, p , (3.1)
λ∈Λ(λ) K

where 1 = (1, . . . , 1) is a vector of K ones.

λ
Therefore, for a fixed λ, the worst case scenario is reached when λi = K
for every i ∈ P and, thereupon, from equations (2.6) and (3.1) the following
holds.  
λ
DK (λ, p) D K K 1, p
IK (p) = sup = sup (3.2)
λ∈Λ(λ) D1 (λ, p) λ>0 D1 (λ, p)
λ>0

Let us emphasize that the result obtained in (3.2) depends on the total
traffic λ and not on each dispatcher’s own traffic λi .
Let us now have a closer look at this game. This sort of strategic games
are called symmetric because all players have the same routing strategy set.

13
14 3.1. Worst traffic conditions for a fixed total traffic

Figure 3.1: An example of a symmetric routing game for K = 2 and N = 3.

As it is shown in [8], for this type of games there is a unique NE. Under this
setting, symmetric games belong to what we call potential games. We next
provide a convex optimization problem introduced and proved in [9], which
will considerably ease the characterisation of the decentralised solution.

Proposition 3.1.1. If the vector y is the global optimum of the following

convex optimization problem
2 X
X Z yj
minimize Fk (yj ) + (K − 1) ck (1 + z)dz
y 0
k=1 j∈Sk

N
X
s.t. yj = λ,
j=1

0 ≤ yj , j = 1, . . . , N
yj
then the strategy x such that xij = K for all i ∈ C and j = 1, . . . , N is the
NE of the symmetric game.

Remark 3.1.1. We stated in the previous chapter that the minimum of

F (y) is achieved when there is only one dispatcher controlling all the traffic
in the system. This result is accomplished by using the proposition above.
Note that, when K = 1, the integral part vanishes and the minimisation
problem becomes
X2 X
Fk (yj ) = F (y),
k=1 j∈Sk

which happens to be the global optimisation problem solved by the central-

ised scheme.
Chapter 3. Inefficiency Analysis 15

Before characterising the centralised and decentralised routing strategies,

we would like to point out the Karush-Kuhn-Tucker (KKT) conditions.
They can be seen as first order necessary conditions for a solution to be
optimal in nonlinear programming. We next use them to make the charac-
terisation of both centralised and decentralised routing strategies easier.

3.2 Characterisation of routing strategies

3.2.1 Centralised routing strategy
We use the KKT conditions as presented in [10] to characterise the central-
ised routing scheme. Our minimisation problem can be written as follows:

min F (y)
y∈RN

N
X
s.t. − yj ≤ 0, ∀j = 1, . . . , N and λ − yj = 0.
j=1
P2 P
Note that F (y) = k=1 j∈Sk Fk (yj ). We also define the Lagrange
function for our problem:

2 X
X N
X N
X
L(y, µ1 , . . . , µN , γ) = Fk (yj ) + µj (−yj ) + γ(λ − yj ) (3.3)
k=1 j∈Sk j=1 j=1

According to the definition of the KKT conditions, y∗ = (y1∗ , . . . , yj∗ , . . . , yN

∗ )

is an optimal routing solution if and only if the following four KKT condi-
tions hold:

(i) Stationarity.
We equal to zero the derivative with respect to yj∗ of the Lagrange
function defined above. That is,

∂L
= 0.
∂yj∗

From equation (3.3), we achieve

∂L
= Fk0 (yj∗ ) − µj − γ = 0.
∂yj∗

Hence,
Fk0 (yj∗ ) = µj + γ, ∀j = 1, . . . , N, k = 1, 2.
16 3.2. Characterisation of routing strategies

(ii) Primal feasibility.

−yj∗ ≤ 0, j = 1, ..., N.

N
X
λ− yj∗ = 0.
j=1

(iii) Dual feasibility. µj ≥ 0, j = 1, . . . , N.

(iv) Complementary slackness. µj (−yj∗ ) = 0, µj ≥ 0.

Our aim is to know what conditions need to be held in order server j to

work at the optimal solution. Following from the complementary slackness
condition, we know µj yj∗ = 0. If yj∗ > 0, then µj = 0 for all j = 1, . . . , N
and, therefore, Fk0 (yj∗ ) = γ, which is the minimum (since γ is a constant).
Observe that Fk0 (y) = ck [(1 + y) + y]. Hence,

yj∗ > 0 ⇐⇒ Fk0 yj∗ = ck 1 + yj∗ + yj∗ is minimal.



(3.4)

Note that, since Fk0 (yj∗ ) = γ, F10 (yj∗ ) = F20 (yk∗ ), ∀j ∈ S1 , ∀k ∈ S2 .

∗
Let us now define λ , which is the maximum value of λ for which the
optimal routing strategy deviates all traffic towards type 1 servers. That is,
∗
λ is the unique solution of
∗
!
λ
F10 = F20 (0) (3.5)
n1

∗
Note that λ is equally distributed among all type 1 servers so that
∗
∗
yj = nλ1 for all j ∈ S1 , while type 2 servers remain unexploited. Therefore,
from equation (3.5) and using F10 (yj∗ ) = c1 [(1 + yj∗ ) + yj∗ ] and F20 (0) = c2 , we
obtain that
∗ ∗
" ! #
λ λ
c1 1+ + = c2 . (3.6)
n1 n1
Bearing in mind that c2 ≥ c1 , we reach two different distributions for
the optimal routing strategy:
∗
• If λ ≤ λ , the centralised routing solution distributes the total traffic
λ equally among type 1 servers so that
(
λ
yj∗ = n1 , if j ∈ S1
0, if j ∈ S2
Chapter 3. Inefficiency Analysis 17

and, consequently, the optimal social cost is

 
X λ
F (y∗ ) = F1 (yj∗ ) = n1 F1 (3.7)
n1
j∈S1

∗
• If λ > λ , the centralised routing solution distributes the total traffic
among all N servers so that yj∗ > 0 for all j = 1, . . . , N and, therefore,
F10 (yj∗ ) = F20 (yk∗ ), ∀j ∈ S1 and ∀k ∈ S2 . Pointing out once again that
Fk0 (y) = ck [(1 + y) + y] for k = 1, 2, F10 (yj∗ ) = F20 (yk∗ ) leads to

c1 1 + yj∗ + yj∗ = c2 [(1 + yk∗ ) + yk∗ ] , ∀j ∈ S1 , ∀k ∈ S2 .




Since y1∗ = . . . = yn∗ 1 and yn∗ 1 +1 = . . . = yN

∗ ,

X X
F (y∗ ) = F1 (yj∗ ) + F2 (yk∗ ) = n1 F1 (y1∗ ) + n2 F2 (yN
∗
) (3.8)
j∈S1 k∈S2

3.2.2 Decentralised routing strategy

For the characterization of the decentralised routing strategy, we follow the
same procedure as in the centralised routing strategy. Note that, according
to proposition (3.1.1), yne = (y1ne , . . . , yN
ne ) is the optimal solution for the

decentralised routing strategy problem. Thus, we define F (y) as the function

we sought to minimise in proposition (3.1.1).
2 X
X Z yj
F (y) = Fk (yj ) + (K − 1) ck (1 + z)dz
k=1 j∈Sk 0

The Lagrange function for our problem is defined below.

N
X N
X
L(y, µ1 , . . . , µN , γ) = F (y) + µj (−yj ) + γ(λ̄ − yj ) (3.9)
j=1 j=1

We next study the KKT conditions for the minimisation problem in propos-
ition (3.1.1).
(i) Stationarity.
We equal to zero the derivative with respect to yjne of the Lagrange
function defined above. That is,
∂L
= 0.
∂yjne

From equation (3.9) we achieve

∂L
= Fk0 (yjne ) + ck (K − 1)(1 + yjne ) − µj − γ = 0
∂yjne
18 3.2. Characterisation of routing strategies

Hence,

Fk0 (yjne ) + ck (K − 1)(1 + yjne ) = µj + γ, ∀j = 1, . . . , N, k = 1, 2.

(ii) Primal feasibility.

−yjne ≤ 0, j = 1, . . . , N.
N
X
λ− yjne = 0.
j=1

(iii) Dual feasibility. µj ≥ 0, j = 1, . . . , N.

(iv) Complementary slackness. µj (−yjne ) = 0, µj ≥ 0.

Our aim is to know what conditions need to hold in order server j to work
at the NE. Following from the complementary slackness condition, we know
µj yjne = 0. If yjne > 0, then µj = 0 for all j = 1, . . . , N and, therefore,

Fk0 (yjne ) + ck (K − 1)(1 + yjne ) = γ, (3.10)

which is the minimum (since γ is a constant). Consequently,

yjne > 0 ⇐⇒ Fk0 (yjne ) + ck (K − 1)(1 + yjne ) is minimal. (3.11)

Remark that Fk0 (yjne ) = ck [(1 + yjne ) + yjne ]. It follows from (3.10) that

Fk0 (yjne ) + ck (K − 1)(1 + yjne ) = ck [(1 + yjne ) + yjne ] + ck (K − 1)(1 + yjne )

= ck K 1 + yjne + yjne


(3.12)

Thus, we get the following from equation (3.11):

yjne > 0 ⇐⇒ ck K 1 + yjne + yjne is minimal.




From equation (3.10), we obtain that ck [K(1 + yjne ) + yjne ] is constant for
either value of k. That is,

c1 [K(1 + yjne ) + yjne ] = c2 [K(1 + ylne ) + ylne ], ∀j ∈ S1 , ∀l ∈ S2 . (3.13)

ne
Let us define λ , which is the maximum value of λ such that, at the
ne
NE, all traffic is deviated towards type 1 servers. In other words, yjne = λn1
ne
for all j ∈ S1 and ylne = 0 for all l ∈ S2 . Substituting in (3.13), λ is the
unique solution of
ne ne
" ! #
λ λ
c1 K 1 + + = c2 K (3.14)
n1 n1
Chapter 3. Inefficiency Analysis 19

ne
As it came to happen in the centralised case, λ is equally distributed
among all type 1 n1 servers, while type 2 servers remain unexploited.
Taking into account that c2 ≥ c1 , we take on two different distributions
for the decentralised routing solutions:
ne
• If λ ≤ λ , the decentralised routing solution distributes the total
traffic λ equally among type 1 servers so that
(
λ
ne n1 , j ∈ S1
yj =
0, j ∈ S2 ,

and, consequently, by equation (2.4), the social cost at the NE is

 
ne
X
ne λ
F (y ) = F1 (yj ) = n1 F1 (3.15)
n1
j∈S1

ne
• If λ > λ , the decentralised routing solution distributes the total
traffic λ among all N servers so that yjne > 0 for all j = 1, . . . , N .
Hence, by equation (3.13), we get the following:

c1 K 1 + yjne + yjne = c2 [K (1 + ykne ) + ykne ] , ∀j ∈ S1 , ∀k ∈ S2 .




Recall that y1ne = . . . = ynne1 and ynne1 +1 = . . . = yN ne . It follows from

equation (2.4) that

X X
F (yne ) = F1 (yjne ) + F2 (ykne ) = n1 F1 (y1ne ) + n2 F2 (yNne
) (3.16)
j∈S1 k∈S2

is the social cost at the NE.

3.3 Characterisation of the inefficiency

Previously, we introduced the strategic game and characterised the solution
at the NE and the optimal routing solution with the aim to compare them.
In this section, we consider the inefficiency ratio as a measure of the loss of
performance due to the selfish behaviour of its players and we analyse its
behaviour as a function of λ.
Let us introduce an interesting result which gives us a general outline of
the behaviour of the inefficiency ratio.
ne ∗ ne ∗
Lemma 3.3.1. λ > λ holds for λ and λ .
∗ ne
Proof. We shall use the equations (3.6) and (3.14), the ones λ and λ are
unique solutions of, respectively. That is,
∗ ∗
" ! #
λ λ
c1 1+ + = c2
n1 n1
20 3.3. Characterisation of the inefficiency

and
ne ne
" ! #
λ λ
c1 K 1+ + = c2 K
n1 n1
c2
We isolate the constant c1 in both equations so we can equal them to
get
ne ne ∗ ∗ ne ∗
! !  
λ λ λ λ λ 1 2λ
1+ + = 1+ + ⇐⇒ 1+ = (3.17)
n1 Kn1 n1 n1 n1 K n1

and ne
λ 2
∗ =
1 + K1


λ
ne ne ∗
1 3 λ
≥ 34 . Hence, λ


Since K ≥ 2, 1 + K ≤ 2 and, therefore, ∗ >λ .
λ

Before stating the main proposition of this dissertation, we define a prop-

erty in the following lemma so as to ease a future proof.

Lemma 3.3.2. For all vectors y > 0 for which n1 y1 + n2 y2 = λ is satisfied,

the following inequality holds:
       
n 2 yN 0 λ λ 0 λ 0 λ
F1 F1 > F1 (y1 ) F1 − F1 F1 (y1 )
λ n1 n1 n1 n1

Proof. First of all, let us recall some expressions we have already used
throughout this work: F1 (y) = c1 y(1 + y) and F10 (y) = c1 [(1 + y) + y].
Substituting in our inequality, we get the following:
   
n2 yN λ λ λ
c1 1 + 2 c1 1+ >
λ n1 n1 n1
   
λ λ λ
c1 (1 + 2y1 ) c1 1+ − c1 1 + 2 c1 y1 (1 + y1 ) (3.18)
n1 n1 n1

Since c1 6= 0, we get rid of them in both RHS and LHS of the above
expression to get
   
n2 yN λ λ λ
1+2 1+ >
λ n1 n1 n1
   
λ λ λ
(1 + 2y1 ) 1+ − 1+2 y1 (1 + y1 ) (3.19)
n1 n1 n1

Since n1 y1 + n2 y2 = λ, we have that λ ≥ y1 n1 and, as a consequence,

λ
n1 ≥ y1 . Hence, we can substitute y1 by nλ1 in the RHS of the inequality so
Chapter 3. Inefficiency Analysis 21

λ
as it still holds. Appropriately, we can get rid of n1 in both LHS and RHS.
We show this result below.

       
n 2 yN λ λ λ λ λ λ λ
1+2 1+ > (1 + 2y1 ) 1+ − 1+2 (1 + y1 )
λ n1 n1 n1 n1 n1 n1 n1
      
⇐⇒ n2λyN 1 + 2 nλ1 1 + nλ1 > (1 + 2y1 ) 1 + nλ1 − 1 + 2 nλ1 (1 + y1 )
Taking into account that the LHS is positive, it is enough for us to prove
that the RHS is negative or zero. Decomposing the RHS, we get
2y1 λ λ 2λ 2y1 λ λ
1 + 2y1 + + − 1 − y1 − − = y1 − ,
n1 n1 n1 n1 n1
λ
which is negative or zero since n1 ≥ y1 .

Using the above result and the previous two sections, we can characterise
the inefficiency in our model, that is, the ratio
 
λ
DK K 1, p
D1 (λ, p)
 
λ
DK K
1,p
Proposition 3.3.3. The Inefficiency ratio D1 (λ,p)
as a function of λ is
∗
I. 1 if λ ∈ [0, λ )
∗ ne
II. strictly increasing with λ if λ ∈ (λ , λ )
ne
III. strictly decreasing with λ if λ ∈ (λ , ∞)

Proof. We next prove the three different cases one by one. Note that
 
λ
DK 1, p = F (yne ) and D1 (λ, p) = F (y∗ ) .
K
∗
I. For λ ∈ [0, λ ), the ratio equals 1.
ne ∗ ∗
Since λ > λ and λ < λ , we have the following from equations (3.7)
and (3.15):
 
λ
F (y∗ ) = F (yne ) = n1 F1
n1
Consequently,  
λ
DK K 1, p F (yne )
= =1
D1 (λ, p) F (y∗ )
22 3.3. Characterisation of the inefficiency

ne
Figure 3.2: Inefficiency is achieved at λ = λ .

∗ ne
II. For λ ∈ (λ , λ ), the ratio is strictly increasing.
 
λ
DK K
1,p
We know that the ratio D1 (λ,p)
is strictly increasing if and only if
its partial derivative with respect to λ is greater than zero. That is,
we have to show   
λ
∂  D K K 1, p
 > 0.
∂λ D1 (λ, p)

By the characterisation of the centralised and decentralised routing

∗ ne
schemes we know that, for λ ∈ (λ , λ ],
   
λ
DK K 1, p n1 F1 nλ1
= ,
D1 (λ, p) F (y∗ )
where
2 X
X X X
∗
F (y ) = Fk (yj∗ ) = F1 (yj∗ )+ F2 (yj∗ ) = n1 F1 (y1∗ )+n2 F2 (yN
∗
).
k=1 j∈Sk j∈S1 j∈S2

We calculate the derivative of the ratio with respect to λ so as to get

   
F10 nλ1 F (y∗ ) − n1 F1 nλ1 F 0 (y∗ )
(3.20)
(F (y∗ ))2

Note that the chain rule is applied to

  0    
λ λ 1 λ
n1 F1 = n1 F10 = F10
n1 n1 n1 n1
Chapter 3. Inefficiency Analysis 23

and, since y∗ = (y1∗ , . . . , yN

∗ ), also to

2 X
0 ∗
X dyj∗
F (y ) = Fk0 (yj∗ ) (3.21)
k=1 j∈Sk
dλ

Therefore,
 
from equation (3.20) and since (F (y∗ ))2 > 0, the ratio
λ
DK K
1,p
D1 (λ,p)
is strictly increasing if and only if
 
2 X ∗
dy
   
λ X j  n1 F1 λ
F10 ∗ 0 ∗


F (y ) >  Fk yj (3.22)
n1 dλ n1
k=1 j∈S k

Note that in equation (3.22) we use the equivalence of F 0 (y∗ ) stated

in equation (3.21). Let us first see what F 0 (y∗ ) answers for.
We know that λ = j∈S1 yj∗ + k∈S2 yk∗ since the sum of all servers’
P P
flow always equals the overall flow of the system, no matter what case
we are in. If we derive the LHS and RHS with respect to λ of the
above mentioned equality, we get the following:
X dyj∗ X dy ∗
k
1= +
j∈S1
dλ k∈S
dλ
2

Take into account that from the characterisation of the centralised

∗
routing scheme for λ > λ ,

F10 (yj∗ ) = F20 (yk∗ ), ∀j ∈ S1 , ∀k ∈ S2 .

By those last two equations,

2 X
X
dyj∗
Fk0 yj∗
dλ̄
k=1 j∈Sk
dy1∗ dy ∗ dy ∗ ∗ dyN
∗
= F10 (y1∗ ) + . . . + F10 (yn∗ 1 ) n1 + F20 (yn∗ 1 +1 ) n1 +1 + . . . + F20 (yN )
dλ dλ dλ dλ
 ∗ dy ∗ 
dy
= F10 (y1∗ ) 1
+ . . . + N = F10 (y1∗ ) (3.23)
dλ dλ

Therefore, from equation (3.22) and using the alternative expression

of F (y∗ ) presented in (3.8), we reach
   
λ λ
F10 [n1 F1 (y1∗ ) + n2 F2 (yN
∗
)] > n1 F10 (y1∗ )F1 , (3.24)
n1 n1
24 3.3. Characterisation of the inefficiency

 
λ
DK K
1,p
which needs to be proved to show that the ratio D1 (λ,p)
is strictly
∗ ne
increasing for λ ∈ (λ , λ ].
Before we continue, we have to prove the convexity of the function F2 ,
which will extremely ease the end of this prove. But first, let us recall
the definition appearing in [11] for a convex function.
Definition 3.3.1. A function f: Rn → R is convex if dom f is a
convex set and for all x,y ∈ dom f, and θ with 0 ≤ θ ≤ 1, we have

f (θx + (1 − θ)y) ≤ θf (x) + (1 − θ)f (y) (3.25)

Needless to say that R, which is where our function F2 is defined, is

a convex set. Hence, we just have to prove the inequality (3.25) for
our function F2 (y) = cy(1 + y). Take any x, y ∈ R and θ ∈ [0, 1].
Substituting in the definition, we get

c[θx + (1 − θ)y][1 + θx + (1 − θ)y] ≤ θcx(1 + x) + cy(1 − θ)(1 + y)

Let us get rid of the c constants in both RHS and LHS to achieve

θx+y(1−θ)+θ2 x2 +2θxy(1−θ)+(1−θ)2 y 2 ≤ θx(1+x)+y(1−θ)(1+y)

We arrange the expression above to get

θ2 x2 + 2θxy(1 − θ) + (1 − θ)2 y 2 ≤ θx2 + y 2 (1 − θ) ⇐⇒

x2 θ(1 − θ) + y 2 θ(1 − θ) − 2θxy(1 − θ) = θ(1 − θ)(x − y)2 ≥ 0

Since θ ∈ [0, 1], the inequality holds and F2 is a convex function.

For a convex function f in a convex domain, we know by [11] that the

following inequality holds:

f (y) ≥ f (x) + ∇f (x)(y − x), ∀x, y ∈ domf

∗ ∈ R. For the function F , we have
Let us take 0, yN 2

∗
F2 (yN ) ≥ F2 (0) + F20 (0)(yN
∗
− 0) = F20 (0)(yN
∗
) (3.26)
ne
since F2 (0) = 0.h By
 definition, λ iis the unique value of λ for which
ne  ne ne
the equality c1 K 1 + n1 + λn1 = c2 K holds. Thus for λ < λ ,
λ

λ̄ne λ̄ne
       
λ λ
c2 K = c1 K 1+ + > c1 K 1 + + .
n1 n1 n1 n1
Let us bring back F20 (y) = c2 [(1 + y) + y] and divide above inequality’s
both RHS and LHS by K to achieve
Chapter 3. Inefficiency Analysis 25

  
λ λ
F20 (0) = c2 > c1 1 + +
n1 Kn1
λ
Bearing in mind that Kn1 > 0, we can get rid of it to get
    
λ λ λ
F20 (0) > c1 1 + + > c1 1 + .
n1 Kn1 n1
       
n1
Since F1 nλ1 = c1 nλ1 1 + nλ1 , we obtain λ 1
F λ
n1 = c1 1 + λ
n1 ,
and, by the expression above,
 
n1 λ
F20 (0) > F1
λ n1
yielding, by equation (3.26),
∗
n 1 yN
 
∗ λ ne
F2 (yN )> F1 , ∀λ < λ .
λ n1
Hence, substituting the above inequality in (3.24), which is the
expression we seek to prove, we reach

  ∗
n 1 n 2 yN
   
λ λ λ
F10 ∗
n1 F1 (y1 ) + F1 0 ∗
> n1 F1 (y1 ) F1
n1 λ n1 n1
Let us divide both RHS and LHS by n1 6= 0 to get
  ∗
n2 yN
     
0 λ ∗ 0 λ λ 0 ∗ λ
F1 F1 (y1 ) + F1 F1 > F1 (y1 ) F1
n1 λ n1 n1 n1
∗
n2 yN 0 λ
       
λ λ λ
⇐⇒ F1 F1 > F10 (y1∗ ) F1 − F10 F1 (y1∗ )
λ n1 n1 n1 n1
(3.27)

This expression holds trueaccording


to lemma (3.3.2). Consequently,
λ
DK K
1,p
we state that the ratio D1 (λ,p)
is strictly increasing as a function of
∗ ne
λ for λ < λ ≤ λ .
ne
III. For λ ∈ (λ , ∞), the ratio is strictly decreasing.

By the equation (3.13) from the characterisation of the decentralised

ne
routing scheme for λ > λ , and choosing y1ne ∈ S1 and yN ne ∈ S , we
2
get the following equation:

c1 [K(1 + y1ne ) + y1ne ] = c2 [K(1 + yN

ne ne
) + yN ]
26 3.3. Characterisation of the inefficiency

c2
Diving both sides by K and setting β = c1 , we obtain
ne ) + y ne ]
c1 [K(1 + y1ne ) + y1ne ] c2 [K(1 + yN N
= ⇐⇒
 K    K  
1 1
y1ne 1 + + 1 = β yN ne
1+ +1 (3.28)
K K

λ−n y ne
By n1 y1ne + n2 yN
ne = λ, we get y ne =
N n2
1 1
and substitute to achieve

λ − n1 y1ne
     
ne 1 1
y1 1 + =β 1+ +1 −1
K n2 K
We simplify the above equation to get y1ne = mλ + sK , where
β
β−1 n2
sK =
  and m =
1
1+ K 1+ n1 β 1 + nn12β
n2

∗
From the characterisation of the centralised routing scheme for λ > λ ,
and choosing y1∗ ∈ S1 and yN∗ ∈ S , we have
2

c1 [(1 + y1∗ ) + y1∗ ] = c2 [(1 + yN

∗ ∗
) + yN ].
λ−n y ∗
Since λ = n1 y1∗ + n2 yN
∗ , we obtain y ∗ =
N
1 1
n2 . Substituting this
expression alongside β = cc21 in the above equation, we get y1∗ = mλ+s1 .
ne
Bear in mind that, for λ > λ ,
F (y∗ ) = n1 F1 (y1∗ ) + n2 F2 (yN
∗
)
and
F (yne ) = n1 F1 (y1ne ) + n2 F2 (yN
ne
),
where Fk (y) = ck y(1 + y), k = 1, 2.
Substituting the expressions above in the inefficiency ratio, we get
λ
DK ( K 1, p) F (yne ) n1 F1 (y1ne ) + n2 F2 (yN
ne )
= =
F (y∗ ) n1 F1 (y1∗ ) + n2 F2 yN ∗


D1 (λ, p)
n1 c1 y1ne (1 + y1ne ) + n2 c2 yN
ne (1 + y ne )
N

= (3.29)
n1 c1 y1∗ (1 + y1∗ ) + n2 c2 yN
∗ 1 + y∗
N

c2
We now divide both sides of the ratio by n1 c1 and we use β = c1 ,
ne = λ−n1 y1ne ∗ = λ−n1 y1∗
yN n2 and yN n2 , in order it to become
ne λ−n1 y1ne
 
λ y ne (1 + y ne ) + n2 β λ−n1 y1 1 +
DK ( K 1, p) 1 1 n1 n2 n2
= ∗ λ−n y ∗
 
D1 (λ, p) λ−n y
y1∗ (1 + y1∗ ) + nn21 β n21 1 1 + n21 1
Chapter 3. Inefficiency Analysis 27

Now, let us use the equivalences y1ne = mλ + sK and y1∗ = mλ + s1 we

computed before so as to achieve
 


n λ−n1 (mλ+sK ) λ−n1 (mλ+sK )
mλ + sK 1 + mλ + sK + n1 β 2
n2 1+ n2
 


n λ−n1 (mλ+s1 ) λ−n1 (mλ+s1 )
mλ + s1 1 + mλ + s1 + n1 β 2
n2 1+ n2

 
1 + mλ + sK + nn21 β λ(1−n1 nm)−n 1 sK λ(1−n1 m)−n1 sK



mλ + sK 2
1 + n2
=
n λ(1−n1 m)−n1 s1  

λ(1−n1 m)−n1 s1
mλ + s1 1 + mλ + s1 + n12 β n2 1 + n2


n2  λ(1−n1 m) n1 sK   λ(1−n1 m) n1 sK

mλ + sK 1 + mλ + sK + n1 β n2 − n2 1 + n2 − n2
=
n2  λ(1−n1 m) n1 s1   

λ(1−n1 m) n1 s1
mλ + s1 1 + mλ + s1 + n1 β n2 − n2 1 + n2 − n2

See that, in the last two steps, we just arranged all the coefficients
λ−n1 (mλ+sK ) λ−n1 (mλ+s1 )
of λ in n2 and n2 together to ease the next step.
After making some calculations, we get a quadratic function in both
above and below expressions. That is,
λ 2
DK ( K 1, p) aλ + bK λ + cK
= 2
D1 (λ, p) aλ + b1 λ + c1
2
 
where a = m2 + nn21β (1−nn12m) , bK = m+2sK m+ nn21 β 1−n1 m
n2 − 2sK n1 (1−n1 m)
n22
2
sK
and cK = (1 − β) K+1 .
We know that the ratio
λ 2
DK ( K 1, p) aλ + bK λ + cK
= 2 (3.30)
D1 (λ, p) aλ + b1 λ + c1

is decreasing with λ if and only if its derivative with respect to λ is

less than zero. Let us compute it.
2 2
!
λ
∂ DK ( K 1, p) (2aλ + bK )(aλ + b1 λ + c1 ) − (aλ + bK λ + cK )(2aλ + b1 )
= 2
∂λ D1 (λ, p) (aλ + b1 λ + c1 )2
(3.31)
2
Since (aλ + b1 λ + c1 )2 > 0, it is enough to prove

 2  
2

2

2aλ + bK aλ + b1 λ + c1 − 2aλ + b1 aλ + bK λ + cK < 0.

λ
DK ( K 1,p)
By equation (3.30) and because of the definition of the ratio D1 (λ,p)
,
2 2
we know that aλ + bK λ + cK > aλ + b1 λ + c1 , so it is enough for us
28 3.3. Characterisation of the inefficiency

to show that 2aλ + bK = 2aλ + b1 , that is,

 
n2 1 − n1 m 2sK n1 (1 − n1 m)
bK = b1 ⇐⇒ m + 2sK m + β −
n1 n2 n22
 
n2 1 − n1 m 2s1 n1 (1 − n1 m)
= m + 2s1 m + β −
n1 n2 n22
We first get rid of the constants where neither sK nor s1 appear to get
n2 2sK n1 (1 − n1 m) n2 2s1 n1 (1 − n1 m)
2sK m − β 2 = 2s1 m − β
n1 n2 n1 n22
2sK (1 − n1 m) 2s1 (1 − n1 m)
⇐⇒ 2sK m − β = 2s1 m − β
n2 n2
sK (1 − n1 m) s1 (1 − n1 m)
⇐⇒ sK m − β = s1 m − β
n2 n2
   
n1 β βsK n1 β βs1
⇐⇒ sK m 1 + − = s1 m 1 + −
n2 n2 n2 n2

Note that in the last step we just arranged the coefficients of sK and
s1 in the LHS and RHS, respectively. Since
β−1 β−1
sK =
  and s1 =  ,
n1 β n1 β
1 + K1 1 + n2 2 1+ n2

we get
   
n1 β β−1 n1 β β−1
sK 1+ = 1 and s1 1 + n = ,
n2 1+ K 2 2
respectively. We substitute those expressions in our equation to achieve

β−1 βsK β − 1 βs1

m 1 − n =m
2
−
n2
1+ K 2

We now use m, sK and s1 obtained at the beginning of the proof to

get
β β
n2 β−1 β β−1 n2 β−1 β β−1
− = −
+ nn12β 1 + K1 n2 1 + 1 1 +


+ nn12β
 
1 n1 β 1 2 n2 2 1 + n1 β
K n2 n2

which happens to be true since in both LHS and RHS we are sub-
tracting the same expressions. For this reason, both RHS and LHS
are equal to zero, meaning that the inequality we sought to proof holds
and, as a consequence, the ratio is decreasing as a function of λ for
ne
λ ∈ [λ , ∞).
Chapter 3. Inefficiency Analysis 29

 
λ
DK K
1,p
Proposition 3.3.4. The ratio D1 (λ,p)
is continuous over [0, +∞) as a
function of λ.
Proof.

First

of all, let us note that, since D1 (λ, p) 6= 0, the domain of
λ
DK K
1,p
D1 (λ,p)
is the real line R. From proposition (3.3.3), we see that the func-
∗ ∗ ne ne
tion D K
D1is split in three different intervals: [0, λ ), (λ , λ ) and (λ , ∞).
∗ ne
Therefore, we have to proof the continuity at λ = λ and λ = λ . We recall
 
λ
DK 1, p = F (yne ) and D1 (λ, p) = F (y∗ ).
K
∗
• The ratio DK
D1 is continuous at λ = λ if and only if
   
λ λ
DK K 1, p DK K 1, p
lim = lim .
λ→λ
∗− D1 (λ, p) λ→λ
∗+ D1 (λ, p)
Let us first have a look at the limit approaching from the left. By the
∗
first proof of proposition (3.3.3), for λ ≤ λ , we know that the ratio
equals 1 since F (yne ) = F (y∗ ) holds. Hence, we have to show
 
λ
DK K 1, p F (yne )
lim = lim = 1.
∗+ D1 (λ, p) ∗+ F (y∗ )
λ→λ λ→λ

Bear in mind that, from the characterisations of centralised and de-

∗ ne
centralised routing schemes for λ ≤ λ ≤ λ ,
 
λ
ne
F (y ) = n1 F1 and F (y∗ ) = n1 F1 (y1∗ ) + n2 F2 (yN
∗
). (3.32)
n1

We recall from the characterisation of the centralised routing scheme

∗
that λ is the unique value of λ such that all traffic deviates towards
∗ ∗
type 1 servers. As a consequence of this, at λ = λ , y1∗ = nλ1 and
∗ = 0 are obtained. Recalling that F (y) = c y(1 + y), we use the
yN k k
∗ to get, at λ = λ∗ ,
expressions of y1∗ and yN
∗ ∗
! !
λ λ
F (y∗ ) = n1 F1 + n2 F2 (0) = n1 F1 .
n1 n1

Therefore, by the above result and from equation (3.32),

   ∗
λ λ
DK K 1, p ne
F (y ) n 1 F 1 n1
lim = lim = ∗  = 1,
∗+ F (y∗ )

λ→λ
∗+ D1 (λ, p) λ→λ n1 F1 λ n1
∗
and the continuity at λ = λ is proven.
30 3.3. Characterisation of the inefficiency

ne
• The ratio DK
D1 is continuous at λ = λ if and only if
   
λ λ
DK K 1, p DK K 1, p
lim = lim .
λ→λ
ne− D1 (λ, p) λ→λ
ne+ D1 (λ, p)

First of all, note that, by the characterisation of the centralised rout-

∗
ing scheme for λ > λ , the expression of D1 (λ, p) for both limits is
D1 (λ, p) = F (y∗ ) = n1 F1 (y1∗ ) + n2 F2 (yN
∗ ).

By the characterisation of the decentralised routing scheme for

ne
λ ≤ λ , we have the following:
   
λ ne λ
DK 1, p = F (y ) = n1 F1
K n1
Therefore,
   ne 
λ λ
DK K 1, p F (yne ) n1 F1 n1
lim = lim = ne ne .
λ→λ
ne− D1 (λ, p) λ→λ
ne− F (y∗ ) n1 F1 (y1∗ (λ )) + n2 F2 (yN
∗ (λ ))

ne
 λ ≥ λ , the cost of the decentralised routing
On the other hand, for
λ
scheme becomes DK K 1, p = F (yne ) = n1 F1 (y1ne ) + n2 F2 (yN
ne ).
ne
Take into consideration that λ is the unique value of λ such that all
ne
the traffic deviates towards type 1 servers. Consequently. at λ = λ ,
ne
we get that y1ne = λn1 and yN ne = 0. We recall F (y) = c y(1 + y) so
k k
ne
that F2 (0) = 0. Hence, at λ = λ ,
ne ne
! !
λ λ
DK 1, p = n1 F1 .
K n1

Therefore, the limit approaching from the right is

   ne 
λ λ
DK K 1, p ne
F (y ) n 1 F1 n1
lim = lim ∗
= ∗ ne ∗ (λne ))
,
λ→λ
ne+ D1 (λ, p) λ→λ
ne+ F (y ) n1 F1 (y1 (λ )) + n2 F2 (yN

which happens to be equal to the one approaching from the left. This
ne
result proves the continuity of the ratio at λ = λ .

Taking into account the results obtained above, it is shown that the
ratio D
D1 is continuous over [0, ∞) as a function of λ.
K

We present a straightforward corollary following from the propositions

(3.3.3) and (3.3.4).
Chapter 3. Inefficiency Analysis 31

 
λ
DK K
1,p ne
Corollary 3.3.5. The ratio D1 (λ,p)
achieves its maximum at λ = λ .

Recall that the main target of this chapter was to show that the NE is
an inefficient solution for our load balancing problem. We have just proved
that the inefficiency ratio, which is the measure we chose to determine how
efficient the NE is, reaches its maximum value when the overall traffic of the
system is equal to the overall traffic at the NE. Moreover, we know that,
the higher value the ratio Ik gets, the further the solution for the decentral-
ised routing scheme from the optimal routing solution is. We conclude by
ne
showing the inefficiency ratio at λ = λ , which is
 ne 
λ
ne
F (y ) n F
1 1 n1
Ik (p) = ∗
= ne ∗ (λne ))
(3.33)
F (y ) n1 F1 (y1∗ (λ )) + n2 F2 (yN
Chapter 4

Characterisation of the PoA

In the previous chapter, we characterised the inefficiency ratio of a server

farm with two types of servers. Here, we aim to characterise the P oA using
the inefficiency ratio. Indeed, let us note that the P oA is achieved for the
worst inefficiency, strictly speaking,
P oA = sup IK (p)
p

In [6], it is also provided an explicit expression of the inefficiency ratio.

Besides, it is shown that the P oA is achieved for n1 = 1, n2 = N − 1 and
c2
c1 → ∞. Taking this all into consideration, in this chapter we aim to show
that the inefficiency for their model depends on n1 and n2 only through
α = nn12 and on c1 and c2 only through β = cc21 . Therefore, the inefficiency
ratio can be written as
IK (p) = IK (α, β).
The starting point is the expression of the inefficiency ratio achieved in
ne
the proof of the characterisation of the inefficiency for λ > λ , precisely,
equation (3.30). We display it below.

λ 2
DK ( K 1, p) aλ + bK λ + cK
Ik (p) = = 2
D1 (λ, p) aλ + b1 λ + c1
ne
First of all, we need an expression of λ for λ = λ . Recall from the charac-
terisation of the decentralised routing strategy the following equality, shown
in equation (3.14):
ne ne
" ! #
λ λ
c1 K 1 + + = c2 K.
n1 n1
c2
We set β = c1 and divide both LHS and RHS by K to get
ne ne  
λ λ K +1 ne
+ = β − 1 ⇐⇒ λ = n1 (β − 1)
n1 Kn1 K

33
34

That is,

ne K
λ = n1 (β − 1) (4.1)
K +1

Consequently, the maximum value of the inefficiency ratio, achieved at

ne
λ = λ , is

ne ne
a(λ )2 + bK λ + cK
IK (p) = ne ne ,
a(λ )2 + b1 λ + c1

2
 
where a = m2 + nn21 β (1−nn12m) , bK = m+2sK m+ nn21 β 1−mn
n2
1
− 2sK n1 (1−mn1 )
2
n2
2
sK
and cK = (1 − β) K+1 . Bear in mind that m and sK are defined in the
previous chapter, concretely, in the third proof of the characterisation of the
inefficiency ratio.
Note that we seek to rewrite every single expression in terms of n1 , n2 ,
c1 , c2 and K, with the aim of using α and β when possible. Therefore, we
bring the expressions of m and sK back to get

β
n2 β
m= =
1 + nn12 β n2 (1 + αβ)

and

β−1 β−1
sK =
1 n1 β
=
1 .
1+ K(1 + n2 )
1+ (1 + αβ)
K

Let us rewrite a, bK and cK .

 2
n1 β
n2 (1 − n1 m)2 β2 β 1 − n2 (1+αβ)
a = m2 + β 2 = 2 +
n1 n2 n2 (1 + αβ)2 α n22
 2
αβ
β2 β 1 − 1+αβ β2 β 1
= 2 + 2 = 2 +
n2 (1 + αβ)2 α n2 n2 (1 + αβ)2 α (1 + αβ)2 n22
 
β 1 β(1 + αβ) β
= 2 2
β+ = 2 2
= 2
n2 (1 + αβ) α αn2 (1 + αβ) αn2 (1 + αβ)
Chapter 4. Characterisation of the PoA 35

 
n2 1 − mn1 2sK n1 (1 − mn1 )
bK = m + 2sK m + β −
n1 n2 n22
  
αβ αβ
β 2(β − 1) β β 1− 2n 1 (β − 1) 1 − 1+αβ
1+αβ
= + 1

+  − 2 1


n2 (1 + αβ) 1 + K (1 + αβ) n2 (1 + αβ) α n2 n2 1 + K (1 + αβ)
" #
β 2(β − 1)β β 1 2α(β − 1)
= + + −
1 + K1 (1 + αβ)2 n2 α n2 (1 + αβ) n2 1 + K1 (1 + αβ)2



n2 (1 + αβ)
" #
β 2(β − 1)β β 2α(β − 1)
= + + 1−
1 + K1 (1 + αβ)2 n2 αn2 (1 + αβ) 1 + K1 (1 + αβ)



n2 (1 + αβ)
" #
β 2(β − 1) 1 2α(β − 1)
= 1+ + −
1 + K1 (1 + αβ) α α 1 + K1 (1 + αβ)



n2 (1 + αβ)
 
β 1 β(α + 1)
= 1+ =
n2 (1 + αβ) α αn2 (1 + αβ)

sK β−1 K(1 − β)(β − 1)

cK = (1 − β) = (1 − β) 1 =
(K + 1)2 (1 + αβ)


K +1 1+ K (1 + αβ)(K + 1)
Note that, since bK is not a function of K, bK = b1 holds. Apart from that,
we also get c1 = (β−1)(1−β)
4(1+αβ) by substituting K = 1 in cK . Therefore,
ne ne
a(λ )2 + bK λ + cK =
β K 2 n21 (β − 1)2 β(α + 1) Kn1 (β − 1) K(β − 1)(1 − β)
= 2 2
+ +
αn2 (1 + αβ) (K + 1) αn2 (1 + αβ) K + 1 (K + 1)2 (1 + αβ)
αβK 2 (β − 1)2 Kβ(β − 1)(α + 1) K(β − 1)(1 − β)
= 2
+ +
(K + 1) (1 + αβ) (K + 1)(1 + αβ) (K + 1)2 (1 + αβ)
 
K(β − 1) Kαβ(β − 1) 1−β
= + β(α + 1) +
(K + 1)(1 + αβ) K +1 K +1
K(β − 1)
= [αβK(β − 1) + β(K + 1)(α + 1) + 1 − β]
(K + 1)2 (1 + αβ)
αK 2 (β − 1)
  
K(β − 1) 2 1 1
= [αKβ + β(α + K) + 1] = β + β +
(K + 1)2 (1 + αβ) (K + 1)2 (1 + αβ) α K
2
αK (β − 1)(1 + αβ)(Kβ + 1) K(β − 1)(βK + 1)
= 2
=
Kα(1 + αβ)(K + 1) (K + 1)2

ne ne αβK 2 (β − 1)2 Kβ(β − 1)(α + 1) (β − 1)(1 − β)

a(λ )2 + b1 λ + c1 = 2
+ +
(K + 1) (1 + αβ) (K + 1)(1 + αβ) 4(1 + αβ)
 2 
β − 1 K αβ(β − 1) Kβ(α + 1) 1 − β
= + +
1 + αβ (K + 1)2 K +1 4
β−1
= [4K 2 αβ(β − 1) + 4Kβ(α + 1)(K + 1) + (1 − β)(K + 1)2 ]
4(1 + αβ)(K + 1)2
36

ne
As a consequence, the inefficiency ratio at λ = λ in terms of α, β and K
is the one displayed below:
K(β−1)(βK+1)
(K+1)2
IK (α, β) = β−1
4(1+αβ)(K+1)2
[4K 2 αβ(β − 1) + 4Kβ(α + 1)(K + 1) + (1 − β)(K + 1)2 ]
4K(βK + 1)(1 + αβ)
= (4.2)
4K 2 αβ(β − 1) + 4Kβ(α + 1)(K + 1) + (1 − β)(K + 1)2

We have just rewritten the ratio IK in terms of α, β and K. We now

show that the maximum value of IK (α, β) as a function of α is achieved at
α = N 1−1 , and thereupon, that the ratio IK (α, β) is non-increasing with α
so that  
1
IK (α, β) ≤ IK ,β .
N −1
Proposition 4.0.1. The ratio IK (α, β) is non-increasing with α if and only
if its derivative with respect to α is smaller than or equal to zero.

Proof. We have to proof the following inequality:

∂IK
≤0
∂α
Let us define
F (α, β) = 4K(βK + 1)(1 + αβ)
and

G(α, β) = 4K 2 αβ(β − 1) + 4Kβ(α + 1)(K + 1) + (1 − β)(K + 1)2

.
Consequently, the derivative of IK (α, β) with respect to α becomes

∂IK GFα − F Gα
= ,
∂α G2
where
Fα = 4Kβ(βK + 1)
and
Gα = 4K 2 β(β − 1) + 4Kβ(K + 1) = 4Kβ(βK + 1)
Note that Fα = Gα = 4Kβ(βK + 1). Since G2 > 0, it is enough for us
to show

GFα − F Gα ≤ 0 ⇐⇒ GGα − F Gα ≤ 0 ⇐⇒ Gα (G − F ) ≤ 0.

Taking into account that K > 1 and β ≥ 1, Gα > 0. Thus we need to

prove that G ≤ F .
Chapter 4. Characterisation of the PoA 37

G ≤ F ⇐⇒ 4αβK 2 (β − 1) + 4Kβ(α + 1)(K + 1) + (1 − β)(K + 1)2

≤ 4K(1 + αβ)(βK + 1)
⇐⇒ 4αK 2 β 2 − 4αβK 2 + 4Kβ(α + 1)(K + 1) + (1 − β)(K + 1)2
≤ 4βK 2 + 4αK 2 β 2 + 4Kαβ + 4K
⇐⇒ 4Kβ(α + 1)(K + 1) + (1 − β)(K + 1)2 ≤ 4βK 2 + 4αβK 2 + 4αβK + 4K
⇐⇒ 4αβK 2 + 4βK 2 + 4αβK + 4βK + (K + 1)2
≤ 4βK 2 + 4αβK 2 + 4αβK + 4K + β(K + 1)2
⇐⇒ 4βK + K 2 + 2K + 1 ≤ 4K + βK 2 + 2βK + β
⇐⇒ (K − 1)2 ≤ β(K − 1)2

Since K > 1, we get 1 ≤ β.

What does this mean? We have just shown that the ratio IK (α, β)
is non-increasing with α if and only if β ≥ 1. Take into consideration
that we defined β = cc12 , leading us to β ≥ 1 since c2 ≥ c1 . Hence, the
above proposition holds and IK (α, β) happens to be non-increasing with α.
Therefore, the worst inefficiency as a function of α is achieved at

 

1
 4K(βK + 1) 1 + Nβ−1
IK ,β =  
N −1 4βK 2 (β−1)
+ 4Kβ N 1−1 + 1 (K + 1) + (1 − β)(K + 1)2
N −1
4K(βK + 1)(N + β − 1)
=
4βK 2 (β − 1) + 4KβN (K + 1) + (N − 1)(1 − β)(K + 1)2
(4.3)

After having characterised the ratio IK (α, β) as a function of α keeping

β as a constant, it is time to study the behaviour of the ratio as a function
of β. In our attempt to find the P oA, we achieved the maximum value
of the ratio as a function
 of α,
 displayed in (4.3). In fact, we study the
1
characterisation of IK N −1 , β as a function of β taking as a starting point
the result in the mentioned equation.
For ease of characterisation, we illustrate in the next page the behaviour
of the ratio as a function of β for a fixed value of N = 10 and for three
different values of K. Note also that

   
1 1
lim IK ,β =1 and lim IK ,β = 1. (4.4)
β→∞ N −1 β→1 N −1
38

Figure 4.1: This graphic shows the behaviour of the ratio as a function of β
for N = 10 and K = 2, 5 and 10.

The graphic shows that IK ( N 1−1 , β) is non-monotone with β. In fact,

we can easily spot that the ratio increases towards a maximum value and,
afterwards, it decreases. In addition, we see that the larger the value of K
is, the larger the maximum value of the ratio is. In the last chapter, we
further analyse what those significant results mean.
Chapter 5

Conclusions

Since we introduced the problem at the beginning of the second chapter, we

have reached multiple results. Now, it is time to discuss them and clarify
what they mean.
First of all, I would like to recall the aim of this dissertation. Dealing
with a non-cooperative game, we sought to compare its solution, which is the
NE, to the optimal routing solution of the problem, which is achieved when
there is only one dispatcher controlling the overall traffic of the system. For
this purpose, we used the inefficiency ratio, which allowed us to compare
the costs of the decentralised and centralised routing schemes under worst
possible conditions. In other words, we characterised both routing schemes
and we compared the costs obtained under the conditions of a symmetric
game. Let us recall that the cost achieved for the decentralised routing
strategy will always be greater than or equal to the cost achieved for the
optimal routing strategy, that is, the centralised routing scheme.
The purpose of using the inefficiency ratio was to determine how far the
solution at the NE from the optimal solution was. For this, we defined the
maximum value of λ for which the NE and the optimal strategy deviate
ne ∗
all traffic towards type 1 servers as λ and λ , respectively. We consider
proposition (3.3.3) as the axis of this work, since the behaviour of the in-
efficiency ratio is fully described as a real function of λ. We next draw
conclusions reached from the mentioned proposition.
∗
For λ < λ , it makes no difference between both routing schemes, since
the inefficiency ratio equals 1. Therefore, we can say that the NE is an
∗
efficient strategy. Nevertheless, for λ being greater than λ but less than
ne
λ , the inefficiency ratio is increasing with λ. Hence, the NE is no longer
efficient and the greater λ is, the bigger the difference between the costs of
both routing strategies is.
ne
For λ = λ , the inefficiency point is achieved. That is, the ratio reaches
its maximum, which means that the difference between the cost of the de-
centralised routing scheme and the optimal solution is the greatest it can be.

39
40

For this case, the ratio is displayed in equation (3.33). From that point on,
the inefficiency ratio is decreasing as a function of λ. Apart from that, we
proved the continuity of the inefficiency ratio as a function of λ over [0, ∞).
In the fourth chapter, we aimed to characterise the P oA using the inef-
ficiency ratio. Let us recall that the P oA for the model in [6] is achieved for
n1 = 1, n2 = N − 1 and cc12 → ∞. Hence, we rewrote the inefficiency ratio
as a function of α and β, having defined those as α = nn12 and β = cc21 . Then,
keeping β constant, we managed to show that the ratio is non-increasing as
a function of α being its maximum at α = N 1−1 . Consequently, we proved
that the inefficiency ratio as a function of α achieves its maximum when
there is just one cheap server and N − 1 expensive servers to distribute the
jobs among.
Finally, for α = N 1−1 and N = 10, we found that the ratio as a function
of β is non-monotone. This is shown in figure 4.1. We set N = 10 (it holds
for any natural number greater than 1) and displayed the behaviour of the
ratio as a function of β for three different values of K. The image shows how
the ratio achieves a maximum, which seems to increase when the value of K
increases. In addition, we achieved a couple of interesting results regarding
the behaviour of the inefficiency. For α = N 1−1 and any value of K, we
obtained the following from equation (4.4):

• If β → ∞, that is, if using expensive servers is infinitely more costly

than using cheap servers, the ratio equals 1. As a consequence, the
NE strategy, which is the solution of the game, is efficient. This makes
sense since the system would refuse to use type 2 servers for a infinitely
large price.

• If β → 1, that is, if the costs for using expensive and cheap servers are
equal, the distinction between two types of servers vanishes. Therefore,
the system distributes the overall traffic equally among N servers in
both routing schemes. Hence, the strategy adopted by the system at
the NE becomes efficient.
Appendix A

Alternative proof of
representing the inefficiency
ratio as a function of α and β

Let us recall the expression in equation (3.33), which is the inefficiency ratio
ne
at λ = λ . As we showed in corollary (3.3.5), this value happens to be the
maximum for any λ > 0, that is, the worst inefficiency.
 ne 
λ
ne
F (y ) n 1 F1 n1
Ik (p) = ∗
= ∗ ne ∗ (λne ))
F (y ) n1 F1 (y1 (λ )) + n2 F2 (yN

We define
ne
!
λ ne ne
A = n1 F1 , B = n1 F1 (y1∗ (λ )) ∗
and C = n2 F2 (yN (λ )).
n1

Recall from the characterisation of the decentralised routing strategy the

following equality:
ne ne
" ! #
λ λ
c1 K 1 + + = c2 K.
n1 n1
c2
We set β = c1 and divide both LHS and RHS by K to get
ne ne  
λ λ K +1 ne
+ = β − 1 ⇐⇒ λ = n1 (β − 1)
n1 Kn1 K

That is,
ne K
λ = n1 (β − 1) (A.1)
K +1
We also defined Fk (y) = ck y(1 + y) previously. Hence,

41
42

ne ne ne
! !
λ λ λ
F1 = c1 1+
n1 n1 n1
ne
We next substitute the expression of λ obtained in (A.1) to get
ne
!  
λ c1 n1 K n1 K(β − 1)
F1 = (β − 1) 1 +
n1 n1 (K + 1) n1 (K + 1)

Consequently,
ne
!  
λ c1 n1 K K(β − 1)
A = n1 F1 = (β − 1) 1 +
n1 K +1 K +1
Kc1 n1 (β − 1)(Kβ + 1)
= (A.2)
(K + 1)2

In the third part of the proof of proposition (3.3.3), we defined

β
∗
y1∗ = mλ + s1 for λ > λ , where m = n2
n β and s1 =  β−1  . For the
n β
1+ n1 2 1+ n1
2 2
ne ne
expression of B, we define y1∗ (λ ) = mλ + s1 . Since α = nn21 ,
β
n2 β β−1
m= = and s1 =
1 + nn21 β n2 (1 + αβ) 2(1 + αβ)
Hence,

ne ne β Kn1 (β − 1) β−1
y1∗ (λ ) = mλ + s1 = +
n2 (1 + αβ) K + 1 2(1 + αβ)
Kn1 β(β − 1) β−1
= +
n2 (1 + αβ)(K + 1) 2(1 + αβ)
 
β−1 αβK 1
= +
1 + αβ K + 1 2

We substitute this expression into B to get

     
∗ ne β−1 αβK 1 β−1 αβK 1
B = n1 F1 (y1 (λ )) = n1 c1 + 1+ +
1 + αβ K + 1 2 1 + αβ K + 1 2

We next simplify the last factor of the expression above to get

   
β−1 αβK 1 β − 1 2αβK + K + 1
1+ + =1+
1 + αβ K +1 2 1 + αβ 2(K + 1)
(β + 1)(K + 1) + 2αβ(1 + βK)
=
2(K + 1)(1 + αβ)
Appendix A. Alternative proof of representing the inefficiency ratio as a
function of α and β 43

For this reason, B becomes the following:

    
β−1 αβK 1 (β + 1)(K + 1) + 2αβ(1 + βK)
B = n1 c1 +
1 + αβ K + 1 2 2(K + 1)(1 + αβ)
  
(β − 1)(2αβK + K + 1) (β + 1)(K + 1) + 2αβ(1 + βK)
= n1 c1
2(K + 1)(1 + αβ) 2(K + 1)(1 + αβ)
n1 c1
= [(β − 1)(2αβK + K + 1)][(β + 1)(K + 1) + 2αβ(βK + 1)]
4(K + 1)2 (1 + αβ)2
ne
∗ = λ −n1 y1∗
Let us recall that yN n2 . We use y1∗ obtained above to get

h  i
Kn1 β−1 αβK 1
ne K+1 (β − 1) − n1 1+αβ K+1 + K2 1
 
αβK 1

∗
yN (λ ) = = α(β − 1) − +
n2 K + 1 1 + αβ K + 1 2
     
K αβ 1 α(β − 1) K 1
= α(β − 1) 1− − = −
K +1 1 + αβ 2(1 + αβ) 1 + αβ K + 1 2
 
α(β − 1) K −1
=
1 + αβ 2(K + 1)

     
∗ ne α(β − 1) K −1 α(β − 1) K −1
C= n2 F2 (yN (λ ))
= n2 c2 1+
1 + αβ 2(K + 1) 1 + αβ 2(K + 1)
    
α(β − 1) K −1 2(1 + αβ)(K + 1) + α(β − 1)(K − 1)
= n2 c2
1 + αβ 2(K + 1) 2(1 + αβ)(K + 1)
n2 c2
= [α(β − 1)(K − 1)][2(1 + αβ)(K + 1) + α(β − 1)(K − 1)]
4(K + 1)2 (1 + αβ)2

n1 c1
B+C = [(β − 1)(2αβK + K + 1)][(β + 1)(K + 1) + 2αβ(βK + 1)]
4(K + 1)2 (1 + αβ)2
n2 c2
+ [α(β − 1)(K − 1)][2(1 + αβ)(K + 1) + α(β − 1)(K − 1)]
4(K + 1)2 (1 + αβ)2
n1 c1 D + n2 c2 E
=
4(K + 1)2 (1 + αβ)2

where

D = [(β − 1)(2αβK + K + 1)][(β + 1)(K + 1) + 2αβ(βK + 1)]

and

E = [α(β − 1)(K − 1)][2(1 + αβ)(K + 1) + α(β − 1)(K − 1)]

Having all this in mind, the ratio becomes the following:

44

Kn1 c1 (β−1)(Kβ+1)
F (yne ) A (K+1)2 4Kn1 c1 (β − 1)(Kβ + 1)(1 + αβ)2
Ik (p) = = = =
F (y∗ ) B+C n1 c1 D+n2 c2 E
4(K+1)2 (1+αβ)2
n1 c1 D + n2 c2 E

We divide both upside and downside by n1 c1 to get

4K(β − 1)(Kβ + 1)(1 + αβ)2

Ik (p) =
D + nn21 cc21 E
c2 n1
and recalling that β = c1 and α = n2 we obtain

4K(β − 1)(Kβ + 1)(1 + αβ)2

Ik (p) =
D + αβ E
where

D = [(β − 1)(2αβK + K + 1)][(β + 1)(K + 1) + 2αβ(βK + 1)]

and

E = [α(β − 1)(K − 1)][2(1 + αβ)(K + 1) + α(β − 1)(K − 1)]

This result shows that the inefficiency ratio depends on n1 and n2 only
through α = nn12 and on c1 and c2 only through β = cc21 . Therefore, the
inefficiency ratio can be expressed as follows:

Ik (p) = Ik (n, c) = Ik (α, β)

Bibliography

[1] Von Neumann, J. Morgenstern, O. (1944). Theory of games and

economic behavior. Princeton University Press.

[2] Osborne, M. J. (2004). An introduction to game theory (Vol. 3, No.

3). New York: Oxford university press. p.116.

[3] Cheng, S. F., Reeves, D. M., Vorobeychik, Y., Wellman, M. P.

(2004). Notes on equilibria in symmetric games. Proceedings of the
6th International Workshop On Game Theoretic And Decision The-
oretic Agents GTDT 2004.

[4] Marden, J. R., Arslan, G., Shamma, J. S. (2009). Cooperative con-

trol and potential games. IEEE Transactions on Systems, Man, and
Cybernetics, Part B (Cybernetics), 39(6), 1393-1407.

[5] Huang, C. C. (2013). Collusion in atomic splittable routing games.

Theory of Computing Systems, 52(4), 763-801.

[6] Doncel, J., Ayesta, U., Brun, O., Prabhu, B. (2014). Is the price of
anarchy the right measure for load-balancing games?. ACM Transac-
tions on Internet Technology (TOIT), 14(2-3), 1-20.

[7] O. Brun B. Prabhu. (Apr 2016). Worst-case analysis of non-

cooperative load balancing. Annals of Operations Research, 239(2),
471–495.

[8] Orda, A., Rom, R., Shimkin, N. (1993). Competitive routing in

multiuser communication networks. IEEE/ACM Transactions on net-
working, 1(5), 510-521.

[9] Cominetti, R., Correa, J. R., Stier-Moses, N. E. (2009). The impact

of oligopolistic competition in networks. Operations Research, 57(6),
1421-1437.

[10] Gordon, G., Tibshirani, R. (2012). Karush-kuhn-tucker conditions.

Optimization, 10(725/36), 725.

45
46 Bibliography

[11] Boyd, S., Boyd, S. P., Vandenberghe, L. (2004). Convex optimiza-

tion. Cambridge university press.