Denis Bouyssou

Marc Pirlot

A note on the asymmetric part of an outranking relation

Keywords: Decisions with multiple attributes, Outranking relations, Concordance, Discordance, Axiomatic analysis

This note discusses the properties of the asymmetric part of an outranking relation à la ELECTRE. Such relations have been used in the pseudodisjunctive version of ELECTRE TRI-B. We show that they have properties that are somewhat different from the ones of outranking relations. Indeed, contrary to outranking relations, they allow to have at the same time veto and bonus effects. We suggest that this explains the difficulty in analyzing the properties of the pseudo-disjunctive version of ELECTRE TRI-B and the complexity of the elicitation methods of its parameters. We give conditions that characterize such relations.

Introduction

Most outranking methods, including the well known ELECTRE methods [START_REF] Roy | Classement et choix en présence de points de vue multiples (la méthode ELEC-TRE)[END_REF]Roy and Bertier, 1973), compare alternatives evaluated on several attributes using the concordance / non-discordance principle. It leads to accepting the proposition that an alternative is "superior" to another if the coalition of attributes supporting it is "sufficiently important" (concordance condition) and there is no attribute that "strongly rejects" it (non-discordance condition). The fact that an alternative is "superior" to another means at least two different things. In the ELECTRE methods, superior means "not worse". Such methods aim at building a reflexive preference relation that is interpreted as an "at least as good as" relation. In other methods, like the TACTIC method [START_REF] Vansnick | On the problems of weights in MCDM (the noncompensatory approach)[END_REF], superior means "strictly better than". Such methods build an asymmetric relation that is interpreted as strict preference.

We have studied, from an axiomatic point of view, both reflexive outranking relations (Bouyssou and Pirlot, 2005a, 2007[START_REF] Bouyssou | An axiomatic analysis of concordance-discordance relations[END_REF] and asymmetric outranking relations (Bouyssou andPirlot, 2002b, 2012). We have also recently unified and generalized the analysis of both cases in [START_REF] Bouyssou | On the relationship between strict and non-strict outraking relations[END_REF]. For other approaches, we refer to [START_REF] Greco | Axiomatic basis of noncompensatory preferences[END_REF] and [START_REF] Dubois | A characterization of generalized concordance rules in multicriteria decision-making[END_REF].

These works leave the following problem open. What are the properties of the asymmetric part of a reflexive outranking relation? This question is not only of theoretical interest. Indeed, the pseudo-disjunctive version (also known as "optimistic", we use here the terminology of Almeida- Dias, Figueira, and[START_REF] Almeida-Dias | ELECTRE TRI-C: A multiple criteria sorting method based on characteristic reference actions[END_REF][START_REF] Roy | Présentation et interprétation de la méthode ELECTRE TRI pour affecter des zones dans des catégories de risque[END_REF] of ELECTRE TRI-B (Roy and Bouyssou, 1993, Ch. 6) makes use of such a relation, contrary to the pseudo-conjunctive version (also known as "pessimistic") that uses a reflexive outranking relation. We will show that the asymmetric part of a reflexive outranking relation is a more complex object than an outranking relation since it allows both veto and bonus effects. The idea of veto is classical in outranking methods and refers to a deleted preference due to an excessively large negative difference of performance on some criterion. The idea of bonus is more uncommon. It refers to a preference induced by a large positive difference of performance on some criterion. This idea was already introduced in [START_REF] Bouyssou | On the relationship between strict and non-strict outraking relations[END_REF]. We will use it here in a slightly different manner: while the bonus effects in [START_REF] Bouyssou | On the relationship between strict and non-strict outraking relations[END_REF] were unconditional, the ones used here will only occur in specific cases.

The rest of the paper is organized as follows. Section 2 introduces our notation and definitions concerning binary relations, product sets and outranking relations. Section 3 presents background material on traces and our previous characterizations of outranking relations. Section 4 presents our main results. A final section concludes and discusses our findings.

Definitions and notation 2.1 Binary relations

A preference relation on a set X is in general denoted by R. Omitting obvious quantifications, we say that a binary relation R on

X is reflexive if a R a. It is complete if a R b or b R a. It is antisymmetric if [a R b and b R a] ⇒ a = b. It is asymmetric if a R b ⇒ Not[b R a]. It is transitive if [a R b and b R c] ⇒ a R c. It is Ferrers if [a R b and c R d] ⇒ [a R d or c R b]. It is semi-transitive if [a R b and b R c] ⇒ [a R d or d R c].
A weak order is a complete transitive relation. A semiorder is a reflexive, Ferrers and semi-transitive relation. As first observed by [START_REF] Luce | Semiorders and a theory of utility discrimination[END_REF], any semiorder R on X induces a weak order T (R) on X that is defined, for all a, b ∈ X,

a T (R) b if ∀c ∈ X, [b R c ⇒ a R c] and [c R a ⇒ c R b].
(1)

Conversely, if R is reflexive and there is a weak order T such that, for all a, b ∈ X, a T b

⇒ ∀c ∈ X, [b R c ⇒ a R c] and [c R a ⇒ c R b], then R is a semiorder. The asymmetric (resp. symmetric) part of R is the binary relation R α (resp. R σ ) such that, for all a, b ∈ X a R α b if [a R b and Not[b R a]] (resp. a R σ b if [a R b and b R a]).

Product sets

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 ≥ 2 sets X i . The set X i gathers all possible evaluations that an alternative can have on attribute i. The sets X i are not assumed to be sets of numbers, not even to be ordered sets. The set {1, 2, . . . , n} of all attributes will be denoted by N .

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

If R is a binary relation on X, 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 . As in Bouyssou and Pirlot (2005a), in order to avoid unnecessary minor complications, we suppose henceforth that all attributes in N are influential for R. Our results in Section 4 will use the slightly stronger hypothesis stating that all attributes are influential for the asymmetric part of R (see Remark 26).

Outranking relations

The following definition of an outranking relation is taken from [START_REF] Bouyssou | On the relationship between strict and non-strict outraking relations[END_REF]. Notice that it is silent about the fact that the relation R is reflexive or asymmetric.

Definition 1 (Concordance-discordance relations) Let R be a binary relation on X = n i=1 X i . We say that R is a concordancediscordance 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 ),

2. 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, (2)
such that, for all x, y ∈ X,

x R y ⇔ [S [x, y] ¤ S [y, x] and V [y, x] = ∅] , (3)
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 CDR.
A concordance relation (CR) is a CDR having a representation in which all relations V i are empty.

A CDR with attribute transitivity (CDR-AT) is a CDR for which, for all i ∈ N ,

• S i is a semiorder

• V i is the asymmetric part of a semiorder U i
• (S i , U i ) form a homogeneous chain of semiorders, i.e., there is a weak order T i on X i such that:

x i T i y i ⇒ ∀z i ∈ X i , [y i S i z i ⇒ x i S i z i ] and [z i S i x i ⇒ z i S i y i ],
and

x i T i y i ⇒ ∀z i ∈ X i , [y i U i z i ⇒ x i U i z i ] and [z i U i x i ⇒ z i U i y i ]. (4)
The asymmetric (resp. symmetric) part of ¤ will be denoted by £ (resp. ). It is easy to show that if ¤ satisfies (2), the same is true for £.

Remark 2

For the case of asymmetric outranking relations [START_REF] Bouyssou | An axiomatic approach to TACTIC[END_REF] have introduced the following definition1 . Instead of (3) they have stated that

x R y ⇔ [P [x, y] ¤ P [y, x] and V [y, x] = ∅] ,
with P i an asymmetric binary relation on X i and ¤ a relation between disjoint subsets of N . This definition is clearly equivalent to the one used above. This is obvious letting A ¤ B ⇔ (N \ B) ¤ (N \ A) and observing that if ¤ satisfies (2) then ¤ also satisfies (2) (and vice versa).

•

Remark 3

Observe that, when S i and U i are complete, the existence of a weak order T i satisfying (4) implies that both S i and U i are semiorders. The above definition could therefore omit to specify that S i and U i are semiorders. Moreover, it is not difficult to check that, when S i and U i are complete, the first part of (4) may equivalently be written as

x i T i y i ⇒ ∀z i ∈ X i , [y i P i z i ⇒ x i P i z i ] and [z i P i x i ⇒ z i P i y i ],
and the second part as

x i T i y i ⇒ ∀z i ∈ X i , [y i V i z i ⇒ x i V i z i ] and [z i V i x i ⇒ z i V i y i ],
where, as before, P i (resp. V i ) is the asymmetric part of S i (resp. U i ). This will be useful later.

•

The following proposition shows that the above definition is flexible enough to cover both the case of a reflexive outranking relation à la ELECTRE and the case of an asymmetric outranking relation à la TACTIC.

Proposition 4 [START_REF] Bouyssou | On the relationship between strict and non-strict outraking relations[END_REF]

, Proposition 8) If R is a CDR with representation ¤, S i , V i , then 1. R is either reflexive or irreflexive. R is reflexive iff N ¤ N . Otherwise, R is irreflexive, 2. R is asymmetric iff ¤ is asymmetric.
Let us illustrate the flexibility of Definition 1 with two well-known examples.

Example 5 (ELECTRE I, [START_REF] Roy | Classement et choix en présence de points de vue multiples (la méthode ELEC-TRE)[END_REF] Outranking relations in ELECTRE I are built as follows. 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 letting:

x i S i y i ⇔ u i (x i ) ≥ u i (y i ) -pt i , x i U i y i ⇔ u i (x i ) ≥ u i (y i ) -vt i . (5)
The relation

V i is the asymmetric part of U i , i.e., x i V i y i ⇔ [x i U i y i and Not[y i U i x i ]] ⇔ u i (x i ) > u i (y i ) + vt 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] = ∅,
where S [x, y] = {i ∈ N :

x i S i y i }, and V [x, y] = {i ∈ N : x i V i y i }.
It is easy to see that a relation R built with ELECTRE I is a reflexive CDR (i.e., an R-CDR) with attribute transitivity (i.e., an R-CDR-AT) according to Definition 1. Indeed, it suffices to take, for all i ∈ N , [START_REF] Vansnick | On the problems of weights in MCDM (the noncompensatory approach)[END_REF] Outranking relations in TACTIC are built as follows. 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 in (5). The relation P i is defined as the asymmetric part of S i , i.e., we have

S i = S i , V i = V i , and, for all A, B ∈ 2 N with A ∪ B = N , A ¤ B ⇔ ( i∈A w i )/( j∈N w j ) ≥ s. Q Example 6 (TACTIC,
x i P i y i ⇔ [x i S i y i and Not[y i S i x i ]] ⇔ u i (x i ) > u i (y i ) + vt i . The relation V i is the asymmetric part of U i , i.e., x i V i y i ⇔ [x i U i y i and Not[y i U i x i ]] ⇔ u i (x i ) > u i (y i ) + vt i An outranking relation R is defined letting, for all x, y ∈ X, x R y ⇔   i∈P [x,y] w i > ρ j∈P [y,x] w j + ε and V [y, x] = ∅   ,
where w i is a positive weight assigned to attribute i, ρ is a multiplicative threshold with ρ ≥ 1, ε is a nonnegative additive threshold, P [x, y] = {i ∈ N :

x i P i y i } and V [x, y] = {i ∈ N : x i V i y i }.
It is easy to see that a relation R built with TACTIC is an asymmetric CDR (i.e., an A-CDR) with attribute transitivity (i.e., an A-CDR-AT) according to Definition 1. Indeed, it suffices to take, for all i ∈ N , S i = S i , V i = V i , and, for all

A, B ∈ 2 N such that A ∪ B = N , A ¤ B ⇔ i∈N \B w i > ρ j∈N \A w j + ε. Q 3 Background

Traces

We first recall a few structural definitions taken from Bouyssou andPirlot (2002a, 2004a,b).

Traces on differences

Our first definition gives conditions under which it is possible to define complete traces on differences.

Definition 7

We say that R satisfies

RC 1 i if (x i , a -i ) R (y i , b -i ) and (z i , c -i ) R (w i , d -i )    ⇒    (x i , c -i ) R (y i , d -i ) or (z i , a -i ) R (w i , b -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 .

Condition RC 1 i amounts to say that all preference differences (x i , y i ) on X i can be weakly ordered. Condition 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 independent (i.e., that, for all i ∈ N all x i , y i ∈ X i and all

a -i , b -i ∈ X -i , (x i , a -i ) R (x i , b -i ) ⇔ (y i , a -i ) R (y i , b -i ))
. Since they will be useful in the sequel, we recall the precise definition of the weak orders induced on each attribute X i as well as the main properties linking them to conditions RC 1 and RC 2. It is easy to check that all CDR satisfy conditions RC 1 and RC 2.

Definition 8

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 )] .
These relations allow to give a precise meaning to the comparison of preference differences on each attribute (see Bouyssou and Pirlot, 2002a, for more detail). By construction, both relations * i and * * i are transitive. The impact of RC 1 i and RC 2 i is to ensure their completeness, as shown below.

Lemma 9 (Bouyssou and Pirlot, 2002a, 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].
Traces on differences are well-behaved, as detailed below.

Lemma 10 (Bouyssou and Pirlot, 2005b, Lemma 3.7) For all x, y ∈ X and all z i , w i ∈ X i ,

[(z i , w i ) ∼ * i (x i , y i ) for all i ∈ N ] ⇒ [x R y ⇔ z R w], [x R y and (z i , w i ) * i (x i , y i )] ⇒ (z i , x -i ) R (w i , y -i ), [x R α y and (z i , w i ) * * i (x i , y i )] ⇒ (z i , x -i ) R α (w i , y -i ), [(z i , w i ) ∼ * * i (x i , y i ) for all i ∈ N ] ⇒      [x R y ⇔ z R w] and [x R α y ⇔ z R α w].

Traces on levels

The next definition gives conditions under which it is possible to define complete traces on the elements of each attribute.

Definition 11

We say that R satisfies

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 .

These conditions are related to the existence of linear arrangements of the elements of X i . AC 1 i suggests that the elements of X i can be 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. It is easy to check that all CDR-AT satisfy conditions AC 1, AC 2, and AC 3.

The following gives a precise definition of the upward and downward dominance relations.

Definition 12

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], (6) x i - i y i ⇔ ∀a ∈ X, b -i ∈ X -i , [a R (x i , b -i ) ⇒ a R (y i , b -i )], (7) x i ± i y i ⇔ x i + i y i and x i - i y i . (8)
By definition, + i , - i and ± i are transitive relations. Conditions AC 1 i , AC 2 i and AC 3 i ensure that they are complete, as shown below.

Lemma 13 (Bouyssou and Pirlot, 2004a

, Lemma 3) 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. Traces on levels are also well-behaved, as detailed below.

Lemma 14 (Bouyssou and Pirlot, 2005b, Lemma 3.5) For all i ∈ N and x, y, z, w ∈ X:

[x R y, z i + i x i ] ⇒ (z i , x -i ) R y, [x R y, y i - i w i ] ⇒ x R (w i , y -i ), [z i ± i x i , y i ± i w i ] ⇒ x R y ⇒ (z i , x -i ) R (w i , y -i ), and x R α y ⇒ (z i , x -i ) R α (w i , y -i ), [z i ∼ ± i x i , y i ∼ ± i w i , for all i ∈ N ] ⇒ x R y ⇔ z R w, and x R α y ⇔ z R α w.

Relations between traces

Traces on differences and on levels will be of central importance in what follows.

We summarize below the main links between the relations * i , * * i , ± i , + i and i below. Lemma 15 (Bouyssou and Pirlot, 2005b, Lemma 3.8) For all i ∈ N and all x i , y i ∈ X i , 1. Bouyssou andPirlot (2002a, 2004a,b) have shown how the conditions introduced so far enable to obtain various numerical representations of R even though it may not be complete or transitive.

x i + i y i ⇔ [(x i , w i ) * i (y i , w i ), for all w i ∈ X i ], 2. x i - i y i ⇔ [(w i , y i ) * i (w i , x i ), for all w i ∈ X i ], 3. x i ± i y i ⇔ [(x i , w i ) * * i (y i , w i ), for all w i ∈ X i ], 4. [ i + i x i and (x i , y i ) * i (z i , w i )] ⇒ ( i , y i ) * i (z i , w i ), 5. [y i - i i and (x i , y i ) * i (z i , w i )] ⇒ (x i , i ) * i (z i , w i ), 6. [z i + i i and (x i , y i ) * i (z i , w i )] ⇒ (x i , y i ) * i ( i , w i ), 7. [ i - i w i and (x i , y i ) * i (z i , w i )] ⇒ (x i , y i ) * i (z i , i ), 8. [x i ∼ + i z i and y i ∼ - i w i ] ⇒ (x i , y i ) ∼ * i (z i , w i ), 9. [x i ∼ ± i z i and y i ∼ ± i w i ] ⇒ (x i , y i ) ∼ * * i (z i , w i ).

Characterization of outranking relations

Concordance relations

The strategy of Bouyssou and Pirlot (2002b, 2005a, 2007[START_REF] Bouyssou | An axiomatic analysis of concordance-discordance relations[END_REF], first presented in [START_REF] Bouyssou | A general model of preference aggregation[END_REF] and [START_REF] Bouyssou | Conjoint measurement without additivity and transitivity[END_REF], to characterize outranking relations is to introduce conditions limiting the number of equivalence classes of * i and * * i . Indeed, it is easy to see that an outranking relation generates a relation * i that has at most four equivalence classes. The first one corresponds to a strict preference. The second one to an indifference. The third one to a reverse strict preference that is not a veto. The fourth one to a reverse strict preference that is veto. When this relation is a concordance relation, the fourth class must be empty. This is the intuition behind the following two conditions.

Definition 16

We say that R satisfies

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 .
MM 1 i without its second premise is called M 1 i . MM 1 i without its second conclusion is called Maj 1 i . MM 1 i without both its second premise and its second conclusion is called UC i .

MM 2 i without its second premise is called M 2 i . MM 2 i without its second conclusion is called Maj 2 i . MM 2 i without both its second premise and its second conclusion is called LC i .

MM 1 i is clearly a weaker condition than both M 1 i and Maj 1 i . Both M 1 i and Maj 1 i are implied by UC i . Similarly, MM 2 i is clearly a weaker condition than both M 2 i and Maj 2 i . Both M 2 i and Maj 2 i are implied by LC i .

It is not difficult to check that a concordance relation (CR) satisfies UC and LC . The need for the weaker conditions introduced above is to ensure that all conditions remain independent from the conditions used to impose the existence of complete traces. We have:

Lemma 17 (Bouyssou and Pirlot, 2013, Lemma 41) 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 Maj 1 i , 3. MM 2 i and RC 2 i entail M 2 i , 4. MM 2 i and RC 1 i entail Maj 2 i .
Under RC 1 i and RC 2 i , we have:

1. MM 1 i ⇔ M 1 i ⇔ Maj 1 i ⇔ UC i , 2. MM 2 i ⇔ M 2 i ⇔ Maj 2 i ⇔ LC i .

Moreover we have:

Lemma 18 (Bouyssou and Pirlot, 2013, Lemma 24) 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 )].
The above two lemmas show that, in presence of RC 1 and RC 2, conditions MM 1 and MM 2 imply that there are only one type of positive differences (corresponding to strict preference) and one type of negative differences (corresponding to reverse strict preference). This is a characteristic of outranking relations in which there is no veto, i.e., of concordance relations. We have:

Theorem 19 (Bouyssou and Pirlot, 2013, Theorems 43 & 52) Let R be a reflexive binary relation on X = n i=1 X i .

1. R is a concordance relation (CR) iff it satisfies RC 1, RC 2, MM 1 and MM 2.

2. R is a concordance relation with attribute transitivity (CR-AT) iff it satisfies RC 1, RC 2, AC 1, AC 3, MM 1, MM 2.

3. In the class of reflexive relations and in the class of asymmetric relations, conditions RC 1, RC 2, AC 1, AC 3, MM 1, MM 2 are independent.

The above result generalizes the ones obtained in Bouyssou and Pirlot (2005a, 2007[START_REF] Zheng | Preference Elicitation for reference based aggregation models: Algorithms and Procedures[END_REF].

Outranking relations

When veto effect are allowed, there can be two types of negative differences: negative difference corresponding to a "normal" reverse preference and negative differences corresponding to a "large" reverse preference, i.e., a negative difference acting as a veto. Taking veto effect into account implies relaxing condition MM 2. This motivates the condition below.

Definition 20

We say that R 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 ), (9) 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 MM 3 if it satisfies MM 3 i , for all i ∈ N . M 3 i is the same condition as MM 3 i except that the second premise has been removed. Maj 3 i is the same condition as MM 3 i except that the second conclusion has been removed.

Let us observe that MM 3 i only differs from MM 2 i by the adjunction of a premise, implying that MM 3 i is a weakening of MM 2 i .

Let us interpret condition M 3 i , under the hypothesis that RC 1 i holds. 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 ordered pair (z i , w i ) represents an unacceptable preference difference, leading to a veto. We have:

Lemma 21 (Bouyssou and Pirlot, 2013, Lemma 55) 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 Maj 3 i , 3. M 3 i and RC 1 i entail Maj 3 i , 4. Maj 3 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 ⇔ Maj 3 i .
The conditions introduced so far are all what we need to characterize outranking relations.

Theorem 22 (Bouyssou and Pirlot, 2013, Theorems 57 & 61) Let R be a binary relation on

X = n i=1 X i . 1. The relation R is a CDR iff it satisfies RC 1, RC 2, AC 1, MM 1 and MM 3. 2. The relation R is a CDR-AT iff it satisfies RC 1, RC 2, AC 1, AC 2, AC 3,
MM 1 and MM 3.

3. Conditions RC 1, RC 2, AC 1, AC 2, AC 3, MM 1 and MM 3 are independent in the class of reflexive relations as well as in the class of asymmetric relations.

The above result generalizes the ones obtained in Bouyssou andPirlot (2009, 2012).

We now have all the necessary background to study the properties of the asymmetric part of a reflexive CDR-AT (i.e., is an R-CDR-AT). Indeed, if the CDR-AT is already asymmetric (i.e., is an A-CDR-AT), there is little point studying its asymmetric part.

4 The asymmetric part of an outranking relation

Introduction

Let R be a reflexive CDR (i.e., an R-CDR) with representation ¤, S i , V i . Using the definition of an R-CDR, its asymmetric part, denoted by R α , is such that, for all x, y ∈ X,

x R α y ⇔ [x R y and Not[y R x]] ⇔    [S [x, y] ¤ S [y, x] and V [y, x] = ∅] and [Not[S [y, x] ¤ S [x, y]] or V [x, y] = ∅] . Such a relation R α is the asymmetric part of an R-CDR. We say that R α is an AP-R-CDR. If, furthermore, the relation R is an R-CDR-AT, we say that R α is an AP-R-CDR-AT.
It is easy to see that the above definition can equivalently be written as:

x R α y ⇔ [S [x, y] £ S [y, x] and V [y, x] = ∅] or (10) S [x, y] S [y, x] and V [y, x] = ∅ and V [x, y] = ∅ . ( 11
)
The first of these conditions is similar to the one defining a CDR. The second one is more complex. In the asymmetric part of an R-CDR, the relation V i may play the rôle of a veto (discarding a pair belonging to the asymmetric part of the concordance relation) or, on the contrary, play the rôle of a bonus (transforming an indifference, w.r.t. the concordance relation, into a strict preference). Note that the "bonus effect" just described is different from the one at work in the concordance relations with bonus studied in Bouyssou and Pirlot (2013, Section 4.7). In the latter, a bonus effect shows up and results in a preference as soon as there is a large enough difference of preference on a single attribute. In the present case, the bonus effect is conditional: it only shows up in case a pair of alternatives are indifferent w.r.t. the concordance relation and there is no veto against preference.

Remark 23

The relations we study in this paper have been defined in an indirect way, namely, as the asymmetric part of a concordance-discordance relation. A direct definition of such relations can easily be obtained from Definition 1. We just have to specify that the relation R is asymmetric and to substitute the condition (3), for having x R y, by conditions ( 10) and ( 11).

•

Remark 24

It is easy to see that there are two simple cases in which the asymmetric part of a reflexive CDR-AT is an asymmetric CDR-AT. The first case is trivial: if the reflexive CDR-AT is antisymmetric, i.e., when the relation is empty, except that N N , the asymmetric part of R is identical to R except for loops. It is then easy to check that the asymmetric part of R is an asymmetric CDR-AT.

The second case is also trivial. When the relation R is a reflexive CDR-AT has a representation in which all relations V i are empty (i.e., is a CR-AT), it is easy to see that the asymmetric part of R is an asymmetric CDR-AT (that is also a CR-AT).

• Indeed, in general, the asymmetric part of a reflexive CDR-AT is not an asymmetric CDR-AT. This is illustrated below.

Example 25 Let N = {1, 2, 3, 4} and X = {x 1 , y 1 , z 1 } × {x 2 , y 2 } × {x 3 , y 3 } × {x 4 , y 4 }. Let R on X be such that x R y ⇔ |S [x, y] | ≥ |S [y, x] | and V [y, x] = ∅, where S [x, y] = {i ∈ N : x i S i y i } and V [x, y] = {i ∈ N : x i V i y i } with: x 1 P 1 y 1 P 1 z 1 , x 2 P 2 y 2 , x 3 P 3 y 3 , x 4 P 4 y 4 , V i = ∅, for i ∈ {2, 3, 4} and x 1 V 1 z 1 .
(where P i denotes the asymmetric part of the complete relation S i ).

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

(x 1 , x 2 , x 3 , y 4 ) R α (z 1 , x 2 , x 3 , x 4 ) and Not[(x 1 , x 2 , x 3 , y 4 ) R α (y 1 , x 2 , x 3 , x 4 )], (x 1 , x 2 , x 3 , x 4 ) R α (y 1 , y 2 , x 3 , x 4 ) and Not[(y 1 , x 2 , x 3 , x 4 ) R α (x 1 , y 2 , x 3 , x 4 )].
The first line implies that, w.r.t. R α , the difference (x 1 , z 1 ) is strictly larger (w.r.t. * 1 ) than the difference (x 1 , y 1 ). The second line shows that the difference (x 1 , y 1 ) is strictly larger (w.r.t. * 1 ) than its opposite (y 1 , x 1 ). It is easy to see that this is impossible in a CDR (see Bouyssou and Pirlot, 2012, Lemma 9.1, for details). Q

The problem we would like to study is the following. Suppose that we are given an asymmetric relation P on X. Under what conditions is there a reflexive CDR-AT R on X such that R α = P ? In other words, under what conditions can we be sure that P is the asymmetric part of a reflexive CDR-AT? Some of the conditions characterizing an R-CDR-AT also hold for an AP-R-CDR-AT. Others will have to be weakened.

In the rest of this section, in order to avoid the superscript α, we use P to denote an asymmetric relation. When P is an AP-R-CDR-AT, the R-CDR-AT of which P is the asymmetric part will be denoted by S. In the rest of this section, unless otherwise specified, the relations * i , * * i , + i , - i and ± i always refer to the relation P.

Remark 26

For an AP-R-CDR P that is the asymmetric part of an R-CDR S, assuming that all attributes are influential for S is in general insufficient for guaranteeing the corresponding property for S α . It is clear that if an attribute is influent for S α it must be influent for S. Indeed the influence of i ∈ N for S α implies that 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 ) S α (y i , y -i ) and Not[(z i , x -i ) S α (w i , y -i )]. Hence we have (x i , x -i ) S (y i , y -i ) and Not[(y i , y -i ) S (x i , x -i )] together with either Not[(z i , x -i ) S (w i , y -i )] or (w i , y -i ) S (z i , x -i ).
In either case we easily conclude that i ∈ N is influential for S.

The converse is not true. Indeed, an attribute which only impact would be to transform some pairs belonging to the symmetric part S σ of S into pairs that are incomparable w.r.t. S, is influential for S but is degenerate for S α .

The condition that all attributes are influential for S α is therefore slightly stronger than the one stating that all attributes are influential for S. Our results on AP-R-CDR-AT will use this slightly stronger hypothesis.

•

Properties of an AP-R-CDR-AT

The main difference between an AP-R-CDR-AT and an R-CR-AT is that with an AP-R-CDR-AT there may exist bonus effects as well as veto effects. Bonus effects amount to creating a new class of positive preference differences. Hence it should not be a surprise that we have to relax condition MM 1. However, as shown in the next lemma, all other conditions needed to characterize R-CDR-AT also hold for AP-R-CDR-AT.

Lemma 27

If P is an AP-R-CDR-AT, then 1. P satisfies RC 1 and RC 2, 2. P satisfies AC 1, AC 2, and AC 3, 3. P satisfies Maj 3 and, hence, MM 3.

Proof

The fact that P is an AP-R-CDR means that there is an R-CDR, S, with representation ¤, S i , V i such that P is the asymmetric part of S. Alternatively, one may use the definition introduced in Remark 23.

Part 1. [RC 1] Suppose that (x i , a -i ) P (y i , b -i ), (z i , c -i ) P (w i , d -i ). We know that Not[y i V i x i ] and Not[w i V i z i ]. If x i V i y i , since (z i , c -i ) P (w i , d -i ), we must have (x i , c -i ) P (y i , d -i ). Similarly, if z i V i w i , since (x i , a -i ) P (y i , b -i ), we must have (z i , a -i ) P (w i , b -i ). If neither x i V i y i nor z i V i w i
, the desired conclusion easily follows from the monotonicity of ¤.

[RC 2] Suppose that (x i , a -i ) P (y i , b -i ), (y i , c -i ) P (x i , d -i ). This implies that neither

x i V i y i nor y i V i x i . If z i V i w i , since (x i , a -i ) P (y i , b -i ), we must have (z i , a -i ) P (w i , b -i ). Similarly if w i V i z i , since (y i , c -i ) P (x i , d -i ), we must have (w i , c -i ) P (z i , d -i ). If neither z i V i w i nor w i V i z i
, the desired conclusion easily follows from the completeness of S i and the monotonicity of ¤.

Part 2. By hypothesis, there is a weak order T i on X i such that

x i T i y i ⇒ ∀z i ∈ X i , [y i S i z i ⇒ x i S i z i ] and [z i S i x i ⇒ z i S i y i ],
and

x i T i y i ⇒ ∀z i ∈ X i , [y i U i z i ⇒ x i U i z i ] and [z i U i x i ⇒ z i U i y i ].
Let us show that, if

z i T i x i , then (x i , a -i ) P (y i , b -i ) implies (z i , a -i ) P (y i , b -i ). By hypothesis, we have S [(z i , a -i ), (y i , b -i )] ⊇ S [(x i , a -i ), (y i , b -i )], S [(y i , b -i ), (z i , a -i )] ⊆ S [(y i , b -i ), (x i , a -i )], V [(y i , b -i ), (z i , a -i )] ⊆ V [(y i , b -i ), (x i , a -i )], V [(z i , a -i ), (y i , b -i )] ⊇ V [(x i , b -i ), (z i , a -i )]. By hypothesis, (x i , a -i ) P (y i , b -i ) means that (x i , a -i ) S (y i , b -i ) and Not[(y i , b -i ) S (x i , a -i )]
. Hence, using the monotonicity of ¤, because (x i , a -i ) S (y i , b -i ), we know that (z i , a -i ) S (y i , b -i ). Suppose now that (y i , b -i ) S (z i , a -i ). Using the monotonicity of ¤, we conclude that (y i , b -i ) S (x i , a -i ), a contradiction. Hence, we have (z i , a -i ) P (y i , b -i ).

Similarly, it is easy to show that, if

y i T i w i , then (x i , a -i ) P (y i , b -i ) implies (x i , a -i ) P (w i , b -i ).
Using these two facts and the completeness of T i , it is easy to check that AC 1, AC 2, and AC 3 hold.

Part 3. Suppose that (x i , a -i ) P (y i , b -i ), (w i , a -i ) P (z i , b -i ), (y i , c -i ) P (x i , d -i ),
and (z i , e -i ) P (w i , f -i ). This implies that it is impossible to have x i V i y i , y i V i x i , z i V i w i and w i V i z i . The desired conclusion easily follows from the monotonicity of ¤. P

The following lemma gives a simple interpretation of Maj 3. It is also useful for checking whether Maj 3 holds.

Lemma 28

Let P be a binary relation on X = n i=1 X i satisfying RC 1 and RC 2. Then P satisfies Maj 3 iff, for all i ∈ N , for all

x i , y i , z i , w i , r i , s i ∈ X i , [(x i , y i ) * i (y i , x i ) * i (z i , w i )] ⇒ (r i , s i ) * i (z i , w i ) and Not[(z i , e -i ) P (w i , f -i )],
for all e -i , f -i ∈ X -i .

Proof

Part [⇒]. Suppose that, for some x i , y i , z i , w i , r i , s i ∈ X i , we have (x i , y i ) * i (y i , x i ) * i (z i , w i ) and (z i , w i ) * i (r i , s i ). This implies (x i , a -i )

P (y i , b -i ), Not[(y i , a -i ) P (x i , b -i )], (y i , c -i ) P (x i , d -i ), Not[(z i , c -i ) P (w i , d -i )] and (z i , e -i ) P (w i , f -i ), for some a -i , b -i , c -i , d -i , e -i , f -i ∈ X -i .
Since this implies Not[(z i , w i ) * i (y i , x i )], we have, using RC 2 and Lemma 9.2, that (w i , z i ) * i (x i , y i ) so that (w i , a -i )

P (z i , b -i ). Using Maj 3 i , (x i , a -i ) P (y i , b -i ), (w i , a -i ) P (z i , b -i ), (y i , c -i ) P (x i , d -i ), and (z i , e -i ) P (w i , f -i ) imply (y i , a -i ) P (x i , b -i ) or (z i , c -i ) P (w i , d -i
), a contradiction. Note that the contradiction is obtained as soon as (z i , e -i ) P (w i , f -i ), for some e -i , f -i ∈ X -i . This proves the second part of the assertion.

Part [⇐]. To prove Maj 3 i , we assume that the first three premises in Maj 3 i are true and the two conclusions are false. Maj 3 i will result if we prove that the fourth premise must be false. Using RC 1 i , the first premise of Maj 3 i and the negation of the first conclusion imply (x i , y i ) * i (y i , x i ). Using RC 1 i again, the third premise and the negation of the second conclusion imply (y i , x i ) * i (z i , w i ).

Since by hypothesis [(x

i , y i ) * i (y i , x i ) * i (z i , w i )] ⇒ Not[(z i , e -i ) P (w i , f -i )],
for all e -i , f -i ∈ X -i , Maj 3 i is established. P

Additional properties of an AP-R-CDR-AT

The following two conditions are clearly weaker than MM 1. They shape the way bonus effects can occur in an AP-R-CDR-AT. The first condition amounts to saying that the inverse of a bonus must be a veto. The second one implies that there is only one type of bonus.

Definition 29

We say that P satisfies

MM 4 i if (x i , a -i ) P (y i , b -i ) and (z i , a -i ) P (w i , b -i ) and (z i , c -i ) P (w i , d -i ) and (w i , e -i ) P (z i , f -i )                    ⇒            (y i , a -i ) P (x i , b -i ) or (x i , c -i ) P (y i , d -i ) or (w i , a -i ) P (z i , b -i ), (12) MM 5 i if (x i , a -i ) P (y i , b -i ) and (z i , c -i ) P (w i , d -i ) and (z i , a -i ) P (w i , b -i ) and (r i , e -i ) P (s i , f -i )                    ⇒                            (y i , a -i ) P (x i , b -i ) or (x i , c -i ) P (y i , d -i ), or (x i , e -i ) P (y i , f -i ), or (z i , e -i ) P (w i , f -i ), or (w i , a -i ) P (z i , b -i ). ( 13
)
We say that MM 4 (resp. MM 5) holds if MM 4 i (resp. MM 5 i ) holds for all i ∈ N . MM 4 i without its third conclusion is called Maj 4 i . MM 5 i without its fifth conclusion is called Maj 5 i .

The above two conditions clearly weaken condition MM 1. Let us note the following relations between our conditions.

Lemma 30

We have

1. Maj 4 i ⇒ MM 4 i , 2. MM 1 i ⇒ MM 4 i , 3. MM 4 i and RC 2 i ⇒ Maj 4 i , 4. Maj 5 i ⇒ MM 5 i , 5. MM 1 i ⇒ MM 5 i , 6. MM 5 i and RC 2 i ⇒ Maj 5 i .

Proof

The first two points are obvious. Indeed, MM 4 i adds to Maj 4 i an additional possible conclusions. Similarly, MM 4 i adds to MM 1 i an additional premise. We prove the third point. Suppose that (x i , a -i )

P (y i , b -i ), (z i , a -i ) P (w i , b -i ), (z i , c -i ) P (w i , d -i ), (w i , e -i ) P (z i , f -i ). If Not[(w i , a -i ) P (z i , b -i )]
, then one of the two possible conclusions of Maj 4 i holds. If (w i , a -i ) P (z i , b -i ), using (z i , c -i ) P (w i , d -i ) and RC 2 i , we have either (y i , a -i ) P (x i , b -i ) or (x i , c -i ) P (y i , d -i ), which are the two possible conclusions of Maj 4 i .

The fourth and fifth points are obvious. Indeed, MM 5 i adds to Maj 5 i an additional premise and an additional possible conclusion. Similarly, MM 5 i adds to MM 1 i an additional premise and two possible conclusions. We prove the sixth point. Suppose that (x i , a -i )

P (y i , b -i ), (z i , c -i ) P (w i , d -i ), (z i , a -i ) P (w i , b -i ), (r i , e -i ) P (s i , f -i ). If Not[(w i , a -i ) P (z i , b -i )]
, we must have one of the four possible conclusions of Maj 5 i . If (w i , a -i ) P (z i , b -i ), then (z i , c -i ) P (w i , d -i ) and RC 2 i imply either (y i , a -i ) P (x i , b -i ) or (x i , c -i ) P (y i , d -i ). Hence, one of the possible conclusions of Maj 5 i holds. P

As shown below, conditions MM 4 and MM 5 are satisfied by an AP-R-CDR-AT.

Lemma 31

If P is an AP-R-CDR then 1. it satisfies Maj 4 and, hence, MM 4, 2. it satisfies Maj 5 and, hence, MM 5.

Proof Part 1. Suppose that (x i , a -i ) P (y i , b -i ), (z i , a -i ) P (w i , b -i ), (z i , c -i ) P (w i , d -i ),
and (w i , e -i ) P (z i , f -i ). This implies that it is impossible to have:

y i V i x i , w i V i z i , and z i V i w i . If x i V i y i , since (z i , c -i ) P (w i , d -i ), we must have (x i , c -i ) P (y i , d -i ). If Not[x i V i y i ],
the desired conclusion easily follows from the monotonicity of ¤.

Part 2. Suppose that (x i , a -i ) P (y i , b -i ), (z i , c -i ) P (w i , d -i ), (z i , a -i ) P (w i , b -i ), and (r i , e -i ) P (s i , f -i ). This implies that it is impossible to have:

y i V i x i , w i V i z i , and s i V i r i . If x i V i y i , since (z i , c -i ) P (w i , d -i ), we must have (x i , c -i ) P (y i , d -i ).
Similarly, if z i V i w i , since (r i , e -i ) P (s i , f -i ), we must have (z i , e -i ) P (w i , f -i ). If neither x i V i y i nor z i V i w i , the desired conclusion easily follows from the monotonicity of ¤. P It is clear that UC i implies M 1 i . Hence, UC i implies MM 1 i and, therefore, MM 4 i and MM 5 i . This will be useful for checking that MM 4 i and MM 5 i hold.

The following two lemmas give an interpretation of Maj 4 and Maj 5 in terms of the relations * i . They can also be useful to check that these conditions hold. Lemma 32 Let P be a binary relation on X = n i=1 X i , which satisfies RC 1. Then P satisfies Maj 4 if and only if, for all i ∈ N , for all

x i , y i , z i , w i , r i , s i ∈ X i , [(z i , w i ) * i (x i , y i ) * i (y i , x i )] ⇒ (r i , s i ) * i (w i , z i ) and Not[(w i , e -i ) P (z i , f -i )], for all e -i , f -i ∈ X -i . Proof Part [⇒]. Suppose that (z i , w i ) * i (x i , y i ) * i (y i , x i ). This implies (z i , c -i ) P (w i , d -i ) and Not[(x i , c -i ) P (y i , d -i )], (x i , a -i ) P (y i , b -i ) and Not[(y i , a -i ) P (x i , b -i )],
for some a -i , b -i , c -i , d -i ∈ X -i . Suppose furthermore that (w i , e -i ) P (z i , f -i ), for some e -i , f -i ∈ X -i . Because RC 1 holds, we know that * i is complete. Hence (x i , a -i ) P (y i , b -i ) implies (z i , a -i ) P (w i , b -i ). Applying now Maj 4 i leads to either (x i , c -i ) P (y i , d -i ) or (y i , a -i ) P (x i , b -i ), a contradiction.

Part [⇐]. To prove Maj 4 i , we assume that the first three premises of Maj 4 i are true and the two conclusions are false. Maj 4 i will result if we prove that the fourth premise must be false. Using RC 1 i , the first premise of Maj 4 i and the negation of the first conclusion imply (x i , y i ) * i (y i , x i ). Using RC 1 i again, the third premise and the negation of the second conclusion imply (z i , w i ) * i (x i , y i ).

Since by hypothesis [(z

i , w i ) * i (x i , y i ) * i (y i , x i )] ⇒ Not[(w i , e -i ) P (z i , f -i )], for all e -i , f -i ∈ X -i , Maj 4 i is established. P Lemma 33
Let P be a binary relation on X = n i=1 X i satisfying RC 1. Then P satisfies Maj 5 iff, for all i ∈ N , for all

x i , y i , z i , w i , r i , s i ∈ X i , [(z i , w i ) * i (x i , y i ) * i (y i , x i )] ⇒ (z i , w i ) * i (r i , s i ), for all r i , s i ∈ X i . Proof Part [⇒]. Suppose that (z i , w i ) * i (x i , y i ) * i (y i , x i ). This implies (z i , c -i ) P (w i , d -i ) and Not[(x i , c -i ) P (y i , d -i )], (x i , a -i ) P (y i , b -i ) and Not[(y i , a -i ) P (x i , b -i )], for some a -i , b -i , c -i , d -i ∈ X -i
. Suppose furthermore that (r i , e -i ) P (s i , f -i ), for some r i , s i ∈ X i and e -i , f -i ∈ X -i . We must show that we have (z i , e -i ) P (w i , f -i ).

Because RC 1 is assumed, we have (z i , w i ) * i (x i , y i ), hence, (z i , a -i ) P (w i , b -i ). We have (x i , a -i ) P (y i , b -i ), (z i , c -i ) P (w i , d -i ), (z i , a -i ) P (w i , b -i ), and (r i , e -i ) P (s i , f -i ), while Not[(y i , a -i ) P (x i , b -i )] and Not[(x i , c -i ) P (y i , d -i )]. Using Maj 5 i , we obtain either (x i , e -i ) P (y i , f -i ) or (z i , e -i ) P (w i , f -i ). Since (z i , w i ) * i (x i , y i ), the former consequence implies the latter, yielding the desired conclusion.

Part [⇐]. To prove Maj 5 i , we assume that the four premises of Maj 5 i are true and the first three conclusions are false. Maj 5 i will result if we prove that the fourth conclusion must be true. Using RC 1 i , the first premise of Maj 5 i and the negation of the first conclusion imply (x i , y i ) * i (y i , x i ). Using RC 1 i again, the second premise together with the negation of the second conclusion imply (z i , w i

) * i (x i , y i ). Since by hypothesis [(z i , w i ) * i (x i , y i ) * i (y i , x i )] ⇒ [(z i , w i ) * i (r i , s i )
] for all r i , s i ∈ X i , the fourth conclusion in Maj 5 i is true, hence Maj 5 i is established. P Our last condition (the "bonus condition") requires that the effect of one bonus is not altered by adding a second bonus on another attribute.

Definition 34

Let i, j ∈ N with i = j. We say that P satisfies

BC ij if (x i , a -i ) P (y i , b -i ) and (x i , c -i ) P (y i , d -i )
and (z j , e -j ) P (w j , f -j ) and (z j , g -j ) P (w j , h -j ) and

(x i , z j , α -ij ) P (y i , w j , β -ij )                            ⇒                            (x i , a -i ) P (y i , b -i ) or (y i , c -i ) P (x i , d -i ) or (z j , e -j ) P (w j , f -j ) or (w j , g -j ) P (z j , h -j ) or (x i , z j , α -ij ) P (y i , w j , β -ij ), for all x i , x i , y i , y i ∈ X i , all z j , z j , w j , w j ∈ X j , all a -i , b -i , c -i , d -i ∈ X -i , all e -j , f -j , g -j , h -j ∈ X -j and all α -ij , β -ij ∈ X -ij .
We say that BC holds if BC ij holds for all i, j ∈ N with i = j.

Condition BC ensures that the combination of bonuses has no different effect from that of a single bonus. In order to motivate this condition, suppose that all the premises of the condition hold. Suppose furthermore that the first four conclusions are false. This implies that the differences (x i , y i ) and (z j , w j ) both act as bonuses, as we shall see in Lemma 38. The last conclusion therefore implies that, replacing a bonus on both i, j ∈ N by a bonus on only one of these two attributes has no effect since at least one bonus is present.

The following lemma shows that BC holds for an AP-R-CDR.

Lemma 35

If P is an AP-R-CDR then it satisfies BC .

Proof

Let ¤, S i , V i be a representation of P. Suppose that all the premises of BC ij hold and that the first four conclusions do not hold. Using the direct definition of an AP-R-CDR (Remark 23), it is readily seen that the above imply:

x i P i y i , Not[x i V i y i ], x i P i y i , x i V i y i , z j P j w j , Not[z j V j w j ], z j P j w j , z j V j w j . Let A = S [(x i , z j , α -ij ), (y i , w j , β -ij )] and B = S [(y i , w j , β -ij ), (x i , z j , α -ij )]. It is clear that A = S [(x i , z j , α -ij ), (y i , w j , β -ij )] and B = S [(y i , w j , β -ij ), (x i , z j , α -ij )]. Because (x i , z j , α -ij ) P (y i , w j , β -ij ), we have A ¤ B. If A £ B, we must have (x i , z j , α -ij ) P (y i , w j , β -ij ). Suppose that A B. Since V [(x i , z j , α -ij ), (y i , w j , β -ij )] = ∅, we have (x i , z j , α -ij ) P (y i , w j , β -ij ). P
The following three lemmas will help checking that BC holds.

Lemma 36

If P satisfies UC i then, for all j = i it satisfies BC ij .

Proof

Suppose that (x i , a -i ) P (y i , b -i ) and (x i , c -i ) P (y i , d -i ). If the second conclusion of BC ij is not verified, we have Not[(y i , c -i ) P (x i , d -i )]. This implies Not[((y i , x i ) * i (x i , y i )] and UC i implies (x i , y i ) * i (a i , b i ), for all a i , b i ∈ X i . Hence, we have (x i , a -i ) P (y i , b -i ), so that the first conclusion of BC ij holds. P Lemma 37 If P satisfies RC 1 i , RC 2 i , and MM 1 i then, for all j = i, it satisfies BC ij .

Proof

The proof follows from combining Lemma 36 with Lemma 17. P

Lemma 38

Let i, j ∈ N with i = j. Let P be a relation satisfying RC 1 i and RC 1 j . Then P satisfies BC ij if and only if, for all x i , x i , y i , y i ∈ X i , and, for all z j , z j , w j , w j ∈ X j , we have that

(x i , y i ) * i (x i , y i ) * i (y i , x i ) (z j , w j ) * j (z j , w j ) * j (w j , z j ) (x i , z j , α -ij ) P (y i , w j , β -ij )    ⇒ (x i , z j , α -ij ) P (y i , w j , β -ij ). ( 14
)

Proof

Conditionally on the fact that * i and * j are complete relations (a consequence of RC 1 i and RC 1 j ), the conjunction of the five premises of BC ij and the negation of the first four consequences is logically equivalent with the premises of ( 14). Applying BC ij yields the consequence of ( 14). Conversely, using ( 14) yields the fifth consequence of BC ij . P

An easy consequence of RC 1 and BC is the following property saying that a bonus on attribute i has the same effect as a bonus on attribute j.

Lemma 39

Let P be a relation satisfying RC 1 and BC . Then, for all i, j ∈ N with i = j, we have:

(x i , a -i ) P (y i , b -i ) and (x i , c -i ) P (y i , d -i )
and (z j , e -j ) P (w j , f -j ) and (z j , g -j ) P (w j , h -j ) and

(x i , z j , α -ij ) P (y i , w j , β -ij )                            ⇒                            (x i , a -i ) P (y i , b -i ) or (y i , c -i ) P (x i , d -i ) or (z j , e -j ) P (w j , f -j ) or (w j , g -j ) P (z j , h -j ) or (x i , z j , α -ij ) P (y i , w j , β -ij ), (15)
for all x i , x i , y i , y i ∈ X i , all z j , z j , w j , w j ∈ X j , all a -i , b -i , c -i , d -i ∈ X -i , all e -j , f -j , g -j , h -j ∈ X -j , and all α -ij , β -ij , ∈ X -ij .

Assuming RC 1, property (15) is equivalent with

(x i , y i ) * i (x i , y i ) * i (y i , x i ) (z j , w j ) * j (z j , w j ) * j (w j , z j ) (x i , z j , α -ij ) P (y i , w j , β -ij )    ⇒ (x i , z j , α -ij ) P (y i , w j , β -ij ). ( 16
)
Proof Assume that the five premises of (15) are satisfied and none of the first four conclusions are. Using RC 1 j , we infer that (z j , w j ) * j (z j , w j ). Hence, from the fifth premise in (15), we deduce that (x i , z j , α -ij ) P (y i , w j , β -ij ), which is the fifth premise of BC . Applying BC we get (x i , z j , α -ij ) P (y i , w j , β -ij ), which establishes property (15).

The proof that ( 15) is equivalent with ( 16) is similar to that of Lemma 38 (assuming that P satisfies RC 1). P Condition (15) can be interpreted in the following way. Suppose that all the premises of the condition hold. Suppose furthermore that the first four conclusions are false. This is easily seen to imply that the differences (x i , y i ) and (z j , w j ) both act as bonuses. The last conclusion therefore implies that, replacing a bonus on i ∈ N by a relation P i (that may or not be a bonus) and replacing a relation P j on j ∈ N (that may or not be a bonus) by a bonus on j has no effect since at least one bonus is present. Property (15) ensures that bonuses can be exchanged between attributes. A bonus on i ∈ N has a similar effect to that of a bonus on j ∈ N .

Vetoes and bonuses

We define on each i ∈ N a relation S i letting, for all x i , y i ∈ X i ,

x i S i y i ⇔ (x i , y i ) * i (y i , x i ). ( 17
)
The asymmetric (resp. symmetric) part of S i will be denoted by P i (resp. I i ). This is standard definition of S i already used for the study of CDR-AT in [START_REF] Bouyssou | An axiomatic analysis of concordance-discordance relations[END_REF]. We have:

Lemma 40

Let P be a binary relation on X = n i=1 X i satisfying RC 1 i . The relation S i on X i defined by (17) is complete. Moreover, if RC 2 i holds and x i I i y i and z i I i w i , then

(x i , y i ) ∼ * i (z i , w i ) ∼ * i (y i , x i ) ∼ * i (w i , z i ) ∼ * i (a i , a i ), for all a i ∈ X i . The relation P i is nonempty.
Proof RC 1 implies that * i is complete. Hence S i is complete. Using the definition of S i , x i I i y i and z i I i w i is equivalent to (x i , y i ) ∼ * i (y i , x i ) and (z i , w i ) ∼ * i (w i , z i ). The conclusion follows from Lemma 9.2. If P i is empty, we must have for all x i , y i , z i , w i ∈ X i , x i I i y i and z i I i w i . This implies (x i , y i ) ∼ * i (z i , w i ), violating the fact that attribute i ∈ N is influential. P

The definition of the relation V i requires more care. Indeed, it includes at the same time cases of vetoes and cases of bonuses. The relation V i will model vetoes. The relation B i will model bonuses. The necessity to define separately the relations V i and B i comes from the fact that one can built degenerate examples in which B i is nonempty while V i is empty (in that case all negative differences act as a veto). Similarly there are cases in which B i is empty but V i is not (e.g., when the relation only contains N N .)

Define the relation V i on X i letting, for all x i , y i ∈ X i

x i V i y i ⇔ (z i , w i ) * i (w i , z i ) * i (y i , x i ) for some z i , w i ∈ X i . (18)
We have:

Lemma 41

Let P be a binary relation on X = n i=1 X i satisfying RC 1, RC 2, and Maj 3. We have:

1. V i ⊆ P i , 2. [x i V i y i and z i V i w i ] ⇒ (y i , x i ) ∼ * i (w i , z i ), 3. [x i P i y i , z i P i w i , Not[x i V i y i ] and Not[z i V i w i ]] ⇒ (y i , x i ) ∼ * i (w i , z i ).
Proof Part 1. Suppose that x i V i y i , so that (z i , w i ) * i (w i , z i ) * i (y i , x i ), for some z i , w i ∈ X i . Suppose that Not[x i P i y i ] so that (y i , x i ) * i (x i , y i ). Using RC 1 and RC 2, it is easy to check that (z i , w i

) * i (w i , z i ) implies (z i , w i ) * i (a i , a i ) * i (w i , z i )
, for all a i ∈ X i . We therefore obtain (a i , a i ) * i (y i , x i ) * i (x i , y i ). This contradicts RC 2, using Lemma 9.2.

Part 2. Suppose that x i V i y i and z i V i w i . In view of ( 18), Lemma 28 implies that (w i , z i ) * i (y i , x i ) and (y i , x i ) * i (w i , z i ) so that (w i , z i ) ∼ * i (y i , x i ). Part 3. By definition, we have (x i , y i ) * i (y i , x i ) and (z i , w i ) * i (w i , z i ). Suppose that (y i , x i ) * i (w i , z i ). This would imply (x i , y i

) * i (y i , x i ) * i (w i , z i ), contradicting the fact that Not[z i V i w i ]. Similarly it is impossible that (w i , z i ) * i (y i , x i ). Hence, we have (y i , x i ) ∼ * i (w i , z i ). P Remark 42
Assuming RC 1, RC 2 and Maj 3, observe that, if V i is nonempty, then there exists z i , w i ∈ X i such that z i P i w i and Not[z i V i w i ]. Indeed, since V i is nonempty, we know that there are x i , y i ∈ X i such that (z i , w i ) * i (w i , z i ) * i (y i , x i ). Hence, we know that z i P i w i . Suppose now that z i V i w i , so that there are r i , s i ∈ X i such that (r i , s i ) * i (s i , r i ) * i (w i , z i ). This implies (w i , z i ) * i (y i , x i ), violating Lemma 28.

•

Define the relation B i on X i letting, for all x i , y i ∈ X i

x i B i y i ⇔ (x i , y i ) * i (z i , w i ) * i (w i , z i ) for some z i , w i ∈ X i . (19)
Lemma 43

Let P be a binary relation on X = n i=1 X i satisfying RC 1, RC 2, Maj 3, Maj 4, and Maj 5. We have:

1. B i ⊆ P i . 2. z i B i w i and x i B i y i imply (z i , w i ) ∼ * i (x i , y i ). 3. z i B i w i and x i B i y i imply (w i , z i ) ∼ * i (y i , x i ). 4. z i P i w i , Not[z i B i w i ], x i P i y i and Not[x i B i y i ], imply (z i , w i ) ∼ * i (x i , y i ). 5. z i B i w i , x i P i y i , Not[x i B i y i ] imply (z i , w i ) * i (x i , y i ). Proof Part 1. Suppose that x i B i y i , so that (x i , y i ) * i (z i , w i ) * i (w i , z i ),
for some z i , w i ∈ X i . Suppose that Not[x i P i y i ] so that (y i , x i ) * i (x i , y i ). Using RC 1 and RC 2, it is easy to check that (z i , w i ) * i (w i , z i ) implies (z i , w i ) * i (a i , a i ) * i (w i , z i ), for all a i ∈ X i . We therefore obtain (y i , x i ) * i (x i , y i ) * i (a i , a i ). This contradicts RC 2 (Lemma 9.2).

Part 2. Suppose that z i B i w i and x i B i y i . In view of ( 19), Lemma 33 implies (z i , w i ) * i (r i , s i ) and (x i , y i ) * i (r i , s i ), for all r i , s i ∈ X i . This implies (z i , w i ) ∼ * i (x i , y i ). Part 3. Suppose that z i B i w i and x i B i y i . Lemma 32 implies (r i , s i ) * i (w i , z i ) and (r i , s i ) * i (y i , x i ), for all r i , s i ∈ X i . This implies (w i , z i ) ∼ * i (y i , x i ). Part 4. Suppose that

z i P i w i , Not[z i B i w i ], x i P i y i and Not[x i B i y i ]. This implies that (z i , w i ) * i (w i , z i ) and (x i , y i ) * i (y i , x i ). If (z i , w i ) * i (x i , y i ), we obtain z i B i w i , a contradiction. Similarly, it is impossible that (x i , y i ) * i (z i , w i ). Hence,we must have (x i , y i ) ∼ * i (z i , w i ). Part 5. Suppose that z i B i w i , x i P i y i , Not[x i B i y i ]. This implies (z i , w i ) * i (a i , b i ) * i (b i , a i ), for some a i , b i ∈ X i , and (x i , y i ) * i (y i , x i ). If (x i , y i ) * i (z i , w i ), we obtain (x i , y i ) * i (a i , b i ) * i (b i , a i ), implying that x i B i y i , a contradiction. P Remark 44
Observe that if B i is nonempty then there exist z i , w i ∈ X i such that z i P i w i and Not[z i B i w i ].

Assuming that B i is nonempty, we know that there are x i , y i ∈ X i such that (x i , y i ) * i (z i , w i ) * i (w i , z i ). Hence, we know that z i P i w i . It is clearly impossible that z i B i w i , since by Lemma 33, this would imply that (z i , w i ) * i (r i , s i ), for all r i , s i ∈ X i , contrary to the fact that (x i , y i ) * i (z i , w i ).

•

Let us now define the relation V i on X i , letting, for all x i , y i ∈ X i ,

x i V i y i ⇔ [x i B i y i or x i V i y i ]. (20)
Combining Lemma 43.1 with Lemma 41.1 shows that V i ⊆ P i .

The main result

The main result of this note is the following.

Theorem 45 (Characterization of AP-R-CDR) Let P be a binary relation on X = n i=1 X i and assume that all attributes are influential for P. Then P is an AP-R-CDR-AT iff P is an asymmetric relation satisfying RC 1, RC 2, MM 3, MM 4, MM 5, BC , AC 1, AC 2, and AC 3. If V [x, y] ⊇ V [z, w], we know that (x i , y i ) * i (z i , w i ), for all i ∈ N . Since Not[x P y] and z P w, this is contradictory (see Lemma 10).

Otherwise, we repeatedly use BC to build alternatives z and w such that

A = S [z , w ], B = S [w , z ], z P w and V [w , z ] contains a single attribute. Suppose for definiteness that {k} = V [w , z ]. If k ∈ V [x, y],
we have (x i , y i ) * i (z i , w i ), for all i ∈ N , contradicting the fact that Not[x P y] and z P w. If k / ∈ V [x, y], we use property (15), defined in Lemma 39, to build alternatives z and w such that

A = S [z , w ], B = S [w , z ], z P w and { } = V [w , z ] ⊆ V [x, y]
. Hence, we have (x i , y i ) * i (z i , w i ), for all i ∈ N , contradicting the fact that Not[x P y] and z P w.

This shows that, with our definitions, (10-11) hold.

Let us now show that the relation ¤ = £ ∪ defined on the set of subsets of N having N for union is monotonic, i.e., satisfies (2).

Suppose that A £ B. It is easy to see that the proof used in [START_REF] Bouyssou | An axiomatic approach to TACTIC[END_REF] can be used to show that £ is monotonic. Indeed, the set of all x, y ∈ X such that V Let E = C \ A. We have B ⊇ E. We build z, w ∈ X with S [z, w] = C ¤ S [w, z] = B. We know that for all a i ∈ X i , we have a i I i a i . Using such pairs, define z , w ∈ X as follows:

A E B \ E z x i a i x i w y i a i y i It is clear that (z i , w i ) * i (x i , y i ), for all i ∈ N . Hence, we have z P w . Since C ∪ D = N , we have B \ D ⊆ C. Let F = B \ D.
For all i ∈ N , P i is not empty so that we can take, for all i ∈ F , any a i , b i ∈ X i such that a i P i b i . Using such pairs, define z , w ∈ X as follows:

29 C \ F F D z z i a i z i w w i b i w i
It is clear that (z i , w i ) * i (z i , w i ), for all i ∈ N . Hence, we have z P w . Let us finally show that (S i , U i ) form a homogeneous chain of semiorders. We already know that both S i and U i are complete and that V i is included in P i . In view of Remark 3, all we have to show is that there is a weak order T i on X i such that:

x i T i y i ⇒ ∀z i ∈ X i , [y i S i z i ⇒ x i S i z i ] and [z i S i x i ⇒ z i S i y i ], and x i T i y i ⇒ ∀z i ∈ X i , [y i V i z i ⇒ x i V i z i ] and [z i V i x i ⇒ z i V i y i ].
Let us show that the weak order T i can be taken to be ± i , this relation being a weak order due to AC 1, AC 2, and AC 3.

Suppose that

a i S i b i so that (a i , b i ) * i (b i , a i ). Suppose furthermore that x i ± i a i . By construction x i ± i a i implies x i + i a i , which is equivalent to saying that (x i , c i ) * i (a i , c i ), for all c i ∈ X i . Taking c i = b i , we obtain (x i , b i ) * i (a i , b i ). Similarly, x i ± i a i implies x i - i a i , which is equivalent to saying that (c i , a i ) * i (c i , x i ), for all c i ∈ X i . Taking c i = b i , we obtain (b i , a i ) * i (b i , x i ). Hence, we have (x i , b i ) * i (a i , b i ) * i (b i , a i ) * i (b i , x i ), so that (x i , b i ) * i (b i , x i ) and x i S i b i . The proof that b i S i a i and a i ± i x i imply b i S i x i is similar. Suppose now that a i V i b i , so that either a i V i b i or a i B i b i . Suppose that a i V i b i , so that (c i , d i ) * i (d i , c i ) * i (b i , a i ), for some c i , d i ∈ X i . Suppose furthermore that x i ± i a i . By construction, x i ± i a i implies x i - i a i , which is equivalent to saying that (e i , a i ) * i (e i , x i ), for all e i ∈ X i . Taking e i = b i , we obtain (b i , a i ) * i (b i , x i ). Hence, we have (c i , d i ) * i (d i , c i ) * i (b i , a i ) * i (b i , x i ). This implies x i V i b i . The proof that b i V i a i and a i ± i x i imply b i V i x i is similar. Suppose finally that a i B i b i , so that (a i , b i ) * i (c i , d i ) * i (d i , c i ), for some c i , d i ∈ X i . Suppose furthermore that x i ± i a i . By construction x i ± i a i implies x i + i a i , which is equivalent to saying that (x i , c i ) * i (a i , c i ), for all c i ∈ X i . Taking c i = b i , we obtain (x i , b i ) * i (a i , b i ). Hence, we have (x i , b i ) * i (a i , b i ) * i (c i , d i ) * i (d i , c i ), so that x i B i b i . The proof that b i B i a i and a i ± i x i imply b i B i x i is
similar. This completes the proof. P

Remark 46

An easy corollary of the above result is that P is an AP-R-CDR iff it is asymmetric and satisfies RC 1, RC 2, Maj 3, Maj 4, Maj 5, and BC . Indeed, in the above proof, conditions AC 1, AC 2, and AC 3 (via the fact that they imply that ± i is a weak order) are only used to show that (S i , U i ) is a homogeneous chain of semiorders. •

The above result uses 9 conditions. It would be of minor interest if these 9 conditions were not independent. We show below that this is indeed the case in the class of asymmetric relations, i.e., the class of relations of interest for the study of AP-R-CDR-AT.

Proposition 47

In the class of asymmetric relations, conditions RC 1, RC 2, AC 1, AC 2, AC 3, MM 3, MM 4, MM 5, and BC are independent.

Proof

We need 9 examples. [START_REF] Bouyssou | On the relationship between strict and non-strict outraking relations[END_REF] have shown that conditions RC 1, RC 2, AC 1, AC 2, AC 3, MM 1 and MM 3 are independent in the class of asymmetric relations.

We know from Lemma 30 that MM 1 implies MM 4 and MM 5. Moreover, we know from Lemma 37 that RC 1, RC 2, and MM 1 imply BC . Hence, the four examples in [START_REF] Bouyssou | On the relationship between strict and non-strict outraking relations[END_REF] concerning MM 3, AC 1, AC 2, AC 3 can be used here. This leaves us with 5 examples. We give them below in Section 4.6. P

Examples

We give below the 5 examples needed to complete the proof of Proposition 47.

Example 48 (Not[BC ]) Let X = 5 i=1 X i with X i = {x i , y i , z i }, for i = 1, 2 and X j = {x j , y j } for j = 3, 4, 5. We define P as follows. For all a, b ∈ X, we have a P b if 5 i=1 p i (a i , b i ) > 0, where p i is defined in the following table for all pairs (a i , b i ) in X i × X i . p i X 1 X 2 X j for j = 3, 4, 5 21 (x 2 , z 2 ) 11 (x 1 , z 1 ) 10 (x 1 , y 1 ), (y 1 , z 1 ) (x 2 , y 2 ), (y 2 , z 2 ) (x j , y j ) 0 (a 1 , a 1 ) (a 2 , a 2 ) (a j , a j ) -10 (y 1 , x 1 ), (z 1 , y 1 ) (y 2 , x 2 ), (z 2 , y 2 ) (y j , x j ) -100

(z 1 , x 1 ) (z 2 , x 2 )
It is easy to check that relation P is asymmetric, mainly because the opposite (z 1 , x 1 ) and (z 2 , x 2 ) of the bonus pairs (x 1 , z 1 ) and (x 2 , z 2 ) play the rôle of vetoes. Indeed, due to the fact that p 1 (z 1 , x 1 ) = p 2 (z 2 , x 2 ) = -100, these pairs are incompatible with relation P.

For i = 1, 2, 3, 4, 5, we have * i = * * i , which are the weak orders induced by the values assigned to p i in the above table. Hence P satisfies RC 1 and RC 2. It is easy to check that AC 1, AC 2, and AC 3 hold.

(z, w), the third premise never holds, so that the condition is trivially satisfied. If (z 1 , w 1 ) = (z, y), it is easy to check that there are no a -1 , b -1 ∈ X -1 such that (y 1 , a -1 ) P (x 1 , b -1 ), Not[(x 1 , a -1 ) P (y 1 , b -1 )] and Not[(z 1 , a -1 ) P (w 1 , b -1 )], so that no violation of M 3 1 is possible in this case. Q

Discussion

We have analyzed and characterized binary relations P on product sets that can be obtained as the asymmetric part of an outranking relation S. We have seen that these relations are more complex than outranking relations. Indeed, they can be seen as outranking relations only in degenerate cases. Consider two alternatives (x i , a -i ) and (y i , b -i ) that are such that there is no relation V j on the attributes j = i. This complexity stems from the fact that y i V i x i can have two different effects. If S [(x i , a -i ), (y i , b -i )] £ S [(y i , b -i ), (x i , a -i )], then y i V i x i acts as a normal veto. It forbids to have (x i , a -i ) P (y i , b -i ) because the negative preference difference between y i and x i is "too large". If S [(x i , a -i ), (y i , b -i )]

S [(y i , b -i ), (x i , a -i )] then y i V i x i acts as a bonus. It implies that (y i , b i ) P (x i , a i ), because it forbids to have (x i , a -i ) S (y i , b -i ). This makes an AP-R-CDR-AT an object that is far more complex than an outranking relation. This is reflected in our analysis by the fact that conditions MM 4, MM 5 and BC are complex conditions, even though it remains possible to interpret them in terms of the relation * i . This complexity also explains the difference between the pseudodisjunctive (also known as "optimistic") and pseudo-conjunctive (also known as "pessimistic") versions of ELECTRE TRI-B. While the latter uses a reflexive outranking relation (i.e., an R-CDR-AT), the former uses an AP-R-CDR-AT. Because these two objects are different, we should not be surprised by the fact that the theoretical analysis of the pseudo-conjunctive version given in Bouyssou and Marchant (2007a,b) does not carry over to the pseudo-disjunctive version. Similarly, we should not be surprised by the fact that most of elicitation techniques developed for the parameters of ELECTRE TRI-B only deal with the pseudo-conjunctive version (see [START_REF] Cailloux | Eliciting ELECTRE TRI category limits for a group of decision makers[END_REF][START_REF] Damart | Supporting groups in sorting decisions: Methodology and use of a multi-criteria aggregation / disaggregation DSS[END_REF][START_REF] Dias | ELECTRE TRI for groups with imprecise information on parameter values[END_REF]Dias andMousseau, 2003, 2006;[START_REF] Dias | An aggregation / disaggregation approach to obtain robust conclusions with ELECTRE TRI[END_REF][START_REF] Leroy | Learning the parameters of a multiple criteria sorting method[END_REF][START_REF] Mousseau | Valued outranking relations in ELECTRE providing manageable disaggregation procedures[END_REF][START_REF] Mousseau | Inferring an ELECTRE TRI model from assignment examples[END_REF][START_REF] Mousseau | A user-oriented implementation of the ELECTRE TRI method integrating preference elicitation support[END_REF][START_REF] Mousseau | Using assignment examples to infer weights for ELECTRE TRI method: Some experimental results[END_REF][START_REF] Mousseau | Resolving inconsistencies among constraints on the parameters of an MCDA model[END_REF][START_REF] Ngo The | Using assignment examples to infer category limits for the ELECTRE TRI method[END_REF]. There has been a number of recent works proposing elicitation techniques for the pseudo-disjunctive version (see [START_REF] Zheng | Preference Elicitation for reference based aggregation models: Algorithms and Procedures[END_REF][START_REF] Zheng | Learning an optimistic ELECTRE TRI sorting rule[END_REF]. These exceptions do not invalidate the above remark, since these elicitation techniques are far more complex than the ones developed for the pseudo-conjunctive version (they use MILP instead of LP). For more details on this point, we refer to [START_REF] Bouyssou | Some remarks on ELECTRE TRI[END_REF].

A clear limitation of the present work as well as our previous works on outranking relations is that it only deals with crisp relations. Since there are outranking methods such as ELECTRE III [START_REF] Roy | ELECTRE III : un algorithme de classement fondé sur une représentation floue des préférences en présence de critères multiples[END_REF] or PROMETHEE [START_REF] Brans | A preference ranking organisation method. (The PROMETHEE method for multiple criteria decision-making)[END_REF][START_REF] Brans | How to select and how to rank projects: the PROMETHEE method[END_REF]) that use valued relations, an important direction for future research would be to analyze such relations. Although this will surely imply the development of a framework different from the ones used here, this does not seem to be out of reach.

  Part[⇐] of(10)(11). Let A, B ⊆ N such that A ∪ B = N . Because P i is nonempty (since all attributes are influential for P), we know that there are x, y ∈ X such that A = S [x, y] and B = S [y, x]. If A £ B and V [y, x] = ∅, we have, by construction, x P y. Suppose now that A B, V [y, x] = ∅ and V [x, y] = ∅ and Not[x P y]. By construction, we know that there are z, w ∈ X such that z P w, V [w, z] = ∅, A = S [z, w] and B = S [w, z].

  [y, x] = ∅, A = S [x, y] and B = S [y, x] must contain alternatives z, w ∈ X such that V [w, z] = ∅, A = S [z, w], B = S [w, z], and V [z, w] = ∅. Suppose that A B. By construction, we know that there are x, y ∈ X such that A = S [x, y], B = S [y, x], and x P y. Suppose that C ⊇ A, B ⊇ D such that C ∪ D = N . Let us show that there are z, w ∈ X such that C = S [z, w], D = S [w, z], and z P w, which will complete the proof.

CNRS, LAMSADE, UMR 7243 & Université Paris Dauphine, Place du Maréchal de Lattre de Tassigny, F-75775 Paris Cedex 16, France, tel: +33 1 44 05 48 98, fax: +33 1 44 05 40 91, e-mail: bouyssou@lamsade.dauphine.fr.

Université de Mons, Faculté Polytechnique, 9, rue de Houdain, B-7000 Mons, Belgium, tel: +32 65

374682, fax: +32 65 374689, e-mail: marc.pirlot@umons.ac.be.

As noted in[START_REF] Bouyssou | On the relationship between strict and non-strict outraking relations[END_REF], this definition also applies to reflexive outranking relations.

Proof

Necessity was shown above. We show sufficiency.

Define the relation S i and V i on X i as above (formulas ( 17), ( 18), ( 19), ( 20)). We have shown above that S i is complete, that P i is nonempty and that V i is included in P i .

Consider any two subsets A, B ⊆ N such that A ∪ B = N and let:

A £ B ⇔ [x P y, for all x, y ∈ X such that S [x, y] = A, S [y, x] = B, and V [y, x] = ∅].

Similarly, Consider any two subsets A, B ⊆ N such that A ∪ B = N and let:

A B ⇔

x P y, Not[z P w], for some x, y, z, w ∈ X such that

Let us show that, with the previous definitions of S i , V i and ¤, (10-11) holds for P.

Part [⇒] of (10)(11). Suppose that x P y. Using Lemma 28, we know that it is impossible that y i V i x i , for some i ∈ N . Similarly, using Lemma 32, it is impossible that y i B i x i , for some i ∈ N . In view of ( 20 Let us show that we must have x i B i y i , for some i ∈ N .

We have

For all i ∈ N such that x i I i y i , we have, using Lemma 40, (x i , y i ) ∼ * * i (z i , w i ). We have

We have x i P i y i ⇔ z i P i w i . Suppose that there is no j ∈ N such that x j B j y j . Using Parts 4 and 5 of Lemma 43, this implies that (z i , w i ) * i (x i , y i ), for all i ∈ N such that x i P i y i .

We have (z i , w i ) * i (x i , y i ), for all i ∈ N . This is contradictory since x P y and Not[z P w] (see Lemma 10). Hence, we must have x j B j y j , for some j ∈ N . We therefore have S

The only cases of super negative pairs, i.e., pairs (c i , d i ) such that there are elements a

, are again (z 1 , x 1 ) and (z 2 , x 2 ). These pairs, as already observed, play the rôle of vetoes. They are therefore incompatible with relation P, which, in view of Lemma 28, entails that P satisfies Maj 3.

Since (z 1 , x 1 ) and (z 2 , x 2 ) are the opposite of the only two bonus pairs and are never involved in preferences, using Lemma 32 shows that P satisfies Maj 4. Using Lemma 33, it is also clear that Maj 5 holds. Hence, MM 4 and MM 5 hold.

In view of Lemma 38, property BC ij is trivially satisfied for all {i, j} = {1, 2}. Using the same lemma, we see that this example violates BC 12 since we have (

The relation P is asymmetric, since the opposite (y 1 , x 1 ) and (z 1 , x 1 ) of the bonus pairs (x 1 , y 1 ) and (x 1 , z 1 ) are never involved in pairs belonging to P.

For all i, * i is the weak order induced by p i in the above table. For i = 2, 3, * i = * * i while * * 1 separates the bottom class of * 1 in two classes since (y 1 , x 1 ) * * 1 (z 1 , x 1 ). Hence P satisfies RC 1 and RC 2. It is easy to check that AC 1, AC 2, and AC 3 hold.

MM 3 i is trivially satisfied for i = 2, 3 (in view of Lemma 28). For i = 1, the only super negative pairs are (y 1 , x 1 ) and (z 1 , x 1 ) and they are never involved in P. Therefore, using Lemma 28, we have that Maj 3 1 and, hence, MM 3 i , hold.

Maj 4 i is trivially satisfied for i = 2, 3. For i = 1, the only bonus pairs are (x 1 , y 1 ) and (x 1 , z 1 ) and their opposite pairs are never involved in P. Therefore, applying Lemma 32 yields Maj 4 1 and, hence, MM 4.

Maj 5 i and, hence, MM 5 i are trivially satisfied for i = 2, 3 but this example violates Maj 5 1 . Indeed, we have (x 1 , y 1 ) * 1 (y 1 , z 1 ) * 1 (z 1 , y 1 ) but there is a pair 32 above (x 1 , y 1 ) in * 1 , namely, (x 1 , z 1 ) * 1 (x 1 , y 1 ). Since, RC 1 and RC 2 hold, this implies a violation of MM 5 1 (Lemma 33).

In view of Lemma 38, property BC ij is trivially satisfied for all i = j since bonuses occur on the sole attribute X 1 . Q

Example 50 (Not[MM 4]) Let X = 3 i=1 X i with X 1 = {x 1 , y 1 , z 1 } and X j = {x j , y j } for j = 2, 3. The relation P is defined as follows. For all a, b ∈ X, we have a P b if 3 i=1 p i (a i , b i ) > 0, where p i is defined in the following table for all pairs (a i , b i ) in

Hence, at most one of the pairs (a, b) or (b, a) belongs to P. If a 1 = x 1 and b 1 = z 1 , there is only one case in which we have b P a, namely (z 1 , x 2 , x 3 ) P (x 1 , y 2 , y 3 ). In this case, we do not have a P b since Not[(x 1 , y 2 , y 3 ) P (z 1 , x 2 , x 3 )]. Relation P is thus asymmetric. For all i, * i is the weak order induced by function p i defined in the above table. For i = 2, 3, * i = * * i while * * 1 separates the bottom class of * 1 in two classes since [(y 1 , x 1 ) ∼ * * 1 (z 1 , y 1 )] * * 1 (z 1 , x 1 ). Hence P satisfies RC 1 and RC 2. It is easy to check that AC 1, AC 2, and AC 3 hold.

Maj 3 i and, hence, MM 3 i are trivially satisfied for all i since there are no super negative pairs at all (Lemma 28).

Maj 4 i and, hence, MM 4 i are trivially satisfied for i = 2, 3. Maj 4 1 is violated for i = 1. Indeed, we have (x 1 , z 1 ) * 1 (x 1 , y 1 ) * 1 (y 1 , x 1 ) while (z 1 , x 2 , x 3 ) P (x 1 , y 2 , y 3 ), which, combined with Lemma 32, implies that Maj 4 1 is not true. Since RC 1 and RC 2 hold, this implies a violation of MM 4 1 .

Maj 5 i is trivially satisfied for i = 2, 3. For i = 1, (x 1 , z 1 ) is the only bonus and for all (r 1 , s 1 ), we have (x 1 , z 1 ) * 1 (r 1 , s 1 ). Therefore, using Lemma 33, we have established that Maj 5 1 and, hence, MM 5 i hold.

In view of Lemma 38, property BC ij is trivially satisfied for all i = j since a bonus occurs on the sole attribute

b} and X 2 = {x, y}. Let P be empty except that we have (a, x) P (a, y) and (a, x) P (b, y). The relation is clearly asymmetric.

On attribute 1, we have [(a, a)

. This shows that RC 1 1 holds but that RC 2 1 is violated. We have a + 1 b and a - 1 b. Hence, AC 1 1 , AC 2 1 and AC 3 1 hold. It is easy to check that UC 1 and LC 1 hold so that MM 3 1 , MM 4 1 , MM 5 1 , and BC 12 hold. On attribute 2, we have (x, y) * 2 [(x, x) ∼ * 2 (y, x) ∼ * 2 (y, y)]. This shows that RC 1 2 and RC 2 2 hold. We have x + 2 y and x - 2 y. Hence, AC 1 2 , AC 2 2 and AC 3 2 hold. It is easy to check that UC 2 and LC 2 hold so that MM 3 2 , MM 4 2 , MM 5 2 , and BC 21 hold. Q

Example 52 (Not[RC 1]) (This is also Example 92 in [START_REF] Bouyssou | On the relationship between strict and non-strict outraking relations[END_REF]). Let X = X 1 × X 2 × X 3 with X 1 = {x, y, z, w}, X 2 = {a, b} and X 3 = {p, q}. Let P be such that (α, a, p) P (β, a, q), (α, a, p) P (β, b, p), (α, a, p) P (β, b, q), (α, a, q) P (β, b, q), (α, b, p) P (β, b, q), for all (α, β) ∈ Γ 1 = X 2 1 \ {(x, y), (z, y), (z, w)}. We add the following pairs: (x, a, p) P (y, b, p), (x, a, p) P (y, b, q), (x, a, q) P (y, b, q), and (z, a, p) P (w, a, q), (z, a, p) P (w, b, q), (z, b, p) P (w, b, q). This relation has a total of 71 ordered pairs. It is easy to check that it is asymmetric.

On attribute 2, we have b, a). This shows that RC 1 2 and RC 2 2 hold. We have a + 2 b and a - 2 b. Hence, AC 1 2 , AC 2 2 and AC 3 2 hold. It is easy to check that UC 2 and LC 2 hold so that MM 3 2 , MM 4 2 , MM 5 2 , BC 21 , and BC 23 hold.

On attribute 3, we have (p, q) * 3 [(p, p) ∼ * 3 (q, q)] * 3 (q, p]. This shows that RC 1 3 and RC 2 3 hold. We have p + 3 q and p - 3 q. Hence, AC 1 3 , AC 2 3 and AC 3 3 hold. It is easy to check that UC 3 and LC 3 hold so that MM 3 3 , MM 4 3 , MM 5 3 , BC 31 , and BC 32 hold.

On attribute 1, all ordered pairs, except (x, y), (z, y) and (z, w), are in the same equivalence class of ∼ * 1 and above these three pairs. The ordered pairs (x, y) and (z, w) are clearly incomparable w.r.t. * 1 and are both above (z, y). This shows that RC 1 1 fails but that RC 2 1 holds. It is not difficult to check that we have [y

Hence, AC 1 1 , AC 2 1 and AC 3 1 hold. It is easy to see that UC 1 holds. Hence, MM 4 1 , MM 5 1 , BC 12 , and BC 13 hold.

It remains to check that MM 3 1 holds. Let us check that M 3 1 holds. Suppose that (x 1 , a -1 ) P (y 1 , b -1 ), (y 1 , c -1 ) P (x 1 , d -1 ) and (z 1 , e -1 ) P (w 1 , f -1 ). We want to show that we have one of the following three relations: (y 1 , a -1 ) P (x 1 , b -1 ), (z 1 , a -1 ) P (w 1 , b -1 ), (z 1 , c -1 ) P (w 1 , d -1 ).

If (y 1 , x 1 ) ∈ Γ then the first conclusion always holds. If (y 1 , x 1 ) = (z, y), the second premise never holds, so that the condition is trivially satisfied. It remains to deal with the following two cases: (y 1 , x 1 ) = (x, y) and (y 1 , x 1 ) = (z, w). We deal with the first case, the treatment of the second being entirely similar.

Suppose that (y 1 , x 1 ) = (x, y). If (z 1 , w 1 ) = (z, y) and (z 1 , w 1 ) = (z, w), we have (z 1 , w 1 ) * 1 (x, y), so that the third conclusion always holds. If (z 1 , w 1 ) =