ELECTRE

multi-criteria-decision-aid

ELECTRE

This is a method from the family of outranking (i.e. based on pair-wise comparison) MCDA methods. The result is a partial ordering of alternatives (see Partial Order Preference Structure)

Here:

ELECTRE I

ELECTRE I chooses alternatives that are preferred by the majority of the criteria and which don;t cause an unacceptable level of discontentment on other criteria.

Preferences

; Main idea:

When we say $a \ P \ b$?

(1) if we have a lot of criteria for which $u_i(a) > u_i(b)$ (where $u_i$ - some utility function)
(2) and we have no strong arguments that say the opposite of (1)

The ELECTRE methods are based on two concepts:

Concordance Index
Discordance Index

Concordance Index

Or quantification of positive arguments

For ELECTRE 1, when comparing $a$ and $b$

identify all criteria $g_j$ such that $g_j(a) \geqslant g_j(b)$
for all such criteria $g_j$ sum their weights $w_j$,
let $W$ be the sum of all weights: $W = \sum_i w_i$ (we use this for normalization)
define the concordance index as:
: $c(a, b) = \cfrac{1}{W} \sum_{j: g_j(a) \geqslant g_j(b)} w_j$

Note that weight should sum up to 1

There are two extreme cases:

$c(a, b) = 1$: all criteria for $a$ are better than for $b$ (Unanimity)
- have very good reasons to say $a \ P \ b$
$c(a, b) = 0$: there is no criteria in which $a$ better than $b$

Discordance Index

Or quantification of negative arguments

We want to find a strong argument against $a \ P \ b$

if we find such an argument then we cannot say that $a \ P \ b$

For ELECTRE I, define $d(a, b)$ as

0 when $\forall j: g_j(a) \geqslant g_j(v)$ (none when there’s Unanimity)
if $\exists g_i: g_i(b) \geqslant g_i(a)$ then we have an argument against $a \ P \ b$
in this case we want to identify the largest difference between $a$ and $b$:
- $\cfrac{1}{\delta} \max_j [g_j(b) - g_j(a)]$
- $\delta$ is normalization factor: $\delta = \max_{i,c,d} [g_i(c) - g_i(d)]$

Another way

let $D$ be the set of cases where we list cases that cannot be compared
if for a pair of alternatives $(a, b)$ there exists a criteria $g_i$ s.t. $(g_i(a), g_i(b)) \in D$ then we cannot compare these alternatives

Outranking Preference Relation

For ELECTRE I we define $S \equiv P \lor I$ as: (the “as good as relations”, also see Voting Theory Relations)

$a \ S \ b \iff$
- (1) $c(a, b) \geqslant \tilde c$
- : a lot of positive arguments to say $a \ S \ b$
- (2) $d(a, b) \leqslant \tilde d$
- : not many negative arguments to say the opposite
so for that we also have to provide two parameters:
- $\tilde c$ - the ‘‘concordance threshold’’ and $\tilde d$ - the ‘‘discordance threshold’’

Or:

$a \ S \ b \iff$
- (1) $c(a, b) \geqslant \tilde c$
- (2) $\forall g_i: \big(g_i(a), g_i(b)\big) \not \in D$

Note that this relation gives us partial order:

we have $P$ and $I$ (expressed via $S$)
and we have $J$ (when discordance threshold is exceeded)

Graph Kernels

Graph Kernels are used to identify good alternatives.

It is possible to express the outranking relation $S$ in form of a directed graph

Example:

$a$ is better than $e$ and $d$
$d$ is better than $f$ and $c$
etc

A ‘‘kernel’’ of a graph $K \subset A$ is

$\forall a \in K, \not \exists b: a \ S \ b$
: no alternative $a$ inside the kernel $K$ is better than any other alternative $b$ inside $K$
$\forall a,b \in K: a \ ? \ b$
: within the kernel we cannot say anything about the relation between $a$ and $b$
$\forall c \not \in K, \exists a \in K: a \ S \ c$
: each alternative $c$ outside of the kernel $K$ is worse than at least one alternative $a$ inside $K$

For the example above:

$K = {b, d, e}$

Another example

Remarks:

If the graph has no cycles then the kernel is unique
Each cycle can be replaced by a single node (see Strongly Connected Components)

The kernel $K$ of a set $A$ forms a set of preferred alternatives.

Examples

Example 1

| | price | comfort | speed | aesthetic | | 1 | 300 | ex | fast | good | || 2 | 250 | ex | med | good | || 3 | 250 | med | fast | good | || 4 | 200 | med | fast | med | || 5 | 200 | med | med | good | || 7 | 100 | poor | med | med | || $w$ | 5 | 4 | 3 | 3 | $W = \sum w = 15$ |

Concordance

Perform pair-wise comparisons for all elements $A$

let’s compare (1) and (2)
concordance: $c(1, 2) = \cfrac{1}{15} (4 + 3 + 3) = \cfrac{2}{3}$

This way we compare each with each:

| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 1 | - | 10 | 10 | 10 | 10 | 10 | 10 || 2 | 12 | - | 12 | 7 | 10 | 7 | 10 || 3 | 11 | 11 | - | 10 | 10 | 10 | 10 || 4 | 8 | 8 | 12 | - | 12 | 12 | 10 || 5 | 8 | 11 | 12 | 12 | - | 12 | 10 || 6 | 11 | 11 | 11 | 11 | 11 | - | 10 || 7 | 5 | 8 | 5 | 8 | 8 | 9 | - | (note that this is not normalized - need also to divide on 15)

Discordance

In this case we define discordance by enumerating cases that are forbidden

The following tables shows what veto we define

price

comfort

$a$

250

poor

$b$

100

excellent

Graph

So the establish the following relation $S$ and the following graph:

There are two kernels in this case:

2, 4, 7
:
2, 5, 7
:

Kernel:

6 is dominated - remove it
same for 3 and 1
since there’s a cycle we have to decide between 4 and 5, and remove one of them
when we put alternatives into a kernel, it doesn’t mean they are the best, but it means it allows to apply the Dominance principle and remove dominated alternatives

Example 2

A company wants to rank 5 candidates $A,B,C,D,E$ for a promotion
Criteria:
- Reputation of diploma $D$
- Skills $K$
- Personality $P$
- Spoken Languages $L$
- Seniority $S$
Apply ELECTRE with concordance threshold 0.6 and discordance 6

The following evaluation table is obtained

| | $A$ | $B$ | $C$ | $D$ | $E$ | Weight | $D$ | 7 | 11 | 15 | 11 | 16 | 15 || $K$ | 12 | 18 | 6 | 8 | 10 | 15 || $P$ | 13 | 13 | 14 | 19 | 10 | 15 || $L$ | 18 | 16 | 19 | 13 | 19 | 25 || $S$ | 10 | 20 | 16 | 14 | 20 | 20 | Total weight is $W = 15 + 15 + 15 + 25 + 20 = 100$

Concordance

Then we construct the concordance index by comparing alternatives pair-wise

For example, consider alternatives $A$ and $B$

| | $A$ vs $B$ | $B$ vs $A$ | $D$ | | 15 || $K$ | | 15 || $P$ | 25 | 25 || $L$ | 25 | || $S$ | | 20 || ‘'’Total’’’ | 50 | 100 || ‘'’Normalized’’’ | 0.5 | 0.75 | Repeating this for all pairs, construct the following table:

$A$

$B$

$C$

$D$

$E$

$A$

’'’0.75’’’

0.15

0.4

$B$

0.5

0.35

’'’0.75’’’

’'’0.6’’’

$C$

’'’0.85’’’

’'’0.65’’’

’'’0.6’’’

0.5

$D$

’'’0.6’’’

0.25

0.4

0.25

$E$

’'’0.6’’’

’'’0.75’’’

’'’Bold’’’ are alternatives that should be preferred provided that there’s no discordance

recall that $\tilde c = 0.6$ and we check all values that $\geqslant \tilde c$

Discordance

The discordance index is $\tilde d = 6$

we don’t normalize on $\delta$ here because our values are already normalized

Let’s compare $A$ with $B$ and $A$ with $C$:

| | $A$ vs $B$ | $B$ vs $A$ | $A$ vs $C$ | $C$ vs $A$ | $D$ | 7 | - | ‘'’8’’’ | - || $K$ | 6 | - | - | ‘'’6’’’ || $P$ | 0 | 0 | 1 | - || $L$ | - | ‘'’2’’’ | 1 | - || $S$ | ‘'’10’’’ | - | 6 | - || ‘'’Max’’’ | ‘‘10’’ | 2 | ‘‘8’’ | ‘‘6’’ || Rel | $A \ J \ B$ | | $A \ J \ C$ | $C \ J \ A$ |

if a difference exceeds the threshold, the alternatives are incomparable

Graph

Based on the Concordance and Discordance we define the outranking relation $S$

this relation can be depicted as a graph

Sources

Decision Engineering (ULB)
http://web.itu.edu.tr/~topcuil/ya/MDM08Outranking.pptx
http://electre.no.sapo.pt/MElecI2.htm
Multiple Criteria Decision Analysis: State of the Art Surveys, 2005

✏️ Edit on GitHub