1

Fairness in Non-convex Systems
Corinne Touati, Hisao Kameda, Atsushi Inoie
University of Tsukuba, Japan{corinne, kameda, inoie}@osdp.cs.tsukuba.ac.jp

Abstract— In general, the set of users utilities is boundedbecause of the limitation of resources. There may exist
many Pareto optimal points in the set of users utilities.
For selecting a Pareto optimum point, a family of fairness criteria, that contains the max-min fairness and aparameterized family of fairness (by Mo and Walrand), hasbeen proposed and examined in some concrete networking
contexts that result in specific convex utility sets. We newly
examine general compact (closed and bounded) utility sets
which include the specific utility sets as special cases. We
first prove that each of the family of fairness criteria gives
a unique fair (Pareto optimum) point if the utility set isconvex. We find, however, counter-examples where each of
the family of fairness criteria gives multiple fair points if
the utility set is not convex. We propose an extention of thefamily of fairness criteria such that each of them gives onlya unique fair point regardless of whether the utility set isconvex or not, to which we give proofs. By using a specificload balancing model, we illustrate the counter-examples
and how each criterion of our extended fair family gives
a unique fair point.
Index Terms— Fairness, convex and non-convex systems,
Pareto optimality, max-min fairness, proportional fairness,mathematical programming / optimization, load balancing,
distributed computer systems.

I. I NTRODUCTION
In a multi-user system, it is generally not possible
to optimize simultaneously the performance of every
user. Instead, we consider the Pareto optima that are
the points of a system such that there exists no otherstate where all users have simultaneously better benefits.
Thus, we may not have any absolute preference among
Pareto optima. The weighted sum optimization (which
maximizes the weighted sum of the users’ utilities withdifferent weights) is Pareto optimal. The well-known
overall optimization [18], [9], [10], [7] maximizes thetotal utility over all users, and can be seen as a particularcase of weighted sum optimization.
There exist a priori innumerably many Pareto-optimalsituations. The choice of the one to achieve can becontroversial among users and a selection criterion isfairness.
In networking contexts, various fairness concepts havebeen already proposed [2], [13], [8], [14], [15]. Amongthem are the well-known max-min fairness (adopted
by the ABR - Available Bit Rate service of the ATM- Asynchronous Transfer Mode) and the proportional
fairness (achieved by the Vegas version of the TCP protocol [11]). Before them, mathematicians and economists
have developed several fairness criteria, one of theoldest being proposed by Nash [16]. It is commonlyreferred to as the Nash Bargaining Solution and coincides with the proportional fairness introduced by Kelly
when some simplifying assumptions are made [19], [20].
In the context of congestion control, Mo and Walrand[15] introduced a parameterized formulation of fairness,
which was later extended by considering concave andincreasing utility functions in the context of bandwidth
allocation [19], [20]. The utility functions represent thesatisfaction perceived by the user (typically functionof the delay or of the capacity). The interest of thisfamily is that it covers the max-min fair solution, theNash Bargaining Solution and the overall optimization
for particular values of the parameter. It hence enables
the provider of a system to finely tune the solution
according to its trade-off choice between fairness andglobal efficiency. However, the formulation and study
constrained itself to the case where the utility functions
are increasing and concave, which leads to convex utilitysets.
In reality, there exist many systems where the set ofachievable utilities (also called the ”bargaining set” incooperative game theory) is not convex. In such systems,
defining fairness becomes more challenging, which is themain question addressed by this paper. In game theory,some recent research raised the question of how to define
fairness in non-convex systems [5], [21]. These studies
focus, however, on an axiomatic definition while we areinterested here in an optimization formulation.
Additionally, load balancing systems are of great interest since they are a means of efficiently sharing resourcesamong users. Yet, although some research on how to
implement fairness has been conducted [17], there is
still a lack of theoretical formulation of fairness in thisfield, which motivates our research. As a special case, we
hence consider a model consisting of two servers sharedby two users or two sets of users. As the utilities of users

2

we consider the inverse of the delays (or equivalently themean response time) that they observe. For this system,
the utility sets are not convex.
The contributions of this paper are of two kinds. On
the one hand, rather than studying fairness in a specificnetworking environment, we choose to examine it in a
general theoretical framework. In particular, we extend
the definition of max-min fairness and of the Mo andWalrand fair family to any system. For this, we firstshow that in convex systems a unique max-min fairsolution exists while in general utility sets the max-min
fair criterion leads to a finite set of equivalent points.
These points are equivalent in the sense that they only
differ from the user’s labels. Hence, in each system, a”tie-breaking” rule needs to be agreed upon. We also
show that, when the utility set is not convex, the existing
formulation of the fair family has an infinity of solution
points. We then propose a new definition of the family
that assures the uniqueness of the solution. The new
family corresponds to the previously defined one when
the set is convex and we prove that it always gives Pareto
optimal solutions. In addition to these results, we show
that, when implementing the fair family, one has to makesure of using utility and not costs sets.
On the other hand, we apply the fair family in a loadbalancing system. We show that in spite of the simplicityof the model, this system can serve as a support to thestudy of fairness in non-convex systems. We study the
behavior of the fairness objectives through numericalexperiments. In particular, we observe that the fair points
can be located on convex and on concave segments of
the Pareto border and that they rapidly converge to themax-min fair solution.
The rest of this paper is organized as follows. We
first present the max-min fairness and its properties in
non-convex systems (Section II), and then present thefair family also both in convex and non-convex systems(Section III). We then point out that, for any given
system, one must carefully define the utilities (Section
IV). Section V introduce the load balancing model while
Section VI presents shows some numerical results. The
last section finally concludes the article.
II. M AX -M IN FAIRNESS
We consider a system in which we want to shareefficiently and fairly a given resource among n users. We
treat in this section the well known ”max-min” fairness.
In the next section, we focus on a general fair family
that covers, in particular, the max-min criterion.
Max-min fairness has been widely studied in special
cases of convex and compact utility systems (see for

instance [2], [3], [4], [8], [12], [13], [14], [22]). We propose here to study the criterion on a general framework
covering in any compact utility sets (convex or not).
We assume that to each n-dimensional allocation vector corresponds a utility vector u = (u1 , . . . , un ) that
represents the relative satisfaction perceived by the users
with this allocation. We denote by U ⊂ Rn+ \ {0} theachievable utilities, that is, the achievable utilities arestrictly positive.
In the following, we suppose that U is compact (forreal sets, this amounts to suppose that it is closed andbounded).
A. Definition
1) Pareto optimality: Let us first recall the definitionof Pareto optimality over a set U :∀v ∈ U, ∃i, vi > ui ⇒
Π= u∈U. (1)∃j, vj < uj , i, j ∈ {1, ..., n}
The Pareto set is therefore included in the upper rightborder of the utility set, which is why we also refer to it
as the Pareto border. Studying the Pareto set is of interest
since it represents the points that cannot be dominated interms of utilities. Therefore, fair criteria should naturally
reach Pareto efficient equilibria.
2) Max-Min fairness: Max-min fairness is, roughly
speaking, the allocation in which the minimal utility is
maximized, in a recursive manner. More formally, let us
define the associated permutation of a point:
Definition 1: For any point u of Rn , we define anordering permutation p a permutation of {1, ..., n} (thatis to say a bijection from {1, ..., n} to itself) such that→→up(1) ≤ up(2) ≤ ... ≤ up(n) . The vector −u = (−ui )i =(up(i) )i is the ordered representation of u.
Definition 2: We define a partial order relation ≺ by :
→→∀i < k, −ui = −viu ≺ v ⇔ ∃k ∈ {1, ..., n}, −→−→u k < vk .
Following [3], we say that u ∈ U is max-min fairer thanv if v ≺ u.
Let us consider for instance two points of coordinates−u = (7, 3, 6, 3) and v = (5, 4, 6, 3). Then →
u =
→
−
→
−
(3, 3, 6, 7) and v = (3, 4, 5, 6). We compare u and→−v coordinate by coordinate, starting by their smaller
→=−
→
→<−
→
element. As −uv1 and −uv2 then u ≺ v regardless1
2of the values of the bigger elements. We then extend
the definition of the max-min fair solution of [3] to any
system (convex or not):Definition 3: A max-min fair point is maximal for the
relation ≺.

3

We show that, similarly to what is known in special
networking convex cases [2], [3], [4], [8], [12], [13], themax-min fair points are always efficient:
Lemma 1: A max-min fair point is Pareto optimal.
Proof: Suppose that u is not Pareto optimal. Then∃v ∈ U, ∀i, ui ≤ vi , and ∃k, uk < vk , and hence u ≺ v .
We define the following class of equivalence:
Definition 4: Two points u and v are said utility−−
symmetrical, and we write u ∼ v if →
u = →
v (or
equivalently if neither u ≺ v nor v ≺ u).
Similarly, we say that a utility set U is symmetrical if∀u ∈ U , and ∀p permutation of {1, ..., n} the point v
defined by ∀i ∈ {1, ..., n}, vi = up(i) is also an elementof U .
B. Convex utility sets

Hence, there can exists up to n! max-min fair point
in a non-convex system. This result is illustrated in thecase n = 2 by the points u and v in Fig. 1.
Let us recall that fair criteria were originally defined,
in the context of game theory, as the unique solution
satisfying a set of axioms among which is the symmetry
axiom, stating that the solution does not depend on
specific labels [5]. The only difference between two
utility-symmetrical points is the mapping of the solution
to the identity of the users. It has therefore no impact
on the total performance of the system or the fairness ofthe solution. Utility-symmetrical points are, hence, fromthe fair and optimal point of view, identical. Hence, ona system to system basis, a ”tie-breaking” rule as to be
decided upon, which is not needed when restricting U
to be convex.
Remark 1: We can observe an interesting property.
In the case of convex utility functions, the max-min
fair solution is, roughly speaking, the Pareto optimal
point for which the utilities are as close as possible,
minimizing the distance of the Pareto border to theline of equal utilities (u1 = u2 = ... = un ). This
property does not hold with non-convex utility sets. Let
us consider for instance the point a = (a1 , a2 ) andb = (b1 , b2 ) of the Fig. 2, in a two users case. We seethat b2 = a1 but b1 > a2 and so a ≺ b (from Def. 2).
Hence, b is max-min fairer than a although it is locatedfurther from the line u1 = u2 .

When supposing the utility sets U to be convex, wehave the following properties:
Proposition 1: If the utility set U is convex, a uniquemax-min fair point exists.
Proof: Let u and v be two max-min fair points,
u 6= v . If U is convex, we consider z ∈ U such thatz = u+v
2 . As u 6= v , let k such that uk = min{ui |ui 6=vi }. If uk < vk then zk > uk and u ≺ z and u is not
max-min fair. Else, if ∃l, vl < vk then v ≺ z . If not,then vk < zk and hence v ≺ z and v is not max-min
fair.
Proposition 2: If the utility set U is convex andU2
U2usymmetrical, then the max-min fair point u∗ satisfies: u2∗∗∗
u1 = u2 = ... = un .
v
aProof: Suppose that u is max-min fair and that u1b∃i, j, i 6= j, such that ui < uj . Define v ∼ u by vi = uj ,vj = ui and ∀k ∈/ {i, j}, vk = uk and z = u+v
2 . ThenU1∀k ∈/ {i, j}, zk = uk and zi > ui . Hence u ≺ z .
U1
u1 u2
These results are similar to the ones known in thespecial cases of convex sets [2], [3], [4], [8], [12], [13],Fig. 1.
Two points can be Fig. 2. Max-min point b has[14], [15], [19], [20].
less homogeneous utilities thanequally max-min fair.
some other Pareto optima.

C. General caseIn this section, we do not assume the convexity of theutility set.
Proposition 3: Let U be a compact and non-empty
utility set. If u is a max-min fair point, then v is maxmin fair if and only if u ∼ v .
Proof: Let u and v be max-min fair. Then v ⊀ u→→
and u ⊀ v and hence −u =−v.
Conversely, let u be max-min fair and v such thatu ∼ v . Let z ∈ U . Then either z ≺ u (which impliesz ≺ v ) or z ∼ u (which leads to z ∼ v ). Hence v is
max-min fair.

D. Summary of the section
In this section, we have extended the definition ofmax-min fairness to any utility set. We have shown thatwhen the utility set is convex and compact, a uniquemax-min fair point exists. When the set is not convex,
there exists a set of equivalent max-min fair points. These
points are equivalent in the sense that they correspondto a re-ordering of the users’ labels. Hence, on any
system, a ”tie-breaking rule” needs to be agreed upon.
In Section V, we provide an example of such rule.

4III. G ENERAL FAIR FAMILY
In networking contexts, most of the research of fairequilibria has been conducted in the case of resource
sharing with increasing and concave utility functions,which leads to convex utility sets. Recently, in thecontext of congestion control, Mo and Walrand [15] proposed a general and simple uniform description (parameterized by parameter α) of a wide family of fair criteria,
including in particular proportional fairness and maxmin fairness. Touati et al. [19], [20] then generalized itin order to express it in term of utility rather than on the
resource itself. Yet, the previous formulation restrained
itself to the case where the utility functions are increasing
and convex. In this section, we propose to extend the fair
family to any system.
A. Definition
Consider the solution of maxu∈U Fα (u) where

1−α
1 X

if α ≥ 0, α 6= 1,
β
u

i
i
1 − αi (2)Fα (u) = Xif α = 1.
log uii

In this formulation, α is called the fairness parameter andβi > 0, i ∈ {1, ..., n} are the weights associated to theusers’ utility functions. The case α = 0 corresponds tothe weighted sum of the utilities of the users. When α →1 the criterion converges to a Nash bargaining solution
or proportional fair point.
In the following, and without loss of generality, we
suppose that ∀i, βi = 1. (This amounts in considering
the utilities v ∈ V with ∀i, vi = βi ui . Obviously, the set
V is convex if and only if U is convex.)
Our study rely on the following lemmas:
Lemma 2: Let V ⊂ Rn+ be a compact and non-empty
and G a strictly concave and continuous function fromV to R. Then, there exists G̃ ∈ R and SG̃ ⊂ Rn suchthatG̃ = max G(v) and SG̃ = {v ∈ V|G(v) = G̃} =
6 ∅.
v∈V
(3)
Moreover, if G is increasing with respect to each of its
variables, then the points of SG̃ are Pareto optimal withrespect to the set V .
Proof: As V is compact and G is continuous, then
G(V) is compact (see, e.g. [23]), which gives Eq. (3).
Suppose that u ∈ SG̃ is not Pareto optimal. Then,
there exists v ∈ V such that ∀i ∈ {1, ..., n}, vi ≥ ui ,and that ∃j ∈ {1, ..., n}, vj > uj . Then G(v1 , ..., vn ) ≥G(u1 , ..., uj−1 , vj , uj+1 , ..., un ) > G(u1 , ..., un ). Hence,G(v) > G̃ which is impossible.

Lemma 3: For each α > 0, the function Fα definedin Eq. (2) is continuous, strictly concave and strictlyincreasing with any of its n variables.
Proof: On R+ \ {0}, we define: 1 1−αif α 6= 1, α > 01−α xfα : x 7→
log(x)
if α = 1.
Obviously, fα is strictly increasing and concave. Hencethe result, by summation over the n variables.
B. Convex utility sets
We extend the formulation of Eq. (2) to convex andcompact utility sets. We first prove the uniqueness of thesolutions.
Lemma 4: Consider the notations of Lemma 2. If V
is convex then SG̃ is a singleton.
Proof: Suppose that ∃u, v ∈ SG̃ , u 6= v . Then
G(u) = G(v) = G̃. Consider z = u+v
2 . As V is convex,
then z ∈ V . As G is strictly concave, then G(z) > G̃
which contradicts the definition of G̃.
We can now apply the result to the optimization
function Fα . From Lemma 3 and 4, we obtain:
Theorem 1: If the utility set U is convex and compact,ethen, for each α > 0, there exists a unique point u
solution of F (eu) = max Fα (u) and it is Pareto optimal.
u∈U
Remark 2: Obviously, when α = 0, the function F0
is linear and therefore not strictly concave. Therefore, if
the utility set is not strictly concave, several solutions
may be obtained. This is actually a well-known result:the global optimization is not unique.
Finally, we note that, similarly to what is obtainedwith linear utilities in flow control, as α grows to infinity
the solution Sα converges to the one given by the maxmin fair criterion [15]. In the following subsection, we
propose to study the general framework of all compact
utility sets.
C. Extension of the fair family to general utility sets
Definition 5: For any utility set U and α > 0, we
define F̃α = max Fα (u) and SF̃α = {u ∈ U|Fα (u) =u∈UF̃α }. For clarity of presentation, we note in the following
Sα instead of SF̃α .
From Lemma 2 and 3, we have:
Proposition 4: For any compact utility set U , F̃αexists and Sα is not empty. Additionally, Sα is includedin the Pareto border.
When the set U is not convex, cases where theoptimization problem have several solutions (even infinitely many) exist. (Concrete examples will be given
in Section VI.) More precisely, if U is a subset of Rn ,

5

Sα is a set of dimension up to n − 1. We therefore seethat the formulation of Eq. (2) does not constitute a good
general fairness objective when the utility sets are notconvex.
a) General algorithm: One interesting property ofthe set of solutions Sα is that it is Pareto optimal. We
therefore propose to consider an algorithm that determines exactly one point of Sα . As shown in Section II,
with general utility sets, the max-min fairness criterion
gives a finite set of equivalent points. We therefore
propose to consider, as a fair solution associated to theparameter α, the max-min fair solution of the set Sα .
We then show, in the rest of this subsection, how todetermine the max-min fair point of a (non-convex) set.
We propose to then apply this method to the set Sα , forany value of α.
b) Determining the max-min fair solution: We propose to determine the max-min fair point of the system
by using the fair family. The following proposition
characterizes the set of solutions corresponding to an
infinite value of α:
Proposition 5: The solution S∞ corresponding to an
infinite value of α is the set of points u such that:→ = max{−→
S = {u ∈ Π|−uv , v ∈ U}},

increases (its shape is given by the curved dashed line
for an intermediate value). Finally, when α is infinite, theshape of F∞,K is given by the thick line. Simultaneously,
when K increases, Fα,K gets further from the origin.
Hence, we see that, although a ∈ S∞ and b ∈ S∞ , forany finite value of α, we have F (b) > F (a).

with Π the Pareto border.
Proof: From Prop. 4, these points are Pareto
optimal. Consider α > 1 and u ∈ Sα . As α > 1, wehave:−→1−α ≥ −→1−α ≥ ... ≥ −
1−α
u
u
u→
1
2
n
→
with −
u the ordered representation of u (as defined in→Def. 1). Define m = min{i ∈ {2, ..., n}, −ui 1−α <−→1−αu1}. As α grows to infinity, then ∀i ≥ m,−→1−α→→)1−α → 0, and therefore F (α) ≃ (m − 1) u1
.
(−
ui /−
u
1
1−α

D. Procedure to obtain a unique fair point for the Mo
and Walrand fairness and for the Max-min fairness

∞

1

1

We illustrate this result in Fig. 3, which is an enhancement of Fig. 2 for a two users case. All the points of the
thick line correspond to S∞ and hence are identicallyfair for the Mo and Walrand extended family. Therefore,
computing S∞ is not sufficient to determine the max-min
fair solution.
Yet, we can show an interesting characterization of themax-min points by the fair family:
Theorem 2: A point u ∈ U is max-min fair if andonly if∃α∗ , ∀α > α∗ , u ∈ Sα
Proof: See Appendix.
Consider again Fig. 3. For a given α ≥ 0 and K ∈ R,
we consider the curve Fα,K of points of solution u ofFα (u) = K . For α = 0, F0,K has the shape of thedashed line. As α increases, the concavity of the curve

U2
a
b

F∞,K
Fα,K
F0,K

U1
Fig. 3.

Some solutions of F̃∞ are not acceptable.

Hence, in a non-convex system, the class of max-min
fair points is given by the intersection of the solution of
the fair family for large values of α.

In this section, we give the procedures to obtain aunique fair point corresponding to: a) Max-min fairness
and b) the Mo and Walrand solution.
Let U a compact utility set (not necessarily convex).
Consider the family Fα as defined in Eq. (2). Our
procedure is as follows:
1) Do: V := U , i := 1.
2) If computing max-min fairness (a), then choose arandomly large value of α1 . Else (b), take α1 = α.
3) Repeat:(F̃αi = max Fαi (u)u∈V• compute.
Sαi = {u ∈ V|Fαi (u) = F̃αi }• Do: V := Sαi , i := i + 1• Randomly choose a large value αi (αi 6=
αj , j < i)until all points of V are utility-symmetrical (asdefined in Def. 4)4) If V has more than one element, then apply thetie-breaking rule. Examples of tie-breaking rules
are vast. For example, one could choose to givepriority to users with low indices. Another solution
would be to randomly choose one of the equivalentpoints. In Section VI, we give a possible rule inload balancing systems.

6

The convergence of the procedure is assured by Theorem 2. We note that the procedure would require at
most n iterations. In practice, however, this number
could be much lower. Also, Fα rapidly converges to F∞
and in practice, it is sufficient to consider values of theparameter above 20.
Remark 3: To check whether all the elements of anon-empty set V are utility-symmetrical, one can proceed
as follows:• Set i := 0
• Choose x ∈ V• Remove x from V• While i = 0 do:
If V = ∅ then i = 1,else
– Choose y ∈ V– if x ≺ y or y ≺ x then i = 2– Remove y from V .
• If i = 1 (respectively i = 2), all the elements are
utility-symmetrical (respectively they are not).
E. Summary of the section
We have shown in this section that, for any convex
system and any fairness parameter, the Mo and Walrand
formulation gives a unique solution. On the other hand,when the utility set is not supposed convex, we haveseen that the set of solution Sα can have infinitely many
optimal elements (we provide a concrete example in
Section VI). We therefore proposed to extend the fair
family so as to choose, for any solution set, the maxmin fair solution of Sα . However, in a general nonconvex system, computing the max-min fair solution is
not a simple problem. We hence provided a method todetermine the max-min fair solution of a general set
by using the optimization of a simple concave function(Eq. (2)).
IV. A NOTE ON COST MINIMIZATION PROBLEMS
It is sometimes useful to consider a set of costs,
rather than of utilities. The cost functions could be, forinstance, the delay experienced for each flow of a system.
We show in this section that the minimization of theobjective (2) over the cost set is not acceptable as a faircriterion. A concrete example will be given in the context
of load balancing in Remark 4 in Section V.
A. Definition
We can define the Pareto border Π′ of a cost set
similarly as of a utility set (Eq. (1)) by reversing theinequalities. Let us denote by C the set of costs. Then,it seems natural to adapt the fair family to find the setof solutions Tα in C such as to minimize

1−α
1 X

if α ≥ 0, α 6= 1,
β
c

i i
1 − αi Hα (c) = X
(4)


if
α
=
1.
log
c
i

i

B. Validity

The following proposition shows that when α grows
to infinity, the solution given by the minimization of Hα
is such that it minimizes the smaller cost, which is not
max-min fair.
Proposition 6: The solution T∞ corresponding to an
infinite value of α is the set of points x such that:−→→T∞ = {c ∈ Π′|−c1 = min{d1 , d ∈ Π′}}with Π′ the Pareto border for the cost set C .
Proof: Similarly to Lemma 2, we can show thatthese points are Pareto optimal. Let c be in the set ofsolutions Tα . For α > 1, we have:−→→→c 1−α ≥ −c 1−α ≥ ... ≥ −
c 1−α
1

2

n

Let us define m ∈ N+ by m = max{i, i ∈−→{1, ..., n}, →ci 1−α < −c1 1−α }. As α grows to infinity thenm−→c1 1−α X
1−α
→
→
βi .
(−
ci /−
c1 )
→ 0 and hence Hα (c) ∼1−αi=1V. L OAD BALANCING MODEL
A. Load balancing model
We consider the simple distributed computer systemrepresented in Fig. 4. It consists of two servers (computers), labelled 1 and 2, and two flows of demands φ1
and φ2 arriving from users 1 and 2 at servers 1 and
2, respectively (similar to the system studied in [6]). A
fraction xi (0 ≤ xi ≤ φi , i ∈ {1, 2}) of a flow of jobs
is forwarded from server i to the other server j (6= i).
We denote by x the vector (x1 , x2 ) and by l1 and l2 ,respectively, the resulting loads on nodes 1 and 2. Then∀i, j ∈ {1, 2}, i 6= j, li = φi − xi + xj . We assume
that node i has an exponential service time with mean
1/µi (i ∈ {1, 2}). Then, the mean delay at server i under
the load of rate βi is given by (µi −βi )−1 . For simplicity,
we assume that forwarding a job requires a fixed delayt. Therefore the delay experienced by the flow arrivingfrom the user i, can be written: for i, j ∈ {1, 2}, (i 6= j),
φi − xi1
Ti (x) =φi µi − φi + xi − xj1
+xi t +. (5)µj − φj + xj − xi

7

-0.8

1

2

max-min fairsolutionU ′ =U ′

-0.9

1

-1

φ1

Fig. 4.

-1.1

x2
φ2

φ1 = 2.1,
φ2 = 2.7,µ1 = 3,µ2 = 3.7,
t = 0.001.

α=0
α=1

U2′
x1

System parameters:

2

α=2
-1.2

Load balancing system
-1.3
-1.3

and the necessary condition (NC) for the system to befeasible is µ1 + µ2 > φ1 + φ2 . The set X is clearly
convex.
When x1 − x2 → µ2 − φ2 or x1 − x2 → φ1 − µ1 ,the values of Ti and T2 grow to infinity. We thenapproximates X by:
0 ≤ xi ≤ φi , i ∈ {1, 2} and2
Xε = x ∈ R
φ1 − µ1 + ε ≤ x1 − x2 ≤ µ2 − φ2 − εwith ε a positive constant. Then, we can allow Ti , i ∈{1, 2} to have arbitrarily large values by properly choosing the value of ε. Additionally, for any ε > 0, the set
Xε is compact.
2) Utilities: As a utility function, we consider the
inverse of the delay (which is homogeneous to a capacity
allocation): Ui (x) = 1/Ti (x). The utility set is then

-1.1

U1′

-1

-0.9

-0.8

Fig. 5. The minimization of cost functions is not acceptable as afair criterion.

B. A non-convex utility set
As illustrated by Fig. 6, the utility set is not necessarily
convex. As a result, the Pareto set may be locally concave
or discontinuous.
0.7
0.6
0.5

U2

A difficulty in its analysis is that the performance ofeach user depends on the allocations of others. To write
it more formally, for each i (i ∈ {1, 2}), Ti depends on
xj with j 6= i.
1) Set of constraints: We denote by X the set of
constraints on (x1 , x2 ). The forwarding rates should bepositive or null and bounded by the arrival flow. Also,
the service time at each server should not grow withoutbounds: µi − φi + xi − xj > 0, ∀i, j ∈ {1, 2}, i 6= j .
Hence, we have
0 ≤ xi ≤ φi , i ∈ {1, 2} andX = x ∈ R2,
φ1 − µ1 < x1 − x2 < µ2 − φ2

-1.2

0.4
0.3
0.2
0.1
0.1

0.2

0.3

0.4

U1

0.5

0.6

0.7

φ1 = 0.4,
φ2 = 0.5,µ1 = 1,µ2 = 1.2,
t = 0.1.

(a) Non-convex set
0.75

0.7

Paretoborder

0.65

U2

0.6

Achievable
Set

0.55

0.5

0.45
0.5

0.55

0.6

U1

0.65

0.7

0.75

(b) Discontinuous Pareto borderFig. 6.

Utility set

Uε = {u = (u1 , u2 )|∃x ∈ Xε , ui = Ui (x), i ∈ {1, 2}}.

Obviously ∀u ∈ Uε , ∀i ∈ {1, 2}, ui > 0.
Remark 4: Although it would seem natural to consider the utility Ui′ (T (x)) = −T (x), we note that it
would amount to consider the cost minimization family
H of Section IV, which is not acceptable. This result is
illustrated on Fig. 5. We see how the solutions of Hαdiverge from the max-min fair point as α increases, andhence how Hα is not acceptable as a fair family.

Compactness: The utility set is compact, as it is theimage of a compact set (Xε ) by continuous functions (U1and U2 ).
In this section, we have described a simple loadbalancing system. We have seen that, in spite of thesimplicity of the model, the utility set can be non-convex.
In the following section, we apply our general fairness
criterion to this system.

8

VI. FAIR LOAD BALANCING

B. Numerical results

A. Computational method
Since the utility set is not necessarily convex, we
apply the procedure of the extended fair family definedin Section. III-D. In the general case (of n users), theconstruction needs at most n iterations. Hence, in thissimple load balancing system, we solve the optimization
problem of Eq. (2) at most n = 2 times.
To compute the fair solutions, we fix the value of εof ε = 0.001 and proceed as follows:•

1) Example and interest of the method: Fig. 7 represents an example where the Mo and Walrand faircriterion does not give a unique solution, that is, the setof the fair solutions, S5∗ , has multiple points (note thestatement given after Prop. 4). This shows the appeal of
our method. (φ1 = 1, φ2 = 1.2, µ1 = 1.5, µ2 = 3, t =0.05 and α = 5.)
We illustrate in Figs. 7 and 8 the construction of ourfair solution. As S5∗ is not reduced to a single elementg 20 (Eq. (8)) and the unique(Fig. 7), we compute Fsol
solution u5 (Eq. (9)) shown in Fig. 8.
1.5

•

nd

1.1

1
1

Fig. 7.

1.4

1.5

u5 ≈ (1.18, 1.05)

1.2

x−19 + y −19 = 0.081

2
is a set of
dimension 1. When it does not consist of a single
point, we consider α′ , with α′ sensibly larger than
α and then solve

1.15

1.1

1.1

Fig. 8.

1.15

1.2

U1

1.25

1.3

Extended fairness: solution.

(8)

Tie-breaking rule: We recall that for each value of theparameter, the fair family gives a class of solution point.
In this case, there is at most 2! = 2 equivalent solution
points (similar to a and b of Fig. 1). We hence need to
set up a ”tie-breaking rule”:
If u = (a, b) and v = (b, a) with a < b are equivalently
fair for some value of the parameter α, then the chosen
solution point is:
u if U1 ((0, 0)) < U2 ((0, 0)),v otherwise.

1.3

1.25

U2

(7)

^
uα such that uα ∈ Sα∗ and Fα′ (uα ) = Fsol
α′ .
(9)

•

1.2

1.3

and the unique solution

•

1.1

U1
S5∗ is not a singleton.

(6)

iteration: Since n = 2, then Sα∗

∗
^
Fsol
α′ = max{Fα′ (x), x ∈ Sα },y = 2.605 − 1.173x
1.2

and Sα with a 0.1% accuracy. That is, we determine
the set :fα }.
Sα∗ = {x ∈ Xε |Fα (x) ≥ 0.999F

φ1 = 1,
φ2 = 1.2,µ1 = 1.5,µ2 = 3,x−4 + y −4 = 1.01
t = 0.05.

1.3

1st iteration: For given values of the parameters(µ1 , µ2 , φ1 , φ2 , t and α), we set up our program soas to computefα = max{Fα (x)|x ∈ Xε }
F

S5∗

1.4

U2

In this section, we study the properties of the fair (and
optimal) points in the load balancing problem describedin the previous section.
In the following subsection, we present how we applied the fair family to the system. Section VI-B thenpresent some numerical results we obtained.

2) Remarks: We provide here some remarks drawn
from numerical results.
Set S ∗α: As previously mentioned, the set Sα∗ is ofdimension 1. It is either:• a single point (Fig. 9 with α = 0, 1, 2, ..., 70)• a portion of curve, either continuous (Fig. 7) or not(Fig. 10).
Convergence For very large values of α, the program
becomes unstable, due to accumulation of round-off
errors. Hence, in the experiments, we limited the valueof α to be less than 100, which might be, for special
values of the parameters, not sufficient for reaching themax-min fair point. Yet, as the construction of the α-fairpoint considers the max-min fair point of a restricted partof the Pareto set, the experiments show that in practice

9
1.2

α=0

1.1

α=2

U2

1

φ1 = 0.9,

α=70

0.9

φ2 = 0.4,
0.8

U1 = U 2µ1 = 1.5,

0.7µ2 = 2,0.6

t = 0.35.

0.5
0.5

Fig. 9.

0.55

0.6

0.65

0.7

0.75

U1

0.8

0.85

Locally convex Pareto border.

1.2

x−1.5 + y −1.5 = 2.165

φ1 = 1.1,

1.1

Non-convex systems exist in a variety of networking situations. We have exhibited a simple static loadbalancing model in which the utility set is not convex.
The system consists of two identical servers (computers)with their own arrival and own queue. We have assumed
that the delay induced by forwarding a flow is fixed,
and have considered as a utility function the inverse of
the total delay experienced by the flow. We have seenthat in spite of the simplicity of the model, the utility
set can be non-convex and the Pareto border continuous
or not. Through numerical results, we examined theparameterized fairness objectives in the load balancing
system.

φ2 = 2,
∗
S2.5

U2

1

µ1 = 2,µ2 = 3,t = 0.05.

0.9

0.8

0.7
0.7

Fig. 10.

0.8

0.9

U1

1

1.1

1.2

The set Sα∗ can be discontinuous.

the family rapidly converges to the max-min fair point
as α grows.
Tie-breaking rule Finally, we note that in our experiments, we did not face any situation where we had tomake use of the tie-breaking rule. Although in theory
utility-symmetrical fair points exists, we expect them tobe rarely found in practice.
VII. C ONCLUSION
In this paper, we have studied in a general frameworka family of points parameterized by a parameter α whichenables us to finely tune the tradeoff between global
efficiency and fairness. Our starting point was a family
originally introduced in the context of fair bandwidth
allocation. We have shown that this family can be used in
the much wider range of systems in which the utility set
is convex and compact. More precisely, we have shownthat in that case the fair family has a unique solution.
In addition, when the utility set is not convex, we haveshown that there exists a class of equivalent max-min
fair points. As a given optimization function does notnecessarily have a unique extremum, the fair family may
have infinitely many solution points and defining fairness
becomes more challenging. We have therefore defined a
new fair family, that coincides with the previous one
when the utility functions are supposed convex andwhich gives a unique solution for any (compact) utility
set. This research hence opens the road for deeper study
on fairness with general utility sets.

A PPENDIX
Proof of Theorem 2 1) (sufficiency) Let v be max→→
min fair and u ∈ U . If u is max-min fair, then −u =−v
and so Fα (u) = Fα (v).
If u is not max-min fair, then u ≺ v . Define m =→→→→min{i ∈ {1, ..., n}|−ui < −
vi }. Then −ui = −
vi for i =−→→′1, ..., m. Define also m = min{i > m|vm < −vi }. Then
−
→
−
→
−
−−−→
−−−→
−→
v→
m = vm+1 = ... = vm′ −1 < vm′ and vj > vm , j =′m , ..., n.
We then want to show that ∃ε such that ∀α >ε, Fα(v) > Fα(u) .
We have:1−α m−1
1−α
m−1
→
→
X −
X −
uj
vj
=
.
•
−
−
v→
v→
m
m
j=1
j=1
1−α
n −
→
X
vj
−→ 0. Therefore ∃ε1 > 1 such
•
−
α→∞
v→
m
′
j=m
1−α
n −
→
X
vj
that α > ε1 ⇒
< 1.
−
v→
m
j=m′
 −→ 1−αum•→ +∞, then ∃ε2 > 1 such that α >
−
v→
m 
1−α
−
u→
m
> m′ − m + 1.
ε2 ⇒ −v→−→m −−−→−−−→−→• Since vm = vm+1 = ... = vm′ −1 < vm′ , then
′
m
−1
→
X −
vj
= m′ − m
−
v→
j=m

m

1−α
n −
→
X
uj
Finally, for all α > max{ε1 , ε2 }:
=
−
v→
1−α
m−1
→
X −
vj
j=1

−
v→
m

+

1−α
n −
→
X
uj

j=m′

−
v→
m

j=1 m
1−α
n −
→
X
vj

+ m′ − m >

j=1

−
v→
m

and so Fα (v) > Fα (u). Hence ∀u ∈ U not max-min
fair, ∃ε, ∀α > ε, Fα (v) > Fα (u).
2) (necessity) The proof of necessity goes similarly asthat of sufficiency. Let v ∈ U such that ∃ε1 such that∀α > ε1 , v ∈ Sα . Let u ∈ U, u 6= v . Suppose that v ≺

10

→
→
u. Then define m and m′ with m = min{i|−ui > −
vi },
−
→
−
→
′
and m = min{i|um′ > um }. Then as before,
1−α m−1
1−α
m−1
→
→
X−
X−
uj
vj
=
.
−
−
u→
u→
m
m
j=1

j=1

1−α
−
v→
m
−
→
−
→
→ ∞ and therefore
As um > vm , then −→
um
−

1−α
v→
m
∃ε2 such that ∀α > ε2 , −→> m′ − m + 1. As
um
1−α
1−α
n −
n −
→
→
X
X
uj
uj
→ 0, then ∃ε3 ,
< 1.
−
−
u→
u→
m
m
′
′
j=m

j=m

Finally, for any α > max{ε1 , ε2 , ε3 }, Fα (u) > Fα (v),which contradicts v ∈ Sα .
R EFERENCES[1] Aubin, J-P (1998). Optima and Equilibria: An Introduction to
Nonlinear Analysis, 2nd Ed.. Springer-Verlag. Berlin.
[2] Bertsekas, D. and R. Gallager (1992). Data Networks, 2nd Ed..
Prentice-Hall. Englewood Cliffs.
[3] Bonald, T. and L. Massoulié (2001). Impact of fairness oninternet performance. In: Proc. Sigmetrics Conf., 82–91.
[4] Le Boudec, J-Y. Le (2000). Rate Adaptation, Congestion Control
and Fairness: A Tutorial. Ecole Polytechnique Féd. de Lausanne.
[5] Conley, J and S. Wilkie (1996) An Extension of the Nash Bargaining Solution to Nonconvex Problems. Games and Economic
behavior 13, 26-38.
[6] Kameda, H., E. Altman, T. Kozawa and Y. Hosokawa (2000).
Braess-like paradoxes in distributed computer systems. IEEE
Trans. Automatic Control 45(9), 1687–1691.
[7] Kameda, H., J. Li, C. Kim and Y. Zhang (1997). Optimal Load
Balancing in Distributed Computer Systems. Springer.
[8] Kelly, F. P. (1997). Charging and rate control for elastic traffic.
European Transactions on Telecommunications 8, 33–37.
[9] Kim, C. and H. Kameda (1990). An algorithm for optimal
static load balancing in distributed computer systems. IEEE Trans.
Comput. 41, 381–384.
[10] Li, J. and H. Kameda (1998). Load balancing problems for
multiclass jobs in distributed/parallel computer systems. IEEE
Trans. Comput. 47, 322–332.
[11] Low, S., L. Peterson and L. Wang. (2001) Understanding TCP
Vegas: a duality model. In: Proc. of ACM SIGMETRICS, 226-235.
[12] Massoulié, L. and J. Roberts (1999). Bandwidth sharing: objectives and algorithms. In: Proc of IEEE INFOCOM 3, 1395–1403.
[13] Maulloo, A., F. P. Kelly and D. Tan (1998). Rate control incommunication networks: Shadow prices, proportional fairness
and stability. J. of the Operational Res. Soc. 49, 237–252.
[14] Mazumdar, R., L. G. Mason and C. Douligeris (1991). Fairness
in network optimal flow control: Optimality of product forms.
IEEE Trans. Communications 39(5), 775–782.
[15] Mo, J. and J. Walrand (2000). Fair end-to-end window-basedcongestion control. IEEE/ACM Trans. Networking 8(5), 556–567.
[16] Nash, J. (1950). The Bargaining Problem. Econometrica 18,
155–162.
[17] Sabin, G., V. Sahasrabudhe and P. Sadayappan (2004). On
Fairness in Distributed Job Scheduling Across Multiple Sites. In:
Proc. of IEEE Int. Conf. on Cluster Computing, 35- 44.
[18] Tantawi, A. N. and D. Towsley (1985). Optimal static loadbalancing in distributed computer systems. J. ACM 32(2), 445–
465.

[19] Touati, C., E. Altman, and J. Galtier (2001). On fairness inbandwidth allocation. Inria Research Report RR 4269.
[20] Touati, C., E. Altman, and J. Galtier (2002). Utility Based Fair
Bandwidth Allocation. In: Proc. of IASTED NPDPA, 126-131.
[21] Xu, Y and N. Yoshihara (2005). Alternative characterizationsof three bargaining solutions for nonconvex problems. COE/RES
Discussion Paper Series, No.126.
[22] Yaı̈che, H., R. R. Mazumdar and C. Rosenberg (2000). A
game theoretic framework for bandwidth allocation and pricing
in broadband networks. IEEE/ACM Trans. on Net. 8(5), 667–677.
[23] Zakon, E. (2004). Mathematical Analysis, Vol I, ISBN 1931705-02-X.