3. Advanced Topics
- Author:
Raymond Bisdorff, Emeritus Professor of Applied Mathematics and Computer Science, https://rbisdorff.github.io/
- Version:
Python 3.11 (release: 3.11.6)
- PDF version:
- Copyright:
R. Bisdorff 2013-2023
In this part of the Digraph3 documentation, we provide an insight in computational enhancements one may get when working in a bipolar-valued epistemic logic framework, like - easily coping with missing data and uncertain criterion significance weights, - computing valued ordinal correlations between bipolar-valued outranking digraphs, - computing digraph kernels and solving bipolar-valued kernel equation systems and, - testing for stability and confidence of outranking statements when facing uncertain performance criteria significance weights or decision objectives’ importance weights.
Contents
- Enhancing the outranking based MCDA approach
- Enhancing social choice procedures
- Theoretical advancements
3.1. Enhancing the outranking based MCDA approach
“The goal of our research was to design a resolution method [..] that is easy to put into practice, that requires as few and reliable hypotheses as possible, and that meets the needs [of the decision maker].”
—Benayoun R, Roy B, Sussmann B [13]
3.1.1. Coping with missing data and indeterminateness
In a stubborn keeping with a two-valued logic, where every argument can only be true or false, there is no place for efficiently taking into account missing data or logical indeterminateness. These cases are seen as problematic and, at best are simply ignored. Worst, in modern data science, missing data get often replaced with fictive values, potentially falsifying hence all subsequent computations.
In social choice problems like elections, abstentions are, however, frequently observed and represent a social expression that may be significant for revealing non represented social preferences.
In marketing studies, interviewees will not always respond to all the submitted questions. Again, such abstentions do sometimes contain nevertheless valid information concerning consumer preferences.
3.1.1.1. A motivating data set
Let us consider such a performance tableau in file graffiti07.py gathering a Movie Magazine ‘s rating of some movies that could actually be seen in town [1] (see Fig. 3.1).
1>>> from outrankingDigraphs import *
2>>> t = PerformanceTableau('graffiti07')
3>>> t.showHTMLPerformanceTableau(title='Graffiti Star wars',
4... ndigits=0)
15 journalists and movie critics provide here their rating of 25 movies: 5 stars (masterpiece), 4 stars (must be seen), 3 stars (excellent), 2 stars (good), 1 star (could be seen), -1 star (I do not like), -2 (I hate), NA (not seen).
To aggregate all the critics’ rating opinions, the Graffiti magazine provides for each movie a global score computed as an average grade, just ignoring the not seen data. These averages are thus not computed on comparable denominators; some critics do indeed use a more or less extended range of grades. The movies not seen by critic SJ, for instance, are favored, as this critic is more severe than others in her grading. Dropping the movies that were not seen by all the critics is here not possible either, as no one of the 25 movies was actually seen by all the critics. Providing any value for the missing data will as well always somehow falsify any global value scoring. What to do ?
A better approach is to rank the movies on the basis of pairwise bipolar-valued at least as well rated as opinions. Under this epistemic argumentation approach, missing data are naturally treated as opinion abstentions and hence do not falsify the logical computations. Such a ranking (see the tutorial on Ranking with incommensurable performance criteria) of the 25 movies is provided, for instance, by the heat map view shown in Fig. 3.2.
>>> t.showHTMLPerformanceHeatmap(Correlations=True,
... rankingRule='NetFlows',
... ndigits=0)
There is no doubt that movie mv_QS, with 6 ‘must be seen’ marks, is correctly best-ranked and the movie mv_TV is worst-ranked with five ‘don’t like’ marks.
3.1.1.2. Modelling pairwise bipolar-valued rating opinions
Let us explicitly construct the underlying bipolar-valued outranking digraph and consult in Fig. 3.3 the pairwise characteristic values we observe between the two best-ranked movies, namely mv_QS and mv_RR.
1>>> g = BipolarOutrankingDigraph(t)
2>>> g.recodeValuation(-19,19) # integer characteristic values
3>>> g.showHTMLPairwiseOutrankings('mv_QS','mv_RR')
Six out of the fifteen critics have not seen one or the other of these two movies. Notice the higher significance (3) that is granted to two locally renowned movie critics, namely JH and VT. Their opinion counts for three times the opinion of the other critics. All nine critics that have seen both movies, except critic MR, state that mv_QS is rated at least as well as mv_RR and the balance of positive against negative opinions amounts to +11, a characteristic value which positively validates the outranking situation with a majority of (11/19 + 1.0) / 2.0 = 79%.
The complete table of pairwise majority margins of global ‘at least as well rated as’ opinions, ranked by the same rule as shown in the heat map above (see Fig. 3.2), may be shown in Fig. 3.4.
1>>> ranking = g.computeNetFlowsRanking()
2>>> g.showHTMLRelationTable(actionsList=ranking, ndigits=0,
3... tableTitle='Bipolar characteristic values of\
4... "rated at least as good as" situations')
Positive characteristic values, validating a global ‘at least as well rated as’ opinion are marked in light green (see Fig. 3.4). Whereas negative characteristic values, invalidating such a global opinion, are marked in light red. We may by the way notice that the best-ranked movie mv_QS is indeed a Condorcet winner, i.e. better rated than all the other movies by a 65% majority of critics. This majority may be assessed from the average determinateness of the given bipolar-valued outranking digraph g.
>>> print( '%.0f%%' % g.computeDeterminateness(InPercents=True) )
65%
Notice also the indeterminate situation we observe, for instance, when comparing movie mv_PE with movie mv_NP.
>>> g.showHTMLPairwiseComparison('mv_PE','mv_NP')
Only eight, out of the fifteen critics, have seen both movies and the positive opinions do neatly balance the negative ones. A global statement that mv_PE is ‘at least as well rated as’ mv_NP may in this case hence neither be validated, nor invalidated; a preferential situation that cannot be modelled with any scoring approach.
It is fair, however, to eventually mention here that the Graffiti magazine’s average scoring method is actually showing a very similar ranking. Indeed, average scores usually confirm well all evident pairwise comparisons, yet enforce comparability for all less evident ones.
Notice finally the ordinal correlation tau values in Fig. 3.2 3rd row. How may we compute these ordinal correlation indexes ?
Back to Content Table
3.1.2. On confident outrankings with uncertain criteria significance weights
When modelling preferences following the outranking approach, the signs of the majority margins do sharply distribute validation and invalidation of pairwise outranking situations. How can we be confident in the resulting outranking digraph, when we acknowledge the usual imprecise knowledge of criteria significance weights coupled with small majority margins?
To answer this question, one usually requires qualified majority margins for confirming outranking situations. But how to choose such a qualifying majority level: two third, three fourth of the significance weights ?
In this tutorial we propose to link the qualifying significance majority with a required alpha%-confidence level. We model therefore the significance weights as random variables following more or less widespread distributions around an average significance value that corresponds to the given deterministic weight. As the bipolar-valued random credibility of an outranking statement hence results from the simple sum of positive or negative independent random variables, we may apply the Central Limit Theorem (CLT) for computing the bipolar likelihood that the expected majority margin will indeed be positive, respectively negative.
3.1.2.1. Modelling uncertain criteria significance weights
Let us consider the significance weights of a family F of m criteria to be independent random variables Wj, distributing the potential significance weights of each criterion j = 1, …, m around a mean value E(Wj) with variance V(Wj).
Choosing a specific stochastic model of uncertainty is usually application specific. In the limited scope of this tutorial, we will illustrate the consequence of this design decision on the resulting outranking modelling with four slightly different models for taking into account the uncertainty with which we know the numerical significance weights: uniform, triangular, and two models of Beta laws, one more widespread and, the other, more concentrated.
When considering, for instance, that the potential range of a significance weight is distributed between 0 and two times its mean value, we obtain the following random variates:
A continuous uniform distribution on the range 0 to 2E(Wj). Thus Wj ~ U(0, 2E(Wj)) and V(Wj) = 1/3(E(Wj))^2;
A symmetric beta distribution with, for instance, parameters alpha = 2 and beta = 2. Thus, Wi ~ Beta(2,2) * 2E(Wj) and V(Wj) = 1/5(E(Wj))^2.
A symmetric triangular distribution on the same range with mode E(Wj). Thus Wj ~ Tr(0, 2E(Wj), E(Wj)) with V(Wj) = 1/6(E(Wj))^2;
A narrower beta distribution with for instance parameters alpha = 4 and beta = 4. Thus Wj ~ Beta(4,4) * 2E(Wj) , V(Wj) = 1/9(E(Wj))^2.
It is worthwhile noticing that these four uncertainty models all admit the same expected value, E(Wj), however, with a respective variance which goes decreasing from 1/3, to 1/9 of the square of E(W) (see Fig. 3.6).
3.1.2.2. Bipolar-valued likelihood of ‘’at least as good as “ situations
Let A = {x, y, z,…} be a finite set of n potential decision actions, evaluated on F = {1,…, m}, a finite and coherent family of m performance criteria. On each criterion j in F, the decision actions are evaluated on a real performance scale [0; Mj ], supporting an upper-closed indifference threshold indj and a lower-closed preference threshold prj such that 0 <= indj < prj <= Mj. The marginal performance of object x on criterion j is denoted xj. Each criterion j is thus characterising a marginal double threshold order on A (see Fig. 3.7):
- Semantics of the marginal bipolar-valued characteristic function:
+1 signifies x is performing at least as good as y on criterion j,
-1 signifies that x is not performing at least as good as y on criterion j,
0 signifies that it is unclear whether, on criterion j, x is performing at least as good as y.
Each criterion j in F contributes the random significance Wj of his ‘at least as good as’ characteristic to the global characteristic in the following way:
Thus, becomes a simple sum of positive or negative independent random variables with known means and variances where signifies x is globally performing at least as good as y, signifies that x is not globally performing at least as good as y, and signifies that it is unclear whether x is globally performing at least as good as y.
From the Central Limit Theorem (CLT), we know that such a sum of random variables leads, with m getting large, to a Gaussian distribution Y with
, and
.
And the likelihood of validation, respectively invalidation of an ‘at least as good as’ situation, denoted , may hence be assessed by the probability P(Y>0) = 1.0 - P(Y<=0) that Y takes a positive, resp. P(Y<0) takes a negative value. In the bipolar-valued case here, we can judiciously make usage of the standard Gaussian error function , i.e. the bipolar 2P(Z) - 1.0 version of the standard Gaussian P(Z) probability distribution function:
The range of the bipolar-valued hence becomes [-1.0;+1.0], and , i.e. a negative likelihood represents the likelihood of the correspondent negated ‘at least as good as’ situation. A likelihood of +1.0 (resp. -1.0) means the corresponding preferential situation appears certainly validated (resp. invalidated).
Example
Let x and y be evaluated wrt 7 equisignificant criteria; Four criteria positively support that x is as least as good performing than y and three criteria support that x is not at least as good performing than y. Suppose E(Wj) = w for j = 1,…,7 and Wj ~ Tr(0, 2w, w) for j = 1,…7. The expected value of the global ‘at least as good as’ characteristic value becomes: with a variance .
If w = 1, and . By the CLT, the bipolar likelihood of the at least as good performing situation becomes: , which corresponds to a global support of (0.66 + 1.0)/2 = 83% of the criteria significance weights.
A Monte Carlo simulation with 10 000 runs empirically confirms the effective convergence to a Gaussian (see Fig. 3.8 realised with gretl [4] ).
Indeed, , with an empirical probability of observing a negative majority margin of about 17%.
3.1.2.3. Confidence level of outranking situations
Now, following the classical outranking approach (see [BIS-2013p] ), we may say, from an epistemic perspective, that decision action x outranks decision action y at confidence level alpha %, when
an expected majority of criteria validates, at confidence level alpha % or higher, a global ‘at least as good as’ situation between x and y, and
no considerably less performing is observed on a discordant criterion.
Dually, decision action x does not outrank decision action y at confidence level alpha %, when
an expected majority of criteria at confidence level alpha % or higher, invalidates a global ‘at least as good as’ situation between x and y, and
no considerably better performing situation is observed on a concordant criterion.
Time for a coded example
Let us consider the following random performance tableau.
1>>> from randomPerfTabs import RandomPerformanceTableau
2>>> t = RandomPerformanceTableau(
3... numberOfActions=7,
4... numberOfCriteria=7,seed=100)
5
6>>> t.showPerformanceTableau(Transposed=True)
7 *---- performance tableau -----*
8 criteria | weights | 'a1' 'a2' 'a3' 'a4' 'a5' 'a6' 'a7'
9 ---------|------------------------------------------------------------
10 'g1' | 1 | 15.17 44.51 57.87 58.00 24.22 29.10 96.58
11 'g2' | 1 | 82.29 43.90 NA 35.84 29.12 34.79 62.22
12 'g3' | 1 | 44.23 19.10 27.73 41.46 22.41 21.52 56.90
13 'g4' | 1 | 46.37 16.22 21.53 51.16 77.01 39.35 32.06
14 'g5' | 1 | 47.67 14.81 79.70 67.48 NA 90.72 80.16
15 'g6' | 1 | 69.62 45.49 22.03 33.83 31.83 NA 48.80
16 'g7' | 1 | 82.88 41.66 12.82 21.92 75.74 15.45 6.05
For the corresponding confident outranking digraph, we require a confidence level of alpha = 90%. The ConfidentBipolarOutrankingDigraph
class provides such a construction.
1>>> from outrankingDigraphs import\
2... ConfidentBipolarOutrankingDigraph
3
4>>> g90 = ConfidentBipolarOutrankingDigraph(t,confidence=90)
5>>> print(g90)
6 *------- Object instance description ------*
7 Instance class : ConfidentBipolarOutrankingDigraph
8 Instance name : rel_randomperftab_CLT
9 # Actions : 7
10 # Criteria : 7
11 Size : 15
12 Uncertainty model : triangular(a=0,b=2w)
13 Likelihood domain : [-1.0;+1.0]
14 Confidence level : 0.80 (90.0%)
15 Confident majority : 0.14 (57.1%)
16 Determinateness (%) : 62.07
17 Valuation domain : [-1.00;1.00]
18 Attributes : ['name', 'bipolarConfidenceLevel',
19 'distribution', 'betaParameter', 'actions',
20 'order', 'valuationdomain', 'criteria',
21 'evaluation', 'concordanceRelation',
22 'vetos', 'negativeVetos',
23 'largePerformanceDifferencesCount',
24 'likelihoods', 'confidenceCutLevel',
25 'relation', 'gamma', 'notGamma']
The resulting 90% confident expected outranking relation is shown below.
1>>> g90.showRelationTable(LikelihoodDenotation=True)
2 * ---- Outranking Relation Table -----
3 r/(lh) | 'a1' 'a2' 'a3' 'a4' 'a5' 'a6' 'a7'
4 -------|------------------------------------------------------------
5 'a1' | +0.00 +0.71 +0.29 +0.29 +0.29 +0.29 +0.00
6 | ( - ) (+1.00) (+0.95) (+0.95) (+0.95) (+0.95) (+0.65)
7 'a2' | -0.71 +0.00 -0.29 +0.00 +0.00 +0.29 -0.57
8 |(-1.00) ( - ) (-0.95) (-0.65) (+0.73) (+0.95) (-1.00)
9 'a3' | -0.29 +0.29 +0.00 -0.29 +0.00 +0.00 -0.29
10 |(-0.95) (+0.95) ( - ) (-0.95) (-0.73) (-0.00) (-0.95)
11 'a4' | +0.00 +0.00 +0.57 +0.00 +0.29 +0.57 -0.43
12 |(-0.00) (+0.65) (+1.00) ( - ) (+0.95) (+1.00) (-0.99)
13 'a5' | -0.29 +0.00 +0.00 +0.00 +0.00 +0.29 -0.29
14 |(-0.95) (-0.00) (+0.73) (-0.00) ( - ) (+0.99) (-0.95)
15 'a6' | -0.29 +0.00 +0.00 -0.29 +0.00 +0.00 +0.00
16 |(-0.95) (-0.00) (+0.73) (-0.95) (+0.73) ( - ) (-0.00)
17 'a7' | +0.00 +0.71 +0.57 +0.43 +0.29 +0.00 +0.00
18 |(-0.65) (+1.00) (+1.00) (+0.99) (+0.95) (-0.00) ( - )
19 Valuation domain : [-1.000; +1.000]
20 Uncertainty model : triangular(a=2.0,b=2.0)
21 Likelihood domain : [-1.0;+1.0]
22 Confidence level : 0.80 (90.0%)
23 Confident majority : 0.14 (57.1%)
24 Determinateness : 0.24 (62.1%)
The (lh) figures, indicated in the table above, correspond to bipolar likelihoods and the required bipolar confidence level equals (0.90+1.0)/2 = 0.80 (see Line 22 above). Action ‘a1’ thus confidently outranks all other actions, except ‘a7’ where the actual likelihood (+0.65) is lower than the required one (0.80) and we furthermore observe a considerable counter-performance on criterion ‘g1’.
Notice also the lack of confidence in the outranking situations we observe between action ‘a2’ and actions ‘a4’ and ‘a5’. In the deterministic case we would have and . All outranking situations with a characteristic value lower or equal to abs(0.143), i.e. a majority support of 1.143/2 = 57.1% and less, appear indeed to be not confident at level 90% (see Line 23 above).
We may draw the corresponding strict 90%-confident outranking digraph, oriented by its initial and terminal strict prekernels (see Fig. 3.9).
1>>> gcd90 = ~ (-g90)
2>>> gcd90.showPreKernels()
3 *--- Computing preKernels ---*
4 Dominant preKernels :
5 ['a1', 'a7']
6 independence : 0.0
7 dominance : 0.2857
8 absorbency : -0.7143
9 covering : 0.800
10 Absorbent preKernels :
11 ['a2', 'a5', 'a6']
12 independence : 0.0
13 dominance : -0.2857
14 absorbency : 0.2857
15 covered : 0.583
16>>> gcd90.exportGraphViz(fileName='confidentOutranking',
17... firstChoice=['a1', 'a7'],lastChoice=['a2', 'a5', 'a6'])
18
19 *---- exporting a dot file for GraphViz tools ---------*
20 Exporting to confidentOutranking.dot
21 dot -Grankdir=BT -Tpng confidentOutranking.dot -o confidentOutranking.png
Now, what becomes this 90%-confident outranking digraph when we require a stronger confidence level of, say 99% ?
1>>> g99 = ConfidentBipolarOutrankingDigraph(t,confidence=99)
2>>> g99.showRelationTable()
3 * ---- Outranking Relation Table -----
4 r/(lh) | 'a1' 'a2' 'a3' 'a4' 'a5' 'a6' 'a7'
5 -------|------------------------------------------------------------
6 'a1' | +0.00 +0.71 +0.00 +0.00 +0.00 +0.00 +0.00
7 | ( - ) (+1.00) (+0.95) (+0.95) (+0.95) (+0.95) (+0.65)
8 'a2' | -0.71 +0.00 +0.00 +0.00 +0.00 +0.00 -0.57
9 | (-1.00) ( - ) (-0.95) (-0.65) (+0.73) (+0.95) (-1.00)
10 'a3' | +0.00 +0.00 +0.00 +0.00 +0.00 +0.00 +0.00
11 | (-0.95) (+0.95) ( - ) (-0.95) (-0.73) (-0.00) (-0.95)
12 'a4' | +0.00 +0.00 +0.57 +0.00 +0.00 +0.57 -0.43
13 | (-0.00) (+0.65) (+1.00) ( - ) (+0.95) (+1.00) (-0.99)
14 'a5' | +0.00 +0.00 +0.00 +0.00 +0.00 +0.29 +0.00
15 | (-0.95) (-0.00) (+0.73) (-0.00) ( - ) (+0.99) (-0.95)
16 'a6' | +0.00 +0.00 +0.00 +0.00 +0.00 +0.00 +0.00
17 | (-0.95) (-0.00) (+0.73) (-0.95) (+0.73) ( - ) (-0.00)
18 'a7' | +0.00 +0.71 +0.57 +0.43 +0.00 +0.00 +0.00
19 | (-0.65) (+1.00) (+1.00) (+0.99) (+0.95) (-0.00) ( - )
20 Valuation domain : [-1.000; +1.000]
21 Uncertainty model : triangular(a=2.0,b=2.0)
22 Likelihood domain : [-1.0;+1.0]
23 Confidence level : 0.98 (99.0%)
24 Confident majority : 0.29 (64.3%)
25 Determinateness : 0.13 (56.6%)
At 99% confidence, the minimal required significance majority support amounts to 64.3% (see Line 24 above). As a result, most outranking situations don’t get anymore validated, like the outranking situations between action ‘a1’ and actions ‘a3’, ‘a4’, ‘a5’ and ‘a6’ (see Line 5 above). The overall epistemic determination of the digraph consequently drops from 62.1% to 56.6% (see Line 25).
Finally, what becomes the previous 90%-confident outranking digraph if the uncertainty concerning the criteria significance weights is modelled with a larger variance, like uniform variates (see Line 2 below).
1>>> gu90 = ConfidentBipolarOutrankingDigraph(t,
2... confidence=90,distribution='uniform')
3
4>>> gu90.showRelationTable()
5 * ---- Outranking Relation Table -----
6 r/(lh) | 'a1' 'a2' 'a3' 'a4' 'a5' 'a6' 'a7'
7 -------|------------------------------------------------------------
8 'a1' | +0.00 +0.71 +0.29 +0.29 +0.29 +0.29 +0.00
9 | ( - ) (+1.00) (+0.84) (+0.84) (+0.84) (+0.84) (+0.49)
10 'a2' | -0.71 +0.00 -0.29 +0.00 +0.00 +0.29 -0.57
11 | (-1.00) ( - ) (-0.84) (-0.49) (+0.56) (+0.84) (-1.00)
12 'a3' | -0.29 +0.29 +0.00 -0.29 +0.00 +0.00 -0.29
13 | (-0.84) (+0.84) ( - ) (-0.84) (-0.56) (-0.00) (-0.84)
14 'a4' | +0.00 +0.00 +0.57 +0.00 +0.29 +0.57 -0.43
15 | (-0.00) (+0.49) (+1.00) ( - ) (+0.84) (+1.00) (-0.95)
16 'a5' | -0.29 +0.00 +0.00 +0.00 +0.00 +0.29 -0.29
17 | (-0.84) (-0.00) (+0.56) (-0.00) ( - ) (+0.92) (-0.84)
18 'a6' | -0.29 +0.00 +0.00 -0.29 +0.00 +0.00 +0.00
19 | (-0.84) (-0.00) (+0.56) (-0.84) (+0.56) ( - ) (-0.00)
20 'a7' | +0.00 +0.71 +0.57 +0.43 +0.29 +0.00 +0.00
21 | (-0.49) (+1.00) (+1.00) (+0.95) (+0.84) (-0.00) ( - )
22 Valuation domain : [-1.000; +1.000]
23 Uncertainty model : uniform(a=2.0,b=2.0)
24 Likelihood domain : [-1.0;+1.0]
25 Confidence level : 0.80 (90.0%)
26 Confident majority : 0.14 (57.1%)
27 Determinateness : 0.24 (62.1%)
Despite lower likelihood values (see the g90 relation table above), we keep the same confident majority level of 57.1% (see Line 25 above) and, hence, also the same 90%-confident outranking digraph.
Note
For concluding, it is worthwhile noticing again that it is in fact the neutral value of our bipolar-valued epistemic logic that allows us to easily handle alpha% confidence or not of outranking situations when confronted with uncertain criteria significance weights. Remarkable furthermore is the usage, the standard Gaussian error function (erf) provides by delivering signed likelihood values immediately concerning either a positive relational statement, or when negative, its negated version.
Back to Content Table
3.1.3. On stable outrankings with ordinal criteria significance weights
3.1.3.1. Cardinal or ordinal criteria significance weights
The required cardinal significance weights of the performance criteria represent the Achilles’ heel of the outranking approach. Rarely will indeed a decision maker be cognitively competent for suggesting precise decimal-valued criteria significance weights. More often, the decision problem will involve more or less equally important decision objectives with more or less equi-significant criteria. A random example of such a decision problem may be generated with the Random3ObjectivesPerformanceTableau
class.
1>>> from randomPerfTabs import \
2... Random3ObjectivesPerformanceTableau
3
4>>> t = Random3ObjectivesPerformanceTableau(
5... numberOfActions=7,
6... numberOfCriteria=9,seed=102)
7
8>>> t
9 *------- PerformanceTableau instance description ------*
10 Instance class : Random3ObjectivesPerformanceTableau
11 Seed : 102
12 Instance name : random3ObjectivesPerfTab
13 # Actions : 7
14 # Objectives : 3
15 # Criteria : 9
16 Attributes : ['name', 'valueDigits', 'BigData', 'OrdinalScales',
17 'missingDataProbability', 'negativeWeightProbability',
18 'randomSeed', 'sumWeights', 'valuationPrecision',
19 'commonScale', 'objectiveSupportingTypes', 'actions',
20 'objectives', 'criteriaWeightMode', 'criteria',
21 'evaluation', 'weightPreorder']
22>>> t.showObjectives()
23 *------ show objectives -------"
24 Eco: Economical aspect
25 ec1 criterion of objective Eco 8
26 ec4 criterion of objective Eco 8
27 ec8 criterion of objective Eco 8
28 Total weight: 24.00 (3 criteria)
29 Soc: Societal aspect
30 so2 criterion of objective Soc 12
31 so7 criterion of objective Soc 12
32 Total weight: 24.00 (2 criteria)
33 Env: Environmental aspect
34 en3 criterion of objective Env 6
35 en5 criterion of objective Env 6
36 en6 criterion of objective Env 6
37 en9 criterion of objective Env 6
38 Total weight: 24.00 (4 criteria)
In this example (see Listing 3.1), we face seven decision alternatives that are assessed with respect to three equally important decision objectives concerning: first, an economical aspect (Line 24) with a coalition of three performance criteria of significance weight 8, secondly, a societal aspect (Line 29) with a coalition of two performance criteria of significance weight 12, and thirdly, an environmental aspect (Line 33) with a coalition four performance criteria of significance weight 6.
The question we tackle is the following: How dependent on the actual values of the significance weights appears the corresponding bipolar-valued outranking digraph ? In the previous section, we assumed that the criteria significance weights were random variables. Here, we shall assume that we know for sure only the preordering of the significance weights. In our example we see indeed three increasing weight equivalence classes (Listing 3.2).
1>>> t.showWeightPreorder()
2 ['en3', 'en5', 'en6', 'en9'] (6) <
3 ['ec1', 'ec4', 'ec8'] (8) <
4 ['so2', 'so7'] (12)
How stable appear now the outranking situations when assuming only ordinal significance weights?
3.1.3.2. Qualifying the stability of outranking situations
Let us construct the normalized bipolar-valued outranking digraph corresponding with the previous 3 Objectives performance tableau t.
1>>> from outrankingDigraphs import BipolarOutrankingDigraph
2>>> g = BipolarOutrankingDigraph(t,Normalized=True)
3>>> g.showRelationTable()
4 * ---- Relation Table -----
5 r(>=) | 'p1' 'p2' 'p3' 'p4' 'p5' 'p6' 'p7'
6 ------|------------------------------------------------
7 'p1' | +1.00 -0.42 +0.00 -0.69 +0.39 +0.11 -0.06
8 'p2' | +0.58 +1.00 +0.83 +0.00 +0.58 +0.58 +0.58
9 'p3' | +0.25 -0.33 +1.00 +0.00 +0.50 +1.00 +0.25
10 'p4' | +0.78 +0.00 +0.61 +1.00 +1.00 +1.00 +0.67
11 'p5' | -0.11 -0.50 -0.25 -0.89 +1.00 +0.11 -0.14
12 'p6' | +0.22 -0.42 +0.00 -1.00 +0.17 +1.00 -0.11
13 'p7' | +0.22 -0.50 +0.17 -0.06 +0.78 +0.42 +1.00
We notice on the principal diagonal, the certainly validated reflexive terms +1.00 (see Listing 3.3 Lines 7-13). Now, we know for sure that unanimous outranking situations are completely independent of the significance weights. Similarly, all outranking situations that are supported by a majority significance in each coalition of equi-significant criteria are also in fact independent of the actual importance we attach to each individual criteria coalition. But we are also able to test (see [BIS-2014p]) if an outranking situation is independent of all the potential significance weights that respect the given preordering of the weights. Mind that there are, for sure, always outranking situations that are indeed dependent on the very values we allocate to the criteria significance weights.
Such a stability denotation of outranking situations is readily available with the common showRelationTable()
method.
1>>> g.showRelationTable(StabilityDenotation=True)
2* ---- Relation Table -----
3r/(stab) | 'p1' 'p2' 'p3' 'p4' 'p5' 'p6' 'p7'
4----------|------------------------------------------
5 'p1' | +1.00 -0.42 +0.00 -0.69 +0.39 +0.11 -0.06
6 | (+4) (-2) (+0) (-3) (+2) (+2) (-1)
7 'p2' | +0.58 +1.00 +0.83 0.00 +0.58 +0.58 +0.58
8 | (+2) (+4) (+3) (+2) (+2) (+2) (+2)
9 'p3' | +0.25 -0.33 +1.00 0.00 +0.50 +1.00 +0.25
10 | (+2) (-2) (+4) (0) (+2) (+2) (+1)
11 'p4' | +0.78 0.00 +0.61 +1.00 +1.00 +1.00 +0.67
12 | (+3) (-1) (+3) (+4) (+4) (+4) (+2)
13 'p5' | -0.11 -0.50 -0.25 -0.89 +1.00 +0.11 -0.14
14 | (-2) (-2) (-2) (-3) (+4) (+2) (-2)
15 'p6' | +0.22 -0.42 0.00 -1.00 +0.17 +1.00 -0.11
16 | (+2) (-2) (+1) (-2) (+2) (+4) (-2)
17 'p7' | +0.22 -0.50 +0.17 -0.06 +0.78 +0.42 +1.00
18 | (+2) (-2) (+1) (-1) (+3) (+2) (+4)
- We may thus distinguish the following bipolar-valued stability levels:
+4 | -4 : unanimous outranking | outranked situation. The pairwise trivial reflexive outrankings, for instance, all show this stability level;
+3 | -3 : validated outranking | outranked situation in each coalition of equisignificant criteria. This is, for instance, the case for the outranking situation observed between alternatives p1 and p4 (see Listing 3.4 Lines 6 and 12);
+2 | -2 : outranking | outranked situation validated with all potential significance weights that are compatible with the given significance preorder (see Listing 3.2. This is case for the comparison of alternatives p1 and p2 (see Listing 3.4 Lines 6 and 8);
+1 | -1 : validated outranking | outranked situation with the given significance weights, a situation we may observe between alternatives p3 and p7 (see Listing 3.4 Lines 10 and 16);
0 : indeterminate relational situation, like the one between alternatives p1 and p3 (see Listing 3.4 Lines 6 and 10).
It is worthwhile noticing that, in the one limit case where all performance criteria appear equi-significant, i.e. there is given a single equivalence class containing all the performance criteria, we may only distinguish stability levels +4 and +3 (rep. -4 and -3). Furthermore, when in such a case an outranking (resp. outranked) situation is validated at level +3 (resp. -3), no potential preordering of the criteria significance weights exists that could qualify the same situation as outranked (resp. outranking) at level -2 (resp. +2).
In the other limit case, when all performance criteria admit different significance weights, i.e. the significance weights may be linearly ordered, no stability level +3 or -3 may be observed.
As mentioned above, all reflexive comparisons confirm an unanimous outranking situation: all decision alternatives are indeed trivially as well performing as themselves. But there appear also two non reflexive unanimous outranking situations: when comparing, for instance, alternative p4 with alternatives p5 and p6 (see Listing 3.4 Lines 14 and 16).
Let us inspect the details of how alternatives p4 and p5 compare.
1>>> g.showPairwiseComparison('p4','p5')
2 *------------ pairwise comparison ----*
3 Comparing actions : (p4, p5)
4 crit. wght. g(x) g(y) diff | ind pref r() |
5 ec1 8.00 85.19 46.75 +38.44 | 5.00 10.00 +8.00 |
6 ec4 8.00 72.26 8.96 +63.30 | 5.00 10.00 +8.00 |
7 ec8 8.00 44.62 35.91 +8.71 | 5.00 10.00 +8.00 |
8 en3 6.00 80.81 31.05 +49.76 | 5.00 10.00 +6.00 |
9 en5 6.00 49.69 29.52 +20.17 | 5.00 10.00 +6.00 |
10 en6 6.00 66.21 31.22 +34.99 | 5.00 10.00 +6.00 |
11 en9 6.00 50.92 9.83 +41.09 | 5.00 10.00 +6.00 |
12 so2 12.00 49.05 12.36 +36.69 | 5.00 10.00 +12.00 |
13 so7 12.00 55.57 44.92 +10.65 | 5.00 10.00 +12.00 |
14 Valuation in range: -72.00 to +72.00; global concordance: +72.00
Alternative p4 is indeed performing unanimously at least as well as alternative p5: r(p4 outranks p5) = +1.00 (see Listing 3.4 Line 11).
The converse comparison does not, however, deliver such an unanimous outranked situation. This comparison only qualifies at stability level -3 (see Listing 3.4 Line 13 r(p5 outranks p4) = 0.89).
1>>> g.showPairwiseComparison('p5','p4')
2 *------------ pairwise comparison ----*
3 Comparing actions : (p5, p4)
4 crit. wght. g(x) g(y) diff | ind pref r() |
5 ec1 8.00 46.75 85.19 -38.44 | 5.00 10.00 -8.00 |
6 ec4 8.00 8.96 72.26 -63.30 | 5.00 10.00 -8.00 |
7 ec8 8.00 35.91 44.62 -8.71 | 5.00 10.00 +0.00 |
8 en3 6.00 31.05 80.81 -49.76 | 5.00 10.00 -6.00 |
9 en5 6.00 29.52 49.69 -20.17 | 5.00 10.00 -6.00 |
10 en6 6.00 31.22 66.21 -34.99 | 5.00 10.00 -6.00 |
11 en9 6.00 9.83 50.92 -41.09 | 5.00 10.00 -6.00 |
12 so2 12.00 12.36 49.05 -36.69 | 5.00 10.00 -12.00 |
13 so7 12.00 44.92 55.57 -10.65 | 5.00 10.00 -12.00 |
14 Valuation in range: -72.00 to +72.00; global concordance: -64.00
Indeed, on criterion ec8 we observe a small negative performance difference of -8.71 (see Listing 3.6 Line 7) which is effectively below the supposed preference discrimination threshold of 10.00. Yet, the outranked situation is supported by a majority of criteria in each decision objective. Hence, the reported preferential situation is completely independent of any chosen significance weights.
Let us now consider a comparison, like the one between alternatives p2 and p1, that is only qualified at stability level +2, resp. -2.
1>>> g.showPairwiseOutrankings('p2','p1')
2 *------------ pairwise comparison ----*
3 Comparing actions : (p2, p1)
4 crit. wght. g(x) g(y) diff | ind pref r() |
5 ec1 8.00 89.77 38.11 +51.66 | 5.00 10.00 +8.00 |
6 ec4 8.00 86.00 22.65 +63.35 | 5.00 10.00 +8.00 |
7 ec8 8.00 89.43 77.02 +12.41 | 5.00 10.00 +8.00 |
8 en3 6.00 20.79 58.16 -37.37 | 5.00 10.00 -6.00 |
9 en5 6.00 23.83 31.40 -7.57 | 5.00 10.00 +0.00 |
10 en6 6.00 18.66 11.41 +7.25 | 5.00 10.00 +6.00 |
11 en9 6.00 26.65 44.37 -17.72 | 5.00 10.00 -6.00 |
12 so2 12.00 89.12 22.43 +66.69 | 5.00 10.00 +12.00 |
13 so7 12.00 84.73 28.41 +56.32 | 5.00 10.00 +12.00 |
14 Valuation in range: -72.00 to +72.00; global concordance: +42.00
15 *------------ pairwise comparison ----*
16 Comparing actions : (p1, p2)
17 crit. wght. g(x) g(y) diff | ind pref r() |
18 ec1 8.00 38.11 89.77 -51.66 | 5.00 10.00 -8.00 |
19 ec4 8.00 22.65 86.00 -63.35 | 5.00 10.00 -8.00 |
20 ec8 8.00 77.02 89.43 -12.41 | 5.00 10.00 -8.00 |
21 en3 6.00 58.16 20.79 +37.37 | 5.00 10.00 +6.00 |
22 en5 6.00 31.40 23.83 +7.57 | 5.00 10.00 +6.00 |
23 en6 6.00 11.41 18.66 -7.25 | 5.00 10.00 +0.00 |
24 en9 6.00 44.37 26.65 +17.72 | 5.00 10.00 +6.00 |
25 so2 12.00 22.43 89.12 -66.69 | 5.00 10.00 -12.00 |
26 so7 12.00 28.41 84.73 -56.32 | 5.00 10.00 -12.00 |
27 Valuation in range: -72.00 to +72.00; global concordance: -30.00
In both comparisons, the performances observed with respect to the environmental decision objective are not validating with a significant majority the otherwise unanimous outranking, resp. outranked situations. Hence, the stability of the reported preferential situations is in fact dependent on choosing significance weights that are compatible with the given significance weights preorder (see Significance weights preorder).
Let us finally inspect a comparison that is only qualified at stability level +1, like the one between alternatives p7 and p3 (see Listing 3.8).
1>>> g.showPairwiseOutrankings('p7','p3')
2*------------ pairwise comparison ----*
3Comparing actions : (p7, p3)
4crit. wght. g(x) g(y) diff | ind pref r() |
5ec1 8.00 15.33 80.19 -64.86 | 5.00 10.00 -8.00 |
6ec4 8.00 36.31 68.70 -32.39 | 5.00 10.00 -8.00 |
7ec8 8.00 38.31 91.94 -53.63 | 5.00 10.00 -8.00 |
8en3 6.00 30.70 46.78 -16.08 | 5.00 10.00 -6.00 |
9en5 6.00 35.52 27.25 +8.27 | 5.00 10.00 +6.00 |
10en6 6.00 69.71 1.65 +68.06 | 5.00 10.00 +6.00 |
11en9 6.00 13.10 14.85 -1.75 | 5.00 10.00 +6.00 |
12so2 12.00 68.06 58.85 +9.21 | 5.00 10.00 +12.00 |
13so7 12.00 58.45 15.49 +42.96 | 5.00 10.00 +12.00 |
14Valuation in range: -72.00 to +72.00; global concordance: +12.00
15*------------ pairwise comparison ----*
16Comparing actions : (p3, p7)
17crit. wght. g(x) g(y) diff | ind pref r() |
18ec1 8.00 80.19 15.33 +64.86 | 5.00 10.00 +8.00 |
19ec4 8.00 68.70 36.31 +32.39 | 5.00 10.00 +8.00 |
20ec8 8.00 91.94 38.31 +53.63 | 5.00 10.00 +8.00 |
21en3 6.00 46.78 30.70 +16.08 | 5.00 10.00 +6.00 |
22en5 6.00 27.25 35.52 -8.27 | 5.00 10.00 +0.00 |
23en6 6.00 1.65 69.71 -68.06 | 5.00 10.00 -6.00 |
24en9 6.00 14.85 13.10 +1.75 | 5.00 10.00 +6.00 |
25so2 12.00 58.85 68.06 -9.21 | 5.00 10.00 +0.00 |
26so7 12.00 15.49 58.45 -42.96 | 5.00 10.00 -12.00 |
27Valuation in range: -72.00 to +72.00; global concordance: +18.00
In both cases, choosing significance weights that are just compatible with the given weights preorder will not always result in positively validated outranking situations.
3.1.3.3. Computing the stability denotation of outranking situations
Stability levels 4 and 3 are easy to detect, the case given. Detecting a stability level 2 is far less obvious. Now, it is precisely again the bipolar-valued epistemic characteristic domain that will give us a way to implement an effective test for stability level +2 and -2 (see [BIS-2004_1p], [BIS-2004_2p]).
Let us consider the significance equivalence classes we observe in the given weights preorder. Here we observe three classes: 6, 8, and 12, in increasing order (see Listing 3.2). In the pairwise comparisons shown above these equivalence classes may appear positively or negatively, besides the indeterminate significance of value 0. We thus get the following ordered bipolar list of significance weights:
W = [-12. -8. -6, 0, 6, 8, 12].
In all the pairwise marginal comparisons shown in the previous Section, we may observe that each one of the nine criteria assigns one precise item out of this list W. Let us denote q[i] the number of criteria assigning item W[i], and Q[i] the cumulative sums of these q[i] counts, where i is an index in the range of the length of list W.
In the comparison of alternatives a2 and a1, for instance (see Listing 3.7), we observe the following counts:
W[i] |
-12 |
-8 |
-6 |
0 |
6 |
8 |
12 |
---|---|---|---|---|---|---|---|
q[i] |
0 |
0 |
2 |
1 |
1 |
3 |
2 |
Q[i] |
0 |
0 |
2 |
3 |
4 |
7 |
9 |
Let use denote -q and -Q the reversed versions of the q and the Q lists. We thus obtain the following result.
W[i] |
-12 |
-8 |
-6 |
0 |
6 |
8 |
12 |
---|---|---|---|---|---|---|---|
-q[i] |
2 |
3 |
1 |
1 |
2 |
0 |
0 |
-Q[i] |
2 |
5 |
6 |
7 |
9 |
9 |
9 |
Now, a pairwise outranking situation will be qualified at stability level +2, i.e. positively validated with any significance weights that are compatible with the given weights preorder, when for all i, we observe Q[i] <= -Q[i] and there exists one i such that Q[i] < -Q[i]. Similarly, a pairwise outranked situation will be qualified at stability level -2, when for all i, we observe Q[i] >= -Q[i] and there exists one i such that Q[i] > -Q[i] (see [BIS-2004_2p]).
We may verify, for instance, that the outranking situation observed between a2 and a1 does indeed verify this first order distributional dominance condition.
W[i] |
-12 |
-8 |
-6 |
0 |
6 |
8 |
12 |
---|---|---|---|---|---|---|---|
Q[i] |
0 |
0 |
2 |
3 |
4 |
7 |
9 |
-Q[i] |
2 |
5 |
6 |
7 |
9 |
9 |
9 |
Notice that outranking situations qualified at stability levels 4 and 3, evidently also verify the stability level 2 test above. The outranking situation between alternatives a7 and a3 does not, however, verify this test (see Listing 3.8).
W[i] |
-12 |
-8 |
-6 |
0 |
6 |
8 |
12 |
---|---|---|---|---|---|---|---|
q[i] |
0 |
3 |
1 |
0 |
3 |
0 |
2 |
Q[i] |
0 |
3 |
4 |
4 |
7 |
7 |
9 |
-Q[i] |
2 |
2 |
5 |
5 |
6 |
9 |
9 |
This time, not all the Q[i] are lower or equal than the corresponding -Q[i] terms. Hence the outranking situation between a7 and a3 is not positively validated with all potential significance weights that are compatible with the given weights preorder.
Using this stability denotation, we may, hence, define the following robust version of a bipolar-valued outranking digraph.
3.1.3.4. Robust bipolar-valued outranking digraphs
We say that decision alternative x robustly outranks decision alternative y when
x positively outranks y at stability level higher or equal to 2 and we may not observe any considerable counter-performance of x on a discordant criterion.
Dually, we say that decision alternative x does not robustly outrank decision alternative y when
x negatively outranks y at stability level lower or equal to -2 and we may not observe any considerable better performance of x on a discordant criterion.
The corresponding robust outranking digraph may be computed with the RobustOutrankingDigraph
class as follows.
1>>> from outrankingDigraphs import RobustOutrankingDigraph
2>>> rg = RobustOutrankingDigraph(t) # same t as before
3>>> rg
4 *------- Object instance description ------*
5 Instance class : RobustOutrankingDigraph
6 Instance name : robust_random3ObjectivesPerfTab
7 # Actions : 7
8 # Criteria : 9
9 Size : 22
10 Determinateness (%) : 68.45
11 Valuation domain : [-1.00;1.00]
12 Attributes : ['name', 'methodData', 'actions', 'order',
13 'criteria', 'evaluation', 'vetos',
14 'valuationdomain', 'cardinalRelation',
15 'ordinalRelation', 'equisignificantRelation',
16 'unanimousRelation', 'relation',
17 'gamma', 'notGamma']
18>>> rg.showRelationTable(StabilityDenotation=True)
19 * ---- Relation Table -----
20 r/(stab) | 'p1' 'p2' 'p3' 'p4' 'p5' 'p6' 'p7'
21 ---------|------------------------------------------------------------
22 'p1' | +1.00 -0.42 +0.00 -0.69 +0.39 +0.11 +0.00
23 | (+4) (-2) (+0) (-3) (+2) (+2) (-1)
24 'p2' | +0.58 +1.00 +0.83 +0.00 +0.58 +0.58 +0.58
25 | (+2) (+4) (+3) (+2) (+2) (+2) (+2)
26 'p3' | +0.25 -0.33 +1.00 +0.00 +0.50 +1.00 +0.00
27 | (+2) (-2) (+4) (+0) (+2) (+2) (+1)
28 'p4' | +0.78 +0.00 +0.61 +1.00 +1.00 +1.00 +0.67
29 | (+3) (-1) (+3) (+4) (+4) (+4) (+2)
30 'p5' | -0.11 -0.50 -0.25 -0.89 +1.00 +0.11 -0.14
31 | (-2) (-2) (-2) (-3) (+4) (+2) (-2)
32 'p6' | +0.22 -0.42 +0.00 -1.00 +0.17 +1.00 -0.11
33 | (+2) (-2) (+1) (-2) (+2) (+4) (-2)
34 'p7' | +0.22 -0.50 +0.00 +0.00 +0.78 +0.42 +1.00
35 | (+2) (-2) (+1) (-1) (+3) (+2) (+4)
We may notice that all outranking situations, qualified at stability level +1 or -1, are now put to an indeterminate status. In the example here, we actually drop three positive outrankings: between p3 and p7, between p7 and p3, and between p6 and p3, where the last situation is actually already put to doubt by a veto situation (see Listing 3.9 Lines 22-35). We drop as well three negative outrankings: between p1 and p7, between p4 and p2, and between p7 and p4 (see Listing 3.9 Lines 22-35).
Notice by the way that outranking (resp. outranked) situations, although qualified at level +2 or +3 (resp. -2 or -3) may nevertheless be put to doubt by considerable performance differences. We may observe such an outranking situation when comparing, for instance, alternatives p2 and p4 (see Listing 3.9 Lines 24-25).
1>>> rg.showPairwiseComparison('p2','p4')
2 *------------ pairwise comparison ----*
3 Comparing actions : (p2, p4)
4 crit. wght. g(x) g(y) diff | ind pref r() | v veto
5 -------------------------------------------------------------------------
6 ec1 8.00 89.77 85.19 +4.58 | 5.00 10.00 +8.00 |
7 ec4 8.00 86.00 72.26 +13.74 | 5.00 10.00 +8.00 |
8 ec8 8.00 89.43 44.62 +44.81 | 5.00 10.00 +8.00 |
9 en3 6.00 20.79 80.81 -60.02 | 5.00 10.00 -6.00 | 60.00 -1.00
10 en5 6.00 23.83 49.69 -25.86 | 5.00 10.00 -6.00 |
11 en6 6.00 18.66 66.21 -47.55 | 5.00 10.00 -6.00 |
12 en9 6.00 26.65 50.92 -24.27 | 5.00 10.00 -6.00 |
13 so2 12.00 89.12 49.05 +40.07 | 5.00 10.00 +12.00 |
14 so7 12.00 84.73 55.57 +29.16 | 5.00 10.00 +12.00 |
15 Valuation in range: -72.00 to +72.00; global concordance: +24.00
Despite being robust, the apparent positive outranking situation between alternatives p2 and p4 is indeed put to doubt by a considerable counter-performance (-60.02) of p2 on criterion en3, a negative difference which exceeds slightly the assumed veto discrimination threshold v = 60.00 (see Listing 3.10 Line 9).
We may finally compare in Fig. 3.10 the standard and the robust version of the corresponding strict outranking digraphs, both oriented by their respective identical initial and terminal prekernels.
The robust version drops two strict outranking situations: between p4 and p7 and between p7 and p1. The remaining 14 strict outranking (resp. outranked) situations are now all verified at a stability level of +2 and more (resp. -2 and less). They are, hence, only depending on potential significance weights that must respect the given significance preorder (see Listing 3.2).
To appreciate the apparent orientation of the standard and robust strict outranking digraphs shown in Fig. 3.10, let us have a final heat map view on the underlying performance tableau ordered by the NetFlows ranking rule.
>>> t.showHTMLPerformanceHeatmap(Correlations=True,
... rankingRule='NetFlows')
As the inital prekernel is here validated at stability level +2, recommending alternatives p4, as well as p2, as potential first choices, appears well justified. Alternative a4 represents indeed an overall best compromise choice between all decision objectives, whereas alternative p2 gives an unanimous best choice with respect to two out of three decision objectives. Up to the decision maker to make his final choice.
For concluding, let us mention that it is precisely again our bipolar-valued logical characteristic framework that provides us here with a first order distributional dominance test for effectively qualifying the stability level 2 robustness of an outranking digraph when facing performance tableaux with criteria of only ordinal-valued significance weights. A real world application of our stability analysis with such a kind of performance tableau may be consulted in [BIS-2015p].
Back to Content Table
3.1.4. On unopposed outrankings with multiple decision objectives
When facing a performance tableau involving multiple decision objectives, the robustness level +/-3, introduced in the previous Section, may lead to distinguishing what we call unopposed outranking situations, like the one shown between alternative p4 and p1 (, see Listing 3.4 Line11), namely preferential situations that are more or less validated or invalidated by all the decision objectives.
3.1.4.1. Characterising unopposed multiobjective outranking situations
Formally, we say that decision alternative x outranks decision alternative y unopposed when
x positively outranks y on one or more decision objective without x being positively outranked by y on any decision objective.
Dually, we say that decision alternative x does not outrank decision alternative y unopposed when
x is positively outranked by y on one or more decision objective without x outranking y on any decision objective.
Let us reconsider, for instance, the previous performance tableau with three decision objectives (see Listing 3.1):
1>>> from randomPerfTabs import\
2... Random3ObjectivesPerformanceTableau
3
4>>> t = Random3ObjectivesPerformanceTableau(
5... numberOfActions=7,
6... numberOfCriteria=9,seed=102)
7
8>>> t.showObjectives()
9 *------ show objectives -------"
10 Eco: Economical aspect
11 ec1 criterion of objective Eco 8
12 ec4 criterion of objective Eco 8
13 ec8 criterion of objective Eco 8
14 Total weight: 24.00 (3 criteria)
15 Soc: Societal aspect
16 so2 criterion of objective Soc 12
17 so7 criterion of objective Soc 12
18 Total weight: 24.00 (2 criteria)
19 Env: Environmental aspect
20 en3 criterion of objective Env 6
21 en5 criterion of objective Env 6
22 en6 criterion of objective Env 6
23 en9 criterion of objective Env 6
24 Total weight: 24.00 (4 criteria)
We notice in this example three decision objectives of equal importance (see Listing 3.11 Lines 10,15,19). What will be the outranking situations that are positively (resp. negatively) validated for each one of the decision objectives taken individually ?
We may obtain such unopposed multiobjective outranking situations by operating an epistemic o-average fusion (see the ~digraphsTools.symmetricAverage
method) of the marginal outranking digraphs restricted to the coalition of criteria supporting each one of the decision objectives (see Listing 3.12 below).
1>>> from outrankingDigraphs import BipolarOutrankingDigraph
2>>> geco = BipolarOutrankingDigraph(t,objectivesSubset=['Eco'])
3>>> gsoc = BipolarOutrankingDigraph(t,objectivesSubset=['Soc'])
4>>> genv = BipolarOutrankingDigraph(t,objectivesSubset=['Env'])
5>>> from digraphs import FusionLDigraph
6>>> objectiveWeights = \
7... [t.objectives[obj]['weight'] for obj in t.objectives]
8
9>>> uopg = FusionLDigraph([geco,gsoc,genv],
10... operator='o-average',
11... weights=objectiveWeights)
12
13>>> uopg.showRelationTable(ReflexiveTerms=False)
14* ---- Relation Table -----
15 r | 'p1' 'p2' 'p3' 'p4' 'p5' 'p6' 'p7'
16-----|------------------------------------------------------------
17'p1' | - +0.00 +0.00 -0.69 +0.39 +0.11 +0.00
18'p2' | +0.00 - +0.83 +0.00 +0.00 +0.00 +0.00
19'p3' | +0.00 -0.33 - +0.00 +0.50 +0.00 +0.00
20'p4' | +0.78 +0.00 +0.61 - +1.00 +1.00 +0.67
21'p5' | -0.11 +0.00 +0.00 -0.89 - +0.11 +0.00
22'p6' | +0.00 +0.00 +0.00 -0.44 +0.17 - +0.00
23'p7' | +0.00 +0.00 +0.00 +0.00 +0.78 +0.42 -
24Valuation domain: [-1.000; 1.000]
Positive (resp. negative) characteristic values, like (see Listing 3.12 Line 17), show hence only outranking situations being validated (resp. invalidated) by one or more decision objectives without being invalidated (resp. validated) by any other decision objective.
For easily computing this kind of unopposed multiobjective outranking digraphs, the outrankingDigraphs module
conveniently provides a corresponding UnOpposedBipolarOutrankingDigraph
constructor.
1>>> from outrankingDigraphs import\
2... UnOpposedBipolarOutrankingDigraph
3
4>>> uopg = UnOpposedBipolarOutrankingDigraph(t)
5>>> uopg
6 *------- Object instance description ------*
7 Instance class : UnOpposedBipolarOutrankingDigraph
8 Instance name : unopposed_outrankings
9 # Actions : 7
10 # Criteria : 9
11 Size : 13
12 Oppositeness (%) : 43.48
13 Determinateness (%) : 61.71
14 Valuation domain : [-1.00;1.00]
15 Attributes : ['name', 'actions', 'valuationdomain', 'objectives',
16 'criteria', 'methodData', 'evaluation', 'order',
17 'runTimes', 'relation', 'marginalRelationsRelations',
18 'gamma', 'notGamma']
19>>> uopg.computeOppositeness(InPercents=True)
20 {'standardSize': 23, 'unopposedSize': 13,
21 'oppositeness': 43.47826086956522}
The resulting unopposed outranking digraph keeps in fact 13 (see Listing 3.13 Lines 12-13) out of the 23 positively validated standard outranking situations, leading to a degree of oppositeness -preferential disagreement between decision objectives- of .
We may now, for instance, verify the unopposed status of the outranking situation observed between alternatives p1 and p5.
1>>> uopg.showPairwiseComparison('p1','p5')
2 *------------ pairwise comparison ----*
3 Comparing actions : (p1, p5)
4 crit. wght. g(x) g(y) diff | ind pref r() |
5 ec1 8.00 38.11 46.75 -8.64 | 5.00 10.00 +0.00 |
6 ec4 8.00 22.65 8.96 +13.69 | 5.00 10.00 +8.00 |
7 ec8 8.00 77.02 35.91 +41.11 | 5.00 10.00 +8.00 |
8 en3 6.00 58.16 31.05 +27.11 | 5.00 10.00 +6.00 |
9 en5 6.00 31.40 29.52 +1.88 | 5.00 10.00 +6.00 |
10 en6 6.00 11.41 31.22 -19.81 | 5.00 10.00 -6.00 |
11 en9 6.00 44.37 9.83 +34.54 | 5.00 10.00 +6.00 |
12 so2 12.00 22.43 12.36 +10.07 | 5.00 10.00 +12.00 |
13 so7 12.00 28.41 44.92 -16.51 | 5.00 10.00 -12.00 |
14 Valuation in range: -72.00 to +72.00; global concordance: +28.00
In Listing 3.14 we see that alternative p1 does indeed positively outrank alternative p5 from the economic perspective () as well as from the environmental perspective (). Whereas, from the societal perspective, both alternatives appear incomparable ().
When fixed proportional criteria significance weights per objective are given, these outranking situations appear hence stable with respect to all possible importance weights we could allocate to the decision objectives.
This gives way for computing multiobjective choice recommendations.
3.1.4.2. Computing unopposed multiobjective choice recommendations
Indeed, best choice recommendations, computed from an unopposed multiobjective outranking digraph, will in fact deliver efficient choice recommendations.
1>>> uopg.showBestChoiceRecommendation()
2 Best choice recommendation(s) (BCR)
3 (in decreasing order of determinateness)
4 Credibility domain: [-1.00,1.00]
5 === >> potential first choice(s)
6 choice : ['p2', 'p4', 'p7']
7 independence : 0.00
8 dominance : 0.33
9 absorbency : 0.00
10 covering (%) : 33.33
11 determinateness (%) : 50.00
12 === >> potential last choice(s)
13 choice : ['p3', 'p5', 'p6', 'p7']
14 independence : 0.00
15 dominance : -0.61
16 absorbency : 0.11
17 covered (%) : 33.33
18 determinateness (%) : 50.00
Our previous robust best choice recommendation (p2 and p4, see Fig. 3.10) remains, in this example here, stable. We recover indeed the best choice recommendation [‘p2’, ‘p4’, ‘p7’] (see Listing 3.15 Line 6). Yet, notice that decision alternative p7 appears to be at the same time a potential first as well as a potential last choice recommendation (see Line 13), a consequence of p7 being completely incomparable to the other decision alternatives when restricting the comparability to only unopposed strict outranking situations.
We may visualize this kind of efficient choice recommendation in Fig. 3.12 below.
1>>> (~(-uopg)).exportGraphViz(fileName = 'unopDigraph',
2... firstChoice = ['p2', 'p4'],
3... lastChoice = ['p3', 'p5', 'p6'])
4 *---- exporting a dot file for GraphViz tools ---------*
5 Exporting to unopDigraph.dot
6 dot -Grankdir=BT -Tpng unopDigraph.dot -o unopDigraph.png
In order to make now an eventual best unique choice, a decision maker will necessarily have to weight, in a second stage of the decision aiding process, the relative importance of the individual decision objectives (see tutorial on computing a best choice recommendation).
Back to Content Table
3.3. Theoretical advancements
3.3.1. Ordinal correlation equals bipolar-valued relational equivalence
3.3.1.1. Kendall’s tau index
M. G. Kendall ([KEN-1938p]) defined his ordinal correlation (tau) index for linear orders of dimension n as a balancing of the number #Co of correctly oriented pairs against the number #In of incorrectly oriented pairs. The total number of irreflexive pairs being n(n-1), in the case of linear orders, . Hence . In case #In is zero, (all pairs are equivalently oriented); inversely, in case #Co is zero, (all pairs are differently oriented).
Noticing that , and recalling that the bipolar-valued negation is operated by changing the sign of the characteristic value, Kendall’s original tau definition implemented in fact the bipolar-valued negation of the non equivalence of two linear orders:
i.e. the normalized majority margin of equivalently oriented irreflexive pairs.
Let R1 and R2 be two random crisp relations defined on a same set of 5 alternatives. We may compute Kendall’s tau index as follows.
1>>> from digraphs import *
2>>> R1 = RandomDigraph(order=5,Bipolar=True)
3>>> R2 = RandomDigraph(order=5,Bipolar=True)
4>>> E = EquivalenceDigraph(R1,R2)
5>>> E.showRelationTable(ReflexiveTerms=False)
6 * ---- Relation Table -----
7 r(<=>)| 'a1' 'a2' 'a3' 'a4' 'a5'
8 ------|-------------------------------------------
9 'a1' | - -1.00 1.00 -1.00 1.00
10 'a2' | -1.00 - -1.00 1.00 -1.00
11 'a3' | -1.00 -1.00 - 1.00 1.00
12 'a4' | -1.00 1.00 -1.00 - 1.00
13 'a5' | -1.00 1.00 -1.00 1.00 -
14 Valuation domain: [-1.00;1.00]
15>>> E.correlation
16 {'correlation': -0.1, 'determination': 1.0}
In the table of the equivalence relation above (see Listing 3.34 Lines 9-13), we observe that the normalized majority margin of equivalent versus non equivalent irreflexive pairs amounts to (9 - 11)/20 = -0.1, i.e. the value of Kendall’s tau index in this plainly determined crisp case (see Listing 3.34 Line 16).
What happens now with more or less determined and even partially indeterminate relations ? May we proceed in a similar way ?
3.3.1.2. Bipolar-valued relational equivalence
Let us now consider two randomly bipolar-valued digraphs R1 and R2 of order five.
1>>> R1 = RandomValuationDigraph(order=5,seed=1)
2>>> R1.showRelationTable(ReflexiveTerms=False)
3 * ---- Relation Table -----
4 r(R1)| 'a1' 'a2' 'a3' 'a4' 'a5'
5 ------|-------------------------------------------
6 'a1' | - -0.66 0.44 0.94 -0.84
7 'a2' | -0.36 - -0.70 0.26 0.94
8 'a3' | 0.14 0.20 - 0.66 -0.04
9 'a4' | -0.48 -0.76 0.24 - -0.94
10 'a5' | -0.02 0.10 0.54 0.94 -
11 Valuation domain: [-1.00;1.00]
12>>> R2 = RandomValuationDigraph(order=5,seed=2)
13>>> R2.showRelationTable(ReflexiveTerms=False)
14 * ---- Relation Table -----
15 r(R2)| 'a1' 'a2' 'a3' 'a4' 'a5'
16 ------|-------------------------------------------
17 'a1' | - -0.86 -0.78 -0.80 -0.08
18 'a2' | -0.58 - 0.88 0.70 -0.22
19 'a3' | -0.36 0.54 - -0.46 0.54
20 'a4' | -0.92 0.48 0.74 - -0.60
21 'a5' | 0.10 0.62 0.00 0.84 -
22 Valuation domain: [-1.00;1.00]
We may notice in the relation tables shown above that 9 pairs, like (a1,a2) or (a3,a2) for instance, appear equivalently oriented (see Listing 3.35 Lines 6,17 or 8,19). The EquivalenceDigraph
class implements this relational equivalence relation between digraphs R1 and R2 (see Listing 3.36).
1>>> eq = EquivalenceDigraph(R1,R2)
2>>> eq.showRelationTable(ReflexiveTerms=False)
3 * ---- Relation Table -----
4 r(<=>)| 'a1' 'a2' 'a3' 'a4' 'a5'
5 ------|-------------------------------------------
6 'a1' | - 0.66 -0.44 -0.80 0.08
7 'a2' | 0.36 - -0.70 0.26 -0.22
8 'a3' | -0.14 0.20 - -0.46 -0.04
9 'a4' | 0.48 -0.48 0.24 - 0.60
10 'a5' | -0.02 0.10 0.00 0.84 -
11 Valuation domain: [-1.00;1.00]
In our bipolar-valued epistemic logic, logical disjunctions and conjunctions are implemented as max, respectively min operators. Notice also that the logical equivalence corresponds to a double implication and that the implication is logically equivalent to the disjunction .
When and denote the bipolar-valued characteristic values of relation R1, resp. R2, we may hence compute as follows a majority margin between equivalently and not equivalently oriented irreflexive pairs (x,y).
is thus given by the sum of the non reflexive terms of the relation table of eq, the relation equivalence digraph computed above (see Listing 3.36).
In the crisp case, is now normalized with the maximum number of possible irreflexive pairs, namely n(n-1). In a generalized r-valued case, the maximal possible equivalence majority margin M corresponds to the sum D of the conjoint determinations of and (see [BIS-2012p]).
Thus, we obtain in the general r -valued case:
corresponds thus to a classical ordinal correlation index, but restricted to the conjointly determined parts of the given relations R1 and R2. In the limit case of two crisp linear orders, D equals n(n-1), i.e. the number of irreflexive pairs, and we recover hence Kendall ‘s original tau index definition.
It is worthwhile noticing that the ordinal correlation index we obtain above corresponds to the ratio of
: the normalized majority margin of the pairwise relational equivalence statements, also called valued ordinal correlation, and
: the normalized determination of the corresponding pairwise relational equivalence statements, in fact the determinateness of the relational equivalence digraph.
We have thus successfully out-factored the determination effect from the correlation effect. With completely determined relations, . By convention, we set the ordinal correlation with a completely indeterminate relation, i.e. when D = 0, to the indeterminate correlation value 0.0. With uniformly chosen random r-valued relations, the expected tau index is 0.0, denoting in fact an indeterminate correlation. The corresponding expected normalized determination d is about 0.333 (see [BIS-2012p]).
We may verify these relations with help of the corresponding equivalence digraph eq (see Listing 3.37).
1>>> eq = EquivalenceDigraph(R1,R2)
2>>> M = Decimal('0'); D = Decimal('0')
3>>> n2 = eq.order*(eq.order - 1)
4>>> for x in eq.actions:
5... for y in eq.actions:
6... if x != y:
7... M += eq.relation[x][y]
8... D += abs(eq.relation[x][y])
9>>> print('r(R1<=>R2) = %+.3f, d = %.3f, tau = %+.3f' % (M/n2,D/n2,M/D))
10
11 r(R1<=>R2) = +0.026, d = 0.356, tau = +0.073
In general we simply use the computeOrdinalCorrelation()
method which renders a dictionary with a ‘correlation’ (tau) and a ‘determination’ (d) attribute. We may recover r(<=>) by multiplying tau with d (see Listing 3.38 Line 4).
1>>> corrR1R2 = R1.computeOrdinalCorrelation(R2)
2>>> tau = corrR1R2['correlation']
3>>> d = corrR1R2['determination']
4>>> r = tau * d
5>>> print('tau(R1,R2) = %+.3f, d = %.3f,\
6... r(R1<=>R2) = %+.3f' % (tau, d, r))
7
8 tau(R1,R2) = +0.073, d = 0.356, r(R1<=>R2) = +0.026
We provide for convenience a direct showCorrelation()
method:
1>>> corrR1R2 = R1.computeOrdinalCorrelation(R2)
2>>> R1.showCorrelation(corrR1R2)
3 Correlation indexes:
4 Extended Kendall tau : +0.073
5 Epistemic determination : 0.356
6 Bipolar-valued equivalence : +0.026
We may now illustrate the quality of the global ranking of the movies shown with the heat map in Fig. 3.2.
3.3.1.3. Fitness of ranking heuristics
We reconsider the bipolar-valued outranking digraph g modelling the pairwise global ‘at least as well rated as’ relation among the 25 movies seen above (see Listing 3.39).
1>>> g = BipolarOutrankingDigraph(t,Normalized=True)
2 *------- Object instance description ------*
3 Instance class : BipolarOutrankingDigraph
4 Instance name : rel_grafittiPerfTab.xml
5 # Actions : 25
6 # Criteria : 15
7 Size : 390
8 Determinateness : 65%
9 Valuation domain : {'min': Decimal('-1.0'),
10 'med': Decimal('0.0'),
11 'max': Decimal('1.0'),}
12>>> g.computeCoSize()
13 188
Out of the 25 x 24 = 600 irreflexive movie pairs, digraph g contains 390 positively validated, 188 positively invalidated, and 22 indeterminate outranking situations (see the zero-valued cells in Fig. 3.4).
Let us now compute the normalized majority margin r(<=>) of the equivalence between the marginal critic’s pairwise ratings and the global Net-Flows ranking shown in the ordered heat map (see Fig. 3.2).
1>>> from linearOrders import NetFlowsOrder
2>>> nf = NetFlowsOrder(g)
3>>> nf.netFlowsRanking
4 ['mv_QS', 'mv_RR', 'mv_DG', 'mv_NP', 'mv_HN', 'mv_HS', 'mv_SM',
5 'mv_JB', 'mv_PE', 'mv_FC', 'mv_TP', 'mv_CM', 'mv_DF', 'mv_TM',
6 'mv_DJ', 'mv_AL', 'mv_RG', 'mv_MB', 'mv_GH', 'mv_HP', 'mv_BI',
7 'mv_DI', 'mv_FF', 'mv_GG', 'mv_TF']
8>>> for i,item in enumerate(\
9... g.computeMarginalVersusGlobalRankingCorrelations(\
10... nf.netFlowsRanking,ValuedCorrelation=True) ):\
11... print('r(%s<=>nf) = %+.3f' % (item[1],item[0]) )
12
13 r(JH<=>nf) = +0.500
14 r(JPT<=>nf) = +0.430
15 r(AP<=>nf) = +0.323
16 r(DR<=>nf) = +0.263
17 r(MR<=>nf) = +0.247
18 r(VT<=>nf) = +0.227
19 r(GS<=>nf) = +0.160
20 r(CS<=>nf) = +0.140
21 r(SJ<=>nf) = +0.137
22 r(RR<=>nf) = +0.133
23 r(TD<=>nf) = +0.110
24 r(CF<=>nf) = +0.110
25 r(SF<=>nf) = +0.103
26 r(AS<=>nf) = +0.080
27 r(FG<=>nf) = +0.027
In Listing 3.40 (see Lines 13-27), we recover above the relational equivalence characteristic values shown in the third row of the table in Fig. 3.2. The global Net-Flows ranking represents obviously a rather balanced compromise with respect to all movie critics’ opinions as there appears no valued negative correlation with anyone of them. The Net-Flows ranking apparently takes also correctly in account that the journalist JH, a locally renowned movie critic, shows a higher significance weight (see Line 13).
The ordinal correlation between the global Net-Flows ranking and the digraph g may be furthermore computed as follows:
1>>> corrgnf = g.computeOrdinalCorrelation(nf)
2>>> g.showCorrelation(corrgnf)
3 Correlation indexes:
4 Extended Kendall tau : +0.780
5 Epistemic determination : 0.300
6 Bipolar-valued equivalence : +0.234
We notice in Listing 3.41 Line 4 that the ordinal correlation tau(g,nf) index between the Net-Flows ranking nf and the determined part of the outranking digraph g is quite high (+0.78). Due to the rather high number of missing data, the r -valued relational equivalence between the nf and the g digraph, with a characteristics value of only +0.234, may be misleading. Yet, +0.234 still corresponds to an epistemic majority support of nearly 62% of the movie critics’ rating opinions.
It would be interesting to compare similarly the correlations one may obtain with other global ranking heuristics, like the Copeland or the Kohler ranking rule.
3.3.1.4. Illustrating preference divergences
The valued relational equivalence index gives us a further measure for studying how divergent appear the rating opinions expressed by the movie critics.
It is remarkable to notice in the criteria correlation matrix (see Fig. 3.19) that, due to the quite numerous missing data, all pairwise valued ordinal correlation indexes r(x<=>y) appear to be of low value, except the diagonal ones. These reflexive indexes r(x<=>x) would trivially all amount to +1.0 in a plainly determined case. Here they indicate a reflexive normalized determination score d, i.e. the proportion of pairs of movies each critic did evaluate. Critic JPT (the editor of the Graffiti magazine), for instance, evaluated all but one (d = 24*23/600 = 0.92), whereas critic FG evaluated only 10 movies among the 25 in discussion (d = 10*9/600 = 0.15).
To get a picture of the actual divergence of rating opinions concerning jointly seen pairs of movies, we may develop a Principal Component Analysis ([2]) of the corresponding tau correlation matrix. The 3D plot of the first 3 principal axes is shown in Fig. 3.20.
>>> g.export3DplotOfCriteriaCorrelation(ValuedCorrelation=False)
The first 3 principal axes support together about 70% of the total inertia. Most eccentric and opposed in their respective rating opinions appear, on the first principal axis with 27.2% inertia, the conservative daily press against labour and public press. On the second principal axis with 23.7.7% inertia, it is the people press versus the cultural critical press. And, on the third axis with still 19.3% inertia, the written media appear most opposed to the radio media.
3.3.1.5. Exploring the better rated and the as well as rated opinions
In order to furthermore study the quality of a ranking result, it may be interesting to have a separate view on the asymmetric and symmetric parts of the ‘at least as well rated as’ opinions (see the tutorial on Manipulating Digraph objects).
Let us first have a look at the pairwise asymmetric part, namely the ‘better rated than’ and ‘less well rated than’ opinions of the movie critics.
>>> ag = AsymmetricPartialDigraph(g)
>>> ag.showHTMLRelationTable(actionsList=g.computeNetFlowsRanking(),ndigits=0)
We notice here that the Net-Flows ranking rule inverts in fact just three ‘less well ranked than’ opinions and four ‘better ranked than’ ones. A similar look at the symmetric part, the pairwise ‘as well rated as’ opinions, suggests a preordered preference structure in several equivalently rated classes.
>>> sg = SymmetricPartialDigraph(g)
>>> sg.showHTMLRelationTable(actionsList=g.computeNetFlowsRanking(),ndigits=0)
Such a preordering of the movies may, for instance, be computed with the computeRankingByChoosing()
method, where we iteratively extract dominant kernels -remaining first choices- and absorbent kernels -remaining last choices- (see the tutorial on Computing Digraph Kernels). We operate therefore on the asymmetric ‘better rated than’, i.e. the codual ([3]) of the ‘at least as well rated as’ opinions (see Listing 3.42 Line 2).
1>>> from transitiveDigraphs import RankingByChoosingDigraph
2>>> rbc = RankingByChoosingDigraph(g,CoDual=True)
3>>> rbc.showRankingByChoosing()
4 Ranking by Choosing and Rejecting
5 1st First Choice ['mv_QS']
6 2nd First Choice ['mv_DG', 'mv_FC', 'mv_HN', 'mv_HS', 'mv_NP',
7 'mv_PE', 'mv_RR', 'mv_SM']
8 3rd First Choice ['mv_CM', 'mv_JB', 'mv_TM']
9 4th First Choice ['mv_AL', 'mv_TP']
10 4th Last Choice ['mv_AL', 'mv_TP']
11 3rd Last Choice ['mv_GH', 'mv_MB', 'mv_RG']
12 2nd Last Choice ['mv_DF', 'mv_DJ', 'mv_FF', 'mv_GG']
13 1st Last Choice ['mv_BI', 'mv_DI', 'mv_HP', 'mv_TF']
Back to Content Table
3.3.2. On computing digraph kernels
3.3.2.1. What is a graph kernel ?
We call choice in a graph, respectively a digraph, a subset of its vertices, resp. of its nodes or actions. A choice Y is called internally stable or independent when there exist no links (edges) or relations (arcs) between its members. Furthermore, a choice Y is called externally stable when for each vertex, node or action x not in Y, there exists at least a member y of Y such that x is linked or related to y. Now, an internally and externally stable choice is called a kernel.
A first trivial example is immediately given by the maximal independent vertices sets (MISs) of the n-cycle graph (see tutorial on computing isomorphic choices). Indeed, each MIS in the n-cycle graph is by definition independent, i.e. internally stable, and each non selected vertex in the n-cycle graph is in relation with either one or even two members of the MIS. See, for instance, the four non isomorphic MISs of the 12-cycle graph as shown in Fig. 1.62.
In all graph or symmetric digraph, the maximality condition imposed on the internal stability is equivalent to the external stability condition. Indeed, if there would exist a vertex or node not related to any of the elements of a choice, then we may safely add this vertex or node to the given choice without violating its internal stability. All kernels must hence be maximal independent choices. In fact, in a topological sense, they correspond to maximal holes in the given graph.
We may illustrate this coincidence between MISs and kernels in graphs and symmetric digraphs with the following random 3-regular graph instance (see Fig. 3.23).
1>>> from graphs import RandomRegularGraph
2>>> g = RandomRegularGraph(order=12,degree=3,seed=100)
3>>> g.exportGraphViz('random3RegularGraph')
4 *---- exporting a dot file for GraphViz tools ---------*
5 Exporting to random3RegularGraph.dot
6 fdp -Tpng random3RegularGraph.dot -o random3RegularGraph.png
A random MIS in this graph may be computed for instance by using the MISModel
class.
1>>> from graphs import MISModel
2>>> mg = MISModel(g)
3 Iteration: 1
4 Running a Gibbs Sampler for 660 step !
5 {'a06', 'a02', 'a12', 'a10'} is maximal !
6>>> mg.exportGraphViz('random3RegularGraph_mis')
7 *---- exporting a dot file for GraphViz tools ---------*
8 Exporting to random3RegularGraph-mis.dot
9 fdp -Tpng random3RegularGraph-mis.dot -o random3RegularGraph-mis.png
It is easily verified in Fig. 3.24 above, that the computed MIS renders indeed a valid kernel of the given graph. The complete set of kernels of this 3-regular graph instance coincides hence with the set of its MISs.
1>>> g.showMIS()
2 *--- Maximal Independent Sets ---*
3 ['a01', 'a02', 'a03', 'a07']
4 ['a01', 'a04', 'a05', 'a08']
5 ['a04', 'a05', 'a08', 'a09']
6 ['a01', 'a04', 'a05', 'a10']
7 ['a04', 'a05', 'a09', 'a10']
8 ['a02', 'a03', 'a07', 'a12']
9 ['a01', 'a03', 'a07', 'a11']
10 ['a05', 'a08', 'a09', 'a11']
11 ['a03', 'a07', 'a11', 'a12']
12 ['a07', 'a09', 'a11', 'a12']
13 ['a08', 'a09', 'a11', 'a12']
14 ['a04', 'a05', 'a06', 'a08']
15 ['a04', 'a05', 'a06', 'a10']
16 ['a02', 'a04', 'a06', 'a10']
17 ['a02', 'a03', 'a06', 'a12']
18 ['a02', 'a06', 'a10', 'a12']
19 ['a01', 'a02', 'a04', 'a07', 'a10']
20 ['a02', 'a04', 'a07', 'a09', 'a10']
21 ['a02', 'a07', 'a09', 'a10', 'a12']
22 ['a01', 'a03', 'a05', 'a08', 'a11']
23 ['a03', 'a05', 'a06', 'a08', 'a11']
24 ['a03', 'a06', 'a08', 'a11', 'a12']
25 number of solutions: 22
26 cardinality distribution
27 card.: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
28 freq.: [0, 0, 0, 0, 16, 6, 0, 0, 0, 0, 0, 0, 0]
29 execution time: 0.00045 sec.
30 Results in self.misset
31>>> g.misset
32 [frozenset({'a02', 'a01', 'a07', 'a03'}),
33 frozenset({'a04', 'a01', 'a08', 'a05'}),
34 frozenset({'a09', 'a04', 'a08', 'a05'}),
35 ...
36 ...
37 frozenset({'a06', 'a02', 'a12', 'a10'}),
38 frozenset({'a06', 'a11', 'a08', 'a03', 'a05'}),
39 frozenset({'a03', 'a06', 'a11', 'a12', 'a08'})]
We cannot resist in looking in this 3-regular graph for non isomorphic kernels (MISs, see previous tutorial). To do so we must first, convert the given graph instance into a digraph instance. Then, compute its automorphism generators, and finally, identify the isomorphic kernel orbits.
1>>> dg = g.graph2Digraph()
2>>> dg.showMIS()
3 *--- Maximal independent choices ---*
4 ...
5 ['a06', 'a02', 'a12', 'a10']
6 ...
7 number of solutions: 22
8 cardinality distribution
9 card.: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
10 freq.: [0, 0, 0, 0, 16, 6, 0, 0, 0, 0, 0, 0, 0]
11 execution time: 0.00080 sec.
12 Results in self.misset
13>>> dg.automorphismGenerators()
14 *----- saving digraph in nauty dre format -------------*
15 ...
16 # automorphisms extraction from dre file #
17 # Using input file: randomRegularGraph.dre
18 echo '<randomRegularGraph.dre -m p >randomRegularGraph.auto x' | dreadnaut
19 # permutation = 1['1', '11', '7', '5', '4', '9', '3', '10', '6', '8', '2', '12']
20>>> dg.showOrbits(dg.misset)
21 *--- Isomorphic reduction of choices
22 ...
23 current representative: frozenset({'a09', 'a11', 'a12', 'a08'})
24 length : 4
25 number of isomorph choices 2
26 isormorph choices
27 ['a06', 'a02', 'a12', 'a10'] # <<== the random MIS shown above
28 ['a09', 'a11', 'a12', 'a08']
29 ...
30 *---- Global result ----
31 Number of choices: 22
32 Number of orbits : 11
33 Labelled representatives:
34 ...
35 ['a09', 'a11', 'a12', 'a08']
36 ...
In our random 3-regular graph instance (see Fig. 3.23), we may thus find eleven non isomorphic kernels with orbit sizes equal to two. We illustrate below the isomorphic twin of the random MIS example shown in Fig. 3.24 .
All graphs and symmetric digraphs admit MISs, hence also kernels.
It is worthwhile noticing that the maximal matchings of a graph correspond bijectively to its line graph’s kernels (see the LineGraph
class).
1>>> from graphs import CycleGraph
2>>> c8 = CycleGraph(order=8)
3>>> maxMatching = c8.computeMaximumMatching()
4>>> c8.exportGraphViz(fileName='maxMatchingcycleGraph',
5... matching=maxMatching)
6 *---- exporting a dot file for GraphViz tools ---------*
7 Exporting to maxMatchingcyleGraph.dot
8 Matching: {frozenset({'v1', 'v2'}), frozenset({'v5', 'v6'}),
9 frozenset({'v3', 'v4'}), frozenset({'v7', 'v8'}) }
10 circo -Tpng maxMatchingcyleGraph.dot -o maxMatchingcyleGraph.png
In the context of digraphs, i.e. oriented graphs, the kernel concept gets much richer and separates from the symmetric MIS concept.
3.3.2.2. Initial and terminal kernels
In an oriented graph context, the internal stability condition of the kernel concept remains untouched; however, the external stability condition gets indeed split up by the orientation into two lateral cases:
A dominant stability condition, where each non selected node is dominated by at least one member of the kernel;
An absorbent stability condition, where each non selected node is absorbed by at least one member of the kernel.
A both internally and dominant, resp. absorbent stable choice is called a dominant or initial, resp. an absorbent or terminal kernel. From a topological perspective, the initial kernel concept looks from the outside of the digraph into its interior, whereas the terminal kernel looks from the interior of a digraph toward its outside. From an algebraic perspective, the initial kernel is a prefix operand, and the terminal kernel is a postfix operand in the kernel equation systems (see Digraph3 advanced topic on bipolar-valued kernel membership characteristics).
Furthermore, as the kernel concept involves conjointly a positive logical refutation (the internal stability) and a positive logical affirmation (the external stability), it appeared rather quickly necessary in our operational developments to adopt a bipolar characteristic [-1,1] valuation domain, modelling negation by change of numerical sign and including explicitly a third median logical value (0) expressing logical indeterminateness (neither positive, nor negative, see [BIS-2000] and [BIS-2004a]).
In such a bipolar-valued context, we call prekernel a choice which is externally stable and for which the internal stability condition is valid or indeterminate. We say that the independence condition is in this case only weakly validated. Notice that all kernels are hence prekernels, but not vice-versa.
In graphs or symmetric digraphs, where there is essentially no apparent ‘ laterality ‘, all prekernels are initial and terminal at the same time. They correspond to what we call holes in the graph. A universal example is given by the complete digraph.
1>>> from digraphs import CompleteDigraph
2>>> u = CompleteDigraph(order=5)
3>>> u
4 *------- Digraph instance description ------*
5 Instance class : CompleteDigraph
6 Instance name : complete
7 Digraph Order : 5
8 Digraph Size : 20
9 Valuation domain : [-1.00 ; 1.00]
10 ---------------------------------
11>>> u.showPreKernels()
12 *--- Computing preKernels ---*
13 Dominant kernels :
14 ['1'] independence: 1.0; dominance : 1.0; absorbency : 1.0
15 ['2'] independence: 1.0; dominance : 1.0; absorbency : 1.0
16 ['3'] independence: 1.0; dominance : 1.0; absorbency : 1.0
17 ['4'] independence: 1.0; dominance : 1.0; absorbency : 1.0
18 ['5'] independence: 1.0; dominance : 1.0; absorbency : 1.0
19 Absorbent kernels :
20 ['1'] independence: 1.0; dominance : 1.0; absorbency : 1.0
21 ['2'] independence: 1.0; dominance : 1.0; absorbency : 1.0
22 ['3'] independence: 1.0; dominance : 1.0; absorbency : 1.0
23 ['4'] independence: 1.0; dominance : 1.0; absorbency : 1.0
24 ['5'] independence: 1.0; dominance : 1.0; absorbency : 1.0
25 *----- statistics -----
26 graph name: complete
27 number of solutions
28 dominant kernels : 5
29 absorbent kernels: 5
30 cardinality frequency distributions
31 cardinality : [0, 1, 2, 3, 4, 5]
32 dominant kernel : [0, 5, 0, 0, 0, 0]
33 absorbent kernel: [0, 5, 0, 0, 0, 0]
34 Execution time : 0.00004 sec.
35 Results in sets: dompreKernels and abspreKernels.
In a complete digraph, each single node is indeed both an initial and a terminal prekernel candidate and there is no definite begin or end of the digraph to be detected. Laterality is here entirely relative to a specific singleton chosen as reference point of view. The same absence of laterality is apparent in two other universal digraph models, the empty and the indeterminate digraph.
1>>> ed = EmptyDigraph(order=5)
2>>> ed.showPreKernels()
3 *--- Computing preKernels ---*
4 Dominant kernel :
5 ['1', '2', '3', '4', '5']
6 independence : 1.0
7 dominance : 1.0
8 absorbency : 1.0
9 Absorbent kernel :
10 ['1', '2', '3', '4', '5']
11 independence : 1.0
12 dominance : 1.0
13 absorbency : 1.0
14 ...
In the empty digraph, the whole set of nodes gives indeed at the same time the unique initial and terminal prekernel. Similarly, for the indeterminate digraph.
1>>> from digraphs import IndeterminateDigraph
2>>> id = IndeterminateDigraph(order=5)
3>>> id.showPreKernels()
4 *--- Computing preKernels ---*
5 Dominant prekernel :
6 ['1', '2', '3', '4', '5']
7 independence : 0.0 # <<== indeterminate
8 dominance : 1.0
9 absorbency : 1.0
10 Absorbent prekernel :
11 ['1', '2', '3', '4', '5']
12 independence : 0.0 # <<== indeterminate
13 dominance : 1.0
14 absorbency : 1.0
Both these results make sense, as in a completely empty or indeterminate digraph, there is no interior of the digraph defined, only a border which is hence at the same time an initial and terminal prekernel. Notice however, that in the latter indeterminate case, the complete set of nodes verifies only weakly the internal stability condition (see above).
Other common digraph models, although being clearly oriented, may show nevertheless no apparent laterality, like odd chordless circuits, i.e. holes surrounded by an oriented cycle -a circuit- of odd length. They do not admit in fact any initial or terminal prekernel.
1>>> from digraphs import CirculantDigraph
2>>> c5 = CirculantDigraph(order=5,circulants=[1])
3>>> c5.showPreKernels()
4 *----- statistics -----
5 digraph name: c5
6 number of solutions
7 dominant prekernels : 0
8 absorbent prekernels: 0
Chordless circuits of even length 2 x k, with k > 1, contain however two isomorphic prekernels of cardinality k which qualify conjointly as initial and terminal candidates.
1>>> c6 = CirculantDigraph(order=6,circulants=[1])
2>>> c6.showPreKernels()
3 *--- Computing preKernels ---*
4 Dominant preKernels :
5 ['1', '3', '5'] independence: 1.0, dominance: 1.0, absorbency: 1.0
6 ['2', '4', '6'] independence: 1.0, dominance: 1.0, absorbency: 1.0
7 Absorbent preKernels :
8 ['1', '3', '5'] independence: 1.0, dominance: 1.0, absorbency: 1.0
9 ['2', '4', '6'] independence: 1.0, dominance: 1.0, absorbency: 1.0
Chordless circuits of even length may thus be indifferently oriented along two opposite directions. Notice by the way that the duals of all chordless circuits of odd or even length, i.e. filled circuits also called anti-holes (see Fig. 3.27), never contain any potential prekernel candidates.
1>>> dc6 = -c6 # dc6 = DualDigraph(c6)
2>>> dc6.showPreKernels()
3 *----- statistics -----
4 graph name: dual_c6
5 number of solutions
6 dominant prekernels : 0
7 absorbent prekernels: 0
8>>> dc6.exportGraphViz(fileName='dualChordlessCircuit')
9 *---- exporting a dot file for GraphViz tools ---------*
10 Exporting to dualChordlessCircuit.dot
11 circo -Tpng dualChordlessCircuit.dot -o dualChordlessCircuit.png
We call weak, a chordless circuit with indeterminate inner part. The CirculantDigraph
class provides a parameter for constructing such a kind of weak chordless circuits.
1>>> c6 = CirculantDigraph(order=6, circulants=[1],
2... IndeterminateInnerPart=True)
It is worth noticing that the dual version of a weak circuit corresponds to its converse version, i.e. -c6 = ~c6 (see Fig. 3.28).
1>>> (-c6).exportGraphViz()
2 *---- exporting a dot file for GraphViz tools ---------*
3 Exporting to dual_c6.dot
4 circo -Tpng dual_c6.dot -o dual_c6.png
5>>> (~c6).exportGraphViz()
6 *---- exporting a dot file for GraphViz tools ---------*
7 Exporting to converse_c6.dot
8 circo -Tpng converse_c6.dot -o converse_c6.png
It immediately follows that weak chordless circuits are part of the class of digraphs that are invariant under the codual transform, cn = - (~ cn ) = ~ ( -cn ).
3.3.2.3. Kernels in lateralized digraphs
Humans do live in an apparent physical space of plain transitive lateral orientation, fully empowered in finite geometrical 3D models with linear orders, where first, resp. last ranked, nodes deliver unique initial, resp. terminal, kernels. Similarly, in finite preorders, the first, resp. last, equivalence classes deliver the unique initial, resp. unique terminal, kernels. More generally, in finite partial orders, i.e. asymmetric and transitive digraphs, topological sort algorithms will easily reveal on the first, resp. last, level all unique initial, resp. terminal, kernels.
In genuine random digraphs, however, we may need to check for each of its MISs, whether one, both, or none of the lateralized external stability conditions may be satisfied. Consider, for instance, the following random digraph instance of order 7 and generated with an arc probability of 30%.
1>>> from randomDigraphs import RandomDigraph
2>>> rd = RandomDigraph(order=7,arcProbability=0.3,seed=5)
3>>> rd.exportGraphViz('randomLaterality')
4 *---- exporting a dot file for GraphViz tools ---------*
5 Exporting to randomLaterality.dot
6 dot -Grankdir=BT -Tpng randomLaterality.dot -o randomLaterality.png
The random digraph shown in Fig. 3.29 above has no apparent special properties, except from being connected (see Line 3 below).
1>>> rd.showComponents()
2 *--- Connected Components ---*
3 1: ['a1', 'a2', 'a3', 'a4', 'a5', 'a6', 'a7']
4>>> rd.computeSymmetryDegree(Comments=True,InPercents=True)
5 Symmetry degree (%) of digraph <randomDigraph>:
6 #arcs x>y: 14, #symmetric: 1, #asymmetric: 13
7 #symmetric/#arcs = 7.1
8>>> rd.computeChordlessCircuits()
9 [] # no chordless circuits detected
10>>> rd.computeTransitivityDegree(Comments=True,InPercents=True)
11 Transitivity degree (%) of graph <randomDigraph>:
12 #triples x>y>z: 23, #closed: 11, #open: 12
13 #closed/#triples = 47.8
The given digraph instance is neither asymmetric (a3 <–> a6) nor symmetric (a2 –> a1, a1 -/> a2) (see Line 6 above); there are no chordless circuits (see Line 9 above); and, the digraph is not transitive (a5 -> a2 -> a1, but a5 -/> a1). More than half of the required transitive closure is missing (see Line 12 above).
Now, we know that its potential prekernels must be among its set of maximal independent choices.
1>>> rd.showMIS()
2 *--- Maximal independent choices ---*
3 ['a2', 'a4', 'a6']
4 ['a6', 'a1']
5 ['a5', 'a1']
6 ['a3', 'a1']
7 ['a4', 'a3']
8 ['a7']
9 ------
10>>> rd.showPreKernels()
11 *--- Computing preKernels ---*
12 Dominant preKernels :
13 ['a2', 'a4', 'a6']
14 independence : 1.0
15 dominance : 1.0
16 absorbency : -1.0
17 covering : 0.500
18 ['a4', 'a3']
19 independence : 1.0
20 dominance : 1.0
21 absorbency : -1.0
22 covering : 0.600 # <<==
23 Absorbent preKernels :
24 ['a3', 'a1']
25 independence : 1.0
26 dominance : -1.0
27 absorbency : 1.0
28 covering : 0.500
29 ['a6', 'a1']
30 independence : 1.0
31 dominance : -1.0
32 absorbency : 1.0
33 covering : 0.600 # <<==
34 ...
Among the six MISs contained in this random digraph (see above Lines 3-8) we discover two initial and two terminal kernels (Lines 12-34). Notice by the way the covering values (between 0.0 and 1.0) shown by the digraphs.Digraph.showPreKernels()
method (Lines 17, 22, 28 and 33). The higher this value, the more the corresponding kernel candidate makes apparent the digraph’s laterality. We may hence redraw the same digraph in Fig. 3.30 by looking into its interior via the best covering initial kernel candidate: the dominant choice {‘a3’,’4a’} (coloured in yellow), and looking out of it via the best covered terminal kernel candidate: the absorbent choice {‘a1’,’a6’} (coloured in blue).
1>>> rd.exportGraphViz(fileName='orientedLaterality',
2... bestChoice=set(['a3', 'a4']),
3... worstChoice=set(['a1', 'a6']))
4*---- exporting a dot file for GraphViz tools ---------*
5 Exporting to orientedLaterality.dot
6 dot -Grankdir=BT -Tpng orientedLaterality.dot -o orientedLaterality.png
In algorithmic decision theory, initial and terminal prekernels may provide convincing best, resp. worst, choice recommendations (see tutorial on computing a best choice recommendation).
3.3.2.4. Computing good and bad choice recommendations
To illustrate this idea, let us finally compute good and bad choice recommendations in the following random bipolar-valued outranking digraph.
1>>> from outrankingDigraphs import *
2>>> g = RandomBipolarOutrankingDigraph(seed=5)
3>>> g
4 *------- Object instance description ------*
5 Instance class : RandomBipolarOutrankingDigraph
6 Instance name : randomOutranking
7 # Actions : 7
8 # Criteria : 7
9 Size : 26
10 Determinateness : 34.275
11 Valuation domain : {'min': -100.0, 'med': 0.0, 'max': 100.0}
12>>> g.showHTMLPerformanceTableau()
The underlying random performance tableau (see Fig. 3.31) shows the performance grading of 7 potential decision actions with respect to 7 decision criteria supporting each an increasing performance scale from 0 to 100. Notice the missing performance data concerning decision actions ‘a2’ and ‘a5’. The resulting strict outranking - i.e. a weighted majority supported - better than without considerable counter-performance - digraph is shown in Fig. 3.32 below.
1>>> gcd = ~(-g) # Codual: the converse of the negation
2>>> gcd.exportGraphViz(fileName='tutOutRanking')
3 *---- exporting a dot file for GraphViz tools ---------*
4 Exporting to tutOutranking.dot
5 dot -Grankdir=BT -Tpng tutOutranking.dot -o tutOutranking.png
All decision actions appear strictly better performing than action ‘a7’. We call it a Condorcet loser and it is an evident terminal prekernel candidate. On the other side, three actions: ‘a1’, ‘a2’ and ‘a4’ are not dominated. They give together an initial prekernel candidate.
1>>> gcd.showPreKernels()
2 *--- Computing preKernels ---*
3 Dominant preKernels :
4 ['a1', 'a2', 'a4']
5 independence : 0.00
6 dominance : 6.98
7 absorbency : -48.84
8 covering : 0.667
9 Absorbent preKernels :
10 ['a3', 'a7']
11 independence : 0.00
12 dominance : -74.42
13 absorbency : 16.28
14 covered : 0.800
With such unique disjoint initial and terminal prekernels (see Line 4 and 10), the given digraph instance is hence clearly lateralized. Indeed, these initial and terminal prekernels of the codual outranking digraph reveal best, resp. worst, choice recommendations one may formulate on the basis of a given outranking digraph instance.
1>>> g.showBestChoiceRecommendation()
2 ***********************
3 Rubis best choice recommendation(s) (BCR)
4 (in decreasing order of determinateness)
5 Credibility domain: [-100.00,100.00]
6 === >> potential first choice(s)
7 * choice : ['a1', 'a2', 'a4']
8 independence : 0.00
9 dominance : 6.98
10 absorbency : -48.84
11 covering (%) : 66.67
12 determinateness (%) : 57.97
13 - most credible action(s) = { 'a4': 20.93, 'a2': 20.93, }
14 === >> potential last choice(s)
15 * choice : ['a3', 'a7']
16 independence : 0.00
17 dominance : -74.42
18 absorbency : 16.28
19 covered (%) : 80.00
20 determinateness (%) : 64.62
21 - most credible action(s) = { 'a7': 48.84, }
Notice that solving bipolar-valued kernel equation systems (see Bipolar-Valued Kernels in the Advanced Topics) provides furthermore a positive characterization of the most credible decision actions in each respective choice recommendation (see Lines 14 and 23 above). Actions ‘a2’ and ‘a4’ are equivalent candidates for a unique best choice, and action ‘a7’ is clearly confirmed as the last choice.
In Fig. 3.33 below, we orient the drawing of the strict outranking digraph instance with the help of these first and last choice recommendations.
1>>> gcd.exportGraphViz(fileName='bestWorstOrientation',
2... bestChoice=['a2','a4'],
3... worstChoice=['a7'])
4 *---- exporting a dot file for GraphViz tools ---------*
5 Exporting to bestWorstOrientation.dot
6 dot -Grankdir=BT -Tpng bestWorstOrientation.dot -o bestWorstOrientation.png
The gray arrows in Fig. 3.33, like the one between actions ‘a4’ and ‘a1’, represent indeterminate preferential situations. Action ‘a1’ appears hence to be rather incomparable to all the other, except action ‘a7’. It may be interesting to compare this result with a Copeland ranking of the underlying performance tableau (see the tutorial on ranking with uncommensurable criteria).
1>>> g.showHTMLPerformanceHeatmap(colorLevels=5, ndigits=0,
2... Correlations=True, rankingRule='Copeland')
In the resulting linear ranking (see Fig. 3.34), action ‘a4’ is set at first rank, followed by action ‘a2’. This makes sense as ‘a4’ shows three performances in the first quintile, whereas ‘a2’ is only partially evaluated and shows only two such excellent performances. But ‘a4’ also shows a very weak performance in the first quintile. Both decision actions, hence, don’t show eventually a performance profile that would make apparent a clear preference situation in favour of one or the other. In this sense, the prekernels based best choice recommendations may appear more faithful with respect to the actually definite strict outranking relation than any ‘forced’ linear ranking result as shown in Fig. 3.34 above.
3.3.2.5. Tractability
Finally, let us give some hints on the tractability of kernel computations. Detecting all (pre)kernels in a digraph is a famously NP-hard computational problem. Checking external stability conditions for an independent choice is equivalent to checking its maximality and may be done in the linear complexity of the order of the digraph. However, checking all independent choices contained in a digraph may get hard already for tiny sparse digraphs of order n > 20 (see [BIS-2006b]). Indeed, the worst case is given by an empty or indeterminate digraph where the set of all potential independent choices to check is in fact the power set of the vertices.
1>>> e = EmptyDigraph(order=20)
2>>> e.showMIS() # by visiting all 2^20 independent choices
3 *--- Maximal independent choices ---*
4 [ '1', '2', '3', '4', '5', '6', '7', '8', '9', '10',
5 '11', '12', '13', '14', '15', '16', '17', '18', '19', '20']
6 number of solutions: 1
7 execution time: 1.47640 sec. # <<== !!!
8>>> 2**20
9 1048576
Now, there exist more efficient specialized algorithms for directly enumerating MISs and dominant or absorbent kernels contained in specific digraph models without visiting all independent choices (see [BIS-2006b]). Alain Hertz provided kindly such a MISs enumeration algorithm for the Digraph3 project (see showMIS_AH()
). When the number of independent choices is big compared to the actual number of MISs, like in very sparse or empty digraphs, the performance difference may be dramatic (see Line 7 above and Line 15 below).
1>>> e.showMIS_AH() # by visiting only maximal independent choices
2 *-----------------------------------*
3 * Python implementation of Hertz's *
4 * algorithm for generating all MISs *
5 * R.B. version 7(6)-25-Apr-2006 *
6 *-----------------------------------*
7 ===>>> Initial solution :
8 [ '1', '2', '3', '4', '5', '6', '7', '8', '9', '10',
9 '11', '12', '13', '14', '15', '16', '17', '18', '19', '20']
10 *---- results ----*
11 [ '1', '2', '3', '4', '5', '6', '7', '8', '9', '10',
12 '11', '12', '13', '14', '15', '16', '17', '18', '19', '20']
13 *---- statistics ----*
14 mis solutions : 1
15 execution time : 0.00026 sec. # <<== !!!
16 iteration history: 1
For more or less dense strict outranking digraphs of modest order, as facing usually in algorithmic decision theory applications, enumerating all independent choices remains however in most cases tractable, especially by using a very efficient Python generator (see independentChoices()
below).
1 def independentChoices(self,U):
2 """
3 Generator for all independent choices with associated
4 dominated, absorbed and independent neighborhoods
5 of digraph instance self.
6 Initiate with U = self.singletons().
7 Yields [(independent choice, domnb, absnb, indnb)].
8 """
9 if U == []:
10 yield [(frozenset(),set(),set(),set(self.actions))]
11 else:
12 x = list(U.pop())
13 for S in self.independentChoices(U):
14 yield S
15 if x[0] <= S[0][3]:
16 Sxgamdom = S[0][1] | x[1]
17 Sxgamabs = S[0][2] | x[2]
18 Sxindep = S[0][3] & x[3]
19 Sxchoice = S[0][0] | x[0]
20 Sx = [(Sxchoice,Sxgamdom,Sxgamabs,Sxindep)]
21 yield Sx
And, checking maximality of independent choices via the external stability conditions during their enumeration (see computePreKernels()
below) provides the effective advantage of computing all initial and terminal prekernels in a single loop (see Line 10 and [BIS-2006b]).
1 def computePreKernels(self):
2 """
3 computing dominant and absorbent preKernels:
4 Result in self.dompreKernels and self.abspreKernels
5 """
6 actions = set(self.actions)
7 n = len(actions)
8 dompreKernels = set()
9 abspreKernels = set()
10 for choice in self.independentChoices(self.singletons()):
11 restactions = actions - choice[0][0]
12 if restactions <= choice[0][1]:
13 dompreKernels.add(choice[0][0])
14 if restactions <= choice[0][2]:
15 abspreKernels.add(choice[0][0])
16 self.dompreKernels = dompreKernels
17 self.abspreKernels = abspreKernels
Back to Content Table
3.3.3. Bipolar-valued kernel membership characteristic vectors
3.3.3.1. Kernel equation systems
Let G(X,R) be a crisp irreflexive digraph defined on a finite set X of nodes and where R is the corresponding {-1,+1}-valued adjacency matrix. Let Y be the {-1,+1}-valued membership characteristic (row) vector of a choice in X. When Y satisfies the following equation system
where for all x in X,
then Y characterises an initial kernel ([SCH-1985p]).
When transposing now the membership characteristic vector Y into a column vector , the following equation system
makes similarly characterise a terminal kernel.
Let us verify this result on a tiny random digraph.
1>>> from digraphs import *
2>>> g = RandomDigraph(order=3,seed=1)
3>>> g.showRelationTable()
4 * ---- Relation Table -----
5 R | 'a1' 'a2' 'a3'
6 ------|---------------------
7 'a1' | -1 +1 -1
8 'a2' | -1 -1 +1
9 'a3' | +1 +1 -1
10>>> g.showPreKernels()
11 *--- Computing preKernels ---*
12 Dominant preKernels :
13 ['a3']
14 independence : 1.0
15 dominance : 1.0
16 absorbency : -1.0
17 covering : 1.000
18 Absorbent preKernels :
19 ['a2']
20 independence : 1.0
21 dominance : -1.0
22 absorbency : 1.0
23 covered : 1.000
It is easy to verify that the characteristic vector [-1, -1, +1] satisfies the initial kernel equation system; a3 gives an initial kernel. Similarly, the characteristic vector [-1, +1, -1] verifies indeed the terminal kernel equation system and hence a2 gives a terminal kernel.
We succeeded now in generalizing kernel equation systems to genuine bipolar-valued digraphs ([BIS-2006_1p]). The constructive proof, found by Marc Pirlot, is based on the following fixpoint equation that may be used for computing bipolar-valued kernel membership vectors,
3.3.3.2. Solving bipolar-valued kernel equation systems
John von Neumann showed indeed that, when a digraph G(X,R) is acyclic with a unique initial kernel K characterised by its membership characteristics vector Yk, then the following double bipolar-valued fixpoint equation
will admit a stable high and a stable low fixpoint solution that converge both to Yk ([SCH-1985p]).
Inspired by this crisp double fixpoint equation, we observed that for a given bipolar-valued digraph G(X,R), each of its dominant or absorbent prekernels Ki in X determines an induced partial graph G(X,R/Ki) which is acyclyc and admits Ki as unique kernel (see [BIS-2006_2p]).
Following the von Neumann fixpoint algorithm, a similar bipolar-valued extended double fixpoint algorithm, applied to G(X,R/Ki), allows to compute hence the associated bipolar-valued kernel characteristic vectors Yi in polynomial complexity.
Algorithm
in : bipolar-valued digraph G(X,R),out : set {Y1, Y2, .. } of bipolar-valued kernel membership characteristic vectors.
enumerate all initial and terminal crisp prekernels K, K2, … in the given bipolar-valued digraph (see the tutorial on Computing Digraph Kernels);
for each crisp initial kernel Ki:
construct a partially determined subgraph G(X,R/Ki) supporting exactly this unique initial kernel Ki;
Use the double fixpoint equation T2 with the partially determined adjacency matrix R/Ki for computing a stable low and a stable high fixpoint;
Determine the bipolar-valued Ki-membership characteristic vector Yi with an epistemic disjunction of the previous low and high fixpoints;
repeat step (2) for each terminal kernel Kj by using the double fixpoint equation T2 with the transpose of the adjacency matrix R/Kj.
Time for a practical illustration.
1>>> from outrankingDigraphs import *
2>>> g = RandomBipolarOutrankingDigraph(Normalized=True,seed=5)
3>>> print(g)
4 *------- Object instance description ------*
5 Instance class : RandomBipolarOutrankingDigraph
6 Instance name : rel_randomperftab
7 # Actions : 7
8 # Criteria : 7
9 Size : 26
10 Determinateness (%) : 67.14
11 Valuation domain : [-1.0;1.0]
12 Attributes : ['name', 'actions', 'criteria', 'evaluation',
13 'relation', 'valuationdomain', 'order',
14 'gamma', 'notGamma']
The random outranking digraph g, we consider here in Listing 3.43 for illustration, models the pairwise outranking situations between seven decision alternatives evaluated on seven incommensurable performance criteria. We compute its corresponding bipolar-valued prekernels on the associated codual digraph gcd.
1>>> gcd = ~(-g) # strict outranking digraph
2>>> gcd.showPreKernels()
3 *--- Computing prekernels ---*
4 Dominant prekernels :
5 ['a1', 'a4', 'a2']
6 independence : +0.000
7 dominance : +0.070
8 absorbency : -0.488
9 covering : +0.667
10 Absorbent prekernels :
11 ['a7', 'a3']
12 independence : +0.000
13 dominance : -0.744
14 absorbency : +0.163
15 covered : +0.800
16 *----- statistics -----
17 graph name: converse-dual_rel_randomperftab
18 number of solutions
19 dominant kernels : 1
20 absorbent kernels: 1
21 cardinality frequency distributions
22 cardinality : [0, 1, 2, 3, 4, 5, 6, 7]
23 dominant kernel : [0, 0, 0, 1, 0, 0, 0, 0]
24 absorbent kernel: [0, 0, 1, 0, 0, 0, 0, 0]
25 Execution time : 0.00022 sec.
The codual outranking digraph, modelling a strict outranking relation, admits an initial prekernel [a1, a2, a4] and a terminal one [a3, a7] (see Listing 3.44 Line 5 and 11).
Let us compute the initial prekernel restricted adjacency table with the domkernelrestrict()
method.
1>>> k1Relation = gcd.domkernelrestrict(['a1','a2','a4'])
2>>> gcd.showHTMLRelationTable(
3... actionsList=['a1','a2','a4','a3','a5','a6','a7'],
4... relation=k1Relation,
5... tableTitle='K1 restricted adjacency table')
We first notice that this initial prekernel is indeed only weakly independent: The outranking situation between a4 and a1 appears indeterminate. The corresponding initial prekernel membership characteristic vector may be computed with the computeKernelVector()
method.
1>>> gcd.computeKernelVector(['a1','a2','a4'],Initial=True,Comments=True)
2 --> Initial prekernel: {'a1', 'a2', 'a4'}
3 initial low vector : [-1.00, -1.00, -1.00, -1.00, -1.00, -1.00, -1.00]
4 initial high vector: [+1.00, +1.00, +1.00, +1.00, +1.00, +1.00, +1.00]
5 1st low vector : [ 0.00, +0.21, -0.21, 0.00, -0.44, -0.07, -0.58]
6 1st high vector : [+1.00, +1.00, +1.00, +1.00, +1.00, +1.00, +1.00]
7 2nd low vector : [ 0.00, +0.21, -0.21, 0.00, -0.44, -0.07, -0.58]
8 2nd high vector : [ 0.00, +0.21, -0.21, +0.21, -0.21, -0.05, -0.21]
9 3rd low vector : [ 0.00, +0.21, -0.21, +0.21, -0.21, -0.07, -0.21]
10 3rd high vector : [ 0.00, +0.21, -0.21, +0.21, -0.21, -0.05, -0.21]
11 4th low vector : [ 0.00, +0.21, -0.21, +0.21, -0.21, -0.07, -0.21]
12 4th high vector : [ 0.00, +0.21, -0.21, +0.21, -0.21, -0.07, -0.21]
13 # iterations : 4
14 low & high fusion : [ 0.00, +0.21, -0.21, +0.21, -0.21, -0.07, -0.21]
15 Choice vector for initial prekernel: {'a1', 'a2', 'a4'}
16 a2: +0.21
17 a4: +0.21
18 a1: 0.00
19 a6: -0.07
20 a3: -0.21
21 a5: -0.21
22 a7: -0.21
We start the fixpoint computation with an empty set characterisation as first low vector and a complete set X characterising high vector. After each iteration, the low vector is set to the negation of the previous high vector and the high vector is set to the negation of the previous low vector.
A unique stable prekernel characteristic vector Y1 is here attained at the fourth iteration with positive members a2: +0.21 and a4: +0.21 (60.5% criteria significance majority); a1: 0.00 being an ambiguous potential member. Alternatives a3, a5, a6 and a7 are all negative members, i.e. positive non members of this outranking prekernel.
Let us now compute the restricted adjacency table for the outranked, i.e. the terminal prekernel [a3, a7].
1>>> k2Relation = gcd.abskernelrestrict(['a3','a7'])
2>>> gcd.showHTMLRelationTable(
3... actionsList=['a3','a7','a1','a2','a4','a5','a6'],
4... relation=k2Relation,
5... tableTitle='K2 restricted adjacency table')
Again, we notice that this terminal prekernel is indeed only weakly independent. The corresponding bipolar-valued characteristic vector Y2 may be computed as follows.
1>>> gcd.computeKernelVector(['a3','a7'],Initial=False,Comments=True)
2 --> Terminal prekernel: {'a3', 'a7'}
3 initial low vector : [-1.00, -1.00, -1.00, -1.00, -1.00, -1.00, -1.00]
4 initial high vector : [+1.00, +1.00, +1.00, +1.00, +1.00, +1.00, +1.00]
5 1st low vector : [-0.16, -0.49, 0.00, -0.58, -0.16, -0.30, +0.49]
6 1st high vector : [+1.00, +1.00, +1.00, +1.00, +1.00, +1.00, +1.00]
7 2nd low vector : [-0.16, -0.49, 0.00, -0.58, -0.16, -0.30, +0.49]
8 2nd high vector : [-0.16, -0.49, 0.00, -0.49, -0.16, -0.26, +0.49]
9 3rd low vector : [-0.16, -0.49, 0.00, -0.49, -0.16, -0.26, +0.49]
10 3rd high vector : [-0.16, -0.49, 0.00, -0.49, -0.16, -0.26, +0.49]
11 # iterations : 3
12 high & low fusion : [-0.16, -0.49, 0.00, -0.49, -0.16, -0.26, +0.49]
13 Choice vector for terminal prekernel: {'a3', 'a7'}
14 a7: +0.49
15 a3: 0.00
16 a1: -0.16
17 a5: -0.16
18 a6: -0.26
19 a2: -0.49
20 a4: -0.49
A unique stable bipolar-valued high and low fixpoint is attained at the third iteration with a7 positively confirmed (about 75% criteria significance majority) as member of this terminal prekernel, whereas the membership of a3 in this prekernel appears indeterminate. All the remaining nodes have negative membership characteristic values and are hence positively excluded from this prekernel.
When we reconsider the graphviz drawing of this outranking digraph (see Fig. 52 in the tutorial on Computing Digraph Kernels),
it becomes obvious why alternative a1 is neither included nor excluded from the initial prekernel. Same observation is applicable to alternative a3 which can neither be included nor excluded from the terminal prekernel. It may even happen, in case of more indeterminate outranking situations, that no alternative is positively included or excluded from a weakly independent prekernel; the corresponding bipolar-valued membership characteristic vector being completely indeterminate (see for instance the tutorial on Computing a Best Choice Recommendation).
To illustrate finally why sometimes we need to operate an epistemic disjunctive fusion of unequal stable low and high membership characteristics vectors (see Step 2.c.), let us consider, for instance, the following crisp 7-cycle graph.
1>>> g = CirculantDigraph(order=7,circulants=[-1,1])
2>>> g
3 *------- Digraph instance description ------*
4 Instance class : CirculantDigraph
5 Instance name : c7
6 Digraph Order : 7
7 Digraph Size : 14
8 Valuation domain : [-1.00;1.00]
9 Determinateness (%) : 100.00
10 Attributes : ['name', 'order', 'circulants', 'actions',
11 'valuationdomain', 'relation',
12 'gamma', 'notGamma']
Digraph c7 is a symmetric crisp digraph showing, among others, the maximal independent set {‘2’, ‘5’, ‘7’}, i.e. an initial as well as terminal kernel. We may compute the corresponding initial kernel characteristic vector.
1>>> g.computeKernelVector(['2','5','7'],Initial=True,Comments=True)
2 --> Initial kernel: {'2', '5', '7'}
3 initial low vector : [-1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0]
4 initial high vector : [+1.0, +1.0, +1.0, +1.0, +1.0, +1.0, +1.0]
5 1 st low vector : [-1.0, 0.0, -1.0, -1.0, 0.0, -1.0, 0.0]
6 1 st high vector : [+1.0, +1.0, +1.0, +1.0, +1.0, +1.0, +1.0]
7 2 nd low vector : [-1.0, 0.0, -1.0, -1.0, 0.0, -1.0, 0.0]
8 2 nd high vector : [ 0.0, +1.0, 0.0, 0.0, +1.0, 0.0, +1.0]
9 stable low vector : [-1.0, 0.0, -1.0, -1.0, 0.0, -1.0, 0.0]
10 stable high vector : [ 0.0, +1.0, 0.0, 0.0, +1.0, 0.0, +1.0]
11 #iterations : 3
12 low & high fusion : [-1.0, +1.0, -1.0, -1.0, +1.0, -1.0, +1.0]
13 Choice vector for initial prekernel: {'2', '5', '7'}
14 2: +1.00
15 5: +1.00
16 7: +1.00
17 1: -1.00
18 3: -1.00
19 4: -1.00
20 6: -1.00
Notice that the stable low vector characterises the negative membership part, whereas, the stable high vector characterises the positive membership part (see Lines 9-10 above). The bipolar disjunctive fusion assembles eventually both stable parts into the correct prekernel characteristic vector (Line 12).
The adjacency matrix of a symmetric digraph staying unchanged by the transposition operator, the previous computations, when qualifying the same kernel as a terminal instance, will hence produce exactly the same result.
Note
It is worthwhile noticing again the essential computational role, the logical indeterminate value 0.0 is playing in this double fixpoint algorithm. To implement such kind of algorithms without a logical neutral term would be like implementing numerical algorithms without a possible usage of the number 0. Infinitely many trivial impossibility theorems and dubious logical results come up.
Back to Content Table
3.3.4. On characterizing bipolar-valued outranking digraphs
3.3.4.1. Necessary properties of the outranking digraph
Bipolar-valued outranking digraphs verify two necessary properties [BIS-2013p]:
They are weakly complete. For all pairs (x, y) of decision actions:
and,
The construction of the outranking relation verifies the coduality principle. For all pairs (x, y) of decision actions, .
Now, the codual of weakly complete digraphs correspond to the class of asymmetric digraphs i.e. partial tournaments. If, on the one limit, all outranking relations are symmetric, the partial tournament will be empty. On the other hand, if the outranking relation models a linear ranking, the tournament will be complete and transitive.
Let us consider for instance such a partial tournament [6].
In Fig. 3.38, only the transitive closure between alternatives a and d is missing. Otherwise, the relation would be modelling a linear ranking from a to d. If this relation is actually supposed to model a strict outranking relation then both alternatives a and d positively outrank each other. Is it possible to build a corresponding valid performance tableau which supports epistemically this partial tournament?
It is indeed possible to define such a performance tableau by, first, using a single criterion g1 of significance weight 2 modelling the apparent linear ranking: a > b > c > d. We can, secondly, add a criterion g2 of significance weight 3 modelling exclusively the missing “as well evaluated as” situation between a and d. Both criteria admit without loss of genericity a performance measurement scale of 0 to 100 points with an indifference discrimination threshold of 2.5 and preference discrimination threshold of 5 points. No considerable performance difference discrimination is needed in this example.
1>>> from outrankingDigraphs import *
2>>> pt = PerformanceTableau('testBouyssou')
3>>> pt.showPerformanceTableau(ndigits=0)
4 *---- performance tableau ----*
5 Criteria | 'g1' 'g2'
6 Actions | 2 3
7 ---------|---------------
8 'a' | 70 70
9 'b' | 50 NA
10 'c' | 30 NA
11 'd' | 10 70
12>>> g = BipolarOutrankingDigraph(pt)
13>>> g.showRelationTable()
14 * ---- Relation Table -----
15 r | 'a' 'b' 'c' 'd'
16 -----|---------------------------
17 'a' | +1.00 +0.40 +0.40 +1.00
18 'b' | -0.40 +1.00 +0.40 +0.40
19 'c' | -0.40 -0.40 +1.00 +0.40
20 'd' | +0.20 -0.40 -0.40 +1.00
21 Valuation domain: [-1.000; 1.000]
In Listing 3.46 Lines 8-11 we notice that criterion g1 models with a majority margin of 2/5 = 0.40 the requested linear ranking and criterion g2 warrants with a majority margin of 1/5 = 0.20 that d is “at least as well evaluated as” d (see Lines 17 and 20) leading to the necessary reciprocal outranking situations between a and d.
It becomes apparent with the partial tournament example here that, when the number of criteria is not constrained, we may model this way compatible pairwise outranking situations independently one of the other.
3.3.4.2. Partial tournaments may be strict outranking digraphs
In the randomDigraphs
module we provide the RandomPartialTournament
class for providing such partial tournament instances.
1>>> from randomDigraphs import RandomPartialTournament
2>>> rpt = RandomPartialTournament(order=5,seed=998)
3>>> rpt.showRelationTable()
4 * ---- Relation Table -----
5 S | 'a1' 'a2' 'a3' 'a4' 'a5'
6 ------|-----------------------------------
7 'a1' | 0.00 1.00 1.00 -1.00 1.00
8 'a2' | -1.00 0.00 1.00 1.00 1.00
9 'a3' | -1.00 -1.00 0.00 1.00 -1.00
10 'a4' | 1.00 -1.00 -1.00 0.00 -1.00
11 'a5' | -1.00 -1.00 -1.00 1.00 0.00
12 Valuation domain: [-1.00;1.00]
13>>> rpt.exportGraphViz()
14 *---- exporting a dot file for GraphViz tools ----*
15 Exporting to randomPartialTournament.dot
16 dot -Grankdir=BT -Tpng randomPartialTournament.dot\
17 -o randomPartialTournament.png
The crisp partial tournament rpt shown in Fig. 3.39 corresponds to the potential strict outranking digraph one may obtain with the following multicriteria performance records measured on 10 criteria admitting a 0-100 scale with a 2.5pts indifference and a 5pts preference discrimination thresholds.
1 *---- performance tableau -----*
2 criteria | weights | 'a1' 'a2' 'a3' 'a4' 'a5'
3 ---------|---------------------------------------
4 'g01' | 1.0 | 60 40 NA NA NA
5 'g02' | 1.0 | 60 NA 40 NA NA
6 'g03' | 1.0 | 40 NA NA 60 NA
7 'g04' | 1.0 | 60 NA NA NA 40
8 'g05' | 1.0 | NA 60 40 NA NA
9 'g06' | 1.0 | NA 60 NA 40 NA
10 'g07' | 1.0 | NA 60 NA NA 40
11 'g08' | 1.0 | NA NA 60 40 NA
12 'g09' | 1.0 | NA NA 50 NA 50
13 'g10' | 1.0 | NA NA NA 40 60
Each one of the ten performance criteria independently models, with a majority margin of 1/10 = 0.10, one of the 10 links between the five nodes of the tournament rpt. Criterion g01 models for instance the asymmetric link between a1 and a2 (Line 4), criterion g9 models the symmetric link between a3 and a5 (Line 12) and so on. The bipolar-valued strict outranking relation we obtain with this performance tableau is the following:
1* ---- Relation Table -----
2 r | 'a1' 'a2' 'a3' 'a4' 'a5'
3 -----|----------------------------------
4 'a1' | - +0.10 +0.10 -0.10 +0.10
5 'a2' | -0.10 - +0.10 +0.10 +0.10
6 'a3' | -0.10 -0.10 - +0.10 -0.10
7 'a4' | +0.10 -0.10 -0.10 - -0.10
8 'a5' | -0.10 -0.10 -0.10 +0.10 -
9 Valuation domain: [-1.000; 1.000]
And we recover here exactly the random partial tournament shown in Fig. 3.39.
To all partial tournament we may this way associate a multicriteria performance tableau, making it hence the instance of a potential bipolar-valued strict outranking digraph. Yet, we have not taken care of reproducing the precise characteristic valuation of a given partial tournament. Is it as well possible to always associate a valid performance tableau which produces a strict outranking digraph with exactly the given characteristic valuation?
3.3.4.3. Recognizing bipolar outranking valuations
From the fact that the epistemic support of a strict outranking –’better evaluated as’– situation is a potential sub-part only of the epistemic support of the corresponding outranking –’at least as well evaluated as’– situation, it follows that for all irreflexive pairs (x, y), , which induces by the coduality principle the following necessary condition on the valuation of a potential outranking digraph:
(3.1)
Condition (3.1) strengthens in fact the weakly completeness property. Indeed:
(3.2)
And,
(3.3)
The bipolar valuation of a valid outranking digraph is hence necessarily characterised by the following condition, algebraically equivalent to Condition (3.1):
(3.4)
It remains to proof that Condition (3.4) is (or is actually not) also sufficient for characterising the valuation of bipolar-valued outranking digraphs. In other words:
Conjecture
For any given bipolar and rational valued digraph verifying (3.4) it is possible to construct with an unconstrained number of criteria a valid performance tableau that results in identically valued pairwise outranking situations.
If the conjecture reveals itself to be true, and we are rather confident that this will indeed be the case, we get a method of complexity for recognizing potential outranking digraph instances with view solely on their relational characteristic valuation (see Listing 3.48 Lines 16-17) [MEY-2008].
1>>> from outrankingDigraphs import *
2>>> t = RandomPerformanceTableau(weightDistribution="equiobjectives",
3... numberOfActions=5,numberOfCriteria=3,
4... missingDataProbability=0.05,seed=100)
5>>> g = BipolarOutrankingDigraph(t)
6>>> g.showRelationTable()
7 * ---- Relation Table -----
8 r | 'a1' 'a2' 'a3' 'a4' 'a5'
9 ------|------------------------------------
10 'a1' | +1.00 -0.33 -0.33 -0.67 -1.00
11 'a2' | +0.33 +1.00 -0.33 +0.00 +0.33
12 'a3' | +1.00 +0.33 +1.00 +0.67 +0.33
13 'a4' | +0.67 +0.00 +0.00 +1.00 +0.67
14 'a5' | +1.00 -0.33 -0.33 -0.67 +1.00
15 Valuation domain: [-1.000; 1.000]
16 >>> g.isOutrankingDigraph()
17 True
Whereas, when we consider in Listing 3.49 a genuine randomly bipolar-valued digraph of order 5, this check will mostly fail.
1>>> rdg = RandomValuationDigraph(order=5)
2>>> rdg.showRelationTable()
3 * ---- Relation Table -----
4 S | 'a1' 'a2' 'a3' 'a4' 'a5'
5------|-------------------------------------------
6 'a1' | 0.00 0.00 -0.68 0.94 0.06
7 'a2' | -0.14 0.00 -0.44 -0.04 0.84
8 'a3' | -0.14 0.12 0.00 -0.10 -0.62
9 'a4' | 0.40 -0.86 0.98 0.00 0.90
10 'a5' | -0.92 0.18 -0.42 0.14 0.00
11 Valuation domain: [-1.00;1.00]
12>>> rdg.isOutrankingDigraph(Debug=True)
13 x,y,relation[x][y],relation[y][x] a1 a2 0.00 -0.14
14 Not a valid outranking valuation
15 x,y,relation[x][y],relation[y][x] a1 a3 -0.68 -0.14
16 Not a valid outranking valuation
17 x,y,relation[x][y],relation[y][x] a1 a5 0.06 -0.92
18 Not a valid outranking valuation
19 x,y,relation[x][y],relation[y][x] a2 a3 -0.44 0.12
20 Not a valid outranking valuation
21 x,y,relation[x][y],relation[y][x] a2 a4 -0.04 -0.86
22 Not a valid outranking valuation
23 x,y,relation[x][y],relation[y][x] a3 a5 -0.62 -0.42
24 Not a valid outranking valuation
25 False
We observe in Lines 13-24 the absence of any relation between a1 and a3, between a2 and a4, and between a3 and a5. This violates the necessary weak completeness Condition (3.2). The pairs (a1, a2) and (a2, a3) furthermore violate Condition (3.3).
A Monte Carlo simulation with randomly bipolar-valued digraphs of order 5 shows that an average proportion of only 0.07% of random instances verify indeed Condition (3.4). With randomly bipolar-valued digraphs of order 6, this proportion drops furthermore to 0.002%. Condition (3.4) is hence a very specific characteristic of bipolar outranking valuations.
Readers challenged by the proof of the sufficiency of Condition (3.4) may find below a bipolar-valued relation verifying (3.4)
1* ---- Relation Table -----
2 r | 'a1' 'a2' 'a3' 'a4' 'a5'
3 -----|----------------------------------
4 'a1' | +1.00 +0.60 +0.60 +0.20 +0.20
5 'a2' | -0.20 +1.00 +0.00 -0.20 +0.20
6 'a3' | -0.40 +0.60 +1.00 +0.20 +0.60
7 'a4' | -0.20 +0.20 -0.20 +1.00 +0.20
8 'a5' | -0.20 +0.00 -0.20 +0.60 +1.00
9Valuation domain: [-1.000; 1.000]
Is it possible to construct a corresponding performance tableau giving exactly the shown valuation? Hint: the criteria may be equi-significant [7].
Solving the previous problem requires to choose an adequate number of criteria. This raises the following question:
What is the minimal number of criteria needed in a performance tableau that corresponds to the valuation of a given bipolar-valued outranking digraph.
We call this number the epistemic dimension of the bipolar-valued outranking digraph. This dimension depends naturally on the potential presence of chordless outranking cycles and indeterminate outranking situations. A crisp linear outranking digraph, for instance, can be modelled with a single performance criterion and is hence of dimension 1. Designing an algorithm for determining epistemic dimensions remains an open challenge.
Let us finally mention that the dual –the negation– of Condition (3.4) characterizes strict outranking valuations. Indeed, by verifying the coduality principle:
we obtain the following condition:
(3.5)
A similar Monte Carlo simulation with randomly bipolar-valued digraphs of order 5 shows that an average proportion of only 0.12% of random instances verify Condition (3.5). With randomly bipolar-valued digraphs of order 6, this proportion drops to 0.006%. Condition (3.5) is hence again a very specific characteristic of bipolar strict outranking valuations.
3.3.4.4. On generating random outranking valuations
The RandomOutrankingValuationDigraph
class from the randomDigraphs
module provides a generator for random outranking valuation digraphs.
1>>> from randomDigraphs import RandomOutrankingValuationDigraph
2>>> rov = RandomOutrankingValuationDigraph(order=5,
3... weightsSum=10,
4... distribution='uniform',
5... incomparabilityProbability=0.1,
6... polarizationProbability=0.05,
7... seed=1)
8>>> rov.showRelationTable()
9 * ---- Relation Table -----
10 S | 'a1' 'a2' 'a3' 'a4' 'a5'
11 ------|-----------------------------------
12 'a1' | 10 -2 10 4 4
13 'a2' | 10 10 10 4 10
14 'a3' | -10 -10 10 0 8
15 'a4' | -4 -3 0 10 8
16 'a5' | 2 -10 2 3 10
17 Valuation domain: [-10;+10]
18>>> rov.isOutrankingDigraph()
19 True
The generator works like this. For each link between , first a random integer number is uniformly drawn for in the given range (see Listing 3.50 Line 3). Then, is uniformly drawn in the remaining integer interval .
In order to favour a gathering around the median zero characteristic value, it is possible to use a triangular law instead (see Line 4).
For inserting random considerable performance difference situations, it is possible to define the probabilities of incomparability (default 10%, see Line 5) and/or polarized outranking situations (5%, see Line 6).
The resulting valuation (see Lines 12-16) verifies indeed condition (3.4) (see Lines 18-19).
Back to Content Table
3.3.5. Consensus quality of the bipolar-valued outranking relation
3.3.5.1. Circular performance tableaux
In order to study the actual consensus quality of a bipolar-valued outranking relation, let us consider a small didactic performance tableau consisting of five decision actions evaluated with respect to five performance criteria of equal significance. On each one of the criteria, we swap first and last ranked evaluations in a circular way (see Lines 8-12 below).
1>>> from perfTabs import CircularPerformanceTableau
2>>> cpt5 = CircularPerformanceTableau(order=5,NoPolarisation=True)
3>>> cpt5.showPerformanceTableau()
4 *---- performance tableau -----*
5 Criteria | 'g1' 'g2' 'g3' 'g4' 'g5'
6 Actions | 1 1 1 1 1
7 ---------|-----------------------------------------
8 'a1' | 0.00 80.00 60.00 40.00 20.00
9 'a2' | 20.00 0.00 80.00 60.00 40.00
10 'a3' | 40.00 20.00 0.00 80.00 60.00
11 'a4' | 60.00 40.00 20.00 0.00 80.00
12 'a5' | 80.00 60.00 40.00 20.00 0.00
In Listing 3.51 Line 2, we do not consider for the moment any considerable performance differences. A performance difference up to 2.5 is considered insignificant, whereas a performance difference of 5.0 and more is attesting a preference situation.
1>>> cpt5.showCriteria()
2 *---- criteria -----*
3 g1 RandomPerformanceTableau() instance
4 Preference direction: max
5 Scale = (0.00, 100.00)
6 Weight = 0.200
7 Threshold ind : 2.50 + 0.00x ; percentile: 0.00
8 Threshold pref : 5.00 + 0.00x ; percentile: 0.00
9 g2 RandomPerformanceTableau() instance
10 ...
All the five decision alternatives show in fact a same performance profile, yet distributed differently on the criteria which are equally significant. The preferential information of such a circular performance tableau does hence not deliver any clue for solving a selection or a ranking decision problem.
Let us inspect the corresponding bipolar-valued outranking digraph.
1>>> from outrankingDigraphs import BipolarOutrankingDigraph
2>>> bodg = BipolarOutrankingDigraph(cpt5)
3>>> bodg.exportGraphViz()
4 *---- exporting a dot file for GraphViz tools ----*
5 Exporting to rel_circular-5-PT.dot
6 dot -Grankdir=BT -Tpng rel_circular-5-PT.dot\
7 -o rel_circular-5-PT.png
In Fig. 3.40 we notice that the outranking digraph models in fact a complete and regular tournament. Each alternative is outranking, respectively outranked by two other alternatives. The outranking relation is not transitive -half of the transitivity arcs are missing- and we observe five equally credible outranking circuits.
1>>> bodg.computeTransitivityDegree()
2 Decimal('0.5')
3>>> bodg.computeChordlessCircuits()
4>>> bodg.showChordlessCircuits()
5 *---- Chordless circuits ----*
6 5 circuits.
7 1: ['a1', 'a4', 'a3'] , credibility : 0.200
8 2: ['a1', 'a4', 'a2'] , credibility : 0.200
9 3: ['a1', 'a5', 'a3'] , credibility : 0.200
10 4: ['a2', 'a5', 'a3'] , credibility : 0.200
11 5: ['a2', 'a5', 'a4'] , credibility : 0.200
3.3.5.2. A difficult decision problem
Due to the regular tournament structure, the Copeland scores are the same for each one of the decision alternatives and we end up with a ranking in alphabetic order.
1>>> from linearOrders import *
2>>> cop = CopelandRanking(bodg,Comments=True)
3 Copeland scores
4 a1 : 0
5 a2 : 0
6 a3 : 0
7 a4 : 0
8 a5 : 0
9 Copeland Ranking:
10 ['a1', 'a2', 'a3', 'a4', 'a5']
Same situation appears below with the NetFlows scores.
1>>> nf = NetFlowsOrder(bodg,Comments=True)
2 Net Flows :
3 a1 : 0.000
4 a2 : 0.000
5 a3 : 0.000
6 a4 : 0.000
7 a5 : 0.000
8 NetFlows Ranking:
9 ['a1', 'a2', 'a3', 'a4', 'a5']
Yet, when inspecting in Fig. 3.40 the outranking relation, we may notice that, when ignoring for a moment the upward arcs, an apparent downward ranking [‘a5’, ‘a4’, ‘a3’, ‘a2’, ‘a1’] comes into view. We can try to recover this ranking with the help of the Kemeny ranking rule.
1>>> ke = KemenyRanking(bodg)
2>>> ke.maximalRankings
3 [['a5', 'a4', 'a3', 'a2', 'a1'],
4 ['a4', 'a3', 'a2', 'a1', 'a5'],
5 ['a3', 'a2', 'a1', 'a5', 'a4'],
6 ['a2', 'a1', 'a5', 'a4', 'a3'],
7 ['a1', 'a5', 'a4', 'a3', 'a2']]
The Kemeny rule delivers indeed five optimal rankings which appear to be the circular versions of the apparent downward ranking [‘a5’, ‘a4’, ‘a3’, ‘a2’, ‘a1’].
The epistemic disjunctive fusion of these five circular rankings gives again an empty relation (see Fig. 3.41 below).
1>>> from transitiveDigraphs import RankingsFusionDigraph
2>>> wke = RankingsFusionDigraph(bodg,ke.maximalRankings)
3>>> wke.exportGraphViz()
All ranking rules based on the bipolar-valued outranking digraph apparently deliver the same result: no effective ranking is possible. When the criteria are supposed to be equally significant, each decision alternative is indeed equally well performing from a multicriteria point of view (see Fig. 3.42).
1>>> cpt5.showHTMLPerformanceHeatmap(Correlations=False,
2... rankingRule=None,ndigits=0,
3... pageTitle='The circular performance tableau')
The pairwise outranking relation shown in Fig. 3.40 does hence represent a faithful consensus of the preference modelled by each one of the five performance criteria. We can inspect the actual quality of this consensus with the help of the bipolar-valued equivalence index (see the advanced topic on the ordinal correlation between bipolar-valued digraphs).
3.3.5.3. The central CONDORCET point of view
The bipolar-valued outranking relation corresponds in fact to the median of the multicriteria points of view, at minimal KENDALL’s ordinal correlation distance from all marginal criteria points of view [BAR-1980p].
1>>> bodg.computeOutrankingConsensusQuality(Comments=True)
2 Consensus quality of global outranking:
3 criterion (weight): valued correlation
4 --------------------------------------
5 g5 (0.200): +0.200
6 g4 (0.200): +0.200
7 g3 (0.200): +0.200
8 g2 (0.200): +0.200
9 g1 (0.200): +0.200
10 Summary:
11 Weighted mean marginal correlation (a): +0.200
12 Standard deviation (b) : +0.000
13 Ranking fairness (a)-(b) : +0.200
As all the performance criteria are supposed to be equally significant, the bipolar-valued equivalence index of the outranking relation with each marginal criterion is at constant level +0.200 (see Listing 3.52).
Let us compute the pairwise ordinal correlation indices between each one the five criteria, including the median outranking relation.
1>>> from digraphs import CriteriaCorrelationDigraph
2>>> cc = CriteriaCorrelationDigraph(bodg,WithMedian=True)
3>>> cc.showRelationTable()
4 * ---- Relation Table -----*
5 S | 'g1' 'g2' 'g3' 'g4' 'g5' 'm'
6 ------|------------------------------------
7 'g1' | 1.00 0.20 -0.20 -0.20 0.20 0.20
8 'g2' | 0.20 1.00 0.20 -0.20 -0.20 0.20
9 'g3' | -0.20 0.20 1.00 0.20 -0.20 0.20
10 'g4' | -0.20 -0.20 0.20 1.00 0.20 0.20
11 'g5' | 0.20 -0.20 -0.20 0.20 1.00 0.20
12 'm' | 0.20 0.20 0.20 0.20 0.20 0.40
13 Valuation domain: [-1.00;1.00]
We observe the same circular arrangement of the pairwise criteria correlations as the one observed in the circular performance tableau. We may draw a 3D principal plot of this correlation space.
1>>> cc.exportPrincipalImage(plotFileName='correlation3Dplot')
In Fig. 3.43 , the median outranking relation m is indeed situated exactly in the middle of the regular pentagon of the marginal criteria.
What happens now when we observe imprecise performance evaluations, considerable performance differences, unequal criteria significance weights and missing evaluations? Let us therefore redo the same computations, but with a corresponding random 3-Objectives performance tableau.
1>>> from randomPerfTabs import\
2... Random3ObjectivesPerformanceTableau
3>>> pt3Obj = Random3ObjectivesPerformanceTableau(
4... numberOfActions=7,numberOfCriteria=13,
5... missingDataProbability=0.05,seed=1)
6>>> pt3Obj.showObjectives()
7 Eco: Economical aspect
8 ec01 criterion of objective Eco 18
9 ec05 criterion of objective Eco 18
10 ec09 criterion of objective Eco 18
11 ec10 criterion of objective Eco 18
12 Total weight: 72.00 (4 criteria)
13 Soc: Societal aspect
14 so02 criterion of objective Soc 12
15 so06 criterion of objective Soc 12
16 so07 criterion of objective Soc 12
17 so11 criterion of objective Soc 12
18 so12 criterion of objective Soc 12
19 so13 criterion of objective Soc 12
20 Total weight: 72.00 (6 criteria)
21 Env: Environmental aspect
22 en03 criterion of objective Env 24
23 en04 criterion of objective Env 24
24 en08 criterion of objective Env 24
25 Total weight: 72.00 (3 criteria)
26>>> from outrankingDigraphs import\
27... BipolarOutrankingDigraph,
28... CriteriaCorrelationDigraph
29>>> g3Obj = BipolarOutrankingDigraph(pt3Obj)
30>>> cc3Obj = CriteriaCorrelationDigraph(g3Obj,
31... ValuedCorrelation=True,WithMedian=True)
32>>> cc3Obj.saveCSV('critCorrTable.csv')
33>>> cc3Obj.exportPrincipalImage(
34... plotFileName='correlation3Dplot-3Obj')
The global outranking relation m remains well situated in the weighted center of the eleven marginal criteria outranking relations. The global outranking relation ‘m’ is indeed mostly correlated with criteria: ‘ec04’ (+0.333), ‘ec06’ (+0.295), ‘en03’ (+0.243) and ‘ec01’ (+0.232) (see Fig. 3.45).
1>>> criteriaList = [x for x in cc3Obj.actions]
2>>> criteriaList.sort()
3>>> cc3Obj.showHTMLRelationTable(actionsList=criteriaList,
4... tableTitle='Valued criteria correlation table',
5... ReflexiveTerms=True,relationName='tau(x,y)',ndigits=3)
Let us conclude by showing in Listing 3.54 how to draw with the R statistics software the dendogram of a hierarchical clustering of the previous relational equivalence table. We use therefore the criteria correlation digraph cc3Obj saved in CSV format (see Listing 3.53 Line 32).
1> x = read.csv('critCorrTable.csv',row.names=1)
2> X = as.matrix(x)
3> dd = dist(X,method='euclidian')
4> hc = hclust(dd)
5> plot(hc)
Fig. 3.46 confirms the actual relational equivalence structure of the marginal criteria outrankings and the global outranking relation. Environmental and economic criteria (left in Fig. 3.44) are opposite to the societal criteria (right in Fig. 3.44). This opposition results in fact from the random generator profile of the given seven decision alternatives as shown in Listing 3.55 below [8].
1>>> pt3Obj.showActions()
2 *----- show decision action -----*
3 key: p1
4 name: public policy p1 Eco+ Soc- Env+
5 profile: {'Eco':'good', 'Soc':'weak', 'Env':'good'}
6 key: p2
7 name: public policy p2 Eco~ Soc+ Env~
8 profile: {'Eco':'fair', 'Soc':'good', 'Env':'fair'}
9 key: p3
10 name: public policy p3 Eco~ Soc~ Env-
11 profile: {'Eco':'fair', 'Soc':'fair', 'Env':'weak'}
12 key: p4
13 name: public policy p4 Eco~ Soc+ Env+
14 profile: {'Eco':'fair', 'Soc':'good', 'Env':'good'}
15 key: p5
16 name: public policy p5 Eco~ Soc+ Env~
17 profile: {'Eco':'fair', 'Soc':'good', 'Env':'fair'}
18 key: p6
19 name: public policy p6 Eco~ Soc- Env+
20 profile: {'Eco':'fair', 'Soc':'weak', 'Env':'good'}
21 key: p7
22 name: public policy p7 Eco- Soc~ Env~
23 profile: {'Eco':'weak', 'Soc':'fair', 'Env':'fair'}
Back to Content Table
3.4. Appendix
3.4.1. Bibliography
Bisdorff R. (2015). “The EURO 2004 Best Poster Award: Choosing the Best Poster in a Scientific Conference”. Chapter 5 in R. Bisdorff, L. Dias, P. Meyer, V. Mousseau, and M. Pirlot (Eds.), Evaluation and Decision Models with Multiple Criteria: Case Studies. Springer-Verlag Berlin Heidelberg, International Handbooks on Information Systems, DOI 10.1007/978-3-662-46816-6_1, pp. 117-166 (downloadable PDF file 754.7 kB).
Bisdorff R., Meyer P. and Veneziano Th. (2014). “Elicitation of criteria weights maximising the stability of pairwise outranking statements”. Journal of Multi-Criteria Decision Analysis (Wiley) 21: 113-124 (downloadable preprint PDF file 431.4 Kb).
Bisdorff R. (2013) “On Polarizing Outranking Relations with Large Performance Differences” Journal of Multi-Criteria Decision Analysis (Wiley) 20:3-12 (downloadable preprint PDF file 403.5 Kb).
Baujard A., Gavrel F., Igersheim H., Laslier J.-F. and Lebon I. (2013). “Approval Voting, Evaluation Voting: An Experiment during the 2012 French Presidential Election”. In Revue Économique (Presses de Sciences Po) Volume 64, Issue 2, pp. 345-356 (dowloadable English translation, 652.5 kB).
Bisdorff R. (2012). “On measuring and testing the ordinal correlation between bipolar outranking relations”. In Proceedings of DA2PL’2012 From Multiple Criteria Decision Aid to Preference Learning, University of Mons 91-100. (downloadable preliminary version PDF file 408.5 kB ).
Balinski M. and Laraki R. (2011) , Majority Judgment : Measuring, Ranking, and Electing, MIT Press, mars 2011, 1re éd. 448 p. ISBN 978-0-262-01513-4
Bisdorff R., Meyer P. and Roubens M.(2008) “RUBIS: a bipolar-valued outranking method for the choice problem”. 4OR, A Quarterly Journal of Operations Research Springer-Verlag, Volume 6, Number 2 pp. 143-165. (Online) Electronic version: DOI: 10.1007/s10288-007-0045-5 (downloadable preliminary version PDF file 271.5Kb).
Meyer P., Marichal J.-L. and Bisdorff R. (2008). Disagregation of bipolar-valued outranking relations. In Modelling, Computation and Optimization in Information Systems and Management Sciences, H. A. Le Thi, P. Bouvry, and D. Pham (eds), Springer CCIS 14 204-213, ISBN 978-3-540-87476-8 (preliminary version PDF file 129.9Kb
Bisdorff R., Pirlot M. and Roubens M. (2006). “Choices and kernels from bipolar valued digraphs”. European Journal of Operational Research, 175 (2006) 155-170. (Online) Electronic version: DOI:10.1016/j.ejor.2005.05.004 (downloadable preliminary version PDF file 257.3Kb).
Bisdorff R. (2006). “On enumerating the kernels in a bipolar-valued digraph”. Annales du Lamsade 6, Octobre 2006, pp. 1 - 38. Université Paris-Dauphine. ISSN 1762-455X (downloadable version PDF file 532.2 Kb).
Bisdorff R. (2004). “Concordant Outranking with multiple criteria of ordinal significance”. 4OR, Quarterly Journal of the Belgian, French and Italian Operations Research Societies, Springer-Verlag, Issue: Volume 2, Number 4, December 2004, Pages: 293 - 308. [ISSN: 1619-4500 (Paper) 1614-2411 (Online)] Electronic version: DOI: 10.1007/s10288-004-0053-7 (downloadable preliminary version PDF file 137.1Kb)
Bisdorff R. (2004). Preference aggregation with multiple criteria of ordinal significance. In: D. Bouyssou, M. Janowitz, F. Roberts, and A. Tsouki´s (eds.), Annales du LAMSADE, 3, Octobre 2004, Université Paris-Dauphine, pp. 25-44 [ISSN 1762-455X] (downloadable PDF file 167.6Kb).
Schmidt G. and Ströhlein Th. (1985), “On kernels of graphs and solutions of games: a synopsis based on relations and fixpoints”. SIAM, J. Algebraic Discrete Methods, 6:54–65.
Barbut M. (1980), “Médianes, Condorcet et Kendall”. Mathématiques et Sciences Humaines, 69:9–13.
Kendall M.G. (1938), “A New Measure of Rank Correlation”. Biometrica 30:81–93
Benyaoun S., Roy B. and Sussmann B. (1966), ELECTRE: une méthode pour guider le choix en présence de points de vue multiples. Tech. Rep. 49, SEMA Direction Scientifique Paris.
Condorcet, J.A.N. de Caritat marquis de (1785), Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix, Imprimerie royale Paris, https://gallica.bnf.fr/ark:/12148/bpt6k417181/f4.item
Brian E. (2008), “Condorcet and Borda in 1784. Misfits and Documents”, Journal Electronique d’Histore des Probabilités et de la Statistique, Vol 4, n°1, Juin/June 2008, https://www.jehps.net/