cahier du lamsade 230 - Base Institutionnelle de Recherche de l ...

Laboratoire d'Analyse et Modélisation **de** Systèmes pour

l'Ai**de** à la Décision

CNRS UMR 7024

CAHIER DU LAMSADE

**230**

Janvier 2005, revise octobre 2005

An axiomatic approach to noncompensatory sorting methods

in MCDM II : More than two categories

Denis Bouyssou, Thierry Marchant

An axiomatic approach to noncompensatory

sorting methods in MCDM,

II: More than two categories 1

Denis Bouyssou 2

CNRS – LAMSADE

10 January 2005

Revised 25 October 2005

Thierry Marchant 3

Ghent University

1 We wish to thank Jose Figueira and Marc Pirlot for their comments on an

earlier draft of this text. Our greatest **de**bt is to Salvatore Greco, Bene**de**tto

Matarazzo and Roman S̷lowiński who alerted us on the relation between our results

on noncompensatory sorting mo**de**ls and the results in S̷lowiński et al. (2002) on

sorting mo**de**ls using a Sugeno integral. Furthermore, their **de**tailed comments

have much contributed to improve an earlier version of this text. The usual caveat

clearly applies.

2 LAMSADE, Université Paris Dauphine, Place **du** Maréchal **de** Lattre **de** Tassigny,

F-75775 Paris Ce**de**x 16, France, tel: +33 1 44 05 48 98, fax: +33 1 44 05

40 91, e-mail: bouyssou@**lamsa de**.dauphine.fr, Corresponding author.

3 Ghent University, Department of Data Analysis, H. Dunantlaan 1, B-

9000 Gent, Belgium, tel: +32 9 264 63 73, fax: +32 9 264 64 87, e-mail:

thierry.marchant@UGent.be.

Abstract

A number of recent papers have investigated the foundations of methods

allowing to sort multi-attributed alternatives between several or**de**red categories.

This paper has a similar objective. Our analysis uses a general

conjoint measurement framework, encompassing most sorting mo**de**ls used

in MDCM, that was proposed in the literature. Within this framework,

we provi**de** an axiomatic analysis of what we call noncompensatory sorting

mo**de**ls, with or without veto effects. These noncompensatory sorting mo**de**ls

contain the pessimistic version of ELECTRE TRI as a particular case.

Our analysis can be seen as an attempt to give a firm axiomatic basis to

ELECTRE TRI, while emphasizing its specific feature, i.e., the rather poor

information that this mo**de**l uses on each attribute.

Keywords: Decision with multiple attributes, Sorting mo**de**ls, Noncompensation,

Conjoint measurement, ELECTRE TRI.

Contents

1 Intro**du**ction and motivation 1

2 Definitions and notation 2

2.1 Binary relations . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.2 The setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.3 Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 A general measurement framework 4

3.1 The mo**de**l . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3.2 Interpretations of mo**de**l (D1) . . . . . . . . . . . . . . . . . . 8

4 ELECTRE TRI 13

5 The noncompensatory sorting mo**de**l 16

5.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

5.2 Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

5.3 Background on twofold partitions . . . . . . . . . . . . . . . . 21

5.4 Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.5 The noncompensatory sorting mo**de**l and the Sugeno integral . 25

5.6 In**de**pen**de**nce of axioms . . . . . . . . . . . . . . . . . . . . . 28

5.7 Uniqueness of the representation . . . . . . . . . . . . . . . . . 29

5.8 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.8.1 The case A k

i

= A ℓ

i . . . . . . . . . . . . . . . . . . . . 32

5.8.2 The case F k = F ℓ . . . . . . . . . . . . . . . . . . . . 34

6 The noncompensatory sorting mo**de**l with veto 35

6.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

6.2 Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

6.3 Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

6.4 In**de**pen**de**nce and uniqueness . . . . . . . . . . . . . . . . . . 44

6.4.1 In**de**pen**de**nce of conditions . . . . . . . . . . . . . . . . 45

6.4.2 Uniqueness . . . . . . . . . . . . . . . . . . . . . . . . 45

7 Conclusion 46

References 47

1 Intro**du**ction and motivation

In most MCDM mo**de**ls, a recommendation is built using a preference relation

comparing alternatives in terms of **de**sirability. Hence, in these mo**de**ls,

the recommendation is **de**rived on the basis of a relative evaluation mo**de**l

as given by the preference relation. This is not always appropriate since,

e.g., the best alternatives may not be **de**sirable at all. This calls for evaluation

mo**de**ls having a more absolute character. In response to this need, the

MCDM community has recently **de**veloped a number of techniques **de**signed

to sort alternatives between or**de**red categories **de**fined by norms. Recent reviews

of this trend of research can be found in Greco et al. (1999b, 2002a,b)

and Zopounidis and Doumpos (2000a, 2002). Contrary to more traditional

approaches based on binary relations for which conjoint measurement provi**de**s

a firm theoretical basis, these techniques have often been proposed on

a more or less ad hoc basis.

A recent research trend (see Greco et al., 2001b; S̷lowiński et al., 2002)

has investigated the theoretical foundations of such methods, adapting traditional

conjoint measurement techniques to **de**al with or**de**red partitions of

multi-attributed alternatives. The aim of this paper is to contribute to this

trend.

In a companion paper (Bouyssou and Marchant, 2005), we proposed an

axiomatic analysis of several sorting mo**de**ls between two categories, concentrating

on what we called noncompensatory sorting mo**de**ls. These mo**de**ls

contain the pessimistic version of ELECTRE TRI as a particular case. As

explained in Bouyssou and Marchant (2005), the choice of ELECTRE TRI

was motivated by the fact that this mo**de**l has generated numerous studies

(see Dias and Clímaco, 2000; Dias and Mousseau, 2006; Dias et al., 2002;

Lourenco and Costa, 2004; Mousseau et al., 2001a; Mousseau and S̷lowiński,

1998; Ngo The and Mousseau, 2002; Tervonen et al., 2005) and has often

been applied in practice (see, e.g., An**de**nmatten, 1995; Aron**de**l and Girardin,

2000; Georgopoulou et al., 2003; Moussa, 2001; Mousseau et al., 2000a, 2001b;

Roy, 2002).

The main aim of this paper is to extend this analysis to the case of

an arbitrary (finite) number of or**de**red categories. We refer the rea**de**r to

Bouyssou and Marchant (2005) for a **de**tailed motivation of such an analysis,

its relation to the literature and its possible implications for the practice of

MCDM. The present paper mostly concentrates on technical results. It can

be read in**de**pen**de**ntly of Bouyssou and Marchant (2005). Our results will

turn to have close connections with some of the results in Greco et al. (2001b)

and S̷lowiński et al. (2002). These connections will be analyzed in **de**tail.

This paper is organized as follows. We intro**du**ce our setting in Section 2.

1

Section 3 intro**du**ces a general conjoint measurement framework that was proposed

in the literature. Section 4 presents the main points of the ELECTRE

TRI sorting technique. Section 5 **de**als with the case of noncompensatory

sorting mo**de**ls. These mo**de**ls are roughly equivalent to the ELECTRE TRI

method when there is no discordance effect. Section 6 extends this analysis

to inclu**de** the possibility of such effects. A final section conclu**de**s.

Throughout the paper, remarks contain comments that can be skipped

on first reading without loss of continuity.

2 Definitions and notation

2.1 Binary relations

We use a standard vocabulary for binary relations. An equivalence (resp. a

weak or**de**r; a total or**de**r; a semior**de**r) is a reflexive, symmetric and transitive

(resp. complete and transitive; complete, antisymmetric and transitive;

complete, Ferrers and semi-transitive) relation.

When T is an equivalence relation on A, A/T will **de**note the set of

equivalence classes of T on A. A partition of A is a collection of nonempty

subsets of A that are pairwise disjoint and such that the union of the elements

in this collection is A. It is clear that, when T is an equivalence relation on

A, A/T is a partition of A. In**de**ed, **de**fining a partition of A is tantamount

to **de**fining an equivalence relation on A.

When T is reflexive and transitive, its symmetric part ι(T) is an equivalence.

It will prove convenient to speak of the equivalence classes of T to

mean the equivalence classes of its symmetric part ι(T). When T is a weak

or**de**r, it in**du**ces on a total or**de**r on A/ι(T). When T is a weak or**de**r and

A/ι(T) is finite, we will often speak of the first or last equivalence class of T.

Let T be a weak or**de**r on A. Following, e.g., Krantz et al. (1971, Chapter

2), we say that B is **de**nse in A for T if, for all a, b ∈ A, [a T b and

Not[b T a]] ⇒ [a T c and c T b, for some c ∈ B].

It is well-known (see Fishburn, 1970; Krantz et al., 1971) that there is a

real-valued function f on A such that, for all a, b ∈ A,

a T b ⇔ f(a) ≥ f(b),

if and only if T is a weak or**de**r and there is a finite or countably infinite set

B ⊆ A that is **de**nse in A for T.

Let T and T ′ be two weak or**de**rs on A. We say that T ′ refines T if, for

all a, b ∈ A, a T ′ b ⇒ a T b. If T ′ refines T and there is a set B that is **de**nse

in A for T ′ , B is also **de**nse in A for T.

2

2.2 The setting

Let n ≥ 2 be an integer and X = X1 × X2 × · · · × Xn be a set of objects.

Elements x, y, z, . . . of X will be interpreted as alternatives evaluated on a

set N = {1, 2, . . ., n} of attributes. For any nonempty subset J of the set of

attributes N, we **de**note by XJ (resp. X−J) the set

i∈J Xi (resp.

i/∈J Xi).

With customary abuse of notation, (xJ, y−J) will **de**note the element w ∈ X

such that wi = xi if i ∈ J and wi = yi otherwise. When J = {i} we will

simply write X−i and (xi, y−i).

2.3 Primitives

Let r ≥ 2 be an integer; we **de**fine R = {1, 2, . . ., r} and R + = {2, 3, . . ., r}.

Our primitives consist in an r-fold partition 〈C 1 , C 2 , . . .,C r 〉 of the set X

(the sets C k are therefore nonempty and pairwise disjoint; their union is the

entire set X). We often abbreviate 〈C 1 , C 2 , . . ., C r 〉 as 〈C k 〉k∈R. Note that

throughout the paper superscripts are used to distinguish between categories

and not, unless otherwise specified, to **de**note exponentiation.

We interpret the partition 〈C k 〉k∈R as the result of a sorting mo**de**l between

or**de**red categories applied to the alternatives in X. We suppose that

the or**de**ring of these categories is known beforehand and that they have been

labelled in such a way that the **de**sirability of a category increases with its

label: the worst category is C 1 and the best one is C r . Our central aim is

to study various mo**de**ls allowing to represent the information contained in

〈C k 〉k∈R.

Remark 1

The fact that we suppose the or**de**ring of categories is known beforehand is

in line with the type of data that is likely to be collected in or**de**r to test the

conditions that will be intro**du**ced below. Furthermore, this does not involve

any serious loss of generality.

In**de**ed, suppose that the or**de**ring of categories is unknown and, consequently,

that the categories have been labelled arbitrarily. In such a case, it

will be extremely unlikely that the conditions intro**du**ced below are satisfied

since they implicitly assume that categories have been labelled according to

their **de**sirability. In this case, we should reformulate our conditions saying

that it is possible to relabel the categories in such a way that these conditions

hold. This would clearly imply a much more cumbersome notation and

formulation of the conditions with almost no additional insight. Hence, we

stick to the framework in which the or**de**ring of the categories is known and

categories are labelled accordingly. •

3

For all k ∈ R + , we **de**fine C ≥k = r

j=k Cj and C

Consi**de**r a measurement mo**de**l in which, for all x ∈ X and all k ∈ R,

x ∈ C k ⇔ σk < F(u1(x1), u2(x2), . . .,un(xn)) < σk+1, (D1)

where σ1, σ2, . . .,σr+1 are real numbers such that σ1 < σ2 < . . . < σr+1, ui is

a real-valued function on Xi and F is a real-valued function on n i=1 ui(Xi)

that is increasing in all its arguments. The weakening of mo**de**l (D1) in

which F is only supposed to be non**de**acreasing in all its arguments will be

called mo**de**l (D2).

Define on each Xi the binary relation R i letting, for all xi, yi ∈ Xi,

xi R i yi ⇔ [for all a−i ∈ X−i and all k ∈ R + , (yi, a−i) ∈ C k ⇒ (xi, a−i) ∈ C ≥k ],

the rationale for the superscript R being that this relation **de**pends on the

entire partition 〈C k 〉k∈R. We use ≻ R i and ∼ R i as is usual. By construction,

R i is reflexive and transitive. When xi R i yi, an alternative (xi, a−i) must

belong to a category that is at least as good as the category containing the

alternative (yi, a−i). Hence, R i may be interpreted as an “at least as good

as” relation in**du**ced on Xi by the partition 〈C k 〉k∈R. We have:

Lemma 3

For all k ∈ R + and all x, y ∈ X,

1. [y ∈ C k and xi R i yi] ⇒ (xi, y−i) ∈ C ≥k ,

2. [xi ∼ R i yi, for all i ∈ N] ⇒ [x ∈ C k ⇔ y ∈ C k ].

Proof

Part 1 is clear from the **de**finition of R i . Part 2 follows. ✷

We say that the partition 〈C k 〉k∈R is R-linear on attribute i ∈ N (condition

linear R

i ) if, for all xi, yi ∈ Xi, all k, ℓ ∈ R + and all a−i, b−i ∈ X−i,

(xi, a−i) ∈ C k

and

(yi, b−i) ∈ C ℓ

⎫

⎬

⎭ ⇒

⎧

⎨

⎩

(yi, a−i) ∈ C ≥k

or

(xi, b−i) ∈ C ≥ℓ

(linear R

i )

We say that 〈C k 〉k∈R is R-linear if it is R-linear on all attributes i ∈ N.

R-linearity was consi**de**red by Goldstein (1991) for the case of twofold and

threefold partitions. It was in**de**pen**de**ntly rediscovered and generalized in

Greco et al. (2001b) for the analysis of r-fold partitions. The adaptation of

this condition to the study of binary relations, first suggested by Goldstein

(1991), is central in the analysis of the “nontransitive **de**composable mo**de**ls”

analyzed in Bouyssou and Pirlot (1999, 2002b, 2004a).

5

Remark 4

Observe that, in the expression of linear R

i , it is possible to replace the

premises (xi, a−i) ∈ Ck and (yi, b−i) ∈ Cℓ by (xi, a−i) ∈ C≥k and (yi, b−i) ∈

C≥ℓ . In**de**ed, suppose that (xi, a−i) ∈ C≥k and (yi, b−i) ∈ C≥ℓ while (yi, a−i) ∈

C

Hence, mo**de**l (D2) implies that we have either (yi, a−i) ∈ C≥k or (xi, b−i) ∈

C≥ℓ , as required by linear R

i .

Part 2. Suppose that ui(xi) ≤ ui(yi). Using the non**de**creasingness of F,

σk < F(u1(a1), . . .,ui−1(ai−1), ui(xi), ui+1(ai+1), . . .,un(an)) < σk+1 implies

σk < F(u1(a1), . . .,ui−1(ai−1), ui(yi), ui+1(ai+1), . . .,un(an)).

This shows that, for all a−i ∈ X−i, (xi, a−i) ∈ C k implies (yi, a−i) ∈ C ≥k , so

that yi R i xi. ✷

Omitting the cumbersome formulation of the or**de**r **de**nseness condition in

terms of the partition 〈C k 〉k∈R, this leads the following result:

Proposition 7

A partition 〈C k 〉k∈R has a representation in mo**de**l (D1) iff it is R-linear and,

for all i ∈ N, there is a finite or countably infinite set X ′ i ⊆ Xi that is **de**nse

in Xi for R i . Furthermore:

• if 〈C k 〉k∈R has a representation in mo**de**l (D1), it has a representation

in which, for all i ∈ N, ui is a numerical representation of R i ,

• mo**de**ls (D1) and (D2) are equivalent.

Proof

The necessity of R-linearity for mo**de**l (D2) results from Part 1 of Lemma 6.

Part 2 of Lemma 6 shows that, in mo**de**l (D2), the weak or**de**r in**du**ced on

Xi by ui always refines R i . Hence, there is a finite or countably infinite set

X ′ i ⊆ Xi that is **de**nse in Xi for R i .

Let us show that the conditions imply mo**de**l (D1), which will also shows

that mo**de**ls (D1) and (D2) are equivalent. Using Lemma 5, we know that

R i is a weak or**de**r. Since there is a finite or countably infinite set X ′ i ⊆ Xi

that is **de**nse in Xi for R i , there is a real-valued function ui on Xi such that,

for all xi, yi ∈ Xi,

xi R i yi ⇔ ui(xi) ≥ ui(yi). (2)

Consi**de**r, on each i ∈ N any function ui satisfying (2) and take any σ1, σ2,

. . ., σr+1 ∈ R such that σ1 < σ2 < · · · < σr+1. For all k ∈ R, consi**de**r any

increasing function φk mapping R into (σk, σk+1). Define F on n i=1 ui(Xi)

letting, for all x ∈ X and all k ∈ R,

n

F(u1(x1), u2(x2), . . ., un(xn)) = φk ui(xi) if x ∈ C k .

The well-**de**finedness of F follows from Part 2 of Lemma 3. Its increasingness

is easily shown using the **de**finition of ui and Part 1 of Lemma 3. ✷

7

i=1

A version of this result for the case of two or three category appears in

Goldstein (1991). Greco et al. (2001b) and S̷lowiński et al. (2002) state a

version of this result when X is finite or countably infinite.

The uniqueness of the representation of 〈C k 〉k∈R in mo**de**l (D1) is quite

weak. It can easily be analyzed along the lines sketched in Bouyssou and

Marchant (2005).

Mo**de**l (D1) contains as particular cases many sorting mo**de**ls that have

been proposed in the literature. Notice, in particular, that when F is taken

to be a sum, mo**de**l (D1) is nothing but the additive sorting mo**de**l used in

the UTADIS technique (Jacquet-Lagrèze, 1995; Zopounidis and Doumpos,

2000b). As shown below, it also contains the pessimistic version of ELEC-

TRE TRI as a particular case. We analyse in the next section several alternative

equivalent interpretations of this mo**de**l proposed in Greco et al.

(2001b) and S̷lowiński et al. (2002).

Remark 8

The above proof shows that mo**de**l (D1) may equivalently be written replacing

one of the two strict inequalities by a non strict one, e.g., letting, for all

x ∈ X,

x ∈ C k ⇔ σk ≤ F(u1(x1), u2(x2), . . ., un(xn)) < σk+1.

In mo**de**l (D2), it is always possible to take F to be a constant on each of

the categories C k , using functions φk mapping R to ρk with σk < ρk < σk+1.

With such a representation, F is also a numerical representation of the weak

or**de**r that is naturally in**du**ced on X by 〈C k 〉k∈R. •

3.2 Interpretations of mo**de**l (D1)

The framework offered by mo**de**l (D1) is quite flexible. Greco et al. (2001b,

Theorem 2.1, parts 3 and 4) 1 have proposed two equivalent reformulations

of mo**de**l (D1).

The first mo**de**l suggested by Greco et al. (2001b, Theorem 2.1, Part 4)

uses “at least” **de**cision rules 2 . In this mo**de**l, a complete and transitive

relation Si is supposed to be **de**fined on each Xi. A **de**cision rule d consists

in a subset N d ⊆ N of attributes and, for each i ∈ N d , an element δ d i ∈ Xi.

The syntax of the “at least” **de**cision rule d is the following:

[xi Si δ d i , ∀i ∈ Nd ] ⇒ x ∈ C ≥k .

1 Closely related results appear, without proof, in S̷lowiński et al. (2002, Theorem 2.1).

2 It is also be possible to use, equivalently, what Greco et al. (2001b) call “at most”

**de**cision rules.

8

A set of **de**cision rules D is said to represent 〈C k 〉k∈R if,

• for each x ∈ C k with k ∈ R +

– there is at least one **de**cision rule in d ∈ D that matches x (i.e.,

such that x satisfies the premises of d: [xi Si δ d i , ∀i ∈ Nd ]) and

assigns x to C ≥k ,

– there is no rule in D that matches x and assigns x to C ≥ℓ with

ℓ > k,

• x ∈ C 1 if there is no **de**cision rule in D that matches x.

Greco et al. (2001b) have argued that a mo**de**l based on **de**cision rules may be

preferable to a mo**de**l based on a functional representation, in terms of simplicity

and transparency (this fact is at the heart of the “rough set approach”

to MCDM problems as presented in Greco et al. 1999b, 2002b, 2005). Greco

et al. (2001b, Theorem 2.1, Part 4) show that the **de**cision rule mo**de**l holds

iff 〈C k 〉k∈R is R-linear.

Remark 9

Because the proof of the above fact is simple and may not be easily accessible,

we recall its main steps below.

It is clear that the “at least” **de**cision rule mo**de**l implies R-linearity.

In**de**ed suppose that (xi, a−i) ∈ C k and (yi, b−i) ∈ C ℓ . If k = 1 or ℓ = 1, there

is nothing to prove. Suppose henceforth that k > 1 and ℓ > 1. Therefore,

(xi, a−i) is matched by rule d 1 ∈ D that assigns it to C ≥k and there is no rule

matching x assigning it to a higher category. Similarly, (yi, b−i) is matched by

rule d 2 ∈ D that assigns it to C ≥ℓ and there is no rule matching y assigning

it to a higher category.

If i /∈ Nd1 or if i /∈ Nd2, it is clear that R-linearity cannot be violated.

Suppose therefore that i ∈ Nd1 and i ∈ Nd2. Since the relations Si are

complete, we have either xi Si yi or yi Si xi. Because (xi, a−i) is matched

by rule d 1 ∈ D and (yi, b−i) is matched by rule d 2 ∈ D, we know that

xi Si δ d1

i and yi Si δ d2

i . Because Si are transitive, we have either that

yi Si δ d1

i or xi Si δ d2

i . Hence, either (yi, a−i) is matched by rule d 1 ∈ D or

(xi, b−i) is matched by rule d 2 ∈ D. This implies either (yi, a−i) ∈ C ≥k or

(xi, b−i) ∈ C≥ℓ , and linear R

i holds.

Conversely, suppose that 〈Ck 〉k∈R is R-linear. Using Lemma 5, we know

that R i is complete and we take, for all i ∈ N, Si = R i . For each x ∈ Ck

**de**fine an “at least” **de**cision dx saying that

[yi Si xi, ∀i ∈ N] ⇒ y ∈ C ≥k .

9

It is clear that each x ∈ C k is matched by rule d x assigning it to C ≥k . Suppose

that there is a rule d ∈ D that matches x and that assigns it to C ≥ℓ with

ℓ > k. This would imply that there is a y ∈ C ℓ such that xi R i yi, for all

i ∈ N. Using Lemma 3, this implies x ∈ C ≥ℓ . This is contradictory since

x ∈ C k and ℓ > k. •

We refer the rea**de**r to Greco et al. (2001b) and to S̷lowiński et al. (2002) for

an in **de**pth study of the **de**cision rule mo**de**l for sorting and several of its

extensions.

The second mo**de**l (henceforth the “relational mo**de**l”) is based on binary

relations. In this mo**de**l, a complete and transitive relation Si is supposed

to be **de**fined on each Xi. A reflexive binary relation S is **de**fined on X in

such a way that it is compatible with the relations Si, i.e., such that, for all

x, y ∈ X, all i, j ∈ N, all zi ∈ Xi and all wj ∈ Xj,

[x S y, zi Si xi, yj Sj wj] ⇒ (zi, x−i) S (wj, y−j). (3)

This expresses the fact that S is compatible with the dominance relation **de**rived

from the relations Si (for a general study of such relations, see Bouyssou

and Pirlot, 2004b). The relation S on X is used to assign alternative to categories

through their comparison with particular elements of X, interpreted

as the lower limiting profiles of the categories. More precisely, the relational

mo**de**l is such that:

x ∈ C ≥k ⇔ x S π k , (4)

where π k ∈ X is interpreted as the lower limiting profile of category C k .

Greco et al. (2001b, Theorem 2.1, Part 3) have shown that the relational

mo**de**l holds iff 〈C k 〉k∈R is R-linear.

Remark 10

We present below a simple proof of the above fact.

It is easy to show that the relational mo**de**l implies R-linearity. In**de**ed

suppose that (xi, a−i) ∈ Ck and (yi, b−i) ∈ Cℓ , so that (xi, a−i) S πk and

(yi, b−i) S πℓ . Since the relations Si are complete, we have either xi Si yi or

yi Si xi. Using (3), this implies that either (yi, a−i) S πk or (xi, b−i) S πℓ .

Hence, we have either (yi, a−i) ∈ C≥k or (xi, b−i) ∈ C≥ℓ , so that linear R

i

holds.

Conversely 3 , suppose that 〈Ck 〉k∈R is R-linear. We know that the relations

R i are weak or**de**rs and we take, for all i ∈ N, Si = R i .

Define a binary relation R

on X letting, for all x, y ∈ X, x R y iff

k ℓ x ∈ C and x ∈ C with k ≥ ℓ . It is easy to see that R is a weak or**de**r on

3 Our proof differs from the one proposed in Greco et al. (2001b). When X is not finite,

the proof proposed by Greco et al. (2001b) would need to be adapted.

10

X having r equivalence classes. Take S = R. Define π k ∈ X to be any

element of C k . We clearly have x ∈ C ≥k ⇔ x S π k . It is easy to see that,

with such **de**finitions, (3) holds. •

Remark 11

In Greco et al. (2001b) and S̷lowiński et al. (2002), it is asserted, but not

proved, that the profiles π k in the relational mo**de**l may always be chosen in

such a way that, for all k ∈ R + and all i ∈ N, we have:

π k+1

i Si π k i , (5)

(profiles satisfying (5) will be called “regular profiles”). This claim is not

correct.

Consi**de**r any partition 〈Ck 〉k∈R that is R-linear. Observe that the complete

and transitive relations Si in the relational mo**de**l must always be such

that R i ⊆ Si. Suppose in**de**ed that xi Si yi and that Not[xi R i yi]. This last

relation implies that, for some k ∈ R + and some a−i ∈ X−i, (yi, a−i) ∈ Ck and (xi, a−i) ∈ C ℓ. In**de**ed,

taking any x ∈ C ℓ we would have x S π ℓ , so that x S π k , which would imply

x ∈ C ≥k . Consi**de**r now the following example.

Example 12

Suppose that n = 3, X1 = {x1, y1}, X2 = {x2, y2} and X3 = {x3, y3}. We

consi**de**r a 4-fold partition 〈C 1 , C 2 , C 3 , C 4 〉 such that C 4 = {(x1, x2, x3), (y1, x2,

x3)}, C 3 = {(x1, y2, x3)}, C 2 = {(x1, x2, y3)} and C 1 containing all remaining

alternatives. It is easy to see that we have xi ≻ R i yi, for all i ∈ N. This shows

that the partition 〈C 1 , C 2 , C 3 , C 4 〉 is R-linear.

Suppose now that the above partition has a representation in the relational

mo**de**l. We must take R i = Si, for all i ∈ N. Because π k ∈ C ≥k , we

must take π 4 to be either (x1, x2, x3) or (y1, x2, x3).

Suppose that we take π 4 = (y1, x2, x3). Since we must have π 3 ∈ C ≥3 and

π 3 = π 4 , we have either π 3 = (x1, x2, x3) or π 3 = (x1, y2, x3). In either case,

(5) is violated.

Suppose now that we take π 4 = (x1, x2, x3). We have either π 3 =

(y1, x2, x3) or π 3 = (x1, y2, x3). Suppose first that π 3 = (y1, x2, x3). We must

take either π 2 = (x1, y2, x3) or π 2 = (x1, x2, y3). In either case, (5) is violated.

Suppose now that π 3 = (x1, y2, x3). We must take either π 2 = (y1, x2, x3) or

π 2 = (x1, x2, y3). In either case, (5) is violated.

11

Therefore there is no representation of 〈C 1 , C 2 , C 3 , C 4 〉 in the relational

mo**de**l such that (5) holds. ✸

The mo**de**ls that we will study in Sections 5 and 6 will not make use of

profiles. Let us however show that how to modify the relational mo**de**l in

or**de**r to ensure that the profiles can always be **de**fined so that (5) holds.

In, what we will call the “relational mo**de**l with nested relations and

regular profiles”, a complete and transitive relation Si is supposed to be

**de**fined on each Xi. For each k ∈ R + , a reflexive binary relation S k is

**de**fined on X. It is supposed that each relation S k satisfies (3) and that the

relations S k are nested, i.e., such that:

S r ⊆ S r−1 ⊆ · · · ⊆ S 2 . (6)

For each k ∈ R + , we **de**fine a profile π k ∈ X in such a way that (5) holds.

In the relational mo**de**l with nested relations and regular profiles, we have:

x ∈ C ≥k ⇔ x S k π k . (7)

A particular case of the relational mo**de**l with nested relations and regular

profiles is obtained if we require all profiles π 2 , π 3 , . . .,π r to be i**de**ntical.

We call this mo**de**l the “relational mo**de**l with nested relations and unique

profile”.

Compared to the relational mo**de**l of Greco et al. (2001b), the relational

mo**de**l with nested relations and regular profiles proposed here uses several

nested binary relations to assign alternative to categories, instead of just one

in the relational mo**de**l, but requires that the profiles dominate each other.

We have:

Proposition 13

A partition 〈C k 〉k∈R has a representation in the relational mo**de**l with nested

relations and regular profiles iff it is R-linear. The relational mo**de**l with

nested relations and regular profiles is equivalent to the relational mo**de**l with

nested relations and unique profile.

Proof

Necessity. Suppose that (xi, a−i) ∈ C k and (yi, b−i) ∈ C ℓ , so that (xi, a−i) S k

π k and (yi, b−i) S ℓ π ℓ . Since the relations Si are complete, we have either

xi Si yi or yi Si xi. Using (3), this implies that either (yi, a−i) S k π k or

(xi, b−i) S ℓ π ℓ . Hence, we have either (yi, a−i) ∈ C ≥k or (xi, b−i) ∈ C ≥ℓ , so

that linear R

i holds.

Sufficiency. Suppose that 〈C k 〉k∈R is R-linear. We know that the relations

R i are weak or**de**rs and we take, for all i ∈ N, Si = R i .

12

For all k ∈ R + , **de**fine a relation Rk on X letting, for all x, y ∈ X,

x Rk y iff [x ∈ C≥k and y ∈ C≥k ] or [x ∈ Cℓ and y ∈ Cℓ′ with k > ℓ ≥ ℓ ′ ] .

It is easy to see that Rk is a weak or**de**r having k equivalence classes. The

first equivalence class of Rk contains all alternatives in C≥k . The other

equivalence classes consist of the categories lower than k that are or**de**red in

the natural way. We take, for all k ∈ R + , Sk = Rk , so that (6) clearly holds.

Using the **de**finition of R i , it is clear that (3) holds, for all k ∈ R+ .

We take πr = πr−1 = · · · = π2 to be equal to an arbitrary element of

Cr . With such a **de**finition, (5) trivially holds. It is easy to see that we have

x ∈ C≥k ⇔ x Sk πk .

Observe that we have built above a representation of 〈Ck 〉k∈R in the

relational mo**de**l with nested relations and unique profile. This proves the

last part of the proposition. ✷

Because the relational mo**de**l of Greco et al. (2001b) does not always lead

to using regular profiles, we consi**de**r that the relational mo**de**l with nested

relations and regular profiles is an attractive alternative to it. With this

mo**de**l in mind, we will suggest below a slight variant of ELECTRE TRI.

Nevertheless, it is clear that the relational mo**de**l of Greco et al. (2001b), the

relational mo**de**l with nested relations and regular profiles and the relational

mo**de**l with nested relations and unique profile are all equivalent. •

4 ELECTRE TRI

For the ease of future reference, we briefly recall here the main points of the

ELECTRE TRI sorting technique. We suppose below that preference and

indifference thresholds are equal and that discordance effects occur in an “all

or nothing” way. This will allow to keep things simple while preserving what

we believe to be the general spirit of the method. Furthermore, for reasons

**de**tailed in Bouyssou and Marchant (2005), we restrict our attention to the

pessimistic version of the method. We refer the rea**de**r to Mousseau et al.

(2000b), Roy and Bouyssou (1993, ch. 6) or Wei (1992) for more **de**tailed

presentations.

The aim of ELECTRE TRI is to sort alternatives evaluated on several attributes

between r or**de**red categories C 1 , C 2 , . . ., C r . This is done as follows.

For all k ∈ R + , there is a profile p k being the lower limit of category C k and

the upper limit of C k−1 . Each of these profiles p k is **de**fined by its evaluations

(p k 1, p k 2, . . .,p k n) on the attributes in N. Define Xi = Xi ∪ {p 2 i,p 3 i, . . .,p r i } and

X = n

i=1 Xi.

13

A semior**de**r Si is supposed to be **de**fined on Xi. We note Pi the asymmet-

ric

part of Si and Ti the weak or**de**r un**de**rlying Si, i.e., we have xi Ti yi iff

[zi Si xi ⇒ zi Si xi] and [yi Si zi ⇒ xi Si zi], for all zi ∈

Xi . The relation

Si is interpreted as an “at least as good” relation on Xi. Because categories

are supposed to be or**de**red, it seems obvious to require that the **de**finition of

the profiles p k is such that, for all i ∈ N,

p r i Ti p r−1

i Ti . . . Ti p 2 i .

A strict semior**de**r Vi inclu**de**d in Pi is supposed to be **de**fined on Xi. It is

interpreted as a “far better than” relation on Xi. We suppose 4 that xi Ti yi

and yi Vi zi imply xi Vi zi and that zi Ti wi and yi Vi zi imply yi Vi wi, so

that the weak or**de**r un**de**rlying the strict semior**de**r Vi is compatible with Ti.

For all k ∈ R + , let λ be a real number between 1/2 and 1. A nonnegative

weight wi is assigned to each attribute i ∈ N. It is supposed that weights

are normalized so that n i=1 wi = 1.

In ELECTRE TRI, we build a binary relation S on X letting, for all

x, y ∈ X, (notice that it would be enough to **de**fine S as a relation between

the sets X and {pr , pr−1 , . . ., p2 }),

⎡

x S y ⇔ ⎣

⎤

wi ≥ λ and [Not[yi Vi xi], for all i ∈ N] ⎦ , (8)

i∈S(x,y)

where S(x, y) = {i ∈ N : xi Si yi}. Hence, we have x S y when x is

judged “at least as good as” y on a qualified weighted majority of attributes

(concordance condition) and there is no attribute on which y is judged “far

better” than x (non-discordance condition).

The sorting of an alternative x ∈ X is based on the comparison of x with

the profiles p k using the relation S. In the pessimistic version of ELECTRE

TRI, we have, for all x ∈ X and all k ∈ R + ,

x ∈ C ≥k ⇔ x S p k .

Remark 14

In the original presentation of the method (see Roy and Bouyssou, 1993,

p. 390), the assignment of an alternative to one of the categories is presented

4 This requirement is obviously satisfied when both Si and Vi are **de**fined using a realvalued

function gi on Xi together with indifference and veto thresholds, as in the usual

presentation.

14

slightly differently: for k = r, r − 1, . . .2, it is tested whether x S p k and x

is assigned to the highest category C k such that this test is positive or to

C 1 if the test is never positive. Our presentation is clearly equivalent to the

original one. •

Remark 15

ELECTRE TRI uses profiles that dominate each other in terms of the relations

Si. Compared to the relational mo**de**ls suggested earlier, it adds

the additional flexibility to choose the profiles outsi**de** the set X. We will

nevertheless show later that, neglecting additivity issues, if a partition can

be obtained with ELECTRE TRI, it is always possible to obtain it using

ELECTRE TRI profiles that belong to X.

For the moment, let us observe that the partition analyzed in Example 12

cannot be obtained with ELECTRE TRI.

In**de**ed, because (x1, x2, x3) ∈ C ≥4 , (x1, y2, x3) /∈ C ≥4 and (x1, x2, y3) /∈

C ≥4 , we know that being at least as good as a profile on attributes {1, 3}

or on attributes {1, 2} is not sufficient to establish outranking. Similarly

because (x1, y2, x3) ∈ C ≥3 and (x1, y2, y3) /∈ C ≥3 , we know that being at

least as good as a profile on attributes {2, 3} is not sufficient to establish

outranking. Hence, to establish outranking it is necessary to be at least as

good as the profile on all attributes.

Hence, since (y1, x2, x3) ∈ C 4 , we must have y1 S1 p 4 1 . Because (x1, x2, y3) ∈

C ≥2 and (y1, x2, y3) /∈ C ≥2 we must have Not[y1 S1 p 2 1 ]. But y1 S1 p 4 1 and

p 4 1 T1 p 2 1 implies y1 S1 p 2 1, a contradiction.

A seemingly very minor modification of ELECTRE TRI would allow it

to be able to represent the partition analyzed in Example 12. Instead of

consi**de**ring a single binary relation S it suffices, as in the relational mo**de**l

with nested relations and regular profiles proposed above, to consi**de**r several

nested binary relations. This can easily be done as follows.

For all k ∈ R + , let λ k be a real number between 1/2 and 1 such that:

λ r ≥ λ r−1 ≥ · · · ≥ λ 2 .

For all k ∈ R + , build a binary relation Sk on X letting, for all x, y ∈ X,

x S k ⎡

y ⇔ ⎣

wi ≥ λ k ⎤

and [Not[yi Vi xi], for all i ∈ N] ⎦ . (9)

i∈S(x,y)

Observe that, by construction, we have:

S r ⊆ S r−1 ⊆ · · · ⊆ S 2 .

15

The sorting of an alternative x ∈ X is based on the comparison of x with the

profiles p k using the relations S k . In the pessimistic version of ELECTRE

TRI, we have, for all x ∈ X and all k ∈ R + ,

x ∈ C ≥k ⇔ x S k p k .

It is clear that this variant remains close to the original spirit of the authors

of ELECTRE TRI. We will call it ELECTRE TRI with nested relations.

Besi**de**s remaining close to the original method, this variant has larger **de**scriptive

ability than the priginal method. In**de**ed, it can represent the partition

analyzed in Example 12. A routine check shows that this example can

be obtained using ELECTRE TRI with nested relations using the following

parameters:

x1 P1 y1 x2 P2 y2 x3 P3 y3,

w1 = 0.25 w2 = 0.35 w3 = 0.4,

p 4 = p 3 = p 2 = (x1, x2, x3),

λ4 = 0, 7 λ3 = 0.6 λ2 = 0.55,

V1 = V2 = V3 = ∅. •

5 The noncompensatory sorting mo**de**l

This section studies a particular case of the sorting mo**de**l (D1) that will turn

to have close links with (the pessimistic version of) ELECTRE TRI in the

absence of veto. As pointed to us by Salvatore Greco, Bene**de**tto Matarazzo

and Roman S̷lowiński, this mo**de**l has intimate connections with the mo**de**l

based on the Sugeno integral studied in Greco et al. (2001b) and S̷lowiński

et al. (2002). They will be studied in Section 5.5.

5.1 Definitions

We say that 〈C k 〉k∈R has a representation in the noncompensatory sorting

mo**de**l if:

(i) for all i ∈ N there are sets A r

i

⊆ A r−1

i

k

2

⊆ · · · ⊆ Ai ⊆ · · · ⊆ Ai ⊆ Xi,

(ii) there are subsets F r , F r−1 , ..., F k , ..., F 2 of 2 N that are such that,

for all k ∈ R + and all I, J ∈ 2 N ,

[I ∈ F k and I ⊆ J] ⇒ J ∈ F k , (10)

16

such that:

and are nested, i.e., such that,

F r ⊆ F r−1 ⊆ · · · ⊆ F 2 , (11)

x ∈ C ≥k ⇔ {i ∈ N : xi ∈ A k

i } ∈ F k , (12)

for all x ∈ X and all k ∈ R + . In this case, we say that 〈F k , 〈A k

i 〉i∈N〉 is a

representation of 〈Ck 〉k∈R in the noncompensatory sorting mo**de**l. We note

A k (x) instead of {i ∈ N : xi ∈ A k

i } when there is no ambiguity on the

un**de**rlying sets A k

k

i . We **de**fine, in Section 5, Ui = Xi \ A k

i .

The interpretation of the noncompensatory sorting mo**de**l is simple. For

all k ∈ R + , we isolate within the set Xi a subset A k

i that we interpret as

containing the elements of Xi that are judged “satisfactory at the level k”. In

or**de**r for an alternative x ∈ X to belong at least to Ck , it is necessary that the

evaluations of x are judged satisfactory at the level k on a subset of attributes

that is “sufficiently important at the level k”, as indicated by the set F k . The

fact that F k satisfies (10) implies that replacing an unsatisfactory evaluation

at the level k by a satisfactory one cannot turn an alternative in Ck into an

alternative in C

5.2 Axioms

Let us first observe that a partition 〈C k 〉k∈R having a representation in the

noncompensatory sorting mo**de**l must be R-linear.

Lemma 16

If a partition 〈Ck 〉k∈R has a representation in the noncompensatory sorting

mo**de**l then it is R-linear.

Proof

Suppose that linear R

i is violated so that, for some k, ℓ ∈ R + , some xi, yi ∈ Xi,

and some a−i, b−i ∈ X−i, (xi, a−i) ∈ Ck , (yi, b−i) ∈ Cℓ , (yi, a−i) ∈ C

for all k, ℓ ∈ R + with ℓ ≤ k, all xi, yi, zi ∈ Xi, and all a−i, b−i ∈ X−i. We

say that 〈Ck 〉k∈R is R-2-gra**de**d if it is R-2-gra**de**d on all i ∈ N. Condi-

tion 2-gra**de**d R

i generalizes condition 2-gra**de**d i intro**du**ced in Bouyssou and

Marchant (2005). A similar i**de**a has been used, for mo**de**ls using binary

relations, in Bouyssou and Pirlot (2002a, 2005) and Greco et al. (2001a).

It is easy to see that the violation of condition 2-gra**de**d R

i will imply

that some relation k i

has more than 2 distinct equivalence classes. In**de**ed,

suppose, in contradiction with condition 2-gra**de**d R

i , that (xi, a−i) ∈ C ≥k and

(yi, b−i) ∈ C ≥k , while (xi, b−i) ∈ C

Proof

It is clear that (13) implies 2-gra**de**d R

i . Taking zi = yi shows that it also

implies linear R

i

. Let us show that the converse implication also holds.

Suppose that (xi, a−i) ∈ C ≥k and (yi, b−i) ∈ C ≥ℓ . If (yi, a−i) ∈ C ≥k ,

2-gra**de**d R

i implies the **de**sired conclusion. If (yi, a−i) /∈ C ≥k , (xi, a−i) ∈ C ≥k

and (yi, b−i) ∈ C ≥ℓ imply, using linear R

i , (xi, b−i) ∈ C ≥ℓ . ✷

•

The following lemma makes clear the consequences of conditions linear R

i and

2-gra**de**d R

i using the relations k i .

Lemma 20

Conditions linear R

i

and 2-gra**de**dR

i

hold iff the following three conditions hold:

(a) k i is a weak or**de**r having at most two distinct equivalence classes,

(b) [xi ≻ k i yi] ⇒ [xi ℓ i yi, for all ℓ ∈ R + ],

(c) [xi ∼ k i zi and xi ≻ k i yi] ⇒ [xi ∼ ℓ i zi, for all ℓ ∈ R + such that ℓ < k].

for all k ∈ R + and all xi, yi, zi ∈ Xi.

Proof

Part [⇐]. Suppose first that linear R

i is violated so that, for some k, ℓ ∈ R + ,

some xi, yi ∈ Xi and some a−i, b−i ∈ X−i, (xi, a−i) ∈ Ck , (yi, b−i) ∈ Cℓ ,

(yi, a−i) ∈ C

(yi, b−i) ∈ C k , (xi, b−i) ∈ C ≥k and (xi, a−i) ∈ C k imply, either (yi, a−i) ∈ C ≥k

or (zi, b−i) ∈ C ≥k , a contradiction. Hence, (a) holds.

Suppose now that, for some k, ℓ ∈ R + such that ℓ < k and some xi, yi, zi ∈

Xi, xi ∼ k i zi, xi ≻ k i yi and Not[xi ∼ ℓ i zi]. Suppose that xi ≻ ℓ i zi, the proof

for the other case being similar. By **de**finition, xi ∼ k i zi and xi ≻ k i yi imply

that (xi, a−i) ∈ C k , (zi, a−i) ∈ C k and (yi, a−i) ∈ C

for all i ∈ N, all xi, yi, zi ∈ Xi and all a−i, b−i ∈ X−i. Furthermore:

1. Conditions (16) and (17) are in**de**pen**de**nt.

2. The representation 〈G , 〈Bi〉i∈N〉 of 〈A , U 〉 is unique iff all attributes

are influent for 〈A , U 〉.

3. Suppose that i ∈ N is influent for 〈A , U 〉. In all representations

〈G , 〈Bi〉〉 of 〈A , U 〉, Bi must coinci**de** with the first equivalence class

of i.

4. If j ∈ N is **de**generate for 〈A , U 〉, it is always possible to take Bj = ∅.

With such a choice, we may always choose G in such a way that I ∈ G

whenever there is some x ∈ A such that {i ∈ N : xi ∈ Bi} ⊆ I.

5. Furthermore, keeping the set G as above, on each **de**generate attribute

j ∈ N we may modify Bj taking it to be an arbitrary subset of Xj. If

this subset is taken to be strict, after this modification, we still have that

I ∈ G whenever there is some x ∈ A such that {i ∈ N : xi ∈ Bi} ⊆ I.

Taking A = C ≥k shows that, if a partition 〈C k 〉k∈R is R-linear, then all

twofold partitions 〈C ≥k , C

subsets B k i ⊆ Xi and a subset G k ⊆ 2 N satisfying (14) such that, for all

x ∈ X,

x ∈ C ≥k ⇔ {i ∈ N : xi ∈ B k i } ∈ G k .

We **de**fine below F k and A k

i on the basis of G k and B k i

cases.

distinguishing two

Case k = r

Let 〈G r , 〈Br i 〉i∈N〉 be the representation of 〈C≥r , C

(zi, b−i) ∈ C ≥k−1 imply (xi, b−i) ∈ C ≥k−1 or (yi, a−i) ∈ C ≥ℓ , a contradiction.

Proof that F k ⊆ F k−1

Let us now prove that F k ⊆ F k−1 . By construction, we know that, for

all k ∈ {3, 4, . . ., r}, I ∈ F k whenever there is some x ∈ C ≥k such that

A k (x) = {i ∈ N : xi ∈ A k

i } ⊆ I. Let I ∈ F k and let x ∈ X be such that

x ∈ C ≥k and A k (x) ⊆ I. Starting with such an alternative x ∈ X, let us

build an alternative x ′ ∈ X as follows. For all i ∈ N such that xi ∈ A k

i , let

x ′ i = xi. Because A k

i

For all i ∈ N such that xi /∈ A k

i

⊆ A k−1

i , we know that on these attributes x ′ i

, we consi**de**r two cases:

∈ A k−1

i .

1. if i is influent for 〈C ≥k−1 , C

{1, 2},{1, 3},{2, 3},{1, 2, 3}}. As explained in the proof of Theorem 22, we

take A 2

1 = B2 1

, A 2

2 = B2 2

, A 2

3

= A 3

3 and F 2 = G 2 .

It can easily be checked that 〈F k , 〈A k

i 〉i∈N〉 is a representation of 〈C k 〉k∈R

in the noncompensatory sorting mo**de**l. This is **de**tailed in Table 1. ✸

5.5 The noncompensatory sorting mo**de**l and

the Sugeno integral

Salvatore Greco, Bene**de**tto Matarazzo and Roman S̷lowiński have brought

to our attention the fact that Theorem 22 has very close connections with

Theorem 2.4 given, without proof, in S̷lowiński et al. (2002) (our results

have been obtained in**de**pen**de**ntly). The purpose of S̷lowiński et al. (2002,

Theorem 2.4) is to characterize partitions that can be represented using a

Sugeno integral.

Let 〈C k 〉k∈R be a partition of X. We say that 〈C k 〉k∈R can be represented

using a Sugeno integral, if there are:

• a non-negative real valued function fi on Xi, for all i ∈ N,

• r − 1 real numbers such that 0 < ρ2 < ρ3 < . . . < ρr

• a real valued function 5 µ on 2 N that is non**de**creasing w.r.t. inclusion

(i.e., such that A ⊆ B implies µ(A) ≤ µ(B)) and such that µ(∅) = 0,

such that, for all x ∈ X,

x ∈ C ≥k ⇔ S〈µ,fi〉(x) =

I⊆N

[fi(xi)]; µ(I) > ρk, (Su)

where S〈µ,fi〉(x) is called the (discrete) Sugeno integral of the vector (f1(x1),

f2(x2), . . ., fn(xn)) w.r.t. the capacity µ. We refer the rea**de**r to Marichal

(2000) for a **de**tailed study of various equivalent forms of S〈µ,fi〉(x), including

the more common forms that involve a reor**de**ring of the vector (f1(x1), f2(x2),

. . ., fn(xn)).

As already observed in Bouyssou and Marchant (2005) for the particular

case of two categories, a partition can be represented in the noncompensatory

sorting mo**de**l iff it can be represented using a Sugeno integral.

Observe first that any partition that can be represented in the noncompensatory

sorting mo**de**l has a representation using a Sugeno integral. Take

5 The function µ is usually called a capacity. It is often supposed that the capacity is

normalized so that µ(N) = 1. This is not necessary for our purposes.

25

i∈I

x Category B 3 (x) B 2 (x) A 2 (x)

(9, 10, 10) C 3 {2, 3} {2} {2, 3}

(9, 10, 11) C 3 {2, 3} {2} {2, 3}

(9, 11, 10) C 3 {2, 3} {2} {2, 3}

(9, 11, 11) C 3 {2, 3} {2} {2, 3}

(10, 9, 10) C 3 {1, 3} {1} {2, 3}

(10, 9, 11) C 3 {1, 3} {1} {2, 3}

(10, 10, 9) C 3 {1, 2} {1, 2} {1, 2}

(10, 10, 10) C 3 {1, 2, 3} {1, 2} {1, 2, 3}

(10, 10, 11) C 3 {1, 2, 3} {1, 2} {1, 2, 3}

(10, 11, 9) C 3 {1, 2} {1, 2} {1, 2}

(10, 11, 10) C 3 {1, 2, 3} {1, 2} {1, 2, 3}

(10, 11, 11) C 3 {1, 2, 3} {1, 2} {1, 2, 3}

(11, 9, 10) C 3 {1, 3} {1} {1, 3}

(11, 9, 11) C 3 {1, 3} {1} {1, 3}

(11, 10, 9) C 3 {1, 2} {1, 2} {1, 2}

(11, 10, 10) C 3 {1, 2, 3} {1, 2} {1, 2, 3}

(11, 10, 11) C 3 {1, 2, 3} {1, 2} {1, 2, 3}

(11, 11, 9) C 3 {1, 2} {1, 2} {1, 2}

(11, 11, 10) C 3 {1, 2, 3} {1, 2} {1, 2, 3}

(11, 11, 11) C 3 {1, 2, 3} {1, 2} {1, 2, 3}

.......... ......... ....... ..... .......

(9, 10, 9) C 2 {2} {2} {2}

(9, 11, 9) C 2 {2} {2} {2}

(10, 9, 9) C 2 {1} {1} {1}

(11, 9, 9) C 2 {1} {1} {1}

.......... ......... ....... ..... .......

(9, 9, 9) C 1 ∅ ∅ ∅

(9, 9, 10) C 1 {3} ∅ {3}

(9, 9, 11) C 1 {3} ∅ {3}

Table 1: Details of Example 23

B 3 (x) = {i ∈ N : xi ∈ B3 i }, B2 (x) = {i ∈ N : xi ∈ B2 i },

B3 1 = B3 2 = B3 3 3 3

2 = {10, 11}, A1 = A2 = A3 = {10, 11},

F 3 = G 3 = {{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}},

B2 1 = B2 2 = {10, 11}, B2 3 = ∅, A 2

1 = A 2

2 = {10, 11}, A 2

3 = {10, 11},

F 2 = G 2 = {{1}, {2}, {1, 2},{1, 3},{2, 3},{1, 2, 3}}.

26

any numbers λk and ρk such that: 0 < λ1 < ρ2 < λ2 < ρ3 < . . . λr−1 < ρr <

λr. Let 〈F k , 〈A k

i 〉i∈N〉 be a representation of 〈Ck 〉k∈R in the noncompensatory

sorting mo**de**l.

For all i ∈ N, **de**fine fi letting, for all xi ∈ Xi,

⎧

fi(xi) = λr if xi ∈ A

⎪⎨

r

i ,

fi(xi) = λr−1 if xi ∈ A r−1

i \ A r

i ,

fi(xi) = λr−2 if xi ∈ A r−2

i \ A r−1

i ,

.

fi(xi) = λ2 if xi ∈ A

⎪⎩

2

i

fi(xi) = λ1 otherwise,

and µ on 2N letting, for all A ∈ 2N ,

⎧

µ(A) = λr if A ∈ F r ,

\ A 3

i ,

µ(A) = λr−1 if A ∈ F

⎪⎨

r−1 \ F r ,

µ(A) = λr−2 if A ∈ F r−2 \ F r−1 ,

.

µ(A) = λ2 if A ∈ F

⎪⎩

2 \ F 3 ,

µ(A) = λ1 otherwise.

With such **de**finitions, for all x ∈ X, the value S〈µ,fi〉(x) belongs to {λ1, λ2,

. . ., λr}. We have x ∈ C ≥k iff {i ∈ N : xi ∈ A k

i } ∈ F k , which implies

S〈µ,fi〉(x) ≥ λk > ρk. Similarly, it is easy to see that if x /∈ C ≥k , we have

S〈µ,fi〉(x) ≤ λk−1, so that S〈µ,fi〉(x) < ρk. Hence, any partition that has a

representation in the noncompensatory sorting mo**de**l can be represented in

mo**de**l (Su).

Consi**de**r now a partition 〈C k 〉k∈R of X that can be represented in the

mo**de**l (Su). Let us show that such a partition satisfies (13). Suppose that

(xi, a−i) ∈ C ≥k , (yi, b−i) ∈ C ≥ℓ and (xi, b−i) /∈ C ≥ℓ . Using mo**de**l (Su),

(yi, b−i) ∈ C ≥ℓ and (xi, b−i) /∈ C ≥ℓ imply fi(xi) ≤ λℓ. Since (xi, a−i) ∈ C ≥k ,

we must have, for some I ∈ 2 N such that i /∈ I, µ(I) > ρk and

j∈I fj(aj) >

ρk. This implies (zi, a−i) ∈ C ≥k , for all zi ∈ Xi.

Combining the above observations and Lemma 19 with Theorem 22, we

have proved:

Proposition 24

A partition 〈C k 〉k∈R of a set X has a representation in the noncompensatory

sorting mo**de**l iff it has a representation in the Sugeno integral mo**de**l (Su).

S̷lowiński et al. (2002, Theorem 2.4) state, without proof, that a partition

〈C k 〉k∈R can be represented in the Sugeno integral mo**de**l (Su) iff it satis-

27

fies condition (13). The above proposition, connects S̷lowiński et al. (2002,

Theorem 2.4) and our Theorem 22, showing, in fact, that they are characterizations

of the same un**de**rlying mo**de**l.

5.6 In**de**pen**de**nce of axioms

Let us show that none of the two conditions used in Theorem 22 can be

dispensed with. Consi**de**r first the following condition:

⎫

⎧

⎪⎬ ⎨ (xi, b−i) ∈ C

⇒

⎩

⎪⎭

≥k

or

(zi, a−i) ∈ C≥k (18)

(xi, a−i) ∈ C ≥k

and

(yi, a−i) ∈ C ≥k

and

(yi, b−i) ∈ C ≥k

for all xi, yi, zi ∈ Xi, all a−i, b−i ∈ X−i and all k ∈ R + . Condition (18) is

nothing but condition 2-gra**de**d R

i restricted to the case ℓ = k. The following

example shows that the conjunction of R-linearity and condition (18), for all

i ∈ N, is not sufficient to precipitate the noncompensatory sorting mo**de**l.

Example 25

Let n = 3, X = {x1, y1, z1} × {x2, y2} × {x3, y3} and r = 3. Let C 3 =

{(x1, x2, x3), (y1, x2, x3)}, C 2 = {(x1, x2, y3), (x1, y2, x3), (y1, x2, y3), (y1, y2, x3),

(y1, y2, y3), (z1, x2, x3), (z1, x2, y3), (z1, y2, x3)} and C 1 = {(z1, y2, y3), (x1, y2, y3)}.

We have y1 ≻ R 1 x1 ≻ R 1 z1, x2 ≻ R 2 y2 and x3 ≻ R 3 y3, which shows that

〈C k 〉k∈R is R-linear.

The twofold partition 〈C ≥3 , C

(z1, x2, x3) ∈ C

Remark 27

Suppose that, for some ℓ ∈ R + , there is an attribute j ∈ N that is **de**generate

for 〈C ≥ℓ , C ℓ such that j ∈ N is influent for 〈C ≥k , C

{(x1, y2, y3), (y1, x2, y3), (y1, y2, x3), (y1, y2, y3)}.

All attributes are influent for the twofold partition 〈C≥4 , C

the above construction is exactly equivalent to the concordance part of ELEC-

TRE TRI with nested relations.

We leave to the rea**de**r the, easy, task of extending this construction to

cover the case in which some of the sets A k

i

are empty or when A k

i

= A k+1

i .

Neglecting additivity issues, this shows that a partition that can be obtained

with ELECTRE TRI (with Vi = ∅, for all i ∈ N) using profiles that

are outsi**de** the set X can always be obtained with ELECTRE TRI (still with

Vi = ∅, for all i ∈ N) using profiles that belong to X. •

5.8 Extensions

This section is **de**voted to the study of two particular cases of the noncompensatory

sorting mo**de**l. It may be skipped without loss of continuity.

5.8.1 The case A k

i = A ℓ

i

We analyze here what must be ad**de**d to the conditions in Theorem 22, in

or**de**r to ensure that 〈Ck 〉k∈R has a representation in the noncompensatory

sorting mo**de**l in which A k ℓ

i = Ai , for all k, ℓ ∈ R+ . With such a mo**de**l,

going from C ≥k to C ≥k−1 only involves a change from F k to F k−1 , i.e., a

change in the “strength” of the coalition of attributes nee**de**d to ensure that

an alternative is judged satisfactory.

Suppose that 〈C k 〉k∈R has a representation in the noncompensatory sort-

ing mo**de**l such that A k

i

= A ℓ

i , for all k, ℓ ∈ R+ . Let k ∈ R + and suppose

that (xi, a−i) ∈ C ≥k and (yi, a−i) ∈ C

Proof

Suppose that, for some k, ℓ ∈ R with ℓ < k and some xi, yi, zi ∈ Xi, we have

Not[yi k i xi] and Not[zi ℓ i yi]. By **de**finition this is equivalent to saying

that, for some a−i, b−i ∈ X−i, (xi, a−i) ∈ C ≥k , (yi, a−i) /∈ C ≥k , (yi, b−i) ∈ C ≥ℓ

and (zi, b−i) /∈ C ≥ℓ . This is equivalent to saying that Eq i is violated. ✷

We have:

Proposition 31

An r-fold partition 〈C k 〉k∈R of X has a representation in the noncompen-

satory sorting mo**de**l with A k

i = A ℓ

i , for all k, ℓ ∈ R + iff it is R-linear,

R-2-gra**de**d and satisfies Eq.

Proof

The necessity of R-linearity and R-2-gra**de**dness follows from Theorem 22.

The necessity of Eq was shown above.

Sufficiency. Since 〈C k 〉k∈R is R-linear and R-2-gra**de**d, it has a repre-

sentation in the noncompensatory sorting mo**de**l. Let 〈F k , 〈A k

i 〉i∈N〉 be the

representation built in Theorem 22. Suppose that, for some ℓ ∈ R + with

ℓ < r, we have xi ∈ A ℓ

i . If attribute i ∈ N is **de**generate for 〈C≥ℓ , C ℓ such that i ∈ N is influent for 〈C≥k∗, C

z1 and x2 ≻R 2 y2, so that this partition is R-linear. Condition 2-gra**de**d R

2 is

trivially satisfied. Condition 2-gra**de**d R

1 is violated because (x1, x2) ∈ C3 ,

(y1, x2) ∈ C3 and (y1, y2) ∈ C3 but neither (x1, y2) ∈ C≥3 not (z1, x2) ∈ C≥3 .

We have y1 ≻3 1 x1 ≻3 1 z1 and y1 ≻2 1 [x1 ∼2 1 z1]. Similarly, we have x2 ≻3 2 y2

and x2 ≻2 2 y2. Using Lemma 30, it is easy to see that condition Eq holds. ✸

Example 33

Let n = 3 and X = {x1, y1} × {x2, y2} × {x3, y3} and r = 3. Let C 3 =

{(x1, x2, x3), (y1, x2, x3)}, C 2 = {(x1, x2, y3), (y1, y2, x3)} and C 1 = {(x1, y2, y3),

(y1, y2, y3), (x1, y2, x3), (y1, x2, y3)}. Since all sets Xi have two only elements,

this partition is trivially R-2-gra**de**d. Condition linear2 and linear3 hold with

x2 ≻ R 2 y2 and x3 ≻ R 3 y3. Condition linear1 is violated since (x1, x2, y3) ∈ C 2 ,

(y1, y2, x3) ∈ C 2 but neither (y1, x2, y3) ∈ C ≥2 nor (x1, y2, x3) ∈ C ≥2 .

We have x1 ∼ 3 1 y1, Not[x1 ∼ 2 1 y1] and Not[y1 ∼ 2 1 x1]. We also have xi ≻ 3 i yi

and xi ≻ 2 i yi, for i ∈ {2, 3}. Using Lemma 30, it is easy to see that condition

Eq holds. ✸

5.8.2 The case F k = F ℓ

We analyze here what must be ad**de**d to the conditions in Theorem 22 in

or**de**r to ensure that 〈C k 〉k∈R has a representation in the noncompensatory

sorting mo**de**l in which F k = F ℓ , for all k, ℓ ∈ R + . In this case, going from

C ≥k to C ≥k−1 only involves a change in the **de**finition of the sets A k

i . This

restriction brings the noncompensatory sorting mo**de**l closer to the original

version of ELECTRE TRI. This case is more difficult to analyze than the

preceding one since, in our proofs, the construction of the sets F k is left

implicit. This is a clear drawback of our proof technique.

Take any x ∈ C k and let J(x) be the subset of attributes i ∈ N such

that:

(zi, x−i) ∈ C

that xi /∈ A k

i . On all attributes such that xi ∈ A k

i and xi /∈ A k+1

i , we have

wi ∈ A k+1

i . Therefore, we have A k+1 (w) = A k (x). Because x ∈ C k , we know

that A k (x) ⊆ I implies I ∈ F k . If it is required that w ∈ C ≥k+1 , all such

subsets I will also belong to F k+1 .

We have exhibited a necessary condition for the existence of a representation

in which F k = F k+1 (for all x ∈ C k , the alternative w ∈ X as

built above must belong to C ≥k+1 ). When ad**de**d to R-linearity and R-2gra**de**dness,

it is not difficult to show that this condition is also sufficient to

ensure the existence of such a representation. Since this new condition is quite

cumbersome and the proof is not very instructive, we do not formalize this

point further here. We are not presently aware of a more satisfactory characterization

of this particular case of the noncompensatory sorting mo**de**l, in

spite of its intuitive appeal.

6 The noncompensatory sorting mo**de**l with

veto

This section extends the results of the preceding section to allow for possible

veto effects, as the ELECTRE TRI method.

6.1 Definitions

We consi**de**r a mo**de**l generalizing the noncompensatory sorting mo**de**l in

or**de**r to allow for possible veto effects. We say that 〈C k 〉k∈R has a representation

in the noncompensatory sorting mo**de**l with veto if:

• for all i ∈ N and all k ∈ R + there are disjoint sets A k

i

that:

(i) for all i ∈ N, A r

i

⊆ A r−1

i

(ii) for all i ∈ N, V r

i ⊇ V r−1

i

2 ⊆ · · · ⊆ Ai ,

⊇ · · · ⊇ V 2

i ,

, V k

i ⊆ Xi such

(iii) for all k, ℓ ∈ R + such that k < ℓ, if xi ∈ A k

i , yi ∈ U k

i and xi ∈ V ℓ

i

then yi ∈ V ℓ

i

k

, where, in Section 6, Ui = Xi \ [A k

i

∪ V k

i ],

• there are subsets F r , F r−1 , ..., F 2 of 2 N that are such that, for all

k ∈ R + and all I, J ∈ 2 N ,

and are nested, i.e., such that,

[I ∈ F k and I ⊆ J] ⇒ J ∈ F k , (22)

F r ⊆ F r−1 ⊆ · · · ⊆ F 2 , (23)

35

such that:

x ∈ C ≥k ⇔ {i ∈ N : xi ∈ A k

i } ∈ F k and {i ∈ N : xi ∈ V k

i } = ∅ , (24)

for all x ∈ X and all k ∈ R + . As before we note A k (x) and V k (x) instead

of {i ∈ N : xi ∈ A k

i } and {i ∈ N : xi ∈ V k

i } when there is no ambiguity on

the un**de**rlying sets A k

i

and V k

i .

The interpretation of the noncompensatory sorting mo**de**l with veto is

similar to that of the noncompensatory sorting mo**de**l, the latter being a

particular case of the former. The only difference is that, for each k ∈ R + ,

there is a set V k

i that is repulsive for C ≥k . Since the categories are or**de**red,

the requirement that a level that is repulsive for a given category should

be repulsive for all higher categories is not surprising. This explains the

intro**du**ction of the additional constraints V k k−1

i ⊇ Vi . Condition (iii) is

a consistency requirement on A k

i

, U k

i

and V ℓ

i that can be interpreted as

follows. If xi ∈ A k

i , yi ∈ U k

i , we have an indication that xi is superior to yi.

Supposing now that, for some ℓ > k, xi ∈ V ℓ

i and yi /∈ V ℓ

i

, would give the

inconsistent indication that yi is superior to xi.

The pessimistic version of ELECTRE TRI with nested relations (and,

hence, the pessimistic version of ELECTRE TRI) is a particular case of the

noncompensatory sorting mo**de**l with veto. In**de**ed, remember from Section 4

that in the pessimistic version of ELECTRE TRI with nested relations we

have, for all x ∈ X, and all k ∈ R + ,

x ∈ C ≥k ⎡

⇔ ⎣

wi ≥ λ k and [Not[p k i Vi

⎤

xi], for all i ∈ N] ⎦.

i∈S(x,p k )

Define A k

i = {i ∈ N : xi Si p k }, V k

i = {i ∈ N : pk Vi xi} and let I ∈ F k

whenever

i∈I wi ≥ λ k .

By construction, xi ∈ A k

i implies xi Si p k i . Since p k i ) Ti p k−1

i , we obtain

xi Si p k−1

i , so that xi ∈ A k−1

i . The proof that V k−1

i

The sets A k

i

⊆ V k

i is similar.

and V k

i are disjoint. Suppose now that k < ℓ, xi ∈ A k

i ,

yi ∈ U k

i and xi ∈ V ℓ

i . This implies xi Si p k i , p k i Pi yi and p ℓ i Vi xi. The

first two equations imply xi Ti yi. The third equation therefore implies that

pk i Ti yi, so that yi ∈ V ℓ

i . Because λk ≥ λk−1 , we have F k ⊆ F k−1 . Hence,

〈F k , 〈A k

i , V k

i 〉i∈N〉 is a representation of 〈Ck 〉k∈R in the noncompensatory

sorting mo**de**l with veto.

Remark 34

In the noncompensatory sorting mo**de**l with veto, as soon as xi ∈ V k

i , it is

impossible to have (xi, a−i) ∈ C≥k , for all a−i ∈ X−i. This i**de**a of “discordance”

is simple but therefore rather radical: levels that, on their own,

36

are not repulsive cannot “interact” so that their combination would be repulsive.

Extensions of the noncompensatory sorting mo**de**l with veto that would

tolerate some of these interactions could well lead to interesting mo**de**ls on

the theoretical si**de**, while remaining sufficiently simple so as to be useful in

practice. Such mo**de**ls could be the subject of future research. •

6.2 Axioms

The noncompensatory sorting mo**de**l with veto shares with the noncompensatory

sorting mo**de**l the fact that it implies R-linearity.

Lemma 35

If a partition 〈C k 〉k∈R has a representation in the noncompensatory sorting

mo**de**l with veto then it is R-linear.

Proof

Suppose that linear R

i is violated so that, for some k, ℓ ∈ R + , some xi, yi ∈ Xi,

and some a−i, b−i ∈ X−i, (xi, a−i) ∈ Ck , (yi, b−i) ∈ Cℓ , (yi, a−i) ∈ C

and Marchant (2005), this condition being in turn, inspired by Greco et al.

(2001a) who study veto effects in the context of binary relations.

Note that condition 3v-gra**de**d R

i is the weakening of 2-gra**de**d R

i obtained

by adding to it the premise (zi, c−i) ∈ C≥k . The intuition behind this weakening

is that the noncompensatory sorting mo**de**l with veto requires condition

2-gra**de**d R

i to hold for elements that are not repulsive. Adding the premise

(zi, c−i) ∈ C≥k ensures that zi /∈ V k

i .

Lemma 36

If a partition 〈C k 〉k∈R has a representation in the noncompensatory sorting

mo**de**l with veto then it is R-3v-gra**de**d.

Proof

Suppose that, for some k, ℓ ∈ R + such that ℓ ≤ k, some xi, yi, zi ∈ Xi, and

some a−i, b−i, c−i ∈ X−i, (xi, a−i) ∈ C ≥k , (yi, b−i) ∈ C ≥ℓ , (zi, c−i) ∈ C ≥k

and (zi, a−i) ∈ C

Suppose that 3v-gra**de**d R

i is violated so that, for some ℓ ≤ k, (xi, a−i) ∈

C≥k , (yi, a−i) ∈ C≥k , (yi, b−i) ∈ C≥ℓ , (zi, c−i) ∈ C≥k , (xi, b−i) ∈ C

Sufficiency. Suppose that 〈Ck 〉k∈R is R-linear and R-3v-gra**de**d. For all

k ∈ R + , **de**fine V k

i = {xi ∈ Xi : (xi, a−i) ∈ C k are always satisfied with

such a **de**finition.

Let Y k

i = Xi \ V k

i and Y k =

i∈N

Y k

i

. We have Y k

i

⊆ Y k−1

i , for all

k ∈ {r, r − 1, . . .,3}. Since 〈C k 〉k∈R is a partition, 〈C ≥k , C

Let 〈F ℓ , 〈A ℓ

i 〉i∈N〉 be any representation of 〈D ≥ℓ , D

Let 〈F t , 〈A t

i 〉i∈N〉 be a representation of 〈D≥t , D

on these attributes x ′ i ∈ A s

i . For all i ∈ N such that xi /∈ A t

i , we consi**de**r

two cases.

1. Suppose that i ∈ N is influent for 〈D≥s , D

Example 42

Suppose that n = 3, X1 = X2 = X3 = {8, 9, 10, 11}. We consi**de**r a threefold

partition 〈C 1 , C 2 , C 3 〉. Let C 3 = {(10, 9, 10), (10, 9, 11), (10, 10, 10), (10, 10,

11), (10, 11, 10), (10, 11, 11), (11, 9, 10), (11, 9, 11), (11, 10, 10), (11, 10, 11),

(11, 11, 10), (11, 11, 11) }, C 2 = {(8, 10, 9), (8, 10, 10), (8, 10, 11), (8, 11, 9),

(8, 11, 10), (8, 11, 11), (9, 10, 9), (9, 10, 10), (9, 10, 11), (9, 11, 9), (9, 11, 10),

(9, 11, 11), (10, 9, 9), (10, 10, 8), (10, 10, 9), (10, 11, 8), (10, 11, 9), (11, 9, 9),

(11, 10, 8), (11, 10, 9), (11, 11, 8), (11, 11, 9)} and C 1 = X \ [C 3 ∪ C 2 ].

This partition can be obtained with the pessimistic version of ELECTRE

TRI nested relations with (10, 10, 10) as the limiting profile between C 3 and

C 2 and (10, 10, 9) as the limiting profile between C 2 and C 1 , Si = ≥ for

all i ∈ N, w1 = w3 = 0.4, w2 = 0.2, λ 3 = 0.7, λ 2 = 0.5, V1 = ∅ and

Vi = {(10, 8), (11, 8)}, for i ∈ {2, 3}. This shows that this partition is Rlinear

and R-3v-gra**de**d.

We have:

• V 3

1

= V 3

3

= {8, 9}, V 3

2

• V 2

1 = V 2

3 = ∅, V 2

2 = {8}.

= {8},

For the twofold partition 〈D ≥3 , D

6.4.1 In**de**pen**de**nce of conditions

Example 26 above gives a partition that is R-2-gra**de**d and that satisfies

linear R

i on all but one attribute. Since R-2-gra**de**dness implies R-3v-gra**de**dness,

this gives an example showing that, in Theorem 38, no condition linear R

i is

re**du**ndant.

The following example shows that a partition may be R-linear and may

satisfy 3v-gra**de**d R

i on all but one attribute.

Example 43

Let n = 3, X = {x1, y1, z1} × {x2, y2, z2} × {x3, y3, z3} and r = 4. Let

C 4 = {(x1, x2, x3), (y1, x2, x3), (z1, x2, x3), (x1, y2, x3), (y1, y2, x3), (z1, y2, x3),

(x1, x2, y3), (y1, x2, y3), (z1, x2, y3), (x1, y2, y3), (y1, y2, y3)}, C 3 = {(z1, y2, y3)},

C 2 = {(x1, x2, z3), (y1, x2, z3), (x1, y2, z3), (y1, y2, z3), (x1, z2, x3), (y1, z2, x3),

(x1, z2, y3), (y1, z2, y3), (y1, z2, z3)} and C 1 = {(x1, z2, z3), (z1, z2, z3), (z1, y2, z3),

(z1, z2, y3), (z1, x2, z3), (z1, z2, x3)}.

We have y1 ≻ R 1 x1 ≻ R 1 z1, x2 ≻ R 2 y2 ≻ R 2 z2 and x3 ≻ R 3 y3 ≻ R 3 z3. This

shows that the partition is R-linear.

Condition 3v-gra**de**d R

1 is violated since (x1, y2, y3) ∈ C ≥4 , (y1, y2, y3) ∈

C ≥4 , (y1, z2, z3) ∈ C ≥2 and (z1, x2, x3) ∈ C ≥4 , while (x1, z2, z3) /∈ C ≥2 and

(z1, y2, y3) /∈ C ≥4 .

We have x2 ≻ 4 2 y2 ≻ 4 2 z2, [x2 ∼ 3 2 y2] ≻ 3 2 z2 and [x2 ∼ 2 2 y2] ≻ 2 2 z2. We never

have (α1, z2, α3) ∈ C≥4 . Using Lemma 37, this shows that 3v-gra**de**d R

2 holds.

Similarly, it is easy to check that 3v-gra**de**d R

3 holds. ✸

Hence, we have shown that none of the conditions used in Theorem 38 is

re**du**ndant. Note that, in Example 43, the weakening of condition 3v-gra**de**d R

i

obtained requiring 3v-gra**de**d R

i

only when k = ℓ is satisfied, for all i ∈ N.

Similarly, in Example 26, the weakening of linear R

i requiring linear R

i only

when ℓ = k is satisfied, for all i ∈ N. Hence, our two conditions may not be

weakened in this way.

6.4.2 Uniqueness

Let 〈A , U 〉 be a twofold partition of X. Define Zi = {xi ∈ Xi : (xi, a−i) ∈

U , for all a−i ∈ X−i} and Yi = Xi \ Zi. Let Y = n i=1 Yi and **de**fine A ′ =

A ∩ Y and U ′ = U ∩ Y . We show in Bouyssou and Marchant (2005) that

the representation of 〈A , U 〉 is unique if and only if all attributes i ∈ N are

influent for 〈A ′ , U ′ 〉.

As was the case for the noncompensatory sorting mo**de**l, the additional

constraints brought by the noncompensatory sorting mo**de**l with veto with

more than two categories are such that this sufficient condition is no longer

45

necessary. Since the noncompensatory sorting mo**de**l is a particular case of

the noncompensatory sorting mo**de**l with veto, Example 28 illustrates this

possibility. The uniqueness of the representation in the noncompensatory

sorting mo**de**l with veto can be analyzed using the same lines as in Section

5.7. Since the **de**tails are cumbersome and not informative, we do not

**de**velop this point here. It should nevertheless be clear that as soon as some

attribute is **de**generate for a twofold partition 〈D ≥k , D

ather think that this is linked to the fact that the optimistic version

of ELECTRE TRI is not primarily based on the outranking relation S

but on its asymmetric part and in rather an undirect way.

• Our analysis has lead us to suggest a variant of the original ELECTRE

TRI method that uses a sequence of nested relations. Because this

modification is minor and nevertheless allows to increase the **de**scriptive

power of the technique, i.e., its ability to represent a given partition,

we believe that it would be worthwhile to consi**de**r it in real-world

applications.

• Our results show that the representation of a partition in the noncompensatory

sorting mo**de**l with veto is not likely to be unique. This has

clearly an impact on the way to approach methods trying to infer the

parameters of an ELECTRE TRI mo**de**l from assignment examples

(i.e., from a partition **de**fined on a subset of X) using mathematical

programming techniques (see Dias and Mousseau, 2006; Dias et al.,

2002; Mousseau et al., 2001a; Mousseau and S̷lowiński, 1998; Ngo The

and Mousseau, 2002). Given this non-uniqueness, a particular attention

should be given to the **de**rivation of robust recommendations on

the basis of such methods, i.e., recommendations that remains valid

for all possible values of the parameters that are compatible with the

assignment examples.

The analysis proposed in this paper can, and should, be exten**de**d in several

directions. It would be interesting to use the rich framework offered by

mo**de**l (D1) to tackle the case of other sorting methods. The authors have

started a research on the additive specialization of mo**de**l (D1) that is at

the heart of the famous UTADIS technique (see, e.g, Jacquet-Lagrèze, 1995;

Zopounidis and Doumpos, 2000a,b, 2001). Second, the axiomatic analysis

un**de**rtaken here would clearly call for experimental investigations of the reasonableness

of the conditions exhibited. As already stressed in Goldstein

(1991), experimental violations of R-linearity would have rather important

consequences. This might ren**de**r the analysis in Greco et al. (2001b) and

S̷lowiński et al. (2002) studying mo**de**ls tolerating violations of R-linearity

all the more important.

Summarizing, it seems that sorting mo**de**ls offer a wi**de**ly open field for

foundational research in the area of MCDM and that the general framework

for sorting mo**de**ls studied in Greco et al. (2001b) and S̷lowiński et al. (2002)

seems to be quite convenient to gui**de** such an investigation.

47

References

An**de**nmatten, A. (1995). Évaluation **du** risque **de** défaillance **de**s émetteurs d’obligations,

une approche par l’ai**de** multicritère à la décision. Presses Polytechniques

et Universitaires Roman**de**s, Lausanne.

Aron**de**l, C. and Girardin, P. (2000). Sorting cropping systems on the basis of their

impact on groundwater quality. European Journal of Operational Research,

127(3):467–482.

Bouyssou, D. and Marchant, Th. (2005). An axiomatic approach to noncompensatory

sorting methods in MCDM, I: The case of two categories. Working paper,

LAMSADE, Université Paris Dauphine, available at www.**lamsa de**.dauphine.

fr/ ∼bouyssou/. Bouyssou, D. and Pirlot, M. (1999). Conjoint measurement without additivity and

transitivity. In Meskens, N. and Roubens, M., editors, Advances in Decision

Analysis, pages 13–29. Kluwer, Dordrecht.

Bouyssou, D. and Pirlot, M. (2002a). A characterization of strict concordance relations.

In Bouyssou, D., Jacquet-Lagrèze, É., Perny, P., S̷lowiński, R., Van**de**rpooten,

D., and Vincke, Ph., editors, Aiding Decisions with Multiple Criteria:

Essays in Honour of Bernard Roy, pages 121–145. Kluwer, Dordrecht.

Bouyssou, D. and Pirlot, M. (2002b). Nontransitive **de**composable conjoint measurement.

Journal of Mathematical Psychology, 46:677–703.

Bouyssou, D. and Pirlot, M. (2004a). ‘Additive difference’ mo**de**ls without additivity

and subtractivity. Journal of Mathematical Psychology, 48(4):263–291.

Bouyssou, D. and Pirlot, M. (2004b). Preferences for multiattributed alternatives:

Traces, dominance, and numerical representations. Journal of Mathematical

Psychology, 48(3):167–185.

Bouyssou, D. and Pirlot, M. (2005). A characterization of concordance relations.

European Journal of Operational Research, 167(2):427–443.

Dias, L. C. and Clímaco, J. (2000). ELECTRE TRI for groups with imprecise

information on parameter values. Group Decision and Negotiation, 9:355–377.

Dias, L. C. and Mousseau, V. (2006). Inferring ELECTRE’s veto-related parameters

from outranking examples. European Journal of Operational Research,

170(1):172–191.

Dias, L. C., Mousseau, V., Figueira, J., and Clímaco, J. (2002). An aggregation

/ disaggregation approach to obtain robust conclusions with ELECTRE TRI.

European Journal of Operational Research, 138:332–48.

Fishburn, P. C. (1970). Utility theory for **de**cision-making. Wiley, New York.

Georgopoulou, E., Sarafidis, Y., Mirasgedis, S., Zaimi, S., and Lalas, D. (2003). A

multiple criteria **de**cision-aid approach in **de**fining national priorities for greenhouse

gases emissions re**du**ction in the energy sector. European Journal of

Operational Research, 146(1):199–215.

48

Goldstein, W. M. (1991). Decomposable threshold mo**de**ls. Journal of Mathematical

Psychology, 35:64–79.

Greco, S., Matarazzo, B., and S̷lowiński, R. (1999a). Rough approximation of a

preference relation by dominance relations. European Journal of Operational

Research, 117:63–83.

Greco, S., Matarazzo, B., and S̷lowiński, R. (1999b). The use of rough sets and

fuzzy sets in MCDM. In Gal, T., Hanne, T., and Stewart, T., editors, Multicriteria

**de**cision making, Advances in MCDM mo**de**ls, algorithms, theory and

applications, pages 14.1–14.59, Dordrecht. Kluwer.

Greco, S., Matarazzo, B., and S̷lowiński, R. (2001a). Axiomatic basis of noncompensatory

preferences. Communication to FUR X, 30 May–2 June, Torino,

Italy.

Greco, S., Matarazzo, B., and S̷lowiński, R. (2001b). Conjoint measurement and

rough set approach for multicriteria sorting problems in presence of ordinal

criteria. In Colorni, A., Paruccini, M., and Roy, B., editors, A-MCD-A, Ai**de**

Mulcritère à la Décision / Multiple Criteria Decision Aid, pages 117–144. European

Commission, Joint Research Centre, Luxembourg.

Greco, S., Matarazzo, B., and S̷lowiński, R. (2001c). Rough sets theory for multicriteria

**de**cision analysis. European Journal of Operational Research, 129:1–7.

Greco, S., Matarazzo, B., and S̷lowiński, R. (2002a). Multicriteria classification. In

Klogsen, W. and Zytkow, J., editors, Handbook of data mining and knowledge

discovery, pages 318–328. Oxford University Press, Oxford.

Greco, S., Matarazzo, B., and S̷lowiński, R. (2002b). Rough sets methodology

for sorting problems in presence of multiple attributes and criteria. European

Journal of Operational Research, 138:247–59.

Greco, S., Matarazzo, B., and S̷lowiński, R. (2005). Decision rule approach. In

Figueira, J., Greco, S., and Ehrgott, M., editors, Multiple Criteria Decision

Analysis: State of the Art Surveys, pages 507–562. Springer Verlag, Boston,

Dordrecht, London.

Jacquet-Lagrèze, É. (1995). An application of the UTA discriminant mo**de**l for the

evaluation of R&D projects. In Pardalos, P., Siskos, Y., and Zopounidis, C.,

editors, Advances in Multicriteria Analysis, pages 203–211. Kluwer, Dordrecht.

Krantz, D. H., Luce, R. D., Suppes, P., and Tversky, A. (1971). Foundations

of measurement, vol. 1: Additive and polynomial representations. Aca**de**mic

Press, New York.

Lourenco, R. P. and Costa, J. P. (2004). Using ELECTRE TRI outranking method

to sort MOMILP non dominated solutions. European Journal of Operational

Research, 153(2):271–289.

Marichal, J.-L. (2000). On Sugeno integrals as an aggregation function. Fuzzy Sets

and Systems, 114.

Moussa, N. (2001). Ai**de** multicritère à l’évaluation qualitative par inférence **de**

49

modèles **de** tri ordinal sur une hiérarchie **de** critères. Thèse **de** doctorat, Université

Paris-Dauphine.

Mousseau, V., Figueira, J., and Naux, J.-Ph. (2001a). Using assignment examples

to infer weights for ELECTRE TRI method: Some experimental results.

European Journal of Operational Research, 130:263–275.

Mousseau, V., Roy, B., and Sommerlatt, I. (2000a). Elaboration d’un outil d’ai**de**

à la décision en vue **de** l’évolution **de** la tarification **de**s transports publics en

Ile **de** France. Journal of Decision Systems, 9(2):289–315.

Mousseau, V., Roy, B., and Sommerlatt, I. (2001b). Development of a **de**cision

aiding tool for the evolution of public transport ticket pricing in the Paris

region. In A. Colorni, M. P. and Roy, B., editors, A-MCD-A Ai**de** Multicritère

à la Décision - Multiple Criteria Decision Aiding, pages 213–**230**. European

Commission, Joint Research Centre, Luxembourg.

Mousseau, V. and S̷lowiński, R. (1998). Inferring an ELECTRE TRI mo**de**l from

assignment examples. Journal of Global Optimization, 12:157–174.

Mousseau, V., S̷lowiński, R., and Zielniewicz, P. (2000b). A user-oriented implementation

of the ELECTRE TRI method integrating preference elicitation

support. Computers & Operations Research, 27:757–777.

Ngo The, A. and Mousseau, V. (2002). Using assignment examples to infer category

limits for the ELECTRE TRI method. Journal of Multi-Criteria Decision

Analysis, 11(1):29–43.

Roy, B. (2002). Présentation et interprétation **de** la métho**de** ELECTRE TRI pour

affecter **de**s zones dans **de**s catégories **de** risque. Document **du** LAMSADE 124,

Université **de** Paris Dauphine. 25 pages.

Roy, B. and Bouyssou, D. (1993). Ai**de** multicritère à la décision : métho**de**s et

cas. Economica, Paris.

S̷lowiński, R., Greco, S., and Matarazzo, B. (2002). Axiomatization of utility, outranking

and **de**cision-rule preference mo**de**ls for multiple-criteria classification

problems un**de**r partial inconsistency with the dominance principle. Control

and Cybernetics, 31(4):1005–1035.

Tervonen, T., Almeida-Dias, J., Figueira, J., Lah**de**lma, R., and Salminen, P.

(2005). SMAA-TRI: A parameter stability analysis method for ELECTRE

TRI. Research Report 6, INESC - Coimbra.

Wei, Y. (1992). Ai**de** multicritère à la décision dans le cadre **de** la problématique

**du** tri : concepts, métho**de**s et applications. Thèse **de** doctorat, Université Paris

Dauphine, Paris.

Zopounidis, C. and Doumpos, M. (2000a). Intelligent **de**cision aiding systems based

on multiple criteria for financial engineering. Kluwer, Dordrecht.

Zopounidis, C. and Doumpos, M. (2000b). PREFDIS: A multicriteria **de**cision support

system for sorting **de**cision problems. Computers & Operations Research,

27(7–8):779–797.

Zopounidis, C. and Doumpos, M. (2001). A preference disaggregation **de**cision

50

support system for financial classification problems. European Journal of Operational

Research, 130(2):402–413.

Zopounidis, C. and Doumpos, M. (2002). Multicriteria classification and sorting

methods: A literature review. European Journal of Operational Research,

138:229–246.

51