ML Wiki

PROMETHEE

This is a method from the family of outranking (i.e. based on pair-wise comparison) MCDA methods.

PROMETHEE stands for Preference Ranking Organization METHod for Enrichment Evaluation

Notation:

• $A = \{a_1, ..., a_n\}$ - set of alternatives
• $F = \{f_1, ..., f_q\}$ - set of criteria (assume we maximize everything)

Note that since we perform pair-wise comparisons, it may become computationally very expensive

There are four steps:

1. Compute Uni-Criterion Preferences
2. Compute Preference Matrix
3. Compute Net-Flow Scores
4. Rankings
   • Complete: PROMETHEE II
   • Partial: PROMETHEE I

Parameters for a problem (a decision maker needs to specify them)

• the type of preference function $P_k$ used for each criterion $f_k$
• weight $w_k$ for each criterion $f_k$

Uni-Criterion Preferences

we calculate the differences in all criteria for all pairs of alternatives:

• $\forall a_i, a_j \in A: d_k(a_i, a_j) = f_k(a_i) - f_k(a_j)$
• since we assume that we maximize everything, the bigger the difference, the better the first alternative is

The resulting value should be normalized:

• we apply a (pre-defined for each criteria $f_k$) preference function $P_k$ to each difference
• $\pi_k = P_k \big[ d_k(a_i, a_j) \big]$
• this transforms the difference into the preference degree

Preference Functions

There are 6 preference functions:

Basic Shapes

• (a) usual preference function
  • as soon as see any difference, the preference is 1
  • no need to specify any parameters
  • this function is very sensitive
• (b) $u$-shape function
  • difference needs to exceed a certain threshold $q$
  • (a) and (b) are typically used for qualitative scales
• (c) $v$-shape
  • with strong preference threshold $p$
• (d) level
• (e) linear
  • same as (c) but with sensitivity threshold $q$
  • 
• (f) $v$-shape

Choosing a shape is already a decision

Preference Matrix

At this step we compute global preference degrees

• that is, for each pair $a_i, a_j$ compute:
• $\pi(a_i, a_j) = \sum_{k=1}^q w_k \cdot \pi_k (a_i, a_j)$
• global preference degree is a weighted sum of uni-criteria preferences

Consequences:

• $\pi(a_i, a_i) = 0$
  • the preference of element $a$ with itself is always 0
  • $\pi(a_i, a_i) = \sum_{k=1}^q w_k \cdot \pi_k (a_i, a_i) = \sum_{k=1}^q w_k \cdot P_k \big[ \underbrace{d_k(a_i, a_i)}_{= \ 0} \big] = 0$
• $\pi(a_i, a_j) \geqslant 0$
  • the preference degree is always positive
  • $\pi(a_i, a_j)$ is a weighed sum of $\pi_k$ which are always positive
  • this is because the preference functions always return positive values
• $\pi(a_i, a_j) + \pi(a_j, a_i) \leqslant 1$
  • todo

Net Flow Scores

For each $a_i, a_j \in A$ we compute net flow scores

• $\Phi^+(a_i) = \cfrac{1}{n-1} \sum_{a_j \in A} \pi(a_i, a_j)$
  • positive outranking net flow
  • "strengths" of an alternative, how an alternative outranks others
  • want to maximize it
• $\Phi^-(a_i) = \cfrac{1}{n-1} \sum_{a_j \in A} \pi(a_j, a_a)$
  • negatives outranking net flow
  • "weaknesses" of an alternative, how an alternative is outranked by others
  • want to minimize it

The values are normalized:

• $\Phi^+(a_i) \in [0, 1]$ and
• $\Phi^-(a_i) \in [0, 1]$

The flow score is computed as difference between the positive flow and negative flow

• $\Phi(a_i) = \Phi^+(a_i) - \Phi^-(a_i) \in [-1, 1]$ and

Uni-criteria flow

• flow computed with respect to only one criteria $f_k$
• $\Phi_k(a) = \cfrac{1}{n-1} \sum_{b \in A} [ P_k(a, b) - P_k(b, a) ]$

Ranking

PROMETHEE I

Partial Order Ranking:

• ranking based only on $\Phi^+(a_i)$ and $\Phi^-(a_i)$ (not on the aggregated flow score)
• let $P^+$ denote the preference of $\Phi^+$
  • $a_i \ P^+ \ a_j \iff \Phi^+(a_i) > \Phi^+(a_j)$ (want to maximize $\Phi^+$)
• let $P^-$ denote the preference of $\Phi^-(a_i)$
  • $a_i \ P^- \ a_j \iff \Phi^+(a_i) < \Phi^+(a_j)$ (want to maximize $\Phi^-$)
• $a_i \ P \ a_j \iff a_i \ P^+ \ a_j \land a_i \ P^- \ a_j$
  • i.e. $a_i$ is preferred to $a_j$ only in case of Unanimity between $\Phi^+$ and $\Phi^-$
• if there is no unanimity, $a \ J \ b$
  • $a$ is not comparable to $b$
  • in this case it's up to the decision maker to decide what to do with these alternatives

PROMETHEE II

This gives a completely ordered preference structure

• i.e. there's no $J$ relation

Define:

• preference as $a_i \ P \ a_j \iff \Phi(a_i) > \Phi(a_j)$
• indifference as $a_i \ I \ a_j \iff \Phi(a_i) = \Phi(a_j)$

These relations are transitive and complete

Properties

Justification

The PROMETHEE property

• the netflow score $\Phi(a_i)$ is a centered score $s_i$ ($\forall i$) that minimizes the following $Q$:
• $Q = \sum_{i=1}^n \sum_{j=1}^n \big[ (s_i - s_j) - (\pi_{ij} - \pi_{ji}) \big]^2 $
• i.e. $Q$ is the sum of squared deviation and we want to minimize it
• proof: PROMETHEE/Properties#The PROMETHEE Property

Property 1

$\Phi(a_i) \in [-1, 1]$

Easy to see that by the way we construct $\Phi(a_i)$

Property 2

Want to show that $\sum_{i = 1}^N \Phi(a_i) = 0$

• $N$ - the number of alternatives
• that can be shown by induction
• proof: PROMETHEE/Properties#Property 2

Preferential Independence

PROMETHEE respects the Preferential Independence hypothesis

• PROMETHEE/Properties#Preferential Independence

Arrow's Impossibility Theorem

Recall that according to the theorem all 5 conditions cannot be satisfied at the same time.

• Independence to Third Alternatives, due to pair-wise comparisons is not respected (shown below in PROMETHEE/Rank Reversal)
• but it satisfies all the rest
• The Monotonicity property is satisfied PROMETHEE/Properties#Monotonicity

Rank Reversal

A rank reversal happens if:

• $\pi_{ij} \geqslant \pi_{ji}$ but in spite of that $\Phi(a_i) \leqslant \Phi(a_j)$
• the main article: PROMETHEE/Rank Reversal

GAIA

PROMETHEE gives you scores and you can compute complete and partial rankings

• GAIA is a tool for visualizing, complimentary to PROMETHEE
• GAIA = Geometrical Analysis for Interactive Assistance

We can represent each alternative as a vector:

• we can represent an alternative as a vector of $q$ components:
  • $[f_1(a_i), ..., f_q(a_i)]$
  • but in this space we have different scales - and things are not easy to compare
• we can use the netflow score, which is a value in $[-1, 1]$
  • $\Phi(a_i) = \sum_{k=1}^{q} w_k \cdot \phi_k(a_i)$
  • where $\Phi_k(a_i) = \cfrac{1}{n-1} \sum_{a_j \ne a_i} \big[ \pi_k(a_i, a_j) - \pi_k(a_j, a_i) \big] $
• so we can represent every alternative $a_i$ as a vector $[\Phi_1(a_i), ..., \Phi_k(a_i)]$ in $q$ dimensional space.

But $q$ dimensional space is really hard to visualize

• GAIA does that
• it applies Principal Component Analysis for projecting $q$-dim space to 2-dim space

$\delta$

• some information is lost during the projection, and the $\delta$ coefficient shows how much information is retained on the plane
• $\delta$ is the ratio between the projected variance and the initial variance
• $\delta \geqslant 70\%$ is good

Example

Consider a "Buying a new car" example (from D-Sight [1])

• points are alternatives
• lines with points at the end are criteria
• the red stick is a decision stick - the projection of weights to the plain

Based on a GAIA plane can make some observations:

• there are conflicting criteria: ones that point in the opposite directions
• there are also criteria that are in synergy: they point in the same direction
• 
• some criteria are close to each other in 2-dim space - they also must be close in the $q$-dim space, so they should have similar profiles
• 
• it is also interesting to see the position of alternatives with respect to criteria: to project each as see which one is the best, worst, etc
• 
• and finally, the projection on the decision stick vector shows what are the best alternatives
• 

Example: Plant Location Problem

Evaluation Table

First we establish the following evaluation table:

	# engineers	power	cost	maintenance	village	security
Italy	75	90	600	5.4	8	5
Belgium	65	58	200	9.7	1	1
Germany	83	60	400	7.2	4	7
Sweden	40	80	1000	7.5	7	10
Austria	52	72	600	2	3	8
France	94	96	3.6	5	6
	min	max	min	min	max	max

• red color - worst value in column
• blue color - best value in column

Pair-wise Comparison

• start with 2 alternatives and consider only 1 criteria at a time
• for example, $G$ermany and $A$ustria:
• cost is better in $G$: 400 vs 600
  • what does it mean?
  • need to normalize this difference to [0, 1] scale - to be able to qualify the difference

Unic. pref			0.25
			-200
Germany	83	60	400	7.2	4	7
	Engineers	Power	Cost	Maint.	Village	Security
Austria	52	72	600	2	3	8
	-31	12		-5.2	-1	1
Unic. pref	1	0.75		1	0.3	0.63

Global Preference Degree

Next step: compute global preference degree for all pairs of alternatives

• assuming a decision maker provides the weights
• eng: 0.1, pow: 0.2, cost: 0.2, maint: 0.1, village: 0.15, security: 0.15 (sum = 1)
• $\pi(A, G) = 1 \cdot 0.1 + 0.75 \cdot 02 + 1 \cdot 0.1 + 0.3 \cdot 0.15 + 0.63 \cdot 0.15 = 0.498$
• $\pi(G, A) = 0.25 \cdot 0.4 = 0.05$
• the closest the $\Pi$ value to 1, the move preferred one alternative to another is

We do this for all pairs and build a preference matrix

	Italy	Belgium	Germany	Sweden	Austria	France
Italy	0	0.28	0.23	0.24	0.09	0.22
Belgium	0.27	0	0.4	0.3	0.27	0.5
Germany	0.22	0.19	0	0.3	0.05	0.43
Sweden	0.43	0.55	0.33	0	0.25	0.25
Austria	0.46	0.55	0.49	0.34	0	0.46
France	0.23	0.4	0.26	0.39	0.12	0

Net Flow Scores

Next we compute the positive and negative net flow scores:

• positive flow: strengths, has to be maximized
• negative flow: weaknesses, has to be minimized

Then we calculate if on average $G$ is better than the rest:

• $\Phi^+(G) = 0.238$ (avg of all $\Pi(G, X)$)
• $\Phi^-(G) = 0.334$ (avg of all $\Pi(X, G)$)
• the total score: $\Phi(G) = \Phi^+(G) - \Phi^-(G) = -0.1 \in [-1, 1]$

PROMETHEE II ranking

ranking the alternatives based on their netflow scores

rank	alternative	$\Phi(G)$	$\Phi^+(G)$	$\Phi^-(G)$
1	Austria	0.302	0.458	0.156
2	Sweden	0.049	0.363	0.314
3	Belgium	-0.041	0.347	0.397
4	Germany	-0.096	0.238	0.334
5	France	-0.099	0.274	0.373
6	Italy	-0.115	2.11	0.326

Note that this is a complete ranking:

• you can always say which alternative is better

PROMETHEE I ranking

	$\Phi^+$	$\Phi^-$
$a$	0.8	0.1
$b$	0.5	0.05
$c$	0.1	0.8

for both $\Phi^+$ and $\Phi^-$ (applying the Unanimity principle)

• $a \ P \ c$
• $b \ P \ c$

Cannot say anything about $a$ and $c$

• for $\Phi^+$: $a \ P \ b$
• for $\Phi^-$: $b \ P \ a$

Sources

• Decision Engineering (ULB)
• An Introduction to Multicriteria Decision Aid: The PROMETHEE and GAIA Methods, Yves De Smet, Karim Lidouh, 2013