key: cord-0044859-dbi10sgv
authors: Mayag, Brice; Tchantcho, Bertrand
title: The Necessary and Possible Importance Relation Among Criteria in a 2-Additive Choquet Integral Model
date: 2020-05-15
journal: Information Processing and Management of Uncertainty in Knowledge-Based Systems
DOI: 10.1007/978-3-030-50143-3_39
sha: e4d4a98ed920005c16832744338d2b548d976585
doc_id: 44859
cord_uid: dbi10sgv

In the context of the representation of a preference information by a 2-additive Choquet integral, we introduce the necessary and possible importance relations allowing to compare the Shapley values of two criteria. We present some sufficient conditions, using a set of binary alternatives, to get a necessary importance relation among two criteria.

In Operational Research domain, Multiple Criteria Decision Making (MCDM) is a scientific field which tries to represent the preferences of a Decision Maker (DM) over a set of alternatives evaluated on a set of criteria often contradictory. To represent a preference information of a DM, allowing some dependencies or interactions among criteria, a 2-additive Choquet integral model, a generalization of the well-known arithmetic mean, is usually elaborated.

The 2-additive Choquet integral is a particular case of the Choquet integral [1] [2] [3] 7] , an aggregation function based on the notion of capacity or fuzzy measure. The identification of the capacity leads to the computation of two important parameters of the 2-additive integral model: the interaction index [10] related to only two criteria and the importance of each criterion (corresponding to the Shapley value [12] ).

We assume that the DM can expresses his preferences through two binary relations on the set of alternatives: a strict and an indifference preference information. There exist some characterization about the representation of such information by a 2-additive Choquet integral, especially when the set of binary alternatives is considered [6, 7, 9] . A binary action is a fictitious alternative which takes either the neutral value 0 for all criteria, or the neutral value 0 for all criteria except for one or two criteria for which it takes the satisfactory value 1.

Under these hypotheses, we try to analyze, in this paper, the comparison of the importance index of two given criteria. To do so, we introduce the notions of necessary and possible importance relations among two criteria. A criterion i is possibly more important than criterion j, if there exists a compatible 2-additive capacity, representing the preference information given by the DM, such that the Shapley value associated to i is greater than the one associated to j. If this conclusion is made for all the compatible capacities, then i is judged necessarily more important than j. The concept of necessary and possible relations were introduced for the alternatives in a robust ordinal regression approach [5] , and extended for the interactions indices in the 2-additive Choquet integral model [9] . We give also some sufficient conditions in order to obtain a necessary importance relation among criteria, in the framework of binary alternatives.

The paper is organized as follows. The next section presents the basic material we need on the 2-additive Choquet integral. The new notions of necessary and possible relations among criteria are introduced in Sect. 3, after a motivating example based on hospitals rankings, in a real-world situation. Our results are presented in Sect. 4 and we end the paper by giving some perspectives of this work.

Let X be a finite set of alternatives evaluated on a set of n criteria N = {1, . . . , n}. The notation 2 N refers to the set of all subsets of N . The set of attributes is denoted by X 1 , . . . , X n . An alternative x is presented by

The notion of interaction among criteria is more simple and understandable, in MCDA, when it concerns only two criteria. That is why the Choquet integral w.r.t. a 2-additive capacity [6, 7] , also called 2-additive Choquet, was proposed in order to take into account the type of interaction between two criteria. This aggregation function, considered as a fuzzy integral, is based on the concept of capacity or fuzzy measure μ defined as a set function from the powerset of criteria 2 N to [0, 1] such that:

We associate to each capacity another set function called the Möbius transform m μ : 2 N → R defined by

A capacity μ on N satisfying the following two conditions:

• For all subset T of N such that |T | > 2, m μ (T ) = 0; • There exists a subset B of N such that |B| = 2 and m μ (B) = 0.

is said to be 2-additive.

In the sequel, we use, for a capacity μ and its Möbius transform m μ , the following notations:

Whenever we use i and j together, it always means that they are different.

Given an alternative x := (x 1 , ..., x n ) of X, the 2-additive Choquet integral of x is expressed as follows [4] :

is the interaction index between the two criteria i and j [2, 10] ;

defined as the importance of criterion i and it corresponds to the Shapley value of i w.r.t. μ [11] .

Equation (2) proves that the 2-additive Choquet integral is a generalization of the weighted sum. Indeed, when there is no interaction among criteria, the Shapley value φ μ i is the weight associated to the criterion i. There is another expression of C μ (u(x)), related to the coefficients of the Möbius transform of μ, given by:

(3) We assume that the DM expresses his preferences on X by giving a strict preference relation P and an indifference relation I on X. We say that the preference information {P, I} on X is representable by a 2-additive Choquet integral if we have: for all x, y ∈ X,

Let us consider eight hospitals (see Table 1 ), specialized in weight loss surgery 1 , and evaluated on four criteria given by the French magazine "Le Point 2 " [8] (see their evaluations in Table 1 below):

• Criterion 1 -Activity: number of procedures performed during one year. Since a hospital has a good score on activity then its teams are more trained and often have good results. Therefore this criterion has to be maximized. • Criterion 2 -Notoriety: It corresponds to the reputation and attractiveness of the hospital. It is a percentage of patients treated in the hospital but living in another French administrative department. The more the percentage increases, more the hospital is attractive.

the sum of inpatient days by the number of patients admissions with the same diagnosis-related group classification. If a hospital is more organized in terms of resources then its ALOS score should be low. • Criterion 4 -Technicality: this particular indicator measures the ratio of procedures performed with an efficient technology compared to the same procedures performed with obsolete technology. The higher the percentage is, the more the team is trained in advanced technologies or complex surgeries. Based on its expertise, the DM (a team of some specialists on weight loss surgery) provides the following preferences where P refers to the strict preference relation:

H1 P H2; H3 P H4; H5 P H6; H8 P H7.

Based on these preferences, he also asks himself the following questions which seem reasonable:

• Is the criterion Activity more important than the criterion Notoriety?

• Is the criterion Activity more important than the criterion ALOS?

First of all, let us try to model his preferences by an additive model. The four preferences could be representable by an arithmetic mean model, w.r.t. a vector of weights (w 1 , w 2 , w 3 , w 4 ) associated to the four criteria, if the following system is feasible:

It is not difficult to see that the first three equations in this system lead

]w 4 > 0 contradicting the last equation. Therefore the arithmetic mean is not able to model the DM preferences (5) .

To prove that these preferences are modeled by a 2-additive Choquet integral, we assume that the marginal utility functions are constructed by using the following monotone normalization formula of the criterion i, where U i (respectively L i ) represents a upper bound (respectively a lower bound) associated to the values of X i : Given

By choosing U 1 = 500, U 2 = U 4 = 100 and L 3 = 5, the obtained utility functions, associated to each hospital, are given by the Table 2 . Table 3 below presents five 2-additive capacities allowing to represent the preferences (5) by 2-additive Choquet integral.

These results show that the importance index of Activity is more important than Notoriety when the capacity of the Parameters 1, 4 and 5 are chosen. Conversely the importance index of the criterion Notoriety is more important than Activity for the capacity of Parameters 2 and 3. Hence, based on the preference giving by the Dean, it is not easy to conclude about the importance of the criterion Activity compared to the criterion Notoriety. We have similar conclusions with Activity and ALOS.

To overcome this limits we introduce in the next section the new notion of necessary and possible importance relation among two criteria.

Let {P, I} be a preference information on X representable by a 2-additive Choquet integral. We denote by C {P, I} 2 the set of all the 2-additive capacities compatible with {P, I}. Definition 1. Given two different criteria i and j. We say that:

Using these definitions, we can conclude that, in our previous example, the criterion Activity is not necessary important than Notoriety. The converse is also true. There exists only a possible importance relation among these two criteria. Now, let us give some sufficient conditions allowing to get the necessary importance relation among two given criteria when the DM expresses his preferences on a set of binary alternatives. 

In this section, we suppose that the DM is able to identify on each criterion i two reference levels: 1 i (the satisfactory or good level) and 0 i (the neutral level). These references are usually used in the elicitation of the parameters of the Choquet integral (see [3, 4] ). We set for convenience u i (1 i ) = 1 and u i (0 i ) = 0.

We ask to the DM, a preference information on a reference subset B of X , called the set of binary alternatives and defined by The following remark shows that the use of the binary alternatives can help to the determination of the 2-additive capacity.

Let μ be a 2-additive capacity. We have

We introduce the relation M modeling the natural monotonicity constraints μ ij ≥ μ i ≥ 0, i, j ∈ N for a 2-additive capacity μ. Let x, y ∈ B, x M y if one of the following two conditions is satisfied:

1. y = a 0 and not(x (P ∪ I) a 0 ), 2. ∃i, j ∈ N such that [x = a ij , y = a i ] and not[x (P ∪ I) y].

• The notation x T C y means that there is a path from x to y, i.e., there exists

• x T C P y denotes a path from x to y containing a strict preference P .

It is proven in [7] that, when the indifference relation is empty, the relation P is representable by a 2-additive Choquet integral if and only if the relation (P ∪ M ) contains no strict cycle, i.e., a cycle containing an element of P .

Lemma 1. Let μ be a 2-additive capacity on a finite set of n criteria N . Let i, j be two different criteria. We have:

Proof. Let μ be a 2-additive capacity on N and i, j ∈ N . The expression of the importance of these criteria w.r.t. μ are

Then we have:

This Lemma will help us to prove our proposition of sufficient conditions to obtain the necessary importance relation of two given criteria. As the number 4 − n appears in Eq. (8), we examine three cases of these sufficient conditions: n = 3, n = 4 and n ≥ 5.

Let P be a strict preference relation on B representable by a 2-additive Choquet integral.

i.e., criterion i is necessary more important than criterion j. N = {i, j, i.e., criterion i is necessary more important than criterion j.

The proof is similar if

If ⎧ ⎨ ⎩ a ik T C P a jk and a il T C P a jl then we have

The proof is similar if

If there exists a permutation σ on N \ {i, j} = {l 1 , l 2 , . . . , l n−2 } such that ⎧ ⎨ ⎩ a j T C P a i and a ilt T C P a jσ(lt) , t = 1, . . . , n − 2 , then we have ⎧ ⎨ ⎩ μ j > μ i and μ ilt > μ jσ(lt) , t = 1, . . . , n − 2.

Example 1. We suppose that the DM in our previous example on hospitals expresses his preferences on the following set of binary alternatives: a 1 , a 2 , a 3 , a 4 , a 12 , a 13 , a 14 , a 23 , a 24 , a 34 }

. he provides these two strict preferences:

• a 13 P a 24 : a satisfactory hospital on Activity and ALOS is strictly preferred to a satisfactory hospital on Notoriety and Technicality. • a 14 P a 23 : a satisfactory hospital on Activity and Technicality is strictly preferred to a satisfactory hospital on Notoriety and ALOS.

Using Proposition 1 for |N | = 4, we can conclude that the criterion Activity is necessary important than Notoriety. Therefore criterion 1 is necessary more important than criterion 2, even if the DM prefers a 2 to a 1 .

j is p-dominated (possibly dominated) by i if there exists l 0 ∈ N \ {i, j} such that the following conditions are satisfied:

This property ensures to have an element a il0 not dominated by any element related to the criterion j. The next proposition shows that, in this case, we always have i possibly important than j. Indeed, if we choose l 0 = 1, then we have not(a 14 T C a 13 ), not(a 24 T C a 13 ) and not(a 34 T C a 13 ).

As indicated in the previous proof, the binary relation T is added to (P ∪ M ) as follows: a 13 T a 14 and a 13 T a 34 .

Hence the partition of B, obtained after the topological sorting on (P ∪ I ∪ T ) given in the previous proof, leads to the following 2-additive capacity μ: ) > 0.

We introduced the concepts of necessary and possible importance relation among the criteria. These notions allow to have a robust interpretation when the parameters of the 2-additive Choquet integral are inferred from a preference information given by the DM. Of course, in the direct elicitation process, the DM may give directly a preference over the Shapley value of two criteria. In this case, the necessary relation is obviously obtained. The main perspective will be the complete characterization of the necessary and possible importance relations. We provided here some sufficient conditions as a first step of this future work.

Theory of capacities

k-order additive discrete fuzzy measures and their representation

Multiple Criteria Decision Analysis: State of the Art Surveys

A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid

Ordinal regression revisited: multiple criteria ranking using a set of additive value functions

A characterization of the 2-additive Choquet integral through cardinal information

A representation of preferences by the Choquet integral with respect to a 2-additive capacity

A 2-additive Choquet integral model for french hospitals rankings in weight loss surgery

Necessary and possible interaction between criteria in a 2-additive Choquet integral model

Techniques for reading fuzzy measures (III): interaction index

A value for n-person games

A value for n-person games

Proof. Let i, j ∈ N . We suppose that j is p-dominated by i, i.e., there exists l 0 ∈ N \ {i, j} such that for all k ∈ N \ {i, j}, not(a jk T C a il0 ) and a il0 T C P a 0 .We add to the binary relation (P ∪ M ), another binary relation T on B defined by: for all x, y ∈ B,Since P is representable by a 2-additive Choquet integral, (P ∪ M ∪ T ) contains no strict cycle. Then there exists a partition {B 0 , B 1 , ..., B m } of B, build by using an appropriate topological sorting on (P ∪ M ∪ T ), as the one detailed in Sect. 5.2. of [7] .Therefore there exists p ∈ {1, ..., m} (since a il0 T C P a 0 ) such that a il0 ∈ B p and each element a jk , k ∈ N \{i, j} belongs to a set B q k with q k ∈ {0, ..., m}, q k < p. We have also a il0 (P ∪ M ) a i and a jk (P ∪ M ) a j . Hence a i ∈ B r , r < p and a j ∈ B r , r < p, r, r ∈ {0, ..., m}.Let us define the mapping f : B → R and μ : 2 N → [0, 1] as follows: For l ∈ {0, ..., m},whereThe capacity μ, defined like this, is 2-additive (see Proposition 7 in Sect. 5.3. of [7] ). Since p > r and p > p k , k ∈ N \ {i, j}, we have