Raymond Bisdorff
email: raymond.bisdorff@uni.lu

Patrick Meyer
email: patrick.meyer@uni.lu

Marc Roubens

RUBIS: a bipolar-valued outranking method for the choice problem

Keywords: Choice problematique, Multiple criteria outranking method, Progressive decision aiding methodology, Digraph kernel MSC classification (2000) 05C20, 90B50

The main concern of this article is to present the Rubis method for tackling the choice problem in the context of multiple criteria decision aiding. Its genuine purpose is to help a decision maker to determine a single best decision alternative. Methodologically we focus on pairwise comparisons of these alternatives which lead to the concept of bipolar-valued outranking digraph. The work is centred around a set of five pragmatic principles which are required in the context of a progressive deci-sion aiding methodology. Their thorough study and implementation in the outranking digraph lead us to define a choice recommendation as an extension of the classical digraph kernel concept.

Introduction

We present a new method for constructing choice recommendations in the context of multiple criteria decision aiding where the objective is to determine a single best alternative from a set of potential decision objects. This work is situated in the context of progressive decision aiding methods (see Sect. 3.1) consisting normally in several stages providing the decision maker (DM) with more and more precise choice recommendations. Each of these steps aims at determining a subset of alternatives among which the best one is situated. As long as such a provisional recommendation consists of several candidates, the decision aiding process may be restarted on this restricted set with new and more detailed information in order to further assist the DM in his decision problem. Note that it may be up to him to determine the ultimate choice from the eventual recommendation of the decision aiding.

Apart from the European multiple criteria decision aiding community [START_REF] Roy | Aide multicritère à la décision : Méthodes et cas. Economica, Paris Roy B, Vanderpooten D[END_REF]Roy and Vanderpooten 1996), the progressive resolution of the choice problem has attracted quite little attention by the Operational Research (OR) field. Seminal work on it goes back to the first article of Roy on the Electre I methods [START_REF] Roy | Classement et choix en présence de points de vue multiples (la méthode ELECTRE)[END_REF]). After Kitainik (1993), interest in solving the choice problem differently from the classical optimisation paradigm has reappeared. An early work of [START_REF] Bisdorff | On defining and computing fuzzy kernels from l-valued simple graphs[END_REF] on valued kernels has resulted in new attempts to tackle the progressive choice problem directly on the valued outranking digraph. After first positive results [START_REF] Bisdorff | Logical foundation of fuzzy preferential systems with application to the electre decision aid methods[END_REF], methodological difficulties appeared when facing highly non-transitive and partial outranking relations. In this paper, we therefore present a new proposal for computing provisional choice recommendations from a valued outranking digraph. Our approach is based on new pragmatic and logical foundations of the progressive choice problematique 1 in the tradition of the pioneering work of Roy and Bouyssou (1993).

The paper is organised as follows. In Sect. 2, we introduce the basic concepts and notation which are necessary for our future discourse. In Sect. 3, we revisit the very foundations of the choice problematique, briefly present the classical Electre methodology, and list new pragmatic principles which are required for computing choice recommendations in a progressive decision aiding process. Sect. 4 deals with the translation of these principles into properties in the bipolar-valued outranking digraph which lead to the concept of hyperkernel, an extension of the classical kernel of a digraph. In Sect. 5, we show how to determine these hyperkernels and detail the Rubis method 2 for computing a choice recommendation.

Fundamental concepts

We start by establishing the backbone of the Rubis method, namely the bipolar-valued credibility scale, modelling the credibility of the validation of preferential statements. 1 A broad typology or category of problems for which multiple criteria decision analysis may be useful (Belton and Stewart 2002,p.15). 2 We propose the name Rubis as a generic identifier for bipolar-valued concordance-based decision aiding methods.

Bipolar-valued credibility calculus

Let ξ be a propositional statement like "alternative x is a choice recommendation" or "alternative x is at least as good as alternative y". In a decision process, a DM may either accept or reject these statements following his belief in their validation [START_REF] Bisdorff | Logical foundation of fuzzy preferential systems with application to the electre decision aid methods[END_REF]. This degree of credibility (or credibility for short) may be represented via a credibility scale L = [-1, 1] supporting the following semantics. Let ξ and ψ be two propositional statements to which are associated credibilities r and s ∈ L:

1. If r = +1 (resp. r = -1) then it is assumed that ξ is clearly validated (resp. clearly non-validated). If 0 < r < +1 (resp. -1 < r < 0) then it is assumed that ξ is more validated than non-validated (resp. more non-validated than validated). If r = 0 then ξ could either be validated or non-validated, a situation we call undetermined. 2. If r > s then it is assumed that the validation of ξ is more credible than that of ψ (or that the non-validation of ψ is more credible than that of ξ ). 3. The credibility of the disjunction ξ ∨ ψ (resp. the conjunction ξ ∧ ψ) of these statements equals the credibility of the statement that is the most (resp. the less) credible of both, i.e., max(r, s) [resp. min(r, s)]. 4. -r ∈ L denotes the credibility of the non-validation of ξ , i.e., the credibility of the validation of the logical negation of ξ (written ¬ξ ).

Definition 2.1 The credibility associated with the validation of a propositional statement ξ , defined on a credibility domain L and verifying properties (1) to ( 4) is called a bipolar-valued characterisation of ξ .

It follows from property (4) that the graduation of credibility degrees concerns both the affirmation and the negation of a propositional statement [START_REF] Windelband | Beiträge zur Lehre vom negativen Urteil[END_REF]. Starting from +1 (certainly validated) and -1 (certainly non-validated), one can approach a central position 0 by a gradual weakening of the absolute values of the credibility degrees. This particular point 0 in L represents an undetermined situation concerning the validation or non-validation of a given propositional statement [START_REF] Bisdorff | Logical foundation of fuzzy preferential systems with application to the electre decision aid methods[END_REF][START_REF] Bisdorff | Logical foundation of multicriteria preference aggregation[END_REF].

Definition 2.2

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

D(ξ ) = |r |.
For both a clearly validated and a clearly non-validated statement, the determinateness equals 1. On the opposite, for an undetermined statement, this determinateness equals 0. This establishes the central degree 0 as an important neutral value in the bipolar-valued credibility calculus. Propositions characterised with this degree 0 may be either seen as suspended or as missing statements [START_REF] Bisdorff | Logical foundation of multicriteria preference aggregation[END_REF]. The credibility degree 0 represents a temporary delay in characterising the validation or non-validation of a propositional statement. In the framework of progressive decision aiding, this feature allows us to easily cope with currently undetermined preferential situations that may eventually become determined to a certain degree, either as validated or non-validated, in a later stage of the decision aiding process.

The following subsection introduces the important concept of bipolar-valued outranking digraph which is the preferential support for the Rubis choice decision aiding methodology.

The bipolar-valued outranking digraph

Let X = {x, y, z, . . .} be a finite set 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 relative significance weight 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 of F is linked a 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. Let j (x, y) be the difference of the performances g j (x)g j (y). To each preference scale for each j of F is associated a variable indifference threshold q j (g j (x)) ∈ [0, 1[, a preference threshold p j (g j (x)) ∈ [q j (g j (x)), 1[, a weak veto threshold wv j (g j (x)) ∈ [p j (g j (x)), 1] ∪ {2} and a strong veto threshold v j (g j (x)) ∈ [wv j (g j (x)), 1] ∪ {2}, where the complete absence of veto is modelled via the value 2. All these threshold functions are supposed to verify the standard non-decreasing monotonicity condition (Roy and Bouyssou 1993, p. 56).

Let S be a binary relation on X . Classically, an outranking situation x Sy between two decision alternatives x and y of X is assumed to hold if there is a sufficient majority of criteria which supports an "at least as good as" preferential statement and there is no criterion which raises a veto against it [START_REF] Roy | Aide multicritère à la décision : Méthodes et cas. Economica, Paris Roy B, Vanderpooten D[END_REF]. The validation of such an outranking situation may quite naturally be expressed in the bipolar credibility calculus defined in Sect. 2.1. Our formulation is based on the classical Electre definition of the outranking index. Nevertheless the reader should notice some slight but important differences, due to the semantics of the underlying bipolar valuation.

Indeed, in order to characterise a local "at least as good as" situation between two alternatives x and y of X for each criterion j of F, we use the following function C j : X × X → {-1, 0, 1} such that:

C j (x, y) = ⎧ ⎪ ⎨ ⎪ ⎩ 1 if j (x, y) > -q j (g j (x)) ; -1 if j (x, y) ≤ -p j (g j (x)) ; 0 otherwise .
Credibility 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 Sect. 2.1). Note here the deviation from the classical Electre concordance index, where a linear transition between certainly validated and certainly non-validated situations is proposed (Roy and Bouyssou 1993).

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

V j (x, y) = ⎧ ⎪ ⎨ ⎪ ⎩ 1 if j (x, y) ≤ -v j (g j (x)) ; -1 if j (x, y) > -wv j (g j (x)) ; 0 otherwise .
Again, according to the semantics of the bipolar-valued characterisation, the veto function V j renders an undetermined response when the difference of performances is between the weak and the strong veto thresholds wv j and v j .

The global outranking index S, defined for all pairs of alternatives (x, y) ∈ X × X , conjunctively combines a global concordance index, aggregating all local "at least as good as" statements, and the absence of veto on each of the criteria. For any two alternatives x and y of X we have:

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

C(x, y) = j∈F w j • C j (x, y). (2.2)
The min operator in Formula 2.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). If all the V j are equal to -1 (no veto situation is observed), the resulting outranking index S equals the global concordance index C. Following Formulae (2.1) and (2.2), S is a function from X × X to L representing the credibility of the validation or nonvalidation of an outranking situation observed between each pair of alternatives. S is called the bipolar-valued characterisation of the outranking relation S, or for short, the bipolar-valued outranking relation.

The maximum value +1 of the valuation is reached in the case of unanimous concordance, whereas the minimum value -1 is obtained either in the case of unanimous discordance, or if there exists a strong veto situation on at least one criterion. The median situation 0 represents a case of undeterminateness: either the arguments in favour of an outranking are compensated by those against it or, a positive concordance in favour of the outranking is outbalanced by a potential (weak) veto situation.

It is now easy to recover the semantics linked to this bipolar-valued characterisation from our earlier considerations (see Sect. 2.1). For any two alternatives x and y of X , -S(x, y) = +1 means that assertion "x Sy" is clearly validated.

-S(x, y) > 0 means that assertion "x Sy" is more validated than non-validated.

-S(x, y) = 0 means that assertion "x Sy" is undetermined.

-S(x, y) < 0 means that assertion "x Sy" is more non-validated than validated.

-S(x, y) = -1 means that assertion "x Sy" is clearly non-validated.

Definition 2.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). The crisp outranking relation S can be constructed via its bipolar-valued characterisation. S is the set of pairs (x, y) of X × X such that S(x, y)>0. We write G(X, S) the corresponding so-called crisp outranking digraph associated to G (X, S).

Example 1 Consider the set X 1 ={a, b, c, d, e} of alternatives evaluated on a coherent family F 1 ={1,...,5} of criteria of equal weights (see left part of Table 1). To each criterion is associated a rational preference scale in [0, 1] and an indifference threshold of 0.1, a preference threshold of 0.2, a weak veto threshold of 0.6, and a strong veto threshold of 0.8. Based on the performances of the five alternatives on the criteria, we compute the bipolar-valued outranking relation S 1 shown in the right part of Table 1. The crisp outranking digraph G 1 (X 1 , S 1 ) associated to the bipolar-valued outranking digraph G 1 (X 1 , S 1 ) is shown in Fig. 1. Note the dotted 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 to the complement of S in X × X.

The reader, familiar with the Electre methodology, may have noticed much resemblance between the bipolar-valued characterisation S and the classical Electre-type valuations of an outranking relation. It is important to notice, however, that the latter do not necessarily respect the semantics of the bipolar credibility calculus. In particular, the 1/2 value does in general not have the meaning of undetermined validation which is given here to the 0 credibility degree. Furthermore, the bipolar valuation of the outranking relation is solely based on sums and differences of weights of individual criteria.

Let us now introduce some further concepts which are used in this article. The order n of the digraph G(X, S) is given by the cardinality of X , whereas the size p of G is given by the cardinality of S.

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. Definition 2.4 An odd chordless circuit (x i ) m
i=1 is a circuit of odd 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. Following a result by Bouyssou (Notes on bipolar outranking. Personal communication, August, 2006) which extends the results of [START_REF] Bouyssou | Outranking relations: do they have special properties?[END_REF] to the bipolar-valued case, it appears that, apart from certainly being reflexive, the bipolar-valued outranking digraphs do not necessarily have any particular relational properties such as transitivity or total comparability. Indeed he shows that, with a sufficient number of criteria, it is always possible to define a performance table such that the associated crisp outranking digraph renders any given reflexive binary relation. This rather positive result from a methodological point of view, namely that the outranking based methodology is universal, bears however a negative algorithmic consequence. Indeed, as we will show in Sects. 3 and 4, solving the choice problem based on a bipolar-valued outranking relation is a non-trivial algorithmic problem in case of non-transitive and partial outrankings.

Before switching to the following subsection, it is important to underline here that the starting point of this study is deliberately a given performance table, a set of threshold and veto functions as well as significance weights which are all clearly defined and have been acknowledged by the DM. 3Historically, in the context of outranking relations, the progressive choice problem has been solved by using the independent outranking set, i.e., the kernel of a digraph [START_REF] Roy | Classement et choix en présence de points de vue multiples (la méthode ELECTRE)[END_REF][START_REF] Roy | Aide multicritère à la décision : Méthodes et cas. Economica, Paris Roy B, Vanderpooten D[END_REF]. Let us now define this concept in a bipolar-valued outranking digraph.

On kernels in bipolar-valued outranking digraphs

Definition 2.5 Let Y be a non-empty subset of X . 1. Y is said to be outranking (resp. outranked) in G(X, S) 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. strictly independent) in G(X,

S) if and only if

for all x = y in Y we have S(x, y) ≤ 0 (resp. S(x, y) < 0). 3. Y is called an outranking (resp. outranked) kernel if and only if it is an outranking (resp. outranked) and independent set. 4. Y is called a determined outranking (resp. outranked) kernel if and only if it is an outranking (resp. outranked) and strictly independent set.

Example 1 (continued) In the crisp digraph G 1 (see Fig. 1) we can observe two determined outranking kernels, namely the singletons {b} and {c}. The digraph also contains one outranked kernel, namely the pair {d, e}. Note that alternatives d and e are independent (but not strictly independent) from each other.

The set Y 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 . The set Y is called a bipolar-valued characterisation of Y , or for short a bipolar-valued set in G(X, S). The semantics linked to this characterisation can again be derived from the properties of the bipolar-valued scale L (see Sect. 2.1).

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 link between the classical graph theoretic and algebraic representations of kernels (via their bipolar-valued characterisations).

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

max y =x [min( Y (y), S(y, x))] = -Y (x), for all x ∈ X ; (2.3) max y =x [min( S(x, y), Y (y))] = -Y (x), for all x ∈ X.
(2.4)

Let Y + and Y -denote the set of bipolar-valued sets verifying the respective kernel equation systems (2.3) and (2.4) above. Let Y 1 and Y 2 be two elements of

Y + (or Y -). Y 1 is said to be at least as sharp as Y 2 (denoted Y 2 Y 1 ) if and only if for all x in X either Y 1 (x) ≤ Y 2 (x) ≤ 0 or 0 ≤ Y 2 (x) ≤ Y 1 (x).
The relation defines a partial order (antisymmetrical and transitive) (Bisdorff 1997). If Y (x) = 0 for each x in X , Y is called a determined bipolar-valued set.

Theorem 2.7 (Bisdorff et al. 2006)

1. There exists a one-to-one correspondence between the maximal sharp determined sets in Y + (resp. Y -) and the determined outranking (resp. outranked) kernels in G.

Each maximal sharp set in Y

+ (resp. Y -) characterises an outranking (resp. out- ranked) kernel in G.
Proof The first result, specialised to determined sets, is proved in Bisdorff et al. (2006, Theorem 1). The second one results directly from the kernel equation systems of Proposition 2.6.

The maximal sharp sets in Y + (resp. Y -) deliver thus outranking (resp. outranked) kernel characterisations.

Let us furthermore underline, that it may also happen that neither Y + nor Y -contain any determined, or even partially determined sets at all. Such a case arises for example if G is an odd chordless circuit (see Definition 2.4).

Example 1 (continued) Recall that the crisp outranking digraph G 1 contains two outranking kernels and one outranked kernel. The bipolar-valued characterisations of these kernels are shown in Table 2. The outranking kernel {c} is more determined than In the past (see e.g., [START_REF] Bisdorff | Choice procedures in pairwise comparison multiple-attribute decision making methods[END_REF], the authors have promoted the most determined outranking kernel in a bipolar-valued outranking digraph G as a convenient choice recommendation in a progressive choice problem.

Example 1 (continued) The reader can indeed easily verify in the performance table of Example 1 (see Table 1) that alternative c is performing better than alternative b. Alternative a has very contrasted performances and d indisputably presents the worst performances.

However, recent well founded criticisms against the capacity of the outranking kernel concept to generate in general outranking digraphs a satisfactory and convincing choice recommendation led us to reconsider our method. We therefore revisit in the next section the pragmatic foundations of a progressive choice decision aiding methodology.

Foundations of the RUBIS choice decision aiding methodology

First, we revisit the choice problematique in order to identify the type of pragmatic decision aiding we are interested in. A brief comparison with the classical Electre methodology will underline similarities and differences with the Rubis one. Finally, we present new foundations for the choice decision aiding methodology.

The choice problematique

From a classical OR point of view, the choice problem is the search for one best or optimal alternative. From a decision aiding point of view, however, the assistance we may offer the DM depends on the nature of the decision aiding process we support.

Choice and elimination:

Following the tradition [START_REF] Roy | Aide multicritère à la décision : Méthodes et cas. Economica, Paris Roy B, Vanderpooten D[END_REF]Roy and Bouyssou 1993), we call choice problematique the category of decision problems consisting of the search for a single best alternative. Symmetrically to this choice problematique, we define the elimination problematique as the category of decision problems, whose objective it is to search for a single worst alternative.

The interest of considering both opposite problematiques will appear later in Sects. 3.3 and 4.3, where we show that, due to the intransitivity of the outranking relation, certain sets of alternatives can be considered a potential choice, as well as, a potential elimination recommendation (which makes the recommendation ambiguous in both problematiques).

Following the symmetric design of the bipolar credibility calculus, both the choice, and the elimination problematique can be tackled similarly. As the first one is much more common, we will in the sequel exclusively focus on the choice problematique.

Type of decision aiding process:

A decision aiding method is a particular way to solve a given decision problem. A choice recommendation is the output of such a decision aiding method in the particular context of the choice problematique.

Following the nature of the decision aiding process, we have to distinguish between two general kinds of choice problems. On the one hand, choice problems which require the single best alternative to be uncovered in a single decision aiding step, and, on the other hand, choice problems which allow to progressively uncover the single best alternative through the implementation of an iterative, progressive multiple step decision aiding process.

In the first case, a choice recommendation must always propose a single best alternative, whereas in the second case, the choice recommendation is a provisional advice that should, given the current available information, propose all plausible candidates for a final solution. It is in fact a set of potentially best alternatives which has to be refined via further interactions with the DM. We have here to clearly distinguish between a current and the eventual choice recommendation consisting ideally of the single best alternative. If not, this last recommendation requires to be further analysed by the DM himself, in view of determining his ultimate choice.

We focus in the sequel on the resolution of this progressive decision aiding problem, in the tradition of the classical Electre methods.

The Electre choice decision aiding method

The progressive choice problem is extensively discussed and promoted in the context of multiple criteria decision aiding in Roy and Bouyssou (1993) who explain that it is important that the non-retained alternatives for the current choice recommendation are left out for well-founded reasons, acknowledged and approved by the DM. Instead of forcing the decision aiding procedure to elicit a single best alternative at any cost, it is indeed preferable to obtain a set Y of potential candidates for the choice, as long as it can be plainly justified on the basis of the currently available preferential information.

Starting from this methodological position, Roy defines two principles for the construction of a choice recommendation. Subset Y of X is a choice recommendation if:

1. Each alternative which in not selected in Y is outranked by at least one alternative of Y . 2. The number of retained alternatives in the set Y is as small as possible.

The first principle counterbalances the second one. Indeed, it tends to keep the cardinality of the choice recommendation high enough to guarantee that no potentially best alternative is missed out. The second principle tends to keep its cardinality as small as possible in order to focus on the single best choice.

In the context of the Electre methods, [START_REF] Roy | Classement et choix en présence de points de vue multiples (la méthode ELECTRE)[END_REF][START_REF] Roy | Aide multicritère à la décision : Méthodes et cas. Economica, Paris Roy B, Vanderpooten D[END_REF] proposes to use as provisional choice recommendation the concept of outranking kernel, i.e., an independent and outranking set. One can indeed easily check that this recommendation verifies both principles. According to Roy, a choice recommendation has furthermore to be unique. The existence of a unique outranking kernel is, however, only guaranteed when the digraph does not contain any circuits at all [START_REF] Berge | Graphes et hypergraphes. Dunod, Paris Bisdorff R[END_REF]. To avoid a possible emptiness or multiplicity of outranking kernels, [START_REF] Roy | Classement et choix en présence de points de vue multiples (la méthode ELECTRE)[END_REF] initially proposed in the Electre I method to consider the alternatives belonging to maximal circuits as ties. The reduction of the outranking digraph along these ties results in a digraph that always admits a unique outranking kernel. The alternatives gathered in such a maximal circuit might, however, not be all equivalent and behave differently when compared to alternatives exterior to the circuit. Furthermore, the validation of the arcs of such a circuit may be problematic due to imprecision in the data or the preferential information provided by the DM. All in all, these difficulties in the clear interpretation of those circuits led to the development of the Electre IS method (see Roy and Bouyssou 1993). There, robustness considerations allow to remove certain arcs of the outranking digraph leading to a circuit-free graph containing a unique outranking kernel. Note finally that in both methods, the outranking relation is not viewed on a valued credibility scale. The double requirement of sufficient concordance and absence of vetoes is used instead for a crisp validation of pairwise outranking situations.

In this work we do not follow the same approach, even if the bipolar-valued framework would allow it. We instead revisit the very foundations of a progressive choice decision aiding methodology in order to discover how the bipolar-valued concept of outranking kernel may deliver a satisfactory choice recommendation without having to express doubts about a given bipolar-valued characterisation of the outranking relation.

New foundations for a progressive choice decision aiding methodology

In this subsection we introduce five principles (two from the previous discussion and three new ones) that the construction of a choice recommendation in a progressive decision aiding method should follow.

P 1 : Non-retainment for well motivated reasons

Each non-retained alternative must be put aside for well motivated reasons in order to avoid to miss any potentially best alternative.

A similar formulation is that each non-retained alternative must be considered as worse as at least one alternative of the choice recommendation.

P 2 : Minimal size The number of alternatives retained in a choice recommendation should be as small as possible.

This requirement is obvious when recalling that the goal of the choice problem is to find a single best alternative and that ultimately, a choice recommendation containing a single element concludes the progressive decision aiding process.

P 3 : Efficient and informative refinement Each step of the progressive decision aiding must deliver an efficient and informative refinement of the previous recommendation.

The currently delivered recommendation should focus on new and previously unknown preference statements, such that the progressive decision aiding process can converge to a single choice recommendation as quickly and efficiently as possible. Note that a progressive decision aiding process is not required to go on until a single best alternative can be recommended. As already mentioned, it may be up to the DM to determine the ultimate choice from the eventual recommendation of the decision aiding. Principle P 3 is quite similar to the previous principle and appears to make it redundant. In the following section, however, when implementing the Rubis method, their strategic difference will become apparent.

P 4 : Effective recommendation

The recommendation should not correspond simultaneously to a choice and an elimination recommendation.

This principle avoids the formulation of ambiguous recommendations, i.e., both outranking and outranked sets of alternatives, which could appear in intransitive and partial outranking relations. It is worthwhile noting that in a situation where all decision alternatives are either considered to be pairwisely equivalent or incomparable, no effective choice recommendation can be made.

P 5 : Maximal credibility

The choice recommendation must be as credible as possible with respect to the preferential knowledge available in the current step of the decision aiding process.

As the credibility degrees in the bipolar-valued outranking digraph represent the more or less overall concordance or consensus of the criteria to support an outranking situation, it seems quite natural that in the case of several potential choice recommendations, we recommend the one(s) with the highest determinateness of the membership assertions. As mentioned before, the first two principles are identical to those proposed by Roy (see Sect. 3.2). However, alone they are not sufficient to generate satisfactory choice recommendations. The three additional principles P 3 , P 4 , and P 5 will show their operational value when translated in Sect. 4 into properties in the bipolar-valued outranking digraph. Definition 3.1 A choice recommendation which verifies the five principles above is called a Rubis choice recommendation (RCR).

Our goal in the following section is to determine which graph theory-related object these properties characterise as a convincing choice recommendation.

Tackling the choice problem in the bipolar-valued outranking digraph

Let us note beforehand that obvious Rubis choice recommendations exist in case the outranking relation is transitive, namely all maximal alternative(s). However, as already mentioned earlier, the crisp outranking digraphs that we obtain from the bipolar-valued characterisation of an outranking relation are in general not transitive. This clearly motivates the necessity to find a procedure which computes a choice recommendation verifying the five principles for any possible reflexive binary relation.

Throughout this section, we illustrate our discourse via the following didactic example. 4Example 2 Let G 2 (X 2 , S 2 ) be a bipolar-valued outranking digraph, where X 2 = {a, b, c, d, e} and S 2 is given in Table 3 and the associated crisp digraph G 2 (X 2 , S 2 ) is represented in Fig. 2.

Let us now analyse the previously mentioned principles one by one and present their translations in terms of the concepts presented in Sect. 2. Note that all the directed concepts linked to an outranking property can symmetrically be reused in an elimination problematique via the corresponding outranked properties.

4.1 Non-retainment for well motivated reasons (principle: P 1 )

In terms of the bipolar-valued outranking relation, principle P 1 amounts to saying that each non-retained alternative should be outranked by at least one alternative of the choice recommendation.

R 1 : Outranking An RCR 5 is an outranking set in G(X, Y ).
Example 2 (continued) The sets {a, b, e}, {b, c, d}, as well as {a, b, c} for instance, are all outranking sets.

4.2 Minimal size and efficient and informative refinement (principles: P 2 and P 3 )

In this subsection we show that these two principles are closely linked. To rewrite principle P 2 of minimal size in the present context, we first need to define some concepts related to graph theory. The formal counterpart of the minimal size principle is therefore that of irredundancy of the set.

Example 2 (continued) {a, b, e}, {b, c, d}, {b, e, d}, and {a, c} are irredundant outranking sets. {a, b, c}, listed in the context of principle R 1 , is not irredundant outranking because alternative b has an empty private neighbourhood in this set. Let us now switch to principle P 3 (efficient and informative refinement), whose primary objective is to avoid that, in the case of a provisional choice recommendation, the DM may notice a best sub-choice without any further analyses. We require therefore that a choice recommendation Y should be such that the digraph restricted to the nodes of Y does not contain any obvious sub-choice recommendation. Consequently, at each stage of the decision aiding process, the provisional choice recommendation must focus on new and previously undetermined or unknown preference statements. Let us illustrate this with a short example.

Example 3 Consider the problem shown on the crisp digraph represented in Fig. 3. Both highlighted sets Y 1 = {a, b} and Y 2 = {a, d, e, f, . . . , z} verify the principles P 1 and P 2 as outranking irredundant sets. One would be tempted to prefer Y 1 to Y 2 because of its lower cardinality. Nevertheless, Y 1 contains information which is already confirmed at this stage of the progressive search, namely that the statement "a outranks b" is validated. In the case of the choice Y 2 , the next step of the search will focus on alternatives which presently are incomparable. If a further analysis step would focus on the set Y 1 , then it is quite difficult to imagine that the DM will be able to forget about the already confirmed validation of the statement "a outranks b". He will most certainly consider a as the choice, which might however not be the best decision alternative, as a is not outranking any of the alternatives of {d, e, f, . . . , z}.

According to principle P 3 we therefore recommend Y 2 as a choice recommendation.

In view of the previous considerations and the output generated by principles P 1 and P 2 , it is quite natural to define the concept of stability as follows:

Definition 4.3 An outranking (resp. outranked) set Y in G(X, Y ) is said to be sta- ble if and only if the induced subgraph G Y (Y, S| Y ) does not contain any irredundant outranking (resp. outranked) subset.
The outranking (resp. outranked) kernels (see Definition 2.5) of an outranking digraph verify this property of stability. Nevertheless, as already mentioned in Sect. 3.2 and as it is shown in the following property, the existence of an outranking (resp. outranked) kernel is not guaranteed in an outranking digraph.

Property 4.4 If a digraph G(X, S) has no outranking (resp. outranked) kernel, it contains a chordless circuit of odd order.

Proof This property represents the contraposition of Richardson's general result: if a digraph contains no chordless circuit of odd order, then it has an outranking (resp. outranked) kernel (see [START_REF] Richardson | Solution of irreflectice relations[END_REF].

The outranking kernel gives indeed a potential choice recommendation in case the outranking digraph does not contain any chordless circuit of odd order. Consider now the case where a potential choice recommendation, resulting from principles P 1 and P 2 , consists in a chordless circuit Y = {a, b, c} of order 3 such that aSb, bSc and cSa. Such a choice recommendation is clearly neither a kernel nor is it a stable recommendation. Nevertheless, it may be an interesting provisional recommendation because it presents three alternatives to the DM which do not contain obvious information on the possible single choice at this step of the progressive search. In fact, a, b and c can be considered as equivalent potential candidates for the choice in the current stage of the decision process.

Neither the concepts of stability and irredundancy nor that of outranking kernel are in fact sufficient for guiding the search for a choice recommendation in a general outranking digraph. In the first case, potentially interesting choice recommendations are left out and in the latter case, nothing guarantees the existence of a kernel in an outranking digraph. In order to overcome these difficulties, we introduce the concept of hyperindependence, an extension of the independence property discussed in Sect. 2.3. Definition 4.5 A set Y is said to be (strictly) hyperindependent in G if it consists of chordless circuits of odd order p ≥ 1 which are (strictly) independent of each other.

Note that in Definition 4.5 above, singletons are assimilated to chordless circuits of (odd) order 1. Principles P 2 and P 3 can now be translated into the following formal property:

R 2 : Hyperindependence An RCR is a hyperindependent set in G(X, Y ).
As a direct consequence, we can define the concept of hyperkernel.

Definition 4.6 A hyperindependent (resp. strictly hyperindependent) outranking (resp. outranked) set is called an outranking (resp. outranked) hyperkernel (resp. determined hyperkernel).

Example 2 (continued) Set {a, b, d, e} (see Fig. 2) is an outranking hyperkernel. The undetermined outranking relation between b and e implies that the set is not strictly hyperindependent. Note here that this obvious potential choice recommendation would have been left out if the search was restricted to outranking kernels.

In case the outranking digraph does not contain any chordless circuits of odd order 3 and more, the outranking kernels of the digraph deliver potential choice recommendations verifying the two first Rubis principles. In the general case however, the RCR will consist of at least one outranking hyperkernel of the digraph.

4.3 Effective and maximally credible recommendation (principles P 4 and P 5 )

In order to translate principle P 4 (effective recommendation), we introduce the concept of strict outranking set. Recall that one can associate an outranking (resp. outranked) set Y with a bipolar-valued characterisation Y + (resp. Y -). It may happen that both kernel characterisations are solutions of the respective kernel equation systems of Proposition 2.6. In order to determine in this case whether Y is in fact an outranking or an outranked set, it is necessary to specify which of its bipolar-valued characterisations is the more determined. We extend therefore the concept of determinateness of propositional statements (see Definition 2.2) to bipolar-valued characterisations of sets.

Definition 4.7 The determinateness D( Y ) of the bipolar-valued characterisation Y of a set Y is given by the average value of the determinateness degrees D( Y (x)) for all x in X .

In view of the bipolar definition of the global outranking and concordance indexes (Formulae 2.1 and 2.2), which solely balance rational significance weights, we define here the overall determinateness of a bipolar-valued set characterisation as the mean of all the individual membership determinatenesses. Nevertheless other aggregation operators could be used as well.

We can now define the concept of strictness as follows:

Definition 4.8

1. A set Y which is outranking and outranked with the same determinateness, i.e.,

D( Y + ) = D( Y -) is called a null set. 2. A set Y for which D( Y + ) > D( Y -) (resp. D( Y -) > D( Y + )) is called a strict
outranking set (resp. outranked set).

One can now translate the principle of effectiveness P 4 into the following formal property:

R 3 : Strict outranking An RCR is a strict outranking set in G(X, Y ).

This concept allows to solve the problem raised by the following example.

Example 4 Consider the crisp outranking digraph represented on Fig. 4 6 [for the sake of simplicity we suppose that all the arcs which are drawn (resp. not drawn) represent a credibility of the outranking of 1 (resp. -1)]. {a} and {c} are both irredundant outranking sets with the same maximal determinateness 1. However, one can easily see that alternative a compares differently with b than c does. Set {c} is clearly a null set.

If we now require the three properties R 1 , R 2 and R 3 to be verified, only the set {a} can be retained as a potential choice recommendation.

An immediate consequence of the effectiveness principle is that a bipolar-valued outranking digraph, which is completely symmetrical, i.e., with equal credibility degrees for all x Sy and ySx, does not admit any RCR. Every outranking set will automatically be a null set. Indeed, without any asymmetrical preferential statements, it is impossible to derive any preferential discriminations that would support a convincing choice recommendation. Finally, principle P 5 (maximal credibility) involves again the idea of determinateness of bipolar-valued sets (see Definition 4.7). In the case of multiple potential choice recommendations, we recommend the most determined one, i.e., the one with the highest determinateness. Let Y be the set of sets verifying R 1 , R 2 and R 3 in G(Y, S).

R 4 : Maximal determinateness

An RCR is a choice in G(X, S) that belongs to the set

Y * = Y ∈ Y|D( Y ) = max Y ∈ Y D( Y ) . (4.1)
Example 1 (continued) Recall that in this example (see Sect. 2.2), we determined two outranking kernels which were potential choice recommendations (see Table 4). The determinateness of the kernel {c} (0.36) is significantly higher than that of kernel {b} (0.20). Following property R 4 , we recommend in this case the first solution, namely kernel {c}.

In this section, we have presented the translation of the five Rubis principles into properties of sets of alternatives defined in the bipolar-valued outranking digraph. Detailed motivations for these principles have been given. They lead quite naturally to the new concept of outranking hyperkernel of an outranking digraph. Consequently, a maximally determined strict outranking hyperkernel, which by construction verifies all five principles, gives a Rubis choice recommendation.

The following section focuses on the construction of the hyperkernels and proposes a general algorithm for computing the Rubis choice recommendations in a given (non-symmetrical) bipolar-valued outranking digraph.

Computing the RUBIS choice recommendation

We start by presenting an algorithm which allows to determine the hyperkernels of an outranking digraph before presenting some of their properties.

Determination of the hyperkernels

If G(X, S) contains chordless circuits of odd order ( 3), the original outranking digraph is modified into a digraph that we will call the chordless-odd-circuitsaugmented (COCA) outranking digraph G C (X C , S C ). Intuitively, the main idea is to "hide" the problematic circuits behind new nodes which are added to the digraph in a particular way. This may appear to be a problematic perturbation of the original information. Nevertheless, as we will see later, such a transformation does not affect the original problem but only helps to find more suitable solutions.

The procedure to obtain the COCA digraph G C is iterative. The initial digraph is written G 0 (X 0 , S 0 ), and is equal to G(X, S). At step i, the set of nodes becomes X i = X i-1 ∪ C i , where C i is a set of nodes representing the chordless circuits of odd order of G i-1 (X i-1 , S i-1 ). These nodes are called hypernodes. The outranking relation S i-1 is augmented by links between the nodes from X i-1 and those from C i in the following way (the resulting relation is written S i )7 :

∀C k ∈ C i S i (C k , x) = y∈C k S i-1 (y, x) ∀x ∈ X i-1 \ C k , S i (C k , x) = +1 ∀x ∈ C k , (5.1) ∀x ∈ X i-1 , C k ∈ C i S i (x, C k ) = y∈C k S i-1 (x, y) if x / ∈ C k , S i (x, C k ) = +1 i f x ∈ C k .
(5.

2)

The iteration is stopped at step r for which |X r | = |X r +1 |. We then define G C (X C , S C ) as the digraph G r (X r , S r ). As the order of the original digraph G is finite, the number of circuits it may contain is also finite. Therefore, the iteration is a finite process. Note that this iterative approach is necessary because of the fact that new chordless circuits of odd order may appear when new hypernodes are added to the digraph. The outranking (resp. outranked) hyperkernels of G(X, S) are then determined by searching the classical outranking (resp. outranked) kernels of G C (X C , S C ) (Bisdorff 1997(Bisdorff , 2006b)).

Properties of the COCA outranking digraph

This extension of the digraph has two very important properties.

Property 5.1 The outranking (resp. outranked) kernels of G(X, S) are also the outranking (resp. outranked) kernels of G C (X C , S C ).

Proof Let us suppose that G contains at least one odd chordless circuit. Let Y be an outranking kernel of G (the case of the outranked kernels can be treated similarly). We must prove that Y is also an outranking kernel of G C . First, the elements of Y are independent in G and G C because no relation is added between elements of X in X C . Secondly, as Y is an outranking set in G, each element of X \ Y is outranked by at least one element of Y . In particular, if C k is an odd chordless circuit of X , each node of C k is also outranked by at least one element of Y (in X ). Due to the special way S C is built, the node representing C k in X C is also also outranked by at least one element of Y .

Property 5.2 The digraph G C (X C , S C ) contains at least one outranking (resp. outranked) hyperkernel.

Proof Following from the construction principle of the COCA digraph (see Eqs. 5.1, 5.2), a hypernode inherits the outranking (outranked) characteristics of its corresponding odd chordless circuit. A direct consequence of this inheritance is that the outranking, as well as the outranked, neighbourhood of the odd chordless circuit are inherited by the hypernode. Furthermore, the individual nodes of each odd chordless circuit are outranked by and are outranking the hypernode with a credibility of +1 (indifference).

Let us now suppose that G(X, S) contains no outranking kernel (a similar proof can be given for the outranked kernels). According to Property 4.4 this means that G(X, S) contains at least one odd chordless circuit. One can easily understand that if the structure of the digraph requires an element x ∈ X of an odd chordless circuit C k to be in an irredundant outranking set Y , due to the odd number of elements of that particular circuit, one of the two direct neighbours of x in the circuit will also be added to Y . Consequently, Y cannot be kernel in that situation.

Due to the particular construction of the associated COCA digraph G C , there exists, for each odd chordless circuit, a hypernode which inherits its properties, and which is considered as indifferent to it. Consequently, each element of each odd chordless circuit in G C is outranked by, and is outranking, a hypernode. Furthermore, each of the hypernodes has the same outranking and outranked neighbourhoods as its corresponding odd chordless circuit.

Finally, the element x of the odd chordless circuit C k will no longer be problematic in the construction of the outranking kernels of G C because there exists at least one hypernode which is equivalent to x, and which inherits from the outranking neighbourhoods of C k . Consequently C k (as a hypernode) is added to Y instead of x.

Finally we present and discuss the effective computing of a Rubis choice recommendation.

The RCR algorithm

Algorithm

Input: G(X, S), 1. Construct the associated COCA digraph G C (X C , S C ), 2. Extract the sets K + and K -of all outranking and outranked hyperkernels from G C , 3. Eliminate the null kernels from K + , 4. Rank the elements of K + by decreasing logical determinateness, Output: The first ranked element(s) in K + . The first step of the RCR (Rubis choice recommendation, see Definition 3.1) algorithm is by far the most difficult to achieve, as the number of odd chordless circuits in a bipolar-valued outranking digraph can be huge. To study this operational difficulty, we have compiled a sample of 1,000 bipolar-valued outranking digraphs generated from performances of 20 alternatives evaluated randomly on 7-20 criteria with random weights distributions and random thresholds. In nearly 98% of the sample, the time to compute the COCA digraph on a standard desktop computer is less than a second. In one case, we observe an execution time of around 30 s (due to a high number of odd chordless circuits in the digraph).

In Table 5, we note that nearly 75% of the sample digraphs do not admit any odd chordless circuit at all. In 100% of the observations less than ten hypernodes are added to the original outranking digraph.

The second step of the RCR algorithm concerns the extraction of hyperkernels from the COCA digraph. From a theoretical point of view, this step is well-known to be computationally difficult [START_REF] Chvátal | On the computational complexity of finding a kernel[END_REF]). However, this difficulty is directly linked to the arc-density, i.e., the relative size of the digraph. Indeed, only very sparse digraphs, showing an arc-density lower than 10% in the range of digraph orders which are relevant for the choice decision aiding problematique (10-30 alternatives), may present difficulties for the search of kernels. For the test sample of 1,000 random outranking digraphs of order 20, we observe a very high mean density of 82.6% with a standard deviation of 5.7%. Consequently, determining hyperkernels is in general a task which is feasible in a very reasonable time. Indeed, the mean execution time with its standard deviation for this step of the algorithm are around a thousandth of a second on a standard desktop computer.

Finally, eliminating the null hyperkernels and sorting the strict outranking hyperkernels in decreasing order of determinateness is linear in the order of the digraph and involves no computational difficulty at all.

Let us illustrate the RCR algorithm on the second example of this paper (see Sect. 4).

Example 2 (continued)The bipolar-valued outranking digraph of this example (see Fig. 2) contains a chordless circuit of order 3, namely {a, b, d}. The original digraph G 2 is extended to the digraph G C 2 which contains a hyper-node representing {a, b, d}. The corresponding outranking digraph admits an outranking kernel {a, c} and a hyperkernel {{a, b, d}, e} which is both outranking and outranked, but not with the same degree of determinateness (see Table 6). The first one is significantly more determined than the second one. Consequently, the Rubis "choice recommendation" is {{a, b, d}, e}, where alternative e is in an undetermined situation.

Let us finish this last section by indicating that all the examples of this paper have been computed with the free Python module digraphs (Bisdorff 2006a) which allows to manipulate bipolar-valued digraphs and to determine the RCR from a given performance table.

Concluding remarks

In this paper we defined new operational instruments, namely the strict outranking hyperkernel and the chordless circuits augmented digraph, which contribute to enrich the set of decision aiding tools for the choice problematique. New concepts, such as the Rubis choice recommendation, defined on a bipolar-valued outranking digraph, adapt and extend the traditional theoretical and pragmatic framework in which the choice problem is generally tackled. Some topics remain of course untouched. In particular, the authors' future challenge will be to illustrate with a successful Rubis decision aiding practice, that a DM may indeed enhance his actual choices.

  outranking neighbourhood + (x) of a node (or equivalently an alternative) x of X is the union of x and the set of alternatives which are outranked by x. 2. The outranking neighbourhood + (Y ) of a set Y is the union of the outranking neighbourhoods of the alternatives of Y .3. The private outranking neighbourhood+ Y (x) of an alternative x in a set Y is the set + (x) \ + (Y \ {x}).For a given alternative x of a set Y , the set + Y (x) represents the individual contribution of x to the outranking quality of Y . If the private outranking neighbourhood of x in Y is empty, this means that, when x is dropped from this set, Y still remains an outranking set. From this observation one can derive the following definition. Definition 4.2 An outranking (resp. outranked) set Y is said to be irredundant if all the alternatives of Y have non-empty private outranking (resp. outranked) neighbourhoods.

Fig. 3

 3 Fig.3Example 3: an unstable ({a, b}) and a stable({a, d, e, f, . . . , z}) set

Fig. 4

 4 Fig. 4 Example 4: illustration of the necessity of Property R 3

Table 1

 1 Example 1: random performance table and bipolar-valued outranking relation

	Alternatives	Coherent family of criteria			S 1
		1	2	3	4	5	a	b	c	d	e
	a	0.52	0.82	0.07	1.00	0.04	1.0	-0.2	-1.0	0.6	0.4
	b	0.96	0.27	0.43	0.83	0.32	0.4	1.0	0.2	0.2	0.4
	c	0.85	0.31	0.61	0.41	0.98	0.2	0.4	1.0	0.4	0.6
	d	0.30	0.60	0.74	0.02	0.02	-1.0	-1.0	-1.0	1.0 -1.0
	e	0.18	0.11	0.23	0.94	0.63	0.2	0.2	-0.4	0.0	1.0
	Fig. 1 Example 1: associated
	crisp digraph and undetermined
	arc

Table 2

 2 Example 1: bipolar-valued characterisations of the kernels {b} and is therefore the more credible instance. Indeed, one can easily verify that the degrees of logical determination of the membership assertions for {c} are higher than those for {b} (see Definition 2.2). Concerning the outranked kernel {d, e}, it is worthwhile noting that alternative d belongs to it with certainty, whereas the belonging of alternative e to this kernel depends on the undetermined situation d Se. In the context of a progressive method, if this latter outranking becomes more true than false at a later stage, then e can be dropped from the kernel without any regret. On the opposite, if the outranking becomes more non-validated than validated, then e remains part of the then determined kernel {d, e}.

	Y	a	b	c	d	e
	{b}	-0.2	0.2	-0.2	-0.2	-0.2
	{c}	-0.2	-0.4	0.4	-0.4	-0.4
	{d, e}	-0.6	-0.2	-0.4	1.0	0 .0

Table 3

 3 Example 2: the bipolar-valued outranking relation

	S 2	a	b	c	d	e
	a	1.0	0 .2	-1.0	-0.7	-0.8
	b	-0.6	1 .0	0 .8	1 .0	0 .0
	c	-1.0	-1.0	1 .0	0 .2	0 .8
	d	0.6	-0.6	-1.0	1 .0	-0.4
	e	-1.0	-0.8	-0.4	-0.6	1 .0
	Fig. 2 Example 2: the
	associated crisp digraph and an
	undetermined arc

Table 4

 4 Example 1: illustration of the maximal credibility principle

	Y	a	b	c	d	e	D ( Y )
	{c}	-0.2	-0.4	0.4	-0.4	-0.4	0.36	RCR
	{b}	-0.2	0.2	-0.2	-0.2	-0.2	0.20	-

Table 5

 5

	Number of odd chordless circuits in random bipolar-valued outranking	Number of odd chordless circuits	#	Rel. freq. (%)	Cum. freq. (%)
	digraphs of order 20 (1,000 observations)	0 1	735 116	73.5 11.6	73.5 85.1
		2	65	6.5	91.6
		3	25	2.5	94.1
		. . .	. . .	. . .	. . .
		9	1	0.1	100.0

Table 6

 6 Example 2: the associated COCA digraph with the bipolar-valued characterisations of its outranking (+) and outranked (-) hyperkernels

	S C 2	a	b	c	d	e	{a, b, d}	D
	a	0.1	0.2	-1.0	-0.7	-0.8	1.0
	b	-0.6	1.0	0.8	1.0	0.0	1.0
	c	-1.0	-1.0	1.0	0.2	0.8	0.2
	d	0.6	-0.6	-1.0	1.0	-0.4	1.0
	e	-1.0	-8	-0.4	-0.6	1.0	-0.6
	{a, b, d}	1.0	1.0	0.8	1.0	0.0	1.0
	{{a, b, d}, e} +	-0.6	-0.6	-0.6	-0.6	0.0	0 .6	0 .5
	{a, c} +	0.2	-0.2	0.2	-0.2	-0.2	-0.2 0	0.2
	{{a, b, d}, e} -	0.0	0.0	0.0	-0.6	0.0	0.6	0.2

Tackling impreciseness issues in these data is out of the scope of this paper. For first attempts to cope with this topic in a bipolar-valued credibility calculus framework, see[START_REF] Bisdorff | Concordant outranking with multiple criteria of ordinal significance. 4OR[END_REF]).

Roy B (2005) Private communication.

Rubis choice recommendation (see Definition 3.1).

Inspired fromRoy and Bouyssou (1993).

For the sake of simplicity, an element C k of C i will represent a node of X i as well as a the set of nodes of X i-1 representing the circuit C k .

Acknowledgements

The authors would like to thank Bernard Roy and an anonymous referee for their helpful comments.


Niloofar Charmchi

Caroline Collange

André Seznec

Compressed cache layout aware prefetching

Keywords: cache compression, compaction, hardware prefetching

The speed gap between CPU and memory is impairing performance. Cache compression and hardware prefetching are two techniques that could confront this bottleneck by decreasing last level cache misses. However, compression and prefetching have positive interactions, as prefetching benefits from higher cache capacity and compression increases the effective cache size. This paper proposes Compressed cache Layout Aware Prefetching (CLAP) to leverage the recently proposed sector-based compressed cache layouts such as SCC or YACC to create a synergy between compressed cache and prefetching. The idea of this approach is to prefetch contiguous blocks that can be compressed and co-allocated together with the requested block on a miss access. Prefetched blocks that share storage with existing blocks do not need to evict a valid existing entry; therefore, CLAP avoids cache pollution. In order to decide the co-allocatable blocks to prefetch, we propose a compression predictor. Based on our experimental evaluations, CLAP reduces the number of cache misses by 12% and improves performance by 4% on average, comparing to a compressed cache.

I. INTRODUCTION

One of the major challenges for computers is the speed gap between processor and main memory that affects the computer performance. In order to reduce this speed gap between off-chip memory and processor, on-chip memory, referred to as cache, is adopted. Since off-chip memory latency is high, finding techniques to minimize off-chip memory accesses is of essence. Methods such as cache compression and hardware prefetching can decrease the number of last level cache (LLC) misses [START_REF] Sardashti | Yet another compressed cache: A low-cost yet effective compressed cache[END_REF], [START_REF] Michaud | Best-offset hardware prefetching[END_REF]. Prefetching, however, increases the workload's working set size; it can evict useful data.

Our proposed compressed cache layout aware prefetcher (CLAP) finds a trade-off between the utility of prefetched data and the cache capacity. This positive interaction between hardware prefetching and cache compression results in performance improvement. Therefore, prefetching and compression can take advantage of each other. Compression can overcome the eviction of useful data by increasing effective cache size.

In this work we rely on the potentials of sector-based compressed caches for prefetching without causing cache pollution. To the best of our knowledge, this is the first prefetching technique that takes into account the layout of a compressed cache.

This paper makes the following contributions:

• We show that a substantial portion of the cache misses in compressed caches occur in blocks that could be allocated and compacted in a super-block that is already present in the cache. These misses could be avoided at no cost in cache capacity by bringing these blocks in the cache in advance (Section III). • Leveraging this opportunity, we propose CLAP, a unified system that benefits from prefetching and cache compression cooperatively (Section IV). • In order to identify which blocks should be prefetched, we propose a compression predictor (Section IV). • We evaluate the benefits of CLAP compared to a compressed cache without prefetching. Our proposed mechanism improves performance (4% on average) and reduces number of LLC misses (12% on average). Moreover, we show that our proposed strategy is also applicable to other prefetchers, such as next-line and stride (Section V).

II. CACHE COMPRESSION AND PREFETCHING

Cache compression is an important approach for performance enhancement in processors [START_REF] Alameldeen | Adaptive cache compression for high-performance processors[END_REF], [START_REF] Sardashti | A primer on compression in the memory hierarchy[END_REF], [START_REF] Chen | C-pack: A high-performance microprocessor cache compression algorithm[END_REF]. The key idea of cache compression algorithms is to obtain the benefit of larger caches, while retaining the area and power of smaller caches. Compressed caches use compression techniques [START_REF] Pekhimenko | Base-delta-immediate compression: practical data compression for on-chip caches[END_REF], [START_REF] Panda | Dictionary sharing: An efficient cache compression scheme for compressed caches[END_REF] to reduce the size of the cache blocks and compaction methods [START_REF] Sardashti | Yet another compressed cache: A low-cost yet effective compressed cache[END_REF], [START_REF] Sardashti | Decoupled compressed cache: Exploiting spatial locality for energy-optimized compressed caching[END_REF], [START_REF] Sardashti | Skewed compressed caches[END_REF] to allocate compressed blocks together into one data entry.

Hardware prefetching is an approach to reduce the number of cache misses. Multiple approaches have been proposed for hardware prefetching, such as stride prefetcher [START_REF] Fu | Stride directed prefetching in scalar processors[END_REF], next-line prefetcher [START_REF] Smith | Cache memories[END_REF] and offset prefetcher [START_REF] Michaud | Best-offset hardware prefetching[END_REF].

Raghavendra et al. [START_REF] Raghavendra | Pbc: Prefetched blocks compaction[END_REF] propose prefetched blocks compaction that can only compress and compact blocks that are prefetched, whereas our work applies compression and compaction techniques on all data in last level cache and it decides prefetching based on the compressiblity of a block. Patel et al. [START_REF] Patel | Scp: Synergistic cache compression and prefetching[END_REF] improve the STeMS prefetcher by taking advantage of compression, though the compressed cache does not directly benefit from prefetching.

Yet Another Compressed Cache (YACC) [START_REF] Sardashti | Yet another compressed cache: A low-cost yet effective compressed cache[END_REF] and Skewed Compressed Cache (SCC) [START_REF] Sardashti | Skewed compressed caches[END_REF] are among the cost-effective compressed cache layouts. Their objective is to pack the contiguous blocks of a single memory super-block in a single cache location. When all blocks in the super-block are compressible, a cache entry must be allocated for the first block, but the subsequent blocks do not require any extra cache space. The objective of this study is to exploit this opportunity to enable prefetching without pollution.

A sectored cache [START_REF] Liptay | Structural aspects of the system/360 model 85, ii: The cache[END_REF] is a set-associative cache that is designed using a shared tag among contiguous cache blocks. The YACC architecture considers a compressed cache as a sectored cache with variable number of sub-blocks per super-block depending on the compression ratio. Moreover, the address splitting of a conventional cache and a sectored/compressed cache are not the same. These two caches have different hash functions and, therefore, they generate different access patterns.

Dictionary Sharing (DISH) [START_REF] Panda | Dictionary sharing: An efficient cache compression scheme for compressed caches[END_REF] is a compression technique that takes advantage of the YACC layout. A common compression dictionary is shared among all sub-blocks of each super-block. In the remainder of the paper, we assume that DISH is used as the compression algorithm.

III. THE COMPRESSED CACHE UNDERUTILIZATION PROBLEM

A. Evaluating an LLC compressed cache

We have simulated an LLC compressed cache using DISH, for 27 benchmarks, following the evaluation methodology that will be described in Section V. In these settings, cache compression yields only modest improvements (maximum of 13% reduction in number of LLC misses for soplex benchmark), or may even cause more misses due to having consecutive uncompressed blocks compete for entries in the same set. Indeed, the potential capacity of the compressed cache may be underutilized due to factors such as non-compressibility or non-compactability of a block, lack of spatial locality and bulk evictions. Bulk eviction, which is the focus of this work, may happen in a compressed cache as replacement is performed at the granularity of super-blocks and all sub-blocks of a compressible super-block are evicted at once. However, it will take multiple misses to refill the compressible super-block. If we had prefetched these neighbor blocks in advance, we could have avoided the extra misses on the compressed super-block. Figure 1 shows the decision diagram of compressed cache operations on an access. The cache checks all super-blocks of the set for a tag match. If no match is found, the access is a miss. Otherwise, it checks the valid bit of the corresponding sub-block for each matching entry. Finding no such valid subblock also results in a miss.

B. Opportunities for compressed

In order to evaluate the potential of CLAP, we count the prefetching opportunities. As it is shown in Figure 1, the misses that occur on a super-block hit and sub-block miss are potential candidates for prefetching. If such block is coallocatable with the ones that are already present in the superblock, it could have been prefetched at no expense of capacity and the miss could have been avoided. Hence, we don't need to wait for miss accesses for each sub-block to refill the compressed super-block, thereby bulk evictions become less harmful for the cache.

We measure the percentage of misses that could be avoided by taking advantage of CLAP. Figure 2 shows the percentage of LLC misses that occur on blocks that are co-allocatable within an existing super-block blocks that are already present. We could reduce the number of misses by up to 28%, by prefetching compressed blocks before they are requested by the processor, without evicting any data from the cache. This study suggests that there is a potential for a synergistic interaction of prefetching and cache compression in processor architecture. Thus, by prefetching compressible blocks to L3, we seek the reduction in number of LLC misses.

IV. COMPRESSED CACHE LAYOUT AWARE PREFETCHING

In order to enhance cache compression and diminish underutilization of compressed cache, we propose CLAP, a compressed cache layout aware prefetcher. The goal is to avoid misses that happen on a co-allocatable block on a super-block hit and sub-block miss. In other words, if there is an access to a sub-block that is co-allocatable in the super-block, we could have prefetched it beforehand without any cache pollution. Thus, we could avoid this sub-block miss in the cache. In order to steer the prefetcher, we design a predictor that decides whether neighbor sub-blocks are compressible. By applying CLAP on miss accesses, we can prefetch the contiguous blocks if the block is predicted to be compressible.

A. Predicting compression

In order to find which blocks are co-allocatable and are candidate for prefetching before their content is available, we need a predictor. To achieve this goal, we implemented a compression predictor. As the predictor needs to predict the compressibility of blocks that have not been accessed recently or never accessed, a prediction based solely on the block address is not practical. Instead, we predict the compressibility of a stream of memory reads, where a stream corresponds to all accesses performed by a given load instruction in the program.

The key idea of stream-based prediction is that all memory locations accessed by a given load instruction are likely to share the same data-type and similar characteristics. Thus, whether prior blocks accessed by a load instruction were compressible is a good indicator of the compressibility of future blocks loaded from the same instruction.

We use a table indexed by a hash of the PC to store the compressibility likelihood of each load instruction and update it after every read miss. The PC table has 256 sets and 4 ways, using LRU replacement policy. Each entry in this table has a 4-bit saturating counter, a compression bit and a validity bit. The saturating counter and compression bit get updated after every refill response from the memory. Whenever the block is compressible, the saturating counter gets incremented; otherwise, it gets decremented. On every access, the predictor predicts whether a block is compressible, based on the counter. Accessing to the PC table is based on each PC that is carried in the request.

B. Compressed cache layout aware prefetcher

By means of the compression predictor and taking advantage of prefetching, we proposed a compressed cache layout aware prefetcher. Whenever a read request causes a superblock miss, the compression predictor is invoked. Based on the predictor's decision, the prefetcher pre-fetches either three blocks or no block: If it predicts the block is compressible, the cache sends three requests to prefetch the three neighbor subblocks in a super-block. In case the predictor predicts the block is not compressible, the system does not prefetch anything.

V. EVALUATION

We have implemented the DISH compression algorithm in the last level cache within the gem5 simulator [START_REF] Binkert | The gem5 simulator[END_REF]. We use SPEC CPU 2006 benchmarks. The statistics for the benchmarks are collected for 100M simulated instructions after a warm-up period of 50M instructions for 15 different execution snapshots. Table I shows the baseline configuration parameters with a conventional uncompressed cache. We consider a cache slice of 1MB, corresponding to the L3 cache share of a single core. Caches are non-inclusive, non-exclusive and have a write-back policy.

As it is illustrated in Figure 3, CLAP outperforms compressed cache. On average, it improves the performance by 4% comparing to compressed cache. Furthermore, CLAP reduces LLC misses of all applications by 12% on average.

A. Compression predictor

In order to implement CLAP, we propose a predictor to predict whether a sub-block is compressible. We have implemented an ideal compaction predictor which knows the future by accessing the memory beforehand to see whether the neighbor sub-blocks are co-allocatable. It predicts compactability based on the content of individual blocks, using their addresses and it only considers super-blocks that have 4 sub-blocks. However, our compression predictor prefetches all compressible blocks, regardless of compactability, which allows taking into account super-blocks that can hold 2, 3 or 4 sub-blocks.

The number of LLC misses obtained using our proposed compression predictor is within 3% on average (21% in the worst case for zeusmp benchmark) of the ideal compaction predictor. Therefore, our compression predictor is accurate enough to be employed to CLAP. Hence, we can prefetch even the blocks that are not co-allocatable (but only compressible), without increasing the number of misses, and they will be useful in the program.

B. Effective cache capacity

Cache compression increases the effective cache capacity, which can also be increased by taking advantage of prefetching. The effective cache capacity metric is defined as the average number of valid sub-blocks per valid super-block. Figure 4 shows the effective cache capacity for the compressed cache (DISH) and CLAP.

C. Interactions with other prefetchers

Our approach is orthogonal to other prefetching methods. We have employed the CLAP strategy to stride and nextline. Figure 5 shows the comparison between a compressed cache with stride prefetcher and a compressed cache with CLAP. In this configuration of CLAP, we do stride prefetching (with prefetch degree 16) on every cache access and when the compression predictor predicts a block is compressible, we prefetch three neighbor sub-blocks in the same super-block. Using this configuration, we manage to reduce the number of LLC misses by up to 31%. Moreover, we can take benefit of CLAP in a system with next-line prefetching and reduce LLC misses up to 29%.

D. Hardware overhead

The overhead of CLAP over the baseline prefetcher is the compression predictor table that is addressed by PC. The table has 256 × 4 entries and each entry has 46 bits (40-bit PC tag, 4-bit saturating counter, 1-bit compression bit, 1-bit validity bit). Hence, the table requires less than 6kB of memory, which is 0.56% of the 1MB LLC slice we consider. Increasing the cache size by this amount is unlikely to affect performance. This paper proposes CLAP, a hardware prefetcher that is adapted to sector-based compressed cache layouts. Such compressed caches that packs neighbor blocks together are subject to underutilization; therefore, there is a potential to enhance cache compression in systems. For this purpose, we proposed a compression predictor that predicts whether neighbor sub-blocks will be co-allocatable in the same super-block. By applying CLAP on miss accesses, we can prefetch the contiguous blocks if the block is predicted to be compressible. Based on our experiments, CLAP outperforms compressed cache in terms of MPKI (up to 33%) and IPC (up to 24%). Furthermore, we show that our proposed technique can be added to other prefetchers such as stride and next-line.

Fig. 1 :

 1 Fig. 1: Cache operations on read access

Fig. 2 :

 2 Fig. 2: Percentage of avoidable misses with CLAP

Fig. 5 :

 5 Fig. 5: Comparison of compressed cache with only stride prefetcher vs. stride and CLAP, as the number of LLC misses normalized to compressed cache without prefetching

TABLE I :

 I Simulation parameters

	Processor	ARMv8, 6-issue out-of-order at 4GHz
	L1 cache	32kB, 4-way, 2 cycles
	L2 cache	256kB, 8-way, 12 cycles
	L3 cache	1MB, 16-way, 20 cycles
	Cache line size	64-byte
	Replacement policy	LRU
	DRAM	DDR4 2400 MHz, bandwidth 12.8GB/s

VII. ACKNOWLEDGEMENTS

This project was partially supported by Région Bretagne and an Intel Research Grant. We would like to thank Daniel R. Carvalho for his help and also the reviewers for their insightful comments.


Maggie Le Bourhis-Zaimi

M.D Hélène Marini

M.D.b Julie Gueudry

M.D.c Emile Calenda

M.D Thomas Vermeulin

Noelle Frebourg

Ph.D Marc Muraine

Veronique Merle

M.D Noelle Frébourg

Ph.D Véronique Merle

Maggie Le Bourhis-Zaimia

M.D Véronique Merle

Incidence of postoperative nosocomial endophthalmitis: results of an eight-year prospective surveillance programme

Keywords: Postoperative endophthalmitis, cataract surgery, surveillance, surgical prophylaxis

Sir,

Endophthalmitis is a major complication of eye surgery [START_REF] Taban | Acute Endophthalmitis Following Cataract Surgery. A Systematic Review of the Literature[END_REF] . Infection control measures include epidemiological surveillance of nosocomial infections, are a component of hospital infection prevention [START_REF] Haley | The efficacy of infection surveillance and control programs in preventing nosocomial infections in US hospitals[END_REF] . In France, the 2010 guidelines [START_REF]Antibioprophylaxie in surgery and interventionnelle medicine (adult patients). Actualization 2010[END_REF] (SFAR) recommended antibiotic prophylaxis with oral levofloxacin, and indicate that intracameral cefuroxime injection could reduce the incidence of postoperative endophthalmitis but with a low level of evidence. With continuous improvement in surgical techniques and infection control measures, there is a need to assess current rates of postoperative endophthalmitis in routine practice.

The department of ophthalmology at our tertiary care university hospital in France performs 2000 surgical procedures each year. Patients receive a preoperative shower and face cleaning with povidone-iodine scrub the day before and the morning of surgery. In the operating room, after topical administration of tetracaine 1%, povidone-iodine 5% is applied to the skin around the eye and to the ocular surface and instilled in the fornix, before surgery. Until 2010, levofloxacin antibiotic prophylaxis was administered to patients with diabetes, long-term corticosteroid-therapy, or immunosuppressive therapy, and to patients undergoing secondary implantation, or revision surgery with an intraocular period of less than 1 month. Since 2010, levofloxacin antibiotic prophylaxis is also administered for procedures involving implantation of a device, excepting for cataract surgery. In 2011, intracameral injection of cefuroxime was introduced for cataract surgery, except for patients with allergies to cephalosporins and penicillin. The aim of our present study was to calculate the incidence of postoperative endophthalmitis through a prospective surveillance programme during an 8-year period between 2007 and 2014.

Prospective surveillance of postoperative endophthalmitis has been performed at our university hospital since November 2006. All intraocular surgical procedures, except reoperations for endophthalmitis, are included in the surveillance programme. Possible cases of endophthalmitis are identified via both systematic review of bacteriological samples and weekly meetings with eye surgery nurses and with the operating room team. Possible cases of infection are systematically presented to surgeons for validation. Diagnosis of postoperative endophthalmitis is based on the definitions issued by the Center for Disease Control (CDC) [START_REF] Garner | CDC definitions for nosocomial infections[END_REF] for nosocomial infections. All cases of endophthalmitis occurring within 30 days of intraocular surgery (or within 1 year for implants) are taken into account [START_REF] Mangram | The Hospital Infection Control Practices Advisory Committee. Guideline for Prevention of Surgical Site Infection[END_REF] . The number of surgical procedures is obtained via the hospital information system.

A total of 15865 intraocular surgeries (7425 cataract surgery procedures) were performed between 1st January 2007 and 31st December 2014, in 8245 men and 7620 women, median age of 67.7 years (0-102.4). Postoperative endophthalmitis was diagnosed in eight eyes of eight different patients, yielding an incidence of 0.05% (0.02-0.10: 95% CI). Cataract surgery procedures (with or without intraocular lens) accounted for seven of the eight cases of endophthalmitis yielding an incidence of 0.09% (0.04-0.19: 95% CI). The incidence of postoperative endophthalmitis after cataract surgery decreased from 0.32% in 2007 to 0% in 2014. The characteristics of infected patients are summarized in Table 1.

The incidence of postoperative endophthalmitis observed in our survey was low and decreased throughout the study period. We were not able to detect a significant difference

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

3 in the incidence of postoperative endophthalmitis after the introduction of intracameral antibiotic prophylaxis despite a reduction by half of the incidence of endophthalmitis during the period with cefuroxime versus the period without-cefuroxime. This may be explained by the small number of cases of endophthalmitis. The rate of endophthalmitis decreased in our study just after the surveillance programme was set up. This phenomenon has previously been described (under the name of Hawthorne effect) in some instances after the introduction of a nosocomial infection surveillance programme in hospitals [START_REF] Horan | Risk factors for incisional surgical site infection after caesarean section: results of a 5-year multicenter study[END_REF] , although not in a constant way [START_REF] Staszewicz | Thirteen years of surgical site infection surveillance in Swiss hospitals[END_REF] . The fact that the incidence of endophthalmitis remained stable between 2008 and 2014 after the initial decrease may be explained by the low baseline incidence of postoperative endophthalmitis at our university hospital. A study by Wykoff et al. with a similar population and long-term surveillance showed a significant decrease in rates in the 2002-2009 period only when compared with a reference period 20 years previously, suggesting that long-term follow-up is required to highlight a decrease in low rates of postoperative endophthalmitis [START_REF] Wykoff | Nosocomial acute-onset postoperative endophthalmitis at a university teaching hospital (2002-2009)[END_REF] .

The limitations of our study are that it was a single centre study and that in this real life survey we did not collect patients' characteristics. The strengths of our study are the large size of the cohort; the active search method for collecting data on postoperative infections combining several sources of information; the validation of endophthalmitis by both the infection control team and the surgeon; the low risk of missed diagnoses since ours is the only hospital in the region caring for patients with endophthalmitis;, and the fact that the same method was used consistently throughout the study period. In conclusion, our study, conducted in a large cohort, provides an up-to-date incidence rate for postoperative endophthalmitis, which could be used as a reference.

ACKNOWLEDGEMENTS

The authors thank Marie-Agnès Perrier for assistance with data collection and Tristan Petel for his contribution to the long-term prospective surveillance programme and for his invaluable assistance in data collection. We are also grateful to Nikki Sabourin-Gibbs, Rouen University Hospital, for her help in editing the manuscript.

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT