# A Fairness Relation Based on the Asymmetric Choquet Integral and Its Application in Network Resource Allocation Problems

Authors: Aoi Honda; Mario Köppen
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The recent problem of network resource allocation is studied where pairs of users could be in a favourable situation, given that the allocation scheme is refined by some add-on technology. The general question here is whether the additional effort can be effective with regard to the user’s experience of fairness. The computational approach proposed in this paper to handle this question is based on the framework of relational optimization. For representing different weightings for different pairs of users, the use of a fuzzy measure appears to be reasonable. The generalized Choquet integrals are discussed from the viewpoint of representing fairness and it is concluded that the asymmetric Choquet integral is the most suitable approach. A binary relation using the asymmetric Choquet integral is proposed. In case of a supermodular fuzzy measure, this is a transitive and cycle-free relation. The price of fairness with regard to a wireless channel allocation problem taking channel interference into account is experimentally studied and it can be seen that the asymmetric on relation actually selects allocations that perform on average between maxmin fairness and proportional fairness, and being more close to maxmin fairness as long as channel interference is not high.


---

## Body

## 1. Introduction

The rapid spread of wireless communication poses many challenges to the underlying networking technology and infrastructure. Daily experience of using wireless access teaches us the increased efficiency of provider solutions. At this stage of development, the major technical demand is theefficient reuse of existing resources or their usage expansion based on cost-efficient technical add-ons. That brings that the main valuation criterion today is the total utility of network infrastructure employment, with a lower focus on fairness aspects of resource allocation and distribution. For now, the standard user of a wireless infrastructure does not have the immediate experience of fairness, taking the access vector of other users into account—the needed information is simply not available for the user. This might change in the future and fairness might become the primary not the secondary aspect in comparison to efficiency. Recently, the relation between fairness and efficiency (in the sense of the total sum of per-user valuations) has become a relevant research issue. Obviously, a fair allocation is not an “optimal” allocation since the total valuation will be lower than the maximum possible. However, bounds do exist and in basic settings it is already known that the “price of fairness” is actually not so high [1].In the specification of fairness, the so-called “standards of comparison” (SoC) give an important formal instrument for the specification of fair solutions. It refers to a modality of comparing two solutions, where a solutionA passes a specific test with regard to another solution B. A classical example is the Nash standard of comparison for bargaining negotiations [2]; a solution is consideredbetter than another solution if the relative wins are not outperformed by relative losses. If a solution A appears to be better than any other solution, that is, the relative losses are always larger than or equal to the relative wins, the solution is seen as a stable point in negotiations, and there is no incentive to deviate from this solution. Later on, a few issues with the Nash SoC led to the formulation of an alternative Kalai-Smorodinsky SoC [3]. This approach promotes the user that receives the least allocation (which is also the base for the economical and political ideas of Rawls [4]). Both approaches, originally developed in economical science, have been rediscovered in network telecommunication theory and are very popular approaches in current research; the Nash SoC is now better known as proportional fairness [5] and the Kalai-Smorodinsky SoC as maxmin fairness [6]. It comes out that, even historically, the cultural distinction between these two fundamental kinds of fairness existed for long time [7]. In between, a mediating approach that links proportional fairness and maxmin fairness, the so-called α-fairness, has been formulated as well [8]; if α
=
0 the relation refers to proportional fairness, and (with some caution) if α
→
∞, the relation approximates maxmin fairness.However, the fairness models so far are based on a per-user valuation of “wins” and “losses” where only a single user can decide what is in her interest and what not. For example, in proportional fairness, the SoC is based on the comparison between two allocation vectorsx and y of the same dimension:
(1)
∑
i
‍
y
i
-
x
i
x
i
≤
0
.
One can see that each user, formally, contributes a single index value to the comparison test. However, as mentioned above for the case of wireless communication, increased demand of reuse of existing resources by new technical means and add-ons puts alsogroups of users into different situations that nevertheless need to be compared. There are many refined technologies explored these days that exhibit this property. One example is channel interference; in a wireless infrastructure, a base station BS has to allocate transmission channels (i.e., ranges of frequency bandwidth) to its subscriber stations (SS). The safe way is to allocate at most one SS to a channel. However, if SSs are well separated, that is, the channel interference of two SSs using the same frequency band is low, the same channel can be assigned to more than one SS. The question is how to know about this opportunity by proper measurement and about the best way to employ this. Several studies have been devoted to this technical challenge, but what they all have in common is the establishment of a pairwise relation between users, usually also weighted, as, for example, in [9–14].Besides channel interference, there are many other newer networking technologies where this aspect of pairwise user weight appears; in cognitive radio, unused channel capacities of primary users can be on occasion allocated to secondary users. The pairwise relation here is represented by a conflict matrix that contains lower values where the chance that two users (one from the group of primary users, one from the group of secondary users) transmitting data in the same time intervall is low. The encounter probability also plays an important role in peer-to-peer networking, opportunistic networking, and vehicular networks.Now, if considering above formalization of proportional fairness, how do we take this aspect into account; that is, the fact that a loss or win (relative or absolute) matters differently for different pairs of users? In other words, if, for example, user 1 and user 2 both experience losses when comparing two solutions could be taken differently from a situation where user 1 experiences a win and user 2 a loss. So far, no “pairwise standard of comparison” is known and it does not seem to be reasonable to define a different SoC for each different situation due to combinatorial explosion. The related problematic is about the price of fairness here; if a provider will consider a fair solution instead of the most efficient one, and taking the collision matrix information of a specific situation between users into account, is it worthy of the effort to implement the resource-reusing solution at all (i.e., to employ low channel interference, or to set up a schedule for cognitive radio secondary user channel assignment) if at the end no other allocation will be provided than without the technical add-on?The primary goal of this paper is to provide a formal fairness approach that can distinguish groups of users and weight them differently where needed. For this, it is needed to understand the SoC in terms of (set-theoretic) relations, following [15]. Then, a specific relation will be introduced based on fuzzy measure theory and related fuzzy integrals. It happens that this relation comes out to be a transitive relation (allowing for ranking of solutions, as well as fast search algorithms) and can be used to valuate the efficiency losses related to making fair allocations.Fuzzy measures [16, 17], which are called nonadditive measures [18] or capacity [19], are monotone and usually nonnegative set function. Since they can be used to express interactions between items that are not expressible by additive measures, many studies have been done on their application in fields such as subjective evaluation problems, decision-making support, and pattern recognition. The generalization with respect to fuzzy measures, a generalization of the Lebesgue integral, is proposed by several authors. The Choquet integral defined by Choquet [19] takes its place as one of them and is most widely used. The original Choquet integral is only for nonnegative functions, so that several generalizations for general functions which are not necessarily nonnegative have been given. There are mainly two types of generalization, one of which is called the symmetric Choquet integral or the Šipoš integral [20], and another one which is called the asymmetric Choquet integral is given in [18]. Concerning the details of these integrals, the first attempt was made by Denneberg [18]. This has been followed by Grabisch et al. They study properties and application to multicriteria decision making and so on, for example, in [21, 22]. Recent generalizations of the symmetric Choquet integral, employing averages and balanced weights over permutations, are the fusion Choquet integral [23] and the balancing Choquet integral [24].On the other hand, preference modelling and the related preference prediction have become research fields of increasing importance. The use of the Choquet integral as a base for a preference relation has been the topic of [25] where it is used to solve combinatorial optimization problems. The application of a preference relation model based on Choquet integral in multiobjective dynamic programming is the topic of [26]. In these works, the optimality is prespecified and given by independent means. Here, we shall focus on the formal representations of fairness in resource distribution as optimality issue by itself. Our proposal is to evaluate distributions from the aspect of fairness.In this paper, we compare the generalized Choquet integral, the symmetric Choquet integral, and the asymmetric Choquet integral from the viewpoint of representing fairness with the result that the asymmetric Choquet integral is more suitable for describing fairness. We also propose a fairness relation using the asymmetric Choquet integral.The paper is organized as follows. Section2 introduces notations and necessary materials about fuzzy measure and the Choquet integral and recalls the relational approach to fairness. Then, Section 3 presents discussion about two generalized Choquet integrals. The fairness relation is proposed in Section 4, and we give a sufficient condition that this relation is consistent and transitive. Section 5 gives a demonstration of how our fairness relation is used for decision making. Section 6 compares the solutions obtained by this fairness relation with the proportional and maxmin fair solutions by way of experiments.


## 2. Preliminaries

### 2.1. Relational Optimization

Speaking about optimality is speaking about comparing things. The basic mathematical instrument for the representation of optimality is the concept of a binary relation. Here, we want to recall some basic terms and definitions; for more details, see, for example, [15]. A (set-theoretic) binary relation R over a domain A is a subset of A
×
A; that is, a set of ordered pairs (
x
,
y
) with x
,
y
∈
A. It is said that x is in relation R to y (sometimes also written as x
R
y or, if the focus is on comparison, x
≥
R
y). There are alternative ways to represent relations, like a set comprehension, a mapping or function from A into the powerset of A, an incidence matrix or a directed graph. Also, relations can have properties. Two properties are of particular interest in the following; a relation issymmetric if from (
x
,
y
)
∈
R it follows that also (
y
,
x
)
∈
R and it is asymmetric if from (
x
,
y
)
∈
R it always follows that (
y
,
x
) does not belong to R. Each relation can be decomposed into a symmetric and an asymmetric part, written as R
=
I
(
R
)
∪
P
(
R
), where I
(
R
) is a symmetric relation and P
(
R
) is an asymmetric relation. It is easy to decide to which part a pair (
x
,
y
)
∈
R belongs in this decomposition; if (
y
,
x
) is also in R, it belongs to the symmetric part I
(
R
); if not, it belongs to the asymmetric part P
(
R
). It means that each relation, no matter what its domain is made of, shows mixed aspects of equality or similarity and a means of “betterness” or preference. For example, the real-valued “≥” relation is decomposed into an equivalence relation “=” as symmetric part and a strictly larger relation “>” as asymmetric part (which is well symbolized by ≥). If we write x
≥
R
y for a relation, then x
>
R
y will denote the asymmetric part, reflecting the “betterness” aspect of a relation R over domain A.Any relationR can expose specific elements of its domain A which are commonly called greatest, maximal, minimal, and least elements. Agreatest element x
* of the domain A with regard to R has the property that for any x
∈
A (including x
*) it holds that x
*
≥
R
x. All greatest elements comprise thebest set. Amaximal element x
* has the property that there is no x
∈
P
(
R
) such that x
>
R
x
* and all such x
* comprise themaximum set (of A with respect to R). Minimal and least elements are defined correspondingly. Note that they do not need to exist in general.One can easily see that a standard of comparison, as it was mentioned in the introduction section, is the same as the concept of a greatest element. However, often it is the case that best sets are empty. Therefore, it is convenient to refer to the maximum set as optimization goal, for several reasons. (1) In case of a finite domain, the maximum set is nonempty if the asymmetric part of the relation is cycle-free (i.e., the corresponding directed graph does not contain any cycles). (2) If there is a greatest element, it will also belong to the maximum set. (3) The maximum set can be seen as a “frontier”; they are not greatest elements but at least no better one is known.In [15], the special case of fairness relations has been intensively discussed. It is comparable and easy to represent proportional fairness, maxmin fairness, leximin fairness, α-fairness, and so forth by this relational framework. Then, (Pareto-) efficient solutions can be found by finding the maximum sets for these relations. But, the advantage is also that the transition of a relational concept to another domain becomes possible (by applying the same formal definition), or that the relation can be specified in such a way that completely new aspects are taken into account (e.g., multiresource usage, collaboration between agents, or vector-valued evaluations). This is because the concept of maximality applies to any relation, no matter what its domain is. Therefore, if we want to handle the above mentioned problem of pairwise weights, we just have to specify a corresponding relation (that is preferably cycle-free and Pareto-efficient).The last point that should be mentioned here is that the finding of maximum sets can be a challenging task, even if the complexityO
(
n
2
) is not so high. Thus, exhaustive search by a complete pairwise comparison can rapidly become intractable (e.g., a maximum set over a domain with one million elements would need 1
0
12 pairwise comparisons). One possibility is to use metaheuristic search algorithms to approximate maximum sets; other alternatives are currently under investigations. In case the relation is transitive, the search for maximum sets can be performed in “batches”; that is, decompose the domain into nonoverlapping subsets and find the maximum set for each subset and then the maximum set of the union of the found maximum sets.


### 2.2. Computational Fairness

We have now used the term “fairness” several times without providing a general definition. For example, considering a given relationR, when is it safe to say that this is a fairness relation? Actually, there is no common understanding of fairness to which all researchers and practitioners would fully agree. It would go beyond the scope of this paper to consider the numerous considerations that have been done in order to provide a computational model of fairness, but at least we can summarize the basic ideas. The additional restriction here is that the focus is on the modality of a distribution, thus excluding other societal important concepts like procedural fairness or interaction fairness.The common theme of all approaches to (distributional) fairness is to divide a set of resources among a number of agents. As already mentioned in the introduction, with far longest cultural history, we can find ideas about proportionality in the assignment (proportional according to demand, ability, suitability, availability, most available good, etc.) or the resolution of conflicts about contended goods in following an equity principle. Besides a relation point of view, in order to compare different possible assignments, the aspect can be also seen in aggregating the distributional aspects of all agents and thus keeping the spread of allocation differences small. This idea becomes strongly related to the theory of majorization [27], where numerical comparison between different ways of distributing the same total is strongly related to the Schur-convexity of the used comparison measure. The application of this approach and its various generalizations have been intensively studied, for example, in [28].Any continuation of a formal approach to fairness (in the sense of a “definition of fairness”) would need the specification ofaxioms that represent criteria derived from specific ways of how to balance—in a just way—the conflicts between agents that are in a better and agents that are in a worse situation—keeping in mind that fairness does generally not stand for the simple requirement of complete even allocations. Such axioms can refer to impartiality of distribution, consistency between solutions for different domains, mathematical assumptions about the domain, limiting behaviours, strategy-proofness of related procedures, or efficiency of the distribution.Saying this, the considered aspect of fairness here is the balance between users who would gain more and users who would gain less in an alternative allocation. We will use aggregation operators for representing the joint state of all winning and all loosing agents, thus basically following the “recipe” of proportional fairness. But, as a new aspect, we also want to take a different weighting for groups of agents into account. Fuzzy integrals are a well-known formal approach for such a representation.


### 2.3.  Fuzzy Measures and Integrals

We now want to recall basic issues of fuzzy measures and integrals in more detail. Most of the material can be gathered together from various publications and textbooks, but a comprehensive description, as it will be given now, might be of advantage for the understanding of the main proposal—a fairness relation based on the asymmetric Choquet integral for supermodular fuzzy measures.Throughout this paper, we consider a finite universal setN
:
=
{
1,2
,
…
,
n
} and 2
N denotes the power set of N.Definition 1 (Fuzzy measure [16, 17]).
A set functionμ
:
2
N
→
[
0
,
∞
) is a fuzzy measure if it satisfies the following conditions: (i)
μ
(
∅
)
=
0 and μ
(
N
)
<
+
∞,
(ii)
for anyS
,
T
∈
2
N
,
μ
(
S
)
≤
μ
(
T
) whenever S
⊂
T.
Properties (i) and (ii) express boundedness and monotonicity, respectively.Definition 2 (superadditivity, subadditivity).
A fuzzy measureμ is superadditive if μ satisfies μ
(
S
∪
T
)
≥
μ
(
S
)
+
μ
(
T
) and subadditive if μ satisfies μ
(
S
∪
T
)
≤
μ
(
S
)
+
μ
(
T
), for any S
,
T
∈
2
N satisfying S
∩
T
=
∅.Definition 3 (submodularity, supermodularity).
A fuzzy measureμ is supermodular if μ satisfies μ
(
S
∪
T
)
+
μ
(
S
∩
T
)
≥
μ
(
S
)
+
μ
(
T
) and submodular if μ satisfies μ
(
S
∪
T
)
+
μ
(
S
∩
T
)
≤
μ
(
S
)
+
μ
(
T
), for any S
,
T
∈
2
N.Definition 4 (dual measure).
Letμ be a fuzzy measure. The dual measure of μ is defined by
(2)
m
d
(
S
)
:
=
μ
(
N
)
-
μ
(
S
c
)
.
The dual measure of a fuzzy measure is also a fuzzy measure.Proposition 5.
Ifμ is supermodular, then μ is superadditive. If μ is submodular, then μ is subadditive.Proof.
Whenμ is supermodular, μ
(
S
∪
T
)
+
μ
(
S
∩
T
)
≥
μ
(
S
)
+
μ
(
T
) is satisfied for any S
,
T
∈
2
N, and S
∩
T
=
∅. It implies μ
(
S
∪
T
)
≥
μ
(
S
)
+
μ
(
T
) for any S
,
T
∈
2
N satisfying S
∩
T
=
∅. The second assertion is obtained in a similar manner.Proposition 6.
μ is supermodular if and only if μ
d is submodular. Similarly, μ is submodular if and only if μ
d is supermodular.Proof.
Assume thatμ is supermodular. Then, we have, for any S
,
T
∈
2
N,
(3)
μ
d
(
S
∪
T
)
+
μ
d
(
S
∩
T
)
=
μ
(
N
)
-
μ
(
(
S
∪
T
)
c
)
+
μ
(
N
)
-
μ
(
(
S
∩
T
)
c
)
=
2
μ
(
N
)
-
μ
(
S
c
∩
T
c
)
-
μ
(
S
c
∪
T
c
)
≤
2
μ
(
N
)
-
μ
(
S
c
)
-
μ
(
T
c
)
=
μ
d
(
S
)
+
μ
d
(
T
)
.
Following the above in reverse, we obtain the converse. Replacing ≤ with ≥, we obtain the second assertion.Proposition 7.
Ifμ is a superadditive fuzzy measure, then μ
d
(
S
)
≥
μ
(
S
) for any S
∈
2
N.Proof.
We haveμ
(
S
)
+
μ
(
S
c
)
≤
μ
(
N
) by superadditivity of μ. Hence, μ
(
S
)
≤
μ
(
N
)
-
μ
(
S
c
)
=
μ
d
(
S
).Definition 8 (λ-fuzzy measure).
A fuzzy measureμ is a λ-fuzzy measure if there exists λ
>
-
1 such that μ
(
S
∪
T
)
=
μ
(
S
)
+
μ
(
T
)
+
λ
μ
(
S
)
μ
(
T
) for any S
,
T
∈
2
N satisfying S
∩
T
=
∅ and μ
(
N
)
=
1.Definition 9 (χ-fuzzy measure).
A fuzzy measureμ on finite set N
=
{
1,2
,
…
,
n
} is a χ-fuzzy measure if there exists
(4)
χ
≥
1
-
min
⁡
i
∈
N
μ
(
{
i
}
)
∑
i
∈
N
μ
(
{
i
}
)
such that
(5)
μ
(
S
)
=
χ
|
S
|
-
1
∑
i
∈
S
‍
μ
(
{
i
}
)
for any S
∈
2
N. Here, |
S
| denotes the cardinal number of S.λ
≥
0 and χ
≥
1 imply superadditivity, and λ
≤
0 and χ
≤
1 imply subadditivity. The dual measure of a λ-fuzzy measure and of a χ-fuzzy measure are not necessarily a λ-fuzzy measure and a χ-fuzzy measure.Proposition 10.
Letμ be a λ-fuzzy measure. Then, μ is superadditive if and only if μ is supermodular. Similarly, μ is subadditive if and only if μ is submodular.Proof.
The sufficiencies hold by Proposition5. We show the necessities.
Assumeμ is a superadditive λ-fuzzy measure; that is, λ
≥
0. Then, we have, for any S
,
T
∈
2
N,
(6)
μ
(
S
∪
T
)
+
μ
(
S
∩
T
)
=
μ
(
S
)
+
μ
(
T
∖
S
)
+
λ
μ
(
S
)
μ
(
T
∖
S
)
+
μ
(
S
∩
T
)
≥
μ
(
S
)
+
μ
(
T
∖
S
)
+
λ
μ
(
S
∩
T
)
μ
(
T
∖
S
)
+
μ
(
S
∩
T
)
=
μ
(
S
)
+
μ
(
T
)
.
Replacing ≤ with ≥, we obtain the second assertion.Definition 11 (Choquet integral [19]).
Given a fuzzy measureμ
:
2
N
→
[
0,1
] and a nonnegative function f on N, the Choquet integral of f with respect to μ is defined by
(7)
(
C
)
∫
‍
f
d
μ
=
∫
0
+
∞
‍
μ
(
{
x
f
(
x
)
>
r
}
)
d
r
.In the case thatN is a finite set, (7) can be rewritten as
(8)
(
C
)
∫
‍
f
d
μ
:
=
∑
i
=
1
n
‍
(
a
i
-
a
i
-
1
)
μ
(
S
i
)
,
where a
i
:
=
f
(
i
), a
0
=
0, a
1
≤
a
2
≤
⋯
≤
a
n, and S
i
:
=
{
i
,
…
,
n
}. (cf. Figure 1). Note that this computation will include a permutation reordering of the a
i to ensure that they are in nondecreasing order.Figure 1
Choquet integral.The Choquet integral can be generalized to general functions, which are not necessarily nonnegative, in several ways. Here, we show the following two generalizations, the asymmetric Choquet integral and the symmetric Choquet integral.Definition 12 (asymmetric Choquet integral [18]).
Given a fuzzy measureμ
:
2
N
→
[
0,1
] and a function f on N, the asymmetric Choquet integral of f with respect to μ is defined by
(9)
(
ASC
)
∫
‍
f
d
μ
∶
=
∫
-
∞
0
‍
(
μ
(
{
x
∣
f
(
x
)
>
r
}
)
ddddddddd
-
m
(
N
)
)
d
r
+
∫
0
+
∞
‍
μ
(
x
∣
f
(
x
)
>
r
)
d
r
.Definition 13 (symmetric Choquet integral [20]).
Given a fuzzy measureμ
:
2
N
→
[
0,1
] and a function f on N, the symmetric Choquet integral of f with respect to μ is defined by(10)
(
SC
)
∫
‍
f
d
μ
∶
=
-
∫
0
+
∞
‍
μ
(
{
x
∣
f
-
(
x
)
>
r
}
)
d
r
+
∫
0
+
∞
‍
μ
(
{
x
∣
f
+
(
x
)
>
r
}
)
d
r
,
where f
+
:
=
f
∨
0
,
f
-
:
=
-
(
f
∧
0
).Proposition 14.
Consider(11)
(
ASC
)
∫
‍
f
d
μ
=
-
∫
-
∞
0
‍
μ
d
(
{
x
∣
f
-
(
x
)
>
r
}
)
d
r
+
∫
0
+
∞
‍
μ
(
{
x
∣
f
+
(
x
)
>
r
}
)
d
r
.Proof.
Because(12)
∫
-
∞
0
‍
(
μ
(
{
x
∣
f
(
x
)
>
r
}
)
-
μ
(
N
)
)
d
r
=
∫
‍
(
μ
(
{
x
∣
-
f
-
(
x
)
>
r
}
)
-
μ
(
N
)
)
d
r
=
-
∫
‍
(
μ
(
{
x
∣
f
-
(
x
)
≤
r
}
)
-
μ
(
N
)
)
d
r
=
-
∫
‍
μ
d
(
{
x
∣
f
-
(
x
)
>
r
}
)
d
r
.By this proposition, we can say that the difference between the asymmetric Choquet integral and the symmetric Choquet integral is based on which measure are used for integrating the negative part off.


## 2.1. Relational Optimization

Speaking about optimality is speaking about comparing things. The basic mathematical instrument for the representation of optimality is the concept of a binary relation. Here, we want to recall some basic terms and definitions; for more details, see, for example, [15]. A (set-theoretic) binary relation R over a domain A is a subset of A
×
A; that is, a set of ordered pairs (
x
,
y
) with x
,
y
∈
A. It is said that x is in relation R to y (sometimes also written as x
R
y or, if the focus is on comparison, x
≥
R
y). There are alternative ways to represent relations, like a set comprehension, a mapping or function from A into the powerset of A, an incidence matrix or a directed graph. Also, relations can have properties. Two properties are of particular interest in the following; a relation issymmetric if from (
x
,
y
)
∈
R it follows that also (
y
,
x
)
∈
R and it is asymmetric if from (
x
,
y
)
∈
R it always follows that (
y
,
x
) does not belong to R. Each relation can be decomposed into a symmetric and an asymmetric part, written as R
=
I
(
R
)
∪
P
(
R
), where I
(
R
) is a symmetric relation and P
(
R
) is an asymmetric relation. It is easy to decide to which part a pair (
x
,
y
)
∈
R belongs in this decomposition; if (
y
,
x
) is also in R, it belongs to the symmetric part I
(
R
); if not, it belongs to the asymmetric part P
(
R
). It means that each relation, no matter what its domain is made of, shows mixed aspects of equality or similarity and a means of “betterness” or preference. For example, the real-valued “≥” relation is decomposed into an equivalence relation “=” as symmetric part and a strictly larger relation “>” as asymmetric part (which is well symbolized by ≥). If we write x
≥
R
y for a relation, then x
>
R
y will denote the asymmetric part, reflecting the “betterness” aspect of a relation R over domain A.Any relationR can expose specific elements of its domain A which are commonly called greatest, maximal, minimal, and least elements. Agreatest element x
* of the domain A with regard to R has the property that for any x
∈
A (including x
*) it holds that x
*
≥
R
x. All greatest elements comprise thebest set. Amaximal element x
* has the property that there is no x
∈
P
(
R
) such that x
>
R
x
* and all such x
* comprise themaximum set (of A with respect to R). Minimal and least elements are defined correspondingly. Note that they do not need to exist in general.One can easily see that a standard of comparison, as it was mentioned in the introduction section, is the same as the concept of a greatest element. However, often it is the case that best sets are empty. Therefore, it is convenient to refer to the maximum set as optimization goal, for several reasons. (1) In case of a finite domain, the maximum set is nonempty if the asymmetric part of the relation is cycle-free (i.e., the corresponding directed graph does not contain any cycles). (2) If there is a greatest element, it will also belong to the maximum set. (3) The maximum set can be seen as a “frontier”; they are not greatest elements but at least no better one is known.In [15], the special case of fairness relations has been intensively discussed. It is comparable and easy to represent proportional fairness, maxmin fairness, leximin fairness, α-fairness, and so forth by this relational framework. Then, (Pareto-) efficient solutions can be found by finding the maximum sets for these relations. But, the advantage is also that the transition of a relational concept to another domain becomes possible (by applying the same formal definition), or that the relation can be specified in such a way that completely new aspects are taken into account (e.g., multiresource usage, collaboration between agents, or vector-valued evaluations). This is because the concept of maximality applies to any relation, no matter what its domain is. Therefore, if we want to handle the above mentioned problem of pairwise weights, we just have to specify a corresponding relation (that is preferably cycle-free and Pareto-efficient).The last point that should be mentioned here is that the finding of maximum sets can be a challenging task, even if the complexityO
(
n
2
) is not so high. Thus, exhaustive search by a complete pairwise comparison can rapidly become intractable (e.g., a maximum set over a domain with one million elements would need 1
0
12 pairwise comparisons). One possibility is to use metaheuristic search algorithms to approximate maximum sets; other alternatives are currently under investigations. In case the relation is transitive, the search for maximum sets can be performed in “batches”; that is, decompose the domain into nonoverlapping subsets and find the maximum set for each subset and then the maximum set of the union of the found maximum sets.


## 2.2. Computational Fairness

We have now used the term “fairness” several times without providing a general definition. For example, considering a given relationR, when is it safe to say that this is a fairness relation? Actually, there is no common understanding of fairness to which all researchers and practitioners would fully agree. It would go beyond the scope of this paper to consider the numerous considerations that have been done in order to provide a computational model of fairness, but at least we can summarize the basic ideas. The additional restriction here is that the focus is on the modality of a distribution, thus excluding other societal important concepts like procedural fairness or interaction fairness.The common theme of all approaches to (distributional) fairness is to divide a set of resources among a number of agents. As already mentioned in the introduction, with far longest cultural history, we can find ideas about proportionality in the assignment (proportional according to demand, ability, suitability, availability, most available good, etc.) or the resolution of conflicts about contended goods in following an equity principle. Besides a relation point of view, in order to compare different possible assignments, the aspect can be also seen in aggregating the distributional aspects of all agents and thus keeping the spread of allocation differences small. This idea becomes strongly related to the theory of majorization [27], where numerical comparison between different ways of distributing the same total is strongly related to the Schur-convexity of the used comparison measure. The application of this approach and its various generalizations have been intensively studied, for example, in [28].Any continuation of a formal approach to fairness (in the sense of a “definition of fairness”) would need the specification ofaxioms that represent criteria derived from specific ways of how to balance—in a just way—the conflicts between agents that are in a better and agents that are in a worse situation—keeping in mind that fairness does generally not stand for the simple requirement of complete even allocations. Such axioms can refer to impartiality of distribution, consistency between solutions for different domains, mathematical assumptions about the domain, limiting behaviours, strategy-proofness of related procedures, or efficiency of the distribution.Saying this, the considered aspect of fairness here is the balance between users who would gain more and users who would gain less in an alternative allocation. We will use aggregation operators for representing the joint state of all winning and all loosing agents, thus basically following the “recipe” of proportional fairness. But, as a new aspect, we also want to take a different weighting for groups of agents into account. Fuzzy integrals are a well-known formal approach for such a representation.


## 2.3.  Fuzzy Measures and Integrals

We now want to recall basic issues of fuzzy measures and integrals in more detail. Most of the material can be gathered together from various publications and textbooks, but a comprehensive description, as it will be given now, might be of advantage for the understanding of the main proposal—a fairness relation based on the asymmetric Choquet integral for supermodular fuzzy measures.Throughout this paper, we consider a finite universal setN
:
=
{
1,2
,
…
,
n
} and 2
N denotes the power set of N.Definition 1 (Fuzzy measure [16, 17]).
A set functionμ
:
2
N
→
[
0
,
∞
) is a fuzzy measure if it satisfies the following conditions: (i)
μ
(
∅
)
=
0 and μ
(
N
)
<
+
∞,
(ii)
for anyS
,
T
∈
2
N
,
μ
(
S
)
≤
μ
(
T
) whenever S
⊂
T.
Properties (i) and (ii) express boundedness and monotonicity, respectively.Definition 2 (superadditivity, subadditivity).
A fuzzy measureμ is superadditive if μ satisfies μ
(
S
∪
T
)
≥
μ
(
S
)
+
μ
(
T
) and subadditive if μ satisfies μ
(
S
∪
T
)
≤
μ
(
S
)
+
μ
(
T
), for any S
,
T
∈
2
N satisfying S
∩
T
=
∅.Definition 3 (submodularity, supermodularity).
A fuzzy measureμ is supermodular if μ satisfies μ
(
S
∪
T
)
+
μ
(
S
∩
T
)
≥
μ
(
S
)
+
μ
(
T
) and submodular if μ satisfies μ
(
S
∪
T
)
+
μ
(
S
∩
T
)
≤
μ
(
S
)
+
μ
(
T
), for any S
,
T
∈
2
N.Definition 4 (dual measure).
Letμ be a fuzzy measure. The dual measure of μ is defined by
(2)
m
d
(
S
)
:
=
μ
(
N
)
-
μ
(
S
c
)
.
The dual measure of a fuzzy measure is also a fuzzy measure.Proposition 5.
Ifμ is supermodular, then μ is superadditive. If μ is submodular, then μ is subadditive.Proof.
Whenμ is supermodular, μ
(
S
∪
T
)
+
μ
(
S
∩
T
)
≥
μ
(
S
)
+
μ
(
T
) is satisfied for any S
,
T
∈
2
N, and S
∩
T
=
∅. It implies μ
(
S
∪
T
)
≥
μ
(
S
)
+
μ
(
T
) for any S
,
T
∈
2
N satisfying S
∩
T
=
∅. The second assertion is obtained in a similar manner.Proposition 6.
μ is supermodular if and only if μ
d is submodular. Similarly, μ is submodular if and only if μ
d is supermodular.Proof.
Assume thatμ is supermodular. Then, we have, for any S
,
T
∈
2
N,
(3)
μ
d
(
S
∪
T
)
+
μ
d
(
S
∩
T
)
=
μ
(
N
)
-
μ
(
(
S
∪
T
)
c
)
+
μ
(
N
)
-
μ
(
(
S
∩
T
)
c
)
=
2
μ
(
N
)
-
μ
(
S
c
∩
T
c
)
-
μ
(
S
c
∪
T
c
)
≤
2
μ
(
N
)
-
μ
(
S
c
)
-
μ
(
T
c
)
=
μ
d
(
S
)
+
μ
d
(
T
)
.
Following the above in reverse, we obtain the converse. Replacing ≤ with ≥, we obtain the second assertion.Proposition 7.
Ifμ is a superadditive fuzzy measure, then μ
d
(
S
)
≥
μ
(
S
) for any S
∈
2
N.Proof.
We haveμ
(
S
)
+
μ
(
S
c
)
≤
μ
(
N
) by superadditivity of μ. Hence, μ
(
S
)
≤
μ
(
N
)
-
μ
(
S
c
)
=
μ
d
(
S
).Definition 8 (λ-fuzzy measure).
A fuzzy measureμ is a λ-fuzzy measure if there exists λ
>
-
1 such that μ
(
S
∪
T
)
=
μ
(
S
)
+
μ
(
T
)
+
λ
μ
(
S
)
μ
(
T
) for any S
,
T
∈
2
N satisfying S
∩
T
=
∅ and μ
(
N
)
=
1.Definition 9 (χ-fuzzy measure).
A fuzzy measureμ on finite set N
=
{
1,2
,
…
,
n
} is a χ-fuzzy measure if there exists
(4)
χ
≥
1
-
min
⁡
i
∈
N
μ
(
{
i
}
)
∑
i
∈
N
μ
(
{
i
}
)
such that
(5)
μ
(
S
)
=
χ
|
S
|
-
1
∑
i
∈
S
‍
μ
(
{
i
}
)
for any S
∈
2
N. Here, |
S
| denotes the cardinal number of S.λ
≥
0 and χ
≥
1 imply superadditivity, and λ
≤
0 and χ
≤
1 imply subadditivity. The dual measure of a λ-fuzzy measure and of a χ-fuzzy measure are not necessarily a λ-fuzzy measure and a χ-fuzzy measure.Proposition 10.
Letμ be a λ-fuzzy measure. Then, μ is superadditive if and only if μ is supermodular. Similarly, μ is subadditive if and only if μ is submodular.Proof.
The sufficiencies hold by Proposition5. We show the necessities.
Assumeμ is a superadditive λ-fuzzy measure; that is, λ
≥
0. Then, we have, for any S
,
T
∈
2
N,
(6)
μ
(
S
∪
T
)
+
μ
(
S
∩
T
)
=
μ
(
S
)
+
μ
(
T
∖
S
)
+
λ
μ
(
S
)
μ
(
T
∖
S
)
+
μ
(
S
∩
T
)
≥
μ
(
S
)
+
μ
(
T
∖
S
)
+
λ
μ
(
S
∩
T
)
μ
(
T
∖
S
)
+
μ
(
S
∩
T
)
=
μ
(
S
)
+
μ
(
T
)
.
Replacing ≤ with ≥, we obtain the second assertion.Definition 11 (Choquet integral [19]).
Given a fuzzy measureμ
:
2
N
→
[
0,1
] and a nonnegative function f on N, the Choquet integral of f with respect to μ is defined by
(7)
(
C
)
∫
‍
f
d
μ
=
∫
0
+
∞
‍
μ
(
{
x
f
(
x
)
>
r
}
)
d
r
.In the case thatN is a finite set, (7) can be rewritten as
(8)
(
C
)
∫
‍
f
d
μ
:
=
∑
i
=
1
n
‍
(
a
i
-
a
i
-
1
)
μ
(
S
i
)
,
where a
i
:
=
f
(
i
), a
0
=
0, a
1
≤
a
2
≤
⋯
≤
a
n, and S
i
:
=
{
i
,
…
,
n
}. (cf. Figure 1). Note that this computation will include a permutation reordering of the a
i to ensure that they are in nondecreasing order.Figure 1
Choquet integral.The Choquet integral can be generalized to general functions, which are not necessarily nonnegative, in several ways. Here, we show the following two generalizations, the asymmetric Choquet integral and the symmetric Choquet integral.Definition 12 (asymmetric Choquet integral [18]).
Given a fuzzy measureμ
:
2
N
→
[
0,1
] and a function f on N, the asymmetric Choquet integral of f with respect to μ is defined by
(9)
(
ASC
)
∫
‍
f
d
μ
∶
=
∫
-
∞
0
‍
(
μ
(
{
x
∣
f
(
x
)
>
r
}
)
ddddddddd
-
m
(
N
)
)
d
r
+
∫
0
+
∞
‍
μ
(
x
∣
f
(
x
)
>
r
)
d
r
.Definition 13 (symmetric Choquet integral [20]).
Given a fuzzy measureμ
:
2
N
→
[
0,1
] and a function f on N, the symmetric Choquet integral of f with respect to μ is defined by(10)
(
SC
)
∫
‍
f
d
μ
∶
=
-
∫
0
+
∞
‍
μ
(
{
x
∣
f
-
(
x
)
>
r
}
)
d
r
+
∫
0
+
∞
‍
μ
(
{
x
∣
f
+
(
x
)
>
r
}
)
d
r
,
where f
+
:
=
f
∨
0
,
f
-
:
=
-
(
f
∧
0
).Proposition 14.
Consider(11)
(
ASC
)
∫
‍
f
d
μ
=
-
∫
-
∞
0
‍
μ
d
(
{
x
∣
f
-
(
x
)
>
r
}
)
d
r
+
∫
0
+
∞
‍
μ
(
{
x
∣
f
+
(
x
)
>
r
}
)
d
r
.Proof.
Because(12)
∫
-
∞
0
‍
(
μ
(
{
x
∣
f
(
x
)
>
r
}
)
-
μ
(
N
)
)
d
r
=
∫
‍
(
μ
(
{
x
∣
-
f
-
(
x
)
>
r
}
)
-
μ
(
N
)
)
d
r
=
-
∫
‍
(
μ
(
{
x
∣
f
-
(
x
)
≤
r
}
)
-
μ
(
N
)
)
d
r
=
-
∫
‍
μ
d
(
{
x
∣
f
-
(
x
)
>
r
}
)
d
r
.By this proposition, we can say that the difference between the asymmetric Choquet integral and the symmetric Choquet integral is based on which measure are used for integrating the negative part off.


## 3. Description of Fairness by the Choquet Integral

In this section, we discuss the generalized Choquet integrals in terms of describing fairness by the Choquet integral. Letμ be a fuzzy measure on 2
N and f
=
(
x
1
,
x
2
,
…
,
x
n
) a function on N. For example, N corresponds to a set consisting of n players and f corresponds to a distribution of resources, where f can take negative values. The more players are satisfied, the fairer the distribution is.Example 15.
Letn
=
3 and there are 6 resources. Then, f
1
=
(
2,2
,
2
) is fairer than f
2
=
(
4,2
,
0
) and f
2 is fairer than f
3
=
(
6,0
,
0
). To describe this, we use the Choquet integral with respect to a submodular function. Suppose that μ
(
S
) takes the same values according to |
S
| (note that in this case the Choquet integral becomes an OWA operator and properties like submodularity depend on the choice of OWA weights). If μ is submodular, then we have
(13)
(
C
)
∫
‍
f
1
d
μ
≥
(
C
)
∫
‍
f
2
d
μ
≥
(
C
)
∫
‍
f
3
d
μ
.
Next, we consider the negative distribution.Example 16.
Letn
=
3 and there are -
6 resources. Then, f
1
=
(
-
2
,
-
2
,
-
2
) is fairer than f
2
=
(
-
4
,
-
2,0
) and f
2 is fairer than f
3
=
(
-
6,0
,
0
). Let μ be a submodular function. If we use the symmetric Choquet integral, then we have
(14)
(
SC
)
∫
‍
f
1
d
μ
≤
(
SC
)
∫
‍
f
2
d
μ
≤
(
SC
)
∫
‍
f
3
d
μ
,
where all integrals take negative values. And if μ
′ would be another but superadditive fuzzy measure, then we obtain
(15)
(
SC
)
∫
‍
f
1
d
μ
′
≥
(
SC
)
∫
‍
f
2
d
μ
′
≥
(
SC
)
∫
‍
f
3
d
μ
′
which is not what we wanted. In other words, we can never describe both positive fairness and negative fairness by one fuzzy measure using the symmetric Choquet integral. On the other hand, using the asymmetric Choquet integral with respect to μ where μ
d is superadditive, we obtain
(16)
(
ASC
)
∫
‍
f
1
d
μ
≥
(
ASC
)
∫
‍
f
2
d
μ
≥
(
ASC
)
∫
‍
f
3
d
μ
.
If μ is a supermodular fuzzy measure, then μ is superadditive and μ
d is subadditive. Therefore, using the asymmetric Choquet integral with respect to a supermodular fuzzy measure, we can describe both positive fairness and negative fairness by one fuzzy measure.According to these examples, the asymmetric Choquet integral with respect to a superadditive fuzzy measure is better suited for describing fairness. The Möbius transform enables us to construct fuzzy measure easily.Definition 17 (Möbius transform).
The Möbius transform ofμ, denoted by m
μ
:
2
N
→
[
-
1,1
], is defined by
(17)
m
μ
(
S
)
:
=
∑
T
⊆
S
‍
(
-
1
)
|
S
∖
T
|
μ
(
T
)
for any S
∈
2
N. Conversely, we obtain
(18)
μ
(
S
)
=
∑
T
⊆
S
‍
m
μ
(
T
)
by the inverse Möbius transform for any S
∈
2
N, and there is a one-to-one correspondence between μ and m
μ.Note that if the sum of all Möbius masses is 1, then the corresponding fuzzy measure of the whole set is 1.Proposition 18.
Ifm
μ
(
S
)
≥
0 for any S
∈
2
N, then μ is supermodular.Proof.
Assume, for anyS
∈
2
N, m
μ
(
S
)
≥
0. Then, denoting that r
:
=
S
∖
T
,
s
:
=
S
∩
T
,
t
:
=
T
∖
S for S
,
T
∈
2
N, we have
(19)
μ
(
S
∪
T
)
+
μ
(
S
∩
T
)
=
∑
C
⊆
S
∪
T
‍
m
μ
(
U
)
+
∑
U
⊆
S
∩
T
‍
m
μ
(
U
)
=
(
∑
U
⊆
r
‍
+
∑
U
⊆
s
‍
+
∑
U
⊆
t
‍
+
∑
U
⊆
r
∪
s
,
U
∩
r
≠
∅
,
U
∩
s
≠
∅
ggggg
+
∑
U
⊆
s
∪
t
,
U
∩
s
≠
∅
,
U
∩
t
≠
∅
‍
+
∑
U
⊆
r
∪
t
,
U
∩
r
≠
∅
,
U
∩
t
≠
∅
‍
g
g
+
∑
U
⊆
r
∪
s
∪
t
,
U
∩
r
≠
∅
,
U
∩
s
≠
∅
,
U
∩
t
≠
∅
)
m
μ
(
U
)
+
∑
U
⊆
s
‍
m
μ
(
U
)
,
μ
(
S
)
+
μ
(
T
)
=
∑
U
⊆
S
‍
m
μ
(
U
)
+
∑
U
⊆
T
‍
m
μ
(
U
)
=
(
∑
U
⊆
r
‍
+
∑
U
⊆
s
‍
+
∑
U
⊆
r
∪
s
,
U
∩
r
≠
∅
,
U
∩
s
≠
∅
‍
)
m
μ
(
U
)
+
(
∑
U
⊆
s
‍
+
∑
U
⊆
t
‍
+
∑
U
⊆
s
∪
t
,
U
∩
s
≠
∅
,
U
∩
t
≠
∅
)
m
μ
(
U
)
,
so that we obtain(20)
(
μ
(
S
∪
T
)
+
μ
(
s
)
)
-
(
μ
(
S
)
+
μ
(
T
)
)
=
(
∑
U
⊆
r
∪
s
∪
t
,
U
∩
r
≠
∅
,
U
∩
s
≠
∅
,
U
∩
t
≠
∅
‍
∑
U
⊆
r
∪
t
,
U
∩
r
≠
∅
,
U
∩
t
≠
∅
ggggg
+
∑
U
⊆
r
∪
s
∪
t
,
U
∩
r
≠
∅
,
U
∩
s
≠
∅
,
U
∩
t
≠
∅
‍
)
m
μ
(
U
)
≥
0
.Remark 19.
The converse of Proposition18 is not necessarily true. In fact, define m
μ on N
=
{
1,2
,
3
} by
(21)
m
μ
(
S
)
:
=
{
0
,
S
=
∅
,
1
,
S
≠
∅
,
{
1,2
,
3
}
,
-
1
2
,
S
=
{
1,2
,
3
}
.
Then, we obtain a supermodular fuzzy measure,
(22)
μ
(
∅
)
=
0
,
μ
(
{
1
}
)
=
μ
(
{
2
}
)
=
μ
(
{
3
}
)
=
1
,
μ
(
{
1,2
}
)
=
μ
(
{
1,3
}
)
=
μ
(
{
2,3
}
)
=
3
,
μ
(
{
1,2
,
3
}
)
=
11
2
.


## 4. Fairness Relation Using the Asymmetric Choquet Integral

Definition 20 (Choquet Integral relation).
Letx
=
(
x
1
,
x
2
,
…
,
x
n
), let y
=
(
y
1
,
y
2
,
…
,
y
n
), and let μ be a fuzzy measure. x is said to CI-dominate y, denoted by x
≥
μ
y, if and only if
(23)
(
ASC
)
∫
‍
(
x
-
y
)
d
μ
≥
θ
.AssumeN is a set of all players x and y are distributions of resources to all players. Then, x
-
y means each degree of satisfaction of the distribution x compared with the distribution y. Since the more players are satisfied, the fairer the distribution is, x
≥
μ
y means x is at least as fair as y. By x
>
μ
y we denote the corresponding strict relation.Proposition 21.
Letμ be a superadditive fuzzy measure on 2
N. Then, it is an antisymmetric relation; that is, x
≥
μ
y and y
≥
μ
x implies x
=
y for any functions x
,
y on N.Proposition 22.
Ifμ is a supermodular measure on 2
N, then >
μ is a transitive relation; that is, if x
≥
μ
y and y
≥
μ
z, then x
≥
μ
z for any functions x
,
y
,
z on N.By Propositions21 and 22, using the asymmetric Choquet integral with respect to supermodular functions, we obtain a fair ordering relation.The proofs for Propositions21 and 22 will be given in the Appendix of this paper.


## 5. Decision Making by CI-Fairness: A Numerical Example

In this section, we want to demonstrate how CI-fairness relation can be used for decision making. Consider a situation where resources have to be allocated to 3 agentsA
,
B, and C, but sets of agents can utilize resources differently (e.g., giving a commodity to one agent, how many items can she produce within a time unit?). Such resource utilization can be assessed by a fuzzy measure:
(24)
subset
S
μ
(
S
)
∅
0
A
0.1
B
0.3
C
0.5
A
,
B
0.5
A
,
C
0.5
B
,
C
0.8
A
,
B
,
C
1Here, for example,C appears to be the best in resource utilization, but A is good in collaboration. The measure is superadditive. We can also see that this is a supermodular measure. There are 3 cases to check; the other follow from subsethood or superadditivity:(1)
μ
(
{
A
,
B
}
∪
{
A
,
C
}
)
+
μ
(
{
A
,
B
}
∩
{
A
,
C
}
)
=
μ
(
{
A
,
B
,
C
}
)
+
μ
(
{
A
}
)
=
1.1
≥
μ
(
{
A
,
B
}
)
+
μ
(
{
A
,
C
}
)
=
1.0;
(2)
μ
(
{
A
,
B
}
∪
{
B
,
C
}
)
+
μ
(
{
A
,
B
}
∩
{
B
,
C
}
)
=
μ
(
{
A
,
B
,
C
}
)
+
μ
(
{
B
}
)
=
1.3
≥
μ
(
{
A
,
B
}
)
+
μ
(
{
B
,
C
}
)
=
1.3;
(3)
μ
(
{
A
,
C
}
∪
{
B
,
C
}
)
+
μ
(
{
A
,
C
}
∩
{
B
,
C
}
)
=
μ
(
{
A
,
B
,
C
}
)
+
μ
(
{
C
}
)
=
1.5
≥
μ
(
{
A
,
C
}
)
+
μ
(
{
B
,
C
}
)
=
1.3;
(25)
(
1,2
,
3
)
≥
μ
(
1,3
,
2
)
(
1,2
,
3
)
≥
μ
(
2,1
,
3
)
(
1,2
,
3
)
≥
μ
(
2,3
,
1
)
(
1,2
,
3
)
≥
μ
(
3,1
,
2
)
(
1,2
,
3
)
≥
μ
(
3,2
,
1
)
(
1,3
,
2
)
≥
μ
(
2,3
,
1
)
(
1,3
,
2
)
≥
μ
(
3,1
,
2
)
(
1,3
,
2
)
≥
μ
(
3,2
,
1
)
(
2,1
,
3
)
≥
μ
(
2,3
,
1
)
(
2,1
,
3
)
≥
μ
(
3,1
,
2
)
(
2,1
,
3
)
≥
μ
(
3,2
,
1
)
(
2,3
,
1
)
≥
μ
(
3,2
,
1
)
(
3,1
,
2
)
≥
μ
(
3,2
,
1
)
.We find the allocation (
1,2
,
3
) in relation to all other allocations, but no allocation is in relation to (
1,2
,
3
). This is natural, given the order of resource utilization weights for the three agents. By rank, we can now also order the other 5 allocations.Now, we want to allocate three shares of a resource of 6 units(
1,2
,
3
) among A
,
B
,
C and compare the 6 possible permutations of (
1,2
,
3
) by the Choquet integral relation with θ
=
0. For example, to see if allocation x
=
(
1,2
,
3
) is in relation to the allocation y
=
(
2,3
,
1
), we have to test
(26)
(
C
)
∫
‍
[
x
-
y
]
+
d
μ
≥
(
C
)
∫
‍
[
y
-
x
]
+
d
μ
d
.
In this case, [
x
-
y
]
+
=
(
0,0
,
2
) and [
y
-
x
]
+
=
(
1,1
,
0
). So, the first integral becomes 2
×
μ
(
{
C
}
)
=
1.0 and the second integral 1
×
μ
d
(
{
A
,
B
}
)
=
(
1
-
μ
(
{
C
}
)
)
=
0.5. From 1.0
≥
0.5, then x
≥
μ
y follows.Among all possible 30 pairs(
x
,
y
) with x
≠
y, we can find 13 cases in total where the Choquet integral relation holds.Figure2 shows the Hasse diagram of the relation for the 6 possible allocations. We can see that, as an effect of the better collaboration weight of A, allocation (
2,1
,
3
) is promoted and appears on the same rank as the strong allocation (
1,3
,
2
) (strong with regard to single agent utilization of a resource) and also of better rank than the allocation (
2,3
,
1
)—expressing the preference for C as partner of A when comparing possible wins and losses in the allocation. Finally, as expected, there is no case to allocate 3 shares to A.Figure 2
CI-Fairness relation among six possible allocations. The connections include transitivity.


## 6. Experiments

In this section, we will show how the CI-fairness can be applied in a practical situation. We study wireless channel allocation in the network layer; a base station BS that is connected to the backbone can command over a numberm of wireless transmissionchannels and allocates them to a number n of users (or subscriber stations, mobile stations, relay stations, etc.—depending on the specific network architecture) for uplink or downlink traffic. In the most abstract notation, the BS makes the allocation based on a measured or estimatedchannel state information; if it allocates a channel i to user j there will be achannel coefficient
C
i
j from [
0,1
] that represents (in a simplified form) to what degree the user can employ that channel. For example, remote users are likely to have smaller channel coefficients than users that are close to the BS. Here, an allocation is seen asfeasible if each channel is allocated to one user and to each user at least one channel is assigned.The sum of all channel coefficients of allocated channels for a specific user is seen as theperformance of the allocation for that user. Then, the optimality task is related to the performance vector for all users. This is a direct reference to a relation between performance vectors, and various fairness relations can be easily and conveniently studied in this context. If the number of channels and users is not too large, exhaustive search for maximum sets is possible. For example, for 4 users and 6 channels, there are 1560 feasible allocations, which means about 2.4 Mio. pairwise comparisons.In this model, channel allocation ignores low channel interferences between users and specific channels by the restriction that each channel is allocated to exactly one user. However, if implementing a wireless access where some users can use the same channel for transmission, it might be hard to decide the exact schedule of such multiple assignments, or to decide if installing such a scheme at all. Therefore, we follow a more simplified approach; channel interference will be represented by a conflict matrix between users, where low elements for pairs of users indicate the option to use multichannel assignment. Then, we use the converse elements of the conflict matrix as masses in the Möbius transform. More specifically, the Möbius masses for single element sets are set to equal values, the masses for two-element are set to 1 minus the corresponding element of the conflict matrix, and all other are set to 0. Then, the massvector is normalized to a total of all masses of 1 to ensure that for the fuzzy measure the measure for the whole set is 1. The inverse Möbius transform of such a mass vector gives a supermodular measure that can be used to specify a CI-based fairness relation according to Definition20.Now, this relation is applied to all feasible channel allocations—it means we are not considering a specific use of multichannel assignment but we are looking for the influence that such a multichannel allocation could have on the specific selection of maximal elements. Then, the focus is on the disadvantage that some pairs of users can experience if their favoured situation (e.g., to be distant enough to use the same channel) is not taken into account. The similar approach can be considered for cognitive radio, opportunistic networking, P2P, vehicular networks, and so forth.We might especially look for theprice of fairness [1], compared to a standard proportional fair or maxmin fair allocation.Some example results are shown in Table1. There, for the case of 4 users and 6 cells, the maximum sets over all feasible allocations were computed for CI-fairness using a measure as described above, proportional fairness, and maxmin fairness. The conflict matrix elements for the CI-fairness were uniform randomly set within specific ranges. All results are averaged over 30 repetitions. Note that average sizes of maximum sets were found to be 4.2 for maxmin fairness, 6.1 for proportional fairness, and 41.9 for CI-fairness, so the CI-fairness produces larger maximum sets, an issue that should be addressed in future works. The table now shows average performances over all maximal elements.Table 1
Comparison of total performances for capacity, proportional, and maxmin fairness.
Fairness relation
Average performance
Conflict matrix range 0 to 1
CI
4.2882
Proportional
4.54661
maxmin
4.14688
Conflict matrix range 0.9 to 1
CI
4.56051
Proportional
4.51135
maxmin
4.22561
Conflict matrix range 0 to 0.2
CI
4.09365
Proportional
4.41848
maxmin
4.04879We see with regard to efficiency the well-known fact that proportional-fair allocations are in average more efficient than maxmin fair allocations. The CI-fairness appears to select maximal relations with a total performance between proportional fairness and maxmin fairness. In case of strong interferences (where a multichannel assignment is not reasonable), it is very close to proportional fairness, while in case of low interference it appears to be more close to maxmin fairness, that is, the fairness relation favouring least elements. Thus, such an empirical result can be understood in the sense that the neglecting of the potential multichannel assignment corresponds with the neglection of strong users. This is also particularly appearing for the general case, where all conflict matrix elements were randomly selected between 0 and 1; also here, the average performance appears more close to maxmin fairness than proportional fairness.


## 7. Conclusion

A fairness relation among vectors based on the asymmetric Choquet integral was studied. It formally follows the Nash standard of comparison where the relative losses and wins are replaced by absolute losses and wins, but instead taking weights for groups of vector components into account. Thus, it can represent, for example, pairs of users that are in a favourable situation regarding resource allocation. The appealing points of this CI-relation are as follows. (1) In case a supermodular measure is used for the integration, the relation will be transitive, which suits faster search for maximal elements; (2) it can be parametrized by giving a weight to each subset of vector components (while in practice this might be relevant only for smaller subsets). The representation of the fuzzy measure by its Möbius transform appears to be a convenient way to yield a supermodular fuzzy measure; the masses just need to be all nonnegative. Thus, the relation can be conveniently applied in many practical applications to specify optimality. Slight disadvantages are with the complexity of the involved calculations, and some empirical evidence for specifying larger maximum sets than other fairness relations like proportional fairness and maxmin fairness.In case of wireless channel allocation, how CI-fairness can be used to help deciding whether implementations of more complex allocation schemes are indeed worth the effort was suggested. This method can be applied to many other problems of higher efficiency of network resource utilization. In future work, we will consider the use of advanced fuzzy integrals like balancing and fusion Choquet integral and the adjustment of related CI-fairness parameters to specific situations and what can be concluded from such parameters. We will also more intensively study the performance issues with regard to computational effort and search for maximal elements and study conditions where also greatest elements exist.



---

*Source: 725974-2014-07-17.xml*