Denis Bouyssou
email: bouyssou@lamsade.dauphine.fr

Marc Pirlot
email: marc.pirlot@umons.ac.be.

A consolidated approach to the axiomatization of outranking relations: A survey and new results

Keywords: Multiple criteria decision analysis, Concordance, Discordance, Outranking methods, Conjoint measurement, Nontransitive preferences, Veto, Bonus, Co-duality

Outranking relations such as produced by the Electre I or II or the Tactic methods are based on a concordance and non-discordance principle that leads to declaring that an alternative is "superior" to another, if the coalition of attributes supporting this proposition is "sufficiently important" (concordance condition) and if there is no attribute that "strongly rejects" it (non-discordance condition). Such a way of comparing alternatives is rather natural and does not require a detailed analysis of tradeoffs between the various attributes. However, it is well known that it may produce binary relations that do not possess any remarkable property of transitivity or completeness. The axiomatic foundations of outranking relations have recently received attention. Within a conjoint measurement framework, characterizations of reflexive concordance-discordance relations have been obtained. These relations encompass those generated by the Electre I and II methods, which are non-strict (reflexive) relations. A different characterization has been provided for strict (asymmetric) preference relations such as produced by Tactic. In this paper we briefly review the various kinds of axiomatizations of outranking relations proposed so far in the literature. Then we analyze the relationships between reflexive and asymmetric outranking relations in a conjoint measurement framework, consolidating our previous work. Co-duality plays an essential rôle in our analysis. It allows us to understand the correspondence between the previous characterizations. Making a step further, we provide a common axiomatic characterization for both types of relations. Applying the co-duality operator to concordance-discordance relations also yields a new and interesting type of preference relation that we call concordance relation with bonus. The axiomatic characterization of such relations results directly from co-duality arguments.

Introduction

In multiple criteria decision processes it often occurs that the information needed to build a value function model with the aim of ranking the alternatives is difficult to elicit. In these cases, the analyst has the choice to turn to methods having an "ordinal flavor" in which the alternatives are compared in a pairwise manner. Such methods mainly take advantage of the order on the criteria scales and lead to one or several binary relations, known as outranking relations.

Most outranking methods, including the well known Electre methods (Roy, 1968, Roy andBertier, 1973), 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 the following two conditions are fulfilled:

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

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

Stating that an alternative is "superior" to another may have two different meanings. In Electre methods, "superior" means "not worse", i.e., "at least as good as". Such methods aim at building a reflexive preference relation that is interpreted as an "at least as good as" relation. In general, such relations may lack nice transitivity or completeness properties (on these issues, see [START_REF] Bouyssou | On some properties of outranking relations based on a concordancediscordance principle[END_REF][START_REF] Bouyssou | Outranking relations: Do they have special properties?[END_REF].

In other outranking methods, like the Tactic method [START_REF] Bouyssou | Noncompensatory and generalized noncompensatory preference structures[END_REF], "superior" means "strictly better than". Such methods build an asymmetric relation that is interpreted as strict preference. As in the reflexive case, the obtained relations are not necessarily transitive and they may have cycles.

The outranking relation produced by certain outranking methods (such as Electre III, Roy, 1978, or Promethee, Brans and[START_REF] Brans | A preference ranking organisation method. (The PROMETHEE method for multiple criteria decision-making)[END_REF] are valued relations. In this work we restrict ourselves to crisp outranking relations.

Although they have proved their usefulness in numerous applications (see, e.g., Roy and Bouyssou, 1993, chapters 8 to 10 and a commented bibliography of case studies, or, more recently, Figueira et al., 2005, Section 5 andFigueira et al., 2013, Section 4.4.6), outranking methods are not as popular as the methods based on a score or a value function. There are two main reasons for that. The first is that outranking methods cannot guarantee that the pairwise comparison of alternatives will result in a ranking. Indeed, outranking relations based on the concordance & non-discordance principle above may be both non-transitive and incomplete. This is an unamendable limitation which is related to Arrow's impossibility theorem 1 (see [START_REF] Bouyssou | On some properties of outranking relations based on a concordancediscordance principle[END_REF]. Therefore, outranking methods generally involve a phase of exploitation of the outranking relation, which produces a ranking. The second reason is related to the absence of axiomatic foundations for these methods, at the time they were introduced. The goal of this paper is to review the efforts made in order to axiomatize concordance & non-discordance relations and to present our own recent contributions in a unified framework, which also leads to new results.

An overview of axiomatic work on outranking relations

The first contribution to the characterization of outranking relations is in the spirit of [START_REF] Fishburn | Noncompensatory preferences[END_REF] study of noncompensatory preferences. In this model of preferences, the comparison of two alternatives only depends on the way they compare w.r.t. the various criteria and is independent of the other alternatives. [START_REF] Bouyssou | Noncompensatory and generalized noncompensatory preference structures[END_REF] and [START_REF] Bouyssou | Some remarks on the notion of compensation in MCDM[END_REF] elaborate on this idea to obtain a characterization of a subclass of outranking relations. [START_REF] Fargier | Modélisation des préférences par une règle de concordance généralisée[END_REF] (see also [START_REF] Dubois | Towards a qualitative multicriteria decision theory[END_REF][START_REF] Dubois | On the limitation of ordinal approaches to decision making[END_REF][START_REF] Kaufmann | A characterization of generalized concordance rules in multicriteria decision-making[END_REF] followed a similar path proposing a characterization of concordance relations, which appears to be limited to a subclass of concordance relations for which all attributes are essential (for a discussion including a simple example of a concordance relation w.r.t. which all attributes are inessential, see BP05b, Section 5.2)1 .

Another approach, which the present work aims at synthesizing, describes concordance & non-discordance relations in a conjoint measurement framework. The latter was most fruitful for analyzing the dominant paradigm of the additive function model [START_REF] Krantz | Additive and polynomial representations[END_REF]. This line of research starts with two papers (Bouyssou andPirlot, 1999, Bouyssou et al., 1997) which characterize outranking relations as relations on a product set of attributes scales that distinguish a small number of preference differences on each attribute. More precisely, on a given dimension, an alternative can be at least as good, worse or unacceptably worse as compared to another. This is essentially in line with the idea of an ordinal aggregation method, for which the distinction between large and small differences is meaningless. The axioms, except for the condition on the number of distinguished classes of preference differences, are expressed as cancelation conditions, in the style of conjoint measurement theory.

BP02b establish a characterization of strict (i.e., irreflexive) concordance relations in which axioms are formulated as cancelation conditions (i.e., without specifying explicitly the number of preference differences classes). In a communication at the FUR X Conference, [START_REF] Greco | Axiomatic basis of noncompensatory preferences[END_REF] present cancelation conditions characterizing (non-strict) concordance relations. As pointed out in BP05b, section 5.1, these conditions are restrictive since they characterize a subclass of all outranking relations corresponding to those produced by the Electre I aggregation rule. Furthermore, their axioms do not enter in the general axiomatic framework outlined in [START_REF] Bouyssou | A general model of preference aggregation[END_REF] and [START_REF] Bouyssou | Conjoint measurement without additivity and transitivity[END_REF], which impedes a clear understanding of how outranking relations distinguish from those obtained by other aggregation rules.

Axiomatization can indeed be a manner of analyzing crisp binary relations defined on a product set and organizing them. Three papers (BP02a, BP02b, BP04b) set general frameworks for the analysis of relations on a product set interpreted as preference relations (in a broad sense, since we do not impose them to be transitive or complete). We define two general families of models based on traces induced by the preference on each attribute scale. The first family we analyze relies on traces on differences of preference (BP02a) and the second, on traces on levels (BP04a). The third paper in the series (BP04b) considers models combining both types of traces. These families encompass a wide variety of preference models that have been discussed in literature.

In BP05b, BP07 and BP09a, we successively describe reflexive concordance relations and concordance & non-discordance relations within the framework studied in BP02a and BP04b by providing additional axioms that are independent of those defining the framework. In the continuation of BP02c and within the same framework, we also deal with strict (irreflexive) concordance & non-discordance relations in BP05c and BP06.

Note that a different approach can be followed, which consists in characterizing the procedures used to produce outranking relations instead of the relations themselves. For studies following this path, the interested reader is referred to [START_REF] Bouyssou | A general model of preference aggregation[END_REF] and Marchant (2003Marchant ( , 2007) ) (see also Bouyssou et al., 2006, chapter 5).

Goal of the present paper

The purpose of this paper is to consolidate our previous work by presenting both strict and non strict concordance & non-discordance relations in a unified framework.

Common sense and usage suggest a simple relationship between strict and nonstrict preference relations: alternative x is at least as good as alternative y if y is not better than x and vice versa. In terms of binary relations, this amounts saying that the "at least as good as" and "better than" relations are the co-dual of each other, i.e., one is the complement of the inverse of the other. This intuition should be questioned. Indeed, starting from an asymmetric preference relation and taking its co-dual leads to a complete preference, while, usually, non-strict outranking relations are incomplete preference relations. Conversely, the co-dual of an incomplete relation, such as a non-strict outranking relation, is not asymmetric, hence it hardly can be interpreted as a strict preference. Should we consider the asymmetric part of the co-dual? As we shall see, such a relation is not a strict outranking relation as they can be defined in the spirit of the Tactic method.

Although co-duality does not yield a straightforward correspondence between strict and non-strict outranking relations, it is an important tool to study it and also obtain new axiomatic characterizations of strict and non-strict outranking relations. The rest of the paper is organized as follows. After notation is presented in the next section, we discuss this question in an informal way in Section 3, using definitions of strict and non-strict outranking relations that respectively encompass the relations yielded by the Tactic and Electre methods. In Section 4, we recall what is needed from our previous axiomatic work and analyze in a formal way the relationship between strict and non-strict outranking relations mainly using coduality. This analysis leads us to the definition and characterization of a new model for preference relations (strict and non-strict concordance relations with "bonus"). Finally, we draw some conclusions and present perspectives for future research.

Preliminary remarks

Before entering into the core of the subject, we make the following points in order to avoid ambiguities.

1. The aim of our axiomatic approach is to understand what distinguishes the different models of preferences and what their relationships are. We do not intend to justify the use of certain models by means of normative arguments. The present type of axiomatic analysis could be described as informative or structural.

2. While we study objects, namely concordance & non-discordance relations, that are involved in the Electre or Tactic methods, we do not aim at characterizing the final output of such methods. The latter methods' characteristic is that they proceed in two steps. The first step yields a crisp binary relation which results from the comparison of all alternatives in pairs, independently of irrelevant ones. The second step exploits this, often intransitive and incomplete, relation in order to produce the expected sort of output, i.e., a complete ranking or a choice set. The result of the first step is called an outranking relation and we interpret it all along as a preference relation.

The question of the transitivity of preferences is a controversial one, both as a rationality requirement and as experimental evidence [START_REF] Fishburn | Intransitive indifference in preference theory: A survey[END_REF][START_REF] Iverson | Statistical issues in measurement[END_REF], May, 1954, Tversky, 1969, Van Acker, 1990). In particular, it is possible to design experiments in which the decision maker is asked to make binary choices, without any mechanism forcing the transitivity or the completeness of the resulting relation. It would be interesting to test whether the resulting relations can be interpreted as a concordance & nondiscordance relation. Regarding the incompleteness issue, recent experiments [START_REF] Deparis | When conflict induces the expression of incomplete preferences[END_REF] show that preferences may be incomplete when the decision maker is granted the possibility not to choose. Our standpoint, in this work, is that concordance & non-discordance relations could actually be observed in such situations.

3. Our axioms are expressed as cancelation conditions, in the style of conjoint measurement theory. They are the usual way of formulating properties such as the classical preference independence condition (see, e.g., Krantz et al., 1971, Ch. 6). The intuition behind such axioms is best understood in terms of traces (see BP05a, for a detailed analysis of traces), which are marginal relations induced by the preference on the criteria scales. Therefore, we generally interpret our axioms by proving equivalent properties of some traces (see, e.g., Lemma 22).

Notation and definitions

In this section we set the notation and recall some elementary definitions that will be used throughout the paper.

A preference relation on a set X is, in general, denoted by R. A binary relation

R on X is said to be reflexive if a R a, for all a ∈ X. It is complete if a R b or b R a, for all a, b ∈ X. Relation R is asymmetric if a R b ⇒ Not[b R a], for all a, b ∈ X. It is transitive if (a R b and b R c) ⇒ a R c, for all a, b, c ∈ X. It is Ferrers if (a R b and c R d) ⇒ (a R d or c R b), for all a, b, c, d ∈ X. It is semi-transitive if (a R b and b R c) ⇒ (a R d or d R c), for all a, b, c, d ∈ X.
A weak order is a complete transitive relation. A semiorder is a reflexive Ferrers and semi-transitive relation. A pair of semiorders (R 1 , R 2 ) on X form a homogeneous chain of semiorders [START_REF] Doignon | Biorder families, valued relations and preference modelling[END_REF] if R 1 ⊆ R 2 and there is a weak order T on X such that, for i = 1, 2, we have

x T y ⇒ for all z ∈ X, [y R i z ⇒ x R i z] and [z R i x ⇒ z R i y].
(1)

When a pair of alternatives (a, b) belongs to a relation R, we write indifferently (a, b) ∈ R or a R b. Starting from a relation R, we can derive several other relations by using appropriate operators. For all a, b ∈ X, we define:

• the dual (or inverse or reciprocal) R d : a R d b if b R a, • the complement R c : a R c b if Not[a R b], • the co-dual R cd : a R cd b if Not[b R a], • the asymmetric part R α : a R α b if a R b and Not[b R a], • the symmetric part R σ : a R σ b if a R b and b R a, • the symmetric complement R ρ : a R ρ b if Not[a R b] and Not[b R a].
We recall a few straightforward properties of the co-dual operator, for they will be used in the sequel. The co-dual of a complete relation is its asymmetric part. The co-dual of an asymmetric relation is complete. The co-dual operator is an involution between the set of complete relations and the set of asymmetric ones. It also establishes an involution between reflexive and irreflexive relations (see Monjardet (1978) for proofs and many more results).

The set of alternatives will be denoted by X. As is usual in conjoint measurement this set will be identified with the Cartesian product n i=1 X i of n sets X i . The latter are interpreted as the range of values of n attributes (n ≥ 2) that completely describe the alternatives in the decision problem at hand. These sets X i are not assumed to be sets of numbers, not even to be ordered sets. The set {1, 2, . . . , n} will be denoted by N . We use X -i to denote the Cartesian product j∈N,j =i X j . Assuming that x is an element of X, x -i is the element of X -i obtained by removing the ith coordinate of vector x, which describes x on attribute i. Assuming that a belongs to X and x i ∈ X i , (x i , a -i ) is the element of X which has the same description as a on all attributes but one: the description of (x i , a -i ) on the ith attribute is x i .

Variants of outranking relations

We start with briefly recalling the definition of a reflexive outranking relation as used in the Electre I method and show that such relations fit in with a slightly more general and abstract definition. Such relations are interpreted as non-strict preferences. We do the same with the asymmetric outranking relation of the Tactic method. Such relations are interpreted as strict preferences. On the basis of these general definitions, we investigate the relationship between reflexive and asymmetric outranking relations, mainly using co-duality.

In order to avoid unnecessary minor complications, we restrict our attention to relations R on X = n i=1 X i for which each attribute is influential. This requirement is a sort of non-triviality condition for attributes. We say that attribute

i ∈ N is influential (for R ) 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 ) R (y i , y -i ) and Not[(z i , x -i ) R (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 .

Electre I

We describe how a reflexive outranking relation, interpreted as a non-strict preference, is built according to the Electre I method2 . Using a real-valued function u i defined on X i , and a pair of non-negative thresholds pt i and vt i , with pt i ≤ vt i , we define the semiorders S i and U i as follows3 : for all x i , y i ∈ X i ,

x i S i y i ⇔ u i (x i ) ≥ u i (y i ) -pt i (2) x i U i y i ⇔ u i (x i ) ≥ u i (y i ) -vt i .
(3)

The pair of relations (S i , U i ) on X i form a homogeneous nested chain of semiorders as defined in Section 2 (with the underlying weak order T i such that

x i T i y i ⇔ u i (x i ) ≥ u i (y i ))
. Relation S i interprets as the "at least as good" relation on attribute i. The relation P i , the asymmetric part of S i , is interpreted as a "better than" relation. pt i is the preference threshold on attribute i. We read "x i U i y i " as "level x i is not unacceptably bad with respect to level y i ". The relation U i is a non-veto relation on attribute i. In contrast, the co-dual of U i is the veto relation V i . It is defined as follows: for all x i , y i ∈ X i ,

y i V i x i ⇔ Not[x i U i y i ] ⇔ u i (x i ) < u i (y i ) -vt i . ( 4
)
Hence y i V i x i means that y i is far better than x i .

In Electre I, the outranking relation R is determined using positive weights w i attached to each attribute and a threshold s with (1/2 ≤ s ≤ 1), such that, for all x, y ∈ X,

x R y ⇔ i∈S(x,y) w i j∈N w j ≥ s and V (y, x) = ∅, (5)
where S(x, y) = {i ∈ N : x i S i y i }, the set of attributes on which x is at least as good as y, and V (y, x) = {i ∈ N : y i V i x i }, the set of attributes on which x is unacceptably bad as compared to y.

Outranking relations such as R are reflexive, need not be complete and do not in general enjoy nice transitivity properties [START_REF] Bouyssou | Outranking relations: Do they have special properties?[END_REF]. As a consequence, deriving a recommendation to the decision maker on the basis of such relations is not straightforward. In order to do that, the analyst may use one of the so-called exploitation procedures (see Roy andBouyssou, 1993, Ch. 6, or Bouyssou et al., 2006, Ch. 7).

Remark 1

Note that we do not consider valued outranking relations such as those obtained by the Electre III (see Roy, 1978, Roy andBouyssou, 1993, pp. 284-289) and the Promethee [START_REF] Brans | A preference ranking organisation method. (The PROMETHEE method for multiple criteria decision-making)[END_REF] methods. This is due to the fact that the tools currently developed in the framework of conjoint measurement theory only deal with crisp relations. In contrast, our analysis does encompass the crisp outranking relations produced by the Electre II method. We do not develop this point further for the sake of conciseness.

•

Outranking relations

A general definition of a reflexive outranking relation was given in BP09a, where such a relation is referred to as a reflexive concordance-discordance relation (R-CDR). The same paper established a characterization of such relations by a system of independent axioms. Since it turns out that reflexivity plays no rôle in the analysis, we restate this definition below, dropping the assumption that the relation is reflexive. In the sequel, the expression outranking relation will be used as exact synonymous of concordance-discordance relation (CDR).

Definition 2 (Concordance-discordance relation (CDR))

A binary relation R on X = n i=1 X i is a concordance-discordance relation (CDR) if there are:

1. 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 ,
3. 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 with A ∪ B = N and

C ∪ D = N , [A ¤ B, C ⊇ A, B ⊇ D] ⇒ C ¤ D, (6) such that, for all x, y ∈ X, x R y ⇔ [S(x, y) ¤ S(y, x) and V (y, x) = ∅] , ( 7
)
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 type I representation of R as a CDR.

A concordance relation (CR) is a CDR in which the V i relations are all empty 4 .

. As explained in BP09a, the type I representation ¤, S i , V i of a CDR may not be unique. This is true even if all attributes are supposed to be influential. When we speak below of a representation of type I ¤, S i , V i of a CDR, we mean one possible representation of type I of the CDR. As detailed in BP05b and BP07 the situation is different with CR. When all attributes are influential, they have a unique representation of type I. Similar remarks will hold for the representations of type II introduced below.

In the above definition, for each attribute i, S i is interpreted as a non-strict preference relation on X i . The asymmetric part P i of S i is the strict preference on X i and V i is the veto relation. Relation ¤ is used in pairwise comparisons of alternatives, it compares coalitions of attributes in terms of their importance: if A and B denote subsets of attributes, A ¤ B reads "the coalition of attributes A is at least as important as the coalition B". In the sequel, we shall use the notation £ (resp. ) to denote the asymmetric (resp. symmetric) part of ¤. Consequently, A £ B (resp. A B) reads "the coalition of attributes A is strictly more important (resp. equally important as) coalition B).

It is easy to see that the outranking relation of Electre I satisfies the above definition. In particular5 , the relation ¤ is defined by:

A ¤ B if i∈A w i j∈N w j ≥ s.
Rule (5) implies that the relation built in the Electre I procedure is reflexive.

Remark 3 (Outranking relations with attribute transitivity)

Due to (2) and (3), relations S i and V i in Electre I have additional properties, namely S i is a semiorder, V i is the asymmetric part of the semiorder U i and S i and U i form a homogeneous chain of two semiorders. Concordance discordance relations with these additional properties have been defined and characterized in BP09a under the name reflexive concordance-discordance relations with attribute transitivity (R-CDR-AT). When required, the suffix "-AT" will be added to acronyms characterizing outranking relations, meaning that the corresponding relations also have the attribute transitivity property. Note that the concordance relation C(R) associated with a concordance-discordance relation in the sense of Definition 2 is itself a particular case of this definition, in which the veto relation V i is assumed to be empty. Such relations were studied and characterized in BP05b and BP076 .

•

Tactic

Another type of outranking relation has been introduced by Vansnick (1986). His Tactic method yields an asymmetric outranking relation interpreted as a strict preference. We briefly recall its definition. Let P i be the asymmetric part of the semiorder S i defined by (2) and let V i be the asymmetric part of relation U i defined by (3). Since U i is complete, V i is also the co-dual of U i . An outranking relation R of the Tactic type is defined as follows:

x R y ⇔ i∈P (x,y)

w i > ρ j∈P (y,x) w j + ε and V (y, x) = ∅, (8)
where w i is a weight assigned to attribute i, ρ is a multiplicative threshold with ρ ≥ 1, ε is a nonnegative additive threshold, P (y, x) = {i ∈ N :

x i P i y i } and V (y, x) = {i ∈ N : y i V i x i }.
Such an outranking relation is clearly asymmetric by construction, hence irreflexive.

As with Electre I, Tactic inspires a general definition of outranking relations that we discuss in the next section.

An alternative definition of outranking relations

The alternative definition of a concordance-discordance relation that we give below is a variant of the one originally proposed in BP06 and BP12, which was restricted to asymmetric preference relations. We drop this restriction and, in Lemma 6, we show that the unrestricted version of the definition is equivalent to Definition 2.

Definition 5

A binary relation R on X = n i=1 X i is a concordance-discordance relation 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., for all A, B, C, D ⊆ N with A ∩ B = ∅ and C ∩ D = ∅, [A ¤ • B, C ⊇ A, B ⊇ D] ⇒ C ¤ • D, ( 9
)
such that, for all x, y ∈ X,

x R y ⇔ [P • (x, y) ¤ • P • (y, x) and V • (y, x) = ∅], (10)
where

P • (x, y) = {i ∈ N : x i P • i y i } and V • (y, x) = {i ∈ N : y i V • i x i }. We say that ¤ • , P • i , V • i is a type II representation of R .
It is readily checked that the outranking relation produced by Tactic satisfies this definition. In Tactic the relation ¤ • is asymmetric.

Lemma 6 (Equivalence of the definitions of CDR) Definitions 2 and 5 are equivalent.

Proof

Assume that R satisfies Definition 2 and that ¤, S i , V i is a type I representation of R. We construct a representation ¤ • , P • i , V • i of type II satisfying (10) letting:

P • i = P i (the asymmetric part of S i ), ∀i ∈ N V • i = V i , ∀i ∈ N (11)
and ¤ • is defined as follows: for all A, B ⊆ N , with A ∩ B = ∅,

A ¤ • B if (N \ B) ¤ (N \ A). ( 12
)
It is straightforward to check that ¤ • satisfies monotonicity condition (9) and that R satisfies condition (10).

Conversely, let R be a relation that satisfies (10) and ¤ • , P • i , V • i a type II representation of R. We build a type I representation ¤, S i , V i of R by letting:

S i = (P • i ) cd (the co-dual of P • i ), ∀i ∈ N (13) V i = V • i , ∀i ∈ N ( 14
)
and ¤ is defined as follows: for all A, B ⊆ N , with

A ∪ B = N , A ¤ B if (N \ B) ¤ • (N \ A). ( 15
)
Again, it is easy to prove that ¤ satisfies (6) and that R satisfies condition (7). Observe that because P • i , it co-dual S i is complete. P

The proof of the lemma has established a correspondence between representations of type I and type II of a CDR, which we state in the following definition.

Definition 7 (Conjugate representations)

Let R be a CDR and ¤, S i , V i (resp. ¤ We state below three consequences of the equivalence of the two definitions of CDR.

1. It is immediate that an asymmetric outranking relation as yielded by the Tactic method described above satisfies the alternative definition of a CDR (Definition 5). By Lemma 6, it also satisfies Definition 2. Asymmetric concordance-discordance relations will be referred to by the acronym A-CDR.

2. If ¤, S i , V i and £ • , P • i , V • i )
are dual representations of a CDR, R, we see that condition (5) in Electre I could equivalently be formulated in terms of the strict preference P i as i∈P (y,x) w i j∈N w j ≤ 1 -s.

3. Let R be a CDR and let ¤, S i , V i , ¤ • , P • i , V • i be conjugate representations of R. The concordance part C(R) of the outranking relation R has been defined, using (7) and assuming V i = ∅, by x C(R) y if S(x, y) ¤ S(y, x). In the same spirit, we may use (10), assuming

V • i = ∅, yielding x C(R) y if P (x, y) ¤ • P (y, x). Assuming that ¤, S i , V i and ¤ • , P • i , V • i
are conjugate representations of R, it is easy to see that the latter definition is equivalent with the initial one.

Summarizing, we may say that all crisp outranking relations, either those reflexive relations produced, e.g., by the Electre I method, or the asymmetric ones produced, e.g., by Tactic are CDR. Their distinctive structural features are mainly properties such as reflexivity vs irreflexivity, asymmetry or completeness. These properties of the outranking relations are reflected in their representations, more precisely, in corresponding properties of ¤ or ¤ • . The following proposition formally states some useful related results.

Proposition 8

Let R be a CDR and ¤, S i , V i (resp. ¤ • , P • i , V • i ) its representation of type I (resp. of type II). We have:

1. R is either reflexive or irreflexive, R is reflexive ⇔ N ¤ N ⇔ ∅ ¤ • ∅, otherwise, R is irreflexive, 2. R is asymmetric ⇔ ¤ is asymmetric ⇔ ¤ • is asymmetric, 3. R is complete ⇔ (A ¤ B or B ¤ A), ∀A, B ⊆ N, A ∪ B = N ⇔ (C ¤ • D or C ¤ • D), ∀C, D ⊆ N, C ∩ D = ∅.
The straightforward proof is left to the reader. For Parts 2 and 3, the proof of the ⇒ part uses the hypothesis that all attributes are influential (so that, for all A, B ⊆ N such that A ∪ B = N , there are x, y ∈ X such that S(x, y) = A and S(y, x) = B and for all C, D ⊆ N such that C ∩ D = ∅, there are z, w ∈ X such that P • (z, w) = C and P • (w, z) = D).

These properties can immediately be applied to outranking relations built using Electre I or Tactic. If R arises from Electre I, it satisfies (5) so that N ¤ N . As a consequence of Proposition 8.1, R is reflexive. A relation R arising from Tactic satisfies (8). This implies Not[∅ ¤

• ∅] and [C ¤ • D ⇒ Not[D ¤ • C]],
for all C, D ⊆ N with C ∩ D = ∅. Hence, using Proposition 8.1 and 8.2, we see that R is irreflexive and asymmetric.

Remark 9 (The rôle of co-duality)

This section has shown that both reflexive and asymmetric outranking relations can be described in a common framework specified by either Definition 2 or, equivalently, Definition 5. In spite of this resemblance, their interpretations are rather contrasted since reflexive preferences are usually interpreted as "at least as good" relations while asymmetric preferences are interpreted as "better than" relations. With these interpretations, some sort of semantic relationship is intuitively expected between "at least as good" and "better than" relations. If we start with a reflexive preference relation R, interpreted as an "at least as good" relation, the corresponding "better than" relation is the asymmetric part R α of R. Conversely, starting with an asymmetric preference relation R (like in the Tactic method), how can we define the corresponding "at least as good" relation? At first glance, it is tempting to say that x is at least as good as y if y is not better than x, which amounts to define the "at least as good" relation as the co-dual of R . Such a definition automatically yields a complete reflexive relation (in view of the properties of the co-dual operator that were recalled in Section 2). This is problematic since reflexive preference relations cannot always be assumed to be complete (see [START_REF] Deparis | When conflict induces the expression of incomplete preferences[END_REF], for an experimental investigation of incomparability in preferences). In particular, in the context of outranking methods, pairs of alternatives may be incomparable, due for instance to veto effects (see Roy, 1996). Actually, an asymmetric outranking relation can be, in general, the asymmetric part of several reflexive outranking relations. Determining a unique reflexive relation having a given asymmetric part requires additional information, namely the specification of the list of incomparable pairs of alternatives (referred to as the incomparability relation in Roy, 1996).

Although co-duality does not determine a correspondence between reflexive and asymmetric outranking relations, it plays a major rôle for understanding their relationship. Therefore, we devote the rest of Section 3 to investigate the effect of the co-dual and asymmetric part operators on outranking relations. We first consider concordance relations (with empty veto relations) then we examine the case of concordance-discordance relations.

•

The co-dual and the asymmetric part of a concordance relation

We first define the co-dual of the relation comparing the coalitions of attributes in Definition 2 and state properties of such relations that will be useful in the sequel.

Definition 10

Let ¤ be a relation between subsets of N having N for union. We call the co-dual of ¤, the relation ¤ cd between subsets of N having N for union that is defined as follows: for all A, B ⊆ N , with

A ∪ B = N , we have A ¤ cd B ⇔ Not[B ¤ A].

Lemma 11

Let ¤ and ¤ be two relations between subsets of N having N for union and satisfying monotonicity condition (6).

1. The intersection ¤ ∩ ¤ of these relations is a relation between subsets of N having N for union and satisfying (6).

2. The co-dual ¤ cd and the asymmetric part ¤ α of ¤ both satisfy condition (6).

Proof. The proof is left to the reader.

Remark 12

Similar properties can be established for relations ¤ • that intervene in type II representations of concordance relations (CR). We emphasize that ¤ • is a relation between disjoint subsets of N and satisfies monotonicity condition (9). •

The co-dual of a CR is a CR and there is a correspondence between the type I representations of these relations.

Proposition 13

Let R be a CR that has a representation of type I, ¤, (x, y)]. The latter condition can be rewritten as x R cd y ⇔ S(x, y) ¤ cd S(y, x) , where ¤ cd is the co-dual of ¤. Using Lemma 11.2, we know that ¤ cd , S i is a type I representation of R cd . P

S i . The co-dual R cd of R is also a CR with a representation of type I that is ¤ cd , S i . Proof We have x R y ⇔ [S(x, y) ¤ S(y, x)]. The co-dual R cd of R is such that x R cd y ⇔ Not[y R x]. Hence, we have x R cd y ⇔ Not[S(y, x) ¤ S

Remark 14

A quite similar correspondence holds for type II representations.

If ¤ • , P • i is a type II representation of R, ¤ • cd , P • i is a type II representation of R cd .
Moreover, if the type I and II representations of R are dual of one another (Definition 7), the corresponding representations of R cd are also dual of one another. In particular, if ¤ and ¤ • are linked through relations ( 12) and ( 15) then their respective co-dual ¤ cd and ¤ • cd are linked through the same relations.

•

Remark 15

The general properties of the co-dual operator, which were recalled in Section 2, apply to the particular case of concordance relations. In particular, the co-dual of a reflexive CR is an irreflexive CR and conversely. Also, the co-dual of an asymmetric CR is a complete CR and conversely.

•

We now turn to considering the asymmetric part of a R-CR. Taking the asymmetric part of a R-CR yields a CR (that is of course asymmetric hence irreflexive).

Proposition 16

The asymmetric part of a R-CR, that has a type I representation ¤, S i , is the A-CR that has a type I representation ¤ α , S i with ¤ α , the asymmetric part of ¤. (y, x) and Not[S(y, x) ¤ S(x, y)]]. The latter condition can be rewritten as x R α y ⇔ [S(x, y) ¤ α S(y, x)], where ¤ α is the asymmetric part of ¤. Using Lemma 11.2, we know that ¤ α , S i is a type I representation of R α . P

Proof Let R be a R-CR. We have x R y ⇔ [S(x, y) ¤ S(y, x)]. The asymmetric part R α of R is such that x R α y ⇔ x R y and Not[y R x]. Hence, we have x R α y ⇔ [S(x, y) ¤ S

Remark 17 (Type II representations)

A remark similar to Remark 14 can be formulated for type II representations of R and R α . In particular, let ¤

• , P • i be a type II representation of R. The asymmetric part R α of R has a type II representation ¤ •α , P • i , with ¤ •α , the asymmetric part of ¤ • .
•

Summarizing, if a R-CR is complete, its asymmetric part is an A-CR which is also its co-dual. On the other hand, for a given A-CR, there are several R-CR having it as their asymmetric part. One of them is a complete relation and its co-dual. Note also that all what we said for CR remains valid for CR-AT, i.e., CR with attribute transitivity (as defined in Remark 3).

Vetoes and bonuses

We now address the general case of outranking relations with veto. Considering concordance-discordance relations changes the picture. The correspondence between R-CR and A-CR described in the previous section no longer holds. In particular, the asymmetric part of a R-CDR is not, in general, an A-CDR. We investigate such issues below.

Let R be a R-CDR. For all x, y ∈ X, we have that

x R y if x C(R) y and x N D(R) y, where C(R) is the R-CR associated with R and x N D(R) y if Not[y i V i x i ], for all i ∈ N (see Remark 4).
The asymmetric part R α of R obtains as follows:

x R α y ⇔ x R y and Not[y R x] ⇔ [x C(R) y and x N D(R) y] and [Not[y C(R) x] or Not[y N D(R) x]]
It is easy to see that the above definition can equivalently be written as:

x R α y ⇔ Hence we have x R α y if and only if one of the following two exclusive conditions is fulfilled:

1. (x, y) belongs to the asymmetric part of C(R) and x N D(R) y or 2. (x, y) belongs to the symmetric part of C(R), x N D(R) y and, for some i ∈ N , x i V i y i
Case 1 corresponds to the definition of an A-CDR since, by Proposition 16, the asymmetric part of C(R), which is a R-CR, is an A-CR, a non-discordance condition is imposed on it.

Case 2 looks a bit more unexpected. There is no such condition in the definition of an A-CDR or in the Tactic motivating example of an A-CDR. With Case 2, we have x R α y when (x, y) belongs to the symmetric part of C(R) and there is no veto of y against x (∀j, Not[y j V j x j ]) but on some attribute i, we have x i V i y i , which means that x i is a much better performance than y i on attribute i. The presence of a veto in favor of x against y can thus have a positive effect in breaking a tie in the concordance relation. We call such an effect a bonus.

In contrast with Proposition 16, the asymmetric part of an R-CDR is not, in general, an A-CDR, due to the possible occurrence of bonus effects.

Let us now examine the effect of the co-dual operator on concordance-discordance relations. Assume, for instance, that R is an A-CDR. By definition of an A-CDR, we have:

x R y if x C(R) y and x N D(R) y, where C(R) is the A-CR associated with R. The co-dual R cd of R is such that: x R cd y ⇔ Not[y C(R) x] or Not[y N D(R) x]. ( 16
)
The first condition in the righthand side of ( 16) states that (x, y) belongs to the co-dual of C(R). We know that the co-dual of this A-CR is a complete R-CR (Proposition 13). The second condition in the righthand side of ( 16), means again that there may be a bonus effect, i.e., that x i V i y i (for any i ∈ N ) entails x R cd y. Condition ( 16) defining the co-dual of an A-CDR is very similar to the one defining a R-CDR except that veto plays a positive rôle here. In contrast with Proposition 13, the co-dual of a CDR is not, in general, a CDR, due to the possible occurrence of bonus effects. It is a concordance relation with bonus (CRB) as defined below. In this definition, the non-veto condition in Definition 2 is just transformed into a bonus condition.

Definition 18 (Concordance relation with bonus (CRB))

A binary relation R on X = n i=1 X i is a concordance relation with bonus (CRB) if there are:

1. 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 , 3. a binary relation ¤ between subsets of N having N for union that is mono- tonic w.r.t. inclusion, i.e., for all A, B, C, D ⊆ N with A ∪ B = N and C ∪ D = N , [A ¤ B, C ⊇ A, B ⊇ D] ⇒ C ¤ D, ( 17
) such that, for all x, y ∈ X, x R y ⇔ [S(x, y) ¤ S(y, x) or V (x, y) = ∅] , ( 18
)
where S(x, y) = {i ∈ N :

x i S i y i } and V (x, y) = {i ∈ N : x i V i y i }. We say that ¤, S i , V i is a representation of R as a CRB.
Note that a concordance relation (CR) is a CRB in which all the V i relations are empty. As for concordance-discordance relations, we may distinguish reflexive CRB's (R-CRB) on the one hand and asymmetric CRB's (A-CRB) on the other hand. The alternative definition of a CDR established in Lemma 6 can also be transposed for CRB's without any difficulty and we omit the details.

It is easy to see that CRB's and CDR's are related through co-duality as stated in the following proposition.

Proposition 19

Relation R on X is a concordance-discordance relation if and only if its co-dual R cd is a concordance relation with bonus and conversely.

Proof

Let R be a CDR having ¤, S i , V i as a representation of type I. Using Proposition 13, we know that R cd is a concordance relation that has ¤ cd , S i as a representation of type I as a CR. Since R cd is defined, for all x, y ∈ X, by

x R cd y ⇔ Not[S(y, x) ¤ S(x, y) and V (y, x) = ∅] ⇔ Not[S(y, x) ¤ S(x, y)] or [V (y, x) = ∅] ⇔ [S(x, y) ¤ cd S(y, x)] or [V (y, x) = ∅],
we see that it is a CRB having a representation of type I, which is

¤ cd , S i , V i .
The converse is also true. Starting with R, a CRB that has a type I representation ¤ cd , S i , we apply the co-dual operator as follows:

x R cd y ⇔ Not[S(y, x) ¤ S(x, y) or V (y, x) = ∅] ⇔ Not[S(y, x) ¤ S(x, y)] and [V (y, x) = ∅] ⇔ [S(x, y) ¤ cd S(y, x)] and [V (y, x) = ∅].
Relation R cd is a CDR that admits the type I representation ¤ cd , S i , V i . P

Because the asymmetric part R α of a R-CDR, R may involve at the same time bonus and veto effects, simple examples show that it is neither an asymmetric CDR nor an asymmetric CRB. Such relations require an analysis that is more complex than the one for CDR or CRB. It is detailed in BP14.

Summary

Summarizing the above analysis of the relationship between non-strict and strict outranking relations, we draw the reader's attention to the following points.

1. As long as we are concerned with concordance relations, without considering vetoes, we see that there is no deep difference in nature between non-strict and strict concordance relations: R-CR and A-CR satisfy the same definition (Definition 2). They just differ by the additional property that they are respectively reflexive or asymmetric. Moreover, the asymmetric part of a R-CR is an A-CR. The co-dual of an A-CR is a complete R-CR. Knowing an A-CR, there is no way of distinguishing indifference from incomparability in view of reconstructing an hypothetic original R-CR of which the A-CR that we know would be the asymmetric part. From a practical point of view, this can be seen as an advantage of R-CR models over A-CR's. The preferential information encoded in a R-CR permits to distinguish incomparable pairs of alternatives from indifferent ones, while A-CR's do not allow for that.

2. Allowing for vetoes changes the picture. The asymmetric part of a R-CDR is not an A-CDR but a more complex object, in general consisting of two disjoint relations: on the one hand, the intersection of the asymmetric part of the associated concordance relation and the non discordance relation (as expected). On the other hand, a part of the indifference relation of the associated concordance relation determined as follows: if one of the two arcs linking a pair of alternatives in the indifference part of the concordance relation is broken due to a veto, while the other is not, then the remaining arc belongs to the asymmetric part of the R-CDR. In this case, the veto relation acts as a bonus.

In the rest of this paper, we take advantage of the just explored co-duality relationships between strict and non-strict outranking relations, in order to unify and deepen the axiomatic analysis that we presented in several previous papers (BP02b, BP05b, BP06, BP07, BP09a).

Axiomatic analysis

We start by recalling some of earlier results on the characterization of CR and CDR. Then we study the effect of the co-dual operator on our axioms. We derive new axiomatic characterizations of classical outranking relations as well as we obtain characterizations of preference relations involving bonuses instead of vetoes. Our main goal is to offer a unified and comprehensive framework allowing clear understanding of the relationships between strict and non strict outranking relations.

Background

We briefly recall the axioms used in the characterization of reflexive CDR obtained in BP09a, under the assumption that all attributes are influential.

Definition 20 (Axioms RC 1, RC 2) Let R be a binary relation on a set X = n i=1 X i . This relation is said to satisfy:

RC 1 i if (x i , a -i ) R (y i , b -i ) and (z i , c -i ) R (w i , d -i )      ⇒      (z i , a -i ) R (w i , b -i ) or (x i , c -i ) R (y i , d -i ), RC 2 i if (x i , a -i ) R (y i , b -i ) and (y i , c -i ) R (x i , d -i )      ⇒      (z i , a -i ) R (w i , b -i ) or (w i , c -i ) R (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 R satisfies RC 1 (resp. RC 2) if it satisfies RC 1 i (resp. RC 2 i ) for all i ∈ N .
An interpretation of these axioms was provided in BP02a. It relies on a reformulation of the axioms in terms of traces left by the preference R on each attribute scale. The relevant traces in the present case are relations comparing preference differences on each attribute. They are precisely defined as follows (see also BP05a, for more detail on traces).

Definition 21 (Relations *

i , * * i ) Let R 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 ) ⇔ ∀a -i , b -i ∈ X -i , [(z i , a -i ) R (w i , b -i ) ⇒ (x i , a -i ) R (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 )] .
In order to understand the close relationship between * i and RC 1 i , assume that RC 1 i is not true. Hence, for some

x i , y i , z i , w i ∈ X i and some a -i , b -i , c -i , d -i ∈ X -i , both premises of RC 1 i are satisfied and none of its conclusions. We thus have (x i , a -i ) R (y i , b -i ) and Not[(z i , a -i ) R (w i , b -i )], which is tantamount to Not[(z i , w i ) * i (x i , y i )]. Similarly, we have (z i , c -i ) R (w i , d -i ) and Not[(x i , c -i ) R (y i , d -i )], which means Not[(x i , y i ) * i (z i , w i )].
Hence it is clear that RC 1 i holds if and only if all pairs of elements in X i are comparable w.r.t. * i . This conclusion constitutes the first part of the lemma below. The second part is obtained similarly, considering RC 2 i (see BP02a, for the proof).

Lemma 22 (BP02a, 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 , Not[(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].
Since * i and * * i are transitive by definition, the above lemma states that * i (resp. * * i ) is a weak order if and only if RC 1 i holds (resp. RC 1 i and RC 2 i hold). The precise interpretation of axiom RC 1 i and RC 2 i are thus as follows. Axiom RC 1 i amounts to say that all preference differences (x i , y i ) on X i can be weakly ordered. Axiom RC 2 i establishes a link between opposite differences of preferences such as (x i , y i ) and (y i , x i ). Note that RC 2 entails that R is an independent preference relation.

Remark 23

In the sequel, all introduced axioms may be interpreted in terms of properties of some traces. These properties will be stated in lemmas, the proof of which basically constitutes the interpretation of the axioms. For the sake of conciseness, we shall not provide more explicit interpretations.

•

A crucial feature of CR and CDR is that they induce relations * i and * * i having a limited number of equivalence classes. This is the motivation for the following two conditions.

Definition 24 (Axioms M 1, M 2) Let R 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 ) R (y i , b -i ) and (z i , c -i ) R (w i , d -i )      ⇒                (y i , a -i ) R (x i , b -i ) or (w i , a -i ) R (z i , b -i ) or (x i , c -i ) R (y i , d -i ), (19) M 2 i if (x i , a -i ) R (y i , b -i ) and (y i , c -i ) R (x i , d -i )      ⇒                (y i , a -i ) R (x i , b -i ) or (z i , a -i ) R (w i , b -i ) or (z i , c -i ) R (w i , d -i ), (20) 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 .
The interpretation of M 1 i and M 2 i , respectively conditional on RC 2 i and RC 1 i , results from the following lemma.

Lemma 25 1. If R satisfies RC 2 i , then R satisfies M 1 i ⇔ [for all x i , y i , z i , w i ∈ X i , Not[(y i , x i ) * i (x i , y i )] ⇒ (x i , y i ) * i (z i , w i )], 2. If R satisfies RC 1 i , then R satisfies M 2 i ⇔ [for all x i , y i , z i , w i ∈ X i , Not[(y i , x i ) * i (x i , y i )] ⇒ (z i , w i ) * i (y i , x i )],
Proof

The proof of item 1 (resp. item 2) results from the combination of BP07, Lemma 11.1 and 11.3 (resp. 11.2 and 11.4) and BP05b, Lemma 16.1 (resp. 16.2). P

Let us call a positive preference difference (resp. negative preference difference) one that is at least (resp. at most) as large as the opposite preference difference.

Under RC 2 i , M 1 i says that a positive preference difference is at least as large as any other preference difference. In other terms, there is only one class of positive preference differences. Under RC 1 i , M 2 i states the symmetric property for negative preference differences. For more detail on the interpretation of M 1 and M 2, see BP07 and BP05b).

Remark 26 (Axioms UC and LC )

A simpler-and slightly stronger-version of axioms M 1 i , M 2 i was used in our initial characterization of concordance relations in BP05b. These axioms, respectively labeled UC i and LC i , obtain by dropping the second in the three possible conclusions in the definitions of M 1 i and M 2 i . The substitution of UC i and LC i by M 1 i and M 2 i in the characterization of reflexive CR was motivated by the need for independent sets of axioms. By Lemma 16.3 in BP05b, we established indeed that RC 2 i , UC i and LC i imply RC 1 i . The second in the three possible conclusions in the definitions of M 1 i and M 2 i has precisely the effect of guaranteeing the independence of the set of axioms RC 1 i , RC 2 i , M 1 i and M 2 i , as is shown in the next theorem.

•

Theorems 27 and 29 below are variants of Theorems 13 in BP07 and Theorem 19 in BP09a, respectively. The theorems stated below are slightly more general than their previous versions in two respects. First they are stated for general binary relations, instead of reflexive relations. The reflexivity property was actually playing no rôle in the proofs of the previous characterizations, which remain unchanged and are thus omitted. The second detail is that the independence of the axioms is now stated in the class of complete relations (instead of the class of reflexive ones). Most of the examples previously used to show the independence of the axioms were complete relations. For the sake of completeness, we recall these examples below and provide an additional one that is needed for proving Theorem 29.

Theorem 27

The binary relation R on X = n i=1 X i is a concordance relation (CR) iff it satisfies RC 1, RC 2, M 1 and M 2. These axioms are independent in the class of complete binary relations.

Proof

As we said before, the proof of Theorem 13 in BP07 remains valid for general binary relations and we omit it. The independence of the axioms in the class of complete relations results from the following examples (see Appendix):

Violated axiom RC 1 i RC 2 i M 1 i M 2 i
Example 79 77 78 83

P

We now introduce a weakened version of M 2 i , axiom M 3 i , which allows for vetoes, i.e., "large negative" preference differences forbidding that a pair of alternatives may belong to the global preference relation.

Definition 28

Let R 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 ) R (y i , b -i ) and (y i , c -i ) R (x i , d -i ) and (z i , e -i ) R (w i , f -i )                ⇒                (y i , a -i ) R (x i , b -i ) or (z i , a -i ) R (w i , b -i ) or (z i , c -i ) R (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 R satisfies M 3 if it satisfies M 3 i for all i ∈ N .
We observe that M 3 i only differs from M 2 i by the adjunction of the third premise, implying that M 3 i is a weakening of M 2 i . The interpretation of M 3 i , under the hypothesis that RC 1 i holds, results from that of M 2 i as stated in Lemma 25.2. Assuming RC 1 i amounts to say that * i is complete. Hence if the first two premises of M 3 i hold and neither the first nor the third conclusion do, then we have

(x i , y i ) * i (y i , x i ) * i (z i , w i ).
In these circumstances, the second conclusion cannot be true, since this would imply that (z i , w i ) * i (y i , x i ), a contradiction with (y i , x i ) * i (z i , w i ). Hence, none of the three conclusions holds and M 3 i can only be satisfied if it never happens that (z i , e -i ) R (w i , f -i ). This means that the pair (z i , w i ) represents an unacceptable preference difference, leading to a veto. We have the following result.

Theorem 29

The binary relation R on X = n i=1 X i is a concordance-discordance relation (CDR) iff it satisfies RC 1, RC 2, M 1 and M 3. These axioms are independent in the class of complete binary relations.

Proof

As said before, the proof of Theorem 19 in BP09a remains valid for general binary relations and we omit it. In order to prove the independence of the axioms in the class of complete relations, we may invoke again those examples used in the proof of Theorem 27. It only remains to exhibit an example of a complete relation satisfying RC 1, RC 2, M 1 and M 3 i on all attributes but one. Example 83 in appendix fulfills this requirement. P

Characterizations of CR via co-duality

From Proposition 13 we know that the co-dual of a concordance relation R is also a CR. Starting from the axioms above, it is not difficult to reformulate them in terms of the co-dual relation R cd . Let R be any relation on X. Consider for instance axiom RC 1 i . Using contraposition, we obtain: R satisfies RC 1 i , i.e.,

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 )]
if and only if R cd satisfies:

(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 ),
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, the above condition is axiom RC 1 i imposed on relation R cd . Hence, R satisfies RC 1 1 iff its co-dual does. It can be similarly shown 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 co-dual.

The picture is not exactly the same for M 1 and M 2. Let us recall axioms Maj1 and Maj2 that have been introduced for characterizing strict concordance relations in BP06, Th. 2 (see also BP05c).

Definition 30 (Axioms Maj1, Maj2)

Let R be a binary relation on a set X = n i=1 X i . This relation is said to satisfy:

Maj1 i if (x i , a -i ) R (y i , b -i ) and (z i , a -i ) R (w i , b -i ) and (z i , c -i ) R (w i , d -i )                ⇒      (y i , a -i ) R (x i , b -i ) or (x i , c -i ) R (y i , d -i ), ( 21
)
Maj2 i if (x i , a -i ) R (y i , b -i ) and (w i , a -i ) R (z i , b -i ) and (y i , c -i ) R (x i , d -i )                ⇒      (y i , a -i ) R (x i , b -i ) or (z i , c -i ) R (w i , d -i ), ( 22
)
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 Maj1 (resp. Maj2) holds if Maj1 i (resp. Maj2 i ) holds for all i ∈ N . Contraposition of M 1 i yields: R satisfies M 1 i if and only if R cd satisfies the following condition: 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 (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 ). ( 23
)
It is readily seen that this condition is axiom Maj2 i imposed on relation R cd . Indeed expressions ( 22) and ( 23) only differ by the positions of a -i and b -i , c -i and d -i , z i and w i , which have been interchanged, and by the substitution of R with R cd . Paraphrasing this result, we state that imposing M 1 i on R is tantamount to imposing Maj2 i on its co-dual R cd and conversely.

In a similar way, starting from condition M 2 i imposed on R, we obtain the following equivalent condition imposed 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 ). ( 24
)
We observe that the latter condition is axiom Maj1 i imposed on relation R cd (with the positions of a -i and b -i , c -i and d -i , z i and w i having been interchanged). Imposing M 2 i on R is equivalent to imposing Maj1 i on its co-dual R cd and conversely.

We collect our findings in the next lemma. Its proof results from the above observations.

Lemma 31

Let R be any relation on X and R cd its co-dual. The following statements hold, 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 Maj2 i , 4. R satisfies M 2 i iff R cd satisfies Maj1 i .
Co-duality induces a simple correspondence between the relations comparing preference differences on each attribute, namely the relations * i (resp. * * i ) associated with a relation R and its co-dual R cd . To avoid ambiguity, we write *

i (R), * * i (R) (resp. * i (R cd ), * * i (R cd ))
to denote the two relations comparing preference differences on attribute i associated with R (resp. R cd ). Using Definition 21 and that of R cd , it is straightforward to establish the following result.

Lemma 32

Let R be any relation on X and R cd its co-dual. For all i ∈ N , for all x i , y i , z i , w i ∈ X i , we have:

1. (x i , y i ) * i (R cd ) (z i , w i ) iff (w i , z i ) * i (R) (y i , x i ), 2. (x i , y i ) * * i (R cd ) (z i , w i ) iff (x i , y i ) * * i (R) (z i , w i ).

Remark 33

In Remark 26, we pointed out that M 1 i (resp. M 2 i ) is a weakening of axiom UC i (resp. LC i ) that was used in an earlier-non independent-characterization of concordance relations. It is easy to see that also axioms Maj1 i and Maj2 i are respectively weakened forms of UC i and LC i , obtained by imposing an additional clause (the second one) as a premise. We thus have that UC i entails Maj1 i and LC i entails Maj2 i , a property that will be used below.

In the context of the present paper, UC and LC are at an advantage w.r.t. M 1 and M 2 or Maj1 and Maj2 since they form a pair of cross co-dual conditions. It is indeed easy to check that imposing UC i on relation R is equivalent to imposing LC i on its co-dual R cd and conversely.

•

Starting from the characterization of a reflexive concordance relation (Theorem 27) and using the results of Lemma 31, we easily obtain a "dual" characterization of irreflexive CR's. Actually, the characterization of reflexive CR's is also valid for irreflexive CR's and conversely. The following lemma will help us establishing characterizations that are valid for both reflexive and irreflexive concordance relations. We remind the reader that a CR is either reflexive or irreflexive (Proposition 8.1).

Lemma 34

The following implications hold for all i ∈ N :

1. M 1 i and RC 2 i entail Maj1 i , 2. Maj1 i and RC 1 i entail M 1 i , 3. M 2 i and RC 1 i entail Maj2 i , 4. Maj2 i and RC 2 i entail M 2 i .
Under RC 1 i and RC 2 i , we have:

1. M 1 i ⇔ Maj1 i , 2. M 2 i ⇔ Maj2 i . Proof 1. Assume that RC 2 i and M 1 i hold for a relation R . If we have Not[(w i , a -i ) R (z i , b -i )] in (19)
, M 1 i entails the two remaining possible consequences in (21). On the contrary, if (w i , a -i ) R (z i , b -i ) holds true, since we have that

(z i , c -i ) R (w i , d -i ), we may apply RC 2 i yielding (y i , a -i ) R (x i , b -i ) or (x i , c -i ) R (y i , d -i
), which are the desired consequences in order to establish that Maj1 i holds.

2. Assume that RC 1 i and

Maj1 i hold. If (z i , a -i ) R (w i , b -i ) is true then Maj1 i implies that the first or the third conclusion of M 1 i is true. Otherwise, we have (x i , a -i ) R (y i , b -i ) and (z i , c -i ) R (w i , d -i ). Applying RC 1 i we get either (z i , a -i ) R (w i , b -i ) or (x i , c -i ) R (y i , d -i ).
We have assumed that the former does not hold, hence the latter is true, which establishes M 1 i .

3. Assuming that RC 1 i and M 2 i hold, we show that Maj2 i is satisfied. If the second consequence in (20) does not hold, i.e., if we have

Not[(z i , a -i ) R (w i , b -i )]
, then M 2 i entails one or the other consequence in Maj2 i . On the contrary, if (z i , a -i ) R (w i , b -i ) holds, considering the third premise of Maj2 i , i.e., (y i , c -i ) R (x i , d -i ) and using RC 1 i , we get either consequence of Maj2 i .

4. Finally, assuming that RC 2 i and Maj2 i hold, we derive M 2 i . This is immediate whenever (w i , a -i ) R (z i , b -i ) is true since then Maj2 i implies that the first or the third conclusion of M 2 i is true. In the opposite case, from

(x i , a -i ) R (y i , b -i ) and (y i , c -i ) R (x i , d -i ), we obtain, using RC 2 i , that (w i , a -i ) R (z i , b -i ) or (z i , c -i ) R (w i , d -i ).
Since the former has been assumed to be false, the latter, which is the third conclusion of M 2 i , is true, concluding the proof. The equivalence of M 1 i and Maj1 i under RC 1 i and RC 2 i results from the first two items. The equivalence of M 2 i and Maj2 i , under RC 1 i and RC 2 i is a consequence of items 3 and 4. P

We also have the following result. Assume there is some x such that x R x and consider any z ∈ X. From

(x i , x -i ) R (x i , x -i ) and RC 2 i , we deduce that (z i , x -i ) R (z i , x -i ). For j = i, using RC 2 j , we can similarly show that (z i , z j , x -ij ) R (z i , z j , x -ij ).
Continuing in a similar way, we finally obtain z R z.

Lemma

A new independent self co-dual characterization of CR

Axioms M 1 i and Maj1 i (resp. M 2 i and Maj2 i ) admit a common weaker formulation, MM 1 i (resp. MM 2 i ), that simplifies the characterizations of CR and will be useful in the sequel.

Definition 41 (Axioms MM 1, MM 2)

Let R be a binary relation on a set X = n i=1 X i . This relation is said to satisfy:

MM 1 i if (x i , a -i ) R (y i , b -i ) and (z i , a -i ) R (w i , b -i ) and (z i , c -i ) R (w i , d -i )                ⇒                (y i , a -i ) R (x i , b -i ) or (w i , a -i ) R (z i , b -i ) or (x i , c -i ) R (y i , d -i ), MM 2 i if (x i , a -i ) R (y i , b -i ) and (w i , a -i ) R (z i , b -i ) and (y i , c -i ) R (x i , d -i )                ⇒                (y i , a -i ) R (x i , b -i ) or (z i , a -i ) R (w i , b -i ) or (z i , c -i ) R (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 MM 1 (resp. MM 2) holds if MM 1 i (resp. MM 2 i ) holds for all i ∈ N .

Note that MM 1 i , without its second premise, is identical to M 1 i . MM 1 i , without its second conclusion, is Maj1 i . MM 1 i , without both its second premise and its second conclusion, is UC i . MM 1 i is clearly a weaker condition than both M 1 i and Maj1 i . Similar observations can be made, linking MM 2 i , M 2 i and Maj2 i . MM 2 i is a weakened variant of the two others. However, under RC 1 i and RC 2 i , MM 1 i can be shown to be equivalent to M 1 i , Maj1 i and U C i , as stated in the following lemma. A similar statement holds for MM 2 i .

Lemma 42

The following implications hold for all i ∈ N :

1. MM 1 i and RC 1 i entail M 1 i , 2. MM 1 i and RC 2 i entail Maj1 i , 3. MM 2 i and RC 2 i entail M 2 i , 4. MM 2 i and RC 1 i entail Maj2 i .
Under RC 1 i and RC 2 i , we have:

1. MM 1 i ⇔ M 1 i ⇔ Maj1 i ⇔ UC i , 2. MM 2 i ⇔ M 2 i ⇔ Maj2 i ⇔ LC i .

Proof

The proofs are very similar to those used to establish Lemma 34. We prove the first implication, leaving the three others to the reader. Assume that MM 1 i and RC 1 i hold. We show that M 1 i must be true. Applying RC 1 i to the premises of

M 1 i yields (x i , c -i ) R (y i , d i ) or (z i , a -i ) R (w i , b -i ).
If the former is true, then M 1 i is verified. Else, all three premises of MM 1 i are satisfied, which entails the disjunction of three conclusions that is common to M 1 i and MM 1 i . The proofs of the two equivalences directly results from the four implications, Lemma 34 and Lemma 11.3 and 11.4 in BP07. The latter says that RC 2 i and M 1 i entail UC i and that RC 1 i and M 2 i entail LC i . By definition, UC i entails M 1 i and LC i entails M 2 i . P

Axioms MM 1 i and MM 2 i are cross co-dual, as are UC i and LC i (Remark 33).

More precisely, we have:

Lemma 43

Let R be a binary relation on X and R cd its co-dual. The following hold for all i ∈ N :

1. R satisfies MM 1 i iff R cd satisfies MM 2 i , 2. R satisfies MM 2 i iff R cd satisfies MM 1 i .

Proof

The proof results immediately from contraposition and using the definition of the co-dual. P

Using Lemmas 42 and 43, it is easy to derive the following new characterization result.

Theorem 44

The

Concordance relations with attribute transitivity

An additional property of CR, called attribute transitivity, was defined and studied in BP05b and BP07. Attribute transitivity amounts to assuming that the relations S i in Definition 2 are semiorders as is the case in most ordinal aggregation methods. We have shown in the two above-mentioned papers that reflexive concordance relations with attribute transitivity (R-CR-AT) can be characterized by adding axioms AC 1, AC 2 and AC 3, which are similar to RC 1 and RC 2 and were introduced and discussed in BP04a and BP02a. We recall these axioms and examine how they behave w.r.t. co-duality. Reflexive CR with attribute transitivity have been characterized in BP05b and BP07. We use co-duality to derive characterizations of irreflexive CR with attribute transitivity.

Axioms AC 1, AC 2 and AC 3 are recalled in the following definition.

Definition 45 (Axioms AC 1, AC 2, AC 3) Let R be a binary relation on a set X = n i=1 X i . This relation is said to satisfy:

AC 1 i if (x i , a -i ) R (y i , b -i ) and (z i , c -i ) R (w i , d -i )      ⇒      (z i , a -i ) R (y i , b -i ) or (x i , c -i ) R (w i , d -i ), AC 2 i if (x i , a -i ) R (y i , b -i ) and (z i , c -i ) R (w i , d -i )      ⇒      (x i , a -i ) R (w i , b -i ) or (z i , c -i ) R (y i , d -i ), AC 3 i if (x i , a -i ) R (y i , b -i ) and (y i , c -i ) R (w i , d -i )      ⇒      (x i , a -i ) R (z i , b -i ) or (z i , c -i ) R (w i , d -i ), for all x i , y i , z i , w i ∈ X i , all a -i , b -i , c -i , d -i ∈ X -i . We say that R 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 .
An interpretation of these axioms was provided in BP04a. Essentially, these axioms are related to the existence of linear arrangements of the elements (levels) of X i . AC 1 i suggests that the elements of X i can be linearly ordered relatively to "upward dominance": if x i "upward dominates" z i , then

(z i , c -i ) R (w i , d -i ) entails (x i , c -i ) R (w i , d -i ).
AC 2 i has a similar interpretation regarding "downward dominance". AC 3 i ensures that the upward and downward dominance orders are not incompatible. The following gives a precise definition of the upward and downward dominance relations.

Definition 46 (Relations +

i , - i and ± i ) Let R 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 ) R b ⇒ (x i , a -i ) R b], ( 25
) x i - i y i ⇔ ∀a ∈ X, b -i ∈ X -i , [a R (x i , b -i ) ⇒ a R (y i , b -i )], ( 26
) x i ± i y i ⇔ x i + i y i and x i - i y i . ( 27
)
By definition, + i , - i and ± i are transitive relations. Axioms AC 1 i , AC 2 i and AC 3 i ensure that they are complete, as restated in the next lemma.

Lemma 47 (BP04a, Lemma 3.1-4) Let R be a binary relation on a set X = n i=1 X i . R satisfies:

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.
As implied by Remark 3, a concordance relation with attribute transitivity is a CR having a representation ¤, S i , with relations S i that are semiorders. The following theorem characterizes CR with attribute transitivity. As for Theorems 27 and 29, it is a slight variation on Theorem 26 in BP07, which is formulated here for general binary relations. The independence of the axioms is not only valid for reflexive but also complete relations.

Theorem 48

The binary relation R on X = n i=1 X i is a concordance relation with attribute transitivity (CR-AT), i.e., has a representation ¤, S i in which all S i are semiorders, iff it satisfies RC 1, RC 2, AC 1, AC 3, M 1, M 2. In the class of complete relations, these axioms are independent.

Proof

The proof of the characterization result in Theorem 26 in BP07 remains valid for general binary relations and it is omitted. The latter was formulated for reflexive relations but this hypothesis plays no rôle in the proof so that the result is valid for general relations. We recall the examples establishing the independence of the axioms in the proof of Lemma 19 in BP07:

Violated axiom RC 1 i RC 2 i AC 1 i AC 3 i M 1 i M 2 i Example 79 77 81 82 78 83
All these relations are complete. Therefore the axioms are independent in the set of complete relations. P

Remark 49

Note that axiom AC 2 does not appear in this characterization because it is not independent of the other axioms. Indeed, Lemma 27.1 in BP06 and Lemma 11, items 3 and 4 in BP07 imply that under RC 1, RC 2, M 1 and M 2, axioms AC 1 and AC 2 are equivalent. AC 2 can thus substitute AC 1 in the characterization of reflexive CR with attribute transitivity.

•

We now examine how axioms AC 1, AC 2, AC 3 can be transposed in terms of the co-dual relation R cd . Using contraposition, as we have done above with RC 1 i , we can easily prove the following results.

Lemma 50

Let R be any relation on X and R cd its co-dual. The following equivalences hold, for all i ∈ N :

1. R satisfies AC 1 i iff R cd satisfies AC 2 i , 2. R satisfies AC 2 i iff R cd satisfies AC 1 i , 3. R satisfies AC 3 i iff R cd satisfies AC 3 i .
In the theorem below we extend the characterizations obtained in Theorem 36 to CR with attribute transitivity (CR-AT). The next lemma will be used in the proof of the theorem.

Lemma 51

Let R be a relation on X and R d its dual relation. We have the following:

1. R satisfies RC 1 i (resp. RC 2 i , AC 3 i , M 1 i , Maj1 i , M 2 i , Maj2 i , UC i , LC i )
for some i ∈ N if and only if R d satisfies the same property, 2. R satisfies AC 1 i (resp. AC 2 i ) for some i ∈ N if and only if R d satisfies AC 2 i (resp. AC 1 i ) for the same i.

Proof

The proof consists in checking that each of the equivalences holds, starting from the properties definition. It is easy once it is noted that, for all i ∈ N and all x i , y i , z i , w i ∈ X i ,

x i + i (R d ) y i ⇔ y i - i (R) x i , x i - i (R d ) y i ⇔ y i + i (R) x i , (x i , y i ) * i (R d ) (z i , w i ) ⇔ (y i , x i ) * i (R) (w i , z i ),
where

+ i (K) (resp. - i (K), * i (K)) denotes the relation + i (resp.
- i , * i ) using K as the base relation. P

A result similar to Lemma 32 can be established for the upward and downward dominance relations + i , - i , ± i . As in this lemma, our notation makes explicit whether the upward and downward dominance relations refer to R or its co-dual R cd .

Lemma 52

Let R be a binary relation on X and R cd its co-dual. For all i ∈ N , for all x i , y i ∈ X i , we have: To prove the independence of the axioms in the set of complete relations, the examples used in the proof of Theorem 48 are also suitable here since these examples satisfy M 1 i whenever they satisfy MM 1 i and similarly for M 2 i and MM 2 i . According with Lemma 51, taking the dual of these examples and substituting AC 1 by AC 2 in the characterization preserves the independence of the axioms. Taking the co-dual of these examples leads to asymmetric relations, showing the independence of the axioms characterizing CR-AT in the class of asymmetric relations.

1. x i + i (R cd ) y i iff x i - i (R) y i , 2. x i - i (R cd ) y i iff x i + i (R) y i , 3. x i ± i (R cd ) y i iff x i ± i (R) y i . Proof The proof

P Corollary 54

The relation R on X is a concordance relation with attribute transitivity (CR-AT) iff R satisfies RC 1, RC 2, AC 1, AC 3, Maj1 and Maj2. These axioms are independent in the class of complete relations and in the class of asymmetric relations. In this characterization, AC 1 can be substituted by AC 2 without any other change.

Proof

Under RC 1 and RC 2, MM 1 is equivalent to Maj1 and MM 2 to Maj2 (Lemma 42). This new characterization hence results from Theorem 53. The independence of the axioms in the set of complete relations results from the following examples (in appendix):

Violated axiom RC 1 i RC 2 i AC 1 i AC 3 i Maj1 i Maj2 i Example (

Characterizations of a CDR

In the last section we have shown that two different "dual" characterizations of concordance relations (Theorem 48 and Corollary 54) can be obtained using coduality. The picture is not the same for concordance-discordance relations, which are significantly more complex objects than CR. As discussed in Section 3.6, reflexes of automatic "co-dualization" must be abandoned since the co-dual of a CDR is not a CDR but a CRB (Proposition 19). Nonetheless, two characterizations of reflexive and irreflexive CDR can be obtained from previous results. With Theorem 29, we have recalled a characterization of a reflexive concordance-discordance relation (R-CDR). It involves axiom M 1 and a weakening of axiom M 2, called M 3 (see Definition 28). Examining the proof of this result in BP09a shows that the reflexivity of the relation plays no rôle, so that this characterization is valid both for reflexive and irreflexive CDR's.

A similar characterization of asymmetric CDR was given in BP06, using axiom Maj1 and a weakening of Maj2, that was called Maj3. This axiom was constructed as M 3 from M 2, by adding a premise to Maj2.

In the same spirit as we introduced, in the previous section, axiom MM 1 (resp. MM 2) generalizing both M 1 and Maj1 (resp. M 2 and Maj2), we now define the new axiom MM 3 as follows.

Definition 55 (MM 3 and Maj3

) A relation R on X satisfies MM 3 i if (x i , a -i ) R (y i , b -i ) and (w i , a -i ) R (z i , b -i ) and (y i , c -i ) R (x i , d -i ) and (z i , e -i ) R (w i , f -i )                          ⇒                (y i , a -i ) R (x i , b -i ) or (z i , a -i ) R (w i , b -i ) or (z i , c -i ) R (w i , d -i ), (28) 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 . Maj3 i
is the same condition as MM 3 i except that the second conclusion has been removed. We say that R satisfies MM 3 (resp. Maj3) if it satisfies MM 3 i (resp. Maj3 i ) for all i ∈ N .

Dropping the second premise in MM 3 i yields M 3 i . Removing the second conclusion yields Maj3 i . Obviously, M 3 i (resp. Maj3 i ) entails MM 3 i . Under RC 1 i and RC 2 i , axioms M 3 i , Maj3 i and MM 3 i are equivalent as shown in the following lemma.

Lemma 56

The following implications hold:

1. MM 3 i and RC 2 i entail M 3 i , 2. MM 3 i and RC 1 i entail Maj3 i , 3. M 3 i and RC 1 i entail Maj3 i , 4. Maj3 i and RC 2 i entail M 3 i .
Under RC 1 i and RC 2 i , we have:

MM 3 i ⇔ M 3 i ⇔ Maj3 i .

Proof

The proof, similar to that of Lemma 42, is left to the reader. P

Remark 57

Note that axioms M 3 i and Maj3 i are not linked by co-duality. The co-dual counterpart of MM 3 i has not been met before. This is related with the fact that the co-dual of a CDR is not a CDR, in general, but a CRB, i.e., a concordance relation with bonus (Proposition 19). Such relations will be studied and characterized in Section 4.7.

•

We are in position to produce a new characterization result, valid for any CDR, which is the following.

Theorem 58 (Characterization of CDR)

The relation R on X is a concordance-discordance relation (CDR) iff R satisfies RC 1, RC 2, MM 1 and MM 3. These axioms are independent in the set of complete relations and in the set of asymmetric relations.

Proof

By Theorem 29, we know that a relation R that is a CDR satisfies RC 1, RC 2, M 1 and M 2. Since M 1 implies MM 1 and M 3 implies MM 3, R also satisfies MM 1 and MM 3. Conversely, if a relation R satisfies RC 1 and RC 2, then MM 1 (resp. MM 3) is equivalent to M 1 (resp. M 3) (by Lemmas 42 and 56). Hence, using Theorem 29, we have that R is a CDR.

In the class of complete relations, the following examples (in appendix) prove the independence of the axioms.

Violated axiom RC 1 i RC 2 i MM 1 i MM 3 i Example 80 77 78 83
For proving the independence of the axioms in the class of asymmetric relations, we can still use co-duality arguments for obtaining part of the required examples but not all of them. Since Examples 80 and 77 satisfy MM 1 and MM 2, their co-dual also satisfy these two properties (Lemma 43), hence they satisfy MM 3. In addition, Example (80) cd satisfies RC 2 i but not RC 1 i and conversely for Example (77

) cd . Example 83 satisfies RC 1, RC 2, MM 1, MM 2 j , for j = 1 but not MM 2 1 . Its co-dual satisfies RC 1, RC 2, MM 1 j for j = 1, MM 2, hence MM 3, but not MM 1 1 .
It thus proves the independence of MM 1 1 for asymmetric relations.

For proving the independence of MM 3, we need a new example. Example 84 is an asymmetric relation verifying RC 1, RC 2, MM 1, but not MM 3 1 . To sum up, the following examples (in appendix) prove the independence of the axioms in the class of asymmetric relations:

Violated axiom RC 1 i RC 2 i MM 1 i MM 3 i Example (80) cd (77) cd (83) cd 84 P Corollary 59 The relation R on X is a concordance-discordance relation (CDR) 1. iff R satisfies RC 1, RC 2, Maj1 and Maj3, 2. iff R satisfies RC 1, RC 2, M 1 and M 3.
Both sets of axioms are independent in the class of complete relations and in the class of asymmetric relations.

Proof

Under RC 1 and RC 2, axiom MM 1 (resp. MM 3) is equivalent to Maj1 (resp. Maj3) by Lemmas 42 and 56. Using the same lemmas also entails that, under RC 1 and RC 2, axiom M 1 (resp. M 3) is equivalent to MM 1 (resp. MM 3). The new characterizations are thus a direct consequence of Theorem 58. The independence of the axioms for complete relations as well as for asymmetric relations is established by the same examples as in Theorem 58, except in one case. For complete relations, in order to prove the independence of RC 1 from the other axioms in the second characterization, we need to invoke Example 79, which is a complete relations satisfying RC 2, M 1, M 3 and RC 1 j for j = 1, but not RC 1 1 . P

CDR with attribute transitivity

A CDR with attribute transitivity (CDR-AT) is not just a CDR which admits a representation in which S i are semiorders. A certain relationship between S i and V i must also be verified. CDR-AT have been studied in BP09a, Section 5.2. We first recall the definition of a CDR-AT and the characterization result obtained in BP09a.

Definition 60 (CDR with attribute transitivity)

A CDR with attribute transitivity (CDR-AT) is a 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.
The following is Theorem 29 in BP09a. The independence of the axioms is stated for reflexive relations.

Theorem 61

The relation R on X is a CDR-AT iff R satisfies RC 1, RC 2, AC 1, AC 2, AC 3, M 1 and M 3. These axioms are independent in the class of reflexive relations.

The question of the independence-or not-of the axioms in the class of complete relations and in the class of asymmetric relations is more delicate for CDR-AT than for CR-AT (Theorem 53) or for CDR (Theorem 58). In view of examining the independence issue for CDR-AT in a simpler way, we relax axioms M 1 and M 3 into MM 1 and MM 3 respectively. In view of Lemmas 42 and 56, it is clear that axioms RC 1, RC 2, AC 1, AC 2, AC 3, MM 1 and MM 3 yield another characterization of CDR-AT. In the class of complete relations, this set of axioms, although weaker than those used in Theorem 61, are not independent as attested by Proposition 74 in Appendix. Similarly, Proposition 76 in Appendix shows that, if R is a relation (that may not be complete or asymmetric) on X satisfying RC 2, AC 1, AC 2, AC 3, Maj1 and Maj3, then it also satisfies RC 1. These are other cases of asymmetry in our results for which we do not presently have a clear explanation.

Concordance relations with bonus

We know that the co-dual of a CDR is a CRB, i.e., a concordance relation with bonus (Definition 18) by Proposition 19. Starting from the characterization of a CDR given in Theorem 58, we can easily derive a characterization of a CRB using contraposition and co-duality.

Lemmas 31 and 43 entail that the co-dual of a CDR is a relation that satisfies RC 1, RC 2, MM 2 and an axiom that is obtained from MM 3 by using contraposition and co-duality. We call the latter DMM 3 and define it below.

Definition 64 (Axiom

DMM 3) A relation R on X satisfies DMM 3 i if (x i , a -i ) R (y i , b -i ) and (z i , a -i ) R (w i , b -i ) and (z i , c -i ) R (w i , d -i )                ⇒                          (y i , a -i ) R (x i , b -i ) or (w i , a -i ) R (z i , b -i ) or (x i , c -i ) R (y i , d -i ) or (z i , e -i ) R (w i , f -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 . We say that R satisfies DMM 3 if it satisfies DMM 3 i for all i ∈ N .
Note that dropping the second conclusion of DMM 3 i yields an axiom that is the "co-dual" of M 3 i and which we call DM 3 i . In a similar way, dropping the second premise of DMM 3 i yields an axiom that is the "co-dual" of Maj3 i and which we shall call DMaj3 i . We note these results in the following lemma.

Lemma 65

The relation R on

X satisfies MM 3 i (resp. M 3 i , Maj3 i ) iff its co-dual R cd satisfies DMM 3 i (resp. DM 3 i , DMaj3 i ).
Comparing DMM 3 i with MM 1 i , we observe that the former only differ from the latter by an additional conclusion. We thus have the following.

Lemma 66

If the relation R on X satisfies MM 1 i then it satisfies DMM 3 i .

As compared with MM 1 i , DMM 3 i offers a fourth possible conclusion, which interprets, under RC 1 i and RC 2 i , as the possible existence of a "preference difference" (z i , w i ) on attribute i that is "so large" that we always have (z i , e -i ) R (w i , f -i ) whatever the levels e -i and f -i on the other attributes can be. Such a large difference of preference was called a bonus in Section 3.6. This interpretation is established in the next lemma.

Lemma 67

Let R be a binary relation on X. If R satisfies RC 1 i , RC 2 i and DMM 3 i , then, for all x i , y i , z i , w i , r i , s i ∈ X i , if (z i , w i ) * i (x i , y i ) * i (y i , x i ), we then have:

1. (z i , w i ) * i (r i , s i ), 2. (z i , e -i ) R (w i , f -i ), for all e -i , f -i ∈ X -i . Proof If (z i , w i ) * i (x i , y i ) * i (y i , x i ), there are a -i , b -i , c -i , d -i ∈ X -i , such that (i) (x i , a -i ) R (y i , b -i ), (ii) Not[(y i , a -i ) R (x i , b -i )], (iii) (z i , c -i ) R (w i , d -i ) and (iv) Not[(x i , c -i ) R (y i , d -i )].
Applying RC 1 i to (i) and (iii), and taking (iv) into account yields (v) (z i , a -i ) R (w i , b -i ). Since (i), (iii) and (v) match the premises of DMM 3 i , we get one of the four possible conclusions. The first and the third one are in contradiction with (ii) and (iv). Due to RC 2 i and Lemma 22.2, we obtain that (y i , x i ) * i (w i , z i ). From this and (ii) we deduce that the third conclusion is not true. The only remaining possibility is thus the fourth conclusion of DMM 3 i , which establishes the second part of the lemma and implies the first part. P

Starting from Theorem 58 and considering a relation R that is the co-dual of a CDR, we obtain directly the following characterization of a CRB.

Theorem 68 (Characterization of CRB)

The relation R on X is a CRB iff it satisfies RC 1, RC 2, MM 2 and DMM 3. These axioms are independent both in the class of complete and in the class of asymmetric relations.

Proof

This result is a direct consequence of two facts:

• by definition, the co-dual of a CRB is a CDR and conversely,

• R satisfies RC 1, RC 2, MM 2 and DMM 3 iff its co-dual R cd satisfies RC 1, RC 2, MM 1 and MM 3 (Lemmas 31, 43 and 65).

Examples showing the independence of the axioms are obtained by taking the codual of those used in the proof of Theorem 58 to show the independence of the axioms characterizing a CDR. P

Corollary 69

The relation R on X is a CRB 1. iff it satisfies RC 1, RC 2, M 2 and DM 3, 2. iff it satisfies RC 1, RC 2, Maj2 and DMaj3.

These two families of axioms are independent both in the class of complete and in the class of asymmetric relations.

Proof

These characterizations, as well as the independence of the axioms, result from Theorem 29 and Corollary 59 respectively, by the same argument as we used to prove Theorem 68 starting from Theorem 58. P

CRB with attribute transitivity

The co-dual of a CDR-AT is a CRB with attribute transitivity (CRB-AT), i.e., a CRB which satisfies AC 1, AC 2 and AC 3 since the first two axioms are cross co-dual and the latter is self co-dual (Lemma 50). In view of Proposition 19, and its proof, the co-dual of a CDR, R, having a type I representation ¤, S i , V i , is a CRB having a type I representation which is ¤ cd , S i , V i , with the same relations S i , V i as for R . If it happens that R is a CDR-AT, S i , V i form an homogeneous chain of semiorders as defined in Section 2. These properties are thus inherited by the co-dual of R, which prompts the following definition of a CRB-AT.

Definition 70 (CRB with attribute transitivity)

A CRB with attribute transitivity (CRB-AT) is a CRB 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 an homogeneous chain of semiorders.

We obtain a characterization of a CRB-AT from that of a CDR-AT, by co-duality arguments. This yields the following theorem, which is similar to Theorem 62

Proof

The proof of this theorem obtains from that of Theorem 62 by co-duality arguments. In particular, the co-dual of the examples used to prove the independence of the axioms in the three cases considered in Theorem 62 can be used here in the co-dual case. We emphasize that co-duality transforms complete relations into asymmetric ones and conversely. P

Remark 72

The independence result in the class of irreflexive relations (Part 1 of Theorem 71) is not semantically attractive in a preference modelling context, since strict preference relations are not only irreflexive but also asymmetric. The relevant result for strict preference relations is contained in Part 2 of Theorem 71. For non-strict preference relations, which are just supposed to be reflexive, Part 3 is the relevant result, since independence in the class of complete relations entails independence in the larger class of reflexive relations.

•

Remark 73

Remark 63 can be transposed by co-duality to yield alternative characterizations of CRB-AT. In particular, for asymmetric CRB-AT, independent characterizations are obtained by substituting MM 2 by M 2 or by Maj2 and/or DMM 3 by DM 3 or by DMaj3 in the characterization of asymmetric CDR-AT given in the previous theorem. For complete CRB-AT, the following sets of axioms constitute independent characterizations:

• RC 1, RC 2, AC 1, AC 2, AC 3, Maj2 and DM 3,

• RC 1, RC 2, AC 1, AC 2, AC 3, M 2 and DM 3.

•

Conclusion

From the present research and a series of previous papers investigating outranking relations, we draw the following lessons.

1. It is possible to analyze concordance relations and concordance-discordance relations, both reflexive (such as in Electre) and asymmetric (such as in Tactic), in the framework and with the classical tools of conjoint measurement.

2. This research has illustrated the interest of an axiomatic analysis by showing (a) that new models (namely, concordance relations with bonus) can be defined and characterized just by using such a simple transformation as co-duality, (b) that new characterizations of known models can be obtained using such a transformation, (c) that axiomatic analysis allows us to present a corpus of models (reflexive and asymmetric outranking relations) in a unified framework and to better understand their inter-relations.

Co-duality has played an important rôle in our analysis. While the co-dual of a concordance relation is a concordance relation, it is no longer the case as soon as vetoes come into play.

A noticeable product of our investigation using co-duality is the observation that the asymmetric part of a reflexive concordance-discordance relation is not a concordance-discordance relation since it involves both veto and bonus effects. Knowing the properties of such relations (i.e., the asymmetric part of a reflexive concordance discordance relation) is of importance since they are used in some multi-criteria sorting methods, namely the optimistic version of the Electre Tri method (Roy and Bouyssou, 1993, p. 391. This version is also known as "pseudodisjunctive"). The pessimistic version of this method (also known as "pseudoconjunctive") is well-understood (it is characterized in Bouyssou andMarchant, 2007a,b, S lowiński et al., 2002) and methods for learning its parameters on the basis of assignment examples were developed since 1998 (see, e.g., [START_REF] Leroy | Learning the parameters of a multiple criteria sorting method[END_REF], Mousseau and S lowiński, 1998, Mousseau et al., 2006). It is not the case with the optimistic version. No axiomatic characterization is known. A method for learning its parameters was recently proposed (Zheng et al., 2011(Zheng et al., , 2014)). The recent interest for this method in applications (Metchebon Takougang et al., 2014) motivates further investigation (see [START_REF] Bouyssou | On the relations between ELECTRE TRI-B and ELEC-TRE TRI-C and on a new variant of ELECTRE TRI-B[END_REF]. For lack of place, an axiomatic characterization of the asymmetric part of a concordancediscordance relation was not included in the present paper. This is dealt with in BP14.

In closing, two brief remarks on possible additional developments arising from the present analysis.

With the idea of bonus, some light was shed on what could be called an optimistic counterpart of the notion of veto. The notion of bonus could make sense in practical situations. Indeed, taking for granted that the usual outranking concept is relevant for modeling preferences in certain cases, the notion of bonus naturally comes into play in the asymmetric part of the traditional non-strict outranking relations as it became apparent in our analysis. Alternative outranking models could thus consider the possibility of bonuses instead of vetoes.

Another interesting issue is related to recent work by [START_REF] Bisdorff | On the bipolar foundation of the outranking concept[END_REF][START_REF] Bisdorff | On polarizing outranking relations with large performance differences[END_REF]. This author adopts a logicist and argumentative viewpoint in his interpretation of outranking. This is in line with the usual presentation of the outranking concept according to which alternative x outranks alternative y if there are enough reasons for asserting that x is at least as good as y while there is no reason that strongly opposes this assertion (Roy, 1991). R. Bisdorff starts with the same observation that we made in Remark 9: for preferences that are not complete relations, their co-dual is not their asymmetric part, hence the interpretation of the co-dual as the "better than" relation corresponding to the preference viewed as an "at least as good" relation is impaired. In order to restore this relationship viewed as essential in the framework of an argumentative interpretation of outranking relations, R. Bisdorff uses a bipolar representation of concordance and discordance relations (on a [-1, 1] scale, with 0 playing the special rôle of coding contradictory information). He proposes an adapted definition of an outranking relation, which restores the identity of the co-dual and the asymmetric part of the relation.

The latter remarks show that new and interesting models of preference can be developed in the spirit of the classical outranking relations by combining ingredients such as concordance, vetoes and bonuses, in a way that preserves intuitively appealing properties. The usefulness of such models for representing actual preferences in practical applications has yet to be investigated.

Appendices A Propositions 74 and 76

Proposition 74 If R is a complete binary relation on X satisfying RC 2, AC 1, AC 2, AC 3, MM 1 and MM 3, then R satisfies RC 1.

For proving this proposition, we need the following lemma.

Lemma 75

Let R be a binary relation on X satisfying RC 2 i , AC 1 i , AC 2 i , AC 3 i and Maj1 i , on some attribute i. Consider four levels x, y, z, w ∈ X i such that the pairs (x, y) and (z, w) are not comparable w.r.t. the relation * i , which we denote by (x, y) (z, w)). The relative positions of these pairs and the opposite pairs are as follows:

1. [(y, x) ∼ * i (w, z)] * i [(x, y) (z, w)], 2. furthermore, one of the following configurations holds true: w). In the above, the notation [(x, y) (z, w)] means that the incomparable pairs [(x, y) and (z, w) have the same relationships with the other pairs listed.

(a) [(y, z) ∼ * i (y, x) ∼ * i (w, z)] * i [(x, y) (z, w)] * i (z, y) (b) [(w, x) ∼ * i (y, x) ∼ * i (w, z)] * i [(x, y) (z, w)] * i (x,
Proof (of Lemma 75) 1. Let x, y, z, w ∈ X i be such that the pairs (x, y) and (z, w) are incomparable w.r.t. relation * i , i.e., we have:

Not[(x, y) * i (z, w)] and Not[(z, w) * i (x, y)]. ( 30
)
In view of Definition 21, this means that there are a, b, c, d ∈ X -i such that: 4. (z, w) * i (y, x) is established in a similar way as the previous item. We thus have the following situation: (x, y) and (z, w) are incomparable differences w.r.t. * i , both are strictly preferred to (y, x) and (w, z), which are indifferent pairs. We now use AC 1 i , AC 2 i and AC 3 i . The main consequence of these axioms is that the relations + i , - i and ± i are complete (Lemma 47). Moreover, we have, for all s, t, u, v ∈ X i :

(x, c) R (y, d), Not[(z, c) R (w, d)], (z, a) R (w, b), Not[(x, a) R (y, b)], (31)
s + i t ⇒ (s, u) * i (t, u) (33) s - i t ⇒ (v, t) * i (v, s) (34)
(direct consequence of AC 1 i , AC 2 i and the definitions of + i , - i and * i ). Consider the pairs (x, y) and (z, w). We claim that there are u, v ∈ X i such that (u, v) * i (x, y) and (u, v) * i (z, w). Furthermore, (u, v) is either (x, w) or (z, y). Observe first that we cannot have: because this would imply that (x, y) and (z, w) are comparable. Our claim is thus proved with (u, v) = (x, w). If the situation was such that z ± i x and w ± i y, then we would have that (z, y) * i (z, w) and (z, y) * i (x, y). The rôle of (u, v) would be played by (z, y). Our claim is proved.

Assume first that (u, v) = (x, w). From (x, c) R (y, d) in ( 31 The case in which we assume (u, v) = (z, y) yields a similar contradiction. As a conclusion, we have established that (y, x) * i (x, y). 3. We draw the consequences of the fact that (y, x) * i (x, y), by adapting the ideas that we used in Part 2 of the present proof, under the opposite hypothesis.

The fact that (y, x)

(x, c) R (y, d) Not[(z, c) R (w, d)] (z, a) R (w, b) Not[(x, a) R (y, b)] ( 35
)
Hence R is in the conditions of application of Lemma 75. We shall assume that the configuration described in conclusion 2.(a) of the lemma holds true, i.e., we have:

[(y, z) ∼ * i (y, x) ∼ * i (w, z)] * i [(x, y) (z, w)] * i (z, y). ( 36
)
Note that case 2.(b) can be dealt with similarly. We leave it to the reader. Since R satisfies MM 3 and RC 2, it satisfies M 3 (Lemma 56.1). In the configuration described by (36), M 3 i implies that the pair (z, y) is a veto. Indeed, assume that there are e, f ∈ X -i such that (z, e) R (y, f ). We have (x, y) * i (z, y), which means there are g, h ∈ X -i such that (x, g) R (y, h) and Not [(z, g)

) R (x, b), (x, g) R (y, h), (z, e) R (y, f ), Not[(x, a) R (y, b)], Not[(z, a) R (y, b)] and Not[(z, g) R (y, h)]
, yields a contradiction with M 3 i . We thus have shown that for all e, f ∈ X -i , we have

Not[(z, e) R (y, f )] (37)
The fact that R is complete enters into play in the following way. Since R is complete, (37) entails that for all e, f ∈ X -i , we have (y, e) R (z, f ). Since (36) tells us that (y, z) ∼ * i (w, z) ∼ * i (y, x), we also have, for all e, f ∈ X -i , (w, e) R (z, f ) and (y, e) R (x, f ). In other words, (y, z), (w, z) and (y, x) are bonuses as defined in Section 3.6. The relation R induces not only a relation * i comparing pairs of levels on X i , but also a similar relation * -i on the pairs of elements of X -i . For e, f, g, h ∈ X -i , we have (e, f ) *

-i (g, h) iff, for all u, v ∈ X i , [(u, g) R (v, h)] ⇒ [(u, e) R (v, f )].
The assumption (35) also means that the pairs (a, b), (c, d) ∈ X -i × X -i are not comparable w.r.t. * -i . This relation is transitive by definition and complete iff RC 1 i holds.

If AC 1, AC 2 and AC 3 hold, we claim that there are g, h ∈ X -i with (a, b) * -i

(g, h) and (c, d) * -i (g, h). AC 1, AC 2 and AC 3 imply that ± j is a complete weak order for all j ∈ N . We define g (resp.h) by specifying its level g j (resp. h j ) for each j = i as follows: for all j = i,

g j = min {a j , c j } = a j if c j ± j a j c j if a j ± j c j (38) h j = max {b j , d j } = b j if b j ± j d j d j if d j ± j b j (39)
Starting from the trivial (a, b) * -i (a, b) and applying repeatedly ( 33) and (34), using g and h, we obtain (a, b) * -i (g, h). One proves similarly that (c, d) * -i (g, h). We finish the proof by showing that the above induces a contradiction with M 3 i . We have that Not [(x, a) The proposition below is another result, besides Proposition 74, showing that RC 1 has relationships with the other axioms even though the considered relations here are neither complete nor asymmetric.

Proposition 76

If R is a relation on X satisfying RC 2 i , AC 1 i , AC 2 i , AC 3 i , Maj1 i and Maj3 i , for some i ∈ N , then R satisfies RC 1 i .

Proof

Let us assume that R does not verify RC 1 i on some attribute i, i.e., there exist x, y, z, w ∈ X i and a, b, c, d ∈ X -i such that:

B Examples

The examples below have been checked in order to determine whether they satisfy the following axioms: RC 1, RC 2, AC 1, AC 2, AC 3, UC , LC , M 1, M 2, Maj1, Maj2, MM 1, MM 2, M 3, Maj3, MM 3, DMM 3.

Those among these axioms that are not satisfied are mentioned below next to the example label. All axioms from the previous list that are not explicitly mentioned are proved to be satisfied. By default, the examples are complete relations. Relations that are asymmetric are explicitly labeled as such, as well as relations that are neither complete nor asymmetric. Using Lemma 22, it is easy to see that RC1 and RC2 1 hold but that RC2 2 is violated. Using Lemma 8.1 and 8.2 in BP07 it is clear that U C and LC hold so that the same is true for M 1 and M 2. As a consequence of Remark 33, we have that R satisfies Maj1 and Maj2. Since M 3 (resp. Maj3) is entailed by M 2 (resp. Maj2), R also satisfies M 3 (resp. Maj3). Since R satisfies M 1 (resp. M 2) it satisfies its relaxed version MM 1 (resp. MM 2). As R satisfies M 2 it fulfills M 3 and MM 3. As R satisfies M 1 it fulfills DMM 3. Finally, using Lemma 15 in BP07, it is routine to check that we have:

• x ± 1 y, • a ± 2 b.
Hence • a ± 1 b and x ± 2 y ± 2 z.

Using Lemma 22, it is easy to check that R satisfies RC 1, RC2, AC 1, AC 2, AC 3. It is clear that U C 1 , LC 1 and LC 2 hold. U C 2 is violated since we have (x, y) * 2 (y, x) and Not[(x, y) * 2 (x, z)]. Parts 1 and 2 of Lemma 11 in BP07, show that conditions M 1 1 and M 2 hold. By Part 3 of Lemma 11 in BP07, M 1 2 cannot hold. Using Lemma 34 shows that Maj1 1 and Maj2 hold while Maj1 2 does not. Using Lemma 42 shows that MM 1 1 and MM 2 hold while MM 1 2 does not. Since R satisfies M 2 (resp. Maj2, MM 2), this implies that M 3 (resp. Maj3, MM 3) also holds. Since M 1 1 holds, DMM 3 1 holds too. We show that DMM 3 2 also holds. Assume the contrary. Taking RC 1 2 into account, this implies that there are x 2 , y 2 , z 2 , w 2 ∈ X 1 such that (z 2 , w 2 ) * 2 (x 2 , y 2 ) * 2 (y 2 , x 2 ). Hence (z 2 , w 2 ) can only be (x, z). The fourth conclusion of DMM 3 2 is always true since (u, x) R (v, z) for all u, v ∈ X 1 = {a, b}. Q

Example 79 (Not[RC 1 i , AC 2 i , LC i , Maj2 i , Maj3 1 ]) This is Example 12 in BP07. Also used in Example 24 in the same paper.

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

Not [(x, a, α 3 ) R (y, b, β 3 )], Not[(z, α 2 , p) R (w, β 2 , q)], Not[(x, α 2 , p) R (w, β 2 , q)], Not[(α 1 , a, p) R (β 1 , b, q)],

- - - × - - × × - - - × - × - × xaq - - - - - - × × - - - - - - - - xbp - - - - - - - - - - - - - × - × xbq - - - - - - - - - - - - - - - - yap - - - × - - - × - - - × - - - × yaq -
For j ∈ {2, 3}, RC 1 j , RC 2 j , AC 1 j , AC 2 j , AC 3 j , UC j and LC j are clearly satisfied, implying M 1 j and M 2 j (see Remark 26) as well as Maj1 j and Maj2 j (see Remark 33), MM 1 j and MM 2 j . On attribute 1 it is easy to check that RC 2 1 , AC 2 1 and AC 3 1 are verified while RC 1 1 and AC 1 1 are violated. Using Lemma 8(1) in BP07, we observe that UC 1 is satisfied, implying M 1 1 , Maj1 1 and MM 1 1 . LC 1 does not hold but M 2 1 does as we shall see.

Using the notation in condition (20), for establishing M 2 1 we only have to consider the cases in which (y 1 , x) = (y, x) or (y 1 , x) = (z, x) (otherwise (y 1 , x) * 1 (x, y 1 ) and consequently the first conclusion of ( 20) is satisfied). Assume that (y 1 , x) = (y, x) and that the first conclusion is not satisfied. This means that either a -1 = ap and b -1 = aq or a -1 = bp and b -1 = bq. We now distinguish two cases regarding (z i , w i ):

1. if (z i , w i ) = (z, x), the third conclusion is always satisfied because of the second premise and the fact that (z i , w i ) * 1 (y, x), 2. if (z i , w i ) = (z, x) and a -1 = ap and b -1 = aq or a -1 = bp and b -1 = bq, the second conclusion is satisfied because we have zap R xaq and zbp R xbq.

The case in which (y 1 , x) = (z, x) is dealt with similarly. Consequently, R satisfies M 2 1 , MM 2 1 , M 3 1 and MM 3 1 . For establishing that Maj2 1 does not hold, we consider the case in which (y 1 , x) = (y, x) and use the notation of ( 22) in Definition 30. In the previous analysis we only need to reconsider the case in which the second conclusion of M 2 i was used, i.e., when (z i , w i ) = (z, x) and a 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 R such that:

x R 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 (a, b) = 2, p 3 (p, p) = p 3 (q, q) = 0, p 3 (q, p) = -2.

(y, x), (y, z) or (w, z). If (s, t) = (y, z), (2) never holds true. In case (s, t) = (y, x), (1) and ( 4) imply [S = ap and T = bp] or [S = aq and T = bq]. Contradicting (5), we have (u, S) R (v, T ) for all u, v ∈ X 1 except for (u, v) = (z, y), for which (3) does not hold. The case in which (s, t) = (w, z) is dealt with similarly. As a conclusion, M 3 1 holds for R .

R violates M 2 1 . M 2 1 does not hold if we can find s, t, u, v ∈ X 1 and S, T, U, V ∈ X -1 such that: (1) (s, S) R (t, T ), (2) (t, U ) R (s, V ), (3) Not[(t, S) R (s, T )], (4) Not[(u, S) R (v, T )], (5) Not[(u, U ) R (v, V )]. These 5 conditions can be simultaneously fulfilled by setting: s = y, t = x, u = z, v = y and S = ap, T = bp, U = ap, V = aq. Since MM 2 i and RC 2 i entail M 2 i (Lemma 42.3), R violates MM 2 1 .

R violates Maj3 1 . Maj3 1 does not hold if we can find s, t, u, v ∈ X 1 and S, T, U, V, Q, R ∈ X -1 such that: (1) (s, S) R (t, T ), (2) (v, S) R (u, T ), (3) (t, U ) R (s, V ), (4) (u, Q) R (v, R), (5) Not[(t, S) R (s, T )], (6) Not[(u, U ) R (v, V )]. These 6 conditions can be simultaneously fulfilled by setting: s = y, t = x, u = z, v = w and S = ap, T = bp, U = ap, V = aq, Q = ap, R = bq. Since Maj2 i entails Maj3 i , R also violates Maj2 1 .

Since R satisfies M 1 1 (resp. M 3 1 ) it satisfies MM 1 1 (resp. MM 3 1 ). Since R satisfies MM 1 1 it satisfies DMM 3 1 (by Lemma 66). Q

  [x C(R) y and Not[y C(R) x] and x N D(R) y] or [x C(R) y and y C(R) x and x N D(R) y and Not[y N D(R) x]] .

  ) and (x, w) * i (x, y), we derive (x, c) R (w, d). Similarly, (z, a) R (w, b) and (x, w) * i (z, w) entail (x, a) R (w, b). This allows us to derive a contradiction with Maj1 i . Indeed, we have (x, c) R (w, d), (x, a) R (w, b) and (z, a) R (w, b). Using Maj1 i yields either (w, a) R (z, b) or (z, c) R (w, d). None of this conclusions holds true. The latter is false by hypothesis (see (31)) and the former cannot be true since (x, y) * i (w, z) and Not[(x, a) R (y, b)].

X

  -i such that (y, e) R (z, f ) and Not[(y, e) R (x, f )]. Since (y, x) * i (z, w) and (z, a) R (w, b), we get (y, a) R (x, b). From (y, z) * i (y, x) and (y, a) R (x, b), we derive (y, a) R (z, b). By (31), we also have Not[(x, a) R (y, b)] . The following configuration is not compatible with Maj1 i : (y, a) R (x, b), (y, a) R (z, b), (y, e) R (z, f ), Not[(x, a) R (y, b)], Not[(y, e) R (x, f )]. We

  R (y, h)]. It holds true that (y, a) R (x, b) since, by (35), (z, a) R (w, b) and, by (36), (y, x) * i (z, w). Finally, we have Not[(x, a) R (y, b)] by (35) and Not[(z, a) R (y, b)] since (x, y) * i (z, y). Gathering the relevant preferences, i.e., (y, a

  R (y, b)] entails Not[(x, g) R (y, h)] and Not[(z, c) R (w, d)] entails Not[(z, g) R (w, h)] (since a difference on X -i is substituted by a smaller one w.r.t. * -i ). Since (y, x) is a bonus, we have in particular (y, g) R (x, h). By (35), we have (x, c) R (y, d) and (z, a) R (w, b). Gathering the relevant preferences, i.e., (y, g) R (x, h), (x, c) R (y, d), (z, a) R (w, b), Not[(x, g) R (y, h)], Not[(z, g) R (w, h)] and Not[(z, c) R (w, d)], yields a contradiction with M 3 i . P

  (x, c) R (y, d) Not[(z, c) R (w, d)] (z, a) R (w, b) Not[(x, a) R (y, b)]. (40) In other words, the pairs (x, y) and (z, w) are incomparable w.r.t. relation * i . Therefore, R is in the conditions of application of Lemma 75 and we have [(y, x) ∼ * i (w, z)] * i [(x, y), (z, w)]. The latter is not compatible with Maj3 i as we shall see. Since (y, x) * i (z, w) and using (z, a) R (w, b) in (40), we obtain that (y, a) R (x, b). From (w, z) ∼ * i (y, x) and (y, a) R (x, b), we derive (w, a) R (z, b). We also directly use the four clauses in (40). The following facts contradict Maj3 i : (y, a) R (x, b), (w, a) R (z, b), (x, c) R (y, d), (z, a) R (w, b), Not[(x, a) R (y, b)] and Not[(z, c) R (w, d)]. P

Example 77 (

 77 Not[RC2 i ]) This is example 25 in BP07. Let N = {1, 2} and X = {x, y} × {a, b}. Let R on X be identical to X 2 except that, Not[(y, a) R (x, a)] and Not[(y, b) R (x, a)]. This relation is complete.It is easy to check that we have:• (x, y), (x, x), (y, y) * 1 (y, x) and• [(a, b), (b, b)] * 2 [(a, a), (b, a)].

  AC 1, AC 2 and AC 3 hold. Q Example 78 (Not[UC i , M 1 i , Maj1 i , MM 1 i ]) This is Example 33 in BP05b. Also used in the proof of Part 5 of BP07, Lemma 11 and as Example 23 in BP07.Let X = {a, b} × {x, y, z} and R on X be identical to the linear order:(a, x) R (a, y) R (a, z) R (b, x) R (b, y) R (b, z),except that (a, z) and (b, x) are indifferent: (a, z) R (b, x) and (b, x) R (a, z) both hold true. This is a complete relation.We have, abusing notation,• (a, b) * 1 [(a, a), (b, b)] * 1 (b, a) and • (x, z) * 2 [(x,x), (y, y), (z, z), (x, y), (y, z)] * 2 [(y, x), (z, x), (z, y)],

  -1 = ap and b -1 = aq or a -1 = bp and b -1 = bq. We have xap R yaq, Not[yap R xaq], xap R zaq, yap R xbp and Not[zap R xbp], which means that Maj2 1 does not hold. Since (z, x) is no veto (as we have, e.g., zap R xaq), the latter also shows that R does not satisfy Maj3 1 . Q Example 81 (Not[AC 1 i , AC 2 i ]) This is Example 36 in BP05b. Also used in Example 21 in BP07.Let X = {a, b, c, d} × {x, y}. We build R as the CR in which:• a I 1 b, a P 1 c, a I 1 d, b I 1 c, b P 1 d, c I 1 d, • x P 2 y, • {1, 2} £ ∅, {1, 2} {2}, {1, 2} {1}, {2} {1}.Therefore, R links any two elements of X except that we have:(a, x) R (c, y) but Not[(c, y) R (a, x)] and (b, x) R (d, y) but Not[(d, y) R (b, x)]. Hence R is a complete relation. Since it is a CR, it satisfies RC 1, RC 2, UC , LC , M 1, M 2, Maj1, Maj2, MM 1, MM 2, M 3, Maj3, MM 3 and DMM 3.It is easy to see that AC3 and AC1 2 as well as AC 2 2 hold.AC1 1 is violated since (d, y) R (a, x) and (c, y) R (b, x) but neither (c, y) R (a, x) nor (d, y) R (b, x). AC 2 1 is also violated (Part 1 of Lemma 27 in BP05b). Q Example 82 (Not[AC3 i ])This is Example 35 in BP05b. Also used as Example 20 in BP07. Let X = {a, b, c, d} × {x, y}. We build the CR in which:• a P 1 b, a I 1 c, a P 1 d, b I 1 c, b P 1 d, c I 1 d, • x P 2 y, • {1, 2} £ ∅, {1, 2} {2}, {1, 2} {1}, {2} {1}.Therefore, R links any two elements of X except that we have:(a, x) R (b, y) but Not[(b, y) R (a, x)], (b, x) R (d, y) but Not[(d, y) R (b, x)] and (a, x) R (d, y) but Not[(d, y) R (a, x)]. Hence R is a complete relation. Since it is a CR, it satisfies RC 1, RC 2, UC , LC , M 1, M 2, Maj1, Maj2, MM 1, MM 2, M 3, Maj3, MM 3 and DMM 3.It is easy to see that AC1 holds and, hence, AC2 (by Part 1 of Lemma 27 in BP05b). One verifies that AC3 2 holds. AC3 1 is violated since (c, y) R (a, x),(d, y) R (c, x) but neither (b, y) R (a, x) nor (d, y) R (b, x). Q Remark.The co-dual of this relation is an asymmetric relation that satisfies all axioms of a CR-AT except AC 3 1 . In particular, it satisfies M 3 and Maj3 since it satisfies M 2 and Maj2. Example 83 (Not[LC i , M 2 i , Maj2 i , MM 2 i , M 3 i , Maj3 i , MM 3 i ]) This is Example 38 in BP09b. It is used in Remark 16 in BP09a (but erroneously referred to as Example 39 in BP09b).

• Remark 4 (Concordance and non-discordance relations)

	(V (y, x) = ∅). Alternatively, an outranking relation R can be viewed as the
	intersection of two relations: a concordance relation C(R) and a non-discordance
	relation. The concordance relation C(R) is defined by x C(R) y if S(x, y) ¤ S(y, x).
	The non-discordance relation N D(R) is defined by x N D(R) y if V (y, x) = ∅.
	Hence, we have x R y iff [x C(R) y and x N D(R) y].
	Condition (7) explicitly defines an outranking relation as a relation that satisfies
	two rules: a concordance rule (S(x, y) ¤ S(y, x)) and a non-discordance rule

Remark 38 (Earlier characterization of asymmetric CR)

  34 establishes that under conditions RC 1 and RC 2, M 1 is equivalent to Maj1 and M 2 is equivalent to Maj2. As a consequence, both characterizations are valid for reflexive CR's. Using Lemma 31, this implies that both characterizations are also valid for irreflexive CR's.are two alternative characterizations of a CR. The examples used in the proof of Theorem 36 for showing that RC 1, RC 2, M 1 and M 2 are independent in the class of complete relations also show that RC 1, RC 2, Maj1 and M 2 are independent in the same class. By co-duality, this implies that RC 1, RC 2, Maj1 and M 2 are independent in the class of asymmetric relations. This means that these axioms constitute a third independent characterization of CR. In contrast, RC 1, RC 2, M 1 and Maj2 do not form an independent family of axioms, be it in the class of complete or in the class of asymmetric relations, as implied by Lemma 35. We have no simple explanation for this asymmetry. We conjecture that it is linked to the fact that the respective rôles of RC 1 and of RC 2 are not symmetric in our analysis.

	4. We know (Theorem 27) that axioms RC 1, RC 2, M 1 and M 2 (first charac-
	terization) are independent in the class of complete relations. The following
	examples (the same as for Theorem 27) show their independence. Each ax-
	iom is violated on a single attribute, referred to by i, and satisfied on all
	other attributes.
	Violated axiom RC 1 i RC 2 i M 1 i M 2 i
	Example	79	77	78	83
	Example	80	77	78	83
	Using co-duality, this implies that both sets of axioms are independent in
	the class of asymmetric relations.				P
	Remark 37
	For showing the independence of RC 1 in both characterizations, we need two
	different examples (we used Examples 79 and 80). It is indeed a consequence of
	Lemma 35 that there is no relation satisfying RC 2 For asymmetric relations, the properties in the third item in Theorem 36 have
	been previously shown to constitute a characterization of a concordance relation
	by a set of independent axioms (BP06, Theorem 2).		•
	Remark 39 (Other characterizations)
	In view of Lemma 34, it is clear that
	• R satisfies RC 1, RC 2, Maj1 and M 2,
	• R satisfies RC 1, RC 2, M 1 and Maj2,

The following examples (see in appendix) prove that RC 1, RC 2, Maj1 and Maj2 are also independent in the class of complete relations:

Violated axiom RC 1 i RC 2 i Maj1 i Maj2 i i , M 1 i , Maj1 i , M 2 i , Maj2 i and Not[RC 1 i ].

• • Remark 40 (Axioms UC and LC and co-duality) Since UC and LC are cross co-dual conditions (see Remark 33), the family of axioms RC 1, RC 2, UC and LC clearly offer a characterization of concordance relations within both reflexive or irreflexive relations (as well as within both complete or asymmetric relations). Unfortunately, these axioms are not independent since BP05b, Lemma 16 establishes that RC 2 i , UC i and LC i imply RC 1 i . Dropping RC 1, however, yields an independent characterization of a CR since we know (BP05b, Theorem 18) that a binary relation is a CR iff it satisfies RC 2, UC and LC . Moreover, the latter axioms are independent in the class of complete relations as attested by Examples 77, 78 and 83, in appendix. The dependence of RC 1, RC 2, UC and LC lead us to introduce axioms M 1 and M 2, which are discussed in BP07. Theorem 36 tells us that Maj1 and Maj2, introduced for characterizing asymmetric relations, can substitute M 1 and M 2, also in the case of complete relations, without hampering the independence of the axioms. •

  follows immediately from Definition 46 and from that of R cd . P The relation R on X is a concordance relation with attribute transitivity (CR-AT) iff R satisfies RC 1, RC 2, AC 1, AC 3, MM 1 and MM 2. These axioms are independent in the class of complete relations and in the class of asymmetric relations. In this characterization, AC 1 can be substituted by AC 2 without any other change.

	Theorem 53 (Characterization of CR-AT)

Proof

If R is a CR-AT, we know by Theorem 48 that it satisfies RC 1, RC 2, AC 1, AC 3,

M 1 and M 2. M 1 (resp. M 2) implies MM 1 (resp. MM 2). Conversely, if R satisfies RC 1, RC 2, AC 1, AC 3, MM 1 and MM 2, it satisfies M 1 and M 2 (Lemma 42) hence it is a CR-AT.

By Remark 49, we may substitute AC 1 by AC 2 in the characterization since, under RC 1, RC 2, M 1 and M 2, axioms AC 1 and AC 2 are equivalent.

  d denotes the dual 7 of the relation described in Example 80. In view of Lemma 51, this relation does not satisfy RC 1 1 . It satisfies AC 1 1 but not AC 2 1 . The possibility of substituting AC 1 by AC 2 and keep the independence of the axioms is shown as in Theorem 53 by taking the dual of the examples. The independence of the axioms in the set of asymmetric relations is established by taking the co-dual of the examples. P

	80) d	77	81	82	78	83
	Note that (80)

  1. The case of complete relations. The examples used in the proof of Theorem 62 for showing the independence of RC 2 i , AC 1 i , AC 2 i and AC 3 i , namely Examples 77, 85, 86 and 82, all satisfy axioms M 1, Maj1, M 3, Maj3. Examples 78 (resp. 83) showing the independence of MM 1 (resp. MM 3) satisfies neither M 1 nor Maj1 (resp. neither M 3 nor Maj3). 2. The case of asymmetric relations. In view of Proposition 76 in Appendix, RC 1 i is implied by RC 2 i , AC 1 i , AC 2 i , AC 3 i , Maj1 i and Maj3 i . It is also the case when Maj3 is substituted by M 3 (since Lemma 56.4 tells us that Maj3 i and RC 2 i entail M 3 i ). The following sets of axioms however are independent in the class of asymmetric relations: (a) RC 1, RC 2, AC 1, AC 2, AC 3, M 1 and M 3, (b) RC 1, RC 2, AC 1, AC 2, AC 3, Maj1 and M 3. The independence of these axioms results from the same examples as those used in Theorem 62 for asymmetric relations. Indeed, Examples 90, (77) cd , 88, 89 and (82) cd all satisfy MM 1, M 1, Maj1, MM 3, M 3 and Maj3. Example 87 violates not only MM 1 but also M 1 and Maj1. Example 84 violates not only MM 3 but also M 3 and Maj3. •

  Theorem 711. The relation R on X is a CRB-AT iff R satisfies RC 1, RC 2, AC 1, AC 2, AC 3, MM 2 and DMM 3. These axioms are independent in the class of irreflexive relations.2. If R is an asymmetric relation on X, it is a CDR-AT iff R satisfies RC 2, AC 1, AC 2, AC 3, MM 2 and DMM 3. These axioms are independent in the class of asymmetric relations.3. If R is a complete relation on X, it is a CDR-AT iff R satisfies RC 1, RC 2,AC 1, AC 2, AC 3, MM 2 and DMM 3. These axioms are independent in the class of complete relations.

  in other words, R does not satisfy RC 1 i .Using RC 2 i and Lemma 22.2 imply that we have (y, x) * i (w, z) and (w, z) * The former is incompatible with Maj1 i as we shall see. Note that R satisfies Maj1 i by Lemma 34.1.2. We show that assuming (x, y) * i (y, x) leads to a contradiction. From (x, y) *

	i (32) The same axiom and lemma entail that (x, y) and (y, x) are comparable w.r.t. * (y, x), yielding: (y, x) ∼ * i (w, z) i , i.e., we must have (x, y) * i (y, x) or (y, x) * (y, x), we first derive the following consequences: 1. (z, w) * i (w, z). Assuming Not[(z, w) * i (w, z)] implies, by Lemma 22.2, that (w, z) * i (z, w). Hence we would have: (x, y) * i (y, x) ∼ * i (w, z) * i (z, w). Using the transitivity of * i leads to (x, y) * i (z, w), a contradiction. The same contradiction can be derived if we suppose (z, w) ∼ * i (w, z). 2. (x, y) * i (y, x). Else, from (x, y) ∼ * i (y, x) we would derive (z, w) * i (w, z) ∼ * i (y, x) ∼ * i (x, y), from which we deduce (z, w) * i (x, y), a con-tradiction. 3. (x, y) * i (w, z). Assuming Not[(x, y) * i (w, z)] implies, by Lemma 22.2, that (y, x) * i (z, w). Hence we would have: (w, z) ∼ * i (y, x) * i (z, w). Using the transitivity of * i leads to (w, z) * i (z, w), a contradiction. The i (x, y). i same contradiction can be derived if we suppose (x, y) ∼ * i (w, z).

  i . Both are strictly preferred to (x, y) and (z, w), which are indifferent pairs.Using AC 1 i , AC 2 i and AC 3 i , we derive exactly the same consequences as in Part 2, i.e., we have either [x ±

	con-
	tradiction.
	3. (y, x) * i (z, w). Assuming Not[(y, x) * i (z, w)] implies, by Lemma 22.2,
	that (x, y) * i (w, z). Hence we would have: (x, y) * i (w, z) ∼ * i (y, x). Using
	the transitivity of * i leads to (x, y) * i (y, x), a contradiction. The same
	contradiction can be derived if we suppose (y, x) ∼ * i (z, w).
	4. (w, z) i z and y ± i w] or [z ± i x and w ± i y]. If [x ± i z and y ± i w], we conclude that (x, y) * i (z, y) and (z, w) * i (z, y).
	We can have neither (x, y) ∼ * i (z, y) nor (z, w) ∼ * i (z, y), because this would
	imply that (x, y) and (z, w) are comparable. Since we have Not[(z, y) * i (x, y)],
	we deduce that (y, z) * i (y, x), using Lemma 22.2. Having (y, z) * i (y, x) is
	impossible since this would contradict Maj1 i . Indeed, assume that there are e, f ∈

* i (x, y) entails the following: 1. (w, z) * i (z, w). Assuming Not[(w, z) * i (z, w)] implies, by Lemma 22.2, that (z, w) * i (w, z). Hence we would have: (z, w) * i (w, z) ∼ * i (y, x) * i (x, y). Using the transitivity of * i leads to (z, w) * i (x, y), a contradiction. The same contradiction arises if we suppose (z, w) ∼ * i (w, z). 2. (y, x) * i (x, y). Else, from (y, x) ∼ * i (x, y) we would derive (x, y)

∼ * i (y, x) ∼ * i (w, z) * i (z,

w)

, from which we deduce (x, y) * i (z, w), a * i (x, y) is established in a similar way as the previous item.

We thus have the following situation: (y, x) and (w, z) are incomparable differences w.r.t. *

  Since R satisfies MM 1 and RC 2, it satisfies also Maj1 (Lemma 42.2). Let us assume that R does not verify RC 1 i on some attribute i. We shall derive a contradiction from this assumption. If RC 1 i is not verified by R, there exist four levels x, y, z, w ∈ X i such that (x, y) and (z, w) are incomparable w.r.t. relation *

	have thus established that
	(y, z) ∼ * i (y, x). Starting from Not[(z, y) * i (z, w)], one proves similarly that
	(y, z) ∼ * i (w, z) and we finally have that (y, z) ∼ * i (w, z) ∼ * i (y, x). In the case in which [z ± i x and w ± i y], one proves in an analogous way
	that (x, y) * i (x, w), (z, w) * i (x, w) and (w, x) ∼ * i (y, x) ∼ * i (w, z).
	This concludes the proof of Lemma 75.	P
	Proof (of Proposition 74)

i , or, in other words, there are a, b, c, d ∈ X -i such that:

In the sequel, previous papers by the present authors will be referred by their initials, BP, followed by the year of publication and possibly a letter to distinguish different papers published the same year.

This version of the Electre I method is not the historical one (Roy, 1968), but a more "modern" version as presented in Roy andBouyssou (1993, p. 251).

Assuming the existence of constant threshold representations for these semiorders is not restrictive for finite X i(Aleskerov et al., 2007, p. 222).

When a concordance discordance (resp. concordance relation) relation is irreflexive, reflexive or asymmetric we will use the acronyms I-CDR, R-CDR and A-CDR (resp. I-CR, R-CR and A-CR) when we want to emphasize this fact.

See BP09a, p. 470, for more detail.

This characterization was given for reflexive concordance relations (R-CR), but this restriction is inessential and our characterization is valid for general CR.

By Proposition 8.1, we know that any concordance relation R is either reflexive or irreflexive. If R is reflexive, Theorem 27 establishes the first characterization. Since any irreflexive CR is the co-dual of a reflexive CR, Lemma 31 implies that the second characterization holds for irreflexive CR's.

We really mean the dual, not the co-dual.

--------------ybp ---------------ybq ---------------

This lemma was stated for reflexive relations but its proof does not depend on the reflexivity hypothesis. It is also valid for irreflexive, and a fortiori asymmetric, relations.

This lemma was stated for reflexive relations but its proof does not depend on the reflexivity hypothesis. It is also valid for irreflexive, and a fortiori asymmetric, relations.

Acknowledgments

We thank an anonymous referee and the editor for insightful comments on a previous version of this paper. These helped us to remove some ambiguities and hopefully led to a more appropriately focussed paper. The usual caveat applies.

T. Marchant. An axiomatic characterization of different majority concepts. European Journal of Operational Research, 179(1):160-173, 2007. K. O. May. Intransitivity, utility and the aggregation of preference patterns. Econometrica, 22:1-13, 1954. S. A. Metchebon Takougang, M. Pirlot, B. Some, and S. Yonkeu. Multicriteria assesment aid for degraded landscape: a case study. In R. Bisdorff, L. C. Dias, P. Meyer, V. Mousseau, and M. Pirlot, editors, Evaluation and Decison models: Applications. Springer-Verlag, Berlin, 2014. Forthcoming. B. Monjardet. Axiomatiques et propriétés des quasi-ordres. Mathématiques et Sciences Humaines, 63:51-82, 1978. V. Mousseau and R. S lowiński. Inferring an ELECTRE TRI model from assignment examples. Journal of Global Optimization, 12(2):157-174, 1998. V. Mousseau, L. C. Dias, and J. Figueira. Dealing with inconsistent judgments in multiple criteria sorting models. 4OR, 4(3):145-158, 2006. M. Pirlot. A common framework for describing some outranking procedures. Journal of Multi-Criteria Decision Analysis, 6:86-92, 1997. B. Roy. Classement et choix en présence de points de vue multiples (la méthode ELEC-TRE). RIRO, 2:57-75, 1968. B. Roy. ELECTRE III : un algorithme de classement fondé sur une représentation floue des préférences en présence de critères multiples. Cahiers du CERO, 20:3-24, 1978. B. Roy. The outranking approach and the foundations of ELECTRE methods. Theory and Decision, 31:49-73, 1991. B. Roy. Multicriteria methodology for decision aiding. Kluwer, Dordrecht, 1996. Original version in French "Méthodologie multicritère d'aide à la décision", Ed. Economica, collection Gestion, Paris, 1985. B. Roy and P. Bertier. La méthode ELECTRE II : une application au media-planning. In M. Ross, editor, OR'72, pages 291-302. North Holland, Amsterdam, 1973. B. Roy and D. Bouyssou. Aide multicritère à la décision : Méthodes et cas. Economica, Paris, 1993. R. S lowiński, S. Greco, and B. Matarazzo. Axiomatization of utility, outranking and decision-rule preference models for multiple-criteria classification problems under partial inconsistency with the dominance principle. Control and Cybernetics, 31(4):1005-1035, 2002. A. Tversky. Intransitivity of preferences. Psychological Review, 76:31-48, 1969. P. Van Acker. Transitivity revisited. Annals of Operations Research, 23:1-35, 1990. J.-C. Vansnick. On the problems of weights in MCDM (the noncompensatory approach). European Journal of Operational Research, 24:288-294, 1986. J. Zheng, V. Mousseau, M. Pirlot, and S. A. Metchebon Takougang. Eliciting preferential parameters of ELECTRE TRI method for optimistic rule. Technical report, École Centrale Paris, 2011. J. Zheng, S. A. Metchebon Takougang, V. Mousseau, and M. Pirlot. Learning criteria

Our next result is a new characterization theorem for CDR-AT, in the general case and in the case of complete and of asymmetric relations.

Theorem 62

1. The relation R on X is a CDR-AT iff R satisfies RC 1, RC 2, AC 1, AC 2, AC 3, MM 1 and MM 3. These axioms are independent in the class of reflexive relations.

2. If R is a complete relation on X, it is a CDR-AT iff R satisfies RC 2, AC 1, AC 2, AC 3, MM 1 and MM 3. These axioms are independent in the class of complete relations.

3. If R is an asymmetric relation on X, it is a CDR-AT iff R satisfies RC 1, RC 2, AC 1, AC 2, AC 3, MM 1 and MM 3. These axioms are independent in the class of asymmetric relations.

Proof

The usual argument, based on Lemmas 42 and 56 allows us to substitute M 1 by MM 1 and M 3 by MM 3 in the characterization of (general) CDR-AT provided in Theorem 61. The independence of the axioms is established by the same examples as in Theorem 61.

For complete CDR-AT, axiom RC 1 can be dropped from their characterization, in view of Proposition 74. In the class of complete relations, axioms RC 2, AC 1, AC 2, AC 3, MM 1 and MM 3 are independent as attested by the following examples: The resulting sets of axioms remain independent in the class of complete relations but this is not always the case in the class of asymmetric relations, as we shall see.

- There is a total of 25 such pairs that are marked by a cross in Table 1. It is not difficult to check that R is complete.

For i ∈ {2, 3}, it is easy to check that we have:

which shows,

• using Parts 1 and 2 of Lemma 22, that RC1 2 , RC1 3 , RC2 2 and RC2 3 hold,

• using Lemma 47, that AC 1 2 , AC 1 3 , AC 2 2 , AC 2 3 , AC 3 2 and AC 3 3 hold.

Using Parts 1 and 2 of Lemma 8 in BP07, it is easy to check that LC 2 , LC 3 , U C 2 and U C 3 hold. Hence, using Parts 3 and 4 of Lemma 11 in BP07, we know that M 1 2 , M 1 3 , M 2 2 and M 2 3 hold. Using Lemma 34, we have also Maj1 2 , Maj1 3 , Maj2 2 and Maj2 3 .

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

for all (c 1 , d 1 ) ∈ Γ = {(x, x), (x, z), (y, x), (y, y), (y, z), (y, w), (z, x), (z, y), (z, z), (w, x), (w, y), (w, z), (w, w)}. The pairs (x, w) and (z, w) are linked by ∼ * 1 . The pairs (x, y) and (x, w) are not comparable in terms of * 1 since (x, a, p) R (y, a, q) and Not [(x, a, p) R (w, a, q)], while (x, a, p) R (w, b, p) and Not [(x, a, p) R (y, b, p)]. Similarly, the pairs (x, y) and (z, w) are not comparable in terms of * 1 . This shows, using Part 1 of Lemma 22, that RC1 1 is violated.

Using Part 2 of Lemma 22, it is easy to see that RC2 1 holds. Using Part 1 of Lemma 8 in BP07, shows that U C 1 holds. Hence, using Part 3 of Lemma 11 in BP07, we know that M 1 1 holds.

In view of Part 6 of Lemma 16 in BP05b, LC 1 does not hold (since this lemma tells us that RC 2 1 , UC 1 and LC 1 entail RC 1 1 . We now check that M 2 1 holds. The two premises of M 2 1 are that (a 1 , a -1 ) R ( b 1 , b -1 ) and(b 1 , c -1 ) R (a 1 , d -1 ). The three possible conclusions of M 2 1 are that (b

Suppose first that (b 1 , a 1 ) ∈ Γ. In this case, we have (b

). Hence, the first conclusion of M 2 1 holds.

Suppose now that (b 1 , a 1 ) = (x, y).

) and the third conclusion of M 2 1 holds.

If (c 1 , d 1 ) = (x, w), it is easy to check that there are no

This shows that M 2 1 cannot be violated if (b 1 , a 1 ) = (x, y). A similar reasoning shows that M 2 1 cannot be violated if (b 1 , a 1 ) = (x, w) or if (b 1 , a 1 ) = (z, w). Hence, M 2 1 holds and so does M 3 1 .

Using Remark 33, we know that R satisfies Maj1 1 since UC i entails Maj1 i . Since R satisfies RC 2 1 , M 1 1 but not RC 1 1 , it cannot satisfy Maj2 1 , as a consequence of Lemma 35. Since R satisfies M 1 and M 2, it also satisfies MM 1, DMM 3, MM 2, M 3 and MM 3.

Maj3 2 (resp. Maj3 3 ) holds because Maj2 2 (resp. Maj2 3 ) holds but Maj3 1 is violated as shown by the following configuration (which also confirms that Maj2 1 is violated): (y, a, p) R (x, b, p), (w, a, p) R (z, a, p), (w, a, p) R (z, a, q), (z, a, p) R (w, a, p), Not[(x, a, p) R (y, b, p)], Not [(z, a, p) R (w, a, q)].

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

Hence AC 1 1 holds. Since (x, w) and (x, y) are not comparable w.r.

LC , Maj2, Maj3. It is easy to check that R is asymmetric. As for the comparison of preference differences on each attribute, we have for all (α, β)

• (p, q) * 3 [(p, p), (q, q)] * 3 (q, p).

The upward and downward dominance relations on attributes 2 and 3 are as follows:

• a ± 2 b,

On attribute 1, we have:

• y and z are not comparable w.r.

This is a complete relation. Indeed if 3 i=1 p i (x i , y i ) < 0, then p 1 (x, y 1 ) < 4. This implies that p 1 (y 1 , x) = 4, hence 3 i=1 p i (y i , x i ) ≥ 0. It is easily checked that we have (with (α, α) standing for (x, x), (y, y) and (z, z)):

This shows that RC 1, RC 2, AC 1, AC 2 and AC 3 are satisfied. Using Parts 1 of Lemma 8 and Lemma 11 in BP07 shows that U C and M 1 hold. Similarly, using Parts 2 of Lemma 8 and Lemma 11 in BP07

shows that

Hence M 2 1 is violated too. Lemma 11, Part 2, in BP07 implies that LC 1 is also violated. Using Lemmas 34, 42 and 56, we obtain that R satisfies Maj1, MM 1,

Let X = {x, y, z} × {a, b} × {p, q} and R on X be as described in Table 3: It is easy to check that R is asymmetric. It is not difficult to see that we have, abusing notation,

, and

(x, a, p) R (y, a, p), (x, a, p) R (z, a, p), (y, a, p) R (x, b, p) and (z, a, p) R (x, b, q) but neither (y, a, p) R (x, a, p) nor (z, a, p) R (x, b, p).

Since RC 1 and RC 2 hold, Lemma 34 implies that R satisfies M 1, M 2 2 , M 2 3 but not M 2 1 . M 3 2 and M 3 3 hold while M 3 1 is violated (Lemma 56). By Lemma 11 in BP07, R satisfies UC , LC 2 , LC 3 but not LC 1 . By Lemmas 42 and 56, we know that MM 2 1 and MM 3 1 are violated. MM 2 j and MM 3 j are satisfied for j = 2, 3. R satisfies MM 1 so that it also satisfies DMM 3.

From relations * i described above, we infer the following:

which implies that R satisfies AC 1, AC 2 and AC 3.

This is Example 36 in BP09b.

Let X = X 1 × X 2 with X 1 = {x, y, z, w} and X 2 = {a, b}. We build a 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,

By construction, R is a CDR. Hence, it satisfies RC 1, RC 2, M 1, Maj1, MM 1, M 3, Maj3 and MM 3 (Theorem 58 and Lemmas 42 and 56). It satisfies M 2 2 , Maj2 2 , MM 2 2 , but not M 2 1 (due to the veto on X 1 ), not Maj2 1 (by Lemma 34) and not MM 2 1 (by Lemma 42). Since R satisfies M 1 it also fulfills DMM 3. Using Lemma 11 in BP07, we get that UC and LC 2 are satisfied but LC 1 is violated.

The relation R contains all pairs in X × X except the following ones:

due to the fact that Not[∅ ¤ {1, 2}], and

One pair is common to these two series of four pairs, so that R is equal to X × X minus the seven distinct pairs in the lists above. It is a complete relation.

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:

The relation + 1 is not complete. We have z + 1 x, x + 1 y and x + 1 w but neither

It is a slight variation on Example 85 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 a 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),

• a P 2 b (and all I 2 loops) and the relation V 2 is empty,

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 an homogeneous chain 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, R is a CDR. Hence, it satisfies RC 1, RC 2, M 1, Maj1, MM 1, M 3, Maj3 and MM 3 (Theorem58 and Lemmas 42 and 56). It satisfies M 2 2 , Maj2 2 , MM 2 2 , but not M 2 1 (due to the veto on X 1 ), not Maj2 1 (by Lemma 34) and not MM 2 1 (by Lemma 42). Since R satisfies M 1 it also fulfills DMM 3. Using Lemma 11 in BP07, we get that UC and LC 2 are satisfied but LC 1 is violated.

The relation R contains all pairs in X × X except the following ones:

due to the fact that Not[∅ ¤ {1, 2}], and

One pair is common to these two series of four pairs, so that R is equal to X × X minus the seven distinct pairs in the lists above. It is clear that R is complete.

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:

Let X = {a, b} × {x, y, z} and R on X be identical to the strict linear order (abusing notation in an obvious way):

except that we have also (a, y) R (b, x).

It is easy to see that R is asymmetric. We have, abusing notation: a), and

Using Lemma 22, it is easy to check that R satisfies RC 1 and RC 2. It is clear that U C 1 , LC 1 and LC 2 hold. This implies that M 2, Maj2, MM 2, M 3, Maj3, MM 3 hold as well as M 1 1 , Maj1 1 and MM 1 1 .

Maj1 2 is violated since (a, x) R (a, y), (a, x) R (a, z), (b, x) R (a, z) but neither (a, y) R (a, x) nor (b, x) R (a, y). As a consequence, U C 1 is also violated. Since RC 1 and RC 2 hold, Lemmas 34 and 42 imply that M 1 2 and MM 1 2 are violated.

Since M 1 1 holds, DMM 3 1 holds too. We show that DMM 3 2 also holds. Assume the contrary. Taking RC 1 2 into account, this implies that there are a, b, z 2 , w 2 ∈ X 2 such that (z 2 , w 2 ) * 2 (a, b) * 2 (b, a). Hence (z 2 , w 2 ) can only be (x, z) or (y, z). The fourth conclusion of DMM 3 2 is always true since (u, x) R (v, z) and (u, y) R (v, z) for all u, v ∈ X 1 = {a, b}.

Using Lemma 47, we have:

Hence AC 1, AC 2 and AC 3 hold.

This example is an asymmetric variant of Example 85. Let X = X 1 × X 2 with X 1 = {x, y, z, w} and X 2 = {a, b}. We build a CDR on X with:

By construction, R is an asymmetric CDR. Hence, it satisfies RC 1, RC 2, M 1, Maj1, MM 1, M 3, Maj3, MM 3 (Theorem 58 and Lemmas 42 and 56). It satisfies M 2 2 but not M 2 1 (due to the veto on X 1 ), not Maj2 1 (by Lemma 42) and not MM 2 1 (by Lemma 42). Using Lemma 11 in BP07, we get that U C and LC 2 are satisfied but LC 1 is violated 8 .

Since R satisfies M 1 it verifies DMM 3. The relation R contains the following pairs in X × X:

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:

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, a) R (w, a) but Not[(w, a) R (w, a)] and (w, b) R (z, a) but Not [(y, b) R (z, a)]. This shows that AC 1 1 is violated. Condition AC 3 1 holds since + 1 and - 1 are not incompatible. Each of P • 1 and V • 1 is the asymmetric part of some semiorder but these semiorders do not form an homogeneous chain of semiorders (the weak order induced by P • 1 imposes that w is placed in the last position while that induced by V • 1 imposes the last position to y).

Q

This example is an asymmetric variant of Example 86 Let X = X 1 × X 2 with X 1 = {x, y, z, w} and X 2 = {a, b}. We build a CDR on X with:

By construction, R is an asymmetric CDR. Hence, it satisfies RC 1, RC 2, M 1, Maj1, MM 1, M 3, Maj3, MM 3 (Theorem 58 and Lemmas 42 and 56). It satisfies M 2 2 but not M 2 1 (due to the veto on X 1 ), not Maj2 1 (by Lemma 42) and not MM 2 1 (by Lemma 42). Using Lemma 11 in BP07, we get that U C and LC 2 are satisfied but LC 1 is violated 9 .

Since R satisfies M 1 it verifies DMM 3. The relation R contains the following pairs in X × X: 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: a)]. This shows that AC 2 1 is violated. Condition AC 3 1 holds since + 1 and - 1 are not incompatible. Each of P • 1 and V • 1 is the asymmetric part of some semiorder but these semiorders do not form an homogeneous chain of semiorders (the weak order induced by P • 1 imposes that w is placed in the first position while that induced by V

71

It is easy to see that R is an asymmetric relation.

As for the comparison of preference differences on each attribute, we have, for all (α, β) ∈ Γ = {(x, x), (y, y), (z, z), (w, w), (x, z), (x, w), (y, x), (y, z), (y,w), (z,x),(w, x), (w, y), (w, z)},

• (α, β) * 1 (x, y) * 1 (z, y) and (α, β) * 1 (z, w) * 1 (z, y), while (x, y) and (z, w) are incomparable in terms of * 1 ,

• (a, b) * 2 [(a, a), (b, b)] * 3 (b, a),

• (p, q) * 3 [(p, p), (q, q)] * 3 (q, p).

The upward and downward dominance relations are as follows:

• a ± 2 b,

• p ± 3 q.

RC 1 1 does not hold since the pairs (x, y) and (z, w) are not comparable w.r.t. * 1 , but RC 1 2 and RC 1 3 hold true. For j ∈ {1, 2, 3}, RC 2 j , AC 1 j , AC 2 j , AC 3 j are clearly satisfied. For j = 2 and j = 3, using Lemma 25, we see that R fulfills M 1 j and M 2 j hence it satisfies UC j and LC j (by Lemma 11 in BP07), Maj1 j and Maj2 j ( by Lemma34), UC j and LC j (by Lemma 11 in BP07), M 3 j , Maj3 j , MM 1 j , MM 2 j and MM 3 j (since each of the latter is implied by one of the previously established properties of R ).

R satisfies M 1 1 . Assume to the contrary that there are s, t, u, v ∈ X 1 and S, T, U, V ∈ X -1 such that: (1) (s, S) R (t, T ), (2) (u, U ) R (v, V ), (3) Not[(t, S) R (s, T )], (4) Not[(s, U ) R (t, V )], (5) Not[(v, S) R (u, T )]. Using (1), (3) and Lemma 22.2, we deduce that (s, t) can only be one of the pairs (y, x), (y, z) or (w, z). In all three cases, (2) and (4) cannot both hold true since (s, t) * 1 (u, v), for all u, v ∈ X 1 , a contradiction.

R satisfies Maj1 1 . Assume to the contrary that there are s, t, u, v ∈ X 1 and S, T, U, V ∈ X -1 such that: (1) (s, S) R (t, T ), (2) (u, S) R (v, T ), (3) (u, U ) R (v, V ), (4) Not[(t, S) R (s, T )], (5) Not[(s, U ) R (t, V )]. Using (1), (4) and Lemma 22.2, we deduce that (s, t) can only be one of the pairs (y, x), (y, z) or (w, z). In all three cases, (3) and ( 5) cannot both hold true since (s, t) * 1 (u, v), a contradiction.

R satisfies M 3 1 . Assume to the contrary that there are s, t, u, v ∈ X 1 and S, T, U, V, Q, R ∈ X -1 such that: (1) (s, S) R (t, T ), (2) (t, U ) R (s, V ), (3) (u, Q) R (v, R), (4) Not[(t, S) R (s, T )], (5) Not[(u, S) R (v, T )], (6) Not[(u, U ) R (v, V )]. Using (1), (4) and Lemma 22.2, we deduce that (s, t) can only be one of the pairs