PROMETHEE
This is a method from the family of outranking (i.e. based on pairwise 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 pairwise comparisons, it may become computationally very expensive
There are four steps:
 Compute UniCriterion Preferences
 Compute Preference Matrix
 Compute NetFlow Scores
 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$
UniCriterion 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 (predefined 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 unicriteria 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$
Net Flow Scores
For each $a_i, a_j \in A$ we compute net flow scores
 $\Phi^+(a_i) = \cfrac{1}{n1} \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}{n1} \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
Unicriteria flow
 flow computed with respect to only one criteria $f_k$
 $\Phi_k(a) = \cfrac{1}{n1} \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$
PROMETHEE respects the Preferential Independence hypothesis
Recall that according to the theorem all 5 conditions cannot be satisfied at the same time.
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}{n1} \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
$\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 DSight [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 2dim 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
Pairwise 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)
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