Denis Bouyssou
email: bouyssou@lamsade.dauphine.fr

Marc Pirlot
email: marc.pirlot@fpms.ac.be.cor-responding

An axiomatic analysis of concordance-discordance relations

Keywords: Multiple criteria analysis, Concordance, Discordance, Outranking methods, Conjoint measurement, Nontransitive preferences

published or not. The documents may come

Introduction

Building a preference relation on a set of alternatives evaluated on several attributes is the focal point of Multiple Criteria Decision Analysis (MCDA). The classical approach to achieve this goal consists in building a value function on the set of alternatives (see [START_REF] Keeney | Decisions with multiple objectives: Preferences and value tradeoffs[END_REF]. Since this approach requires a detailed analysis of the tradeoffs between attributes and is demanding in terms of time and information, it cannot always be used in practice. For this reason, alternative methods have been proposed among which the outranking methods that compare alternatives in a pairwise manner and decide which is preferred on the basis of their evaluations on the several attributes. They do not require a detailed analysis of tradeoffs and mainly rest on "ordinal" considerations (for detailed presentations of these methods, we refer to Bouyssou et al. 2006;[START_REF] Roy | The outranking approach and the foundations of ELECTRE methods[END_REF][START_REF] Roy | Aide multicritère à la décision : Méthodes et cas[END_REF][START_REF] Vincke | Multi-criteria decision aid[END_REF][START_REF] Vincke | Outranking approach[END_REF].

Most outranking methods, including the well known 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 | La méthode ELECTRE II : une application au mediaplanning[END_REF], base the comparison of alternatives on the so-called concordance / non-discordance principle. It leads to accepting the proposition that an alternative is "superior" to another if:

• concordance condition: the coalition of attributes supporting it is "sufficiently important",

• non-discordance condition: there is no attribute that "strongly rejects" it.

The fact that an alternative is "superior" to another can mean at least two different things. In the ELECTRE methods, superior means "not worse". Such methods aim at building a reflexive preference relation that is interpreted as an "at least as good as" relation. In general, these relations may lack nice transitivity or completeness properties (on these issues, see [START_REF] Bouyssou | On some properties of outranking relations based on a concordance-discordance principle[END_REF][START_REF] Bouyssou | Outranking relations: Do they have special properties? Journal of Multi-Criteria Decision Analysis[END_REF]. Our main goal in this paper is to characterize the reflexive binary relations that can be obtained on the basis of the concordancediscordance principle like in the ELECTRE I [START_REF] Roy | Classement et choix en présence de points de vue multiples (la méthode ELECTRE)[END_REF]) and ELECTRE II methods [START_REF] Roy | La méthode ELECTRE II : une application au mediaplanning[END_REF]. In doing so, we build on previous works aiming at characterizing the relations that can be obtained only using the first part of the concordance / non-discordance principle, i.e., the concordance condition (Bouyssou andPirlot 2005a, 2007).

In other methods, like the TACTIC method [START_REF] Vansnick | On the problems of weights in MCDM (the noncompensatory approach)[END_REF], superior means "strictly better than". Such methods build an asymmetric relation that is interpreted as strict preference. As in the reflexive case, irreflexive (or asymmetric) relations that can be obtained only using the concordance condition have been previously characterized in Bouyssou andPirlot (2002a, 2005b). While the correspondence between reflexive and irreflexive concordance relations is straightforward (they are codual of each other), this is no longer the case when the non-discordance condition comes into play. We examine this issue below, which will give us the opportunity to extend and integrate previous results on the subject.

As first presented in [START_REF] Bouyssou | A general model of preference aggregation[END_REF], the general strategy followed in this paper is to view outranking relations as a particular case of relations having a representation in the nontransitive decomposable models introduced in [START_REF] Bouyssou | Conjoint measurement without additivity and transitivity[END_REF], 2002b, 2004a); this was indeed our initial motivation for developing them. This particular case obtains when only a few distinct levels of preference differences are distinguished. This roughly leads to analysing "ordinal aggregation" as an aggregation in which there are only three types of preferences differences: positive, null and negative ones. This paper expands on this simple idea. It is organized as follows. Our setting is introduced in Section 2. Section 3 recalls what is needed of our previous results on the axiomatic characterization of concordance relations. We propose a characterization of reflexive concordance-discordance relations in Section 4. In Section 5, we consider the special case of reflexive concordance-discordance relations with attribute transitivity. In these relations, a transitive preference structure is postulated on each attribute as is the case in most methods used in practice. In Section 6, we investigate how our results may be used, through the use of coduality, to characterize asymmetric outranking relations produced by methods such as TACTIC. A final section discusses our results and positions them with respect to the existing literature on the subject, most notably the "noncompensation approach" developed in [START_REF] Bouyssou | Noncompensatory and generalized noncompensatory preference structures[END_REF] and the approach of Greco et al. (2001a).

With this paper, we more or less put an end to a research program started more than ten years ago (see [START_REF] Bouyssou | A general model of preference aggregation[END_REF]) and aiming at obtaining axiomatic foundations for outranking methods. In the course of this research, many intermediate results were obtained. This explains the large number of citations to some of our earlier papers. We beg the reader's leniency for that.

The setting 2.1 Binary relations

A binary relation R on a set A is a subset of A × A. We mostly write a R b instead of (a, b) ∈ R. A binary relation R on A is said to be:

• reflexive if [a R a], • complete if [a R b or b R a], • symmetric if [a R b] ⇒ [b R a], • asymmetric if [a R b] ⇒ [Not[b R a]], • transitive if [a R b and b R c] ⇒ [a R c], • Ferrers if [(a R b and c R d) ⇒ (a R d or c R b)], • semi-transitive if [(a R b and b R c) ⇒ (a R d or d R c)]
for all a, b, c, d ∈ A.

The codual of relation R on A is the relation R cd on A defined by:

a R cd b ⇔ Not[b R a], (1)
for all a, b ∈ A (we often write b R a instead of Not[b R a]). Taking the codual of a relation is an involutive operation, i.e., the codual of the codual of a relation is this relation. The codual of a complete relation is an asymmetric relation and conversely. Our use of the term "codual" follows [START_REF] Aleskerov | Utility Maximization, Choice and Preference[END_REF] [START_REF] Roubens | Preference modelling[END_REF], use the term "dual" for the same relation).

The asymmetric part of a relation R on A is the binary relation α[R] on A such that:

a α[R] b ⇔ a R b and Not[b R a] ⇔ a R cd b and Not[b R cd a], (2)
for all a, b ∈ A. Let us note that the asymmetric part of a relation is identical to the asymmetric part of its codual.

The symmetric part of a relation R on A is the binary relation σ[R] on A defined by:

a σ[R] b ⇔ a R b and b R a (3)
The completion of a relation R on A is the binary relation

R on A such that: a R b ⇔ a R b or [Not[a R b] and Not[b R a]] ⇔ a R b or a R cd b, (4)
for all a, b ∈ A. The completion of a relation is identical to the completion of its codual.

A weak order (resp. an equivalence) is a complete and transitive (resp. reflexive, symmetric and transitive) binary relation. If R is an equivalence on A, A/R will denote the set of equivalence classes of R on A. When R is a weak order, it is clear that σ[R] is an equivalence. We often abuse terminology and speak of the equivalence classes of R to mean the equivalence classes of σ [R].

A semiorder is a complete, Ferrers, semi-transitive binary relation. A strict semiorder is an asymmetric Ferrers, semi-transitive binary relation. It is easy to check that the asymmetric part of a semiorder is a strict semiorder. As first observed by [START_REF] Luce | Semiorders and a theory of utility discrimination[END_REF], any semiorder R on A induces a unique weak order R wo on A that is defined as follows:

a R wo b if ∀c ∈ A, [b R c ⇒ a R c] and [c R a ⇒ c R b].
(5)

Notation and definitions

In this paper will always denote a reflexive binary relation on a set X = n i=1 X i with n ≥ 2. Elements of X will be interpreted as alternatives evaluated on a set N = {1, 2, . . . , n} of attributes and as an "at least as good as" relation between these alternatives. We denote by (resp. ∼) the asymmetric (resp. symmetric) part of . A similar convention holds when is starred, superscripted and/or subscripted.

For any nonempty subset J of the set of attributes N , we denote by X J (resp. X -J ) the set i∈J X i (resp. i / ∈J X i ). With customary abuse of notation, (x J , y -J ) will denote the element w ∈ X such that w i = x i if i ∈ J and w i = y i otherwise. We sometime omit braces around sets. For instance, when J = {i} we write X -i and (x i , y -i ).

We say that attribute i ∈ N is influent (for ) if there are x i , y i , z i , w i ∈ X i and x -i , y -i ∈ X -i such that (x i , x -i ) (y i , y -i ) and (z i , x -i ) (w i , y -i ) and degenerate otherwise. A degenerate attribute has no influence whatsoever on the comparison of the elements of X and may be suppressed from N . As in Bouyssou and Pirlot (2005a), in order to avoid unnecessary minor complications, we suppose henceforth that all attributes in N are influent.

Concordance relations

In Bouyssou and Pirlot (2005a), we have given a general definition of concordance relations and have shown that the preference relations produced by most of outranking methods fit into this framework, provided that no veto effect occurs (i.e., when only the concordance part of the concordance / non-discordance principle is used). We recall this definition below, adding the term "reflexive" to it, since we shall consider irreflexive (or asymmetric) concordance-discordance relations in Section 6.

Definition 1 (Reflexive concordance relation) Let be a reflexive binary relation on X = n i=1 X i . We say that is a reflexive concordance relation (or, more briefly, that is an R-CR) if there are:

• a complete binary relation S i on each X i (i = 1, 2, . . . , n),
• a binary relation ¤ between subsets of N having N for union that is monotonic w.r.t. inclusion, i.e., for all

A, B, C, D ⊆ N such that A ∪ B = N and C ∪ D = N , [A ¤ B, C ⊇ A, B ⊇ D] ⇒ C ¤ D, (6)
such that, for all x, y ∈ X,

x y ⇔ S(x, y) ¤ S(y, x),

where S(x, y) = {i ∈ N : x i S i y i }. We say that ¤, S i is a representation of as an R-CR. Throughout the paper, P i (resp. I i ) will denote the asymmetric

(resp. symmetric) part of S i . Let A, B ⊆ N such that A ∪ B = N . We abbreviate [A ¤ B and B ¤ A] as A B and [A ¤ B and Not[B ¤ A]] as A £ B.
Let us illustrate this definition by some classic examples.

Example 2 (Simple majority preferences)

The binary relation is a simple majority preference relation if there is a weak order S i on each X i such that:

x y ⇔ |{i ∈ N : x i S i y i }| ≥ |{i ∈ N : y i S i x i }| .
A simple majority preference relation is easily seen to be an R-CR defining ¤ letting, for all

A, B ⊆ N such that A ∪ B = N , A ¤ B ⇔ |A| ≥ |B| . Q Example 3 (Semiordered weighted majority)
The binary relation is a semiordered weighted majority preference relation if there are a real number ε ≥ 0 and, for all i ∈ N ,

• a semiorder S i on X i ,

• a real number w i > 0, such that:

x y ⇔ i∈S(x,y)

w i ≥ j∈S(y,x) w j -ε.
Such a relation is easily seen to be a complete R-CR defining ¤ letting, for all A, B ⊆ N such that A ∪ B = N :

A ¤ B ⇔ i∈A w i ≥ j∈B w j -ε. Q 2.
i ∈ N , • a semiorder S i on X i , • a strict semiorder V i on X i such that V i ⊆ P i ,
• a positive real number w i > 0, such that, for all x, y ∈ X,

x y ⇔ i∈S(x,y) w i j∈N w j ≥ s and V (y, x) = ∅, where V (y, x) = {i ∈ N : y i V i x i }.
The "concordance part" of the ELECTRE I preference is what we obtain if there is no veto or, in other words, if the relation V i is empty. The concordance part of an ELECTRE I preference relation is easily seen to be an R-CR defining ¤ letting, for all

A, B ⊆ N such that A ∪ B = N , A ¤ B ⇔ i∈A w i j∈N w j ≥ s.
In practice, the relations S i and V i are usually obtained as follows, using a real-valued function u i defined on X i and a pair of positive thresholds pt i and vt i , with pt i ≤ vt i . We have, for all x i , y i ∈ X i ,

x i S i y i ⇔ u i (x i ) ≥ u i (y i ) -pt i (8) x i V i y i ⇔ u i (x i ) > u i (y i ) + vt i . (9)
The set V (y, x) is then the set of attributes on which u i (y i ) > u i (x i )+vt i , i.e., those on which y is "so much better" than x that it is excluded to conclude that x y. An intuitive interpretation of the ELECTRE I preference relation could therefore run as follows: x is at least as good as y if there is a majority of attributes on which x is at least as good as y (the attributes belonging to S(x, y) should be "sufficiently important") and there is no attribute on which x is too much worse than y (the set V (y, x) should be empty). Q ELECTRE I is an example of what we call a reflexive concordance-discordance relation, a precise definition of which follows.

Definition 5 (Reflexive concordance-discordance relation) Let be a reflexive binary relation on X = n i=1 X i . We say that is a reflexive concordance-discordance relation (or, more briefly, that is an R-CDR) if there are:

• a complete binary relation S i on each X i (i = 1, 2, . . . , n) (with asymmetric part P i and symmetric part I i ),

• an asymmetric binary relation

V i on each X i (i = 1, 2, . . . , n) such that V i ⊆ P i ,
• a binary relation ¤ between subsets of N having N for union that is monotonic w.r.t. inclusion, i.e., such that (6) holds, such that, for all x, y ∈ X,

x y ⇔ [S(x, y) ¤ S(y, x) and V (y,

x) = ∅] , (10)
where S(x, y) = {i ∈ N :

x i S i y i } and V (y, x) = {i ∈ N : y i V i x i }.
We say that ¤, S i , V i is a representation of as an R-CDR.

In the ELECTRE I method, when relations S i and V i are defined respectively using equations ( 8) and (9), we have V i ⊆ P i . It is also clear that S i is a semiorder. Similarly, the relation V i is a strict semiorder that is the asymmetric part of a semiorder U i that obtains as the codual of V i , i.e., is such that: for all x i , y i ∈ X i ,

x i U i y i iff Not[y i V i x i ] iff u i (x i ) ≥ u i (y i ) -vt i .
Since vt i ≥ pt i , it is clear that S i ⊆ U i (so that their asymmetric parts are related by the opposite inclusion: P i ⊇ V i ). We say that (S i , U i ) form a nested chain of semiorders (ordered by inclusion).

The nested chain (S i , U i ) has an additional crucial property. Using (5), consider the weak order S i wo associated to the semiorder S i and the weak order U i wo associated to the semiorder U i . From ( 8) and ( 9), it is clear that their intersection T i = U i wo ∩ S i wo is again a weak order. This additional property transforms the nested chain of semiorders (S i , U i ) into a homogeneous nested chain of semiorders.

Nested chains of two semiorders were first studied by [START_REF] Cozzens | Double semiorders and double indifference graphs[END_REF]. They appear as a particular case in a more general framework, analyzed in [START_REF] Doignon | Biorder families, valued relations and preference modelling[END_REF].

Remark 6

It is easy to add a non-discordance condition to the definition of the relations in Examples 2 and 3, yielding respectively a simple majority preference relation with veto and a semiordered weighted majority preference with veto. •

Background

In this section, we briefly present the axiomatic framework and the previously obtained characterization of reflexive concordance relations within this framework.

Conjoint measurement framework

Concordance relations rely on comparing alternatives in pairwise manner on the basis of preference differences on each attribute. The relations defined below were introduced in Bouyssou and Pirlot (2002b). They will play a fundamental rôle in the sequel.

Definition 7 (Relations comparing preference differences) Let be a binary relation on a set X = n i=1 X i . We define the binary relations * i and * * i on X 2 i letting, for all x i , y i , z i , w i ∈ X i ,

(x i , y i ) * i (z i , w i ) ⇔ [for all a -i , b -i ∈ X -i , (z i , a -i ) (w i , b -i ) ⇒ (x i , a -i ) (y i , b -i )], (x i , y i ) * * i (z i , w i ) ⇔ [(x i , y i ) * i (z i , w i ) and (w i , z i ) * i (y i , x i )].
The definition of * i suggests that (x i , y i ) * i (z i , w i ) can be interpreted as saying that the preference difference between x i and y i is at least as large as the preference difference between z i and w i . The definition of * i does not imply that the two "opposite" differences (x i , y i ) and (y i , x i ) are linked. This is at variance with the intuition concerning preference differences and motivates the introduction of the relation

RC 1 i if (x i , a -i ) (y i , b -i ) and (z i , c -i ) (w i , d -i )    ⇒    (x i , c -i ) (y i , d -i ) or (z i , a -i ) (w i , b -i ), RC 2 i if (x i , a -i ) (y i , b -i ) and (y i , c -i ) (x i , d -i )    ⇒    (z i , a -i ) (w i , b -i ) or (w i , c -i ) (z i , d -i ), for all x i , y i , z i , w i ∈ X i and all a -i , b -i , c -i , d -i ∈ X -i . We say that satisfies RC 1 (resp. RC 2) if it satisfies RC 1 i (resp. RC 2 i ) for all i ∈ N .
Condition RC 1 i is equivalent to requiring that any two preference differences are comparable in terms of * i . Condition RC 2 i imposes a "mirror effect" on the comparison of preference differences. This is summarized in the following:

Lemma 9 (Bouyssou and Pirlot 2002b, Lemma 1)

1. RC 1 i ⇔ [ * i is complete]. 2. RC 2 i ⇔ [for all x i , y i , z i , w i ∈ X i , (x i , y i ) * i (z i , w i ) ⇒ (y i , x i ) * i (w i , z i )]. 3. [RC 1 i and RC 2 i ] ⇔ [ * * i is complete].
4. In the class of reflexive relations, RC 1 and RC 2 are independent conditions.

We consider binary relations on X that can be represented in the following model introduced in Bouyssou and Pirlot (2002b):

x y ⇔ F (p 1 (x 1 , y 1 ), p 2 (x 2 , y 2 ), . . . , p n (x n , y n )) ≥ 0, (M)
where p i are real-valued functions on X 2 i that are skew symmetric (i.e., such that p i (x i , y i ) = -p i (y i , x i ), for all x i , y i ∈ X i ) and F is a real-valued function on n i=1 p i (X 2 i ) being nondecreasing in all its arguments and such that, abusing notation, F (0) ≥ 0. This model extends the additive nontransitive model studied in [START_REF] Fishburn | Continuous nontransitive additive conjoint measurement[END_REF][START_REF] Fishburn | Nontransitive additive conjoint measurement[END_REF], in which F is a sum.

It is useful to interpret p i as a function measuring preference differences between levels on attribute i ∈ N . The fact that the functions p i are supposed to be skew symmetric means that the preference difference between x i and y i is the opposite of the preference difference between y i and x i , which seems a reasonable hypothesis. In order to compare alternatives x and y, model (M) proceeds as follows. On each attribute i ∈ N , the preference difference between x i and y i is measured using p i . The synthesis of these preference differences is performed applying the function F to the p i (x i , y i )'s. We then conclude that x y when this synthesis is nonnegative. Given this interpretation, it seems reasonable to suppose that F is nondecreasing in each of its arguments. The fact that F (0) ≥ 0 simply means that the synthesis of null preference differences on each attribute should be nonnegative; this ensures that will be reflexive.

For finite or countably infinite sets, conditions RC 1 and RC 2 together with reflexivity are all that is needed in order to characterize model (M). We have:

Theorem 10 (Bouyssou and Pirlot 2002b, Theorem 1) Let be a binary relation on X = n i=1 X i . If, for all i ∈ N , X 2 i /∼ * * i is finite or countably infinite then has a representation (M) if and only if (iff ) it is reflexive and satisfies RC 1 and RC 2.

The extension of this result to the general case is easy but will not be useful here.

Characterization of concordance relations

The general strategy used in Bouyssou andPirlot (2005a, 2007) to characterize concordance relations is to use model (M) as a building block adding additional conditions ensuring that all functions p i take at most three distinct values. Hence, the "ordinal" character of the aggregation at work in concordance relations is modelled by saying that in an ordinal method, there can be at most three distinct types of preference differences: positive, null and negative ones. The additional conditions used in [START_REF] Bouyssou | Further results on concordance relations[END_REF] to capture concordance relations are as follows.

Definition 11 (Conditions M 1 and M 2) Let be a binary relation on a set X = n i=1 X i . This relation is said to satisfy:

M 1 i if (x i , a -i ) (y i , b -i ) and (z i , c -i ) (w i , d -i )    ⇒            (y i , a -i ) (x i , b -i ) or (w i , a -i ) (z i , b -i ) or (x i , c -i ) (y i , d -i ), M 2 i if (x i , a -i ) (y i , b -i ) and (y i , c -i ) (x i , d -i )    ⇒            (y i , a -i ) (x i , b -i ) or (z i , a -i ) (w i , b -i ) or (z i , c -i ) (w i , d -i ), for all x i , y i , z i , w i ∈ X i and all a -i , b -i , c -i , d -i ∈ X -i . We say that M 1 (resp. M 2) holds if M 1 i (resp. M 2 i ) holds for all i ∈ N .
It is not difficult to see that M 1 i and M 2 i drastically limit the possibility of distinguishing several classes of preference differences on each attribute using * i . Suppose for instance that the premises of M 1 i holds and that its first conclusion if false. Because (x i , a -i ) (y i , b -i ) and (y i , a -i ) (x i , b -i ), it is clear that the preference difference (y i , x i ) is not larger (w.r.t. the relation * i ) than its opposite preference difference (x i , y i ). In an R-CR, this can only happen if the difference (x i , y i ) is "positive" and, thus, the difference (y i , x i ) is "negative". But if the difference (x i , y i ) is "positive", there cannot exist a difference larger than (x i , y i ). Therefore if

(z i , c -i ) (w i , d -i ), we should obtain (x i , c -i ) (y i , d -i ).
This is what is required by M 1 i (disregarding its second possible conclusion that only ensures that the condition will be independent from the ones used to characterize model (M)). Condition M 2 i has a dual interpretation: if (y i , x i ) is not larger than its opposite preference difference (x i , y i ) then there can be no difference smaller than (y i , x i ).

Remark 12

In Bouyssou and Pirlot (2005a), we used two conditions that are stronger than M 1 i and M 2 i . It will prove useful to introduce them. The relation is said to satisfy: Bouyssou and Pirlot (2005a, Lemma 16) and Bouyssou and Pirlot (2007, Lemma 11) show that:

U C i if (x i , a -i ) (y i , b -i ) and (z i , c -i ) (w i , d -i )    ⇒    (y i , a -i ) (x i , b -i ) or (x i , c -i ) (y i , d -i ), LC i if (x i , a -i ) (y i , b -i ) and (y i , c -i ) (x i , d -i )    ⇒    (y i , a -i ) (x i , b -i ) or (z i , c -i ) (w i , d -i ), for all x i , y i , z i , w i ∈ X i and all a -i , b -i , c -i , d -i ∈ X -i .
1. U C i ⇒ M 1 i . 2. LC i ⇒ M 2 i . 3. U C i ⇔ [(y i , x i ) * i (x i , y i ) ⇒ (x i , y i ) * i (z i , w i ), for all x i , y i , z i , w i ∈ X i ]. 4. LC i ⇔ [(y i , x i ) * i (x i , y i ) ⇒ (z i , w i ) * i (y i , x i ), for all x i , y i , z i , w i ∈ X i ].
The problem with U C and LC is that they interact with RC 1 and RC 2 (see Bouyssou and Pirlot 2005a, Lemma 16). This explains our use of the slightly more involved conditions M 1 and M 2.

•

The following appears as Theorem 13 in [START_REF] Bouyssou | Further results on concordance relations[END_REF].

Theorem 13

Let be a binary relation on X = n i=1 X i . Then is an R-CR iff it is reflexive and satisfies RC 1, RC 2, M 1 and M 2. In the class of reflexive relations, conditions RC 1, RC 2, M 1 and M 2 are independent.

The above result demonstrates that the framework of model (M) is adequate for analyzing R-CR. We show below that this is also the case for R-CDR.

Characterization of reflexive concordancediscordance relations

The definition of a reflexive concordance-discordance relation has been given in Section 2.4 (Definition 5). In an R-CDR the concordance condition is tempered by a non-discordance condition forbidding to have x y when there is one attribute on which y is far better then x. In terms of preference differences, this adds the possibility of having two categories of negative differences: normal ones (acting as in an R-CR) and intolerable ones (corresponding to a veto).

The following lemma shows that an R-CDR is always a particular case of model (M) (i.e., conditions RC 1, RC 2 hold) and that, as in an R-CR, there can be only one type of positive differences (condition M 1 holds).

Lemma 14

If is an R-CDR then it satisfies RC 1, RC 2 and M 1.

Proof [RC 1] Let ¤, S i , V i be a representation of . Suppose that (x i , a -i ) (y i , b -i ), (z i , c -i ) (w i , d -i ). This implies that Not[y i V i x i ] and Not[w i V i z i ]. Suppose that y i P i x i . The definition of an R-CDR implies that (z i , a -i ) (w i , b -i ). If x i P i y i , the definition of an R-CDR implies that (x i , c -i ) (y i , d -i ). Suppose now that x i I i y i . If z i S i w i , we obtain, us- ing the definition of an R-CDR, (z i , a -i ) (w i , b -i ). If w i P i z i , using the definition of an R-CDR leads to (x i , c -i ) (y i , d -i ). [RC 2] Suppose that (x i , a -i ) (y i , b -i ), (y i , c -i ) (x i , d -i ). This implies that Not[y i V i x i ] and Not[x i V i y i ]. Suppose that x i S i y i . If z i S i w i , we know that Not[w i V i z i ] and the definition of an R-CDR leads to (z i , a -i ) (w i , b -i ). If w i S i z i , we know that Not[z i V i w i ]. The definition of an R-CDR leads to (w i , c -i ) (z i , d -i ). The proof is similar if we suppose that y i S i x i . [M 1] Suppose that (x i , a -i ) (y i , b -i ) and (z i , c -i ) (w i , d -i ). This implies that Not[y i V i x i ] and Not[w i V i z i ].
If y i S i x i , we know that Not[x i V i y i ] so that we have (y i , a -i ) (x i , b -i ), using the definition of an R-CDR. If x i P i y i , we know that Not[y i V i x i ] so that we have (x i , c -i ) (y i , d -i ), using the definition of an R-CDR. P

With Lemma 14 at hand, it is clear, in view of Theorem 13 that characterizes R-CR, that condition M 2 is, in general, not satisfied by R-CDR. This is due to the possible presence of a veto effect: it may happen that the premise of M 2 i is fulfilled while the conclusion is false because the pair (w i , z i ) belongs to V i . This motivates the introduction of the following condition that is satisfied by R-CDR as we shall show in the sequel. The work of Greco et al. (2001a) has been inspiring in devising it. Definition 15 Let be a binary relation on a set X = n i=1 X i . This relation is said to satisfy:

M 3 i if (x i , a -i ) (y i , b -i ) and (y i , c -i ) (x i , d -i ) and (z i , e -i ) (w i , f -i )            ⇒            (y i , a -i ) (x i , b -i ) or (z i , a -i ) (w i , b -i ) or (z i , c -i ) (w i , d -i ), for all x i , y i , z i , w i ∈ X i and all a -i , b -i , c -i , d -i , e -i , f -i ∈ X -i . We say that satisfies M 3 if it satisfies M 3 i for all i ∈ N .
The meaning of M 3 i can be intuitively expressed as follows. Suppose that the three premises of M 3 i hold and that its first conclusion is false (we disregard the second possible conclusion of M 3 i , the rôle of which is to ensure that the condition is independent from the ones needed to characterize model (M)). This implies that the difference (y i , x i ) is "negative" since it is not larger than its opposite difference (x i , y i ). In an R-CDR a negative preference difference is the smallest among all preference difference that do not correspond to a veto. Because (

z i , e -i ) (w i , f -i ), we know that Not[w i V i z i ]. Hence, the difference (z i , w i ) is not smaller than the difference (y i , x i ), so that (y i , c -i ) (x i , d -i ) implies (z i , c -i ) (w i , d -i ).
The following formalizes the above reasoning showing that condition M 3 holds in an R-CDR.

Lemma 16

If is an R-CDR then it satisfies M 3.

Proof Suppose that (x i , a -i ) (y i , b -i ), (y i , c -i ) (x i , d -i ) and (z i , e -i ) (w i , f -i ). By construction, we know that Not[x i V i y i ], Not[y i V i x i ] and Not[w i V i z i ]. If y i S i x i , the definition of an R-CDR implies (y i , a -i ) (x i , b -i ). If x i P i y i , the definition of an R-CDR implies (z i , c -i ) (w i , d -i ).
Hence M 3 i is fulfilled. P

The following lemma analyzes the structure of the relation * i under RC 1, RC 2, M 1 and M 3. It shows that when there are two distinct types of negative differences, the smallest ones can be interpreted as a veto.

Lemma 17

Let be a binary relation on

X = n i=1 X i . If satisfies RC 1, RC 2, M 1 and M 3, then, for all x i , y i , z i , w i , r i , s i ∈ X i , 1. (x i , y i ) * i (y i , x i ) ⇒ (x i , y i ) * i (z i , w i ). 2. [(x i , y i ) * i (y i , x i ) * i (z i , w i )] ⇒ (r i , s i ) * i (z i , w i ). Furthermore, we have (z i , a -i ) (w i , b -i ), for all a -i , b -i ∈ X -i .

Proof

Part 1 follows from results obtained in [START_REF] Bouyssou | Further results on concordance relations[END_REF]: by Lemma 11.3 in this paper, we know that RC 2 i and M

1 i imply U C i , i.e., that (y i , x i ) * i (x i , y i ) ⇒ (x i , y i ) * i (z i , w i ), for all x i , y i , z i , w i ∈ X i (see Remark 12). Since RC 1 i is equivalent to the fact that * i is complete, (y i , x i ) * i (x i , y i ) implies (x i , y i ) * i (y i , x i ), which proves Part 1.
Part 2. Suppose that, for some

x i , y i , z i , w i , r i , s i ∈ X i , we have (x i , y i ) * i (y i , x i ) * i (z i , w i ) and (z i , w i ) * i (r i , s i ). This implies (x i , a -i ) (y i , b -i ), (y i , a -i ) (x i , b -i ), (y i , c -i ) (x i , d -i ), (z i , c -i ) (w i , d -i ) and (z i , e -i ) (w i , f -i ), (r i , e -i ) (s i , f -i ), for some a -i , b -i , c -i , d -i , e -i , f -i ∈ X -i . Using M 3 i , (x i , a -i ) (y i , b -i ), (y i , c -i ) (x i , d -i ), (z i , e -i ) (w i , f -i ), (y i , a -i ) (x i , b -i ) and (z i , c -i ) (w i , d -i ) imply (z i , a -i ) (w i , b -i ). This leads to (y i , c -i ) (x i , d -i ), (z i , c -i ) (w i , d -i ), (z i , a -i ) (w i , b -i ) and (y i , a -i ) (x i , b -i ), contradicting the completeness of * i that follows from RC 1 i . Note that the contradiction is obtained as soon as (z i , e -i ) (w i , f -i ),
for some e -i , f -i ∈ X -i . This proves the second part of the assertion. P

Remark 18 It is clear that M 2 i implies M 3 i . Indeed, M 3 i is obtained from M 2 i by adding the premise (z i , e -i ) (w i , f -i ).
Example 38 below will show that there are reflexive relations satisfying RC 1, RC 2, M 1 on all attributes and M 3 i on all but one attribute. In view of Theorem 13, this shows that conditions RC 1, RC 2, M 1 and M 3 are independent in the class of reflexive relations.

•

For relations satisfying RC 1, RC 2, M 1 and M 3, we define a relation S i on X i , using * i for comparing each difference (x i , y i ) to its "opposite" difference (y i , x i ). Similarly, we introduce the veto relation V i when a difference is strictly smaller (in terms of * i ) than two opposite differences. The properties of these relations are studied in the following lemma.

Lemma 19

Let be a binary relation on X = n i=1 X i satisfying RC 1, RC 2, M 1 and M 3.

1. The relation S i on X i defined letting x i S i y i iff (x i , y i ) * i (y i , x i ) is complete.
Furthermore, letting P i denote the asymmetric part of S i , we have that z i P i w i and

x i P i y i imply (z i , w i ) ∼ * i (x i , y i ).
2. If x i I i y i and z i I i w i , where I i is the symmetric part of S i , then

(x i , y i ) ∼ * i (z i , w i ) ∼ * i (y i , x i ) ∼ * i (w i , z i ) ∼ * i (a i , a i ) for all a i ∈ X i . 3. Define the relation V i on X i letting x i V i y i if, for some z i , w i ∈ X i , (z i , w i ) * i (w i , z i ) * i (y i , x i ). We have: (a) V i ⊆ P i , (b) [z i V i w i and x i V i y i ] ⇒ (w i , z i ) ∼ * i (y i , x i ), (c) [x i P i y i , z i P i w i , Not[x i V i y i ] and Not[z i V i w i ]] ⇒ (y i , x i ) ∼ * i (w i , z i ). Proof Part 1. We have x i S i y i iff (x i , y i ) * i (y i , x i ).
Since * i is complete due to RC 1, it follows that S i is complete. Suppose now that z i P i w i and x i P i y i . Using Lemma 17, we have

(z i , w i ) * i (x i , y i ) and (x i , y i ) * i (z i , w i ) so that (z i , w i ) ∼ * i (x i , y i ). Part 2. Using the definition of S i , x i I i y i and z i I i w i is equivalent to (x i , y i ) ∼ * i (y i , x i ) and (z i , w i ) ∼ * i (w i , z i ).
The conclusion follows from RC 2. Part 3a. We have

x i V i y i iff (z i , w i ) * i (w i , z i ) * i (y i , x i ). Suppose that Not[x i P i y i ] so that (y i , x i ) * i (x i , y i ). Using RC 1 and RC 2, it is easy to check that (z i , w i ) * i (w i , z i ) implies (z i , w i ) * i (a i , a i ) * i (w i , z i ), for all a i ∈ X i . We therefore obtain (a i , a i ) * i (y i , x i ) * i (x i , y i ). This contradicts RC 2.
Part 3b. Suppose that x i V i y i and z i V i w i . Using Lemma 17.2, we have

(w i , z i ) * i (y i , x i ) and (y i , x i ) * i (w i , z i ) so that (w i , z i ) ∼ * i (y i , x i ). Part 3c. By definition, we have (x i , y i ) * i (y i , x i ) and (z i , w i ) * i (w i , z i ). Suppose that (y i , x i ) * i (w i , z i ). This would imply (x i , y i ) * i (y i , x i ) * i (w i , z i ), contradicting the fact that Not[z i V i w i ]. Similarly it is impossible that (w i , z i ) * i (y i , x i ). Hence, we have (y i , x i ) ∼ * i (w i , z i ). P Remark 20
With our definition of S i and V i , for any pair (x i , y i ), there are at most five possible situations:

• x i P i y i and x i V i y i ,

• x i P i y i and Not[x i V i y i ],

• x i I i y i , and the two remaining cases correspond to the first two cases in which the rôles of x i and y i have been exchanged. In terms of * i , we have shown that, for all z i , w i ∈ X i :

• In the first case, we have (x i , y i ) * i (z i , w i ) and (z i , w i ) * i (y i , x i ), for all z i , w i ∈ X i . Furthermore, it is never true that (y i , a -i ) (x i , b -i ).
• In the second case, we have (x i , y i ) * i (z i , w i ), for all z i , w i ∈ X i .

• In the third case we have (x i , y i )

∼ * i (y i , x i ) ∼ * i (z i , z i )
, for all z i ∈ X i .. Since we know by Lemmas 9 and 14 that * i is a weak order, this implies that * i has at most the following four equivalence classes, ordered in decreasing order by * i : (x i , y i ) belongs to

• class 1 iff x i P i y i • class 2 iff x i I i y i • class 3 iff y i P i x i and Not[y i V i x i ] • class 4 iff y i P i x i and y i V i x i .
The relation * * i , which is also a weak order, has at most five classes, the first class of * i being split into two subclasses depending on whether x i V i y i or not.

•

This leads to our characterization of R-CDR.

Theorem 21

Let be a reflexive binary relation on X = n i=1 X i . Then is an R-CDR iff it satisfies RC 1, RC 2, M 1 and M 3. These axioms are independent in the class of reflexive binary relations.

Proof

Necessity results from Lemmas 14 and 16. The independence of the axioms results from Remark 18. We show sufficiency.

Define the relation S i on X i letting x i S i y i if (x i , y i ) * i (y i , x i ). Let P i and I i respectively denote the asymmetric and the symmetric parts of S i . Using Lemma 19.1, we know that S i is complete. Note that, since all attributes have been supposed influent, P i is not empty. Indeed, * i being complete, the influence of i ∈ N implies that there are x i , y i , z i , w i ∈ X i such that (x i , y i ) * i (z i , w i ). If P i is empty, x i , y i , z i , w i fulfill the conditions of Lemma 19.2; hence (x i , y i )

∼ * i (z i , w i ), a contradiction. Define the relation V i on X i letting x i V i y i if, for some z i , w i ∈ X i , (z i , w i ) * i (w i , z i ) * i (y i , x i ). Using Lemma 19.3, we know that V i is included in P i .
Consider two subsets A, B ⊆ N such that A ∪ B = N and let:

A ¤ B ⇔ [x y, for some x, y ∈ X such that S(x, y) = A and S(y, x) = B].
Suppose that x y. Using Lemma 17.2, we must have V (y, x) = ∅. By construction, we have S(x, y) ¤ S(y, x).

Suppose now that V (y, x) = ∅ and S(x, y) ¤ S(y, x). Let us show that we have x y. By construction, S(x, y) ¤ S(y, x) implies that there are z, w ∈ X such that z w, S(x, y) = S(z, w) and S(y, x) = S(w, z). For all i ∈ N such that z i I i w i we have x i I i y i so that, using Lemma 19.2, (x i , y i ) ∼ * i (z i , w i ). For all i ∈ N such that z i P i w i we have x i P i y i so that, using Lemma 19.1, (x i , y i ) ∼ * i (z i , w i ). For all i ∈ N such that w i P i z i , we have y i P i x i . By hypothesis, we have Not[

y i V i x i ]. Because z w, we have Not[w i V i z i ].
Using Lemma 19.3c, we know that (x i , y i ) ∼ * i (z i , w i ). Hence, we have (x i , y i ) ∼ * i (z i , w i ), for all i ∈ N so that z w implies x y. It remains to show that ¤ is monotonic. Suppose that A ¤ B, so that, for some x, y ∈ X, S(x, y) = A, S(y, x) = B and x y. Since x y, we know that Not[y i

V i x i ], for all i ∈ N . Suppose that C ⊇ A, B ⊇ D such that C ∪ D = N . We first show that C ¤ B. Let E = C \ A; we have B ⊇ E. We build z, w ∈ X with S(z, w) = C ¤ S(w, z) = B.
We know that for all a i ∈ X i , we have a i I i a i . Using such pairs, define z, w ∈ X as follows:

A E B\E z x i a i x i w y i a i y i One verifies that V (w, z) = ∅, S(z, w) = A ∪ E = C and S(w, z) = B. For all i ∈ E ⊆ B, (a i , a i ) * i (x i , y i ).
Hence, using the definition of * i , we have x y implies z w. This implies that C ¤ B.

Starting from z and w and C ¤ B, we show that

C ¤ D for D ⊆ B. Since C ∪ D = N , we have B \ D ⊆ C. Let F = B \ D.
For all i ∈ N , P i is not empty so that we can take, for all i ∈ E any a i , b i ∈ X i such that a i P i b i . Using such pairs, define r, s ∈ X as follows:

C \ F F D r z i a i z i s w i b i w i
One verifies that V (s, r) = ∅, S(r, s) = C and S(s, r) = D. For all i ∈ F ⊆ C, we have (a i , b i ) * i (z i , w i ). Hence, using the definition of * i , we have z w implies r s. This implies that C ¤ D, which completes the proof. P

Remark 22

In Bouyssou and Pirlot (2005a, Lemma 2), we showed that, when all attributes are influent, the representation ¤, S i of an R-CR is always unique. It is important here to note that such a result does not hold for the representation ¤, S i , V i of an R-CDR. Indeed suppose that on some attribute i ∈ N , it is impossible that x y as soon as y i P i x i , i.e., (y i , x i ) * i (x i , y i ). This can be represented saying that it is never true that A ¤ B when i ∈ B together with V i = ∅. Alternatively, we may take the relation V i to hold as soon as (y i , x i ) * i (x i , y i ). The first option has been taken in the proof of Theorem 21. This leads to building a representation ¤, S i , V i of an R-CDR that uses a minimal amount of veto. We do not investigate here the additional conditions under which the representation ¤, S i , V i would be unique since this does not seem to add insight on the nature of these relations. These conditions have to do with the fact that for all attributes there are levels linked by S i but not by V i . Note however that assessment methods designed for R-CDR should be prepared to deal with this lack of uniqueness.

•

5 Concordance-discordance relations with attribute transitivity

Our definition of R-CDR in Section 4 does not require the relations S i or V i to possess any remarkable property besides the completeness of S i and the fact that V i ⊆ P i . This is at variance with what is done in most outranking methods (see the examples in Section 2.4). In this section, we show here how to characterize R-CDR with the following additional requirements:

• the relation S i is a semiorder,

• the veto relation V i is a strict semiorder such that V i ⊆ P i , • (S i , U i ) is a homogeneous nested chain of semiorders, where U i denotes the codual of V i .
for all i ∈ N . As discussed in Section 2.4, this will bring us quite close to the models that are used in practice.

As a first step, we show how to refine the framework provided by model (M).

Conjoint measurement framework continued

We first show, following Bouyssou and Pirlot (2004a), how to introduce a linear arrangement of the elements of each X i within the framework of model (M). The following relations play a fundamental rôle.

Definition 23 (Relations comparing the levels on each attribute) Let be a binary relation on a set X = n i=1 X i . We define the binary relations + i , - i and ± i on X i letting, for all x i , y i ∈ X i ,

x i + i y i ⇔ ∀a -i ∈ X -i , b ∈ X, [(y i , a -i ) b ⇒ (x i , a -i ) b], (11) x i - i y i ⇔ ∀a ∈ X, b -i ∈ X -i , [a (x i , b -i ) ⇒ a (y i , b -i )], ( 12
) x i ± i y i ⇔ x i + i y i and x i - i y i . ( 13
)
The definition of ± i suggests that there is a linear arrangement of the elements of X i . The relation reacts in a monotonic way when an element is substituted by another that is "above" the latter in the arrangement. However, nothing in model (M) ensures that the relation ± i is complete. This will indeed require extra conditions.

Remark 24

Let us note that, unsurprisingly, the relation ± i has strong relationships with * i and * * i . Using the definition of these relations, one checks directly that ± i is the trace of * i , i.e., we have, for all x i , y i ∈ X i :

x i + i y i ⇔ [∀z i ∈ X i , (x i , z i ) * i (y i , z i )] , x i - i y i ⇔ [∀w i ∈ X i , (w i , y i ) * i (w i , x i )] , x i ± i y i ⇔ ∀z i ∈ X i , (x i , z i ) * i (y i , z i ) and ∀w i ∈ X i , (w i , y i ) * i (w i , x i ). ( 14
)
It is easy to see that ± i is also the trace of * * i .

•

By construction, the relations + i , - i and ± i are always reflexive and transitive. Their completeness is related to the following axioms.

Definition 25 (Conditions AC 1, AC 2 and AC 3) We say that satisfies:

AC 1 i if x y and z w    ⇒    (z i , x -i ) y or (x i , z -i ) w, AC 2 i if x y and z w    ⇒    x (w i , y -i ) or z (y i , w -i ), AC 3 i if z (c i , a -i ) and (c i , b -i ) y    ⇒    z (d i , a -i ) or (d i , b -i ) y, for all x, y, z, w ∈ X, all a -i , b -i ∈ X -i and all c i , d i ∈ X i . We say that satisfies AC 1 (resp. AC 2, AC 3) if it satisfies AC 1 i (resp. AC 2 i , AC 3 i ) for all i ∈ N .
These three conditions are transparent variations on the theme of the Ferrers (AC 1 and AC 2) and semi-transitivity (AC 3) conditions that are made possible by the product structure of X. They are directly related to properties of relations + i , - i and ± i as stated in the next lemma.

Lemma 26

1. AC 1 i ⇔ + i is complete. 2. AC 2 i ⇔ - i is complete. 3. AC 3 i ⇔ [Not[x i + i y i ] ⇒ y i - i x i ] ⇔ [Not[x i - i y i ] ⇒ y i + i x i ]. 4. [AC 1 i , AC 2 i and AC 3 i ] ⇔ ± i is complete.
5. In the class of reflexive relations satisfying RC 1 and RC 2, AC 1, AC 2 and AC 3 are independent conditions.

Proof

See Bouyssou and Pirlot (2004b, Lemma 3) for Parts 1 to 4 and Bouyssou and Pirlot (2004a, Section 5.1.2) for Part 5. P

In Bouyssou and Pirlot (2004a), we consider binary relations on X that can be represented as:

x y ⇔ F (ϕ 1 (u 1 (x 1 ), u 1 (y 1 )), . . . , ϕ n (u n (x n ), u n (y n ))) ≥ 0, (M*)
where u i are real-valued functions on X i , ϕ i are real-valued functions on u i (X i ) 2 that are skew symmetric, nondecreasing in their first argument (and, therefore, nonincreasing in their second argument) and F is a real-valued function on n i=1 ϕ i (u i (X i ) 2 ) being nondecreasing in all its arguments and such that F (0) ≥ 0.

Going from model (M) to model (M*) amounts to requiring that each function p i measuring preference differences can be factorized as ϕ i (u i (x i ), u i (y i ))) thereby reflecting an underlying linear arrangement of the elements of X i .

The conditions introduced so far allow to characterize model (M*) when each X i is at most countably infinite. We have:

Theorem 27 (Bouyssou and Pirlot 2004a, Theorem 2) Let be a binary relation on a finite or countably infinite set X = n i=1 X i . Then has a representation (M*) if and only if it is reflexive and satisfies RC 1, RC 2, AC 1, AC 2 and AC 3.

Remark 28

Note that, contrary to Theorem 21, Theorem 27 is only stated here for finite or countably infinite sets X. This is no mistake: we refer to Bouyssou and Pirlot (2004a) for details and for the analysis of the extension of this result to the general case.

•

Although model (M*) is a particular case of model (M), it is still flexible enough to contain as particular cases models like the additive value function model [START_REF] Debreu | Topological methods in cardinal utility theory[END_REF][START_REF] Krantz | Foundations of measurement[END_REF]) or Tversky's additive difference model [START_REF] Tversky | Intransitivity of preferences[END_REF]. We show below that it also contains all R-CDR in which the relations S i and U i are semiorders and (S i , U i ) form a homogeneous nested chain of semiorders.

R-CDR with attribute transitivity

Let us first precisely define what we will call R-CDR with attribute transitivity (R-CDR-AT).

Definition 29 (R-CDR with attribute transitivity) An R-CDR with attribute transitivity (R-CDR-AT) is an R-CDR for which, for all i ∈ N :

• S i is a semiorder with asymmetric part P i ,

• V i is the asymmetric part of a semiorder U i with U i ⊇ S i and, hence,

V i ⊆ P i ,
• (S i , U i ) form a homogeneous chain of semiorders, i.e., there is a weak order R i on X i such that:

x i R i y i ⇒ ∀z i ∈ X i , [y i S i z i ⇒ x i S i z i ] and [z i S i x i ⇒ z i S i y i ], (15)
and

x i R i y i ⇒ ∀z i ∈ X i , [y i U i z i ⇒ x i U i z i ] and [z i U i x i ⇒ z i U i y i ]. ( 16
)
Remark 30

It is easy to check that when R i satisfies ( 15) and ( 16), we also have that:

x i R i y i ⇒ ∀z i ∈ X i , [y i P i z i ⇒ x i P i z i ] and [z i P i x i ⇒ z i P i y i ] (17)
and

x i R i y i ⇒ ∀z i ∈ X i , [y i V i z i ⇒ x i V i z i ] and [z i V i x i ⇒ z i V i y i ]. ( 18
)
This will be useful later.

•

The following lemma shows that all R-CDR-AT have a representation in model (M*).

Lemma 31

If is an R-CDR-AT then satisfies AC 1, AC 2 and AC 3.

Proof

Let ¤, S i , V i be a representation of the R-CDR-AT and let R i be the weak order obtained by intersecting the weak orders induced by the semiorders S i and U i .

[AC 1 i ]. Suppose that (x i , x -i ) (y i , y -i ) and (z i , z -i ) (w i , w -i ). We want to show that either (z i , x -i ) (y i , y -i ) or (x i , z -i ) (w i , w -i ).

From the hypothesis, we get that Not[

y i V i x i ] and Not[w i V i z i ]. Since R i is a weak order, either x i R i z i or z i R i x i . Suppose z i R i x i and observe that this together with Not[y i V i x i ] implies Not[y i V i z i ] (due to (18)). We show that (x i , x -i ) (y i , y -i ) implies (z i , x -i ) (y i , y -i ).
If y i P i x i , the conclusion follows from the monotonicity of ¤. If x i S i y i , we also have z i S i y i (using z i R i x i and ( 15)), hence the conclusion follows from the monotonicity of ¤ (if x i I i y i ) or directly (if x i P i y i ). The case in which x i R i z i leads to proving that (x i , z -i ) (w i , w -i ) in an analogous manner.

Hence AC 1 i holds. The proof for AC 2 i is similar, using the fact that either y i R i w i (and then (

x i , x -i ) (w i , y -i )) or w i R i y i (and then (z i , z -i ) (y i , w -i )). [AC 3 i ]. Suppose that (z i , z -i ) (x i , a -i ) and (x i , b -i ) (y i , y -i ). We want to show that either (z i , z -i ) (w i , a -i ) or (w i , b -i ) (y i , y -i ).
The hypothesis implies Not[

x i V i z i ] and Not[y i V i x i ]. We have either x i R i w i or w i R i x i . Assume the former. Together with Not[x i V i z i ] this entails Not[w i V i z i ].
As for AC 1 i , one easily shows that (z i , z -i ) (x i , a -i ) and x i R i w i yield (z i , z -i ) (w i , a -i ). The proof, assuming w i R i x i , is similar. P

The following lemma is an important step towards establishing a characterization of the R-CDR-AT.

Lemma 32

Let be a binary relation on X = n i=1 X i and assume that it is reflexive and satisfies RC 1, RC 2, AC 1, AC 2 and AC 3. Let i ∈ N and take a

i , b i ∈ X i such that (a i , a i ) * i (a i , b i ).
The binary relation T i on X i defined by:

x i T i y i if (x i , y i ) * i (a i , b i ) ( 19
)
is a semiorder and for all such a i , b i , the weak order induced by the semiorder T i contains the weak order ± i .

Proof

Using RC 1 i and RC 2 i , it is easy to show that we have (a i , a i )

∼ * i (b i , b i ), for all a i , b i ∈ X i . Hence, since it is supposed that (a i , a i ) * i (a i , b i ), it is clear that T i is reflexive. Lemma 9 implies that *
i is a weak order and Lemma 26 implies that ± i is also a weak order. Moreover, ± i is the trace of * i , i.e., ± i satisfies ( 14). We first show that T i has the Ferrers property, i.e., x i T i y i and z i T i w i imply x i T i w i or z i T i y i . Since ± i is complete, we either have y i ± i w i or the opposite. In the former case, (14) implies that (x i , w i ) * i (x i , y i ). From x i T i y i , we obtain (x i , y i ) * i (a i , b i ) and, since * i is transitive, we get (x i , w i ) * i (a i , b i ) and x i T i w i . Starting from w i ± i y i , one proves similarly that z i T i y i .

Establishing the semi-transitivity of T i amounts to show that x i T i y i and y i T i z i imply x i T i w i or w i T i z i for all x i , y i , z i , w i ∈ X i . Since ± i is complete, we either have y i ± i w i or the opposite. In the latter case, from w i ± i y i and equation ( 14), we get (w i , z i ) * i (y i , z i ). Using

y i T i z i , we have (y i , z i ) * i (a i , b i ) and, since * i is transitive, (w i , z i ) * i (a i , b i ), hence w i T i z i . Starting from y i ± i w i ,
one proves similarly that x i T i w i . We now prove that the weak order ± i is included in the weak order T i wo induced by T i , that is defined by:

x i T i wo y i if ∀z i ∈ X i , [y i T i z i ⇒ x i T i z i ] and [z i T i x i ⇒ z i T i y i ].
In view of ( 14), it is clear that x i ± i y i implies the condition that defines T i wo . It follows that ± i ⊆ T i wo . P

Applying the previous lemma to an R-CDR that satisfies AC 1, AC 2 and AC 3 yields the following result.

Lemma 33

If is an R-CDR that satisfies AC 1, AC 2 and AC 3 then it is an R-CDR-AT.

Proof

By Theorem 21, we know that satisfies RC 1, RC 2. We are thus in the conditions for applying Lemma 32. With S i as defined in Lemma 19.2 and using Remark 20, we see that S i is just the set of pairs belonging to the first two classes of * i , i.e., the set of pairs (x i , y i ) such that (x i , y i ) * i (x i , x i ). Applying Lemma 32 yields that S i is a semiorder.

In a similar way, using the definition of V i given in Lemma 19.3, we see that V i is formed of the pairs (x i , y i ) such that (y i , x i ) is in the fourth and last class of * i . It is thus a subset of the first class of * i (more precisely, it is the first class of * * i ). The relation V i is the asymmetric part of its codual U i which is easily seen to be formed of the three first classes of * i . Applying Lemma 32, we have that U i is a semiorder and that V i is the asymmetric part of a semiorder. By Lemma 19.3a, we know that V i is included in P i , so that S i is included in U i . Finally Lemma 32 guarantees that the intersection of the weak orders induced by the semiorders S i and U i contains the weak order ± i . It is thus complete, hence a weak order. We can thus take R i in Definition 29 to be ± i . This shows that ¤, S i , V i is a representation of the R-CDR with (S i , U i ) a nested homogeneous chain of semiorders. P

This leads to our characterization of R-CDR-AT.

Theorem 34

Let be a binary relation on X = n i=1 X i . Then is an R-CDR-AT iff it is reflexive and satisfies RC 1, RC 2, M 1, M 3, AC 1, AC 2 and AC 3. In the class of reflexive relations, these conditions are independent.

Proof

The characterization of R-CDR-AT results immediately from Lemma 31, Theorem 21 and Lemma 33. In view of proving the independence of the axioms, we provide below the seven required examples (in all these examples, one of the axioms is false on the first attribute. It is easy to adapt the examples to show that the axiom can be falsified on any attribute).

Example 35 (Not[AC 2 1 ]) Let X = X 1 × X 2 with X 1 = {x, y, z, w} and X 2 = {a, b}. We build an R-CDR on X with:

• w P 1 z, x P 1 z, y P 1 z, w P 1 x, y I 1 w, y I 1 x (and all I 1 loops)

• V 1 is empty except that y V 1 z,
• a P 2 b (and all I 2 loops) and the relation V 2 is empty,

• {1, 2} £ ∅, {1, 2} {2}, {1, 2} {1} and {1} {2}.
Observe that S 1 is a semiorder (the weak order it induces ranks the elements of X 1 in the following order: w, y, x, z). The relation V 1 is a strict semiorder that is included in P 1 . But (S 1 , U 1 ) is not a homogeneous family of semiorders on X 1 since the weak order induced by U 1 ranks y before w, while the weak order induced by S 1 does the opposite.

By construction, is an R-CDR. Hence, it satisfies RC 1, RC 2, M 1 and M 3. The relation contains all pairs in X × X except the following ones: One pair is common to these two series of four pairs, so that is equal to X × X minus the seven distinct pairs in the lists above.

• (z, b) (w,
On X 2 , it is easy to check that we have a ± 2 b, so that AC 1 2 , AC 2 2 and AC 3 2 hold.

On X 1 , it is easy to check that + 1 is complete. We indeed have that:

[y ∼ + 1 w] + 1 x + 1 z.
The relation - 1 is not complete. We have w - 1 x, y - 1 x and x - 1 z but neither y - 1 w nor w - 1 y since (z, a) (w, a) but (z, a) (y, a) and (x, b) (y, a) but (x, b) (w, a). This shows that AC 2 1 is violated. Condition AC 3 1 holds since + 1 and - 1 are not incompatible.

Q Example 36 (Not[AC 1 1 ] )
This example is a slight variant of the above one obtained by reversing all relations S i and V i . Let X = X 1 ×X 2 with X 1 = {x, y, z, w} and X 2 = {a, b}.

We build an R-CDR on X with:

• z P 1 x, z P 1 y, z P 1 w, x P 1 w, x I 1 y, y I 1 w,

• the relation V 1 is empty except that z V 1 y, • b P 2 a,
• the relation V 2 is empty,

• {1, 2} £ ∅, {1, 2} {2}, {1, 2} {1} and {1} {2}.

By construction, is an R-CDR. Hence, it satisfies RC 1, RC 2, M 1 and M 3.

The relation contains all pairs in X × X except the following ones: One pair is common to these two series of four pairs, so that is equal to X × X minus the seven distinct pairs in the lists above.

• (x, b) (z,
On X 2 , it is easy to check that we have b ± 2 a, so that AC 1 2 , AC 2 2 and AC 3 2 hold.

On X 1 , it is easy to check that - 1 is complete. We indeed have that:

z - 1 x - 1 [y ∼ - 1 w].
The relation + 1 is not complete. We have z + 1 x, x + 1 y and x + 1 w but neither y + 1 w nor w + 1 y since (y, b) (x, a) but (w, b) (x, a) and (w, a) (z, a) but (y, a) (z, a). This shows that AC 1 1 is violated. Condition AC 3 1 holds since

- 1 b - 1 [c ∼ - 1 d]). Q Example 38 (Not[M 3 1 ]) Let X = X 1 × X 2 × X 3 with X 1 = {x, y, z}, X 2 = {a, b} and X 3 = {p, q}.
Let us consider the relation such that:

x y ⇔ 3 i=1 p i (x i , y i ) ≥ 0,
the functions p i being such that:

p 1 (x, y) = p 1 (x, z) = p 1 (y, z) = p 1 (x, x) = p 1 (y, y) = p 1 (z, z) = 4, p 1 (y, x) = p 1 (z, y) = -1, p 1 (z, x) = -4 p 2 (a, b) = 2, p 2 (a, a) = p 2 (b, b) = 0, p 2 (b, a) = -2 p 3 (p, q) = 2, p 3 (p, p) = p 3 (q, q) = 0, p 3 (q, p) = -2.
It is easily checked that we have:

[(x, y) ∼ * 1 (x, z) ∼ * 1 (y, z) ∼ * 1 (x, x) ∼ * 1 (y, y) ∼ * 1 (z, z)] * 1 [(y, x) ∼ * 1 (z, y)] * 1 (z, x) x ± 1 y ± 1 z, (a, b) * 2 [(a, a) ∼ * 2 (b, b)] * 2 (b, a), a ± 2 b, (p, q) * 3 [(p, p) ∼ * 2 (q, q)] * 2 (q, p), p ±
3 q. This shows that RC 1, RC 2, AC 1, AC 2 and AC 3 are satisfied. Using the fact that U C i implies M 1 i (see Remark 12) shows that M 1 holds. Similarly, using the fact that LC i implies M 2 i and that M 2 i implies M 3 i shows that M 3 2 and M 3 3 hold. Condition M 3 1 is violated since (x, b, q) (y, a, p), (y, a, q) (x, b, q) and (z, a, p) (x, b, q) while (y, b, q) (x, a, p), (z, b, q) (x, a, p) and (z, a, q) (x, b, q). Q

Example 39 (Not[M 1 1 ]) Example 23 in [START_REF] Bouyssou | Further results on concordance relations[END_REF]

]) Let N = {1, 2, 3} and X = {x 1 , y 1 , z 1 , w 1 } × {x 2 , y 2 } × {x 3 , y 3 }. Let on X be identical to X 2 except that, for all a 1 , b 1 ∈ X 1 , all a 2 , b 2 ∈ X 2
and all a 3 , b 3 ∈ X 3 the following pairs are missing:

(a 1 , x 2 , x 3 ) (b 1 , y 2 , y 3 ), (z 1 , a 2 , a 3 ) (y 1 , b 2 , b 3 ), (x 1 , x 2 , x 3 ) (y 1 , x 2 , y 3 ), (x 1 , y 2 , x 3 ) (y 1 , y 2 , y 3 ), (z 1 , x 2 , x 3 ) (w 1 , y 2 , x 3 ), (z 1 , x 2 , y 3 ) (w 1 , y 2 , y 3 ),
(there is a total of 35 such pairs). It is clear that is reflexive. For i ∈ {2, 3}, it is easy to check that we have:

[(y i , x i ), (x i , x i ), (y i , y i )] * i (x i , y i ), which shows that RC 1 2 , RC 1 3 , RC 2 2 and RC 2 3 hold.

For i ∈ {2, 3}, we also have:

y i + i x i and y i - i x i , which shows that AC 1 2 , AC 1 3 , AC 2 2 , AC 2 3 , AC 3 2 and AC 3 3 hold.
By Lemma 16 in Bouyssou and Pirlot (2005a), it is clear that LC 2 , LC 3 , U C 2 and U C 3 hold, which, by Lemma 11 in [START_REF] Bouyssou | Further results on concordance relations[END_REF], implies that M 1 2 , M 1 3 , M 2 2 and M 2 3 hold. Because M 2 i implies M 3 i , we know that M 3 2 and M 3 3 hold.

On attribute 1, it is easy to check that we have:

(c 1 , d 1 ) * 1 (x 1 , y 1 ), (c 1 , d 1 ) * 1 (z 1 , w 1 ), (x 1 , y 1 ) * 1 (z 1 , y 1 ), (z 1 , w 1 ) * 1 (z 1 , y 1 ),
for all (c 1 , d 1 ) ∈ Γ = {(x 1 , x 1 ), (x 1 , z 1 ), (x 1 , w 1 ), (y 1 , x 1 ), (y 1 , y 1 ), (y 1 , z 1 ), (y 1 , w 1 ), (z 1 , x 1 ), (z 1 , z 1 ), (w 1 , x 1 ), (w 1 , y 1 ), (w 1 , z 1 ), (w 1 , w 1 )}. The pairs (x 1 , y 1 ) and (z 1 , w 1 ) are not comparable in terms of * 1 since (x 1 , x 2 , x 3 ) (y 1 , y 2 , x 3 ) and (z 1 , x 2 , x 3 ) (w 1 , y 2 , x 3 ), while (z 1 , x 2 , x 3 ) (w 1 , x 2 , y 3 ) and (x 1 , x 2 , x 3 ) (y 1 , x 2 , y 3 ). Hence, RC 1 1 is violated.

It is easy to check that RC 2 1 and, using Lemma 16 in Bouyssou and Pirlot (2005a), that U C 1 holds. Hence, we know that M 1 1 holds (Bouyssou and Pirlot 2007, Lemma 11). We have:

[y 1 ∼ + 1 w 1 ] + 1 x 1 + 1 z 1 , y 1 - 1 w 1 - 1 [x 1 ∼ - 1 z 1 ],
which shows that AC 1 1 , AC 2 1 and AC 3 1 hold. It remains to check that M 3 1 holds. The three premises of

M 3 1 are that (a 1 , a -1 ) (b 1 , b -1 ), (b 1 , c -1 ) (a 1 , d -1 ) and (c 1 , e -1 ) (d 1 , f -1 ). The three possible conclusions of M 3 1 are that (b 1 , a -1 ) (a 1 , b -1 ) or (c 1 , a -1 ) (d 1 , b -1 ) or (c 1 , c -1 ) (d 1 , d -1 ). Suppose first that (b 1 , a 1 ) ∈ Γ. In this case, we have (b 1 , a 1 ) * 1 (a 1 , b 1 ), so that (a 1 , a -1 ) (b 1 , b -1 ) implies (b 1 , a -1 ) (a 1 , b -1
). Hence, the first conclusion of M 3 1 holds.

If (b 1 , a 1 ) = (z 1 , y 1 ), the second premise of M 3 1 is never satisfied, so that the condition trivially holds.

Suppose now that (b 1 , a 1 ) = (x 1 , y 1 ). If (c 1 , d 1 ) is distinct from (z 1 , w 1 ) and (z 1 , y 1 ), we have (c 1 , d 1 ) * 1 (x 1 , y 1 ), so that (b 1 , c -1 ) (a 1 , d -1 ) implies (c 1 , c -1 ) (d 1 , d -1 ) and the third conclusion of M 3 1 holds.

If (c 1 , d 1 ) = (z 1 , y 1 ), the third premise of M 3 1 is never satisfied, so that the condition trivially holds.

If (c 1 , d 1 ) = (z 1 , w 1 ), it is easy to check that there are no a -1 , b -1 ∈ X -1 such that (y 1 , a -1 ) (x 1 , b -1 ), (x 1 , a -1 ) (y 1 , b -1 ) and (z 1 , a -1 ) (w 1 , b -1 ), so that no violation of M 3 1 is possible in this case.

A similar reasoning shows that the same is true if it is supposed that (b 1 , a 1 ) = (z 1 , w 1 ). Hence, M 3 1 holds. P

In Bouyssou andPirlot (2005a, 2007), we have studied reflexive concordance relations with attribute transitivity (R-CR-AT). These relations are just R-CR admitting a representation ¤, S i in which all S i are semiorders. These are clearly a special case of R-CDR-AT (Definition 29) in which all V i are empty relations. For further reference, we recall the characterization of R-CR-AT obtained as Theorem 26 in [START_REF] Bouyssou | Further results on concordance relations[END_REF].

Theorem 42 (Characterization of R-CR-AT) A relation on X is an R-CR-AT iff it is reflexive and satisfies RC 1, RC 2, M 1, M 2, AC 1, and AC 3. In the class of reflexive relations, these axioms are independent.

The characterization of R-CR-AT only differs from that of R-CDR-AT by the substitution of axiom M 3 by axiom M 2 and the omission of AC 2, which, in presence of the other conditions is equivalent to AC 1 (see Bouyssou and Pirlot 2005a, Lemma 27).

6 Strict and non-strict preference models: discordance vs bonus Models of preference aim at capturing either strict or non-strict preference. The latter usually corresponds to an "at least as good" relation while strict preference refers to a "better than" relation. For the special case of concordance relations, we have studied and characterized strict (asymmetric) concordance relations (see Bouyssou andPirlot 2002a, 2005b) and non-strict concordance relations (see Bouyssou andPirlot 2005a, 2007). The purpose of this section is to extend and unify these results. One would expect that strict and non-strict concordance relations are related. More precisely, it would be natural that a strict concordance relation is the asymmetric part of a non-strict concordance relation. We shall see below that this is actually the case and that their axiomatic characterizations are related as well.

This picture changes however when discordance comes into play. The relationship between non-strict concordance-discordance preference models, like ELECTRE I (see Example 4) and strict concordance-discordance preference models like TACTIC [START_REF] Vansnick | On the problems of weights in MCDM (the noncompensatory approach)[END_REF] and Example 53 below) is not entirely straightforward, as we shall see.

In our analysis of the correspondence between strict and non-strict preference models, coduality, as defined by (1), will play an important rôle.

Strict and non-strict concordance relations

We start by recalling the definition of a strict (asymmetric) concordance relation (as introduced in Bouyssou and Pirlot 2002a). We present it here as a special case of a more general "irreflexive concordance relation". Although this more general concept is clearly of little practical interest, it will be useful for discussing relationships with reflexive concordance relations (R-CR).

Definition 43 (Irreflexive concordance relation (I-CR))

Let P be an irreflexive binary relation on X = n i=1 X i . We say that P is an irreflexive concordance relation (or, more briefly, that P is an I-CR) if there are:

• an asymmetric binary relation P

• i on each X i (i = 1, 2, . . . , n),
• a binary relation £ • between disjoint subsets of N that is monotonic w.r.t. inclusion, i.e., such that (6) holds, such that, for all x, y ∈ X,

x P y ⇔ P • (x, y)

£ • P • (y, x), ( 20
)
where P • (x, y) = {i ∈ N :

x i P • i y i }.
A strict concordance relation is an irreflexive concordance relation that is asymmetric. We also call such a relation an asymmetric concordance relation (A-CR).

If an R-CR is a complete relation, then its asymmetric part is also the codual of since, by definition of the codual (1), we have x cd y iff y x. We illustrate the coduality between asymmetric I-CR and complete R-CR by the following example.

Example 44 (TACTIC, Vansnick 1986) The binary relation P is an asymmetric semiordered weighted majority preference relation if there are a real number ε ≥ 0 and, for all i ∈ N ,

• the asymmetric part

P • i of a semiorder S • i on X i ,
• a real number w i > 0, such that:

x P y ⇔ i∈P • (x,y) w i > j∈P • (y,x) w j + ε, where P • (x, y) = {i ∈ N : x i P • i y i }. Clearly, the relation P just defined is the codual of the one in Example 3. Indeed, Not[y P x] is equivalent to j∈P • (y,x) w j ≤ i∈P • (x,y) w i + ε, hence, i∈P • (x,y) w i ≥ j∈P • (y,x) w j -ε. Adding the term ∈I • (x,y) w (where I • (x, y) = { ∈ N : x I • y } and I • is the symmetric part of S • )
to both sides, one gets the definition of x y as given in Example 3. Q If a relation is not complete it is no longer the case that its asymmetric part is its codual. However, we cannot make the hypothesis that is complete without excluding interesting reflexive concordance relations (consider, e.g., Example 4 with V i = ∅ and s 1 2 ). In the rest of this section, we try to clarify the relationship between strict and non-strict concordance relations in the general case of non-necessarily complete relations. We start with two lemmas.

Lemma 45

The codual of an R-CR is an I-CR and conversely.

Proof

Let be an R-CR and ¤, S i a representation of . We obtain a representation of cd as an I-CR by taking:

• P • i = S i cd (P • i is asymmetric since S i is complete, by hypothesis), • for all A, B ⊆ N such that A ∩ B = ∅, A £ • B if [N \ B] ¤ [N \ A], (21)
noticing that

[N \ A] ∪ [N \ B] = N implies A ∩ B = ∅.
The required monotonicity property of £ • directly follows from that of ¤.

Conversely, starting from an I-CR, P, and its representation £ • , P • i , one obtains a representation ¤, S i of P cd by putting:

• S i = P • i cd (S i is complete since P •
i is asymmetric, by hypothesis);

• for all A, B ⊆ N such that A ∪ B = N , A ¤ B if [N \ B] £ • [N \ A], (22)
noticing that

[N \ A] ∩ [N \ B] = ∅ implies A ∪ B = N .
The required monotonicity property of ¤ follows from that of £ • . P Lemma 46 1. The completion of an R-CR is an R-CR;

2. The asymmetric part of an I-CR is an I-CR and, hence, an A-CR.

Proof

(1) Let be an R-CR with a representation ¤, S i . The completion of is defined by x y iff x y or [x y and y x]. We obtain a representation ¤, S i of as an R-CR by defining ¤ as follows: for all A, B ⊆ N such that

A ∪ B = N , A ¤ B if [A ¤ B or Not[B ¤ A]]. (23)
Using this definition, we prove that ¤ is monotone. (2) Let P be an I-CR with a representation £ • , P • i . A representation as an I-CR of the asymmetric part α[P] of P is obtained by taking, for all

A, B ⊆ N such that A ∩ B = ∅, A £ • B if A £ • B and Not[B £ • A]. (24)
The monotonicity of £ • is easily obtained using the monotonicity of £ • . Indeed, assume that A £ • B, C ⊇ A and D ⊆ B. By definition, we have

A £ • B and Not[B £ • A]. Clearly, A £ • B implies C £ • D and Not[B £ • A] implies Not[D £ • C]. Hence A £ • B implies C £ • D.
It is easy to check that the relation having £ • , P • i as a representation is indeed an asymmetric I-CR, i.e., an A-CR. P

Using the above lemmas, we can easily prove the expected relationships between R-CR and I-CR.

Proposition 47 1. The asymmetric part of an R-CR is an I-CR (and, hence, an A-CR).

2. The completion of an I-CR is an R-CR.

Proof

(1). Let be an R-CR with a representation ¤, S i . Its asymmetric part is also the asymmetric part of its codual cd . We know by Lemma 45 that cd is an I-CR and by Lemma 46.2 that the asymmetric part of it, which is , is an I-CR.

(2). Let P be an I-CR with a representation £ • , P • i . The completion of P is identical to the completion of its codual P cd , which is an R-CR by Lemma 45. Since the completion of an R-CR is an R-CR (Lemma 46.1), the result follows. P

Characterizations of strict and non-strict concordance relations

The correspondence through coduality between reflexive and irreflexive concordance relations (Lemma 45) is reflected in the axiomatizations of strict and non-strict concordance relations, which we discussed respectively in Bouyssou and Pirlot (2002aPirlot ( , 2005b) ) (strict (asymmetric) concordance relations) and Bouyssou andPirlot (2005a, 2007) (non-strict (reflexive) concordance relations). In this section, we examine the relationships between the axioms that characterize reflexive and irreflexive concordance relations. Consider an R-CR . Its codual, cd , which is not necessarily asymmetric, is an I-CR. From Theorem 13, we know that is an R-CR if and only if it is reflexive and satisfies RC 1, RC 2, M 1 and M 2. By Theorem 42, we know that satisfies, in addition, attribute transitivity (i.e., is an R-CR-AT) iff it also satisfies AC 1 and AC 3 (or AC 2 and AC 3, since in presence of the other conditions, AC 1 and AC 2 are equivalent). Since we want to characterize the codual of , it is interesting to observe the behavior of the axioms RC 1, RC 2, M 1, M 2, AC 1, AC 2 and AC 3 through contraposition. In fact, our discussion will not depend on whether we start with a reflexive relation or an irreflexive relation cd and impose on the latter or the former one of the axioms above. Our results are valid for any relation even non-reflexive or non-irreflexive. Therefore, in the following discussion, we express the axioms using the generic notation R for denoting any relation on X, and R cd , for denoting its codual.

Consider a relation R on X that is assumed to satisfy RC 1 i . The contraposition of RC 1 i is a condition naturally expressed in terms of the codual of R. We have:

R satisfies RC 1 i ⇔ Not[(x i , c -i ) R (y i , d -i )] and Not[(z i , a -i ) R (w i , b -i )]    ⇒    Not[(x i , a -i ) R (y i , b -i )] or Not[(z i , c -i ) R (w i , d -i )] ⇔ (y i , d -i ) R cd (x i , c -i ) and (w i , b -i ) R cd (z i , a -i )    ⇒    (y i , b -i ) R cd (x i , a -i ) or (w i , d -i ) R cd (z i , c -i ), (25) for all x i , y i , z i , w i ∈ X i and all a -i , b -i , c -i , d -i ∈ X -i .
Clearly, (25) is axiom RC 1 i expressed in terms of relation R cd . Hence, we have that R satisfies RC 1 1 iff its codual does. One shows similarly that it is also the case for RC 2 i . We refer to this property saying that axioms RC 1 and RC 2 are self-dual.

The picture is not exactly the same with M 1 and M 2. Contraposition of

M 1 i yields: R satisfies M 1 i ⇔ (x i , b -i ) R cd (y i , a -i ) and (z i , b -i ) R cd (w i , a -i ) and (y i , d -i ) R cd (x i , c -i )            ⇒    (y i , b -i ) R cd (x i , a -i ) or (w i , d -i ) R cd (z i , c -i ), (26) for all x i , y i , z i , w i ∈ X i and all a -i , b -i , c -i , d -i ∈ X -i .
Condition ( 26) is exactly axiom M aj2 i in Bouyssou and Pirlot (2005b), imposed to relation R cd . Paraphrasing this result, imposing M 1 i to R is tantamount to imposing M aj2 i to its codual R cd and conversely. In a similar way, starting from condition M 2 i imposed on R, we obtain the following equivalent condition on R cd : for all x i , y i , z i , w i ∈ X i and all

a -i , b -i , c -i , d -i ∈ X -i , (x i , b -i ) R cd (y i , a -i ) and (w i , b -i ) R cd (z i , a -i ) and (w i , d -i ) R cd (z i , c -i )            ⇒    (y i , b -i ) R cd (x i , a -i ) or (x i , d -i ) R cd (y i , c -i ). (27)
Condition ( 27) is exactly axiom M aj1 i in Bouyssou and Pirlot (2005b), imposed to relation R cd . Again, imposing M 2 i to R is equivalent to imposing M aj1 i to its codual R cd and conversely.

Dealing in the same way with axioms AC 1, AC 2 and AC 3, it is easy to show that R has property AC 1 i (resp. AC 2 i ) iff its codual satisfies AC 2 i (resp. AC 1 i ). Condition AC 3 i is self-dual.

We collect our findings in the next lemma. Its proof results from the above observations. Lemma 48 Let R be any relation on X and R cd its codual. We have the following equivalences, for all i ∈ N :

1. R satisfies RC 1 i iff R cd satisfies RC 1 i ; 2. R satisfies RC 2 i iff R cd satisfies RC 2 i ; 3. R satisfies M 1 i iff R cd satisfies M aj2 i (i.e., condition (26)); 4. R satisfies M 2 i iff R cd satisfies M aj1 i (i.e., condition (27)); 5. R satisfies AC 1 i iff R cd satisfies AC 2 i ; 6. R satisfies AC 3 i iff R cd satisfies AC 3 i .
Using Lemma 48 it is straightforward to derive the following characterization of an irreflexive concordance relation I-CR (resp. of an I-CR with attribute transitivity I-CR-AT) from Theorem 13 (resp. from Theorem 42).

Proposition 49 (Characterization of I-CR and I-CR-AT) A relation P on X is an I-CR iff it is irreflexive and satisfies RC 1, RC 2, M aj1, and M aj2. A relation P is an I-CR-AT iff it is irreflexive and satisfies RC 1, RC 2, M aj1, M aj2, AC 2 and AC 3. In the class of irreflexive relations, RC 1, RC 2, M aj1, M aj2, AC 2 and AC 3 are independent.

Proof A relation is an I-CR iff its codual is an R-CR (Lemma 45). Using the characterization of an R-CR (Theorem 13) and Lemma 48, we get the result. Obviously, if a relation is an I-CR-AT, its codual is an R-CR-AT and we obtain the result using Theorem 42 and Lemma 48. The independence of the axioms results from coduality and the fact that RC 1, RC 2, M 1, M 2, AC 1 and AC 3 are independent axioms (Theorem 42). P

Remark 50

The first part of Proposition 49 has been obtained, for asymmetric relations, in Bouyssou and Pirlot (2006, Theorem 2). The characterization of I-CR-AT has not appeared before. A variant of this characterization is obtained by substituting axiom AC 2 by axiom AC 1. It indeed results from Bouyssou and Pirlot (2005a, Lemma 27) that AC 1 and AC 2 are equivalent in the class of R-CR. •

Remark 51

Proposition 49 also offers a characterization of strict (asymmetric) concordance relations and of strict concordance relations with attribute transitivity. The independence of axioms RC 1, RC 2, M aj1 and M aj2 in the class of asymmetric relations has been established in Bouyssou and Pirlot (2006).

Axioms RC 1, RC 2, M aj1, M aj2, AC 1 and AC 3 are independent in the class of asymmetric relations since axioms RC 1, RC 2, M 1, M 2, AC 1 and AC 3 are independent in the class of complete relations: the examples used to show the independence of the latter in Bouyssou andPirlot (2005a, 2007) were all complete relations. •

Strict concordance-discordance relations

In Bouyssou and Pirlot (2006), we have studied a model of strict (asymmetric) concordance-discordance relation that provides a framework for outranking methods, such as TACTIC [START_REF] Vansnick | On the problems of weights in MCDM (the noncompensatory approach)[END_REF], building an asymmetric relation interpreted as strict preference. We recall here the definition of an asymmetric concordance-discordance relation (A-CDR). As we did for I-CR in Section 6.2, we define the more general irreflexive concordance discordance relations I-CDR, while A-CDR appears as a particular case of it.

Definition 52 (Irreflexive concordance-discordance relation) Let P be an irreflexive binary relation on X = n i=1 X i . We say that P is an irreflexive concordance-discordance relation (or, more briefly, that P is an I-CDR) if there are:

• an asymmetric binary relation P • i on each X i (i = 1, 2, . . . , n),

• an asymmetric binary relation V

• i on each X i (i = 1, 2, . . . , n), with V • i ⊆ P • i ,
• a binary relation £ • between disjoint subsets of N that is monotonic w.r.t. inclusion, i.e., such that (6) holds, such that, for all x, y ∈ X,

x P y ⇔ P • (x, y) £ P • (y, x) and V • (y, x) = ∅,

where P • (x, y) = {i ∈ N :

x i P • i y i } and V • (y, x) = {i ∈ N : y i V • i x i }.
A strict concordance-discordance relation is an asymmetric I-CDR. We also call strict concordance-discordance relations asymmetric concordance-discordance relations (A-CDR).

An example of an A-CDR can be obtained by adding a non-veto condition to the relation defined in Example 44. The result is a version of the outranking relation obtained using the TACTIC method proposed by [START_REF] Vansnick | On the problems of weights in MCDM (the noncompensatory approach)[END_REF].

Example 53 (TACTIC, Vansnick 1986) The binary relation P is a TACTIC outranking relation (with additive threshold) if there are ε, P • i , w i like in Example 44 and, for each i ∈ N , a strict semiorder

V • i such that V • i ⊆ P • i and (V • i , P • i )
forming a nested homogeneous chain of strict semiorders, such that:

x P y ⇔ i∈P • (x,y) w i > j∈P • (y,x) w j + ε and V • (y, x) = ∅ where V • (y, x) = {i ∈ N : y i V • i x i }. Q
Clearly, a TACTIC outranking relation is an A-CDR. We recall the characterization of A-CDR obtained in Bouyssou and Pirlot (2006). It is easy to check that this result also characterizes I-CDR, when the relation is not supposed to be asymmetric.

Theorem 54 (Characterization of I-CDR and A-CDR) A relation P on X is an I-CDR iff it is irreflexive and satisfies RC 1, RC 2, M aj1, and M aj3, where M aj3 is satisfied as soon as the following condition, M aj3 i , is satisfied for all i ∈ N :

(x i , a -i ) P (y i , b -i ) and (w i , a -i ) P (z i , b -i ) and (y i , c -i ) P (x i , d -i ) and (z i , e -i ) P (w i , f -i )                    ⇒    (y i , a -i ) P (x i , b -i ) or (z i , c -i ) P (w i , d -i ), (29) for all x i , y i , z i , w i ∈ X i and all a -i , b -i , c -i , d -i , e -i , f -i ∈ X -i . A relation P is an A-CDR iff
it is an asymmetric I-CDR. In the class of asymmetric relations (and, therefore in the class of irreflexive relations), conditions RC 1, RC 2, M aj1 and M aj3 are independent.

The only difference in the characterization of I-CDR w.r.t. I-CR is the substitution of M aj2 by M aj3, which, obviously, is a weakening of M aj2. Condition M aj3 is obtained from M aj2 exactly in the same way as M 3 is obtained from M 2 (see Remark 18 in Section 4 above).

In Section 6.1, we have established that the codual of an R-CR is an I-CR (and conversely) and that the asymmetric part of an R-CR is an I-CR. The situation is not the same for R-CDR and I-CDR. It is not hard to see that the codual of an I-CDR is an R-CR with bonus as defined below.

Definition 55 (Reflexive concordance relation with bonus R-CRB) Let be a reflexive binary relation on X = n i=1 X i . We say that is a reflexive concordance relation with bonus (or, more briefly, that is an R-CRB) if there are:

• a complete binary relation S i on each X i (i = 1, 2, . . . , n),

• an asymmetric binary relation V i on each X i (i = 1, 2, . . . , n), with V i ⊆ P i ,

• a binary relation ¤ between subsets of N having N for union that is monotonic w.r.t. inclusion, i.e., such that (6) holds, such that, for all x, y ∈ X,

x y ⇔ S(x, y) ¤ S(y, x) or V (x, y) = ∅ (30)

where S(x, y) = {i ∈ N : x i S i y i } and V (x, y) = {i ∈ N :

x i V i y i }.
The correspondence between I-CDR and R-CRB is straightforward.

If £ • , P • i , V • i
is a representation of P as an I-CDR, then a representation, ¤, S i , V i , of its codual P cd as an R-CRB is obtained by defining S i as the codual of P i , ¤ from £ through (22), and taking

V i = V • i .
To illustrate the coduality of I-CDR and R-CRB, consider the relation P defined in Example 53. Its codual P cd is as follows:

x P cd y ⇔ i∈S(x,y)

w i ≥ j∈S(y,x) w j -ε or V • (x, y) = ∅.
The first part of the above condition corresponds the definition of a semiordered weighted majority relation (Example 3) with S i the codual of P • i and S(x, y) = {i ∈ N : x i S i y i }. The second branch of the alternative has an interpretation that is in sharp contrast with the concept of a veto: it says that x can be declared at least as good as y as soon as x is "much better" than y on some attribute (i.e., there is some attribute i on which x i V • i y i ). Clearly, relation P cd is an R-CRB.

Remark 56

Definition 55 introduces a new preference structure that deserves attention in its own right. It is quite easy to derive a characterization of R-CRB using coduality and the characterization of I-CDR. We know from Lemma 48 that imposing RC 1 (resp. RC 2, M aj1) to a relation amounts to imposing RC 1 (resp. RC 2, M 2) to its codual. It is readily seen that imposing M aj3, i.e., (29) (for all i ∈ N ), to a relation R amounts to imposing the following axiom, referred to as M 4, to its codual R cd . We say that R cd satisfies M 4 if, for all i ∈ N , for all x i , y i , z i , w i ∈ X i and all a -i , b -i , c -i , d -i , e -i , f -i ∈ X -i , we have:

(x i , b -i ) R cd (y i , a -i ) and (w i , d -i ) R cd (z i , c -i )    ⇒                    (y i , b -i ) R cd (x i , a -i ) or (z i , b -i ) R cd (w i , a -i ) or (x i , d -i ) R cd (y i , c -i ) or (w i , f -i ) R cd (z i , e -i ). (31)
Note that this axiom is clearly a weakened variant of M 1 that simply adds to it one possible conclusion. Using this new axiom, we directly derive a characterization of an R-CRB from Theorem 54.

Let us denote by c , the "concordance part" of the R-CDR , i.e., c is the relation defined by:

x c y iff S(x, y) ¤ S(y, x).

Clearly, c is an R-CR with representation ¤, S i ; we denote by c its asymmetric part (it is an A-CR) and by ∼ c its symmetric part. An alternative definition of is the following:

x y iff    x c y and V (y, x) = ∅ or x ∼ c y, V (y, x) = ∅ and V (x, y) = ∅. (32)
This means that the asymmetric part of originates either from the asymmetric part of the concordance relation, provided there is no veto, or from the symmetric part of the concordance relation provided that there is no attribute on which y i V i x i and that there is at least one attribute for which x is "much better" than y (i.e., x i V i y i ).

As a conclusion, in the asymmetric part of an R-CDR, V i may play the rôle of a veto (discarding a pair belonging to the asymmetric part of the concordance relation) or, on the contrary, play the rôle of a bonus (transforming an indifference, w.r.t. the concordance relation, into a strict preference).

Hence, the asymmetric part of an R-CDR is a more complex object than an R-CDR. It is not directly based on the application of concordance / nondiscordance principle. This was already observed in Bouyssou and Marchant (2007a,b) for the analysis of the optimistic version of the ELECTRE TRI procedure that make use of the asymmetric part of an R-CDR. Combining the conditions introduced above giving rise to veto effects (29) and bonus effects (31), a characterization of such relations does not seem out of reach. We do not develop this point here.

Discussion

In this paper, we have given several axiomatic characterizations of outranking relations based on the concordance / non-discordance principle. This was done in a traditional conjoint measurement setting, i.e., using a binary relation defined on a Cartesian product as the only primitive. This leads to conditions entirely phrased in terms of that could be subject to empirical tests. Furthermore, the proofs of our results are constructive, which may be useful to devise assessment protocols. Different primitives are used in [START_REF] Pirlot | A common framework for describing some outranking procedures[END_REF] who uses concepts from social choice and, hence, views outranking methods as techniques aggregating information available on each attribute (see also [START_REF] Marchant | An axiomatic characterization of different majority concepts[END_REF]. For a detailed comparison of the conjoint measurement approach followed here and the approach based on social choice concepts, we refer to Bouyssou et al. (2006, Ch. 4-6).

We would like to conclude with the mention of some limitations of the present study and its relation to the literature. We refer to Bouyssou and Pirlot (2005a) for other elements of discussion, including the important issue of the sweeping consequences of imposing nice transitivity properties to outranking relations obtained using the concordance / non-discordance principle.

Limitations and directions for future work

The practitioner of outranking methods will surely have noticed a number of limitations of the present work. We mention here what we consider to be the most important ones.

Our emphasis has been on outranking methods that leads to the construction of "crisp" preference relations. This is a severe limitation since many well known outranking methods, like ELECTRE III [START_REF] Roy | ELECTRE III : un algorithme de classement fondé sur une représentation floue des préférences en présence de critères multiples[END_REF] or the various versions of PROMETHEE [START_REF] Brans | PROMETHEE-GAIA. Une méthodologie d'aide à la décision en présence de critères multiples[END_REF][START_REF] Brans | A preference ranking organisation method. (The PROMETHEE method for multiple criteria decision-making)[END_REF] lead to the construction of valued relations, i.e., relations in which a number is attached to each ordered pair of alternatives reflecting the credibility or intensity of the underlying preference statement. Strictly speaking, this paper does not bring anything to the study of such methods. However, let us mention that it is possible to extend models (M) and (M*) to cover the case of valued binary relations: instead of comparing the value of F to a fixed threshold (0), this value can be seen as defining the valued relation. This calls for further study that will be the subject of a subsequent paper.

With the ELECTRE methods in mind, another limitation of our work is that it does not take "weak preference" (interpreted as an hesitation between indifference and strict preference) into account. This is also a severe limitation since "weak preference" plays an important part in some outranking methods. Nevertheless, as pointed out in [START_REF] Tsoukiàs | From concordance/discordance to the modelling of positive and negative reasons in decision aiding[END_REF], modelling "hesitation" is not an easy task and may necessitate the use of non-classical logics. Hence, it would be accurate to say that our results only deal with "idealized" outranking methods in which "hesitation" plays no rôle. Nevertheless our feeling is that these idealized methods remain close in spirit to the real outranking methods and that our conditions capture some of the central features of the latter.

Another limitation of this work is that our model for concordance remains too general. Indeed, in most methods weights are attached to each attribute and their sum are used to perform the concordance test. Our models do not use weights at all and are simply based on an importance relation between coalition of attributes. We do not consider this limitation as very serious. On the practical side, dispensing with additive weights is indeed feasible, e.g., making use of symbolic inference techniques inspired from the Artificial Intelligence field: this was convincingly demonstrated with the "rough set" approach to MCDA, as presented, e.g., in Greco et al. (2001b[START_REF] Greco | Decision rule approach[END_REF]. On the theoretical side, formulating conditions ensuring that the relation ¤ has an additive representation is not a difficult task. Completing it is unlikely to lead to conditions giving much insight on the underlying methods: since N is finite, these conditions will require a denumerable scheme of conditions that cannot be truncated.

A final important limitation of our work is that it is limited to the so-called "construction phase" of outranking methods. Since the relations obtained as the result of this construction phase do not, in general, possess remarkable properties of transitivity or completeness, using them to devise a recommendation is not an easy task and calls for the application of specific techniques (this is the so-called "exploitation phase"; on such techniques, see Bouyssou et al. 2006;[START_REF] Roy | The outranking approach and the foundations of ELECTRE methods[END_REF][START_REF] Roy | Aide multicritère à la décision : Méthodes et cas[END_REF][START_REF] Vanderpooten | The construction of prescriptions in outranking methods[END_REF]). We have little to say on how an axiomatic analysis that would include both the construction and the exploitation phases of outranking methods could be conducted. This is all the more true that there is no general agreement on what are the "best" techniques to derive a recommendation on the basis of an outranking relation in a given problem formulation. The sorting problem formulation seems the most easy one to deal with: since it only uses the comparison of alternatives with carefully selected profiles, so that intransitivity and incompleteness are not central issues here. Results of this kind have been obtained in Bouyssou and Marchant (2007a,b). The analysis of both the construction and exploitation phases of outranking methods clearly calls for more research (first results were obtained in Bouyssou et al. 2006, Ch. 5, in a social choice framework).

Relation to the literature

this new condition. Indeed, the original noncompensation condition is (up to the point made earlier) satisfied for the concordance part of the method. The effect of discordance is to transform relations into ∼ ones. Hence, TACTIC satisfies condition (35).

There are several problems with this approach (that motivated one of the author of the present paper to abandon it and to develop the material presented here). We already mentioned that it is not flexible enough to cover all concordance relations of interest. We also noted that it is not well suited to introduce a linear arrangement of elements on each X i . This last problem becomes even more important when discordance comes into play and there is a need to introduce links between i and V i . The route followed in [START_REF] Bouyssou | Noncompensatory and generalized noncompensatory preference structures[END_REF] to tackle this problem is correct but somewhat ad hoc.

A final and major limitation of this approach is that, contrary to the approach taken here, it does not generalize outside the realm of asymmetric relations. As first noted in [START_REF] Bouyssou | Some remarks on the notion of compensation in MCDM[END_REF][START_REF] Bouyssou | On some properties of outranking relations based on a concordance-discordance principle[END_REF] it is simple to reformulate the noncompensation condition so that it becomes adapted to the treatment of "at least as good as" relations. This leads to a condition of the type:

(x, y) = (z, w) (y, x) = (w, z) ⇒ [x y ⇔ z w] , (36)
where (x, y) = {i ∈ N : x i i y i } and i is the marginal binary relation on X i induced by , i.e., the relation such that, for all x i , y i ∈ X i ,

x i i y i ⇔ [(x i , a -i ) (y i , a -i ), for all a -i ∈ X -i ] .

This approach was later developed in [START_REF] Fargier | Modélisation des préférences par une règle de concordance généralisée[END_REF] and [START_REF] Dubois | Towards a qualitative multicriteria decision theory[END_REF][START_REF] Dubois | A characterization of generalized concordance rules in multicriteria decision-making[END_REF]. As was the case with the original noncompensation condition, (36) does not allow to deal with the whole variety of concordance relations (see Bouyssou and Pirlot 2005a, Examples 30 and 31), is very specific to this type of relations, and is not very well suited to introduce a linear arrangement of the elements on each X i . Even worse, the route followed by [START_REF] Bouyssou | Noncompensatory and generalized noncompensatory preference structures[END_REF] in order to cope with veto effects does not work here. Mimicking the above approach, we could consider a condition saying that (x, y) = (z, w) (y, x) = (w, z) ⇒ x y ⇒ w z ,

but even such a weak condition fails with most outranking relations. Indeed, as discussed in Section 6, an indifference situation between two alternatives obtained on the sole basis of the concordance test may be broken in an unpredictable way by veto effects. This leads to possible violations of condition (37). It is easy to build examples, e.g., using ELECTRE I, in which one has (x, y) = (z, w), (y, x) = (w, z), x ∼ y and z ∼ w when only the concordance part of the method is used. Introducing veto effects, one can easily obtain x y and w z, violating (37).

The approach using variants of noncompensation is often seen to have some advantages w.r.t. the approach used here. First it has been shown (see [START_REF] Bouyssou | On some properties of outranking relations based on a concordance-discordance principle[END_REF][START_REF] Dubois | A characterization of generalized concordance rules in multicriteria decision-making[END_REF] to be particularly well suited to transfer "Arrow-like" results (i.e., results showing that requiring to have "nice properties" induces a very undesirable repartition of "importance" among the various attributes) to the context of MCDA. Nevertheless, we have shown in Bouyssou and Pirlot (2002a) that a similar analysis can also be performed in our more general framework, which leads to even more powerful results. Noncompensation-like conditions are also often seen as being "simpler" and "more natural" than the type of conditions used here. We disagree. Besides the fact that "simplicity" is a very subjective criterion, we would like to point out that we have strived to present conditions that are entirely phrased using our primitives, i.e., the relation on X. If one tries to reformulate the noncompensation condition with such a constraint, the result does not appear to be much simpler than our conditions. Greco et al. (2001a) Greco et al. (2001a) give results that are closely related to the ones presented here. Motivated by the ELECTRE I method, their aim was to characterize the particular class of R-CDR in which the relation ¤ is such that, for all A, B ⊆ N such that A ∪ B = N ,

The approach of

A ¤ B ⇒ A ¤ N. (38)
It is easy to see that this additional condition is satisfied in ELECTRE I (see Example 4). As we did above, the approach of Greco et al. (2001a) is based on conditions limiting the number of distinct equivalence classes of * i (see [START_REF] Bouyssou | A general model of preference aggregation[END_REF]).

When discordance is not taken into account, the central condition used by Greco et al. (2001a) is the following. We say that is super-coarse on attribute i ∈ N if, for all x i , y i , z i , w i , r i , s i ∈ X i and all a -i , b -i , c -i , d -i ∈ X -i , (x i , a -i ) (y i , b -i ) and (z i , c -i ) (w i , d -i )

   ⇒    (x i , c -i ) (y i , d -i ) or (r i , a -i ) (s i , b -i ). ( 39
)
This condition is clear strengthening of RC 1. It is not difficult to see that a is super-coarse on attribute i ∈ N if and only if * i is complete and has at most two distinct equivalence classes.

It is important to notice that, on its own, super-coarseness does not imply independence (in our framework independence is ensured via the use of RC 2). Therefore nothing prevents (x i , x i ) and (y i , y i ) from belonging to two distinct equivalence classes of * i . In order to characterize R-CR satisfying (38), Greco et al. (2001a) use super-coarseness as well as an additional condition saying that, for all i ∈ N , all x i , y i , w i ∈ X i and all a -i , b -i ∈ X -i , (x i , a -i ) (y i , b -i ) ⇒ (w i , a -i ) (w i , b -i ).

(40)

This is a rather strong condition implying at the same time independence and the fact that the null preference differences (w i , w i ) always belong to the first equivalence class of * i . Its intuitive content appears to be limited. As discussed in Bouyssou and Pirlot (2005a, Sect. 5.2), the result of Greco et al. (2001a) on concordance relations deals with a particular class of R-CR, in contrast with our own results. Furthermore, as this analysis does not explicitly uses conditions RC 1 and RC 2, it not conducted within the broader framework of model (M), which may be viewed as a drawback in view of comparing concordance relations with other types of relations. Finally, condition (40) is not very easy to interpret. Greco et al. (2001a) have noted that adding conditions AC 1, AC 2 and AC 3 implies that the resulting relations S i must be semiorders. Nevertheless, they have not studied the independence of these conditions with respect to conditions (39) and (40). As shown in Bouyssou and Pirlot (2005a, Lemma 27), conditions AC 1 i and AC 2 i turn out to be equivalent for R-CR. Independence issues were indeed the most delicate ones to tackle in Bouyssou and Pirlot (2005a) and [START_REF] Bouyssou | Further results on concordance relations[END_REF].

Although we already mentioned in [START_REF] Bouyssou | A general model of preference aggregation[END_REF] that model (M) offers an adequate framework to tackle R-CDR, it took us some time to devise adequate conditions that would characterize R-CDR within this framework. Greco et al. (2001a) were the first to come up with such conditions; we already mentioned that our condition M 3 is inspired from their work. The main condition used in Greco et al. (2001a) to characterize R-CDR satisfying (38) is the following. We say that is super-coarse with veto on attribute i ∈ N if, for all x i , y i , z i , w i , r i , s i ∈ X i and all a -i , b -i , c -i , d -i ∈ X -i , (x i , a -i ) (y i , b -i ) and (z i , c -i ) (w i , d -i ) and (r i , e -i ) (s i , f -i )

           ⇒    (x i , c -i ) (y i , d -i ) or (r i , a -i ) (s i , b -i ). ( 41
)
This condition is a clear weakening of (39) that have inspired our own weakening of M 2 to obtain M 3. The main result in Greco et al. (2001a) is that R-CDR satisfying (38) are characterized by the conjunction of conditions ( 40) and (41). We do not repeat here the comments made above: this result uses condition (40) and is not conducted within a broader framework, like the one provided by model (M). Nevertheless, it was the first approach that convincingly took discordance into account in a conjoint measurement setting.

  a), (z, b) (x, a), (z, b) (y, a), (x, b) (w, a), due to the fact that Not[∅ ¤ {1, 2}], and • (z, a) (y, a), (z, a) (y, b), (z, b) (y, a), (z, b) (y, b), due to the fact that y V 1 z.

  a), (y, b) (z, a), (w, b) (z, a), (w, b) (x, a), due to the fact that Not[∅ ¤ {1, 2}], and • (y, a) (z, a), (y, b) (z, b), (y, b) (z, a), (y, a) (z, b), due to the fact that z V 1 y.

  Assume that A ¤ B, C ⊇ A and D ⊆ B. If A ¤ B, using the monotonicity of ¤, we have C ¤ D, hence C ¤ D. If Not[B ¤ A], then Not[D ¤ C] (by monotonicity of ¤). We have either C ¤ D or Not[D ¤ C], which, in both cases, yields C ¤ D. The R-CR relation having this representation is clearly the completion of .

  4 Concordance-discordance relations

ELECTRE I builds a reflexive concordance relation that is subsequently "censored" by imposing on it the non-discordance condition. This is illustrated below. Example 4 (ELECTRE I, Roy 1968) The binary relation is an ELECTRE I preference relation if there are a real number s ∈ [1/2, 1] and, for all

  Consider Example 20 in[START_REF] Bouyssou | Further results on concordance relations[END_REF] (see also Example 35 inBouyssou and Pirlot (2005a)). It is shown in[START_REF] Bouyssou | Further results on concordance relations[END_REF]) that Example 20 satisfies RC 1, RC 2, M 1, M 2, AC 1, AC 3 j , j = 1, Not[AC 3 1 ].This example satisfies M 3 since we know that M 2 implies M 3. Since in presence of RC 1, RC 2, M 1, M 2, conditions AC 1 and AC 2 are equivalent (Lemma 27Bouyssou and Pirlot 2005a), also satisfies AC 2 (for instance,

	+ 1 and -1 are not incompatible.	Q
	Example 37 (Not[AC 3 1 ])

-1 is the weak order a

  (see also Example 33 inBouyssou and Pirlot (2005a)) satisfies the required properties. It is shown in[START_REF] Bouyssou | Further results on concordance relations[END_REF] that this example satisfies RC 1, RC 2, M 1 j , j = 1, Not[M 1 1 ], M 2, AC 1 and AC 3. Since M 2 entails M 3, it satisfies M 3. One easily checks that it satisfies AC 2. Q Example 40 (Not[RC 2 1 ])Example 25 in[START_REF] Bouyssou | Further results on concordance relations[END_REF] is appropriate, taking into account that M 2 implies M 3 and that this example can be shown to satisfy AC 2. Q

	Example 41 (Not[RC 1 1

This paper is not the first attempt to analyze the concordance / non-discordance principle in a conjoint measurement perspective. In what follows, we try to position our contribution w.r.t. this earlier literature.

Proposition 57 (Characterization of R-CRB) A relation on X is a reflexive concordance relation with bonus (R-CRB) iff it is reflexive and satisfies RC 1, RC 2, M 2, and M 4.

We leave to the reader the study of the particular case of R-CRB with attribute transitivity.

•

The asymmetric part of an R-CDR

The asymmetric part of an R-CDR is not always an I-CDR, as shown by the following example.

Example 58

Let N = {1, 2, 3, 4} and

where S(x, y) = {i ∈ N : x i S i y i } and V (y, x) = {i ∈ N : y i V i x i } with:

(where P i denotes the asymmetric part of the complete relation S i ).

By construction, is an R-CDR. Denoting by the asymmetric part of , it is easy to check that we have:

The first line implies that, w.r.t. , the difference (x 1 , z 1 ) is strictly larger than the difference (x 1 , y 1 ). The second line shows that the difference (x 1 , y 1 ) is strictly larger than its opposite (y 1 , x 1 ). It is easy to see that this is impossible in an I-CDR (see Bouyssou and Pirlot 2006, Lemma 9, for details). Q Let be an R-CDR with its representation ¤, S i , V i . Using the definition of an R-CDR, we can say that its asymmetric part, denoted by , is such that:

The approach using noncompensation

The work of [START_REF] Bouyssou | Noncompensatory and generalized noncompensatory preference structures[END_REF] on TACTIC is probably the first attempt to tackle the problem studied here. This paper uses a classical conjoint measurement setting to analyze A-CR and A-CDR. The central condition used in this paper to characterize A-CR is a condition called "noncompensation" that was introduced in [START_REF] Fishburn | Axioms for lexicographic preferences[END_REF][START_REF] Fishburn | Noncompensatory preferences[END_REF][START_REF] Fishburn | A survey of multiattribute/multicriteria evaluation theories[END_REF]. It says that, for all x, y, z, w ∈ X,

where (x, y) = {i ∈ N : x i i y i } and i is the marginal binary relation on X i induced by , i.e., the relation such that, for all x i , y i ∈ X i ,

When coupled with a suitable monotonicity condition, or when strengthened as

the noncompensation condition seems to offer an interesting basis to analyze the concordance principle. However, as discussed at length in Bouyssou and Pirlot (2005a, Sect. 5.2) this approach to concordance does not allow to deal with the whole variety of concordance relations. For instance, it prevents one from using a threshold ε that would be greater than the weight of one attribute in the concordance part of TACTIC (see Example 53). Furthermore, this approach is not well suited to characterize a relation in which the relations i would have nice transitivity properties. Finally, the noncompensation condition is very specific to "ordinal" methods. Using it does not allow to characterize concordance relation within a broader framework that also encompasses other types of relations. [START_REF] Bouyssou | Noncompensatory and generalized noncompensatory preference structures[END_REF] have approached the introduction of discordance via the following weakening of the noncompensation condition saying that, for all x, y, z, w ∈ X, (x, y) = (z, w) (y, x) = (w, z) ⇒ x y ⇒ w z .

When (x, y) = (z, w) and (y, x) = (w, z) and x y, this new condition allows to have either z w or z ∼ w, where ∼ is seen here as the symmetric complement of . It is not difficult to see that TACTIC satisfies