Keywords: Aide multicritère à la décision, Approche constructiviste, Problèmes de tri, Electre Tri-nC Multiple criteria decision aiding, Constructive approach, Sorting, Electre Tri-nC, Decision support

Une méthode multicritère de tri en utilisant plusieurs actions caractéristiques de référence pour définir chaque catégorie : la méthode Electre Tri-nC Résumé Dans cet article, une nouvelle méthode de tri, qui généralise la méthode Electre Tri-C, est proposée. On appelle cette méthode Electre Tri-nC. Cette méthode de tri est appropriée à des contextes d'aide à la décision où les catégories sont complètement ordonnées et chacune d'elles étant définie par plusieurs actions caractéristiques de référence au lieu d'une seule par catégorie. Electre Tri-nC a également été conue pour vérifier un ensemble d'exigences structurelles naturelles (la conformité, l'homogénéité, la monotonie et la stabilité), qui peuvent être considérées comme ses propriétés fondamentales. Cette méthode est constituée de deux règles couplées, appelées la règle descendante et la règle ascendante, qui doivent être utilisées conjointement (et pas séparément). Chacune de ces deux règles fait intervenir une fonction de sélection, qui est utilisée pour choisir une catégorie parmi deux catégories consécutives pour l'affectation possible d'une action. Le processus de co-construction entre l'analyste et le décideur peut être amélioré en ajoutant une nouvelle action caractéristique de référence. Cela implique la modification de la définition d'une catégorie et, par conséquent, a des impacts sur les résultats d'affectation, après cette modification. Dans cet article ce type de phénomènes est analysé de faon précise. Un exemple numérique est aussi présenté afin d'illustrer les résultats théoriques majeurs fournis par la méthode Electre Tri-nC. Une comparaison avec certaines méthodes de tri, qui partagent quelques éléments clés avec cette nouvelle méthode de tri, notamment en utilisant plusieurs actions caractéristique de référence pour définir chacune des catégories, permet de conclure que la méthode Electre Tri-nC est appropriée pour tre appliquée aux problèmes de tri.

Introduction

Different decision problems require different approaches to solve them. We are interested in decision aiding contexts in which the objects of a decision (actions, alternatives, ...) must be sorted, or assigned to a set of categories. Such an assignment is based on the evaluation of each action according to multiple criteria. The manner in which the decision aiding is considered in these decision aiding sorting contexts leads to take into account several assumptions: Assumption 1. The set of categories to which the actions must be assigned to is completely ordered (from the best to the worst, from the highest priority to the lowest priority, from the most risky to the least risky, from the most consensual to the least consensual, and so on).

Assumption 2. Each category is designed a priori to receive actions, which will be or might be processed in the same way (at least in a first step).

Assumption 3. Each category is defined by a subset of characteristic reference actions, or characteristic actions, which are the most representative ones in a certain decision aiding context.

Let us suppose that the decision maker is able, through a co-construction interactive process with the analyst, to provide, for each criterion, the performance of each characteristic action. These characteristic actions are used to help the decision maker on the assignment of the objects a decision to the categories.

The case where each category is defined by only one characteristic reference action has already been analyzed by [START_REF] Almeida-Dias | Electre Tri-C: A multiple criteria sorting method based on characteristic reference actions[END_REF]. Therefore, the Electre Tri-C method was proposed. This method is composed of two joint rules, called the descending rule and the ascending rule. Each one of these rules selects only one category for a possible assignment of an action. They are used conjointly in order to highlight the highest category and the lowest category, which can appear potentially appropriate to receive an action. These two extreme categories can be the same. When they differ, this means that the assignment of such an action remains ill-determined within a range of consecutive categories taking into account the way that the set of characteristic actions defines the categories.

The method proposed in this paper, designated Electre Tri-nC, takes appropriately into account the Assumption 3. Therefore, a significant step of the constructive approach framework (see [START_REF] Roy | Decision science or decision-aid science[END_REF] is related to the co-construction of the characteristic actions through an interaction process between the analyst and the decision maker. This co-construction interactive process can be better facilitated by defining several characteristic actions instead of a single one for the definition of each category. In such a case, the decision maker can consider adequate to place more than one characteristic action in a category taking into account their performances in the decision aiding context.

Additionally, the aim is also related to the analysis the role of each subset of characteristic actions for the definition of each category and the impact in the assignment results by adding or removing a characteristic action to or from a subset of characteristic actions.

The rest of this paper is organized as follows. Section 2 is devoted to the main concepts, definitions, and notation; the designing of the categories; and, the structural requirements concerning the Electre Tri-nC method. Section 3 presents the assignment procedure, the justification, and the properties of the Electre Tri-nC method. Section 4 introduces another way for modifying the set of categories, by adding or, eventually, removing a characteristic action to or from a subset of characteristic actions. Section 5 provides a numerical example in order to illustrate the assignment results presented in this paper. Section 6 includes a comparison to some sorting methods, which have some shared features with the Electre Tri-nC method. Finally, the last section offers our concluding remarks and some avenues for future research.

Problem statement

This section is devoted to the main concepts, definitions, and notation; the design of the categories; and, the structural requirements concerning the Electre Tri-nC method.

Concepts, definitions, and notation

Let A = {a 1 , a 2 , . . . , a i , . . .} denote the set of potential actions. This set of actions can be completely known a priori or it may appear progressively during the decision aiding process. The objective is to assign these actions to a set of completely ordered categories, denoted C = {C 1 , C 2 , . . . , C h , . . . , C q }, with q 2. Suppose that a coherent family of n criteria, denoted F = {g 1 , g 2 , . . . , g j , . . . , g n }, with n 3, has been defined in order to evaluate any action considered to be assigned to a certain category (see [START_REF] Roy | Multicriteria Methodology for Decision Aiding[END_REF].

Each criterion g j will be considered as a pseudo-criterion, which means that two thresholds are associated to g j : an indifference threshold, q j , and a preference threshold, p j , such that p j q j 0. These thresholds are introduced in order to take into account the imperfect character of the data from the computation of the performances g j (a), for all a ∈ A, as well as the arbitrariness that affects the definition of the criteria. For more details about the definition of such thresholds, see, for instance, Almeida-Dias et al. (2009, Section 2). Let us notice that the case p j = q j = 0, for all g j ∈ F , is not excluded, but such a case must be considered as unusually realistic. In what follows, assume, without loss of generality, that all criteria g j ∈ F are to be maximized, which means that the preference increases when the criterion performance increases too.

When using the outranking concept, the main idea is that "a outranks a ′ " according to the criterion g j , denoted aS j a ′ , if "a is at least as good as a ′ " on criterion g j . Due to the definition of the indifference thresholds, q j , it is quite natural to consider that such an assertion is validated, without ambiguity, when g j (a)-g j (a ′ ) -q j . But, when -p j g j (a)g j (a ′ ) < -q j , the possibility of indifference between a and a ′ cannot be excluded. This indifference is less and less credible when g j (a)g j (a ′ ) moves closer to -p j .

Let σ(a, a ′ ) denote the credibility of the comprehensive outranking of a over a ′ , which reflects the strength of the statement "a outranks a ′ " (denoted aSa ′ ) when taking all the criteria from F into account. This aggregation issue is based on a single vector of weights, denoted w j , such that w j > 0, j = 1, . . . , n, which is associated to the set of criteria. Additionally, a vector of veto thresholds, denoted v j , such that v j p j can also be associated to the set of criteria. For more details on the computation of σ(a, a ′ ), see, for instance, Almeida-Dias et al. (2009, Section 2).

Let us introduce now the set of characteristic actions. Let B h = {b r h , r = 1, . . . , m h } denote a subset of characteristic actions introduced to define category C h , such that m h 1 and h = 1, . . . , q. These characteristic actions have been conceived to clearly identify a category in a particular decision aiding context (see Section 2.2). Notice that C 1 is the worst category and C q is the best one, with q 2. Let B ∪ {B 0 , B q+1 } denote the set of (q + 2) subsets of characteristic actions, or the set of all the characteristic actions, such that B = {B 1 , B 2 , . . . , B h , . . . , B q }. The two particular subsets of characteristic actions, denoted B 0 = {b 1 0 } and B q+1 = {b 1 q+1 }, contains two reference actions defined as follows: g j (b 1 0 ) is the worst possible performance on criterion g j , and g j (b 1 q+1 ) is the best possible performance on the same criterion g j , for all g j ∈ F . The worst and the best possible performances must be chosen such that, for any action a, one has g j (b 1 0 ) < g j (a) < g j (b 1 q+1 ), for all g j ∈ F . Moreover, for all g j ∈ F , one has g j (b r 1 )g j (b 1 0 ) > 0, r = 1, . . . , m 1 , and g j (b 1 q+1 )g j (b s q ) > 0, s = 1, . . . , m q .

The comparison of an action a to the characteristic actions b r h , r = 1, . . . , m h , provides m h credibility indices of each type, σ(a, b r h ) and σ(b r h , a). In order to make a judgment regarding the way in which an action a is placed with respect to the category C h , it is suitable to find an aggregation operator that allows to obtain a representative credibility index for each action a with respect to each subset of characteristic actions, B h , h = 1, . . . , q. As for the case of decision aiding sorting methods using a set of unordered categories (see, for instance, [START_REF] Perny | Multicriteria filtering methods based on concordance and non-discordance principles[END_REF], [START_REF] Henriet | Systèmes d' Évaluation et de Classification Multicritères pour l'Aide à la Décision : Construction de Modèles et Procédures d'Affectation[END_REF], [START_REF] Belacel | Multicriteria assignment method PROAFTN: Methodology and medical application[END_REF], and [START_REF] Léger | A multicriteria assignment procedure for a nominal sorting problematic[END_REF]), the max operator is also a natural choice in our framework (Definition 1).

Definition 1 (Categorical credibility indices).

(a) σ {a}, B h = max r = 1, ..., m h σ(a, b r h ) (b) σ B h , {a} = max s = 1, ..., m h σ(b s h , a)
The credibility indices computed according to Definition 1(a) can be interpreted as the categorical outranking degrees of action a over the subset of the characteristic actions B h . Similarly, the credibility indices computed according to Definition 1(b) can be interpreted as the categorical outranked degrees of action a over the subset of the characteristic actions B h .

Remark 1. Since for all b r h , 0 σ(a, b r h ) 1 and 0 σ(b s h , a) 1, then one has 0 σ {a}, B h 1 and 0 σ B h , {a} 1.
Let λ denote a credibility level as the minimum degree of credibility, which is considered or judged necessary by the decision maker for validating or not an outranking statement taking all the criteria from F into account.

In general, this minimum credibility level takes a value within the range [0.5, 1]. When comparing an action a to a subset of characteristic actions B h , this credibility level allows to define four λ-binary relations as follows.

Definition 2 (λ-binary relations).

(a) λ-outranking:

{a}S λ B h ⇔ σ {a}, B h λ. (b) λ-preference: {a}P λ B h ⇔ σ {a}, B h λ ∧ σ B h , {a} < λ. (c) λ-indifference: {a}I λ B h ⇔ σ {a}, B h λ ∧ σ B h , {a} λ. (d) λ-incomparability: {a}R λ B h ⇔ σ {a}, B h < λ ∧ σ B h , {a} < λ.
See also Proposition 2, in Section 3.3, which provides additional results related to the above Definition 2.

Designing the categories

The aim of this section is to present the main conditions regarding the nature and the motivation with respect to the design and the definition of the categories. The design of the categories depends on the decision aiding context as well as on the nature of the sorting problem. The design is associated to the set of next processing operations, after providing the assignment results. In order to operationally define such categories, several approaches can be used. In our problem statement framework, two approaches are usually formulated within the co-construction interactive process between the analyst and the decision maker: definition by boundary reference actions or definition by characteristic reference actions.

When the co-construction interactive process is facilitated through the definition of boundary reference actions, each category is defined by a lower boundary action and an upper boundary action. The boundary actions are introduced for modeling the frontiers between two consecutive categories. This means that the lower boundary action of a better category is also the upper boundary action of the worse consecutive category (assume that categories are closed from below).

Sometimes, defining boundary reference actions is a very hard task, where the obtained set of boundary reference actions can be inappropriate. This is particularly the case when the decision maker has a fuzzy idea of the boundary between two consecutive categories. In many real-world decision aiding situations these frontiers have no objective existence, since the separation between two consecutive categories can be conceived in several different ways, including some arbitrariness.

When the co-construction interactive process is facilitated through the definition of characteristic reference actions, each category is defined by a subset of at least one characteristic action. Each subset of characteristic actions should contain typical examples of actions subjected (without doubt) to the same processing operations according to the nature of each category in the decision aiding context considered.

The characteristic actions which define a category are assignment examples which belong to such a category whatever the set of technical and preference parameters associated to the sorting model. This way to proceed allows to incorporate in the sorting model a consistency parameter, which is related to the separability of the characteristic actions from B.

In order to conceive such reference actions, it is required that the characteristic actions belonging to B h+1 and those belonging to B h define two consecutive distinct categories. This means that it is necessary to impose that each characteristic action from B h+1 strictly dominates each characteristic action from B h . Let us recall such a (strict) dominance condition as follows: ∀j,

g j (b s h+1 ) -g j (b r h ) 0 and ∃j, g j (b s h+1 ) -g j (b r h ) > 0, s = 1, . . . , m h+1 ; r = 1, . . . , m h ; h = 1, . . . , (q -1). Remark 2. If B h has three characteristic actions such that B h = {b r h , b s h , b t h }
, where b r h strictly dominates b s h and b s h strictly dominates b t h , then the characteristic action b s h can be deleted from B h because such a reference action does not play any role when comparing any action a to the subset B h . Therefore, b s h is redundant. When considering the possible minimum differences in the performances of the characteristic actions, the (strict) dominance condition is not sufficient for defining two consecutive distinct categories. For instance, if for all g j ∈ F such that 0 g j (b s h+1 )g j (b r h ) q j , s = 1, . . . , m h+1 ; r = 1, . . . , m h ; h = 1, . . . , (q -1), then σ(b r h , b s h+1 ) = 1. Two subsets of characteristic actions, B h+1 and B h , define two consecutive distinct categories only if at least each characteristic action belonging to B h+1 are weakly preferred to each characteristic action belonging to B h according to at least one criterion. This implies that σ(b r h , b s h+1 ) < 1. Therefore, the set of characteristic actions, B, must fulfill the weak separability (Condition 1).

Condition 1 (Weak separability). The set of characteristic actions, B, fulfills the weak separability condition if and only if σ(b r h , b s h+1 ) < 1, r = 1, . . . , m h ; s = 1, . . . , m h+1 ; h = 1, . . . , (q -1).

(2.1)

If the weak separability condition is not fulfilled, then the analyst must improve the co-construction interactive process with the decision maker in order to obtain a consistent set B. According to some practical situations, this condition can be judged, by the decision maker, too weak for defining significant distinct categories through the characteristic actions. In such a case, it is often desirable to impose a stronger condition to the set B, defined as follows:

Condition 2 (Strict separability). The set of characteristic actions, B, fulfills the strict separability condition if and only if

σ(b r h , b s h+1 ) < 1 2 , r = 1, . . . , m h ; s = 1, . . . , m h+1 ; h = 1, . . . , (q -1). (2.2)
However, in certain cases, the set B can also fulfill an even stronger condition than the above two separability conditions, which is defined as follows:

Condition 3 (Hyper-strict separability). The set of characteristic actions, B, fulfills the hyper-strict separability condition if and only if σ(b r h , b s h+1 ) = 0, r = 1, . . . , m h ; s = 1, . . . , m h+1 ; h = 1, . . . , (q -1).

(2.3)

The above separability conditions are applied only between the characteristic actions that belong to different categories. Let us notice that there is no reason to impose some constraints on the characteristic actions belonging to the same category, C h . This means that between each pair of characteristic actions from B h , h = 1, . . . , q, introduced to define the category C h , h = 1, . . . , q, one can have λ-indifference, λ-preference, or λ-incomparability.

Structural requirements

The section introduces the structural requirements (Definition 3) which can be viewed as the desirable properties of the Electre Tri-nC method.

Definition 3 (Structural requirements).

(a) Conformity: each characteristic action b r h , r = 1, . . . , m h , must be assigned to category C h , h = 1, . . . , q. (b) Homogeneity: two actions must be assigned to the same category when they have the same outranking credibility indices with respect to each one of the characteristic actions.

(c) Monotonicity: if an action a strictly dominates a ′ , then a is assigned at least to the same category a ′ is assigned to.

(d) Stability: when applying either a merging or a splitting operation (see Definition 4), the actions previously assigned to the non-modified categories will be assigned to the same categories or, possibly, to the new categories, after modification. More precisely:

(1) After merging two consecutive categories:

-any action previously assigned to a non-adjacent category to the modified ones will remain in the same category; -any action previously assigned to an adjacent category to the modified ones will either be assigned to the same category or to the new category; -any action previously assigned to a merged category will either be assigned to the new category or to an adjacent category.

(2) After splitting a category into two new consecutive categories:

-any action previously assigned to a non-adjacent category to the modified one will remain in the same category;

-any action previously assigned to an adjacent category to the modified one will either be assigned to the same category or to a new category; -any action previously assigned to the split category will either be assigned to a new category or to an adjacent category.

Definition 3(d) implies that the set of characteristic actions, B, will be changed within a co-construction interactive process between the analyst and the decision maker. After a merging operation (Definition 4(a)), the new set of categories becomes

C * = {C 1 , C 2 , . . . , C h-1 , C ′ h , C h+2 , .
. . , C q }. This new set of categories is defined by a new set of characteristic actions, denoted B * = {B 1 , B 2 , . . . , B h-1 , B ′ h , B h+2 , . . . , B q }, which trivially fulfills at least the weak separability condition. After a splitting operation (Definition 4(b)), the new set of categories becomes

C * = {C 1 , C 2 , . . . , C h-1 , C ′ h , C ′′ h , C h+1 , .
. . , C q }. This new set of categories is defined by a new set of characteristic actions, denoted

B * = {B 1 , B 2 , . . . , B h-1 , B ′ h , B ′′ h , B h+1 , .
. . , B q }, which must fulfill at least the weak separability condition.

Definition 4 (Merging and splitting operations).

(a) Merging operation: two consecutive categories, C h and C h+1 , will be merged to become a new one, C ′ h , defined by a new subset of characteristic actions, B ′ h = {b r ′ h , r ′ = 1, . . . , m ′ h }, such that, for all g j ∈ F :

(1) for all b r ′ h , there is at least one b r h verifying g j (b r ′ h )g j (b r h ) 0;

(2) for all b r ′ h , there is at least one b s h+1 verifying g j (b s h+1 )g j (b r ′ h ) 0.

(b) Splitting operation: the category C h is split into two new consecutive categories, C ′ h and C ′′ h , defined by two new distinct subsets of characteristic actions,

B ′ h = {b r ′ h , r ′ = 1, . . . , m ′ h } and B ′′ h = {b r ′′ h , r ′′ = 1, . . . , m ′′ h }, respectively, such that: (1) for all b s h+1 and b r ′′ h , σ(b r ′′ h , b s h+1 ) < 1; (2) for all b r ′′ h and b r ′ h , σ(b r ′ h , b r ′′ h ) < 1; (3) for all b r ′ h and b r h-1 , σ(b r h-1 , b r ′ h ) < 1; (4) for all b r ′′
h , there is at least one b r h verifying g j (b r ′′ h )g j (b r h ) 0, for all g j ∈ F ; (5) for all b r ′ h , there is at least one b r h verifying g j (b r h )g j (b r ′ h ) 0, for all g j ∈ F .

Let us notice that adding or removing a category are particular cases of a merging and/or a spitting operations. Additionally, when each category is able to be defined by more than one characteristic action, it is suitable to analyze the impact of a local modification of a category by adding or removing a characteristic action to or from each subset of characteristic actions (see Section 4).

The Electre Tri-nC method

The aim of this section is to present the assignment procedure, the justifications, and the properties of the Electre Tri-nC method.

Assignment procedure

The Electre Tri-nC assignment procedure is composed of two joint rules, called the descending rule (Definition 5) and the ascending rule (Definition 6), which must be used conjointly (and not separately). These rules are based on the same rules proposed for the Electre Tri-C method [START_REF] Almeida-Dias | Electre Tri-C: A multiple criteria sorting method based on characteristic reference actions[END_REF], while replacing the classical credibility indices by the categorical credibility indices (Definition 1) introduced in Section 2.1.

Each one of the two joint rules makes use of a selecting function, denoted ρ {a}, B h . The objective of this function is to select one category between two consecutive ones, which are candidate to receive an action a. Due to the role played by this function, it must fulfill (see Section 3.2, question (4)) the two following properties: Property 1.

(a) ρ {a}, B h is a function of σ {a}, B h and σ B h , {a} , where B h is a subset of characteristic actions, h = 1, . . . , q.

(b) Let C h be the pre-selected category for a possible assignment of action a. The selection of C h (instead of an adjacent category, which is also candidate) is justified if and only if ρ {a}, B h is strictly greater than the value of the selecting function for the adjacent category. Consequently, if a is the same as one characteristic action from B h , b * h , then ρ {b * h }, B h must be the best of the two values (the equality being excluded). Property 2. Let a and a ′ be two actions that allow to pre-select the same category. If a strictly dominates a ′ , then ρ {a},

B h > ρ {a}, B h+1 ⇒ ρ {a ′ }, B h > ρ {a ′ }, B h+1 . This implication is equivalent, by the logic negation, to ρ {a ′ }, B h+1 ρ {a ′ }, B h ⇒ ρ {a}, B h+1 ρ {a}, B h .
Property 1(a) is imposed in order to clarify the arguments in which Electre Tri-nC is founded. Property 1(b) is necessary so that the selected categories by each one of the two joint rules play the appropriate role, which is given by the Electre Tri-nC assignment procedure. Property 2 is necessary in order to fulfill the monotonicity with respect to each one of the two joint rules.

Definition 5 (Descending rule). Choose a credibility level, λ ( 1 2 λ 1). Decrease h from (q + 1) until the first value, t, such that σ {a}, B t λ (C t will be called the descending pre-selected category):

(a) For t = q, select C q as a possible category to assign action a.

(b) For 0 < t < q, if ρ {a}, B t > ρ {a}, B t+1 , then select C t as a possible category to assign a; otherwise, select C t+1 .

(c) For t = 0, select C 1 as a possible category to assign a.

In the descending rule, a category is selected taking into account that: B t is the highest subset of characteristic actions such that the statement "a outranks B t " is validated with the chosen credibility level, λ. In such a case, the possibility of the assignment of action a to the descending pre-selected category C t must be examined. Nevertheless, taking into account the manner that the subsets of the characteristic actions B t and B t+1 were defined, the assignment of action a to C t+1 is an alternative that must also be examined (in such a case, the statement "a outranks B t+1 " is not validated with the chosen credibility level, λ) because B t+1 was not defined to play the role of a subset of upper bounds for the category C t .

Definition 6 (Ascending rule). Choose a credibility level, λ ( 1 2 λ 1). Increase h from zero until the first value, k, such that σ B k , {a} λ (C k will be called the ascending pre-selected category):

(a) For k = 1, select C 1 as a possible category to assign action a.

(b) For 1 < k < (q + 1), if ρ {a}, B k > ρ {a}, B k-1 then select C k as a possible category to assign a; otherwise, select C k-1 .
(c) For k = (q + 1), select C q as a possible category to assign a.

In the ascending rule, a category is selected taking into account that: B k is the lowest subset of characteristic actions such that the statement "B k outranks a" is validated with the chosen credibility level, λ. In such a case, the possibility of the assignment of action a to the ascending pre-selected category C k must be examined. Nevertheless, taking into account the manner that the subsets of the characteristic actions B k and B k-1 were defined, the assignment of action a to C k-1 is an alternative that must also be examined (in such a case, the statement "B k-1 outranks a" is not validated with the chosen credibility level, λ) because B k-1 was not defined to play the role of a subset of lower bounds for the category C k .

Remark 3. If each one of the subsets of characteristic actions, B h , h = 1, . . . , q, has only one characteristic action such that B h = {b h }, h = 1, . . . , q, then the descending rule (respectively the ascending rule) of Electre Tri-nC becomes the descending rule (respectively the ascending rule) of Electre Tri-C (Almeida-Dias et al.

2009).

Electre Tri-nC assignment procedure leads to select a lowest and a highest possible categories to which an action a can be assigned to by using the descending rule and the ascending rule conjointly (and not separately). Therefore, Electre Tri-nC provides as a possible assignment of action a (see Theorem 2):

-one category, when the two selected categories are the same; -two categories, when the two selected categories are consecutive; -a range of more than two consecutive categories, delimited by the two selected categories.

In what follows, Γ(a) denote the range of consecutive categories provided by Electre Tri-nC as possible categories to which an action a can be assigned to.

Justification of Electre Tri-nC

This section provides the justification for the Electre Tri-nC assignment procedure based on the answers of four key questions:

(1) Why to found an assignment procedure on the basis of the categorical credibility indices of types σ {a}, B h and σ B h , {a} ?

The three following fundamental features, or aspects, characterize the decision aiding context in which Electre Tri-nC has been conceived (see Section 1):

(i) the set of categories, in which the actions must be assigned to, are completely ordered;

(ii) to operate on this assignment, the performances of such actions are evaluated according to several criteria;

(iii) the actions to be assigned are compared with the characteristic actions, which define the set of categories.

There is, therefore, an absolute comparison instead of a relative comparison in order to assign the actions to the categories.

The assignment of an action a to a category C h must naturally be based on the manner that such an action a compares itself with the characteristic actions from B h , which are used to define the category C h . In order to properly take into account the three fundamental features of the problem, an assignment procedure could be founded on the "more or less high credibility" of the following statements: "an action a outranks a subset of characteristic actions B h " and "a subset of characteristic actions B h outranks an action a". The categorical credibility indices σ {a}, B h and σ B h , {a} are appropriate to model this "more or less high credibility".

Taking into account the manner that the characteristic actions from B h are defined, the category C h can receive actions a that outrank B h as well as actions a that are outranked by B h .

(2) Why two joint assignment rules for giving a possible range of consecutive categories in which an action a can be assigned to?

Taking the chosen credibility level, λ, into account, it can exist some actions a such that one of the two following situations occurs (see Proposition 2, in Section 3.3):

(i) there is at least one subset of characteristic actions B h , which is neither outranked by action a nor outranks a (i.e., action a and the subset B h are λ-incomparable);

(ii) there are more than one subset of characteristic actions B h , which are outranked by action a and outrank a at the same time (i.e., action a and the subset B h are λ-indifferent).

In the two above situations, it seems to us inappropriate to assign such an action a to only one category. But, on the contrary, it seems appropriate to search for the lowest category and the highest category likely to receive the action a, including all the possible intermediate categories (if they exist). Taking into account the way that the categories are defined, it can also exist some situations, which differ from those described above (see (i) and (ii)), so that several possibilities of an assignment can be derived. Instead of choosing one of the several categories, based on a more or less arbitrary assignment rule, we think that this choice must be done by the decision maker. In such a case, a category must be chosen by the decision maker according to the performances of the action a, her/his experience, and the set of the next processing operations, which is associated to the definition of the selected categories.

(3) Why to use both descending rule and ascending rule conjointly?

Before answering to this question, the following definition should be introduced.

Definition 7 (Transposition operation). Let p denote the initial sorting problem. Consider the new following sorting problem, denoted p ′ (called transposed sorting problem of p):

(a) The set of new criteria is F ′ = {g ′ j , j = 1, . . . , n}, such that each new criterion, g ′ j , is obtained from the problem p by the inversion of the preference direction of the criterion g

j ∈ F . (b) The set of new categories is C ′ = {C ′ h , h = 1, . . . , q}, such that C ′ h = C q+1-h , h = 1, . . . , q.
In this case, the worst category of the problem p, C 1 , becomes the best one of the problem p ′ , C ′ q , and the best category of the problem p, C q , becomes the worst one of the problem p ′ , C ′ 1 . (c) The performances of all the potential actions and all the subsets of characteristic actions (and notation) remain the same as in the problem p. Therefore, the transposition operation shows a way to replace the descending rule (Definition 5) by the ascending rule (Definition 6). There is no reason to choose only one of the two proposed joint rules, since they are not significantly distinct. On the contrary, when the two joint rules are applied conjointly, they either clearly show a single category where an action a can be assigned to if there is no ambiguity in such an assignment or the lowest category and the highest category likely to receive an action a, while such an assignment remain ill-determined within such a range.

(4) What kind of selecting function, ρ {a}, B h , guarantees that B h plays the required role according to its meaning?

Properties 1 and 2 (see Section 3.1) have been introduced for this purpose. Nevertheless, these two properties do not determine a unique shape for the selecting function, ρ {a}, B h . This function can specifically be defined in several ways. We propose to study the following one:

ρ {a}, B h = min σ {a}, B h , σ B h , {a} . (3.1)
Proposition 1. The min function (3.1) fulfills Properties 1 and 2.

The proof of Proposition 1 is provided in Appendix A.1. It would be interesting to study other specific selecting functions too, but for the sake of simplicity, this min selecting function seems to us as a good choice.

Properties of Electre Tri-nC

The aim of this section is to analyze the properties of the Electre Tri-nC method based on the structural requirements defined in Section 2.3 and according to the conditions imposed to the set of characteristic actions, B. Theorem 1(a) will bring to light the role played by a minimum required level of credibility, λ b , which is defined as follows:

λ b = max h=1,...,(q-1) σ(b r h , b s h+1 ), r = 1, . . . , m h ; s = 1, . . . , m h+1 . (3.2)
If the hyper-strict separability condition is fulfilled, then λ b = 0; if the strict separability condition is fulfilled, then λ b ∈ [0, 1 2 [; and, if the weak separability condition is fulfilled, then λ b ∈ [0, 1[ (see Section 2.2 for more details).

Theorem 1. The Electre Tri-nC assignment procedure fulfills: The proof of Theorem 1 is provided in Appendix A.2.

Corollary 1. If at least the strict separability condition is fulfilled, then the conformity property holds.

The proof of Corollary 1 is trivial according to the proof of Theorem 1(a). Let λ be the chosen credibility level used to define the λ-binary relations (see Definition 2, in Section 2.1). Proposition 2 presents a useful result when comparing an action a to the subsets of characteristic actions in order to shed light on the interpretation of the assignment results provided by Electre Tri-nC (see Theorem 2).

Proposition 2. For any action a compared to the subsets of characteristic actions B h one and only one of the three following cases occurs:

(a) Action a is neither λ-indifferent nor λ-incomparable to B h , h = 1, . . . , q.

(b) Action a is λ-indifferent to at least one subset of characteristic actions B h . Moreover, if B h is not unique, then the subsets of characteristic actions, which are λ-indifferent to action a, define a subset of consecutive categories.

(c) Action a is λ-incomparable to at least one subset of characteristic actions B h . Moreover, if B h is not unique, then the subsets of characteristic actions, which are λ-incomparable to action a, define a subset of consecutive categories.

The proof of Proposition 2 is provided in Appendix A.3.

Theorem 2. Let Γ(a) denote the range of consecutive categories provided by Electre Tri-nC as possible categories to which an action a can be assigned to.

(a) When a is neither λ-indifferent nor λ-incomparable to B h , h = 1, . . . , q: Γ(a) is composed by one or two consecutive categories.

(b) When a is λ-indifferent to at least one subset of characteristic actions B h : Γ(a) is composed by the subset of consecutive categories defined by such λ-indifference, and, possibly, by including one or two of the adjacent categories to them.

(c) When a is λ-incomparable to at least one subset of characteristic actions B h : Γ(a) is composed by the subset of consecutive categories defined by such λ-incomparability, and, possibly, by including one or two of the adjacent categories to them.

The proof of Theorem 2 is provided in Appendix A.4. Based on this proof, let us notice that:

-In the case of λ-indifference, the descending pre-selected category is the highest category, C t , such that a is λ-indifferent to B t , while the ascending pre-selected category is the lowest category, C k , such that a is λ-indifferent to B k .

-In the case of λ-incomparability, the descending pre-selected category is the the worst adjacent category, C t-1 , to the lowest category, C t , such that a is λ-incomparable to B t , while the ascending pre-selected category is the best adjacent category, C k+1 , to the highest category, C k , such that a is λ-incomparable to B k .

On modifying the definition of the categories

The merging and the splitting operations are two ways for modifying the definition of the categories, which necessarily change the number of categories. This section is devoted to another way for modifying the definition of the categories, which does not change their number, but at least the definition of one of them is changed. This modification consists in adding a characteristic action to a subset of characteristic actions. Moreover, changing a definition of a category has also an impact on the actions which could be assigned to the two adjacent categories. Let b * h be a new characteristic action, which is added to B h , for redefining the category C h . Therefore, let B * h = B h ∪ {b * h } be the modified subset of characteristic actions of C h . The decision maker can be interested in such a modification, when she/he is not in agreement with the assignment of some actions a. This can mainly occurs in the two following cases:

a is assigned to C h-1 , while the decision maker considers that a should be assigned to C h ; a is assigned to C h+1 , while the decision maker considers that a should be assigned to C h ; In these cases, the decision maker, in the co-construction interactive process with the analyst, can examine the possibility of adding such an action a as a characteristic action of C h . This way of modifying the definition of a category can also be necessary in order to define a category in a precisely best way.

Theorem 3 introduces the conditions in which such a modification can be done as well as the impact on the assignment results provided by the Electre Tri-nC method. The proof of Theorem 3 is provided in Appendix A.5. Let us notice that removing a characteristic action, bh , from a subset of characteristic actions, B h , is also a way of modifying the definition of the category, C h . However, it seems to us that there is less practical concerns about this modification than the modification by adding a characteristic action for redefining C h . When considering the case of removing a characteristic action, the only required condition is that B h must contain at least two characteristic actions before modification. Let Γ(a) and Γ * (a) be the assignment results of Electre Tri-nC before and after modification, respectively. The modification of the assignment results provided by Theorem 3 is also applied is this case on substituting Γ(a) (adding) by Γ * (a) (removing) and Γ * (a) (adding) by Γ(a) (removing).

A numerical example

The aim of this section is to illustrate the assignment results provided by Electre Tri-nC as well as a comparison to Electre Tri-C (Almeida- [START_REF] Almeida-Dias | Electre Tri-C: A multiple criteria sorting method based on characteristic reference actions[END_REF].

Consider 15 potential actions evaluated on a coherent family of 7 criteria to be maximized, without using veto thresholds (see Tables 1 and2). Suppose that in this numerical example, the decision maker wants to introduce five categories, denoted {C 1 , . . . , C 5 }, defined by a set of characteristic actions, denoted B = {B 1 , . . . , B 5 }, for assigning the potential actions. First, each subset characteristic actions, B h , h = 1, . . . , 5, which defines each category C h , h = 1, . . . , 5, has only one characteristic action, b 1 h , h = 1, . . . , 5, in order to define each one of the categories such that the Electre Tri-C method can be applied. Second, the decision maker wants to change the definition of the categories. Therefore, some characteristic actions are added to each subset of characteristic actions in order to illustrate to results provided by the Electre Tri-nC method (see Table 3). This whole set of characteristic actions fulfills the strict separability condition since λ b = 0.10. Therefore, the chosen credibility level can be any value within the range [0.50, 1]. The subset of such actions where each subset of characteristic actions has only one characteristic action fulfills the hyper-strict separability condition since λ b = 0. Therefore, the chosen credibility level can also be any value within the range [0.50, 1]. Let us suppose that the chosen credibility level is: λ = 0.70. According to such a credibility level, the characteristic actions of each subset B h , h = 1, . . . , 5, are compared as follows:

Table 3: Characteristic actions

(i) Subset B 1 : b 1 1 is λ-preferred to b 2 1 . (ii) Subset B 2 : b 1 2 is λ-preferred by b 3 2 ; b 2 2 is λ-preferred to b 3 2 . Therefore, b 1 2 is λ-preferred by b 2 2 .
(iii) Subset B 3 : b 1 3 is strictly dominated by b 2 3 ; b 3 3 strictly dominates b 2 3 . Therefore, b 2 3 can be removed from B 3 without any impact on the assignment results of any action a to be assigned.

(iv) Subset B 4 : b 1 4 is λ-preferred by b 2 4 ; b 3 4 is λ-preferred to b 2 4 . Therefore, b 1 4 is λ-preferred by b 3 4 . (v) Subset B 5 : b 1 5 is λ-preferred by b 2 5 .
The credibility indices of the comprehensive outranking of the potential actions over the subset of characteristic actions, and vice-versa, are presented in Table 4.

The assignment results provided by Electre Tri-C and Electre Tri-nC (when using the min selecting function (3.1)) are presented in Table 5.

a1 1 0 C2 C3 1 0 C2 C2 a2 0 1 C5 C5 0 1 C5 C5 a3 0 0 C3 C3 0 0 C3 C3 a4 1 0 C2 C3 0 0 C3 C3 a5 0 0 C1 C1 0 0 C1 C1 a6 0 0 C1 C1 0 0 C2 C2 a7 2 0 C2 C4 1 0 C3 C4 a8 0 0 C4 C4 0 0 C4 C4 a9 0 0 C2 C2 0 0 C2 C2 a10 1 0 C2 C2 0 0 C2 C2 a11 0 0 C2 C2 0 0 C2 C2 a12 0 0 C5 C5 0 1 C5 C5 a13 1 0 C2 C2 0 0 C2 C2 a14 2 0 C2 C3 1 0 C2 C3 a15 1 0 C3 C4 0 0 C3 C3
The assignment results presented in Table 5 allow to conclude that:

(i) When adding characteristic actions to redefine a category, the number of cases of λ-incomparability does not increase: see the assignment of actions a 1 , a 4 , a 7 , a 10 , a 13 , a 14 , and a 15 .

(ii) When adding characteristic actions to redefine a category, the number of cases of λ-indifference does not decrease: see the assignment of actions a 2 and a 12 .

(iii) Adding characteristic actions to the categories implies that the upper bound of Γ(a) moves down: see the assignment of actions a 1 and a 15 .

(iv) Adding characteristic actions to the categories implies that the lower bound of Γ(a) moves up: see the assignment of actions a 4 and a 7 .

(v) Adding characteristic actions to the categories implies that both lower and upper bounds of Γ(a) move up: see the assignment of action a 6 .

Taking into account the above conclusions, this numerical example shows that the amplitude of the range of categories provided by Electre Tri-nC can be lower than the amplitude of the range of categories provided by Electre Tri-C. Such numerical results of Electre Tri-nC illustrate the theoretical results provided by Theorems 1, 2, and 3.

Comparison to related sorting methods

The aim of this section is to examine several sorting methods, which have some shared features with the Electre Tri-nC method, while showing the main differences. The sorting methods which are going to be examined in this section have been selected because they make use of several reference actions for defining each category. They mainly belong to two decision aiding sorting contexts.

The first kind of methods are those where the set of decision aiding categories is unordered and each category is defined by several characteristic reference actions. Let us analyse the four following methods:

-Filtering by indifference assignment procedure, denoted here FIP [START_REF] Perny | Multicriteria filtering methods based on concordance and non-discordance principles[END_REF], in which an action a is assigned to C h if and only if a lies in the neighborhood of b r h . -Most indifferent prototype assignment procedure, denoted PIP [START_REF] Henriet | Systèmes d' Évaluation et de Classification Multicritères pour l'Aide à la Décision : Construction de Modèles et Procédures d'Affectation[END_REF], in which an action a is assigned to C h if and only if the near neighborhood of a is b r h . -Proaftn assignment procedure [START_REF] Belacel | Multicriteria assignment method PROAFTN: Methodology and medical application[END_REF], in which an action a is assigned to C h if and only if a is indifferent or roughly equivalent to b r h . -Trinomfc assignment procedure [START_REF] Léger | A multicriteria assignment procedure for a nominal sorting problematic[END_REF], in which an action a is assigned to C h if and only if a is similar to b r h . -Sorting by preference closeness assignment procedure, denoted here Closort [START_REF] Fernández | Multicriteria sorting using a valued preference closeness relation[END_REF], in which an action a is assigned to C h if and only if the preferential closest of a is b r h . The above assignment procedures make use of a closeness relation which was first proposed by S lowiński and [START_REF] Stefanowski | Rough classification with valued closeness relation[END_REF] for a classification procedure using decision rules in the rough set theory framework. The assignment is based on a membership function which is associated to both each category and each action to be assigned according to the max or the min operators. The following property plays a fundamental role in these methods [START_REF] Léger | A multicriteria assignment procedure for a nominal sorting problematic[END_REF]:

Property 3. The credibility index between two actions belonging to the same category must be strictly greater than the credibility index between two actions of different categories.

Electre Tri-nC differs from the the four above sorting methods, since:

-Electre Tri-nC is applied to the decision aiding sorting context where the categories are completely ordered, while the above sorting methods deal with sorting contexts where the categories are are unordered.

-Electre Tri-nC is based on a strong relationship between the preference direction of the criteria and the preference direction of the categories, while this relationship does not exist in the above sorting methods, since the categories are unordered, and such methods are likely to deal with attributes and criteria conjointly. Nevertheless, in Closort [START_REF] Fernández | Multicriteria sorting using a valued preference closeness relation[END_REF] this relationship seems to exist concerning an overall definition of the categories.

-Electre Tri-nC is founded on credibility degrees of an outranking relation, while the above sorting methods are founded on credibility degrees of a closeness relation, or similarity relation.

The second kind of methods are those where the set of decision aiding categories is completely ordered and each category is defined by several boundary reference actions. Each category, denoted here C h , is defined a lower subset of boundary actions, denoted here B h , and an upper subset of boundary actions, denoted here B h+1 . Let us analyse the two following methods:

-Generalized conjunctive assignment procedure, denoted here FSY (Yu 1992, pp. 108-141), in which an action a is assigned to category C h if and only if a outranks at least one boundary actions of B h and a does not outranks any boundary action of B h+1 .

-Filtering by strict preference assignment procedure, denoted here FPP [START_REF] Perny | Multicriteria filtering methods based on concordance and non-discordance principles[END_REF], in which an action a is assigned to category C h if and only if a is preferred to at least one boundary action from B h without being preferred to any boundary action of B h+1 .

According to both above sorting methods, FSY and FPP, the authors suppose that each one of the subsets of boundary actions contains non-dominated actions, or those actions are pairwise incomparable. For FSY, two consecutive subsets of boundary actions are distinguished by the (strict) dominance condition, where each one of the boundary actions from B h is strictly dominated by at least one boundary action from B h+1 and each one of the boundary actions from B h+1 strictly dominates at least one action from B h . In a theoretical point of view, this method FSY can be viewed as a generalization of the Electre Tri-B method (see, for instance, Almeida-Dias et al. (2009, Section 6)). However, the conditions in which the fundamental properties of FSY are fulfilled were not been analyzed by [START_REF] Yu | Aide Multicritère à la Décision dans le Cadre de la Problématique du Tri : Concepts, Méthodes et Applications[END_REF]. Therefore, additional conditions are mainly necessary so that the boundary actions must be assigned to a category delimited by them (the categories being closed from below or being closed from above).

FPP uses the same framework introduced for FSY, while using a preference relation instead of an outranking relation. Moreover, the subset of boundary actions are distinguished in a quite different way, while introducing a distinguishability condition, which means that for any bs h+1 ∈ B h+1 and br h ∈ B h , then g j ( bs h+1 -br h ) > p j , where p j is the preference thresholds.

Electre Tri-nC differs from the the two above sorting methods, since:

-Electre Tri-nC is applied to the decision aiding sorting context where the categories are defined by characteristic reference actions, while the two above sorting methods use boundary reference actions for defining the categories.

-Electre Tri-nC and FSY are based on credibility degrees of an outranking relation, while FPP is based on credibility degrees of a preference relation.

-Electre Tri-nC requires a chosen credibility level, which is judged necessary by the decision maker for validating an outranking statement, while such a credibility level is not necessarily required in the two above of sorting methods.

-The separability of each subset of reference actions is not modeled in the same way. Moreover, the distinguishability condition proposed for FPP is more restrictive than the hyper-strict separability condition (see Section 2.2) introduced for Electre Tri-nC.

-An ascending-based rule is also proposed for FSY and FPP. Such an ascending rule is used conjointly (and not separately) with the descending-based rule in Electre Tri-nC, while in FSY and FPP such two assignment rules are considered as two different assignment procedures so that they can be used separately.

Conclusions

In this paper, we presented a new sorting method, called Electre Tri-nC, which generalizes the Electre Tri-C method. In Electre Tri-nC, each one of the categories can be defined by several characteristic actions instead of a single one per category. This generalization, or extension, allows, in our opinion, to model a larger number of decision aiding situations in the field of sorting problems.

It was proved in this paper that the Electre Tri-nC method fulfills the fundamental properties of conformity, homogeneity, monotonicity, and stability. There is a minimum required credibility level, which is associated with the definition of the characteristic actions in order to obtain a consistent decision aiding assignment model.

If each one of the subsets of characteristic actions has only one characteristic action, then the descending rule (respectively the ascending rule) of the Electre Tri-nC method becomes the descending rule (respectively the ascending rule) of the Electre Tri-C method.

The numerical example presented in Section 5 shows an effective advantage of using Electre Tri-nC in comparison to Electre Tri-C where the range of categories may remain precisely defined by only one category. Adding characteristic actions to a subset of characteristic actions was also analyzed in order to improve the coconstruction interactive process between the analyst and the decision makers on the redefinition of each category (see also Section 4).

The comparison of Electre Tri-nC to some related sorting methods, using several reference actions to defined each one of the categories, allows to conclude that the analysis provided by Electre Tri-nC is original and useful for sorting problems (see Section 6).

As for future research avenues, a decision support system incorporating the concept of characteristic actions is to be implemented. At the same time, we should focus our attention on the inference of some parameters through an disaggregation-aggregation elicitation techniques using characteristic actions.

A Appendix: Proofs

Proof:

First, two mutually exclusive cases must successively be analyzed: Proof:

ρ {a}, B h = σ {a}, B h < σ B h , {a} (
The proof of Corollary 2 is directly obtained from the proof of the above Lemma 1 as follows:

-The logic negation of (b) of Lemma 1 corresponds exactly with the (a) of Corollary 2.

-The logic negation of (a) of Lemma 1 corresponds exactly with the (b) of Corollary 2.

(2) Proof with respect to Property 1 (i) The selection is performed by the descending rule (Definition 5): C t is the descending pre-selected category if and only if the statement "a outranks B t+1 " is not validated with the chosen credibility level, λ, while the statement "a outranks B t " is validated with the same chosen credibility level, λ. In other words, if and only if

Let ρ {a}, B h be a min selecting function such that ρ {a}, B h = min{σ {a}, B h , σ B h , {a} }.
σ({a}, B t+1 ) < λ σ {a}, B t . (A.1)
Arguments in favor of the selection of C t (instead of C t+1 ): this selection seems to be more and more justified when the credibility of the statement "B t outranks a" moves closer to 1. In other words, when σ B t , {a} becomes higher.

Arguments against the selection of C t (instead of C t+1 ): this selection seems to be less and less justified when the credibility of the statement "a outranks B t+1 " moves closer to λ. In other words, when σ({a}, B t+1 ) becomes higher. According to such arguments, when using the descending rule:

-the selection of C t is justified if and only if σ B t , {a} > σ({a}, B t+1 );

-on the contrary, if σ({a}, B t+1 ) σ B t , {a} , then the selection of C t+1 is justified. The chosen min function leads precisely to the same selection as analyzed above for the descending rule because of the following reasons:

-according to (a) of the above Corollary 2, C t is selected if and only if σ B t , {a} > σ({a}, B t+1 ) (the inequality σ({a}, B t+1 ) < σ {a}, B t being always verified, see the inequalities (A.1) above). -according to (b) of the above Lemma 1, C t+1 is selected if and only if σ({a}, B t+1 ) σ B t , {a} (the equality σ({a}, B t+1 ) = σ {a}, B t being excluded here, see the inequalities (A.1) above). (ii) The selection is performed by the ascending rule (Definition 6):

Let C k+1 be the ascending pre-selected category. This category is pre-selected if and only if the statement "B k outranks a" is not validated with the chosen credibility level, λ, while the statement "B k+1 outranks a" is validated with the same chosen credibility level, λ. In other words, if and only if

σ(B k , {a}) < λ σ(B k+1 , {a}). (A.2)
Arguments in favor of the selection of C k+1 (instead of C k ): this selection seems to be more and more justified when the credibility of the statement "a outranks B k+1 " moves closer to 1. In other words, when σ({a}, B k+1 ) becomes higher.

Arguments against the selection of C k+1 (instead of C k ): this selection seems to be less and less justified when the credibility of the statement "B k outranks a" moves away from λ. In other words, when σ(B k , {a}) becomes lower. According to such arguments, when using the ascending rule:

-the selection of C k+1 is justified if and only if σ({a}, B k+1 ) > σ(B k , {a}); -on the contrary, if σ(B k , {a}) σ({a}, B k+1 ), then the selection of C k is justified. The chosen min function leads precisely to the same selection as analyzed above for the ascending rule because of the following reasons:

-according to (b) of the above Corollary 2, C k+1 is selected if and only if σ({a}, B k+1 ) > σ(B k , {a}) (the inequality σ(B k , {a}) < σ(B k+1 , {a}) being always verified, see the inequalities (A.2) above). -according to (a) of the above Lemma 1, C k is selected if and only if σ(B k , {a}) σ({a}, B k+1 ) (the equality σ(B k , {a}) = σ(B k+1 , {a}) being excluded here, see the inequalities (A.2) above).

(3) Proof with respect to Property 2

Let ρ {a}, B h be a min function such that ρ {a}, B h = min{σ {a}, B h , σ B h , {a} }. Consider successively each one of the two joint rules.

(1) Case of the descending rule (Definition 5). Let C t be the descending pre-selected category for action a as well as for action a ′ . This implies that σ {a}, B t λ and σ({a}, B t+1 ) < λ as well as σ({a ′ }, B t ) λ and σ({a ′ }, B t+1 ) < λ. If for action a one has ρ({a}, B t ) > ρ({a}, B t+1 ), then, according to (a) of the above Corollary 2, one has σ B t , {a} > σ({a}, B t+1 ). Taking into account that a strictly dominates a ′ , then according to the monotonicity of σ({a}, B) and σ(B, {a}), one necessarily has σ(B t , {a ′ }) σ B t , {a} and σ({a}, B t+1 ) σ({a ′ }, B t+1 ). In such conditions, σ(B t , {a ′ }) > σ({a ′ }, B t+1 ). This implies that, according to (a) of the above Corollary 2, one obtains ρ({a ′ }, B t ) > ρ({a ′ }, B t+1 ).

(2) Case of the ascending rule (Definition 6).

Let C k+1 be the ascending pre-selected category for action a ′ as well as for action a. This implies that σ(B k+1 , {a ′ }) λ and σ(B k , {a ′ }) < λ as well as σ(B k+1 , {a}) λ and σ(B k , {a}) < λ. If for action a ′ one has ρ({a ′ }, B k+1 ) > ρ({a ′ }, B k ), then, according to (b) of the above Corollary 2, one has σ({a ′ }, B k+1 ) > σ(B k , {a ′ }). Taking into account that a strictly dominates a ′ , then according to the monotonicity of σ({a}, B) and σ(B, {a}), one necessarily has σ(B k , {a ′ }) σ(B k , {a}) and σ({a}, B k+1 ) σ({a ′ }, B k+1 ). In such conditions, σ({a}, B k+1 ) > σ(B k , {a}). This implies that, according to (b) of the above Corollary 2, one obtains ρ({a}, B k+1 ) > ρ({a}, B k ). 2

A.2 Proof of Theorem 1 (in Section 3.3)

The proof of Theorem 1 is applied to the descending rule. It remains valid for the ascending rule according to the transposition operation (see Definition 7).

(a) Conformity: Assume that the strict separability condition holds. Such a condition means that σ(b r h , b s h+1 ) < 1 2 , for r = 1, . . . , m h ; s = 1, . . . , m h+1 ; and, h = 1, . . . , (q -1). This implies that for each b r h , for r = 1, . . . , m h ; and h = 1, . . . , (q -1), one has max s=1,...,m h+1 σ(b r h , b s h+1 ) < 1 2 . In other words, σ({b r h }, B h+1 ) < 1 2 , for r = 1, . . . , m h ; and h = 1, . . . , (q -1). In such a case, one has λ > λ b for any λ ∈ [ 1 2 , 1]. By definition of the characteristic actions and by construction of the credibility indices, one has σ(b s h+1 , b r h ) = 1, for s = 1, . . . , m h+1 ; r = 1, . . . , m h ; and, h = 1, . . . , (q -1), and σ(b r h , b r h ) = 1, for r = 1, . . . , m h ; and h = 1, . . . , q. This implies that σ({b s h+1 }, B h ) = 1, for s = 1, . . . , m h+1 ; and h = 1, . . . , (q -1), and σ({b r h }, B h ) = 1, for r = 1, . . . , m h ; and h = 1, . . . , q. When applying the descending rule, the pre-selected category for the characteristic action b λ and if t ′ is the first value of h such that σ({a ′ }, B t ′ ) λ, then one necessarily has t t ′ . If t > t ′ and C t ′ is selected for the assignment of a ′ , then a better category, C t or C t+1 , is selected for the assignment of a. If t > t ′ and C t ′ +1 is selected for the assignment of a ′ , then the same category, C t ′ +1 , or a better category is selected for the assignment of a. Since ρ({a}, B t ) fulfills Property 2 (see Appendix A.1), if t = t ′ , then the monotonicity is also fulfilled.

u h-1 , {b r ′ h }) < 1, u = 1, . . . , m h-1 ; r ′ = 1, . . . , m ′ h .
According to the descending rule, we will prove successively that:

(1) Any action a previously assigned to a non-adjacent category C s , s (t + 3), then a will be assigned to the same category, after modification.

(2) Any action a previously assigned to a non-adjacent category C s , s (t -2), then a will be assigned to the same category, after modification.

(3) Any action a previously assigned to the adjacent category C t+2 , then a will either be assigned to the same category or to the new category, C ′ t , after modification. (4) Any action a previously assigned to the adjacent category C t-1 , then a will either be assigned to the same category or to the new category, C ′ t , after modification. (5) Any action a previously assigned to the merged category, C t or C t+1 , then a will either be assigned to the new category C ′ t or to an adjacent category, C t-1 or C t+2 , after modification. Let us prove these five cases:

(1) This proof is trivial since there are no changes in the subsets of characteristic actions B t+2 and B t+3 , which are relevant to an assignment to category C t+3 , after modification. Similar analysis is applied to the categories C s , s (t + 4).

(2) This proof is trivial since there are no changes in the subsets of characteristic actions B t-2 and B t-1 , which are relevant to an assignment to category C t-2 , after modification. Similar analysis is applied to the categories C s , s (t -3).

(3) An action a was assigned to C t+2 if and only if one of the two following conditions holds:

(i) σ({a}, B t+2 ) λ and σ({a}, B t+3 ) < λ, with ρ({a}, B t+2 ) > ρ({a}, B t+3 ). In such a case, the proof is similar to (1) above.

(ii) σ({a}, B t+2 ) < λ and σ({a}, B t+1 ) λ, with ρ({a}, B t+1 ) ρ({a}, B t+2 ). After a merging operation as analyzed above, the comparison between action a and B t+2 does not change, i.e., σ({a}, B t+2 ) < λ. When comparing action a with the new characteristic actions, B ′ t , one necessarily obtains σ({a}, B ′ t ) λ since σ({a}, B t+1 ) λ and σ({a}, B t+1 ) σ({a}, B ′ t ). Therefore, if ρ({a}, B ′ t ) > ρ({a}, B t+2 ), then action a is assigned to C ′ t ; otherwise, a is assigned to C t+2 . (4) An action a was assigned to C t-1 if and only if one of the two following conditions holds:

(i) σ({a}, B t-1 ) < λ and σ({a}, B t-2 ) λ, with ρ({a}, B t-2 ) ρ({a}, B t-1 ). In such a case, the proof is similar to (2) above. (ii) σ({a}, B t-1 ) λ and σ {a}, B t < λ, with ρ({a}, B t-1 ) > ρ({a}, B t ). After a merging operation as analyzed above, the comparison between action a and B t-1 does not change, i.e., σ({a}, B ). After a merging operation as analyzed above, the characteristic actions B t and B t+1 do not exist anymore. The comparison between action a, B t-1 , and B t+2 do not change, i.e., σ({a}, B t-1 ) λ and σ({a}, B t+2 ) < λ. Therefore, whatever the way action a is compared to the new characteristic actions, B ′ t , a will be assigned to

C t-1 (when ρ({a}, B t-1 ) > ρ({a}, B ′ t )), to C ′ t (when ρ({a}, B ′ t ) > ρ({a}, B t+2 ) or ρ({a}, B t-1 ) ρ({a}, B ′ t )), or to C t+2 (when ρ({a}, B ′ t ) ρ({a}, B t+2 )).
(5.2) An action a was assigned to C t+1 if and only if one of the two following conditions holds:

(i) σ({a}, B t+1 ) λ and σ({a}, B t+2 ) < λ, with ρ({a}, B t+1 ) > ρ({a}, B t+2 ). This proof is similar to (3.ii) above. In such a case, due to a merging operation, action a will be assigned to C ′ t or to C t+2 , after modification. (ii) σ({a}, B t+1 ) < λ and σ {a}, B t λ, with ρ({a}, B t ) ρ({a}, B t+1 ). This proof is similar to (5.1.ii) above. In such a case, due to a merging operation, action a will be assigned to C (1) Any action a previously assigned to a non-adjacent category C s , s (t + 2), then a will be assigned to the same category, after modification.

(2) Any action a previously assigned to a non-adjacent category C s , s (t -2), then a will be assigned to the same category, after modification.

(3) Any action a previously assigned to the adjacent category C t+1 , then a will either be assigned to the same category or to the new category, C ′′ t , after modification. (4) Any action a previously assigned to the adjacent category C t-1 , then a will either be assigned to the same category or to the new category, C ′ t , after modification. (5) Any action a previously assigned to the split category C t , then a will be assigned to one of the two new categories, C ′ t and C ′′ t , after modification. First, consider that each subset of characteristic actions, B h , has only one characteristic action, such that B h = {b h }, h = 1, . . . , q. In such a case, the following monotonicity properties are trivially verified:

(a) When at least b h+1 strictly dominates b h , h = 1, . . . , (q -1), one has: σ(a, b h ) is a monotonic non-increasing function of b h , h = 1, . . . , q. This means that σ(a, b h ) σ(a, b h+1 ), h = 1, . . . , (q -1); and, σ(b h , a) is a monotonic non-decreasing function of b h , h = 1, . . . , q. This means that σ(b h , a) σ(b h+1 , a), h = 1, . . . , (q -1).

(b) If action a strictly dominates action a ′ , then: σ(a, b h ) σ(a ′ , b h ), h = 1, . . . , q; and σ(b h , a) σ(b h , a ′ ), h = 1, . . . , q.

Second, let us now prove the two following properties:

(1) σ {a}, B h is a monotonic non-increasing function of the subsets B h , h = 1, . . . , q.

(2) σ B h , {a} is a monotonic non-decreasing function of the subsets B h , h = 1, . . . , q.

Therefore, one has:

(1) Consider now that each subset of characteristic actions, B h , has more than one characteristic action. Taking into account that all the characteristic actions belonging to B h+1 differ from all characteristic actions belonging to B h and all the characteristic actions belonging to B h+1 are at least weakly preferred to all characteristic actions belonging to B h , h = 1, . . . , (q -1), then, according to (a.i) and (b.i) above, the following conditions are verified: max r=1,...,m h {σ(a, b r h )} max s=1,...,m h+1 {σ(a, b s h+1 )} and max r=1,...,m h {σ(a, b r h )} max r=1,...,m h {σ(a ′ , b r h )}. This proves that σ {a}, B h is a monotonic non-increasing function of the subsets, B h , h = 1, . . . , q.

(2) Consider now that each subset of characteristic actions, B h , has more than one characteristic action. Taking into account that all the characteristic actions belonging to B h+1 differ from all characteristic actions belonging to B h and all the characteristic actions belonging to B h+1 are at least weakly preferred to all characteristic actions belonging to B h , h = 1, . . . , (q -1), then, according to (a.ii) and (b.ii) above, the following conditions are verified: max r=1,...,m h {σ(b r h , a)} max s=1,...,m h+1 {σ(b s h+1 , a)} and max r=1,...,m h {σ(b r h , a)} max r=1,...,m h {σ(b r h , a ′ )}. This proves that σ B h , {a} is a monotonic non-decreasing function of the subsets, B h , h = 1, . . . , q. 2 A.4 Proof of Theorem 2 (in Section 3.3) (a) If there is only λ-preference relations between an action a and all the subsets of characteristic actions, then the following case occurs (see Proposition 2(a)): {a}P λ B 0 , {a}P λ B 1 , . . ., {a}P λ B h , B h+1 P λ {a}, . . ., B q+1 P λ {a}, with 0 h q. According to the descending rule (Definition 5), the highest index t such that a is λ-preferred to B t is t = h. Thus, if ρ {a}, B t > ρ {a}, B t+1 , then C t is selected for the assignment of action a; otherwise, C t+1 is selected. According to the ascending rule (Definition 6), the lowest index k such that B k is λ-preferred to a is k = (h + 1). Thus, if ρ {a}, B k > ρ {a}, B k-1 , then C k is selected for the assignment of action a; otherwise, C k-1 is selected. Consequently, both joint rules can provide either the same category (C h or C h+1 ) or the descending rule provides the category C h and the ascending rule, the category C h+1 or vice-versa.

(b) If an action a is λ-indifferent to at least one subset of characteristic actions, then the following case occurs (see Proposition 2(b)): {a}P λ B 0 , {a}P λ B 1 , . . ., {a}P λ B h , {a}I λ B h+1 , . . ., {a}I λ B s , B s+1 P λ {a}, . . ., B q+1 P λ {a}, with 0 h (q -1) and (h + 1) s q. According to the descending rule (Definition 5), the highest index t such that a is λ-indifferent to B t is t = s. Thus, if ρ {a}, B t > ρ {a}, B t+1 , then C t is selected for the assignment of action a; otherwise, C t+1 is selected. According to the ascending rule (Definition 6), the lowest index k such that a is λ-indifferent to B k is k = (h+1). Thus, if ρ {a}, B k > ρ {a}, B k-1 , then C k is selected for the assignment of action a; otherwise, C k-1 is selected. Consequently, the descending rule provides always a category at least as good as the one provided by the ascending rule because h < (h + 1) s < (s + 1).

(c) If an action a is λ-incomparable to at least one subset of characteristic actions, then the following case occurs (see Proposition 2(c)): {a}P λ B 0 , {a}P λ B 1 , . . ., {a}P λ B h , {a}R λ B h+1 , . . ., {a}R λ B s , B s+1 P λ {a}, . . ., B q+1 P λ {a}, with 0 h (q -1) and (h + 1) s q. According to the descending rule (Definition 5), the lowest index t such that a is λ-incomparable to B t is t = (h + 1). Thus, if ρ {a}, B t-1 > ρ {a}, B t , then C t-1 is selected for the assignment of action a; otherwise, C t is selected. According to the ascending rule (Definition 6), the highest index k such that a is λ-incomparable to B k is k = s. Thus, if ρ {a}, B k+1 > ρ {a}, B k , then C k+1 is selected for the assignment of action a; otherwise, C k is selected. Consequently, the descending rule provides always a category at most as good as the one provided by the ascending rule because h < (h + 1) s < (s + 1). 2

A.5 Proof of Theorem 3 (in Section 4)

Let us analyse the impact of each one the two following exclusive cases, or even both of them, on the assignment results of Electre Tri-nC, which can change such a range of categories, when a characteristic action b * h is added to B h for modifying the definition of C h :

( h }, fulfills at least the weak separability condition in order to respect the meaningful ordered character of the set of categories. Additionally, the conformity property must hold in order to continue with a coherent assignment model, which means that λ > λ b * , where λ is the same chosen credibility level before and after modification, and λ b * is the minimum required credibility level associated to B * . Let Γ(a) and Γ * (a) be the assignment results of Electre Tri-nC before and after modification, respectively. When taking into account the two above cases, we will prove successively that: (c) Two cases must be analyzed:

1) σ(a, b * h ) > σ {a}, B h and σ(b * h , a) < σ B h , {a} . Therefore, according to Definition 1, σ {a}, B * h > σ {a}, B h , σ B * h , {a} = σ B h ,
(i) C h+1 is the lowest category of Γ(a). There is the possibility of changes in Γ(a), if and only if C h+1 is obtained where the descending pre-selected is C t , or the ascending pre-selected category is C k+1 , before modification.

-After modification, the descending pre-selected category remains C t . In such a case, one has σ {a}, B * t λ and σ {a}, B t+1 < λ. If ρ {a}, B * t ρ {a}, B t+1 , then C t+1 remains the selected category for a possible assignment of a; otherwise, C t becomes the selected category.

-After modification, the ascending pre-selected category can remain C k+1 . In such a case, one has σ B k+1 , {a} λ and σ B * k , {a} < λ. If ρ {a}, B k+1 > ρ {a}, B * k , then C k+1 remains the selected category for a possible assignment of a; otherwise, C k becomes the selected category.

-After modification, the ascending pre-selected category can become C k . In such a case, one has σ B * k , {a} λ and σ B k-1 , {a} < λ. If ρ {a}, B * k > ρ {a}, B k-1 , then C k becomes the the selected category for a possible assignment of a; otherwise, C k-1 becomes the selected category.

Therefore, the lowest category of Γ * (a) is C h+1 , or it can either be C h or C h-1 . In such a case, at most the two categories, C h and C h-1 , can be added to Γ(a).

(ii) C h-1 is the highest category of Γ(a). There is the possibility of changes in Γ(a), if and only if C h-1 is obtained where the descending pre-selected is C t-1 , or the ascending pre-selected category is C k , before modification.

-After modification, the descending pre-selected category can remain C t-1 . In such a case, one has σ {a}, B t-1 λ and σ {a}, B * t < λ. If ρ {a}, B t-1 > ρ {a}, B * t , then C t-1 remains the selected category for a possible assignment of a; otherwise, C t becomes the selected category.

-After modification, the descending pre-selected category can become C t . In such a case, one has σ {a}, B * t λ and σ {a}, B t+1 < λ. If ρ {a}, B * t > ρ {a}, B t+1 , then C t becomes the selected category for a possible assignment of a; otherwise, C t+1 becomes the selected category.

-After modification, the ascending pre-selected category remains C k . In such a case, one has σ B * k , {a} λ and σ B k-1 , {a} < λ. If ρ {a}, B * k ρ {a}, B k-1 , then C k-1 remains the selected category for a possible assignment of a; otherwise, C k becomes the selected category.

Therefore, the highest category of Γ * (a) is C h-1 , or it can either be C h or C h+1 . In such a case, at most the two categories, C h and C h+1 , can be added to Γ(a).

(d) Two cases must be analyzed:

(i) C h-1 is the lowest category of Γ(a). This proof of similar to (c.ii) above. The lowest category of Γ * (a) is C h-1 , or it can either be C h or C h+1 . In such a case, at most the two categories, C h and C h+1 , can be removed from Γ(a).

(ii) C h+1 is the highest category of Γ(a). This proof of similar to (c.i) above. The highest category of Γ * (a) is C h+1 , or it can either be C h or C h-1 . In such a case, at most the two categories, C h and C h-1 , can be removed from Γ(a).

(e) Two cases must be analyzed:

(i) C h is the lowest category of Γ(a) There is the possibility of changes in Γ(a), if and only if C h is obtained where the descending pre-selected is C t-1 , or the ascending pre-selected category is C k+1 , before modification.

-After modification, the descending pre-selected category can remain C t-1 . In such a case, one has σ {a}, B t-1 λ and σ {a}, B * t < λ. Since ρ {a}, B t ρ {a}, B ′ t , one necessarily has ρ {a}, B t-1 ρ {a}, B ′ t . This implies that C t remains the selected category for a possible assignment of a.

-After modification, the descending pre-selected category can become C t . In such a case, one has σ {a}, B * t λ and σ {a}, B t+1 < λ. If ρ {a}, B * t > ρ {a}, B t+1 , then C t remains the selected category for a possible assignment of a; otherwise, C t+1 becomes the selected category.

-After modification, the ascending pre-selected category can remain C k+1 . In such a case, one has σ B k+1 , {a} λ and σ B * k , {a} < λ. Since ρ {a}, B k ρ {a}, B ′ k , one necessarily has ρ {a}, B k+1 ρ {a}, B ′ k . This implies that C k remains the selected category for a possible assignment of a.

-After modification, the ascending pre-selected category can become C k . In such a case, one has σ B * k , {a} λ and σ B k-1 , {a} < λ. If ρ {a}, B * k > ρ {a}, B k-1 , then C k remains the the selected category for a possible assignment of a; otherwise, C k-1 becomes the selected category.

Therefore, the lowest category of Γ * (a) is C h , or it can either be C h-1 or C h+1 . In such a case, C h-1 can be added to, or C h can be removed from Γ(a).

(ii) C h is the highest category of Γ(a). This proof of similar to (e.i) above. The highest category of Γ * (a) is C h , or it can either be C h-1 or C h-1 . In such a case, C h+1 can be added to, or C h can be removed from Γ(a). 2

  (a) the conformity property if λ > λ b .(b) the homogeneity, the monotonicity, and the stability properties.

Theorem 3 .

 3 Let b * h be an action, which is added as a characteristic action to the initial subset B h for modifying the definition of C h . Suppose that B * = B ∪ {b * h } fulfills at least the weak separability condition and the previously chosen credibility level, λ, verifies λ > λ b * . Let Γ(a) and Γ * (a) be the assignment results of Electre Tri-nC before and after modification, respectively. If Γ * (a) = Γ(a), then Γ * (a) is obtained from Γ(a) either by adding or by removing one or two categories among C h-1 , C h , and C h+1 . Moreover, if Γ(a) does not contain any of the categories, C h-1 , C h , or C h+1 , then one necessarily has Γ * (a) = Γ(a).

A. 1

 1 Proof of Proposition 1 (in Section 3.2) This proof is based on the following steps: (1) A related Lemma and Corollary; (2) Proof with respect to Property 1; and (3) Proof with respect to Property 2. (1) A related Lemma and Corollary Let ρ {a}, B h be a min function such that ρ {a}, B h = min{σ {a}, B h , σ B h , {a} }. According to the role that this function should play in the two joint rules of Electre Tri-nC, the following Lemma and Corollary can be stated as follows: Lemma 1. (a) min{σ {a}, B h , σ B h , {a} } min{σ({a}, B h+1 ), σ(B h+1 , {a})} if and only if σ B h , {a} σ({a}, B h+1 ) or σ B h , {a} = σ(B h+1 , {a}). (b) min{σ({a}, B h+1 ), σ(B h+1 , {a})} min{σ {a}, B h , σ B h , {a} } if and only if σ({a}, B h+1 ) σ B h , {a} or σ({a}, B h+1 ) = σ {a}, B h .

( a )

 a By definition, the chosen min function depends on the two credibility indices σ {a}, B h and σ B h , {a} . (b) Consider successively each one of the two joint rules.

  (b.3.1) Stability under a merging operation:Assume that the consecutive categories C h and C h+1 are merged to become a new one, denotedC ′ h . Let B ′ h = {b r ′ h , r ′ = 1, . . . , m ′ h }denote the subset of characteristic actions introduced to define the new category C ′ h . After this modification, the two adjacent categories of C ′ h are C h-1 and C h+2 . From the conditions imposed to b r ′ h , r ′ = 1, . . . , m ′ h , according to the merging operation (see Definition 4.a)), the new set of characteristic actions B ′ is obtained from B when replacing B h and B h+1 by B ′ h . Therefore, one has σ(b r ′ h , b s h+2 ) < 1, r ′ = 1, . . . , m ′ h ; s = 1, . . . , m h+2 , and σ(b

  {a} , and ρ {a}, B * h ρ {a}, B h . (2) σ(a, b * h ) < σ {a}, B h and σ(b * h , a) > σ B h , {a} . Therefore, according to Definition 1, σ {a}, B * h = σ {a}, B h , σ B * h , {a} > σ B h , {a} , and ρ {a}, B * h ρ {a}, B h . The characteristic action b * h can only be added to B h for modifying the definition of C h , if the new set of characteristic actions, B * = B ∪ {b *

  (a) If the lowest category of Γ(a) is C h+2 ; or the highest category of Γ(a) is C h-2 , then Γ * (a) = Γ(a). (b) If the lowest category of Γ(a) is C h-2 ; or the highest category of Γ(a) is C h+2 , then Γ * (a) = Γ(a). (c) If the lowest category of Γ(a) is C h+1 , or the highest category of Γ(a) is C h-1 , then Γ * (a) can differ from Γ(a) in at most two categories among C h-1 , C h , and C h+1 . (d) If the lowest category of Γ(a) is C h-1 , or the highest category of Γ(a) is C h+1 , then Γ * (a) can differ from Γ(a) in at most two categories among C h-1 , C h , and C h+1 . (e) If the lowest category of Γ(a) is C h , or the highest category of Γ(a) is C h , then Γ * (a) can differ from Γ(a) in one category among C h-1 , C h , and C h+1 .Let us prove these five cases:(a) The lowest category remains C h+2 , since there are no changes in B h+1 , B h+2 , and B h+3 , which are relevant to the selection of C h+2 , after modification; or, the highest category remains C h-2 since there are no changes in B h-3 , B h-2 , and B h-1 , which are relevant to the selection of C h-2 , after modification. Therefore, Γ * (a) = Γ(a).(b) The lowest category remains C h-2 , since there are no changes in B h-3 , B h-2 , and B h-1 , which are relevant to the selection of C h-2 , after modification; or, the highest category remains C h+2 since there are no changes in B h+1 , B h+2 , and B h+3 , which are relevant to the selection of C h+2 , after modification. Therefore, Γ * (a) = Γ(a).

  The sorting problems p and p ′ are equivalent. Let σ ′ {a}, B h and σ ′ B h , {a} denote the new categorical credibility indices obtained for the equivalent problem p ′ . It is trivial to prove that, for all action a and all subsets B h , one has: σ ′ {a}, B h = σ B h , {a} and σ ′ B h , {a} = σ {a}, B h . When the descending rule (Definition 5) is applied to the problem p ′ , the categorical credibility indices σ ′ {a}, B h and σ ′ B h , {a} are used to play the same role as the categorical credibility indices σ B h , {a} and σ {a}, B h in the ascending rule (Definition 6) applied to the problem p.

Table 1 :

 1 Criteria and parameters

		Possible performances	Parameters
	Criteria	Worst	Best	qj	pj	vj	wj
	g1	0	250	5	10	-	0.20
	g2	0	500	10	20	-	0.15
	g3	0	600	10	20	-	0.10
	g4	0	150	5	10	-	0.10
	g5	0	300	5	10	-	0.10
	g6	0	30	2	5	-	0.15
	g7	0	30	2	5	-	0.20

Table 2 :

 2 Potential actions

	Actions	g1	g2	g3	g4	g5	g6	g7
	a1	80	75	300	40	25	25	15
	a2	225	460	75	80	20	25	25
	a3	105	310	380	20	125	25	15
	a4	105	125	250	50	40	15	25
	a5	20	60	425	80	90	10	5
	a6	25	150	200	50	25	5	10
	a7	30	125	375	80	200	20	25
	a8	200	400	200	100	40	20	25
	a9	50	100	350	60	60	10	5
	a10	105	95	100	10	120	20	10
	a11	50	20	265	45	25	20	10
	a12	225	425	75	25	250	25	25
	a13	75	80	140	25	10	20	10
	a14	90	100	265	40	30	20	20
	a15	175	350	200	125	50	15	15

Table 4 :

 4 Outranking credibility (potential actions)

		σ {a}, B h						σ B h , {a}
	Actions	B0	B1	B2	B3	B4	B5	B6	B0	B1	B2	B3	B4	B5	B6
	a1	1.00	0.90	0.65	0.45	0.15	0.15	0.00	0.00	0.35	0.55	0.85	0.85	1.00	1.00
	a2	1.00	0.90	0.80	0.80	0.70	0.70	0.00	0.00	0.20	0.20	0.30	0.30	0.85	1.00
	a3	1.00	1.00	0.90	0.90	0.30	0.15	0.00	0.00	0.10	0.20	0.60	0.85	1.00	1.00
	a4	1.00	0.90	0.90	0.65	0.20	0.20	0.00	0.00	0.10	0.35	0.80	0.80	1.00	1.00
	a5	1.00	1.00	0.45	0.20	0.10	0.00	0.00	0.00	0.55	0.80	0.90	0.90	1.00	1.00
	a6	1.00	0.90	0.55	0.00	0.00	0.00	0.00	0.00	0.45	1.00	1.00	1.00	1.00	1.00
	a7	1.00	1.00	0.80	0.65	0.55	0.20	0.00	0.00	0.20	0.35	0.45	0.80	1.00	1.00
	a8	1.00	0.90	0.90	0.80	0.80	0.40	0.00	0.00	0.10	0.20	0.20	0.65	1.00	1.00
	a9	1.00	1.00	0.55	0.10	0.10	0.00	0.00	0.00	0.50	0.90	0.90	1.00	1.00	1.00
	a10	1.00	0.90	0.80	0.35	0.15	0.00	0.00	0.00	0.20	0.65	0.85	1.00	1.00	1.00
	a11	1.00	0.75	0.65	0.25	0.15	0.00	0.00	0.00	0.45	0.75	0.85	1.00	1.00	1.00
	a12	1.00	0.90	0.80	0.80	0.80	0.80	0.00	0.00	0.20	0.20	0.20	0.20	0.85	1.00
	a13	1.00	0.90	0.65	0.15	0.15	0.00	0.00	0.00	0.35	0.85	0.85	1.00	1.00	1.00
	a14	1.00	0.90	0.90	0.45	0.35	0.00	0.00	0.00	0.20	0.55	0.65	1.00	1.00	1.00
	a15	1.00	1.00	0.90	0.80	0.45	0.10	0.00	0.00	0.10	0.20	0.55	0.90	1.00	1.00

Table 5 :

 5 Assignment results (λ = 0.70)

		Electre Tri-C (λ b = 0.00)		Electre Tri-nC (λ b = 0.10)
				Lowest	Highest			Lowest	Highest
	Actions	Nr. R λ	Nr. I λ	Category	Category	Nr. R λ	Nr. I λ	Category	Category

  Then, ρ {a}, B h+1 = σ({a}, B h+1 ) σ {a}, B h . In such a case, the inequality of a) in Lemma 1 is always verified. Case 2: ρ {a}, B h = σ B h , {a} σ {a}, B h . In such conditions, one has ρ {a}, B h ρ {a}, B h+1 if and only if σ B h , {a} min{σ({a}, B h+1 ), σ(B h+1 , {a})}. This is either equivalent to σ B h , {a} σ({a}, B h+1 ) or to σ B h , {a} σ(B h+1 , {a}). This last condition is equivalent to σ B h , {a} = σ(B h+1 , {a}) since σ(B h+1 , {a}) σ B h , {a} . Then, the inequality or the equality of a) in Lemma 1 is always verified. Second, two another mutually exclusive cases must successively be analyzed: ρ {a}, B h+1 = σ({a}, B h+1 ) < σ(B h+1 , {a}) (case 3) and ρ {a}, B h+1 = σ(B h+1 , {a}) σ({a}, B h+1 ) (case 4). In each one of these two cases, let us examine in what conditions one has: ρ {a}, B h+1 ρ {a}, B h . if and only if σ({a}, B h+1 ) min{σ {a}, B h , σ B h , {a} }. This is either equivalent to σ({a}, B h+1 ) σ B h , {a} or to σ({a}, B h+1 ) σ {a}, B h . This last condition is equivalent to σ({a}, B h+1 ) = σ {a}, B h because σ {a}, B h σ({a}, B h+1 ). Then, the inequality or the equality of b) in Lemma 1 is always verified. Case 4: ρ {a}, B h+1 = σ(B h+1 , {a}) σ({a}, B h+1 ). According to the monotonicity of σ({a}, B) and σ(B, {a}) (see Appendix A.3), one obtains σ B h , {a} σ(B h+1 , {a}) σ({a}, B h+1 ) σ {a}, B h . Then, ρ {a}, B h = σ B h , {a} σ(B h+1 , {a}). In such a case, the inequality of b) in Lemma 1 is always verified. min{σ {a}, B h , σ B h , {a} } > min{σ({a}, B h+1 ), σ(B h+1 , {a})} if and only if σ B h , {a} > σ({a}, B h+1 ) and σ({a}, B h+1 ) < σ {a}, B h . (b) min{σ({a}, B h+1 ), σ(B h+1 , {a})} > min{σ {a}, B h , σ B h , {a} } if and only if σ({a}, B h+1 ) > σ B h , {a} and σ B h , {a} < σ(B h+1 , {a}).

	Corollary 2.
	(a)

case 1) and ρ {a}, B h = σ B h , {a} σ {a}, B h (case 2). In each one of these two cases, let us examine in what conditions one has: ρ {a}, B h ρ {a}, B h+1 . Case 1: ρ {a}, B h = σ {a}, B h < σ B h , {a} . According to the monotonicity of σ({a}, B) and σ(B, {a}) (see Appendix A.3), one obtains σ({a}, B h+1 ) σ {a}, B h < σ B h , {a} σ(B h+1 , {a}). Case 3: ρ {a}, B h+1 = σ({a}, B h+1 ) < σ(B h+1 , {a}). In such conditions, one has ρ {a}, B h+1 ρ {a}, B h

  r t is C t since σ(b t , b t ) is always strictly greater than to any λ ∈ [ 1 2 , 1[ and equal to λ if such a chosen credibility level is 1. C t is selected for the assignment of each characteristic action b r t if and only if ρ({b r t }, B t ) > ρ({b r t }, B t+1). This condition is verified, since ρ({b r t }, B t ) fulfills Property 1 (see Appendix A.1). The proof is similar when λ b By definition two different actions, a and a ′ , are compared themselves in an identical manner with respect to the subsets of characteristic actions if and only if the following conditions are verified: σ {a}, B h = σ({a ′ }, B h ) and σ B h , {a} = σ(B h , {a ′ }), for all h = 1, . . . , q. Therefore, for each chosen credibility level, λ, the homogeneity property is verified because the selection of category C t for a possible assignment of action a by the descending rule only depends on ρ({a}, B t ) = f σ {a}, B t , σ B t , {a} and ρ({a}, B t+1 ) = f σ({a}, B t+1 ), σ(B t+1 , {a}) or on ρ({a}, B t-1 ) = f σ({a}, B t-1 ), σ(B t-1 , {a}) and ρ({a}, B t ) = f σ {a}, B t , σ B t , {a} . From the monotonicity properties of σ({a}, B) and σ(B, {a}) (see Appendix A.3), if action a strictly dominates action a ′ , then σ {a}, B h σ({a ′ }, B h ) and σ B h , {a} σ(B h , {a ′ }), h = 1, . . . , q. When applying the descending rule, if t is the first value of h such that σ {a}, B t

	1 2 .
	(b.1) Homogeneity:
	(b.2) Monotonicity:

  t-1 ) λ. When comparing action a with the new characteristic actions, B ′ t , one necessarily obtains σ({a}, B ′ t ) < λ since σ {a}, B t < λ and σ({a}, B ′ t ) σ {a}, B t . Therefore, if ρ({a}, B t-1 ) > ρ({a}, B ′ t ), then action a is assigned to C t-1 ; otherwise, a is assigned to C ′ t . (5) Two cases must be analyzed: (5.1) An action a was assigned to C t if and only if one of the two following conditions holds: (i) σ {a}, B t < λ and σ({a}, B t-1 ) λ, with ρ({a}, B t-1 ) ρ({a}, B t ). This proof is similar to (4.ii) above. In such a case, due to a merging operation, action a will be assigned to C t-1 or to C ′ t , after modification. (ii) σ {a}, B t λ and σ({a}, B t+1 ) < λ, with ρ({a}, B t ) > ρ({a}, B t+1

  Assume that the category C h is split into two new consecutive categories, denoted C ′ h and C ′′ h . Let B ′ h denote the subset of characteristic actions introduced to define the worst of the two new categories, C ′ h , and B ′′ h the subset of characteristic actions introduced to define the best of the two new categories, C ′′ h (see Definition 4.b)). After this modification, the two adjacent categories of the two consecutive new categories C ′ h and C ′′ h are C h-1 and C h+1 . According to the descending rule (Definition 5), it is required to prove successively that:

	t-1 ,
	C ′ t or to C t+2 , after modification.
	(b.3.2) Stability under a splitting operation:

  This proof is similar to the proof of the stability under a merging operation by stating thatC ′ t (merging) = C t (splitting), C t (merging) = C ′ t (splitting), C t+1 (merging) = C ′′ t (splitting), B t (before merging) = B ′ t (splitting), and B t+1 (before merging) = B ′′ t (splitting). It should be noticed that the merging operation is the "inverse operation" of the splitting one, and vice-versa. 2 A.3 Proof of Proposition 2 (in Section 3.3) This proof is based on the proof of the monotonicity of the categorical credibility degrees, σ({a}, B h ) and σ(B h , {a}), and taking into account that B h will play the same role as b h regarding the Electre Tri-C method (Almeida-Dias et al. 2009, Section 4).

Acknowledgements

Juscelino Almeida Dias acknowledges the financial support from the Grant SFRH/ BD/ 22985/ 2005 (Fundação para a Ciência e a Tecnologia, Portugal). The authors also acknowledge the financial support from the Luso-French bilateral cooperation agreement between LAMSADE and CEG-IST (FCT/CNRS 2009). This research also partially benefited from the COST Action Grant IC0602 on "Algorithmic Decision Theory".