Outranking methods

A collective decision problem

For a ranking vote like this one

• 5 voters : x ≻ y ≻ z ≻ t
• 2 voters : t ≻ y ≻ x ≻ z
• 8 voters : z ≻ y ≻ x ≻ t
• 4 voters : x ≻ z ≻ y ≻ t
• 6 voters : t ≻ y ≻ z ≻ x
• 2 voters : t ≻ z ≻ y ≻ x

there are many ways to elect a candidate:

• Method 1: Number of votes placing a candidate in the first rank:
  • $t$ is elected
• Method 2: Two round ballot.
  • $x$ is elected
• Method 3: Sum of ranks (Borda 1770)
  • $y$ iselected
• Method 4: Condorcet’s rule (1785) with pairwise comparisons of candidates
  • $z$ is elected

Social choice vs Multicriteria decision

Social choice

• Each voter gives a ranking on candidates.
• The elected candidate should account for the point of view of all voters.
• Each voter has the same voting power (one vote).

Multicriteria decision

• Each criterion evaluates/compares alternatives.
• The final decision results from the information on all criteria.
• Criteria might not have the same importance

Multiple criteria Decision Analysis With what we have seen so far, we constructed two families of multicriteria methods, whose specificities lie in the order of operations: Aggregate then compare vs compare then aggregate:

TODO: Make table

• Synthesis criterion: Borda, multi-attribute value theory,…
  • aggregate then compare impose a strong structure on the preference model (difficult construction), simple exploitation.
• Pairwise comparaison: Condorcet, Outranking methods, …
  • compare then aggregate
    • Do not impose structure on the preference model (easy construction),
    • Difficult exploitation.

TODO: Central problem:

1. Outranking methods

1.1. Introduction

History Introduced by Bernard Roy et al. in the 1960s, outranking methods works in real application and prove useful in solving the difficulties encountered with a synthetic criterion (i.e. compensation and qualitative data).

TODO: Many methods have been proposed since: ELECTRE, PROMETHEE, TACTIC, …

Decision problems tackled Let us consider a finite set of alternatives $A = { a_{1}, …, a_{n} }$ and a family $F = { g_{1}, …, g_{p} }$ of $p$ criteria. Then, we are interested in tackling:

• Selection / choice
• Ranking
• Sorting / classification

Notion of pseudo-criterion

A pseudo criterion $g_{j}:A \mapsto \mathbb{R}$ with two threshold:

1. An indifference threshold q_{j}
2. A preference threshold p_{j}

such that:

TODO:

• Give intuition + image
• Precise special case:
  • $p_{j} = q_{j}$
  • $q_{j} = 0$
  • $p_{j} = q_{j} = 0$

1.2. Formalism

Concept of outranking relation

• $a$ outranks $b$ ($a \succeq b$) is valid if the arguments in favor of the proposition “$a$ is at least as good as $b$” are sufficiently strong.
• Arguments in favor of $a\succeq b$ are grounded on:
  • Evaluation of $a$ and $b$
  • Information preferences of the DM (weights, threshold)
• If no argument can be found in favor of $a\succeq b$ nor $b \succeq a$ then there is incomparability.

4 preference situations

TODO: Add image

Structure of outranking methods

The relation $\succeq$ has a few intersting properties:

• $a\Delta b \Rightarrow a \succeq b \forall a, b \in A$
• $\succeq$ is reflexive
• $\succeq$ is not necessarily transitive from Condorcet paradox

2. Contruction of outranking relations

Construction of outranking relations

$a \succeq b$ is valid iff two conditions are met:

• Concordance condition (majority principe): A majority of criteria should be in favor of $a \succeq b$.
• Non-discordance condition (respect of minorities): No criterion should strongly contradict $a \succeq b$.

These principles can be implemented in different ways and can impose weak (or stronger) requirements.

2.1. Concordance condition / majority

Concordance condition

Partial concordance: we consider the contribution of each criterion to $a \succeq b$

The partial correspondance index $c_{j}(a, b) \in [0, 1]\  \forall j$ is defined as such:

• $c_{j}(a, b) = 0 \Leftrightarrow g_{j}$ is not in favor of $a \succeq b$
• $c_{j}(a, b) = 1 \Leftrightarrow g_{j}$ fully agrees with $a \succeq b$
• $c_{j}(a, b) \in (0, 1) \Leftrightarrow g_{j}$ partially agrees with $a \succeq b$

This can be implemented as follows:

TODO: Understand the example

Overall concordance (majority)

Overall concordance evaluates the level of majority of criteria in favor of $a \succeq b$

Overall concordance $C (a, b) \in [0, 1]$ is such that:

• $C(a,b) = 0$ when no criterion is in favor of $a \succeq b$
• C(a,b) = 1 when all criteria are in favor of $a \succeq b$
• $C (a, b) \in ]0, 1[$ when some criteria are in favor of $a \succeq b$

which mathematically translates to:

with the weights being positive and normalized.

2.2. Non-discordance condition / veto

Non-discordance condition/Veto

Among criteria which disagree with $a \succeq b$, some can express a strong opposition, a veto which leads to invalidate $a \succeq b$.

On each criterion $g_{j}$, we define a veto threshold $v_{j}$ such that if $g_{j}(a)<g_{j}(b)−v_{j}$ for a given $j$, then $a \succeq b$ is invalidated (whatever the importance of the concordant coalition)

We define, on each criterion, a partial discordance index $d_{j} (a, b) \in [0, 1]$ such that:

• $d_{j}(a,b) = 0$ if $g_{j}$ does not oppose to $a \succeq b$.
• $d_{j}(a,b) = 1$ if $g_{j}$ fully opposes to $a \succeq b$.
• $d_{j}(a,b)\in]0,1[$ if $g_{j}$ partly opooses to $a \succeq b$.

Outranking relation (integrating concordance and non-discordance)

• In the Electre III method, a fuzzy outranking relation is defined: valued outranking $\sigma(a, b) \in [0, 1]$,
• If no discordant criterion exist $\sigma(a, b) = C (a, b)$,
• If one/several criteria is/are discordant $\sigma(a, b) < C (a, b)$,
• If $d_{j}(a,b) = 1$ for one criterion $\sigma(a,b) = 0$

We pose

with $\overline{F} = { j \in F: d_{j}(a, b) > C(a, b) }$

TODO:

• Taxonomy of ELECTRE algorithms
• Outranking relation in Electre IS

One/several outranking relation(s)

According to the considered method, one can construct:

• A unique outranking relation grounded on a requirement level fixed a priori, (Electre I, Electre IS)
• A fuzzy outranking relation $\succeq^{\sigma}$ defined by a a fuzzy membership function $\sigma$ (Electre III, Electre Tri),
• A set of embedded outranking relations $\succeq_{1}\subset \succeq_{2} \subset . . . \subset \succeq_{k}$ grounded on $k$ requirement levels fixed a priori (Electre II, Electre IV).

TODO: Give intuition

Representation of binary relations

A binary outranking relation $\succeq$ represented by an outranking graph $G = (X,U)$ avec :

• $X = A = {a_{1},a_{2},…,a_{n}}$
• $U={(a_{i},a_{j})\in X\times X$ such that $a_{i}\succeq a_{j}}$.

Valued outranking relation

Valued (fuzzy) outranking relation $\succeq^{\sigma}$ represented by a graph $G_{\sigma} = (A,U)$ valued by $\sigma(a_{i},a_{j})$.

TODO: Give intuition

Nested outranking relations

Several nested outranking relations $\succeq_{1}, \succeq_{2}, . . . , \succeq_{k}$ with $k$ graphs $G_{i} =(A, \succeq_{i})$, i =1,…,k:

• $\succeq_{1}\subseteq \succeq_{2}\subseteq … \subseteq \succeq_{k}$
• The weaker the requirement level, the richer the relation.

Nested relations $\succeq_{1}\subset \succeq_{2}\subset \succeq_{3}$

TODO: Add image

Exploiting outranking relations

According to the problem, we are looking to:

1. Select the smallest subset $A^{\text{}} \subset A$ of best alternatives → Choice set $A^{\text{}}$
2. Assign each alternative to a category by partitioning A:

1. Rank order the alternatives according to preferences on A pre-order (possibly partial) on A.

TODO: What is a preorder?

3. Exploitation - building recommandations

Construction de prescriptions Building recommendations/prescriptions

3.1. Exploitation for choice recommendation

3.2. Exploitation for sorting recommendation

3.3. Exploitation for ranking recommendation

Sources

• This blogpost is heavily inspired from Vincent Mousseau lectures, my professor at Centrale-Supélec.
• Layman intuition video