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

 giving an axiomatic characterization of concordance relations. We show how the conditions used in that paper can be weakened so as to become independent from the conditions needed to characterize a general conjoint measurement model tolerating intransitive and/or incomplete relations. This leads to a clearer characterization of concordance relations within this general model.

Introduction and motivation

In [START_REF] Bouyssou | A characterization of concordance relations[END_REF] (henceforth BP05) we propose a characterization of concordance relations and discuss the importance of such a result for a thorough understanding of the so-called "outranking methods" in MCDM (see [START_REF] Roy | The outranking approach and the foundations of ELECTRE methods[END_REF][START_REF] Vincke | Multi-criteria decision aid[END_REF].

The general strategy used in BP05 is the following. Our starting point is a general model of conjoint measurement tolerating intransitive and/or incomplete relations that was introduced in [START_REF] Bouyssou | Nontransitive decomposable conjoint measurement[END_REF] (henceforth BP02). This model investigates conditions allowing to build a numerical representation of a binary relation on a product set X = n i=1 X i such as:

x y ⇔ F (p 1 (x 1 , y 1 ), p 2 (x 2 , y 2 ), . . . , p n (x n , y n )) ≥ 0, (M)

where p i are real-valued functions on X 2 i that are skew symmetric (i.e. such that p i (x i , y i ) = -p i (y i , x i ), for all x i , y i ∈ X i ) and F is a real-valued function on n i=1 p i (X 2 i ) being nondecreasing in all its arguments and such that, abusing notation, F (0) ≥ 0.

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

In BP02, we show that model (M) is, on top of the reflexivity of , essentially characterized by two conditions called RC1 and RC2. Condition RC1 expresses that, on each attribute, adequately defined preference differences can be completely ordered. Condition RC2 imposes that two opposite preference differences, i.e., (x i , y i ) and (y i , x i ), are linked.

The framework offered by model (M) is quite flexible. In particular, it includes all preference relations having a representation in the additive value function model (see [START_REF] Krantz | Additive and polynomial representations[END_REF][START_REF] Wakker | Additive representations of preferences: A new foundation of decision analysis[END_REF] or in the additive difference model (see [START_REF] Fishburn | Additive differences and simple preference comparisons[END_REF][START_REF] Tversky | Intransitivity of preferences[END_REF]. The central point in BP05 is to show that this framework is also sufficiently 1 flexible to contain all concordance relations. The underlying intuition is quite simple.

In order to compare two alternatives x and y, a concordance relation compares, in terms of importance, the coalition of attributes favoring x with the coalition of attributes favoring y. This mode of comparison has a definite ordinal flavor: it does not take into account any notion of preference difference besides what is necessary to distinguish between the attributes favoring x and those favoring y, i.e., positive, null and negative differences. Intuitively, this seems to be quite close to a relation having a representation in model (M) in which each function p i takes at most three distinct values: the sign of p i (x i , y i ) is used to know if attribute i favors x or y.

This intuition is formalized in BP05 and shown to be correct. The characterization of concordance relations proposed there amounts to adding to the conditions precipitating model (M) two additional conditions, called U C and LC, ensuring that each function p i can take at most three distinct values. The main result in BP05 (i.e. Theorem 18) says that adding to the conditions characterizing model (M) (reflexivity of , RC1 and RC2) conditions U C and LC is necessary and sufficient to characterize all concordance relations.

A weak point of this result is that these conditions interact. Indeed, the conjunction of RC2, U C and LC implies RC1 (see BP05, Lemma 16). If model (M) is to be seen as a building block allowing to understand the similarities and differences between various aggregation models proposed in the literature, such an interaction is clearly undesirable. In order to characterize concordance relations, it would be much clearer to have a result that keeps all conditions needed for model (M) and adds additional independent conditions. The purpose of this note is to do so. After having introduced our main notation and definitions in section 2, our improved characterization of concordance relations is presented in section 3. Section 4 deals with the case of concordance relations for which alternatives are compared according to a semiorder on each attribute.

Notation and Definitions

Notation

This note adheres to the, standard, terminology concerning binary relations introduced in BP05. The symbol will always denote a reflexive binary relation on a set X = n i=1 X i with n ≥ 2. Elements of X will be interpreted as alternatives evaluated on a set N = {1, 2, . . . , n} of attributes and as an "at least as good as" relation between these alternatives. The relations ≻ and ∼ are defined as usual and a similar convention will hold when is superscripted and/or subscripted. For any i ∈ N , we denote the set j =i X j by X -i . With customary abuse of notation, (x i , y -i ) will denote the element of X that is obtained from y ∈ X replacing its ith coordinate by x i ∈ X i .

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

Concordance relations

Our definition of concordance relations is identical to the one in BP05, to which we refer for motivation, examples and comments.

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

• a complete binary relation S i on each X i (i = 1, 2, . . . , n),
• a binary relation ☎ between subsets of N having N for union that is monotonic w.r.t. inclusion, i.e. for all A, B, C, D ⊆ N such that A ∪ B = N and C ∪ D = N ,

[A ☎ B, C ⊇ A, B ⊇ D] ⇒ C ☎ D, (1)
such that, for all x, y ∈ X,

x y ⇔ S(x, y) ☎ S(y, x),

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

We say that ☎, S i is a representation of .

Hence, when is a CR, the preference between x and y only depends on the subsets of attributes favoring x or y in terms of the complete relation S i . It does not depend on preference differences between the various levels on each attribute besides the distinction between levels indicated by S i .

3 Concordance relations without attribute transitivity

Background

We briefly recall here the main conditions and results presented in BP05 in order to characterize CR.

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

RC1 i if (x i , a -i ) (y i , b -i ) and (z i , c -i ) (w i , d -i )    ⇒    (x i , c -i ) (y i , d -i ) or (z i , a -i ) (w i , b -i ), RC2 i if (x i , a -i ) (y i , b -i ) and (y i , c -i ) (x i , d -i )    ⇒    (z i , a -i ) (w i , b -i ) or (w i , c -i ) (z i , d -i ), for all x i , y i , z i , w i ∈ X i and all a -i , b -i , c -i , d -i ∈ X -i . We say that satisfies RC1 (resp. RC2) if it satisfies RC1 i (resp. RC2 i ) for all i ∈ N .
The interpretation of conditions RC1 and RC2 is made easier considering their consequences on relations comparing preference differences on each attribute induced by .

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

x i , y i , z i , w i ∈ X i , (x i , y i ) * i (z i , w i ) ⇔ [for all a -i , b -i ∈ X -i , (z i , a -i ) (w i , b -i ) ⇒ (x i , a -i ) (y i , b -i )], (x i , y i ) * * i (z i , w i ) ⇔ [(x i , y i ) * i (z i , w i ) and (w i , z i ) * i (y i , x i )].
The definition of * i suggests that (x i , y i ) * i (z i , w i ) can be interpreted as saying that the preference difference between x i and y i is at least as large as the preference difference between z i and w i . The definition of * i does not imply that the two "opposite" differences (x i , y i ) and (y i , x i ) are linked. This is at variance with the intuition concerning preference differences and motivates the introduction of the relation * * i . By construction, * i and * * i are always reflexive and transitive. Condition RC1 is equivalent to requiring that any two preference differences are comparable in terms of * i . Condition RC2 imposes a "mirror effect" on the comparison of preference differences. This is summarized in the following:

1. RC1 i ⇔ [ * i is complete]. 2. RC2 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. [RC1 i and RC2 i ] ⇔ [ * * i is complete]. 4.
In the class of reflexive relations, RC1 and RC2 are independent conditions.

Remark 5. If, for all z -i , w -i ∈ X -i , [(x i , z -i ) (x i , w -i ), for some x i ∈ X i ] implies [(y i , z -i ) (y i , w -i ), for all y i ∈ X i ],
we say that is independent for N \{i}. We say that is independent if it is independent for N \{i}, for all i ∈ N . It is easy to see (see BP02, Lemma 2) that condition RC2 i implies that is independent for N \ {i}.

•

For finite or countably infinite sets, conditions RC1 and RC2 together with reflexivity allow to characterize model (M). We have:

Theorem 6 (BP02, Theorem 1). Let be a binary relation on

X = n i=1 X i . If, for all i ∈ N , X 2 i /∼ * *
i is finite or countably infinite then has a representation (M) if and only if (iff ) it is reflexive and satisfies RC1 and RC2.

The additional conditions used in BP05 to capture concordance relations are as follows:

Definition 7 (Conditions U C and LC). Let be a binary relation on a set X = n i=1 X i . This relation is said to satisfy:

U C i if (x i , a -i ) (y i , b -i ) and (z i , c -i ) (w i , d -i )    ⇒    (y i , a -i ) (x i , b -i ) or (x i , c -i ) (y i , d -i ), LC i if (x i , a -i ) (y i , b -i ) and (y i , c -i ) (x i , d -i )    ⇒    (y i , a -i ) (x i , b -i ) or (z i , c -i ) (w i , d -i ), for all x i , y i , z i , w i ∈ X i and all a -i , b -i , c -i , d -i ∈ X -i . We say that satisfies U C (resp. LC) if it satisfies U C i (resp. LC i ) for all i ∈ N .
As announced earlier, the main rôle of conditions U C i and LC i is to limit the number of distinct equivalence classes of * i and, hence, * * i . More precisely, condition U C i says that if a preference difference (x i , y i ) is not smaller than its opposite (y i , x i ), then it is the largest possible preference difference. Condition LC i has a dual interpretation. This is summarized in:

1. U C i ⇔ [Not[ (y i , x i ) * i (x i , y i ) ] ⇒ (x i , y i ) * i (z i , w i ), for all x i , y i , z i , w i ∈ X i ]. 2. LC i ⇔ [Not[ (y i , x i ) * i (x i , y i ) ] ⇒ (z i , w i ) * i (y i , x i ), for all x i , y i , z i , w i ∈ X i ]. 3. [RC2 i , U C i and LC i ] ⇒ RC1 i . 4. [RC2 i , U C i and LC i ] ⇒ [ * *
i has at most three equivalence classes]. 5. In the class of reflexive relations, RC2, U C and LC are independent conditions.

The characterization of concordance relations in BP05 is as follows:

Theorem 9 (BP05, Theorem 18). Let be a binary relation on X = n i=1 X i . Then is a CR iff it is reflexive and satisfies RC2, U C and LC.

As argued above, a weakness of this result is that it does not use condition RC1, whereas this condition is needed to characterize model (M). It would be much clearer to weaken conditions U C and/or LC in such a way that they become independent from RC1 and RC2. This is done below.

Results

Our sharper characterization of concordance relations is based on the following two conditions inspired by the work of [START_REF] Bouyssou | An axiomatic approach to noncompensatory sorting methods in MCDM, I: The case of two categories, working paper[END_REF] in the area of sorting models in MCDM.

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

M 1 i if (x i , a -i ) (y i , b -i ) and (z i , c -i ) (w i , d -i )    ⇒            (y i , a -i ) (x i , b -i ) or (w i , a -i ) (z i , b -i ) or (x i , c -i ) (y i , d -i ), M 2 i if (x i , a -i ) (y i , b -i ) and (y i , c -i ) (x i , d -i )    ⇒            (y i , a -i ) (x i , b -i ) or (z i , a -i ) (w i , b -i ) or (z i , c -i ) (w i , d -i ), for all x i , y i , z i , w i ∈ X i and all a -i , b -i , c -i , d -i ∈ X -i .
We say that M 1 (resp. M 2) holds if M 1 i (resp. M 2 i ) holds for all i ∈ N .

Condition M 1 i weakens condition U C i by adding a possible conclusion to it. Condition M 2 i is obtained similarly from LC i . The interpretation of these two new conditions is similar to the one of U C i and LC i : their aim is to drastically limit the possibility of distinguishing several classes of preference differences on each attribute. We have:

Lemma 11.

1. U C i ⇒ M 1 i . 2. LC i ⇒ M 2 i . 3. [RC2 i and M 1 i ] ⇒ U C i .
4. [RC1 i and M 2 i ] ⇒ LC i .

5. In the class of reflexive relations, RC1 i , RC2 i , M 1 i and M 2 i are independent conditions.

Proof.

Parts 1 and 2 follow from the definitions. Part 3. Suppose that (x i , a

-i ) (y i , b -i ) and (z i , c -i ) (w i , d -i ). If Not[ (w i , a -i ) (z i , b -i ) ], M 1 i implies either (y i , a -i ) (x i , b -i ) or (x i , c -i ) (y i , d -i ), as required by U C i . Otherwise if (w i , a -i ) (z i , b -i ), RC2 i and (z i , c -i ) (w i , d -i ) imply (y i , a -i ) (x i , b -i ) or (x i , c -i ) (y i , d -i ), the desired conclusion. Part 4. Suppose that (x i , a -i ) (y i , b -i ) and (y i , c -i ) (x i , d -i ). If Not[ (z i , a -i ) (w i , b -i ) ], M 2 i implies either (y i , a -i ) (x i , b -i ) or (z i , c -i ) (w i , d -i ), as required by LC i . Otherwise if (z i , a -i ) (w i , b -i ), RC1 i and (y i , c -i ) (x i , d -i ) imply either (y i , a -i ) (x i , b -i ) or (z i , c -i ) (w i , d -i
), the desired conclusion.

Part 5. Example 32 in BP05 shows that there are reflexive relations on X satisfying RC1, LC, U C, RC2 j for all j = i, but violating RC2 i . In view of Parts 1 and 2, we know that conditions M 1 and M 2 hold. Similarly, Example 33 in BP05 shows that there are reflexive relations on X satisfying RC1, RC2, LC, U C j for all j = i, but violating U C i . In view of Parts 1 and 2, we know that conditions M 1 and M 2 hold. Finally, Example 34 in BP05, shows that there are reflexive relations on X satisfying RC1, RC2, U C, LC j for all j = i, but violating LC i . Since U C holds, Part 1 implies that M 1 also holds. Since LC j holds, for all j = i, Part 2 implies that M 2 j holds, for all j = i. Since RC1 i holds and LC i is violated, Part 4 implies that M 2 i is violated. The following example completes the proof.

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

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

[(y i , x i ), (x i , x i ), (y i , y i )] ≻ * i (x i , y i ), which shows, using Parts 1 and 2 of Lemma 4 that RC1 2 , RC1 3 , RC2 2 and RC2 3 hold. Using Parts 1 and 2 of Lemma 8, it is easy to check that LC 2 , LC 3 , U C 2 and U C 3 hold. Hence, using Parts 1 and 2 of Lemma 11, we know that M 1 2 , M 1 3 , M 2 2 and M 2 3 hold.

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

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

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

It remains to check that M 2 1 holds. The two premises of M 2 1 are that (a 1 , a -1 ) (b 1 , b -1 ) and (b 1 , c -1 ) (a 1 , d -1 ). The three possible conclusions

of M 2 1 are that (b 1 , a -1 ) (a 1 , b -1 ) or (c 1 , a -1 ) (d 1 , b -1 ) or (c 1 , c -1 ) (d 1 , d -1 ).
Suppose first that (b 1 , a 1 ) ∈ Γ. In this case, we have (b

1 , a 1 ) * 1 (a 1 , b 1 ), so that (a 1 , a -1 ) (b 1 , b -1 ) implies (b 1 , a -1 ) (a 1 , b -1
). Hence, the first conclusion of M 2 1 holds.

Suppose now that (b 1 , a 1 ) = (x 1 , y 1 ). If (c 1 , d 1 ) is distinct from (x 1 , w 1 ) and (z 1 , w 1 ), we have (c

1 , d 1 ) * 1 (x 1 , y 1 ), so that (b 1 , c -1 ) (a 1 , d -1 ) implies (c 1 , c -1 ) (d 1 , d -1
) and the third conclusion of M 2 1 holds. If (c 1 , d 1 ) = (x 1 , w 1 ), it is easy to check that there are no a

-1 , b -1 ∈ X -1 such that (y 1 , a -1 ) (x 1 , b -1 ), (x 1 , a -1 ) (y 1 , b -1 ) and (x 1 , a -1 ) (w 1 , b -1 ), so that no violation of M 2 1 is possible in this case. Since (x 1 , w 1 ) ∼ * 1 (z 1 , w 1 ), the same is true if (c 1 , d 1 ) = (z 1 , w 1 ). This shows that M 2 1 cannot be violated if (b 1 , a 1 ) = (x 1 , y 1 ). A similar reasoning shows that M 2 1 cannot be violated if (b 1 , a 1 ) = (x 1 , w 1 ) or if (b 1 , a 1 ) = (z 1 , w 1 ). Hence, M 2 1 holds. ✷
Combining Lemma 11 with Theorem 9 proves the main result of this section:

Theorem 13. Let be a binary relation on X = n i=1 X i . Then is a CR iff it is reflexive and satisfies RC1, RC2, M 1 and M 2. In the class of reflexive relations, conditions RC1, RC2, M 1 and M 2 are independent.

Compared to Theorem 9, the above result keeps all of reflexivity, RC1 and RC2. Hence, it shows exactly what must be added to the conditions characterizing model (M) in order to obtain the class of all concordance relations. This gives credit to interpreting model (M) as a building block allowing to understand the similarities and differences between several aggregation models. The central rôle of model (M) was already stressed in BP02 in which we analyzed what has to be added to it to obtain the additive value function model (a similar analysis was done in [START_REF] Bouyssou | Additive difference' models without additivity and subtractivity[END_REF] for the additive difference model).

There is however a price to pay for this sharper result: condition M 1 (resp. M 2) is slightly more complex than condition U C (resp. LC) and may be more difficult to test in practice.

Concordance relations with attribute transitivity 4.1 Background

Our definition of CR does not require the relations S i to possess any remarkable property besides completeness. This is at variance with what is done in most ordinal aggregation methods, as shown in BP05.

In BP05, we showed how to characterize CR in which all relations S i are semiorders. Our analysis was based on [START_REF] Bouyssou | Additive difference' models without additivity and subtractivity[END_REF] (henceforth BP04) in which we study binary relations that can be represented in the following specialization of model (M):

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

In order to characterize model (M*), three new conditions are needed.

Definition 14 (Conditions AC1, AC2 and AC3). We say that satisfies:

AC1 i if x y and z w    ⇒    (z i , x -i ) y or (x i , z -i ) w, AC2 i if x y and z w    ⇒    x (w i , y -i ) or z (y i , w -i ), AC3 i if z (x i , a -i ) and (x i , b -i ) y    ⇒    z (w i , a -i ) or (w i , b -i ) y,
for all x, y, z, w ∈ X, all a -i , b -i ∈ X -i and all x i , w i ∈ X i . We say that satisfies AC1 (resp. AC2, AC3) if it satisfies AC1 i (resp. AC2 i , AC3 i ) for all i ∈ N .

The rôle of these conditions is to introduce a linear arrangement of the elements of X i and is detailed in BP04. We summarize their main consequences below.

Lemma 15 (BP04, Lemma 4).

1. AC1 i ⇔ [Not[ (y i , z i ) * i (x i , z i ) ] ⇒ (x i , w i ) * i (y i , w i )]. 2. AC2 i ⇔ [Not[ (z i , x i ) * i (z i , y i ) ] ⇒ (w i , y i ) * i (w i , x i )], 3. AC3 i ⇔ [Not[ (x i , z i ) * i (y i , z i ) ] ⇒ (w i , x i ) * i (w i , y i )] ⇔ [Not[ (z i , x i ) * i (z i , y i ) ] ⇒ (x i , w i ) * i (y i , w i )], for all x i , y i , z i , w i ∈ X i .
The conjunction of the above three conditions together with the conditions needed to characterize model (M) gives necessary and sufficient conditions for model (M*) when X is at most countably infinite. We have:

Theorem 16 (BP04, Theorem 2 and Table 2). Let be a binary relation on a finite or countably infinite set X = n i=1 X i . Then has a representation (M*) if and only if it is reflexive and satisfies RC1, RC2, AC1, AC2 and AC3. In the class of reflexive relations, conditions RC1, RC2, AC1, AC2 and AC3 are independent.

Our main result in BP05 concerning CR in which all relations S i are semiorders is as follows:

Theorem 17 (BP05, Theorem 28 and Lemma 27). Let be a binary relation on X = n i=1 X i . Then is a CR having a representation ☎, S i in which all S i are semiorders iff it is reflexive and satisfies RC2, U C, LC, AC1 and AC3. In the class of reflexive binary relations satisfying RC2, U C and LC, conditions AC1 and AC3 are independent.

As in section 3, a weakness of this result is that it does not use condition RC1 which is central in order to obtain model (M*). An additional weakness is that it does not show that all conditions used are independent but only that conditions AC1 and AC3 are independent in the class of reflexive relations satisfying RC2, U C and LC. We show below how this can be improved.

Remark 18. Notice that Theorem 17, contrary to Theorem 16, does not use condition AC2. Indeed, we show in BP05, Lemma 27, that, for reflexive relations satisfying RC2, U C and LC, conditions AC1 i and AC2 i become equivalent. This is due to the strong constraints on the relation * i introduced by conditions U C i and LC i . In view of Lemma 11 above, there is therefore no hope to keep all of AC1, AC2 and AC3 in a result that would characterize CR in which all relations S i are semiorders if we also want to keep all conditions needed to characterize CR, i.e., reflexivity, RC1, RC2, M 1 and M 2. We simply show below that, replacing the conjunction of RC2, U C and LC by the conjunction of RC1, RC2, M 1 and M 2 allows to obtain a result similar to Theorem 17 in which all conditions are independent.

•

Results

We have:

Lemma 19. In the class of reflexive relations, conditions RC1, RC2, M 1, M 2, AC1 and AC3 are independent.

Proof.

We provide below the six required examples.

Example 20 (RC1, RC2, M 1, M 2, AC1, AC3 j for all j = i, Not[ AC3 i ]).

In

= i, Not[ RC2 i ]). Let N = {1, 2} and X = {x 1 , y 1 } × {x 2 , y 2 }. Let on X be identical to X 2 except that, (y 1 , x 2 ) (x 1 , x 2 ) and (y 1 , y 2 ) (x 1 , x 2 ).
It is easy to check that we have:

• (x 1 , y 1 ), (x 1 , x 1 ), (y 1 , y 1 ) ≻ * 1 (y 1 , x 1 ) and • [(x 2 , y 2 ), (y 2 , y 2 )] ≻ * 2 [(x 2 , x 2 ), (y 2 , x 2 )]. Using, Lemma 4, it is easy to see that RC1 and RC2 1 hold but that RC2 2 is violated. Using Lemma 8 it is clear that U C and LC hold so that the same is true for M 1 and M 2. Finally, using Lemma 15, it is routine to check that AC1 and AC3 hold. ✷

Combining Theorem 17 with Lemmas 11 and 19 proves the main result of this section:

RC1 i , this implies (z i , z i ) ≻ * i (z i , w i ). Using AC3 i and Lemma 15, Not[ (z i , w i ) * i (z i , z i ) ] implies (w i , a i ) * i (z i , a i ), for all a i ∈ X i , so that, in particular, (w i , z i ) * i (z i , z i ). Since (y i , x i ) ∼ * i (z i , z i ), we obtain (w i , z i ) * i (y i , x i ), a contradiction. ✷

The above lemma shows that we can replace RC2 with independence in the statement of Theorem 26 without further changes. It is easy to build examples showing that such a substitution is not possible in the statement of Theorem 13 (e.g., take X = {x 1 , y 1 } × {x 2 , y 2 } and on X identical to X 2 except that (x 1 , x 2 ) (x 1 , y 2 ) and (y 1 , x 2 ) (y 1 , y 2 ), which leads to [(x 1 , y 1 ) ∼ * 1 (y 1 , x 1 )] ≻ * 1 [(x 1 , x 1 ) ∼ * 1 (y 1 , y 1 )] and [(x 2 , x 2 ) ∼ * 2 (y 2 , y 2 ) ∼ * 2 (y 2 , x 2 )] ≻ * 2 (x 2 , y 2 )]. It is clear that this relation is independent. Using Lemma 4, it is easy to check that RC1 and RC2 2 holds. Condition RC2 1 is violated because (x 1 , x 2 ) (y 1 , y 2 ) and (y 1 , x 2 ) (x 1 , y 2 ) while (x 1 , x 2 ) (x 1 , y 2 )). Using Lemma 8, it is clear that U C and LC hold so that the same is true for M 1 and M 2. Using Lemma 15, one can check that conditions AC1 1 , AC2 1 and AC3 1 are violated).

Errata.

We are taking this occasion to correct a number of typos that crept in the published version of BP05.

1.

  Page 429, col. 2, line 10: read "such that A ∪ B = N ". 2. Page 431, col. 1, line -13: read "(x i , y i ) * * i (z i , w i ) ⇔ (w i , z i ) * * i (y i , x i )". 3. Page 433, col. 2, line -20: read "part 6 of lemma 16". 4. Page 435, col. 1, line 13: read (M * ) 5. Page 435, col. 2, line 1: read "contrary to theorem 12, theorem 24 is only stated. . . ". 6. Page 441, col. 1, line 21: read "Proof of theorem 18". 7. Page 442, col. 2, line 17: read "Proof of theorem 28".

  BP05, Example 35 on two attributes is shown to satisfyRC2 1 , RC2 2 U C 1 , U C 2 , LC 1 , LC 2 , AC1 1 , AC1 2 and AC3 2 but to violate AC3 1 . Using Lemma 11, we know that M 1 1 , M 1 2 , M 2 1 and M 2 2 hold. ✸ Example 21 (RC1, RC2, M 1, M 2, AC3, AC1 j for all j = i, Not[ AC1 i ]).In BP05, Example 36 on two attributes is shown to satisfyRC2 1 , RC2 2 U C 1 , U C 2 , LC 1 , LC 2 , AC3 1 ,AC3 2 and AC1 2 but to violate AC1 1 . Using Lemma 11, we know that M 1 1 , M 1 2 , M 2 1 and M 2 2 hold. ✸ Example 22 (RC1, RC2, M 1, AC1, AC3, M 2 j for all j = i, Not[ M 2 i ]). As observed in the proof of Part 5 of Lemma 11, Example 34 in BP05 on two attributes satisfies RC1, RC2, M 1, and M 2 1 but violates M 2 2 . It is easy to check, using Lemma 15, that this example also satisfies AC1 and AC3.

✸

Example 23 (RC1, RC2, M 2, AC1, AC3, M 1 j for all j = i, Not[ M 1 i ]). As observed above in the proof of Part 5 of Lemma 11, Example 33 in BP05 on two attributes satisfies RC1, RC2, M 2 and M 1 1 but violates M 1 2 . It is easy to check, using Lemma 15, that this example also satisfies AC1 and AC3. ✸ Example 24 (RC2, M 1, M 2, AC1, AC3, RC1 j for all j = i, Not[ RC1 i ]). It is easy to check, using Lemma 15, that in Example 12 above, conditions AC1 and AC3 are satisfied (condition AC2 1 is violated but AC2 2 and AC2 3 hold). ✸

Example 25 (RC1, M 1, M 2, AC1, AC3, RC2 j for all j

Theorem 26. Let be a binary relation on X = n i=1 X i . Then is a CR having a representation ☎, S i in which all S i are semiorders iff it is reflexive and satisfies RC1, RC2, M 1, M 2, AC1 and AC3. In the class of reflexive relations, conditions RC1, RC2, M 1, M 2, AC1 and AC3 are independent.

This give a complete characterization of CR in which all S i are semiorders using independent conditions that are all used in the characterization of the underlying model (M*).

Let us finally notice that, for a reflexive relation satisfying conditions RC1, RC2, M 1, M 2, AC1 and AC3, the relations * i become highly constrained. Indeed, the reader might have noticed that in Example 25 above, the violation of RC2 i is, in fact, a violation of the independence of the attributes in N \ {i}. This is not by chance. Indeed, we have:

Lemma 27. Let be a binary relation on a set X = n i=1 X i . Suppose that is reflexive and satisfies RC1 i , M 2 i and AC3 i . Then it satisfies RC2 i if and only if the attributes in N \ {i} are independent.

Proof.

We already observed that condition RC2 i implies that the attributes in N \ {i} are independent. Let us prove the reverse implication.

Suppose that RC2 i is violated, so that, (

Using RC1 i , we know that we have (x i , y i ) ≻ * i (z i , w i ) and (y i , x i ) ≻ * i (w i , z i ). Furthermore, since RC1 i and M 2 i holds, we know from Lemma 11 that LC i holds. Using RC1 i , we distinguish three exclusive cases.

Suppose that (x

, for all a i ∈ X i , so that, in particular, (x i , x i ) * i (y i , x i ). Using the transitivity and completeness of * i this implies (x i , y i )

, for all a i ∈ X i , so that, in particular, (y i , x i ) * i (x i , x i ). Using the transitivity and completeness of * i this implies (y i , x i )

would lead to violation of LC i . Hence, we must have (y i , x i ) ∼ * i (x i , x i ). Since the attributes in N \ {i} are independent, it is easy to see that we must have (z i , z i ) ∼ * i (w i , w i ), for all z i , w i ∈ X i . Hence, we know that (x i , y i ) ∼ * i (z i , z i ). Using