Raymond Bisdorff

On enumerating the kernels in a bipolar-valued outranking digraph

Keywords: Graph Theory, Maximum Independent Sets, Enumerating Kernels, Outranking Digraphs

On enumerating the kernels in a bipolar-valued outranking digraph

Introduction

Minimal independent and outranking or outranked choices, i.e. kernels, in valued outranking digraphs are an essential formal tool for solving best unique choice problems in the context of our multicriteria decision aid methodology [START_REF] Bisdorff | RuBy: A bipolar-valued outranking method for the best choice decision problem[END_REF]. It appears, following recent formal results [START_REF] Bisdorff | Choices and kernels in bipolar valued digraphs[END_REF], that computing these kernels may rely on the enumeration of all kernels observed in the associated crisp median cut outranking digraph. Knowing these crisp kernels allows one to compute the associated bipolar-valued kernel via the fixpoints of the kernel bipolar-valued characteristic equation systems. In this article we shall therefore, first, present the bipolar-valued concepts of outranking digraphs and independent outranking and outranked choices, each associated with their corresponding median cut crisp concept. In a second section, we shall then discuss general algorithms for enumerating crisp outranking and/or outranked choices in a bipolar-valued digraph. A third section will be devoted to extending these algorithms in order to compute the corresponding bipolar-valued choices.

Kernels in bipolar valued directed graphs

In this first section we introduce the fundamental concepts and notations about bipolarvalued outranking graphs and kernels.

Bipolar-valued credibility calculus

Let ξ be a propositional statement like -decision alternative a is a best choice -ordecision alternative a is at least as good as decision alternative b. In a decision process, a decision maker may either accept or reject these statements following his degree of confidence in their truth [START_REF] Bisdorff | Logical foundation of fuzzy preferential systems with application to the Electre decision aid methods[END_REF].

Definition 1 (Bipolar-valued credibility calculus)

The degree of confidence in the truth -the credibility -of a statement may be represented with the help of a rational credibility scale L = [-1 , 1] supporting the following truthdenotation semantics:

1. Let r ∈ L denote the credibility of a statement ξ. If r = +1 (resp. r = -1) then it is assumed that ξ is certainly true (resp. false). If 0 < r < +1 (resp. -1 < r < 0) then it is assumed that ξ is more true than false (resp. more false than true). If r = 0 then ξ is logically undetermined, i.e. ξ could be either true or false;

2. Let ξ and ψ be two propositional statements to which are associated credibilities r and s ∈ L. If r > s > 0 (resp. r < s < 0) then it is assumed that the truth (resp. falsity) of ξ is more credible than that of ψ;

3. Let ξ and ψ be two propositional statements to which are associated credibilities r and s ∈ L. The truthfulness of the disjunction ξ ∨ ψ (resp. the conjunction ξ ∧ ψ) of these statements corresponds to the maximum of their credibilities: max(r, s) (resp. the minimum of their credibilities: min(r, s)).

4. If r ∈ L denotes the degree of confidence in the truth of a propositional statement ξ, then -r ∈ L denotes the degree of confidence in its untruth, i.e. the credibility of the logical negation of ξ (¬ξ).

The credibility degree associated with the truth of a propositional statement ξ and defined in a credibility domain L verifying properties (1) to (4), will be called a bipolar-valued characterisation of ξ.

A consequence of Definition 1 is that the graduation of confidence degrees concerns necessarily at the same time the affirmation as well as the negation of a propositional statement [START_REF] Windelband | Beiträge zur Lehre vom negativen Urteil[END_REF]. Starting from +1 (certainly true) and -1 (certainly false) one can approach the central undetermined degree of credibility 0 by a gradual weakening of the degrees of confidence. This central point in L is a so-called negational fixpoint [6; 7].

Definition 2

The degree of logical determination ( determinateness for short) D(ξ) of a propositional statement ξ is given by the absolute value of its bipolar-valued characterisation: D(ξ) = |r|.

For both a certainly true and a certainly false statement, the determinateness will be 1. On the contrary, for an undetermined statement, this determinateness will be 0.

This clearly establishes the central degree 0 as an important neutral value in the bipolar credibility calculus. Propositions characterised with this degree 0 may be seen, either as suspended, or as missing statements [START_REF] Bisdorff | Logical Foundation of Multicriteria Preference Aggregation[END_REF]. This situation corresponds to what we call a suspension of judgment. It is a temporary delay in characterising the actual truth or falsity of a propositional statement, which may become eventually determined, either as a more true than false, or as a more false than true statement, in a later stage of the decision aiding process.

We will now define the concept of bipolar-valued outranking digraph.

The bipolar-valued outranking digraph

Our starting point is a decision aiding problem on a finite set X = {x, y, z, . . .} of decision objects (or alternatives), evaluated on a finite, coherent family F = {1, . . . , p} of p criteria. To each criterion j of F is associated its significance represented by a rational number w j from the open interval ]0, 1[ such that p j=1 w j = 1. Besides, to each criterion j is connected a rational (normalised) preference scale in [0, 1] which allows to compare the performances of the decision objects on the corresponding preference dimension. Let g j (x) and g j (y) be the performances of two alternatives x and y of X on criterion j. The difference of the performances g j (x)g j (y) is written ∆ j (x, y). Each preference scale for each criterion j supports a rational indifference threshold h j ∈ [0, 1[, a weak preference threshold q j ∈ [h j , 1[, a weak veto threshold wv j ∈ [q j , 1] ∪ {2} and a strong veto threshold v j ∈ [wv j , 1] ∪ {2}, where the complete absence of veto is modelled via the value 2.

Classically, an outranking situation x S y between two decision alternatives x and y of X is assumed to hold if there is a sufficient majority of criteria which support an "at least as good" preferential statement and there is no criterion which raises a veto against it [START_REF] Roy | Méthodologie multicritère d'aide à la décision[END_REF]. As we are going to show, this definition leads quite naturally to a bipolar-valued characterisation of binary outranking statements. Indeed, in order to characterise a local "at least as good" situation between alternatives x and y of X on each criterion j ∈ F , we use the following criterion-function: C j : X × X → {-1, 0, 1} such that:

C j (x, y) =      1 if ∆ j (x, y) > -h j ; -1 if ∆ j (x, y) ≤ -q j ; 0 otherwise .
Following the truth-denotation semantics of the bipolar-valued characterisation, determinateness 0 is assigned to C j (x, y) in case it cannot be determined whether alternative x is at least as good as alternative y or not (see Subsection 1.1).

Similarly, the local veto situation on each criterion j ∈ F is characterised via a criterion based veto-function: V j : X × X → {-1, 0, 1} where:

V j (x, y) =      1 if ∆ j (x, y) ≤ -v j ; -1 if ∆ j (x, y) > -wv j ; 0 otherwise .
According again to the semantics of the bipolar-valued characterisation, the veto function V j renders a logically undetermined response when the loss in performances between two alternatives lies in between the weak and the strong veto thresholds wv j and v j .

The global outranking index S, defined between all pairs of alternatives x, y ∈ X, conjunctively combines a global concordance index -aggregating all local "at least as good" statements -, and the absence of a veto observed on an individual criterion.

S(x, y) = min{ C(x, y), -V 1 (x, y), . . . , -V p (x, y)}, (1)
where the global concordance index C(x, y) is defined as follows:

C(x, y) = j∈F w j • C j (x, y) ∀x, y ∈ X. (2)
The min operator in Formula (1) translates the conjunction between the global concordance index C(x, y) and the negated criterion based veto indexes -V j (x, y) (∀j ∈ F ). in the case of absence of veto, the resulting outranking index S equals the global concordance index C. Following Formulas ( 1) and ( 2), S is a function from X × X to L representing the degree of confidence in the truth of the outranking situation observed between each pair of alternatives. S will be called the bipolar-valued characterisation of the outranking situation S, or for short a bipolar-valued outranking relation.

The maximum possible value of the valuation S(x, y) = +1 is reached in the case of unanimous concordance, whereas the minimum value S(x, y) = -1 is obtained either in the case of unanimous discordance, or if we observe a veto situation on some criterion. The median situation 0 represents a case of indeterminateness: either there are neither enough arguments in favour nor against a given outranking statement or, a potentially sufficient majority in favour of the outranking is outbalanced by an undetermined, i.e. potential veto situation.

We can easily recover the truth-denotation semantics from the previous Subsection (1.1). For any two alternatives x and y of X, -S(x, y) = +1 signifies that the statement "x S y" is certainly true; -S(x, y) > 0 signifies that statement "x S y" is more true than false. A sufficient majority of criteria warrants the truth of the outranking;

-S(x, y) = 0 signifies that statement "x S y" is logically undetermined, i.e. could be either true or false;

-S(x, y) < 0 signifies that assertion "x S y" is more false than true. There is only a minority of the criteria which warrants the truth of the outranking. This is equivalent to saying that a sufficient majority of criteria warrants the truth of the negation of the outranking; -S(x, y) = -1 signifies that assertion "x S y" is certainly false.

Definition 3

The set X associated to a bipolar-valued characterisation S of the outranking relation S ∈ X × X is called a bipolar-valued outranking digraph, denoted G(X, S).

From the truth-denotation semantics of a bipolar-valued characterisation it results that we can recover the crisp outranking S characterised via S as the set of pairs (x, y) such that S(x, y) > 0. We write G(X, S) the corresponding so-called strict 0-cut crisp outranking digraph associated to G(X, S).

Example 1

In order to illustrate the concept of bipolar-valued outranking graph, we consider a set X 1 = {a, b, c, d, e} of five decision alternatives evaluated on a coherent family F 1 = {1, . . . , 5} of five criteria of equal significance. On each criterion we observe a rational preference scale from 0 to 1 with an indifference threshold of 0.1, a preference threshold of 0.2, a weak veto threshold of 0.6, and a veto threshold of 0.8. Table 1 shows a randomly generated performance table [START_REF] Bisdorff | The Python digraph implementation for RuBy: User Manual[END_REF]. Based on the performances of the five al-

digraph G 1 (X 1 , S 1
) is shown in figure 1. We have also represented the undetermined arc from alternative e to d which represents an undetermined outranking. This situation is not expressible in a standard Boolean-valued characterisation of the outranking. Consequently, the ('positive') negation of the general S relation is not identical with the complement of S in X × X.

Let us finish this subsection by introducing some concepts which will be used in the sequel.

A bipolar-valued digraph G(X, S) such that S(x, y) > 0 for all x, y in X will be called determined. If S(x, y) = 0 for some pairs (x, y), we call G partly determined.

The order n of the digraph G(X, S) is given by the cardinality of X, whereas the size m of G is given by the cardinality of S. As X is a finite set of n alternatives, the size m of the digraph G is also finite. The arc density δ of G is given by the ratio of the size over the maximal number of possible arcs in the graph:

δ = m n × n (3)
In example 1, the order of G 1 equals 5 and its size 13, such that its arc density is 52%.

A digraph G(X, S) is said to be empty if the size of G(X, S) equals 0, i.e. S = ∅. On the opposite, a digraph G(X, S) is said to be complete if G(X, S) = K n , i.e. S = X × X. A digraph G(X, S) of order n is said to be connected if the symmetric and transitive closure of G(X, S) equals K n .

A path of order m ≤ n in G(X, S) is a sequence (x i ) m i=1 of alternatives of X such that S(x i , x i+1 ) 0, ∀i ∈ {1, . . . , m -1}. A circuit of order m ≤ n is a path of order m such that S(x m , x 1 ) ≥ 0. An cordless circuit (x i ) m i=1 is a circuit of order m such that S(x i , x i+1 ) 0, ∀i ∈ {1, . . . , m -1}, S(x m , x 1 ) 0 and S(x i , x j ) < 0 otherwise. A path or circuit will be called weak when it contains one or more zero-valued arcs.

Following a result by Bouyssou [12; 13] it appears that, apart from certainly being reflexive, the bipolar-valued outranking digraphs do not necessarily possess any special relational properties such as transitivity or complete comparability. Indeed, with a sufficient number of criteria, it is always possible to define an ad hoc performance table such that the associated crisp 0-cut outranking digraph renders any given reflexive binary relation. This rather positive result from a methodological point of view -the outranking based methodology is universal -bears however a negative algorithmic consequence. Enumerating all kernels in a bipolar-valued outranking digraph becomes a non trivial algorithmic problem in case of non-transitive and partial outrankings, as we will show in the next section.

Before tackling this main topic of this work, let us, first, finish this section with introducing bipolar-valued choices and kernels.

On choices and kernels in bipolar-valued outranking digraphs

A choice in a given bipolar-valued outranking digraph is a non-empty subset of decision objects.

Definition 4

1. A choice Y in G(X, S) is said to be outranking (resp. outranked) if and only if x ∈ Y ⇒ ∃y ∈ Y : S(y, x) > 0 (resp. S(x, y) > 0); 2. Y is said to be independent (resp. weakly independent) if and only if for all x = y in Y we have S(x, y) < 0 (resp. S(x, y) 0;

3. An outranking (resp. outranked) and independent choice will be called an outrank- ing (resp. outranked) kernel;

4. An outranking (resp. outranked) and weakly independent choice will be called a weak outranking (resp. outranked) kernel.

Example 2 (Example 1 continued)

In the strict 0-cut crisp digraph G 1 (see Figure 1) we can observe two outranking kernels, namely the single choices {b} and {c}. The digraph also contains a weak outranked kernel, namely the pair {d, e}. Indeed, alternatives d and e are only weakly independent one from the other.

Let us finish this first section with presenting some interesting properties that kernels in their quality as independent outranking, resp. outranked, choices do possess. To illustrate this part, we use the following example.

Example 3 (B. Roy (2005), private communication)

Let G 2 (X, S1 ) be the bipolar-valued digraph where: X 2 = {a, b, c, d, e} and S2 is given as follows: In example (3), we may notice that the outranking choice {a, b, d, e} in G 2 (see example 3) may be reduced without loosing the property of being outranking. The outranked choice in the same example (3) may not however be reduced without loosing its outrankedness property. Minimal or maximal cardinality of choices with respect to a given qualification is formally captured in the following definition.

Definition 5 (Qualified choices of minimal or maximal cardinality)

A choice Y in G, verifying a property P , is minimal with this property whenever, ∀Y ′ ∈ G which verify the same property P , we have Y ′ ⊆ Y . Similarly, a choice Y in G, verifying a property P , is maximal with this property whenever, ∀Y ′ ∈ G which verify property P , we have Y ′ ⊇ Y . Comparing the outranking choice {a, b, d, e} in example (3) with the minimal outranking choice {a, c} in example (4) we may notice that minimality of outrankingness, resp. outrankedness, is related to the neighbourhoods of the nodes of the digraph.

We denote N + (x) = {y ∈ X / S(x, y) > 0} the open outranked neighbourhood of a node x ∈ X. We denote N + [x] = N + (x) ∪ {x} the closed outranked neighbourhood of x. We denote N -(x) = {y ∈ X / S(y, x) > 0} the open outranking neighbourhood of a node x. We denote N -[x] = N -(x) ∪ {x} the closed outranking neighbourhood of x.

The neighbourhood concept may easily be extended to a choice. The closed and open outranked neighbourhood of a choice Y in G are given by the union of the respective neighbourhoods of the members of the choice:

N + [Y ] = x∈Y N + [x], N + (Y ) = x∈Y N + (x). (4)
The closed and open outranking neighbourhood of a choice Y in G are similarly given by the union of the respective elementary outranking neighbourhoods:

N -[Y ] = x∈Y N -[x], N -(Y ) = x∈Y N -(x). (5)

Definition 6 (Private neighbourhood)

The (closed) private outranked neighbourhood

N + Y [x] of a node x in a choice Y contain- ing x is defined as follows: N + Y [x] = N + [x] -N + [Y -{x}]. Similarly, the (closed) private outranking neighbourhood N - Y [x] of a node x in a choice Y is defined as follows: N - Y [x] = N -[x] -N -[Y -{x}].
In case of a single choice, both the outranked and the outranking neighbourhood are considered to be private by convention.

In the outranking choice Y = {a, b, d, e} of example (3), we may notice that action a for instance has no private outranked neighbourhood. Indeed

N + Y [a] = N + [a] -N + [Y - {a}] where N + [a] = {a, b} and N + [Y -{a}] = X.
Action b however has action c as private outranked neighbourhood. The concept of private neighbourhoods leads us naturally to the notion of irredundant choices.

Definition 7 (±-irredundant choice)

An outranking choice Y in G is called +irredundant if and only if all its members have a non empty private outranked neighbourhood, i.e. ∀x ∈ Y :

N + Y [x] = ∅. Similarly, an outranked choice Y in G is called -irredundant if and only if all its members have a private outranking neighbourhood, i.e. ∀x ∈ Y : N - Y [x] = ∅.
In example (4), the outranking choice {a, c} is +irredundant as

N + {a,c} [a] = {a, b} and N + {a,c} [c] = {c, d, e}. Similarly the outranked choice {b, d, e} is -irredundant as N - {b,d,e} [b] = {a, b}, N - {b,d,e} [d] = {c} and N - {b,d,e} [e] = {e}.
Minimality of outrankingness (resp. outrankedness) and maximality of ±-irredundancy are evidently linked.

Proposition 1 (i) An outranking (resp. outranked) choice Y in G is minimal outranking (resp. outranked) if and only if it is outranking (resp. outranked) and +irredundant (resp. -irredundant) (Cockayne, Hedetniemi, Miller 1978).

(ii) Every minimal outranking (resp. outranked) choice Y in G is maximal +irredundant (resp. -irredundant) (Bollobás, Cockayne, 1979).

Proof: Property (i) following easily from property (2), we demonstrate only the latter one.

[⇒] Let us suppose that Y is minimal outranking but not maximal +irredundant. This implies that there exists a node x ∈ X -Y such that Y ∪ {x} is +irredundant, i.e. N + (Y ) is a proper subset of N + (Y ∪{x}). This contradicts however the fact that Y is outranking.

[⇐] The other way round, let us suppose that Y is maximal +irredundant but not minimal outranking. This implies that there must exist an y ∈ Y such that Y -{y} still remains outranking, i.e. this y cannot have a private outranked neighbourhood with respect to Y . This contradicts however the hypothesis that Y is +irredundant.

A similar reasoning is valid for outranked and -irredundant choices. 2

Similarly, maximal independence and minimal outrankingness or outrankedness are tightly related.

Proposition 2 (Berge, 1958)

Let G(X, S) be a determined bipolar-valued digraph. (i) Every kernel is a minimal outranking (resp. outranked) choice. (ii) Every minimal outranking (resp. outranked) and independent choice is maximal independent.

Proof: [START_REF] Berge | The theory of graphs[END_REF] Let us suppose that an outranking kernel Y is indeed not a minimal outranking (respectively outranked) choice. This implies that there exists an outranking (respectively outranked) choice Y ′ ⊂ Y such that Y ′ is still outranking (respectively outranked). This implies that ∀y ∈ Y -Y ′ there must exist some y ′ ∈ Y ′ such that (y, y ′ ) ∈ S (respectively (y ′ , y) ∈ S. This is contradictory with the fact that Y is independent. (2) Let us suppose that an outranking kernel Y is indeed not a maximal independent choice. This implies that there must exist a Y ′ ⊃ Y such that Y ′ is still independent. But Y is by hypothesis an outranking (respectively outranked) choice, i.e. ∀y ′ ∈ Y ′ -Y there must exist some y ∈ Y such that (y, y ′ ) ∈ S (respectively (y ′ , y) ∈ S. Hence there appears again a contradiction. 2 Not all minimal outranking (resp. outranked) choices are independent, i.e. kernels. In digraph G 2 of example 3, for instance, we observe the following four minimal outranking choices, of which only choice {a, c} is independent and therefore an outranking kernel. Let us therefore suppose that a minimal outranking (respectively outranked) choice Y is indeed not independent. As G is determined, this implies that there exists some proper subset Y ′ ⊂ Y such that for y ∈ Y -Y ′ and y ′ ∈ Y ′ we observe (y, y ′ ) ∈ S (respectively (y ′ , y) ∈ S. As Y is a minimal outranking (respectively outranked) choice, each action in Y must have a private outranked (resp. outranking) neighbourhood and in particular all actions in Y ′ . By transitivity of S, the private neighbourhoods

N + Y (y ′ ) and N - Y (y ′ ) of an action y ′ ∈ Y ′ are transferred to y ∈ Y -Y ′ .
And Y -Y ′ remains therefore an outranking (resp. outranked) choice. This is however contradictory with the hypothesis that Y is minimal with this quality. 2

It is worthwhile noticing that proposition (3) only applies to determined digraphs. In case we observe a partially determined graph, it may happen that a minimal outranking (resp. absorbent) choice is only weakly independent, and vice-versa, it may indeed happen that a maximal independent choice is neither outranking nor outranked. All depends upon the particular presence of undetermined relations.

We have not the space in this paper to present all existence results for kernels in a digraph (see for instance [START_REF] Ghoshal | Topics on domination in directed graphs[END_REF]). Relevant properties for our purpose are summarized below, where we generally suppose that the bipolar-valued digraph is determined.

Proposition 4 (Existence of qualified choices)

1. Every digraph supports minimal outranking (resp. outranked), as well as maximal independent and/or +irredundant (resp. -irredundant) choices.

2. A transitive digraph always supports an outranking (resp. outranked) kernel and all its kernels are of same cardinality (König, 1950 [22]).

3. A symmetric digraph always supports a conjointly outranking and outranked kernel (Berge, 1958 [1]).

4. An acyclic digraph always supports a unique outranking (resp. outranked) kernel (Von Neumann, 1944 [START_REF] Von Neumann | Theory of games and economic behaviour[END_REF]).

5. If a digraph does not contain any cordless circuit of odd length, it supports an outranking (resp. outranked) kernel (Richardson, 1953 [23]).

Bipolar-valued characterisation of choice classes

In the previous sections we have worked with different kinds of choices, namely outranking, outranked, independent, ±-irredundant ones. Similarly to the bipolar-valued characterisation of the digraph, we may now define a bipolar-valued characterisation of these kinds or classes on the power set P(X) of all possible choices we may define in G.

As these classes are all defined with logical conditions applied on bipolar-valued binary outranking statements, we first need to extend the bipolar-valued credibility calculus to well formed logical expressions.

Definition 8 (Well formed logical expressions)

Let G denote a set of ground atomic logical statements. We define inductively the set E of well formed logical expressions in the following way:

1. ∀p ∈ G we have p ∈ E; 2. ∀x, y ∈ E we have (x ∨ y) ∈ E, (x ∧ y) ∈ E, and ¬x ∈ E 3. all p ∈ E result of finite construction.

In order to avoid any problem with precedence of operators, we shall always use brackets to delimit the scope of the logical operators max, min and ¬ in an expression. Here our ground atomic logical expressions are the binary outranking assertions x S y of the given digraph G(X, S). Our well formed logical expressions concern formulas involving these binary outranking assertions.

As the atomic outranking assertions are evaluated in the given digraph G(X, S), following the truth-denotation semantics of Definition 1, we are now able to evaluate any well formed logical expression involving these evaluations S(x, y). We start by defining the degree of ±-irredundancy of a choice in G.

Definition 9 (Bipolar-valued ±-irredundance of choices)

Let G(X, S) be a bipolar-valued digraph. The credibility of (outranking) +irredundancy of action x with respect to choice Y in G is given by:

∆ +irr Y (x) = +1.0 when Y = {x}, max (z,y)∈X×Y -{x} min S(x, z), -S(y, z) otherwise. (6)
Similarly, the credibility of (outranked) -irredundancy of action x with respect to choice Y in G is given by:

∆ -irr Y (x) = +1.0 when Y = {x}, max (z,y)∈X×Y -{x} min S(z, x), -S(z, y) otherwise. (7)
The credibility of +irredundancy of choice Y in G is given by:

∆ +irr (Y ) = min x∈Y ∆ +irr Y (x) (8)
The credibility of -irredundancy of choice Y in G is given by:

∆ -irr (Y ) = min x∈Y ∆ -irr Y (x) (9) Proposition 5 Y in G is a +irredundant outranking (resp. -irredundant) choice if and only if ∆ +irr (Y ) > 0 (resp. ∆ -irr (Y ) > 0). Proof: (⇒) Suppose ∆ +irr (Y ) < 0. Then ∃x ∈ Y such that ∆ +irr Y (x) < 0.
This implies that Y ⊂ X and ∀(z, y) ∈ X × Y -{x} we have min S(x, z), -S(y, z) < 0. In other terms: ∀z ∈ N + [x] : ∃y ∈ Y -{x} such that z ∈ N + [y]. Hence x is redundant and Y cannot be +irredundant.

(⇐) Let us suppose the other way round that x in choice Y is redundant. This implies that N Y + [x] = ∅. In other terms:

N [ x] -N + [Y -{x}] = ∅.
This is exactly the case when for all z ∈ X such that S(x, z) > 0, we find a y ∈ Y -{x} such that S(y, z) > 0.

In this case max (z,y)∈X×Y -{x} ( S(z, x), -S(z, y)) < 0 and ∆ +irr Y (x) < 0. A same development applies for the outranked case. 2 Definition 10 (Bipolar-valued qualification of choices) Let G(X, S) be a bipolar-valued digraph. The credibility of outrankingness of a choice Y in G is given by:

∆ dom (Y ) = +1.0 when Y = X, min x ∈Y max y∈Y S(y, x) otherwise. ( 10
)
The credibility of outrankedness of a choice Y in G is given by:

∆ abs (Y ) = +1.0 when Y = X, min x ∈Y max y∈Y S(x, y) otherwise. ( 11
)
The credibility of independence of a choice Y in G is given :

∆ ind (Y ) = +1.0 if Y = {x}, min y =x y∈Y min x∈Y -S(x, y) otherwise. ( 12
)

Proposition 6

Let G(X, S) be an bipolar-valued outranking graph.

1. Y in G is an independent (resp. weakly independent) choice if and only if

∆ ind (Y ) > 0 (resp. ∆ ind (Y ) 0). 2. Y in G is an outranking (resp. outranked) choice if and only if ∆ dom (Y ) > 0 (resp. ∆ abs (Y ) > 0).
Proof: Property (1) follows immediately from definition (2) which states that a choice Y is indeed independent (weakly independent) if and only if S(x, y) > 0 ( S(x, y) 0) for all x, y ∈ Y .

Property (2), similarly, follows immediately from definition (1), as a choice Y is outranking (resp. outranked) if and only if ∀x ∈ Y : ∃y ∈ Y such that S(y, x) > 0 (resp. S(y, x) > 0). 2

Corollary 1

Let G(X, S) be an bipolar-valued outranking graph and G(X, S) its associated strict 0-cut crisp digraph. The minimal outranking (resp. outranked) choices of G correspond to the minimal outranking (resp. outranked) choices of G.

Proof: Y in G is a minimal outranking (resp. outranked) choice if and only if ∆ +irr (Y ) > 0 and ∆ dom (Y ) > 0 (resp. ∆ -irr (Y ) > 0 and ∆abs(Y ) > 0). 2

This important result from an operational point of view allows to determine the bipolarvalued minimal outranking (resp. outranked) choices in a bipolar-valued digraph G as follows:

1. Compute the minimal outranking (resp. outranked) crisp choices in the associated strict 0-cut digraph G, and 2. Compute the credibility of their qualification.

Corollary 2 (Kitainik 1993)

The set of outranking (resp. outranked) kernels of G is a subset of the set of outranking (resp. outranked) kernels of the associated strict 0-cut crisp digraph G.

Proof: Let G(X, S) be a bipolar-valued outranking graph. Y in G is an outranking (resp. outranked) kernel if and only if ∆ ind (Y ) 0 and ∆ dom (Y ) > 0 (resp. ∆abs(Y ) > 0). 2

It is worthwhile noting, that the actual set of kernels in the associated strict 0-cut digraph G may be larger than than that of the original bipolar-valued digraph G. It may contain, the case given, some outranking or outranked choices, that are indeed only weakly independent. These weak kernels correspond to partly determined choices.

Kitainik's result allows us to determine all possible outranking or outranked (weak) kernels in a bipolar-valued digraph G as follows:

1. We extract all crisp kernels and weak kernels from the associated strict 0-cut crisp graph G and, 2. for each such crisp kernel or weak kernel in G, we compute in G its bipolar-valued credibility.

Enumerating in a bipolar-valued digraph all outranking and outranked crisp kernels will actually be the purpose of the next section.

Enumerating crisp kernels

Enumerating kernels necessarily relies on general techniques for enumerating qualified choices, like minimal outranking or maximal independent ones. We start this section with the presentation of a general framework for enumerating such minimal or maximal qualified choices. After the discussion of their complexity and performance, we present and discuss specific algorithms for enumerating outranking as well as outranked crisp kernels.

Enumerating minimal and maximal qualified choices Definition 11 (Hereditary properties)

A property P of choices is said to be hereditary0 if whenever a choice Y has property P , so does every proper subchoice Y ′ ⊂ Y . A property P of choices is said to be superhereditary if whenever a choice Y has property P , so does every proper superchoice Y ′ ⊃ Y .

Proposition 7

Being outranking or outranked are superhereditary properties of choices in G. Similarly, independence as well as ±-irredundancy are hereditary properties of choices in G.

Proof: Hereditary follows immediately from the definition of an independent, an +irredundant, and an -irredundant choice. Superhereditary follows again readily from the definition being outranking or outranked. 2

Inheritance of being outranking makes it possible to implement the search for minimal outranking choices as a path algorithm in the outranking choices graph associated with G.

Definition 12 (P -choices graphs)

Let G(X, S) be an outranking graph. Let P(X) represent the powerset of choices in G with property P . The couple H(P(X), P ) is called the P choices-graph associated with G. Two choices are linked in H(P(X), P ) if they have some common action.

Proposition 8

1. The outranking and outranked choices graphs associated with G contain the greedy choice X and are each one strongly connected, 2. The ±-irredundant and independent choices graphs associated with G are composed of a set of strongly connected components such that each singleton choice belongs to exactly one component.

Proof: Ad 1. As outrankingness and outrankedness are superhereditary properties, there necessarily exists a path from every possible minimal outranking (resp. outranked) choice to X, the largest outranking (resp. outranked choice) and vice versa.

Ad 2. Both irredundancies as well as the independence property being hereditary, there necessarily exists a path in the corresponding choices-graphs from a maximal ±irredundant (resp. independent) choice to each of its single choice members and vice versa. 2

Following proposition 8, enumerating all minimal outranking or outranked choices may be implemented as a graph traversal algorithm in the corresponding choices graphs, where we try to explore all paths from the largest outranking (resp. outranked) choicethe greedy choice X -to the first subchoices which are ±-irredundant.

Algorithm 1 (Enumerating minimal outranking choices) global Hist Hist ← ∅

# initialise the history Y 0 ← X # start with the greedy choice

K + 0 ← ∅ # initialise the result K + ← MinimalOutrankingChoices (Y 0 , K + 0 )
def MinimalOutrankingChoices (In:

Y i outranking, K + i ; Out: K + i+1 ) K + ← ∅ IRRED ← True for [x ∈ Y i : N + Y i [x] = ∅]: # Retract in turn all redundant nodes IRRED ← False Y i+1 ← Y i -{x} # Y i+1 remains outranking ! if Y i+1 ∈ Hist: K + ← K + ∪ MinimalOutrankingChoices (Y i+1 , K + ): Hist ← Hist ∪ {Y i+1 } if IRRED: K + i+1 + ← K + i ∪ Y # Y is +irredundant (and outranking) else: K + i+1 + ← K + i ∪ K + return K + i+1
Proof: The algorithm starts with the greedy choice Y = X which is always outranking and an empty set of minimal outranking choices. The procedure MinimalOutrankingChoices collects all minimal outranking choices that may be reached from the initial outranking choice Y .

The call invariants of procedure MinimalOutrankingChoices are that the choice Y i is outranking and K + i is a set of minimal outranking choices collected so far.

If Y i is outranking, then Y i+1 = Y i -{x} is constructed only if N + Y i [x] = ∅, i.e.
in case x is a +redundant action and Y i+1 remains outranking. If no more +redundant actions may be found, the procedure stops the walk. As Y 0 = X is outranking, the algorithm walks therefore only on paths of the outranking choices-graph.

Let us suppose that at call i, K + i contains only minimal outranking choices. Two situations may happen. Either the current choice Y i is irredundant or all redundant actions have been removed in turn. In the first case, we are in the presence of a maximal irredundant and dominating choice, i.e. a minimal outranking choice which is added to to the current set K + i . In the second case, all minimal outranking choices when reducing the current choice are first added up in a local result K + to be at the end added up to K + i . This way, K + i+1 can only contain minimal outranking choices. As we start with an empty initial collection K + 0 , it is verified that in the end K + , if not empty, may only contain minimal outranking choices.

Finally, that we algorithm collects all existing minimal outranking choices in G follows from the fact that the outranking choices-graph is strongly connected and that therefore, starting from the greedy choice X, the algorithm walks necessarily through all outranking choices in G. The global history we use keeps track of the visited outranking choices and avoids to explore several times the same outranking choice. 2

The same algorithm delivers the minimal outranked choices when replacing in the loop the private outranked neighbourhood with the corresponding private outranking neighbourhood. This way, we only walk on outranked choices and collect all minimal outranked choices instead.

Based again on proposition (8), we may design a similar graph traversal algorithm in the irredundant choices graph. This time, we try to explore all paths from the smallest +irredundant (resp. -irredundant) choices -the single choices -to all outranking or outranked choices we may find on our way.

Algorithm 2 (Enumerating maximal irredundant choices) global Hist

Hist ← ∅ # initialise the history K + ← ∅ # initialise the result for x ∈ X: Y 0 ← {x} # each singleton is irredundant

K + ← K + ∪ MaxIrredOutrankingChoices (Y 0 , K + , Hist) def MaxIrredOutrankingChoices (In: Y i +irredundant, K + i ; Out: K + i+1 ): if (Y i -X) -N + (Y i ) = ∅: K + i+1 ← K + i ∪ Y i # Y i is outranking else: K + i+1 ← K + i # initialise the result for [x ∈ X -Y i : N + Y i [x] = ∅]: # add all +irredundant actions Y i+1 ← Y i ∪ {x} if Y i+1 ∈ Hist: K + i+1 ← K + i+1 ∪ MaxIrredOutrankingChoices (Y i+1 , K + i+1 ): Hist ← Hist ∪ {Y i+1 } return K + i+1
Proof: The algorithm starts with an empty history and an empty set of minimal outranking choices. The procedure MaxIrredOutrankingChoices then collects all minimal outranking choices that may be reached in turn from each initial single choice Y 0 = {x}, ∀x ∈ X The call invariants of iteration i are that the current choice Y i is +irredundant and K + i contains the minimal outranking choices collected so far.

If Y i is -irredundant, then Y i+1 = Y i ∪ {x} is constructed only if N + Y i [x] = ∅, i.e
. in case x is a +irredundant action with respect to current choice Y i . Y i+1 remains therefore +irredundant. As each Y 0 is in turn +irredundant, the algorithm walks only on paths of the +irredundant choices graph.

Let us suppose that at iteration i, K + i is either empty or contains only minimal outranking choices. Two situations may happen. First, the current choice Y i is outranking and we have found a maximal irredundant, i.e. a minimal outranking choice, and we add it to the current set K + i . In the second case, we gather all minimal outranking choices from the union of the current choice Y i with all possible +irredundant actions, i.e. such that N + Y i [x] = ∅. This way, K + i+1 can only contain minimal outranking choices or stay empty. As we start with an empty initial collection K + 0 , it is verified that in the end K + may only contain minimal outranking choices.

Finally, that the algorithm collects all existing minimal outranking choices in G follows from the fact that the +irredundant choices-graph is composed of strongly connected components. Starting in turn from each single choice, the algorithm walks necessarily through all +irredundant choices existing in H(P(X), +irredundant). In order to avoid visiting the same +irredundant choices several times in turn from each member single choice, we keep a history of visited +irredundant choices, and only proceed recursively with the next choice Y i+1 in case it has not been visited already before. 2

The same algorithm delivers again the minimal outranked choices when replacing the outranked with the outranking neighbourhoods. This way, we only walk on -irredundant choices and collect all minimal outranked choices instead.

Complexity and performance

The problem of finding a minimal outranking or outranked choice of a certain cardinality k, is known to be NP-complete [START_REF] Garey | Computers and intractability[END_REF], so that there is little hope to find efficient algorithms for enumerating all minimal outranking or outranked choices in general digraphs of high orders.

Indeed, the complexity is directly linked to the size of the P -choices graphs. In case a bipolar-valued digraph is empty, only the greedy choice will actually be an outranking choice. The outranking choices graph reduces here to a single node and algorithm 1 will deliver immediately this unique possible solution. As every possible choice in P(X) will be irredundant, the corresponding ±-irredundant choices-graph will be of order 2 n -1 (where n is the order of G) and of size (2 n -1) 2 -(2 n -1). Algorithm 2 therefore rapidly gets totally inefficient.

Similarly, in case G is complete, i.e. G is a complete graph K n , the irredundant choices-graph reduces to n isolated single choices. This time, algorithm 2 delivers immediately the n solutions, whereas the corresponding outranking choices-graph is again of order 2 n -1 and so of huge size (2 n -1) 2 -(2 n -1). Similarly, algorithm 1 this time is totally inefficient.

A stated before, we are mainly interested in dense digraphs where the second algorithm is more efficient in general, except for very low arc densities (see Figure 2.2). We have implemented both algorithms in the Python language (version 2.4) using the optimized inbuilt set class, which delivers constant time access to members of sets (independent of the cardinalities), and which offers optimized set operators like union, intersection, and difference with linear time in the cardinality of the operands [START_REF] Bisdorff | The Python digraph implementation for RuBy: User Manual[END_REF]. In figure (2.2) we have illustrated run time statistics for random digraphs of order 15 with arc densities varying from 10 to 90%.

It is obvious that the MaxIrredOutrankingChoices algorithm is doing much better except for arc densities below 15 %.

Let us now consider a special kind of outranking and outranked choices, namely those where the chosen actions are incomparable with respect to the S relation.

Qualified choices graph traversal algorithms for kernel enumeration

We have seen in the first section, that the independence property is computed from the false part of S. In order to implement path algorithms in the corresponding independentchoices graph, we cannot, as usual rely on the false by failure principle, i.e. the complement of the neighbourhoods, for representing independence. We need to introduce the logically positive concept of disconnects.

Definition 13 (Disconnects)

Let G be an irreflexive digraph. We call disconnect of a node x, denoted D(x) = {y ∈ X : ( S(y, x) < 0) ∨ ( S(x, y) < 0)}, the set of nodes disconnected from x. We call disconnect of a choice Y , the intersection of disconnects of the members of Y :

D(Y ) = x∈Y D(x).

Proposition 9

A choice Y in G is an outranking (respectively outranked) kernel if and only if:

Y ⊆ D(Y ) (independent) ∀x ∈ Y : N -(x) ∩ Y = ∅ (outranking) (resp. ∀x ∈ Y : N + (x) ∩ Y = ∅ (resp. outranked) )
Proof: It is readily seen that a choice Y is indeed independent if and only if the disconnects of the choice members contain the otherwise chosen actions. Similarly, a choice Y is outranking (resp. outranked) if and only if all not members of the choice are in the respective choice neighbourhood. 2

Reducing outranking choices

The previous result allows us to implement an outranking-choices graph traversal algorithm for enumerating all outranking kernels in a bipolar-valued outranking digraph.

Algorithm 3 (Enumerating outranking kernels: variant 1)

Y 0 ← X # start with the greedy choice

K + ← OutrankingKernels-1 (Y 0 ) def OutrankingKernels-1 (In: Y outranking; Out: K + ) if Y ⊆ D(Y ): K + ← Y # Y is independent else: K + ← ∅ for [x ∈ Y : N + Y [x] = ∅]: # Retract in turn all +-redundant nodes Y 1 ← Y -{x} # Y 1 remains outranking ! K + ← K + ∪ OutrankingKernels-1 (Y 1 ) return K +
Proof: Similar in its design to algorithm 1, this algorithm starts again with the greedy choice Y = X which is always outranking by convention and an empty set of minimal outranking kernels. The procedure OutrankingKernels collects all independent outranking choices that may be reached from this initial outranking choice Y . The call invariants of iteration i are that the choice Y i is outranking and K + i is a set of outranking kernels collected so far.

If Y i is outranking, then Y i+1 = Y i -{x} is constructed only if N + Y i [x] = ∅, i.e.
when x is a +irredundant action, so that Y i+1 remains outranking. If no more +irredundant actions may be found, the procedure stops the walk. As Y 0 = X is outranking, the algorithm only walks on paths of the outranking choices-graph.

Let us suppose that at iteration i, K + i contains only outranking kernels. Two situations may happen. Either the current choice Y i is independent or all redundant actions have been removed in turn. In the first case, we are in the presence of an outranking kernel which is added to to the current set K + i . In the second case, all outranking kernels potentially reached when reducing the current choice are first added up in a local result K + to be at the end added up to K + i . This way, K + i+1 can only contain outranking kernels. As we start with an empty initial collection K + 0 , it is verified that in the end K + may only contain minimal outranking choices.

Finally, that we algorithm collects all existing independent outranking choices in G follows from the fact that the outranking-choices graph is strongly connected and that therefore, starting from the greedy choice X, the algorithm walks necessarily through all outranking choices in G. 2

Replacing in this algorithm the +redundancy with the -redundancy test will enumerates simmilarly all outranked kernels. Furthermore, using a weak version of the disconnect concept, allows one to extract, with the same algorithm, all outranking (resp. outranked) kernels and weak kernels.

Extending independent choices

We have noticed from the discussion of the cmplexity of the minimal outranking choices extraction that the outranking digraphs are rather dense digraphs in general such that the outranking-choices graph is generally of very large order. Therefore is it more interesting to implement the kernel enumeration as an independent-choices graph traversal.

Algorithm 4 (Enumerating outranking kernels variant 2)

K + ← ∅ # initialise the result for x ∈ X: Y ← {x} # each singleton is independent K + ← K + ∪ OutrankingKernels-2 (Y, K + ) def OutrankingKernels-2(In: Y independent, K + 0 ; Out: K + ): if N + (Y ) -(Y -X) = ∅: K + ← K + 0 ∪ Y # Y is outranking else: # try adding all independent singletons K + ← K + 0 # initialise the result for [x ∈ X -Y : Y -{x} ⊆ D(x)]: Y 1 ← Y ∪ {x} # Y 1 remains independent ! K + ← K + ∪ OutrankingKernels-2 (Y 1 , K + ) return K +
Before going to prove algorithm 4, we may notice that the independence property in the recursive call invariant here, contrary to the ±-irredundancy properties, is a non oriented concept. This allows to enumerate in the same run, both the outranking and the outranked kernels.

Outranking and outranked kernels in the same run Algorithm 5 (Enumerating outranking and outranked kernels) global Hist Hist ← ∅

# initialise the history

K + ← ∅ # initialise the outranking result K -← ∅ # initialise the outranked result for x ∈ X: Y ← {x} (K + , K -) ← (K + , K -) ∪ AllKernels (Y , (K + , K -))
def AllKernels (In: Y independent, (K + 0 , K - 0 ); Out:

(K + , K -)): if N + (Y ) -(Y -X) = ∅: K + ← K + 0 ∪ Y # Y is outranking if N -(Y ) -(Y -X) = ∅: K -← K - 0 ∪ Y # Y is outranked # try adding all independent singletons (K + , K -) ← (K + 0 , K - 0 ) for [x ∈ D(Y )]: Y 1 ← Y ∪ {x} if Y 1 ∈ Hist: (K + , K -) ← (K + , K -) ∪ AllKernels (Y 1 , (K + , K -)) Hist ← Hist ∪ Y 1 return (K + , K -)
Proof: The algorithm starts with an empty history and empty sets of outranking and outranked kernels. The procedure AllKernels then collects all outranking and outranked kernels that may be reached in turn from each initial single choice Y 0 = {x}, ∀x ∈ X.

The call invariants of procedure AllKernels are that the current choice Y i is strictly independent, and that the current set K + i (resp. K - i ) of results contains the outranking (respectively outranked) kernels collected so far.

If Y i is independent, then Y i+1 = Y i ∪{x} is constructed only if x ∈ D(Y i ), i.e. in case Y i+1 remains independent.
As each Y 0 is in turn independent by convention, the algorithm walks only on paths of the independent choices-graph.

Let us suppose that at recursive call i, K + i and K - i are either empty or contain only outranking or outranked kernels. Three situations may happen. First, the current choice Y i is outranking and we have found a new outranking kernel that we add to the current set K + i . In the second case, the current choice Y i is outranked and we have found a new outranked kernel that we add again to the current set K - i . Thirdly, we gather all outranking and outranked kernels from the union of the current choice Y i with all possible actions x contained in its disconnect. This way, K + i+1 and K - i+1 can only contain outranking, respectively outranked kernels or stay empty. As we start with empty initial collections K + 0 and K - 0 , it is verified that in the end K + , respectively K -, if not empty, may only contain outranking, respectively outranked, kernels.

Finally, that the algorithm collects all existing determined outranking and outranked kernels in G follows from the fact that the strictly-independent-choices graph is strongly connected. Starting in turn from each single choice, the algorithm walks necessarily through all strictly independent choices existing in G. In order to avoid visiting the same strictly independent choices several times in turn from each member single choice, we keep a history of visited choices and only proceed recursively with the next choice Y i+1 in case it has not yet been visited. 2

Again, using a weak version of the disconnect concept, allows one to extend this algorithm to both, the completely determined as well as the weak kernels.

Complexity and computational performance

In figure 2.4 we show run times statistics for kernel extractions from randomly filled bipolar-valued digraphs of order 35. Similar to the previous statistics, we find that the extraction of kernels is computationally easy (run times less than a second) when the arc density is 20% and more. Again, the performance is directly related to the order of the independent-choices graph. Indeed, the higher the arc density, the lower is the order of this choices graph. With an arc density of 50% for instance, we observe an average of only 200 independent choices. We may collect on this choices graph the outranking and outranked kernels in an average of 15 milliseconds on a standard desktop PC. This run time performance is even better supported in general (see figure 2.4) when considering that almost all digraphs of order n contain only kernels such that C n -1.43 ≤ |K| ≤ C n + 2.11 where C n = ln(n)ln(ln(n)) (Tomescu [START_REF] Tomescu | Almost all digraphs have a kernel[END_REF]). For a randomly filled digraph of order 900 and 50% arc density, we may thus observe kernels of average cardinalities of 7. Thus we are able to extract in less than a minute all kernels from digraphs of orders up to 900 and an arc density of 50% and more, under the condition of disposing of a sufficiently large CPU memory. This general performance is most satisfactory, as the particular outranking graphs we are interested in generally represent more or less transitive weak orderings. As empiric studies of random outranking digraphs is confirming, the corresponding digraphs show arc densities always superior to 50% [START_REF] Bisdorff | Étude statistique des graphes de surclassement aléatoires[END_REF]. Nevertheless some digraphs, even of modest order (less than 30), may potentially represent difficult instances. Indeed, as shown in figure 2.4, where we have artificially limited the run time to 10 seconds, a brutal combinatorial explosion appears with digraphs of very low arc density. Here we may easily observe independent choices-graphs of huge exponential size coupled with kernels of cardinalities up to n/2. This definitely limits the practical performance for extracting all kernels from these kinds of digraphs.

But the independent-choices graph traversal approach is not the only possible strategy for computing kernels in a digraph. Very recently, Alain Hertz1 has proposed a pivoting algorithm which, starting from an arbitrary initial maximal independent choice, visits directly all other existing maximal independent sets in the digraph. This algorithm belongs to the family of reverse searching algorithms such as the simplex algorithm in linear algebra. The pivoting from one maximal independent choice to the other is done in a polynomial O(n) step, such that performances in fact only depend on the actual number of kernels observed in the digraph. Even if this last algorithm is not as efficient as the AllKernels procedure for dense digraps of large orders, it however delivers all kernels for difficult digraphs such as cordless n-circuits, and n-paths.

All the preceding discussion only concerns the computation of crisp kernels. In the next section we propose an algebraic approach to the same problem via bipolar-valued membership characterisations of choices, which will deliver the necessary algorithms for solving the general bipolar-valued case.

Algebraic approach

In this last section we use an early observation by Berge [1, see Chapter 5] concerning the fact that kernels in a digraph may be characterised with a specific characteristic functional equation. We extend this idea to the bipolar-valued case with the objective to immediately determine bipolar-valued kernels from the admissible algebraic solutions of these caracteristic equations.

The kernel characteristic equations

A choice Y in G(X, S) may be characterised with the help of bipolar-valued membership assertions Y : X → L, denoting the credibility of the fact that x ∈ Y or not, for all x ∈ X. Y is called a bipolar-valued characterisation of Y , or for short a bipolar-valued choice in G(X, S).

Based on the truth-denotation semantics of the bipolar-valued characterisation domain L (see Subsection 1.1), we obtain the following properties:

-Y (x) = +1 signifies that assertion "x ∈ Y " is certainly true; -Y (x) > 0 signifies that assertion "x ∈ Y " is more true than false; -Y (x) = 0 signifies that assertion "x ∈ Y " is logically undetermined, i.e. could be either true or false;

-Y (x) < 0 signifies that assertion "x ∈ Y " is more false than true;

-Y (x) = -1 signifies that assertion "x ∈ Y " is certainly false. Equivalently, one can say that assertion x / ∈ Y is certainly true.

In the following paragraphs, we recall useful results from [START_REF] Bisdorff | Choices and kernels in bipolar valued digraphs[END_REF]. They allow us to establish a formal relation with the previous classical subset-based definitions of qualified choices.

Let Y be a bipolar valued characteristaion of a choice in G(X, S). We note

Y • S (resp. Y • S -1
) the bipolar-valued matrix product max y =x [min( Y (y), S(y, x))] (resp. max y =x [min( S(x, y), Y (y))]) for all x, y in X.

Proposition 10

The outranking (resp. outranked) kernels of G(X, S) are among the bipolar-valued choices Y satisfying the respective following bipolar-valued kernel caracteristic equation systems:

Y • S = -Y , (resp. Y • S -1 = -Y ). (13)
Proof: Early proofs of this proposition for the Boolean-valued outranked case may be found in [START_REF] Berge | Graphes et hypergraphes[END_REF] and [26; 27]. The classic fuzzy-valued case is tackled in [START_REF] Kitainik | Fuzzy decision procedures with binary relations: towards a unified theory[END_REF], while the bipolar-valued outranking case is thoroughly discussed and proved in [START_REF] Bisdorff | Choices and kernels in bipolar valued digraphs[END_REF]. 2

It is worthwhile noting from the beginning, that certain bipolar-valued kernel characterisations, despite being different in values, may characterise in fact a same crisp choice. To cope with this phenomena, we introduce the following congruence relation on Y, the set of possible characterisations of choices in G.

We say that two bipolar-valued characterisations Ỹ1 and Ỹ1 of choices in G are non contradictory, denoted Ỹ1 ∼ = Ỹ2 if and only if Ỹ1 (x) > 0 ⇔ Ỹ2 (x) > 0 and Ỹ1 (x) < 0 ⇔ Ỹ2 (x) < 0. Every choice Y in G determines a congruence class of non contradictory bipolar-valued characterisations denoted Y / ∼ =Y . Furthermore, it is useful to compare bipolar-valued charaterisations with respect to the sharpness of their charateristic determination.

Definition 14 (Sharpness of bipolar-valued characterisations)

Let Ỹ1 , Ỹ2 ∈ Y characterise choices Y in G. We say that Ỹ1 is sharper than Ỹ2 , denoted Ỹ1 Ỹ2 if and only if for all x ∈ X, either Ỹ1 (x) ≤ Ỹ2 (x) ≤ 0, or 0 ≤ Ỹ2 (x) ≤ Ỹ1 (x).

The sharpness relation determines a partial order on Y, the set of possible bipolarvalued characterisations of choices in G (see [START_REF] Bisdorff | On computing kernels from L-valued simple graphs[END_REF]). The all 0-valued vector Ỹ (x) = 0, ∀x ∈ X acts as bottom, the least sharpest characterisation and all 2 n crisp, i.e. {-1.0, 1.0}valued choice characterisations give the sharpest possible characterisations. In a given congruence class of non-contradictory characteristaions of a given choice Y , the sharpness relation actually gives a lattice with the all 0-valued vector as bottom element and the {-1, 1}-valued characterisation of Y (see [START_REF] Bisdorff | On computing kernels from L-valued simple graphs[END_REF]).

Theorem 1 (Bisdorff, Pirlot, Roubens, 2005) 1. To each maximal sharp solution of the kernel characteristic equation systems ( 13) is associated an outranking (resp. outranked) kernel or weak kernel in G.

2. A choice Y is an outranking (resp. outranked) kernel in G if and only if there exists a corresponding bipolar-valued characteristic vector Ỹ that is a maximal sharp determined solution of the kernel characteristic system [START_REF] Bouyssou | Notes on bipolar outranking relations Private communication[END_REF].

Proof: Ad 1.) (⇐) If Ỹ is a maximal sharp (not trivially undetermined) solution of equation system [START_REF] Bouyssou | Notes on bipolar outranking relations Private communication[END_REF], then the so characterised choice Y will be independent or weakly independent and outranking in G as a direct consequence of Proposition [START_REF] Bisdorff | RuBy: A bipolar-valued outranking method for the best choice decision problem[END_REF]. From [8, see Theroem 2] if follows that in case Ỹ is only partially determined, the associated crisp choice will be necessarily weakly independent only. Ad 2.) (⇐) With the same argument as before, we see that in case the choice Ỹ is actually determined, the associated crisp choice will necessarily be independent and outranking, i.e. an outranking kernel. (⇒) If Y is an outranking kernel in G we show that there exists a unique solution Ỹ ∈ Y / ∼ =Y of the fixpoint equation system:

T ( Ỹ ) = -( Y • S) = Ỹ . (14)
that is a maximal sharp and determined solution of equation system [START_REF] Bouyssou | Notes on bipolar outranking relations Private communication[END_REF].

Indeed, it is readily seen that the fixpoints of equation ( 14) verify in fact the outranking kernel characteristic equation system [START_REF] Bouyssou | Notes on bipolar outranking relations Private communication[END_REF].

Transformation T gives furthermore a non-contradictory transformation of kernel characterisations, i.e. Ỹ ∈ Y / ∼ =Y ⇒ T ( Ỹ ) ∈ Y / ∼ =Y . Indeed, y ∈ Y ⇒ S(y, x) < 0 so that ∀x ∈ Y , min( Ỹ (x), S(x, y)) = S(x, y) < 0, and, ∀x ∈ Y , min( Ỹ (x), S(x, y)) ≤ Ỹ (x) < 0. The combination of both cases shows that T ( Ỹ )(y) > 0. Similarly, x ∈ Y ⇒ ∃y ∈ Y : S(y, x) > 0. For such an y, min( Ỹ (x), S(x, y)) > 0 and hence T ( Ỹ ) < 0.

We may also show that the transformation T is isotone with respect to the sharpness ordering , i.e. if Ỹ1 , Ỹ2 ∈ Y / ∼ =Y are such that Ỹ1 Ỹ2 then T ( Ỹ1 ) T ( Ỹ2 ). Indeed, y ∈ Y ⇒ Ỹ1 (y) > Ỹ2 (y) ⇒ T ( Ỹ1 )(y) > T ( Ỹ2 )(y), and y ∈ Y ⇒ Ỹ1 (y) < Ỹ2 (y) ⇒ T ( Ỹ1 )(y) < T ( Ỹ2 )(y) since the functions max and min are non decreasing.

If we start now the resolution of the fixpoint equation with Ỹ0 (x) = 1.0 when x ∈ Y , and Ỹ0 (x) = -1.0 when x ∈ Y , i.e. the maximal possible sharp characterisation, we necessarily get Ỹi T ( Ỹi-1 ) for i = 1, 2, . . .. As G is of finite order, the bipolar-valued credibility calculus, involving only min, max and signs inversions, is a finite algebra generated by the finite set of additions and subtractions of the weights w j of the individual criteria j as appearing in the bipolar-valued characterisation of the outranking relation.. Therefore there exists a finite number k ≤ n(n -1) such that Ỹk = T ( Ỹk ).

This fixpoint solution Ỹn is unique, determined and maximal sharp (see [8, proof of theorem 1]).

The outranked case is canonically obtained by taking the reversed outranking relation S -1 .2

Solving the kernel characteristic equation system

Smart enumeration with a finite domain solver

It is possible to directly enumerate all maximal sharp solutions from the bipolar-valued kernel characteristic equation systems with the help of a finite domain solver as provided by some Prolog programming environments such as GNU-Prolog [15; 16] or the commercial Prolog software CHIP. Implementation details of such a solving approach may be found in Bisdorff [START_REF] Bisdorff | On defining and computing fuzzy kernels from L-valued simple graphs[END_REF].

In Figure 3.2.1, we show average performance using the GNU-Prolog FD solver. Contrary to our AllKernels Python implementation, better performances are obtained here with smaller arc densities. This is due to the order of the arc-constraints graph which is indeed proportional to the actual size of the outranking digraph. The sparser the outranking digraph, the smaller the order of the constraints graph, the quicker the constraints propagation algorithm will help enumerating all kernels in the graph. However, empiric computing studies reveal that these enumeration techniques get inefficient for dense bipolar-valued outranking digrahs of order 30 and more. It quickly appears that specially adapted fixpoint approaches are much more efficient (see Bisdorff [START_REF] Bisdorff | On computing kernels from L-valued simple graphs[END_REF]).

Fixpoint based solving approaches

The proof of Theorem 1 reveals indeed a possibility to find a maximal sharp bipolarvalued characterisation of an outranking (resp. outranked) kernel under the condition that we already precisely know the associated strict 0-cut choice. 1. With the help of the AllKernels procedure, extract all crisp outranking and outranked kernels K 1 , K 2 , . . . , K j from G;

2. For each outranking K j : With Ỹ0 (x) = +1.0 for all x ∈ K j and Ỹ0 (x) = -1.0 for all x ∈ K j , the iteration Ỹi = T ( Ỹi-1 ) for i = 1, 2, . . . converges to a fixpoint which is Kj = T ( Kj );

3. We repeat the preceding step for the outranked kernels with a reversed fixpoint operator

T -1 ( Ỹ ) = -( Y • S -1 ) = Ỹ ..
Proof: From Proposition 10 we know that the set of bipolar-valued kernels of a given outranking digraph G(X, S) is a subset of the set of crisp kernels we may find in the associated 0-cut crisp digraph G(X, S). For all determined bipolar-valued kernels, we know from Theorem 1 that the fixpoint euqation delivers the unique, maximal sharp, bipolar-valued kernel characterisation. 2

But we may also find a similar way to compute the weak kernels of G. Before tackling this general bipolar-valued case, we may consider the following result.

Theorem 2

Let G(X, S) be a bipolar-valued outranking digraph such that their exists a unique (may be partial) kernel K in G with an associated maximal sharp (not trivially undetermined) K characterisation. Let T 2 : Y → Y be the following dual transformation of a bipolarvalued choice characterisation:

T 2 ( Ỹ ) = --( Y • S) • S . (15)
With Ỹ0 (x) = -1.0 for all x ∈ X, the iteration Ỹi = T 2 ( Ỹi-1 ) for i = 1, 2, . . . converges to the unique fixpoint K = T 2 ( K). The proof of the bipolar-valued case will follow a scheme first set out in Berge [START_REF] Berge | The theory of graphs[END_REF] and thoroughly enlarged in Schmidt and al. [START_REF] Schmidt | Relationen und Graphen[END_REF]. For any bipolar caracterised choice Y in Y, let us denote π( Y ) the crisp choice in X associated with Y .

We may first notice that the single T transformation of bipolar-valued choices is antitone with respect to the subchoice-inclusion relation defined on X through the π function. As a consequence, the dual transformation T 2 will be isotone wrt to the same subchoiceinclusion relation in X. For each possible kernel characterisation K of a kernel in G, Y ∧ and Y ∨ deliver its bipolar-valued characteristic limits (see [START_REF] Schmidt | Relationen und Graphen[END_REF]:

π(-( Y ∨ • S)) = π( Y ∨ ) ⊆ K ⊆ π( Y ∧ ) = π(-( Y ∧ • S)).
As G admits by assumption a unique kernel K, it is necessarily a progressively finite digraph such that the upper fixpoint must also verify π(( S ∧ • S)) ⊆ π(-Y ∨ ). It follows immediately that π( Y ∧ ) = π( K) = π( Y ∨ ). As a consequence, the iterations of Equation 15 will necessarily end up in the sharpness congruence class Y / ∼ =K of the given unique kernel K. Now, from the proof of Theorem 1 we know that these iterations, starting from both, the all 0-valued bottom element in the sharpness lattice, and from the all {-1, 1}-valued characterisation of K -in fact the top element in the same sharpness lattice -, will converge to a lower fixpoint K ∧ showing the sharpest possible negative credibilities of those actions that are excluded from the kernel K, and an upper fixpoint K ∨ showing the sharpest possible positive credibilities of those actions that are definitively included in the kernel K. Combining both fixpoints with the corresponding sharpness lattice addition operator ⊕ (see [START_REF] Bisdorff | On computing kernels from L-valued simple graphs[END_REF]) -K ∧ ⊕ K ∨ -renders finally the required maximal sharp bipolar-valued characterisation of K.2

Based on this result, the following algorithm tackles the enumeration of all bipolarvalued kernels in the general case: Algorithm 7 (Bisdorff 1997) Let G(X, S) be a bipolar-valued outranking digraph.

1. With the help of the AllKernels procedure, extract all outranking and outranked (weak) kernels K 1 , K 2 , . . . , K j (if they exist) from the associated 0-cut graph G(X, S).

2. Associate with each outranking K j a partially defined graph G K j (X, S /K j ) supporting exactly this unique kernel K j .

3. Use the v. Neummann dual fixpoint iteration T 2 for computing in turn Kj in each partial graph G K j .

4. Repeat steps 2 and 3 above for the outranked K j with the reversed dual transformation (T -1 ) 2 .

A detailed description of this algorithm may be found in Bisdorff [START_REF] Bisdorff | On computing kernels from L-valued simple graphs[END_REF].

Complexity

Both Pirlot's and Bisdorff's algorithm involve a first step which enumerates the crisp kernels and/or weak kernels observed in G.

For each such crisp choice, the fixpoint based algorithms compute the corresponding maximal sharp bipolar-valued characterisation in at most n 3n 2 steps, where each case mainly involves two Boolean products of dimension n × 1 and equality tests. Thus they operate in polynomial O(n) time, once the crisp kernels and weak kernels are available.

Main complexity remains thus definitely in the first step, i.e. enumerating all (weak) kernels in a general crisp digraph.

Concluding remarks

This paper compiles our work on studying and computing kernels in valued digraphs from roughly the last ten years. Summer 1995, we indeed obtained the very first valued outranking kernel from a classic example digraph of order 8 (!) well known in the multicriteria decision aid context . The computation was done with the help of a commercial finite domain solver. It took several seconds on a CRAY 6412 superserver with 12 processors operating in a nowadays ridiculous CPU speed of 90 Mhz. In our present Python implementation, such an example is solved with any of the beforehand discussed algorithms in less than a thousandth of a second on a common low budget desktop computer. And this remains practically the same for any relevant example of outranking digraph observed in a real decision aid problem.

Several times we have written in our personal journal that there is certainly now no more potential for any substantial improvement of this computational efficiency; Only to discover, shortly later, that following a new theoretical idea or choosing a more efficient implementation -using for instance the amazing instrument of itorator generators in Python -, execution times could well be divided by 20.

This nowadays available computational efficiency confers the kernel concept a methodological premium for solving specific choice decision problems on the basis of a bipolarvalued outranking digraph.

But it also opens new opportunities for verifying and implementing kernel extraction algorithms for more graph theoretical purposes. New results concerning for instance unlabelled kernels in symmetric graphs have been recently obtained. And, exploring the kernels of known difficult graph instances like the n-cycle becomes possible.

But this is the beginning of a new paper.

Table 2 :Figure 1 :

 21 Figure 1: Example 1: Associated strict 0-cut digraph and undetermined arc

  , e} is an outranked choice.

Example 4 (

 4 Minimal qualified choices in G 2 ) , c} is a minimal outranking choice.

  , d, e} is a minimal outranked choice

3

 3 choices however coincide in determined and transitive digraphs. Proposition Let G(X, S) be a transitive and determined digraph, i.e. the associated crisp graph G(X, S) supports a transitive outranking relation S. A choice Y in G is an outranking (resp. outranked) kernel if and only if Y verifies one of the following equivalent conditions: 1. Y is minimal outranking (resp. outranked); 2. Y is outranking (resp. outranked) and independent; 3. Y is outranking (resp. outranked) and +(-)irredundant; 4. Y is maximal +(-)irredundant. Proof: (1) ⇔ (3) ⇔ (4) are covered by proposition 1, and (2) ⇒ (1) is covered by proposition 2. We only need to prove that (1) ⇒ (2).

Figure 2 :

 2 Figure 2: Run time statistics for randomly filled digraphs of order 15

Figure 3 :

 3 Figure 3: Run time statistics for the AllKernels procedure (Algorithm 5)

Figure 4 :

 4 Figure 4: General performance of Algorithm 5

Figure 5 :

 5 Figure 5: Average performance using the GNU-Prolog FD solver

Proof:

  A classic Boolean-valued restriction of this theorem is attributed to von Neumann (1944) [27, see A3, p. 284].

  i.e. for Y 1 , Y 2 ∈ Y:π( Y 1 ) ⊆ π( Y 2 ) ⇒ π(T 2 ( Ỹ1 )) ⊆ π(T 2 ( Ỹ2 )).As the subset-inclusion relation gives a finite poset on π(Y), we know from general fixpoint theory that Equation 15 admits necessarily a smallest fixpointY ∧ = inf{ Y | Y = T 2 ( Y )} and a largest fixpoint Y ∨ = sup{ Y | Y = T 2 ( Y )}.

Table 1 :

 1

	decision		coherent family of criteria
	objects	1	2	3	4	5
	a	0.52 0.82 0.07 1.00 0.04
	b	0.96 0.27 0.43 0.83 0.32
	c	0.85 0.31 0.61 0.41 0.98
	d	0.30 0.60 0.74 0.02 0.02
	e	0.18 0.11 0.23 0.94 0.63

Example 1: Random performance table ternatives on each criterion, we compute the bipolar-valued outranking relation S 1 shown in table 2. The strict 0-cut crisp digraph G 1 (X 1 , S 1 ) associated to the bipolar-valued

The ideas and results concerning hereditary and superhereditary properties of choices are taken from[20, see Chapter 3].

Private communication, April