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

Abstract

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

1 Introduction

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

Most outranking methods, including the well known Electre methods (Roy 1968; Roy and Bertier 1973), base the comparison of alternatives on the so-called concordance & non-discordance principle. It leads to accepting the proposition that an alternative is “superior” to another if the following two conditions are fulfilled:

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

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

Stating that an alternative is “superior” to another may have two different meanings. In Electre methods, “superior” means “not worse”, i.e., “at least as good as”. Such methods aim at building a reflexive preference relation that is interpreted as an “at least as good as” relation. In general, such relations may lack nice transitivity or completeness properties (on these issues, see Bouyssou 1992, 1996).

In other outranking methods, like the Tactic method (Vansnick 1986), “superior” means “strictly better than”. Such methods build an asymmetric relation that is interpreted as strict preference. As in the reflexive case, the obtained relations are not necessarily transitive and they may have cycles.

The outranking relation produced by certain outranking methods (such as Electre III, Roy 1978, or Promethee, Brans and Vincke 1985) are valued relations. In this work we restrict ourselves to crisp outranking relations.

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

1.1 An overview of axiomatic work on outranking relations

The first contribution to the characterization of outranking relations is in the spirit of Fishburn’s (1976) study of noncompensatory preferences. In this model of preferences, the comparison of two alternatives only depends on the way they compare w.r.t. the various criteria and is independent of the other alternatives. Bouyssou and Vansnick (1986) and Bouyssou (1986) elaborate on this idea to obtain a characterization of a subclass of outranking relations. Fargier and Perny (2001) (see also Dubois et al. 2001, 2002, 2003) followed a similar path proposing a characterization of concordance relations, which appears to be limited to a subclass of concordance relations for which all attributes are essential (for a discussion including a simple example of a concordance relation w.r.t. which all attributes are inessential, see Bouyssou and Pirlot 2005b, Section 5.2).

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

Bouyssou and Pirlot (2002b) establish a characterization of strict (i.e., irreflexive) concordance relations in which axioms are formulated as cancelation conditions (i.e., without specifying explicitly the number of preference differences classes). In a communication at the FUR X Conference, Greco et al (2001) present cancelation conditions characterizing (non-strict) concordance relations. As pointed out in Bouyssou and Pirlot (2005b), section 5.1, these conditions are restrictive since they characterize a subclass of all outranking relations corresponding to those produced by the Electre I aggregation rule. Furthermore, their axioms do not enter in the general axiomatic framework outlined in Bouyssou et al. (1997) and Bouyssou and Pirlot (1999), which impedes a clear understanding of how outranking relations distinguish from those obtained by other aggregation rules.

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

In Bouyssou and Pirlot (2005b, 2007, 2009a), we successively describe reflexive concordance relations and concordance & non-discordance relations within the framework studied in Bouyssou and Pirlot (2002a, 2004b) by providing additional axioms that are independent of those defining the framework. In the continuation of Bouyssou and Pirlot (2002c) and within the same framework, we also deal with strict (irreflexive) concordance & non-discordance relations in Bouyssou and Pirlot (2005c, 2006).

Note that a different approach can be followed, which consists in characterizing the procedures used to produce outranking relations instead of the relations themselves. For studies following this path, the interested reader is referred to Pirlot (1997) and Marchant (2003, 2007) (see also Bouyssou et al. 2006, chapter 5).

1.2 Goal of the present paper

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

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

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

1.3 Preliminary remarks

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

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

• 2. While we study objects, namely concordance & non-discordance relations, that are involved in the Electre or Tactic methods, we do not aim at characterizing the final output of such methods. The latter methods’ characteristic is that they proceed in two steps. The first step yields a crisp binary relation which results from the comparison of all alternatives in pairs, independently of irrelevant ones. The second step exploits this, often intransitive and incomplete, relation in order to produce the expected sort of output, i.e., a complete ranking or a choice set. The result of the first step is called an outranking relation and we interpret it all along as a preference relation. The question of the transitivity of preferences is a controversial one, both as a rationality requirement and as experimental evidence (Tversky 1969; May 1954; Iverson and Falmagne 1985; Fishburn 1970; Van Acker 1990). In particular, it is possible to design experiments in which the decision maker is asked to make binary choices, without any mechanism forcing the transitivity or the completeness of the resulting relation. It would be interesting to test whether the resulting relations can be interpreted as a concordance & non-discordance relation. Regarding the incompleteness issue, recent experiments (Deparis et al. 2012) show that preferences may be incomplete when the decision maker is granted the possibility not to choose. Our standpoint, in this work, is that concordance & non-discordance relations could actually be observed in such situations.

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

2 Notation and definitions

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

A preference relation on a set $X$ is, in general, denoted by $\mathrel {\mathcal {R}}$. A binary relation $\mathrel {\mathcal {R}}$ on $X$ is said to be reflexive if $a \mathrel {\mathcal {R}}a$, for all $a\in X$. It is complete if $a \mathrel {\mathcal {R}}b$ or $b \mathrel {\mathcal {R}}a$, for all $a,b \in X$. Relation $\mathrel {\mathcal {R}}$ is asymmetric if $a \mathrel {\mathcal {R}}b \Rightarrow Not [b \mathrel {\mathcal {R}}a ]$, for all $a,b \in X$. It is transitive if $(a \mathrel {\mathcal {R}}b$ and $b \mathrel {\mathcal {R}}c) \Rightarrow a \mathrel {\mathcal {R}}c$, for all $a,b,c \in X$. It is Ferrers if $(a \mathrel {\mathcal {R}}b$ and $c \mathrel {\mathcal {R}}d) \Rightarrow (a \mathrel {\mathcal {R}}d$ or $c \mathrel {\mathcal {R}}b)$, for all $a,b,c,d \in X$. It is semi-transitive if $(a \mathrel {\mathcal {R}}b$ and $b \mathrel {\mathcal {R}}c) \Rightarrow (a \mathrel {\mathcal {R}}d$ or $d \mathrel {\mathcal {R}}c)$, for all $a,b,c,d \in X$. A weak order is a complete transitive relation. A semiorder is a reflexive Ferrers and semi-transitive relation. A pair of semiorders ($\mathrel {\mathcal {R}}_{1}, \mathrel {\mathcal {R}}_{2}$) on $X$ form a homogeneous chain of semiorders (Doignon et al. 1988) if ${\mathrel {\mathcal {R}}_{1}} \subseteq {\mathrel {\mathcal {R}}_{2}}$ and there is a weak order $\mathrel {\mathcal {T}}$ on $X$ such that, for $i=1,2$, we have

$$\begin{aligned} x \mathrel {\mathcal {T}} y \Rightarrow \text {for all } z \in X, \ [y \mathrel {\mathcal {R}}_{i} z \Rightarrow x \mathrel {\mathcal {R}}_{i} z] \text { and } [z \mathrel {\mathcal {R}}_{i} x \Rightarrow z \mathrel {\mathcal {R}}_{i} y]. \end{aligned}$$

(1)

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

• the dual (or inverse or reciprocal) $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{d}}$: $a \mathrel {\mathord {\mathrel {\mathcal {R}}}^{d}}b$ if $b \mathrel {\mathcal {R}}a$,

• the complement $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{c}}$: $a \mathrel {\mathord {\mathrel {\mathcal {R}}}^{c}}b$ if $Not [a \mathrel {\mathcal {R}}b ]$,

• the co-dual $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$: $a \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}b$ if $Not [b \mathrel {\mathcal {R}}a ]$,

• the asymmetric part $\mathrel {\mathord {\mathcal {R}}^{\alpha } }$: $a \mathrel {\mathord {\mathcal {R}}^{\alpha } }b$ if $a \mathrel {\mathcal {R}}b$ and $Not [b \mathrel {\mathcal {R}}a ]$,

• the symmetric part $\mathrel {\mathord {\mathcal {R}}^{\sigma } }$: $a \mathrel {\mathord {\mathcal {R}}^{\sigma } }b$ if $a \mathrel {\mathcal {R}}b$ and $b \mathrel {\mathcal {R}}a$,

• the symmetric complement $\mathrel {\mathord {\mathcal {R}}^{\rho } }$: $a \mathrel {\mathord {\mathcal {R}}^{\rho } }b$ if $Not [a \mathrel {\mathcal {R}}b ]$ and $Not [b \mathrel {\mathcal {R}}a ]$.

We recall a few straightforward properties of the co-dual operator, for they will be used in the sequel. The co-dual of a complete relation is its asymmetric part. The co-dual of an asymmetric relation is complete. The co-dual operator is an involution between the set of complete relations and the set of asymmetric ones. It also establishes an involution between reflexive and irreflexive relations (see Monjardet (1978) for proofs and many more results).

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

3 Variants of outranking relations

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

In order to avoid unnecessary minor complications, we restrict our attention to relations $\mathrel {\mathcal {R}}$ on $X= \prod _{i=1}^n X_{i}$ for which each attribute is influential. This requirement is a sort of non-triviality condition for attributes. We say that attribute $i \in N$ is influential (for $\mathrel {\mathcal {R}}$ ) if there are $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$ and $x_{-i}, y_{-i} \in X_{-i}$ such that $(x_{i}, x_{-i}) \mathrel {\mathcal {R}}(y_{i}, y_{-i})$ and $Not [(z_{i}, x_{-i}) \mathrel {\mathcal {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$.

3.1 Electre I

We describe how a reflexive outranking relation, interpreted as a non-strict preference, is built according to the Electre I method.¹ 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} \le vt_{i}$, we define the semiorders $\mathrel {S_{i}}$ and $\mathrel {U_{i}}$ as follows:² for all $x_{i}, y_{i} \in X_{i}$,

$$\begin{aligned} x_{i} \mathrel {S_{i}}y_{i}&\Leftrightarrow u_{i}(x_{i}) \ge u_{i}(y_{i}) - pt_{i} \end{aligned}$$

(2)

$$\begin{aligned} x_{i} \mathrel {U_{i}}y_{i}&\Leftrightarrow u_{i}(x_{i}) \ge u_{i}(y_{i}) - vt_{i}. \end{aligned}$$

(3)

The pair of relations $(\mathrel {S_{i}},\mathrel {U_{i}})$ on $X_{i}$ form a homogeneous nested chain of semiorders as defined in Sect. 2 (with the underlying weak order $T_{i}$ such that $x_{i} \mathrel {T_{i}} y_{i} \Leftrightarrow u_{i}(x_{i}) \ge u_{i}(y_{i})$). Relation $\mathrel {S_{i}}$ interprets as the “at least as good” relation on attribute $i$. The relation $\mathrel {P_{i}}$, the asymmetric part of $\mathrel {S_{i}}$, is interpreted as a “better than” relation. $pt_{i}$ is the preference threshold on attribute $i$. We read “$x_{i} \mathrel {U_{i}}y_{i}$” as “level $x_{i}$ is not unacceptably bad with respect to level $y_{i}$”. The relation $\mathrel {U_{i}}$ is a non-veto relation on attribute $i$. In contrast, the co-dual of $\mathrel {U_{i}}$ is the veto relation $\mathrel {V_{i}}$. It is defined as follows: for all $x_{i}, y_{i} \in X_{i}$,

$$\begin{aligned} y_{i} \mathrel {V_{i}}x_{i}&\Leftrightarrow Not [x_{i} \mathrel {U_{i}}y_{i} ]\nonumber \\&\Leftrightarrow u_{i}(x_{i}) < u_{i}(y_{i}) - vt_{i}. \end{aligned}$$

(4)

Hence $y_{i} \mathrel {V_{i}}x_{i}$ means that $y_{i}$ is far better than $x_{i}$.

In Electre I, the outranking relation $\mathrel {\mathcal {R}}$ is determined using positive weights $w_{i}$ attached to each attribute and a threshold $s$ with ($1/2 \le s \le 1)$, such that, for all $x, y \in X$,

$$\begin{aligned} x \mathrel {\mathcal {R}}y&\Leftrightarrow \frac{\sum _{ i \in \mathord {S}(x,y)} w_{i}}{\sum _{j \in N} w_{j}} \ge s \text { and } \mathord {V}(y,x)= \varnothing , \end{aligned}$$

(5)

where $\mathord {S}(x,y) = \lbrace i \in N: x_{i} \mathrel {S_{i}}y_{i}\rbrace$, the set of attributes on which $x$ is at least as good as $y$, and $\mathord {V}(y,x)= \{i \in N: y_{i} \mathrel {V_{i}}x_{i}\}$, the set of attributes on which $x$ is unacceptably bad as compared to $y$.

Outranking relations such as $\mathrel {\mathcal {R}}$ are reflexive, need not be complete and do not in general enjoy nice transitivity properties (Bouyssou 1996). As a consequence, deriving a recommendation to the decision maker on the basis of such relations is not straightforward. In order to do that, the analyst may use one of the so-called exploitation procedures (see Roy and Bouyssou 1993, Ch. 6, or Bouyssou et al. 2006, Ch. 7).

Remark 1

Note that we do not consider valued outranking relations such as those obtained by the Electre III (see Roy 1978; Roy and Bouyssou 1993, pp. 284–289) and the Promethee (Brans and Vincke 1985) methods. This is due to the fact that the tools currently developed in the framework of conjoint measurement theory only deal with crisp relations. In contrast, our analysis does encompass the crisp outranking relations produced by the Electre II method. We do not develop this point further for the sake of conciseness.$\square$

3.2 Outranking relations

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

Definition 2

(Concordance–discordance relation (CDR)) A binary relation $\mathrel {\mathcal {R}}$ on $X= \prod _{i=1}^n {X_{i}}$ is a concordance–discordance relation (CDR) if there are:

• 1. a complete binary relation $\mathrel {S_{i}}$ on each $X_{i}$ $(i = 1, 2, \dots , n)$ (with asymmetric part $\mathrel {P_{i}}$ and symmetric part $\mathrel {I_{i}}$),

• 2. an asymmetric binary relation $\mathrel {V_{i}}$ on each $X_{i}$ $(i = 1, 2, \dots ,n)$ such that ${\mathrel {V_{i}}} \subseteq {\mathrel {P_{i}}}$,

• 3. a binary relation $\mathrel {\unrhd }$ between subsets of $N$ having $N$ for union that is monotonic w.r.t. inclusion, i.e., for all $A, B, C, D \subseteq N$ with $A \cup B = N$ and $C \cup D = N$,

  $$\begin{aligned}{}[A \mathrel {\unrhd }B, C \supseteq A, B \supseteq D] \Rightarrow C \mathrel {\unrhd }D, \end{aligned}$$

  (6)

such that, for all $x, y \in X$,

$$\begin{aligned} x \mathrel {\mathcal {R}}y \Leftrightarrow \left[ \mathord {S}(x,y) \mathrel {\unrhd }\mathord {S}(y,x) \text { and } \mathord {V}(y,x)= \varnothing \right] , \end{aligned}$$

(7)

where $\mathord {S}(x,y) = \lbrace i \in N: x_{i} \mathrel {S_{i}}y_{i}\rbrace$ and $\mathord {V}(y,x)= \lbrace i \in N: y_{i} \mathrel {V_{i}}x_{i} \rbrace$.

We say that $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$ is a type I representation of $\mathrel {\mathcal {R}}$ as a CDR.

A concordance relation (CR) is a CDR in which the $\mathrel {V_{i}}$ relations are all empty.³

As explained in Bouyssou and Pirlot (2009a), the type I representation $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$ of a CDR may not be unique. This is true even if all attributes are supposed to be influential. When we speak below of a representation of type I $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$ of a CDR, we mean one possible representation of type I of the CDR. As detailed in Bouyssou and Pirlot (2005b, 2007) the situation is different with CR. When all attributes are influential, they have a unique representation of type I. Similar remarks will hold for the representations of type II introduced below.

In the above definition, for each attribute $i$, $\mathrel {S_{i}}$ is interpreted as a non-strict preference relation on $X_{i}$. The asymmetric part $\mathrel {P_{i}}$ of $\mathrel {S_{i}}$ is the strict preference on $X_{i}$ and $\mathrel {V_{i}}$ is the veto relation. Relation $\mathrel {\unrhd }$ is used in pairwise comparisons of alternatives, it compares coalitions of attributes in terms of their importance: if $A$ and $B$ denote subsets of attributes, $A \mathrel {\unrhd }B$ reads “the coalition of attributes $A$ is at least as important as the coalition $B$”. In the sequel, we shall use the notation $\mathrel {\rhd }$ (resp. $\mathrel {\triangleq }$) to denote the asymmetric (resp. symmetric) part of $\mathrel {\unrhd }$. Consequently, $A \mathrel {\rhd }B$ (resp. $A \mathrel {\triangleq }B$) reads “the coalition of attributes $A$ is strictly more important (resp. equally important as) coalition $B$).

It is easy to see that the outranking relation of Electre I satisfies the above definition. In particular,⁴ the relation $\mathrel {\unrhd }$ is defined by:

$$\begin{aligned} A \mathrel {\unrhd }B \text { if } \frac{\sum _{ i \in A} w_{i}}{\sum _{j \in N} w_{j}}\ge s. \end{aligned}$$

Rule (5) implies that the relation built in the Electre I procedure is reflexive.

Remark 3

(Outranking relations with attribute transitivity) Due to (2) and (3), relations $\mathrel {S_{i}}$ and $\mathrel {V_{i}}$ in Electre I have additional properties, namely $\mathrel {S_{i}}$ is a semiorder, $\mathrel {V_{i}}$ is the asymmetric part of the semiorder $\mathrel {U_{i}}$ and $\mathrel {S_{i}}$ and $\mathrel {U_{i}}$ form a homogeneous chain of two semiorders. Concordance discordance relations with these additional properties have been defined and characterized in Bouyssou and Pirlot (2009a) under the name reflexive concordance–discordance relations with attribute transitivity (R-CDR-AT). When required, the suffix “-AT” will be added to acronyms characterizing outranking relations, meaning that the corresponding relations also have the attribute transitivity property.$\square$

Remark 4

(Concordance and non-discordance relations) Condition (7) explicitly defines an outranking relation as a relation that satisfies two rules: a concordance rule ($\mathord {S}(x,y) \mathrel {\unrhd }\mathord {S}(y,x)$) and a non-discordance rule ($\mathord {V}(y,x)\ne \varnothing$). Alternatively, an outranking relation $\mathrel {\mathcal {R}}$ can be viewed as the intersection of two relations: a concordance relation $\mathrel {\mathcal {C}(\mathrel {\mathcal {R}})}$ and a non-discordance relation. The concordance relation $\mathrel {\mathcal {C}(\mathrel {\mathcal {R}})}$ is defined by $x \mathrel {\mathcal {C}(\mathrel {\mathcal {R}})} y$ if $\mathord {S}(x,y) \mathrel {\unrhd }\mathord {S}(y,x)$. The non-discordance relation $\mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})}$ is defined by $x \mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})} y \text { if } \mathord {V}(y,x)= \varnothing$. Hence, we have $x \mathrel {\mathcal {R}}y \text { iff } [ x \mathrel {\mathcal {C}(\mathrel {\mathcal {R}})} y \text { and } x \mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})} y]$.

Note that the concordance relation $\mathrel {\mathcal {C}(\mathrel {\mathcal {R}})}$ associated with a concordance–discordance relation in the sense of Definition 2 is itself a particular case of this definition, in which the veto relation $\mathrel {V_{i}}$ is assumed to be empty. Such relations were studied and characterized in (Bouyssou and Pirlot 2005b, 2007).⁵ $\square$

3.3 Tactic

Another type of outranking relation has been introduced by Vansnick (1986). His Tactic method yields an asymmetric outranking relation interpreted as a strict preference. We briefly recall its definition. Let $\mathrel {P_{i}}$ be the asymmetric part of the semiorder $\mathrel {S_{i}}$ defined by (2) and let $\mathrel {V_{i}}$ be the asymmetric part of relation $\mathrel {U_{i}}$ defined by (3). Since $\mathrel {U_{i}}$ is complete, $\mathrel {V_{i}}$ is also the co-dual of $\mathrel {U_{i}}$. An outranking relation $\mathrel {\mathcal {R}}$ of the Tactic type is defined as follows:

$$\begin{aligned} x \mathrel {\mathcal {R}}y \Leftrightarrow \sum _{i \in \mathord {P}(x,y)} w_{i} > \rho \sum _{j \in \mathord {P}(y,x)} w_{j} + \varepsilon \text { and } \mathord {V}(y,x)= \varnothing , \end{aligned}$$

(8)

where $w_{i}$ is a weight assigned to attribute $i$, $\rho$ is a multiplicative threshold with $\rho \ge 1$, $\varepsilon$ is a nonnegative additive threshold, $\mathord {P}(y,x)= \lbrace i \in N: x_{i} \mathrel {P_{i}}y_{i}\rbrace$ and $\mathord {V}(y,x)= \{i \in N: y_{i} \mathrel {V_{i}}x_{i}\}$.

Such an outranking relation is clearly asymmetric by construction, hence irreflexive.

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

3.4 An alternative definition of outranking relations

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

Definition 5

A binary relation $\mathrel {\mathcal {R}}$ on $X= \prod _{i=1}^n {X_{i}}$ is a concordance–discordance relation if there are:

• an asymmetric binary relation $\mathrel {P^{\circ }_{i}}$ on each $X_{i}$ $(i = 1, 2,\ldots ,n)$,

• an asymmetric binary relation $\mathrel {V^{\circ }_{i}}$ on each $X_{i}$ $(i=1,2,\ldots , n)$, with ${\mathrel {V^{\circ }_{i}}} \subseteq {\mathrel {P^{\circ }_{i}}}$,

• a binary relation $\mathrel {\unrhd ^{\circ }}$ between disjoint subsets of $N$ that is monotonic w.r.t. inclusion, i.e., for all $A, B, C, D \subseteq N$ with $A \cap B = \varnothing$ and $C \cap D = \varnothing$,

  $$\begin{aligned}{}[A \mathrel {\unrhd ^{\circ }}B, C \supseteq A, B \supseteq D] \Rightarrow C \mathrel {\unrhd ^{\circ }}D, \end{aligned}$$

  (9)

such that, for all $x, y \in X$,

$$\begin{aligned} x \mathrel {\mathcal {R}}y \Leftrightarrow [\mathord {P^{\circ }}(x,y) \mathrel {\unrhd ^{\circ }}\mathord {P^{\circ }}(y,x) \text { and } \mathord {V^{\circ }(y,x)}= \varnothing ], \end{aligned}$$

(10)

where $\mathord {P^{\circ }}(x,y) = \lbrace i \in N: x_{i} \mathrel {P^{\circ }_{i}}y_{i} \rbrace$ and $\mathord {V^{\circ }(y,x)} = \lbrace i \in N: y_{i} \mathrel {V^{\circ }_{i}}x_{i} \rbrace$.

We say that $\langle {\mathrel {\unrhd ^{\circ }}}, {\mathrel {P^{\circ }_{i}}}, {\mathrel {V^{\circ }_{i}}} \rangle$ is a type II representation of $\mathrel {\mathcal {R}}$.

It is readily checked that the outranking relation produced by Tactic satisfies this definition. In Tactic the relation $\mathrel {\unrhd ^{\circ }}$ is asymmetric.

Lemma 6

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

Proof

Assume that $\mathrel {\mathcal {R}}$ satisfies Definition 2 and that $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$ is a type I representation of $\mathrel {\mathcal {R}}$. We construct a representation $\langle {\mathrel {\unrhd ^{\circ }}}, {\mathrel {P^{\circ }_{i}}}, {\mathrel {V^{\circ }_{i}}} \rangle$ of type II satisfying (10) letting:

$$\begin{aligned} \mathrel {P^{\circ }_{i}}&= {\mathrel {P_{i}}} \text { (the asymmetric part of } \mathrel {S_{i}}), \forall i\in N\nonumber \\ \mathrel {V^{\circ }_{i}}&= {\mathrel {V_{i}}}, \ \forall i \in N\end{aligned}$$

(11)

and $\mathrel {\unrhd ^{\circ }}$ is defined as follows: for all $A, B \subseteq N$, with $A\cap B= \varnothing$,

$$\begin{aligned} A \mathrel {\unrhd ^{\circ }}B \text { if } (N\setminus B) \mathrel {\unrhd }(N\setminus A). \end{aligned}$$

(12)

It is straightforward to check that $\mathrel {\unrhd ^{\circ }}$ satisfies monotonicity condition (9) and that $\mathrel {\mathcal {R}}$ satisfies condition (10).

Conversely, let $\mathrel {\mathcal {R}}$ be a relation that satisfies (10) and $\langle {\mathrel {\unrhd ^{\circ }}}, {\mathrel {P^{\circ }_{i}}}, {\mathrel {V^{\circ }_{i}}} \rangle$ a type II representation of $\mathrel {\mathcal {R}}$. We build a type I representation $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$ of $\mathrel {\mathcal {R}}$ by letting:

$$\begin{aligned} {\mathrel {S_{i}}}&= (\mathrel {P^{\circ }_{i}})^{cd} \text { (the co-dual of }\mathrel {P^{\circ }_{i}}), \forall i\in N\end{aligned}$$

(13)

$$\begin{aligned} {\mathrel {V_{i}}}&= {\mathrel {V^{\circ }_{i}}}, \ \forall i \in N\end{aligned}$$

(14)

and $\mathrel {\unrhd }$ is defined as follows: for all $A, B \subseteq N$, with $A \cup B = N$,

$$\begin{aligned} A \mathrel {\unrhd }B \text { if } (N\setminus B) \mathrel {\unrhd ^{\circ }}(N\setminus A). \end{aligned}$$

(15)

Again, it is easy to prove that $\mathrel {\unrhd }$ satisfies (6) and that $\mathrel {\mathcal {R}}$ satisfies condition (7). Observe that because $\mathrel {P^{\circ }_{i}}$, it co-dual $\mathrel {S_{i}}$ is complete.$\square$

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

Definition 7

(Conjugate representations) Let $\mathrel {\mathcal {R}}$ be a  CDR and $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$  (resp. $\langle {\mathrel {\unrhd ^{\circ }}}, {\mathrel {P^{\circ }_{i}}}, {\mathrel {V^{\circ }_{i}}} \rangle$) a representation of type I (resp. of type II) of $\mathrel {\mathcal {R}}$. We say that these representations are conjugate if $\mathrel {S_{i}}$ and $\mathrel {P^{\circ }_{i}}$ are linked by co-duality, i.e., $x_{i}\mathrel {S_{i}}y_{i}$ if and only if $y_{i} \mathrel {P^{\circ }_{i}}x_{i}$, ${\mathrel {V_{i}}} = {\mathrel {V^{\circ }_{i}}}$, and provided $\mathrel {\unrhd }$ and $\mathrel {\unrhd ^{\circ }}$ are linked by (12) or, equivalently, by (15).

We state below three consequences of the equivalence of the two definitions of CDR.

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

• 2. If $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$ and $\langle {\mathrel {\rhd ^{\circ }}}, {\mathrel {P^{\circ }_{i}}}, {\mathrel {V^{\circ }_{i}}} \rangle$) are dual representations of a CDR, $\mathrel {\mathcal {R}}$, we see that condition (5) in Electre I could equivalently be formulated in terms of the strict preference $\mathrel {P_{i}}$ as

  $$\begin{aligned} \frac{\sum _{ i \in \mathord {P}(y,x)} w_{i}}{\sum _{j \in N} w_{j}} \le 1-s. \end{aligned}$$

• 3. Let $\mathrel {\mathcal {R}}$ be a CDR and let $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$, $\langle {\mathrel {\unrhd ^{\circ }}}, {\mathrel {P^{\circ }_{i}}}, {\mathrel {V^{\circ }_{i}}} \rangle$ be conjugate representations of $\mathrel {\mathcal {R}}$. The concordance part $\mathrel {\mathcal {C}(\mathrel {\mathcal {R}})}$ of the outranking relation $\mathrel {\mathcal {R}}$ has been defined, using (7) and assuming ${\mathrel {V_{i}}} =\varnothing$, by $x \mathrel {\mathcal {C}(\mathrel {\mathcal {R}})} y \text { if } \mathord {S}(x,y) \mathrel {\unrhd }\mathord {S}(y,x)$. In the same spirit, we may use (10), assuming ${\mathrel {V^{\circ }_{i}}} = \varnothing$, yielding $x\mathrel {\mathcal {C}(\mathrel {\mathcal {R}})}y$ if $\mathord {P}(x,y) \mathrel {\unrhd ^{\circ }}\mathord {P}(y,x)$. Assuming that $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$ and $\langle {\mathrel {\unrhd ^{\circ }}}, {\mathrel {P^{\circ }_{i}}}, {\mathrel {V^{\circ }_{i}}} \rangle$ are conjugate representations of $\mathrel {\mathcal {R}}$, it is easy to see that the latter definition is equivalent with the initial one.

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

Proposition 8

Let $\mathrel {\mathcal {R}}$ be a CDR and $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$ (resp. $\langle {\mathrel {\unrhd ^{\circ }}}, {\mathrel {P^{\circ }_{i}}}, {\mathrel {V^{\circ }_{i}}} \rangle$) its representation of type I (resp. of type II). We have:

• 1. $\mathrel {\mathcal {R}}$ is either reflexive or irreflexive, $\mathrel {\mathcal {R}}$ is reflexive $\iff N\mathrel {\unrhd }N$ $\iff$ $\varnothing \mathrel {\unrhd ^{\circ }}\varnothing$, otherwise, $\mathrel {\mathcal {R}}$ is irreflexive,

• 2. $\mathrel {\mathcal {R}}$ is asymmetric $\iff$ $\mathrel {\unrhd }$ is asymmetric $\iff$ $\mathrel {\unrhd ^{\circ }}$ is asymmetric,

• 3. $\mathrel {\mathcal {R}}$ is complete

  • $\iff (A \mathrel {\unrhd }B \text { or } B \mathrel {\unrhd }A), \forall A,B \subseteq N, A \cup B = N$

  • $\iff (C \mathrel {\unrhd ^{\circ }}D \text { or } C \mathrel {\unrhd ^{\circ }}D), \forall C, D \subseteq N, C \cap D = \varnothing .$

The straightforward proof is left to the reader. For Parts 2 and 3, the proof of the $\Rightarrow$ part uses the hypothesis that all attributes are influential (so that, for all $A, B \subseteq N$ such that $A \cup B = N$, there are $x, y \in X$ such that $\mathord {S}(x,y)= A$ and $\mathord {S}(y,x)= B$ and for all $C, D \subseteq N$ such that $C \cap D = \varnothing$, there are $z, w \in X$ such that $\mathord {P^{\circ }}(z,w) = C$ and $\mathord {P^{\circ }}(w,z) = D$).

These properties can immediately be applied to outranking relations built using Electre I or Tactic. If $\mathrel {\mathcal {R}}$ arises from Electre I, it satisfies (5) so that $N\mathrel {\unrhd }N$. As a consequence of Proposition 8.1, $\mathrel {\mathcal {R}}$ is reflexive. A relation $\mathrel {\mathcal {R}}$ arising from Tactic satisfies (8). This implies Not $[\varnothing \mathrel {\unrhd ^{\circ }}\varnothing ]$ and $[C \mathrel {\unrhd ^{\circ }}D \Rightarrow Not [D\mathrel {\unrhd ^{\circ }}C ]]$, for all $C,D \subseteq N$ with $C \cap D = \varnothing$. Hence, using Propositions 8.1 and 8.2, we see that $\mathrel {\mathcal {R}}$ is irreflexive and asymmetric.

Remark 9

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

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

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

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

Definition 10

Let $\mathrel {\unrhd }$ be a relation between subsets of $N$ having $N$ for union. We call the co-dual of $\mathrel {\unrhd }$, the relation $\mathrel {\mathord {\mathrel {\unrhd }}^{cd}}$ between subsets of $N$ having $N$ for union that is defined as follows: for all $A, B \subseteq N$, with $A \cup B = N$, we have $A \mathrel {\mathord {\mathrel {\unrhd }}^{cd}} B \iff Not [B \mathrel {\unrhd }A ]$.

Lemma 11

Let $\mathrel {\unrhd }$ and $\widetilde{\mathrel {\unrhd }}$ be two relations between subsets of $N$ having $N$ for union and satisfying monotonicity condition (6).

• 1. The intersection ${\mathrel {\unrhd }} \cap {\widetilde{\mathrel {\unrhd }}}$ of these relations is a relation between subsets of $N$ having $N$ for union and satisfying (6).

• 2. The co-dual $\mathrel {\mathord {\mathrel {\unrhd }}^{cd}}$ and the asymmetric part $\mathrel {\mathord {\mathrel {\unrhd }}^{\alpha } }$ of $\mathrel {\unrhd }$ both satisfy condition (6).

Proof. The proof is left to the reader.

Remark 12

Similar properties can be established for relations $\mathrel {\unrhd ^{\circ }}$ that intervene in type II representations of concordance relations (CR). We emphasize that $\mathrel {\unrhd ^{\circ }}$ is a relation between disjoint subsets of $N$ and satisfies monotonicity condition (9).$\square$

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

Proposition 13

Let $\mathrel {\mathcal {R}}$ be a CR that has a representation of type I, $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}} \rangle$. The co-dual $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ of $\mathrel {\mathcal {R}}$ is also a CR with a representation of type I that is $\langle {\mathrel {\unrhd }^{cd}}, {\mathrel {S_{i}}} \rangle$.

Proof

We have $x\mathrel {\mathcal {R}}y \iff \left[ \mathord {S}(x,y) \mathrel {\unrhd }\mathord {S}(y,x)\right]$. The co-dual $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ of $\mathrel {\mathcal {R}}$ is such that $x\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}} y \iff Not [y\mathrel {\mathcal {R}}x ]$. Hence, we have $x \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}} y \iff Not [\mathord {S}(y,x) \mathrel {\unrhd }\mathord {S}(x,y) ]$. The latter condition can be rewritten as $x\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}} y \iff \left[ \mathord {S}(x,y) \mathrel {\mathord {\mathrel {\unrhd }}^{cd}} \mathord {S}(y,x)\right]$, where $\mathrel {\mathord {\mathrel {\unrhd }}^{cd}}$ is the co-dual of $\mathrel {\unrhd }$. Using Lemma 11.2, we know that $\langle {\mathrel {\mathord {\mathrel {\unrhd }}^{cd}}}, {\mathrel {S_{i}}} \rangle$ is a type I representation of $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$.$\square$

Remark 14

A quite similar correspondence holds for type II representations. If $\langle {\mathrel {\unrhd ^{\circ }}}, {\mathrel {P^{\circ }_{i}}} \rangle$ is a type II representation of $\mathrel {\mathcal {R}}$, $\langle {\mathrel {\mathord {\mathrel {\unrhd ^{\circ }}\,}^{cd}}}, {\mathrel {P^{\circ }_{i}}} \rangle$ is a type II representation of $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$. Moreover, if the type I and II representations of $\mathrel {\mathcal {R}}$ are dual of one another (Definition 7), the corresponding representations of $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ are also dual of one another. In particular, if $\mathrel {\unrhd }$ and $\mathrel {\unrhd ^{\circ }}$ are linked through relations (12) and (15) then their respective co-dual $\mathrel {\mathord {\mathrel {\unrhd }}^{cd}}$ and $\mathrel {\mathord {\mathrel {\unrhd ^{\circ }}\,}^{cd}}$ are linked through the same relations.$\square$

Remark 15

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

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

Proposition 16

The asymmetric part of a R-CR, that has a type I representation $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}} \rangle$, is the A-CR that has a type I representation $\langle {\mathrel {\mathord {\mathrel {\unrhd }}^{\alpha } }}, {\mathrel {S_{i}}} \rangle$ with $\mathrel {\mathord {\mathrel {\unrhd }}^{\alpha } }$, the asymmetric part of $\mathrel {\unrhd }$.

Proof

Let $\mathrel {\mathcal {R}}$ be a R-CR. We have $x\mathrel {\mathcal {R}}y \iff \left[ \mathord {S}(x,y) \mathrel {\unrhd }\mathord {S}(y,x)\right]$. The asymmetric part $\mathrel {\mathord {\mathcal {R}}^{\alpha } }$ of $\mathrel {\mathcal {R}}$ is such that $x\mathrel {\mathord {\mathcal {R}}^{\alpha } }y \iff x\mathrel {\mathcal {R}}y \text { and } Not [y\mathrel {\mathcal {R}}x ]$. Hence, we have $x\mathrel {\mathord {\mathcal {R}}^{\alpha } }y \iff \left[ \mathord {S}(x,y) \mathrel {\unrhd }\mathord {S}(y,x) \text { and } Not [\mathord {S}(y,x) \mathrel {\unrhd }\mathord {S}(x,y) ]\right]$. The latter condition can be rewritten as $x\mathrel {\mathord {\mathcal {R}}^{\alpha } }y \iff \left[ \mathord {S}(x,y) \mathrel {\mathord {\mathrel {\unrhd }}^{\alpha } } \mathord {S}(y,x)\right]$, where $\mathrel {\mathord {\mathrel {\unrhd }}^{\alpha } }$ is the asymmetric part of $\mathrel {\unrhd }$. Using Lemma 11.2, we know that $\langle {\mathrel {\mathord {\mathrel {\unrhd }}^{\alpha } }}, {\mathrel {S_{i}}} \rangle$ is a type I representation of $\mathrel {\mathord {\mathcal {R}}^{\alpha } }$.$\square$

Remark 17

(Type II representations) A remark similar to Remark 14 can be formulated for type II representations of $\mathrel {\mathcal {R}}$ and $\mathrel {\mathord {\mathcal {R}}^{\alpha } }$. In particular, let $\langle {\mathrel {\unrhd ^{\circ }}}, {\mathrel {P^{\circ }_{i}}} \rangle$ be a type II representation of $\mathrel {\mathcal {R}}$. The asymmetric part $\mathrel {\mathord {\mathcal {R}}^{\alpha } }$ of $\mathrel {\mathcal {R}}$ has a type II representation $\langle {\mathrel {\mathord {\mathrel {\unrhd ^{\circ }}}^{\alpha } }}, {\mathrel {P^{\circ }_{i}}} \rangle$, with $\mathrel {\mathord {\mathrel {\unrhd ^{\circ }}}^{\alpha } }$, the asymmetric part of $\mathrel {\unrhd ^{\circ }}$.$\square$

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

3.6 Vetoes and bonuses

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

Let $\mathrel {\mathcal {R}}$ be a R-CDR. For all $x,y \in X$, we have that $x \mathrel {\mathcal {R}}y$ if $x \mathrel {\mathcal {C}(\mathrel {\mathcal {R}})} y$ and $x \mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})} y$, where $\mathrel {\mathcal {C}(\mathrel {\mathcal {R}})}$ is the R-CR associated with $\mathrel {\mathcal {R}}$ and $x \mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})} y$ if $Not [y_{i} \mathrel {V_{i}}x_{i} ]$, for all $i\in N$ (see Remark 4).

The asymmetric part $\mathrel {\mathord {\mathcal {R}}^{\alpha } }$ of $\mathrel {\mathcal {R}}$ obtains as follows:

$$\begin{aligned}&x \mathrel {\mathord {\mathcal {R}}^{\alpha } }y \Leftrightarrow x\mathrel {\mathcal {R}}y \text { and } Not [y \mathrel {\mathcal {R}}x ] \\&\quad \Leftrightarrow \left\{ \begin{array}{l} \left[ x \mathrel {\mathcal {C}(\mathrel {\mathcal {R}})} y \text { and } x \mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})} y\right] \text { and } \\ \left[ Not [y \mathrel {\mathcal {C}(\mathrel {\mathcal {R}})} x ] \text { or } Not [y \mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})} x ] \right] \end{array} \right. \end{aligned}$$

It is easy to see that the above definition can equivalently be written as:

$$\begin{aligned}&x \mathrel {\mathord {\mathcal {R}}^{\alpha } }y \Leftrightarrow \\&\left\{ \begin{array}{l} \left[ x \mathrel {\mathcal {C}(\mathrel {\mathcal {R}})} y \text { and } Not [y \mathrel {\mathcal {C}(\mathrel {\mathcal {R}})} x ] \text { and } x \mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})} y\right] \text { or } \\ \left[ x \mathrel {\mathcal {C}(\mathrel {\mathcal {R}})} y \text { and } y \mathrel {\mathcal {C}(\mathrel {\mathcal {R}})} x \text { and } x \mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})} y \text { and } Not [y \mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})} x ]\right] . \end{array}\right. \end{aligned}$$

Hence we have $x \mathrel {\mathord {\mathcal {R}}^{\alpha } }y$ if and only if one of the following two exclusive conditions is fulfilled:

• 1. $(x,y)$ belongs to the asymmetric part of $\mathrel {\mathcal {C}(\mathrel {\mathcal {R}})}$ and $x \mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})} y$ or

• 2. $(x,y)$ belongs to the symmetric part of $\mathrel {\mathcal {C}(\mathrel {\mathcal {R}})}$, $x \mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})} y$ and, for some $i \in N$, $x_{i} \mathrel {V_{i}}y_{i}$

Case 1 corresponds to the definition of an A-CDR since, by Proposition 16, the asymmetric part of $\mathrel {\mathcal {C}(\mathrel {\mathcal {R}})}$, which is a R-CR, is an A-CR, a non-discordance condition is imposed on it.

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

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

Let us now examine the effect of the co-dual operator on concordance–discordance relations. Assume, for instance, that $\mathrel {\mathcal {R}}$ is an A-CDR. By definition of an A-CDR, we have: $x \mathrel {\mathcal {R}}y$ if $x \mathrel {\mathcal {C}(\mathrel {\mathcal {R}})} y$ and $x \mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})}y$, where $\mathrel {\mathcal {C}(\mathrel {\mathcal {R}})}$ is the A-CR associated with $\mathrel {\mathcal {R}}$. The co-dual $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ of $\mathrel {\mathcal {R}}$ is such that:

$$\begin{aligned} x \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}y \iff Not [y \mathrel {\mathcal {C}(\mathrel {\mathcal {R}})} x ] \text { or } Not [y \mathrel {\mathcal {ND}(\mathrel {\mathcal {R}})} x ]. \end{aligned}$$

(16)

The first condition in the righthand side of (16) states that $(x,y)$ belongs to the co-dual of $\mathrel {\mathcal {C}(\mathrel {\mathcal {R}})}$. We know that the co-dual of this A-CR is a complete R-CR (Proposition 13). The second condition in the righthand side of (16), means again that there may be a bonus effect, i.e., that $x_{i} \mathrel {V_{i}}y_{i}$ (for any $i \in N$) entails $x \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}y$. Condition (16) defining the co-dual of an A-CDR is very similar to the one defining a R-CDR except that veto plays a positive rôle here. In contrast with Proposition 13, the co-dual of a CDR is not, in general, a CDR, due to the possible occurrence of bonus effects. It is a concordance relation with bonus (CRB) as defined below. In this definition, the non-veto condition in Definition 2 is just transformed into a bonus condition.

Definition 18

(Concordance relation with bonus (CRB)) A binary relation $\mathrel {\mathcal {R}}$ on $X= \prod _{i=1}^n {X_{i}}$ is a concordance relation with bonus (CRB) if there are:

• 1. a complete binary relation $\mathrel {S_{i}}$ on each $X_{i}$ ($i=1,2,\ldots , n$) (with asymmetric part $\mathrel {P_{i}}$ and symmetric part $\mathrel {I_{i}}$),

• 2. an asymmetric binary relation $\mathrel {V_{i}}$ on each $X_{i}$ ($i=1,2,\ldots , n$) such that ${\mathrel {V_{i}}} \subseteq {\mathrel {P_{i}}}$,

• 3. a binary relation $\mathrel {\unrhd }$ between subsets of $N$ having $N$ for union that is monotonic w.r.t. inclusion, i.e., for all $A, B, C, D \subseteq N$ with $A \cup B = N$ and $C \cup D = N$,

  $$\begin{aligned}{}[A \mathrel {\unrhd }B, C \supseteq A, B \supseteq D] \Rightarrow C \mathrel {\unrhd }D, \end{aligned}$$

  (17)

such that, for all $x, y \in X$,

$$\begin{aligned} x \mathrel {\mathcal {R}}y \Leftrightarrow \left[ \mathord {S}(x,y) \mathrel {\unrhd }\mathord {S}(y,x) \text { or } \mathord {V}(x,y)\ne \varnothing \right] , \end{aligned}$$

(18)

where $\mathord {S}(x,y) = \lbrace i \in N: x_{i} \mathrel {S_{i}}y_{i}\rbrace$ and $\mathord {V}(x,y)= \lbrace i \in N: x_{i} \mathrel {V_{i}}y_{i} \rbrace$.

We say that $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$ is a representation of $\mathrel {\mathcal {R}}$ as a CRB.

Note that a concordance relation (CR) is a CRB in which all the $\mathrel {V_{i}}$ relations are empty. As for concordance–discordance relations, we may distinguish reflexive CRB ’s (R-CRB) on the one hand and asymmetric CRB ’s (A-CRB) on the other hand. The alternative definition of a CDR established in Lemma 6 can also be transposed for CRB ’s without any difficulty and we omit the details.

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

Proposition 19

Relation $\mathrel {\mathcal {R}}$ on $X$ is a concordance–discordance relation if and only if its co-dual $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ is a concordance relation with bonus and conversely.

Proof

Let $\mathrel {\mathcal {R}}$ be a CDR having $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$ as a representation of type I. Using Proposition 13, we know that $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ is a concordance relation that has $\langle {\mathrel {\unrhd }}^{cd}, {\mathrel {S_{i}}} \rangle$ as a representation of type I as a CR. Since $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ is defined, for all $x,y \in X$, by

$$\begin{aligned} x \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}y&\Leftrightarrow Not [\mathord {S}(y,x) \mathrel {\unrhd }\mathord {S}(x,y) \text { and } \mathord {V}(y,x)= \varnothing ]\\&\Leftrightarrow Not [\mathord {S}(y,x) \mathrel {\unrhd }\mathord {S}(x,y) ] \text { or } [\mathord {V}(y,x)\ne \varnothing ]\\&\Leftrightarrow [\mathord {S}(x,y) \mathrel {\unrhd }^{cd} \mathord {S}(y,x)] \text { or } [\mathord {V}(y,x)\ne \varnothing ], \end{aligned}$$

we see that it is a CRB having a representation of type I, which is $\langle {\mathrel {\unrhd }^{cd}}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$.

The converse is also true. Starting with $\mathrel {\mathcal {R}}$, a CRB that has a type I representation $\langle {\mathrel {\unrhd }}^{cd}, {\mathrel {S_{i}}} \rangle$, we apply the co-dual operator as follows:

$$\begin{aligned} x \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}y&\Leftrightarrow Not [\mathord {S}(y,x) \mathrel {\unrhd }\mathord {S}(x,y) \text { or } \mathord {V}(y,x)\ne \varnothing ]\\&\Leftrightarrow Not [\mathord {S}(y,x) \mathrel {\unrhd }\mathord {S}(x,y) ] \text { and } [\mathord {V}(y,x)= \varnothing ]\\&\Leftrightarrow [\mathord {S}(x,y) \mathrel {\unrhd }^{cd} \mathord {S}(y,x)] \text { and } [\mathord {V}(y,x)= \varnothing ]. \end{aligned}$$

Relation $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ is a CDR that admits the type I representation $\langle {\mathrel {\unrhd }^{cd}}, {\mathrel {S_{i}}}, {\mathrel {V_{i}}} \rangle$.$\square$

Because the asymmetric part $\mathrel {\mathord {\mathcal {R}}^{\alpha } }$ of a R-CDR, $\mathrel {\mathcal {R}}$ may involve at the same time bonus and veto effects, simple examples show that it is neither an asymmetric CDR nor an asymmetric CRB. Such relations require an analysis that is more complex than the one for CDR or CRB. It is detailed in Bouyssou and Pirlot (2014).

3.7 Summary

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

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

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

In the rest of this paper, we take advantage of the just explored co-duality relationships between strict and non-strict outranking relations, in order to unify and deepen the axiomatic analysis that we presented in several previous papers (Bouyssou and Pirlot 2002b, 2005b, 2006, 2007, 2009a).

4 Axiomatic analysis

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

4.1 Background

We briefly recall the axioms used in the characterization of reflexive CDR obtained in Bouyssou and Pirlot (2009a), under the assumption that all attributes are influential.

Definition 20

(Axioms $RC 1$, $RC 2$) Let $\mathrel {\mathcal {R}}$ be a binary relation on a set $X= \prod _{i=1}^n {X_{i}}$. This relation is said to satisfy:

$$\begin{aligned}&RC 1_{i} \text { if } \left. \begin{array}{c} (x_{i},a_{-i})\mathrel {\mathcal {R}}(y_{i},b_{-i})\\ \text {and}\\ (z_{i},c_{-i})\mathrel {\mathcal {R}}(w_{i},d_{-i}) \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (z_{i},a_{-i})\mathrel {\mathcal {R}}(w_{i},b_{-i})\\ \text {or}\\ (x_{i},c_{-i})\mathrel {\mathcal {R}}(y_{i},d_{-i}), \end{array} \right. \\&RC 2_{i} \text { if } \left. \begin{array}{c} (x_{i},a_{-i})\mathrel {\mathcal {R}}(y_{i},b_{-i})\\ \text {and}\\ (y_{i},c_{-i})\mathrel {\mathcal {R}}(x_{i},d_{-i}) \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (z_{i},a_{-i}) \mathrel {\mathcal {R}}(w_{i},b_{-i})\\ \text {or}\\ (w_{i},c_{-i}) \mathrel {\mathcal {R}}(z_{i},d_{-i}),\\ \end{array} \right. \end{aligned}$$

for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$ and all $a_{-i}, b_{-i}, c_{-i}, d_{-i} \in X_{-i}$. We say that $\mathrel {\mathcal {R}}$ satisfies $RC 1$ (resp. $RC 2$) if it satisfies $RC 1_{i}$ (resp. $RC 2_{i}$) for all $i \in N$.

An interpretation of these axioms was provided in Bouyssou and Pirlot (2002a). It relies on a reformulation of the axioms in terms of traces left by the preference $\mathrel {\mathcal {R}}$ on each attribute scale. The relevant traces in the present case are relations comparing preference differences on each attribute. They are precisely defined as follows (see also Bouyssou and Pirlot 2005a, for more detail on traces).

Definition 21

(Relations $\mathrel {\succsim _{i}^{*}}$, $\mathrel {\succsim _{i}^{**}}$ ) Let $\mathrel {\mathcal {R}}$ be a binary relation on a set $X= \prod _{i=1}^n {X_{i}}$. We define the binary relations $\mathrel {\succsim _{i}^{*}}$ and $\mathrel {\succsim _{i}^{**}}$ on $X_{i}^2$ letting, for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$,

$$\begin{aligned}&\displaystyle (x_{i}, y_{i}) \mathrel {\succsim _{i}^{*}}(z_{i}, w_{i}) \Leftrightarrow \\&\displaystyle \forall a_{-i}, b_{-i} \in X_{-i}, [(z_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i}) \Rightarrow (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i})],\\&\displaystyle (x_{i}, y_{i}) \mathrel {\succsim _{i}^{**}}(z_{i}, w_{i}) \Leftrightarrow \left[ (x_{i}, y_{i}) \mathrel {\succsim _{i}^{*}}(z_{i}, w_{i}) \text { and } (w_{i}, z_{i}) \mathrel {\succsim _{i}^{*}}(y_{i},x_{i})\right] . \end{aligned}$$

In order to understand the close relationship between $\mathrel {\succsim _{i}^{*}}$ and $RC 1_{i}$, assume that $RC 1_{i}$ is not true. Hence, for some $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$ and some $a_{-i}, b_{-i}, c_{-i}, d_{-i} \in X_{-i}$, both premises of $RC 1_{i}$ are satisfied and none of its conclusions. We thus have $(x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i})$ and $Not [(z_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i}) ]$, which is tantamount to $Not [(z_i, w_i) \mathrel {\succsim _{i}^{*}}(x_i, y_i) ]$. Similarly, we have $(z_{i},c_{-i})\mathrel {\mathcal {R}}(w_{i},d_{-i})$ and $Not [(x_{i},c_{-i})\mathrel {\mathcal {R}}(y_{i},d_{-i}) ]$, which means $Not [(x_i, y_i) \mathrel {\succsim _{i}^{*}}(z_i, w_i) ]$. Hence it is clear that $RC 1_i$ holds if and only if all pairs of elements in $X_{i}$ are comparable w.r.t. $\mathrel {\succsim _{i}^{*}}$.

This conclusion constitutes the first part of the lemma below. The second part is obtained similarly, considering $RC 2_{i}$ (see Bouyssou and Pirlot 2002a, for the proof).

Lemma 22

(Bouyssou and Pirlot 2002a, Lemma 1)

• 1. $RC 1_{i}$ $\Leftrightarrow$ $[\mathrel {\succsim _{i}^{*}}$ is complete$]$,

• 2. $RC 2_{i}$ $\Leftrightarrow$ $[\hbox {for all }x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}, Not [(x_{i}, y_{i}) \mathrel {\succsim _{i}^{*}}(z_{i}, w_{i}) ] \Rightarrow (y_{i}, x_{i}) \mathrel {\succsim _{i}^{*}}(w_{i}, z_{i})]$,

• 3. $[ RC 1_{i}$ and $RC 2_{i}]$ $\Leftrightarrow$ $[\mathrel {\succsim _{i}^{**}}$ is complete$]$.

Since $\mathrel {\succsim _{i}^{*}}$ and $\mathrel {\succsim _{i}^{**}}$ are transitive by definition, the above lemma states that $\mathrel {\succsim _{i}^{*}}$ (resp. $\mathrel {\succsim _{i}^{**}}$) is a weak order if and only if $RC 1_{i}$ holds (resp. $RC 1_{i}$ and $RC 2_{i}$ hold).

The precise interpretation of axiom $RC 1_{i}$ and $RC 2_i$ are thus as follows. Axiom $RC 1_{i}$ amounts to say that all preference differences $(x_{i}, y_{i})$ on $X_{i}$ can be weakly ordered. Axiom $RC 2_{i}$ establishes a link between opposite differences of preferences such as $(x_{i}, y_{i})$ and $(y_{i}, x_{i})$. Note that $RC 2$ entails that $\mathrel {\mathcal {R}}$ is an independent preference relation.

Remark 23

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

A crucial feature of CR and CDR is that they induce relations $\mathrel {\succsim _{i}^{*}}$ and $\mathrel {\succsim _{i}^{**}}$ having a limited number of equivalence classes. This is the motivation for the following two conditions.

Definition 24

(Axioms $M1$, $M2$) Let $\mathrel {\mathcal {R}}$ be a binary relation on a set $X= \prod _{i=1}^{n} X_{i}$. This relation is said to satisfy:

$$\begin{aligned}&M1_{i} \text { if } \left. \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i})\\ \text {and}\\ (z_{i}, c_{-i}) \mathrel {\mathcal {R}}(w_{i}, d_{-i}) \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (y_{i}, a_{-i}) \mathrel {\mathcal {R}}(x_{i}, b_{-i})\\ \text {or}\\ (w_{i}, a_{-i})\mathrel {\mathcal {R}}(z_{i}, b_{-i})\\ \text {or}\\ (x_{i}, c_{-i})\mathrel {\mathcal {R}}(y_{i}, d_{-i}), \end{array} \right. \end{aligned}$$

(19)

$$\begin{aligned}&M2_{i} \text { if } \left. \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i})\\ \text {and}\\ (y_{i}, c_{-i}) \mathrel {\mathcal {R}}(x_{i}, d_{-i}) \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (y_{i}, a_{-i}) \mathrel {\mathcal {R}}(x_{i}, b_{-i})\\ \text {or}\\ (z_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i})\\ \text {or}\\ (z_{i}, c_{-i})\mathrel {\mathcal {R}}(w_{i}, d_{-i}), \end{array} \right. \end{aligned}$$

(20)

for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$ and all $a_{-i}, b_{-i}, c_{-i}, d_{-i} \in X_{-i}$. We say that $M1$ (resp. $M2$) holds if $M1_{i}$ (resp. $M2_{i}$) holds for all $i \in N$.

The interpretation of $M1_{i}$ and $M2_{i}$, respectively conditional on $RC 2_{i}$ and $RC 1_{i}$, results from the following lemma.

Lemma 25

• 1. If $\mathrel {\mathcal {R}}$ satisfies $RC 2_{i}$, then $\mathrel {\mathcal {R}}$ satisfies $M1_{i}$ $\iff$ $[$for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}, Not [(y_{i}, x_{i}) \mathrel {\succsim _{i}^{*}}(x_{i}, y_{i}) ] \Rightarrow (x_{i}, y_{i}) \mathrel {\succsim _{i}^{*}}(z_{i}, w_{i})]$,

• 2. If $\mathrel {\mathcal {R}}$ satisfies $RC 1_{i}$, then $\mathrel {\mathcal {R}}$ satisfies $M2_{i}$ $\iff$ $[$for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}, Not [(y_{i}, x_{i}) \mathrel {\succsim _{i}^{*}}(x_{i}, y_{i}) ] \Rightarrow (z_{i}, w_{i}) \mathrel {\succsim _{i}^{*}}(y_{i}, x_{i})]$,

Proof

The proof of item 1 (resp. item 2) results from the combination of Bouyssou and Pirlot (2007), Lemma 11.1 and 11.3 (resp. 11.2 and 11.4) and Bouyssou and Pirlot (2005b), Lemma 16.1 (resp. 16.2).$\square$

Let us call a positive preference difference (resp. negative preference difference) one that is at least (resp. at most) as large as the opposite preference difference. Under $RC 2_{i}$, $M1_{i}$ says that a positive preference difference is at least as large as any other preference difference. In other terms, there is only one class of positive preference differences. Under $RC 1_{i}$, $M2_{i}$ states the symmetric property for negative preference differences. For more detail on the interpretation of $M1$ and $M2$, see Bouyssou and Pirlot 2005b, 2007).

Remark 26

(Axioms $UC$ and $LC$) A simpler–and slightly stronger–version of axioms $M1_{i}$, $M2_{i}$ was used in our initial characterization of concordance relations in Bouyssou and Pirlot (2005b). These axioms, respectively labeled $UC _{i}$ and $LC _{i}$, obtain by dropping the second in the three possible conclusions in the definitions of $M1_{i}$ and $M2_{i}$. The substitution of $UC _{i}$ and $LC _{i}$ by $M1_{i}$ and $M2_{i}$ in the characterization of reflexive CR was motivated by the need for independent sets of axioms. By Lemma 16.3 in Bouyssou and Pirlot (2005b), we established indeed that $RC 2_{i}, UC _{i}$ and $LC _{i}$ imply $RC 1_{i}$. The second in the three possible conclusions in the definitions of $M1_{i}$ and $M2_{i}$ has precisely the effect of guaranteeing the independence of the set of axioms $RC 1_{i}, RC 2_{i}, M1_{i}$ and $M2_{i}$, as is shown in the next theorem.$\square$

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

Theorem 27

The binary relation $\mathrel {\mathcal {R}}$ on $X= \prod _{i=1}^n {X_{i}}$ is a concordance relation (CR) iff it satisfies $RC 1$, $RC 2$, $M1$ and $M2$. These axioms are independent in the class of complete binary relations.

Proof

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

Violated axiom	$RC 1_{i}$	$RC 2_{i}$	$M1_{i}$	$M2_{i}$
Example	79	77	78	83

$\square$

We now introduce a weakened version of $M2_{i}$, axiom $M3_{i}$, which allows for vetoes, i.e., “large negative” preference differences forbidding that a pair of alternatives may belong to the global preference relation.

Definition 28

Let $\mathrel {\mathcal {R}}$ be a binary relation on a set $X= \prod _{i=1}^n {X_{i}}$. This relation is said to satisfy:

$$\begin{aligned} M3_{i} \text { if } \left. \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i})\\ \text {and}\\ (y_{i}, c_{-i}) \mathrel {\mathcal {R}}(x_{i}, d_{-i})\\ \text { and }\\ (z_{i}, e_{-i}) \mathrel {\mathcal {R}}(w_{i}, f_{-i}) \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (y_{i}, a_{-i}) \mathrel {\mathcal {R}}(x_{i}, b_{-i})\\ \text {or}\\ (z_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i})\\ \text {or}\\ (z_{i}, c_{-i})\mathrel {\mathcal {R}}(w_{i}, d_{-i}), \end{array} \right. \end{aligned}$$

for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$ and all $a_{-i}, b_{-i}, c_{-i}, d_{-i}, e_{-i}, f_{-i} \in X_{-i}$. We say that $\mathrel {\mathcal {R}}$ satisfies $M3$ if it satisfies $M3_{i}$ for all $i \in N$.

We observe that $M3_{i}$ only differs from $M2_{i}$ by the adjunction of the third premise, implying that $M3_{i}$ is a weakening of $M2_{i}$. The interpretation of $M3_{i}$, under the hypothesis that $RC 1_{i}$ holds, results from that of $M2_{i}$ as stated in Lemma 25.2. Assuming $RC 1_{i}$ amounts to say that $\mathrel {\succsim _{i}^{*}}$ is complete. Hence if the first two premises of $M3_{i}$ hold and neither the first nor the third conclusion do, then we have $(x_{i}, y_{i}) \mathrel {\succ _{i}^{*}}(y_{i}, x_{i}) \mathrel {\succ _{i}^{*}}(z_{i}, w_{i})$. In these circumstances, the second conclusion cannot be true, since this would imply that $(z_{i}, w_{i}) \mathrel {\succ _{i}^{*}}(y_{i}, x_{i})$, a contradiction with $(y_{i}, x_{i}) \mathrel {\succ _{i}^{*}}(z_{i}, w_{i})$. Hence, none of the three conclusions holds and $M3_{i}$ can only be satisfied if it never happens that $(z_{i}, e_{-i}) \mathrel {\mathcal {R}}(w_{i}, f_{-i})$. This means that the pair $(z_{i}, w_{i})$ represents an unacceptable preference difference, leading to a veto. We have the following result.

Theorem 29

The binary relation $\mathrel {\mathcal {R}}$ on $X= \prod _{i=1}^n {X_{i}}$ is a concordance–discordance relation (CDR) iff it satisfies $RC 1$, $RC 2$, $M1$ and $M3$. These axioms are independent in the class of complete binary relations.

Proof

As said before, the proof of Theorem 19 in Bouyssou and Pirlot (2009a) remains valid for general binary relations and we omit it. In order to prove the independence of the axioms in the class of complete relations, we may invoke again those examples used in the proof of Theorem 27. It only remains to exhibit an example of a complete relation satisfying $RC 1, RC 2, M1$ and $M3_{i}$ on all attributes but one. Example 83 in “Appendix 2” fulfills this requirement. $\square$

4.2 Characterizations of CR via co-duality

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

$\mathrel {\mathcal {R}}$ satisfies $RC 1_{i}$, i.e.,

$$\begin{aligned} \left. \begin{array}{c} Not [(x_{i},c_{-i})\mathrel {\mathcal {R}}(y_{i},d_{-i}) ]\\ \text { and }\\ Not [(z_{i},a_{-i})\mathrel {\mathcal {R}}(w_{i},b_{-i}) ] \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} Not [(x_{i},a_{-i})\mathrel {\mathcal {R}}(y_{i},b_{-i}) ] \\ \text {or}\\ Not [(z_{i},c_{-i})\mathrel {\mathcal {R}}(w_{i},d_{-i}) ] \end{array} \right. \end{aligned}$$

if and only if $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ satisfies:

$$\begin{aligned} \left. \begin{array}{c} (y_{i},d_{-i})\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(x_{i},c_{-i})\\ \text { and }\\ (w_{i},b_{-i})\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(z_{i},a_{-i}) \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (y_{i},b_{-i})\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(x_{i},a_{-i})\\ \text {or}\\ (w_{i},d_{-i})\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(z_{i},c_{-i}), \end{array} \right. \end{aligned}$$

for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$ and all $a_{-i}, b_{-i}, c_{-i}, d_{-i} \in X_{-i}$. Clearly, the above condition is axiom $RC 1_{i}$ imposed on relation $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$. Hence, $\mathrel {\mathcal {R}}$ satisfies $RC 1_{1}$ iff its co-dual does. It can be similarly shown that it is also the case for $RC 2_{i}$. We refer to this property saying that axioms $RC 1$ and $RC 2$ are self co-dual.

The picture is not exactly the same for $M1$ and $M2$. Let us recall axioms $Maj 1$ and $Maj 2$ that have been introduced for characterizing strict concordance relations in Bouyssou and Pirlot (2005c), Bouyssou and Pirlot (2006).

Definition 30

(Axioms $Maj 1$, $Maj 2$) Let $\mathrel {\mathcal {R}}$ be a binary relation on a set $X= \prod _{i=1}^n X_{i}$. This relation is said to satisfy:

$$\begin{aligned}&Maj 1_{i} \text { if } \left. \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i})\\ \text {and}\\ (z_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i})\\ \text {and}\\ (z_{i}, c_{-i}) \mathrel {\mathcal {R}}(w_{i}, d_{-i}) \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (y_{i}, a_{-i}) \mathrel {\mathcal {R}}(x_{i}, b_{-i})\\ \text {or}\\ (x_{i}, c_{-i})\mathrel {\mathcal {R}}(y_{i}, d_{-i}), \end{array} \right. \end{aligned}$$

(21)

$$\begin{aligned}&Maj 2_{i} \text { if } \left. \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i})\\ \text {and}\\ (w_{i}, a_{-i}) \mathrel {\mathcal {R}}(z_{i}, b_{-i})\\ \text {and}\\ (y_{i}, c_{-i}) \mathrel {\mathcal {R}}(x_{i}, d_{-i}) \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (y_{i}, a_{-i}) \mathrel {\mathcal {R}}(x_{i}, b_{-i})\\ \text {or}\\ (z_{i}, c_{-i})\mathrel {\mathcal {R}}(w_{i}, d_{-i}), \end{array} \right. \end{aligned}$$

(22)

for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$ and all $a_{-i}, b_{-i}, c_{-i}, d_{-i} \in X_{-i}$. We say that $Maj 1$ (resp. $Maj 2$) holds if $Maj 1_{i}$ (resp. $Maj 2_{i}$) holds for all $i \in N$.

Contraposition of $M1_{i}$ yields: $\mathrel {\mathcal {R}}$ satisfies $M1_{i}$ if and only if $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ satisfies the following condition: for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$ and all $a_{-i}, b_{-i}, c_{-i}, d_{-i} \in X_{-i}$,

$$\begin{aligned} \left. \begin{array}{c} (x_{i}, b_{-i}) \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(y_{i}, a_{-i})\\ \text {and}\\ (z_{i}, b_{-i}) \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(w_{i}, a_{-i})\\ \text {and}\\ (y_{i}, d_{-i}) \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(x_{i}, c_{-i}) \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (y_{i}, b_{-i}) \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(x_{i}, a_{-i})\\ \text {or}\\ (w_{i}, d_{-i})\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(z_{i}, c_{-i}). \end{array} \right. \end{aligned}$$

(23)

It is readily seen that this condition is axiom $Maj 2_{i}$ imposed on relation $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$. Indeed expressions (22) and (23) only differ by the positions of $a_{-i}$ and $b_{-i}$, $c_{-i}$ and $d_{-i}$, $z_{i}$ and $w_{i}$, which have been interchanged, and by the substitution of $\mathrel {\mathcal {R}}$ with $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$. Paraphrasing this result, we state that imposing $M1_{i}$ on $\mathrel {\mathcal {R}}$ is tantamount to imposing $Maj 2_{i}$ on its co-dual $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ and conversely.

In a similar way, starting from condition $M2_{i}$ imposed on $\mathrel {\mathcal {R}}$, we obtain the following equivalent condition imposed on $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$: for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$ and all $a_{-i}, b_{-i}, c_{-i}, d_{-i} \in X_{-i}$,

$$\begin{aligned} \left. \begin{array}{c} (x_{i}, b_{-i}) \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(y_{i}, a_{-i})\\ \text {and}\\ (w_{i}, b_{-i}) \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(z_{i}, a_{-i})\\ \text {and}\\ (w_{i}, d_{-i}) \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(z_{i}, c_{-i}) \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (y_{i}, b_{-i}) \mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(x_{i}, a_{-i})\\ \text {or}\\ (x_{i}, d_{-i})\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}(y_{i}, c_{-i}). \end{array} \right. \end{aligned}$$

(24)

We observe that the latter condition is axiom $Maj 1_{i}$ imposed on relation $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ (with the positions of $a_{-i}$ and $b_{-i}$, $c_{-i}$ and $d_{-i}$, $z_{i}$ and $w_{i}$ having been interchanged). Imposing $M2_{i}$ on $\mathrel {\mathcal {R}}$ is equivalent to imposing $Maj 1_{i}$ on its co-dual $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ and conversely.

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

Lemma 31

Let $\mathrel {\mathcal {R}}$ be any relation on $X$ and $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ its co-dual. The following statements hold, for all $i \in N$:

• 1. $\mathrel {\mathcal {R}}$ satisfies $RC 1_{i}$ iff $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ satisfies $RC 1_{i}$,

• 2. $\mathrel {\mathcal {R}}$ satisfies $RC 2_{i}$ iff $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ satisfies $RC 2_{i}$,

• 3. $\mathrel {\mathcal {R}}$ satisfies $M1_{i}$ iff $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ satisfies $Maj 2_{i}$,

• 4. $\mathrel {\mathcal {R}}$ satisfies $M2_{i}$ iff $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ satisfies $Maj 1_{i}$.

Co-duality induces a simple correspondence between the relations comparing preference differences on each attribute, namely the relations $\mathrel {\succsim _{i}^{*}}$ (resp. $\mathrel {\succsim _{i}^{**}}$) associated with a relation $\mathrel {\mathcal {R}}$ and its co-dual $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$. To avoid ambiguity, we write $\mathrel {\succsim _{i}^{*}}(\mathrel {\mathcal {R}})$, $\mathrel {\succsim _{i}^{**}}(\mathrel {\mathcal {R}})$ (resp. $\mathrel {\succsim _{i}^{*}}(\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}})$, $\mathrel {\succsim _{i}^{**}}(\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}})$) to denote the two relations comparing preference differences on attribute $i$ associated with $\mathrel {\mathcal {R}}$ (resp. $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$). Using Definition 21 and that of $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$, it is straightforward to establish the following result.

Lemma 32

Let $\mathrel {\mathcal {R}}$ be any relation on $X$ and $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ its co-dual. For all $i \in N$, for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$, we have:

• 1. $(x_{i}, y_{i}) \mathrel {\mathord {\mathrel {\succsim _{i}^{*}}}(\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}})} (z_{i}, w_{i})$ iff $(w_{i}, z_{i}) \mathrel {\mathord {\mathrel {\succsim _{i}^{*}}}(\mathrel {\mathcal {R}})} (y_{i}, x_{i})$,

• 2. $(x_{i}, y_{i}) \mathrel {\mathord {\mathrel {\succsim _{i}^{**}}}(\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}})} (z_{i}, w_{i})$ iff $(x_{i}, y_{i}) \mathrel {\mathord {\mathrel {\succsim _{i}^{**}}}(\mathrel {\mathcal {R}})} (z_{i}, w_{i})$.

Remark 33

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

In the context of the present paper, $UC$ and $LC$ are at an advantage w.r.t. $M1$ and $M2$ or $Maj 1$ and $Maj 2$ since they form a pair of cross co-dual conditions. It is indeed easy to check that imposing $UC _{i}$ on relation $\mathrel {\mathcal {R}}$ is equivalent to imposing $LC_{i}$ on its co-dual $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ and conversely.$\square$

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

Lemma 34

The following implications hold for all $i \in N$:

• 1. $M1_{i}$ and $RC 2_{i}$ entail $Maj 1_{i}$,

• 2. $Maj 1_{i}$ and $RC 1_{i}$ entail $M1_{i}$,

• 3. $M2_{i}$ and $RC 1_{i}$ entail $Maj 2_{i}$,

• 4. $Maj 2_{i}$ and $RC 2_{i}$ entail $M2_{i}$.

Under $RC 1_{i}$ and $RC 2_{i}$, we have:

• 1. $M1_{i}$ $\Leftrightarrow$ $Maj 1_{i}$,

• 2. $M2_{i}$ $\Leftrightarrow$ $Maj 2_{i}$.

Proof

• 1. Assume that $RC 2_{i}$ and $M1_{i}$ hold for a relation $\mathrel {\mathcal {R}}$ . If we have $Not [(w_{i}, a_{-i}) \mathrel {\mathcal {R}}(z_{i}, b_{-i}) ]$ in (19), $M1_{i}$ entails the two remaining possible consequences in (21). On the contrary, if $(w_{i}, a_{-i}) \mathrel {\mathcal {R}}(z_{i}, b_{-i})$ holds true, since we have that $(z_{i}, c_{-i}) \mathrel {\mathcal {R}}(w_{i}, d_{-i})$, we may apply $RC 2_{i}$ yielding $(y_{i}, a_{-i}) \mathrel {\mathcal {R}}(x_{i}, b_{-i})$ or $(x_{i}, c_{-i}) \mathrel {\mathcal {R}}(y_{i}, d_{-i})$, which are the desired consequences in order to establish that $Maj 1_{i}$ holds.

• 2. Assume that $RC 1_{i}$ and $Maj 1_{i}$ hold. If $(z_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i})$ is true then $Maj 1_{i}$ implies that the first or the third conclusion of $M1_{i}$ is true. Otherwise, we have $(x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i})$ and $(z_{i}, c_{-i}) \mathrel {\mathcal {R}}(w_{i}, d_{-i})$. Applying $RC 1_{i}$ we get either $(z_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i})$ or $(x_{i}, c_{-i}) \mathrel {\mathcal {R}}(y_{i}, d_{-i})$. We have assumed that the former does not hold, hence the latter is true, which establishes $M1_{i}$.

• 3. Assuming that $RC 1_{i}$ and $M2_{i}$ hold, we show that $Maj 2_{i}$ is satisfied. If the second consequence in (20) does not hold, i.e., if we have $Not [(z_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i}) ]$, then $M2_{i}$ entails one or the other consequence in $Maj 2_{i}$. On the contrary, if $(z_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i})$ holds, considering the third premise of $Maj 2_{i}$, i.e., $(y_{i}, c_{-i}) \mathrel {\mathcal {R}}(x_{i}, d_{-i})$ and using $RC 1_{i}$, we get either consequence of $Maj 2_{i}$.

• 4. Finally, assuming that $RC 2_{i}$ and $Maj 2_{i}$ hold, we derive $M2_{i}$. This is immediate whenever $(w_{i}, a_{-i}) \mathrel {\mathcal {R}}(z_{i}, b_{-i})$ is true since then $Maj 2_{i}$ implies that the first or the third conclusion of $M2_{i}$ is true. In the opposite case, from $(x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i})$ and $(y_{i}, c_{-i}) \mathrel {\mathcal {R}}(x_{i}, d_{-i})$, we obtain, using $RC 2_{i}$, that $(w_{i}, a_{-i}) \mathrel {\mathcal {R}}(z_{i}, b_{-i})$ or $(z_{i}, c_{-i}) \mathrel {\mathcal {R}}(w_{i}, d_{-i})$. Since the former has been assumed to be false, the latter, which is the third conclusion of $M2_{i}$, is true, concluding the proof.

The equivalence of $M1_{i}$ and $Maj 1_{i}$ under $RC 1_{i}$ and $RC 2_{i}$ results from the first two items. The equivalence of $M2_{i}$ and $Maj 2_{i}$, under $RC 1_{i}$ and $RC 2_{i}$ is a consequence of items 3 and 4.$\square$

We also have the following result.

Lemma 35

If relation $\mathrel {\mathcal {R}}$ satisfies $RC 2_{i}$, $M1_{i}$ and $Maj 2_{i}$, then it satisfies $RC 1_{i}$.

Proof

By Lemma 11.3 in Bouyssou and Pirlot (2007), we have that $RC 2_{i}$ and $M1_{i}$ imply $UC _{i}$. By co-duality arguments, this implies that $RC 2_{i}$ and $Maj 2_{i}$ imply $LC _{i}$. By Lemma 8.3 in Bouyssou and Pirlot (2007), $RC 2_{i}$, $UC _{i}$ and $LC _{i}$ imply $RC 1_{i}$.

Theorem 36

(Characterizations of CR) Let $\mathrel {\mathcal {R}}$ be a relation on $X$. The following statements are equivalent:

• 1. $\mathrel {\mathcal {R}}$ is a concordance relation (CR),

• 2. $\mathrel {\mathcal {R}}$ satisfies $RC 1$, $RC 2$, $M1$ and $M2$,

• 3. $\mathrel {\mathcal {R}}$ satisfies $RC 1$, $RC 2$, $Maj 1$ and $Maj 2$.

The axioms used in each of the above characterizations are independent in the class of complete relations and in the class of asymmetric relations.

Proof

• 1. Let us first note that any relation $\mathrel {\mathcal {R}}$ that satisfies $RC 2$ is either reflexive or irreflexive. The relation is irreflexive if for all $x \in X$, we have $Not [x \mathrel {\mathcal {R}}x ]$. Assume there is some $x$ such that $x \mathrel {\mathcal {R}}x$ and consider any $z \in X$. From $(x_{i}, x_{-i}) \mathrel {\mathcal {R}}(x_{i}, x_{-i})$ and $RC 2_{i}$, we deduce that $(z_{i}, x_{-i}) \mathrel {\mathcal {R}}(z_{i}, x_{-i})$. For $j \ne i$, using $RC 2_{j}$, we can similarly show that $(z_{i}, z_{j}, x_{-ij}) \mathrel {\mathcal {R}}(z_{i}, z_{j}, x_{-ij})$. Continuing in a similar way, we finally obtain $z \mathrel {\mathcal {R}}z$.

• 2. By Proposition 8.1, we know that any concordance relation $\mathrel {\mathcal {R}}$ is either reflexive or irreflexive. If $\mathrel {\mathcal {R}}$ is reflexive, Theorem 27 establishes the first characterization. Since any irreflexive CR is the co-dual of a reflexive CR, Lemma 31 implies that the second characterization holds for irreflexive CR ’s.

• 3. Lemma 34 establishes that under conditions $RC 1$ and $RC 2$, $M1$ is equivalent to $Maj 1$ and $M2$ is equivalent to $Maj 2$. As a consequence, both characterizations are valid for reflexive CR ’s. Using Lemma 31, this implies that both characterizations are also valid for irreflexive CR ’s.

• 4. We know (Theorem 27) that axioms $RC 1$, $RC 2$, $M1$ and $M2$ (first characterization) are independent in the class of complete relations. The following examples (the same as for Theorem 27) show their independence. Each axiom is violated on a single attribute, referred to by $i$, and satisfied on all other attributes.

Violated axiom	$RC 1_{i}$	$RC 2_{i}$	$M1_{i}$	$M2_{i}$
Example	79	77	78	83

The following examples (see in “Appendix 2”) prove that $RC 1$, $RC 2$, $Maj 1$ and $Maj 2$ are also independent in the class of complete relations:

Violated axiom	$RC 1_{i}$	$RC 2_{i}$	$Maj 1_{i}$	$Maj 2_{i}$
Example	80	77	78	83

Using co-duality, this implies that both sets of axioms are independent in the class of asymmetric relations.$\square$

Remark 37

For showing the independence of $RC 1$ in both characterizations, we need two different examples (we used Examples 79 and 80). It is indeed a consequence of Lemma 35 that there is no relation satisfying $RC 2_{i}$, $M1_{i}$, $Maj 1_{i}$, $M2_{i}$, $Maj 2_{i}$ and $Not [ RC 1_{i} ]$.$\square$

Remark 38

(Earlier characterization of asymmetric CR) For asymmetric relations, the properties in the third item in Theorem 36 have been previously shown to constitute a characterization of a concordance relation by a set of independent axioms (Bouyssou and Pirlot 2006, Theorem 2).$\square$

Remark 39

(Other characterizations) In view of Lemma 34, it is clear that

• $\mathrel {\mathcal {R}}$ satisfies $RC 1$, $RC 2$, $Maj 1$ and $M2$,

• $\mathrel {\mathcal {R}}$ satisfies $RC 1$, $RC 2$, $M1$ and $Maj 2$,

are two alternative characterizations of a CR. The examples used in the proof of Theorem 36 for showing that $RC 1$, $RC 2$, $M1$ and $M2$ are independent in the class of complete relations also show that $RC 1$, $RC 2$, $Maj 1$ and $M2$ are independent in the same class. By co-duality, this implies that $RC 1$, $RC 2$, $Maj 1$ and $M2$ are independent in the class of asymmetric relations. This means that these axioms constitute a third independent characterization of CR. In contrast, $RC 1$, $RC 2$, $M1$ and $Maj 2$ do not form an independent family of axioms, be it in the class of complete or in the class of asymmetric relations, as implied by Lemma 35. We have no simple explanation for this asymmetry. We conjecture that it is linked to the fact that the respective rôles of $RC 1$ and of $RC 2$ are not symmetric in our analysis.$\square$

Remark 40

(Axioms $UC$ and $LC$ and co-duality) Since $UC$ and $LC$ are cross co-dual conditions (see Remark 33), the family of axioms $RC 1, RC 2, UC$ and $LC$ clearly offer a characterization of concordance relations within both reflexive or irreflexive relations (as well as within both complete or asymmetric relations). Unfortunately, these axioms are not independent since Bouyssou and Pirlot (2005b), Lemma 16 establishes that $RC 2_{i}, UC _{i}$ and $LC _{i}$ imply $RC 1_{i}$. Dropping $RC 1$, however, yields an independent characterization of a CR since we know (Bouyssou and Pirlot 2005b, Theorem 18) that a binary relation is a CR iff it satisfies $RC 2, UC$ and $LC$ . Moreover, the latter axioms are independent in the class of complete relations as attested by Examples 77, 78 and 83, in “Appendix 2”. The dependence of $RC 1, RC 2, UC$ and $LC$ lead us to introduce axioms $M1$ and $M2$, which are discussed in Bouyssou and Pirlot (2007). Theorem 36 tells us that $Maj 1$ and $Maj 2$, introduced for characterizing asymmetric relations, can substitute $M1$ and $M2$, also in the case of complete relations, without hampering the independence of the axioms.$\square$

4.3 A new independent self co-dual characterization of CR

Axioms $M1_{i}$ and $Maj 1_{i}$ (resp. $M2_{i}$ and $Maj 2_{i}$) admit a common weaker formulation, $MM 1_{i}$ (resp. $MM 2_{i}$), that simplifies the characterizations of CR and will be useful in the sequel.

Definition 41

(Axioms $MM 1$, $MM 2$) Let $\mathrel {\mathcal {R}}$ be a binary relation on a set $X= \prod _{i=1}^n X_{i}$. This relation is said to satisfy:

$$\begin{aligned}&MM 1_{i} \text { if } \left. \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i})\\ \text {and}\\ (z_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i})\\ \text {and}\\ (z_{i}, c_{-i}) \mathrel {\mathcal {R}}(w_{i}, d_{-i}) \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (y_{i}, a_{-i}) \mathrel {\mathcal {R}}(x_{i}, b_{-i})\\ \text {or}\\ (w_{i}, a_{-i}) \mathrel {\mathcal {R}}(z_{i}, b_{-i})\\ \text {or}\\ (x_{i}, c_{-i})\mathrel {\mathcal {R}}(y_{i}, d_{-i}), \end{array} \right. \\&MM 2_{i} \text { if } \left. \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i})\\ \text {and}\\ (w_{i}, a_{-i}) \mathrel {\mathcal {R}}(z_{i}, b_{-i})\\ \text {and}\\ (y_{i}, c_{-i}) \mathrel {\mathcal {R}}(x_{i}, d_{-i}) \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (y_{i}, a_{-i}) \mathrel {\mathcal {R}}(x_{i}, b_{-i})\\ \text {or}\\ (z_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i})\\ \text {or}\\ (z_{i}, c_{-i})\mathrel {\mathcal {R}}(w_{i}, d_{-i}), \end{array} \right. \end{aligned}$$

for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$ and all $a_{-i}, b_{-i}, c_{-i}, d_{-i} \in X_{-i}$. We say that $MM 1$ (resp. $MM 2$) holds if $MM 1_{i}$ (resp. $MM 2_{i}$) holds for all $i \in N$.

Note that $MM 1_{i}$, without its second premise, is identical to $M1_{i}$. $MM 1_{i}$, without its second conclusion, is $Maj 1_{i}$. $MM 1_{i}$, without both its second premise and its second conclusion, is $UC _{i}$. $MM 1_{i}$ is clearly a weaker condition than both $M1_{i}$ and $Maj 1_{i}$. Similar observations can be made, linking $MM 2_{i}, M2_{i}$ and $Maj 2_{i}$. $MM 2_{i}$ is a weakened variant of the two others. However, under $RC 1_{i}$ and $RC 2_{i}$, $MM 1_{i}$ can be shown to be equivalent to $M1_{i}, Maj 1_{i}$ and $UC_{i}$, as stated in the following lemma. A similar statement holds for $MM 2_{i}$.

Lemma 42

The following implications hold for all $i \in N$:

• 1. $MM 1_{i}$ and $RC 1_{i}$ entail $M1_{i}$,

• 2. $MM 1_{i}$ and $RC 2_{i}$ entail $Maj 1_{i}$,

• 3. $MM 2_{i}$ and $RC 2_{i}$ entail $M2_{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} \Leftrightarrow M1_{i} \Leftrightarrow Maj 1_{i} \Leftrightarrow UC _{i}$,

• 2. $MM 2_{i} \Leftrightarrow M2_{i} \Leftrightarrow Maj 2_{i} \Leftrightarrow LC _{i}$.

Proof

The proofs are very similar to those used to establish Lemma 34. We prove the first implication, leaving the three others to the reader. Assume that $MM 1_{i}$ and $RC 1_{i}$ hold. We show that $M1_{i}$ must be true. Applying $RC 1_{i}$ to the premises of $M1_{i}$ yields $(x_{i}, c_{-i}) \mathrel {\mathcal {R}}(y_{i}, d_{i})$ or $(z_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i})$. If the former is true, then $M1_{i}$ is verified. Else, all three premises of $MM 1_{i}$ are satisfied, which entails the disjunction of three conclusions that is common to $M1_{i}$ and $MM 1_{i}$. The proofs of the two equivalences directly results from the four implications, Lemma 34 and Lemma 11.3 and 11.4 in Bouyssou and Pirlot (2007). The latter says that $RC 2_{i}$ and $M1_{i}$ entail $UC _{i}$ and that $RC 1_{i}$ and $M2_{i}$ entail $LC _{i}$. By definition, $UC _{i}$ entails $M1_{i}$ and $LC _{i}$ entails $M2_{i}$. $\square$

Axioms $MM 1_{i}$ and $MM 2_{i}$ are cross co-dual, as are $UC _{i}$ and $LC _{i}$ (Remark 33). More precisely, we have:

Lemma 43

Let $\mathrel {\mathcal {R}}$ be a binary relation on $X$ and $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ its co-dual. The following hold for all $i \in N$:

• 1. $\mathrel {\mathcal {R}}$ satisfies $MM 1_{i}$ iff $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ satisfies $MM 2_{i}$,

• 2. $\mathrel {\mathcal {R}}$ satisfies $MM 2_{i}$ iff $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ satisfies $MM 1_{i}$.

Proof

The proof results immediately from contraposition and using the definition of the co-dual.$\square$

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

Theorem 44

The relation $\mathrel {\mathcal {R}}$ on $X$ is a CR iff it satisfies $RC 1, RC 2, MM 1$ and $MM 2$. These axioms are independent both in the class of complete relations and in the class of asymmetric relations.

Proof

Using Lemma 42.1 and 42.3, we obtain that a relation $\mathrel {\mathcal {R}}$ satisfying $RC 1$, $RC 2$, $MM 1$ and $MM 2$ also satisfies $M1$ and $M2$. Theorem 36 entails that $\mathrel {\mathcal {R}}$ is a CR. The converse is also true by Theorem 36 and the fact that $M1$ implies $MM 1$ and $M2$ implies $MM 2$. The examples used to show the independence of the axioms in Theorem 36 can be used here. This is due to the fact, on the one hand, that $M1$ and $Maj 1$ imply $MM 1$, hence if $\mathrel {\mathcal {R}}$ is an example of relation satisfying one of the former, it satisfies the latter. On the other hand, if $\mathrel {\mathcal {R}}$ is an example that does not satisfy $M1_{i}$ or $Maj 1_{i}$ (resp. $M2_{i}$ or $Maj 2_{i}$), while satisfying $RC 1$ and $RC 2$, it cannot satisfy $MM 1_{i}$ (resp. $MM 2_{i}$), due to Lemma 42.$\square$

4.4 Concordance relations with attribute transitivity

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

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

Definition 45

(Axioms $AC 1$, $AC 2$, $AC 3$) Let $\mathrel {\mathcal {R}}$ be a binary relation on a set $X= \prod _{i=1}^n X_{i}$. This relation is said to satisfy:

$$\begin{aligned}&AC 1_{i} \text { if } \left. \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i}) \\ \text {and}\\ (z_{i}, c_{-i}) \mathrel {\mathcal {R}}(w_{i}, d_{-i}) \\ \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (z_{i},a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i}) \\ \text {or}\\ (x_{i},c_{-i}) \mathrel {\mathcal {R}}(w_{i}, d_{-i}), \\ \end{array} \right. \\&AC 2_{i} \text { if } \left. \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i}) \\ \text {and}\\ (z_{i}, c_{-i}) \mathrel {\mathcal {R}}(w_{i}, d_{-i}) \\ \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i}) \\ \text {or}\\ (z_{i}, c_{-i}) \mathrel {\mathcal {R}}(y_{i}, d_{-i}), \\ \end{array} \right. \\&AC 3_{i} \text { if } \left. \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i})\\ \text {and}\\ (y_{i}, c_{-i}) \mathrel {\mathcal {R}}(w_{i}, d_{-i}) \\ \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(z_{i}, b_{-i})\\ \text {or}\\ (z_{i}, c_{-i}) \mathrel {\mathcal {R}}(w_{i}, d_{-i}), \\ \end{array} \right. \end{aligned}$$

for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$, all $a_{-i}, b_{-i}, c_{-i}, d_{-i} \in X_{-i}$.

We say that $\mathrel {\mathcal {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 \in N$.

An interpretation of these axioms was provided in Bouyssou and Pirlot (2004a). Essentially, these axioms are related to the existence of linear arrangements of the elements (levels) of $X_{i}$. $AC 1_{i}$ suggests that the elements of $X_{i}$ can be linearly ordered relatively to “upward dominance”: if $x_{i}$ “upward dominates” $z_{i}$, then $(z_{i}, c_{-i})\mathrel {\mathcal {R}}(w_{i}, d_{-i})$ entails $(x_{i}, c_{-i})\mathrel {\mathcal {R}}(w_{i}, d_{-i})$. $AC 2_{i}$ has a similar interpretation regarding “downward dominance”. $AC 3_{i}$ ensures that the upward and downward dominance orders are not incompatible. The following gives a precise definition of the upward and downward dominance relations.

Definition 46

(Relations $\mathrel {\succsim _{i}^{+}}$, $\mathrel {\succsim _{i}^{-}}$ and $\mathrel {\succsim _{i}^{\pm }}$) Let $\mathrel {\mathcal {R}}$ be a binary relation on a set $X= \prod _{i=1}^n {X_{i}}$. We define the binary relations $\mathrel {\succsim _{i}^{+}}$, $\mathrel {\succsim _{i}^{-}}$ and $\mathrel {\succsim _{i}^{\pm }}$ on $X_{i}$ letting, for all $x_{i}, y_{i} \in X_{i}$,

$$\begin{aligned} x_{i} \mathrel {\succsim _{i}^{+}}y_{i}&\Leftrightarrow \forall a_{-i} \in X_{-i}, b \in X, [(y_{i}, a_{-i}) \mathrel {\mathcal {R}}b \Rightarrow (x_{i}, a_{-i}) \mathrel {\mathcal {R}}b], \end{aligned}$$

(25)

$$\begin{aligned} x_{i} \mathrel {\succsim _{i}^{-}}y_{i}&\Leftrightarrow \forall a \in X, b_{-i} \in X_{-i}, [a \mathrel {\mathcal {R}}(x_{i}, b_{-i}) \Rightarrow a \mathrel {\mathcal {R}}(y_{i}, b_{-i})], \end{aligned}$$

(26)

$$\begin{aligned} x_{i} \mathrel {\succsim _{i}^{\pm }}y_{i}&\Leftrightarrow x_{i} \mathrel {\succsim _{i}^{+}}y_{i} \text { and } x_{i} \mathrel {\succsim _{i}^{-}}y_{i}. \end{aligned}$$

(27)

By definition, $\mathrel {\succsim _{i}^{+}}$, $\mathrel {\succsim _{i}^{-}}$ and $\mathrel {\succsim _{i}^{\pm }}$ are transitive relations. Axioms $AC 1_{i}$, $AC 2_{i}$ and $AC 3_{i}$ ensure that they are complete, as restated in the next lemma.

Lemma 47

(Bouyssou and Pirlot (2004a), Lemma 3.1–4) Let $\mathrel {\mathcal {R}}$ be a binary relation on a set $X= \prod _{i=1}^n X_{i}$. $\mathrel {\mathcal {R}}$ satisfies:

• 1. $AC 1_{i}\,\Leftrightarrow \,\mathrel {\succsim _{i}^{+}}$ is complete,

• 2. $AC 2_{i}$ $\Leftrightarrow$ $\mathrel {\succsim _{i}^{-}}$ is complete,

• 3. $AC 3_{i} \Leftrightarrow [ Not [x_{i} \mathrel {\succsim _{i}^{+}}y_{i} ] \Rightarrow y_{i} \mathrel {\succsim _{i}^{-}}x_{i}] \Leftrightarrow [ Not [x_{i} \mathrel {\succsim _{i}^{-}}y_{i} ] \Rightarrow y_{i} \mathrel {\succsim _{i}^{+}}x_{i}]$,

• 4. $[ AC 1_{i}$, $AC 2_{i}$ and $AC 3_{i}]$ $\Leftrightarrow$ $\mathrel {\succsim _{i}^{\pm }}$ is complete.

As implied by Remark 3, a concordance relation with attribute transitivity is a CR having a representation $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}} \rangle$, with relations $\mathrel {S_{i}}$ that are semiorders. The following theorem characterizes CR with attribute transitivity. As for Theorems 27 and 29, it is a slight variation on Theorem 26 in Bouyssou and Pirlot (2007), which is formulated here for general binary relations. The independence of the axioms is not only valid for reflexive but also complete relations.

Theorem 48

The binary relation $\mathrel {\mathcal {R}}$ on $X= \prod _{i=1}^n X_{i}$ is a concordance relation with attribute transitivity (CR-AT), i.e., has a representation $\langle {\mathrel {\unrhd }}, {\mathrel {S_{i}}} \rangle$ in which all $\mathrel {S_{i}}$ are semiorders, iff it satisfies $RC 1$, $RC 2$, $AC 1$, $AC 3$, $M1$, $M2$. In the class of complete relations, these axioms are independent.

Proof

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

Violated axiom	$RC 1_{i}$	$RC 2_{i}$	$AC 1_{i}$	$AC 3_{i}$	$M1_{i}$	$M2_{i}$
Example	79	77	81	82	78	83

All these relations are complete. Therefore the axioms are independent in the set of complete relations.$\square$

Remark 49

Note that axiom $AC 2$ does not appear in this characterization because it is not independent of the other axioms. Indeed, Lemma 27.1 in Bouyssou and Pirlot (2006) and Lemma 11, items 3 and 4 in Bouyssou and Pirlot (2007) imply that under $RC 1$, $RC 2$, $M1$ and $M2$, axioms $AC 1$ and $AC 2$ are equivalent. $AC 2$ can thus substitute $AC 1$ in the characterization of reflexive CR with attribute transitivity.$\square$

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

Lemma 50

Let $\mathrel {\mathcal {R}}$ be any relation on $X$ and $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ its co-dual. The following equivalences hold, for all $i \in N$:

• 1. $\mathrel {\mathcal {R}}$ satisfies $AC 1_{i}$ iff $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ satisfies $AC 2_{i}$,

• 2. $\mathrel {\mathcal {R}}$ satisfies $AC 2_{i}$ iff $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ satisfies $AC 1_{i}$,

• 3. $\mathrel {\mathcal {R}}$ satisfies $AC 3_{i}$ iff $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ satisfies $AC 3_{i}$.

In the theorem below we extend the characterizations obtained in Theorem 36 to CR with attribute transitivity (CR-AT). The next lemma will be used in the proof of the theorem.

Lemma 51

Let $\mathrel {\mathcal {R}}$ be a relation on $X$ and $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{d}}$ its dual relation. We have the following:

• 1. $\mathrel {\mathcal {R}}$ satisfies $RC 1_{i}$ (resp. $RC 2_{i}$, $AC 3_{i}$, $M1_{i}$, $Maj 1_{i}$, $M2_{i}$, $Maj 2_{i}$, $UC _{i}$, $LC _{i}$) for some $i \in N$ if and only if $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{d}}$ satisfies the same property,

• 2. $\mathrel {\mathcal {R}}$ satisfies $AC 1_{i}$ (resp. $AC 2_{i}$) for some $i \in N$ if and only if $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{d}}$ satisfies $AC 2_{i}$ (resp. $AC 1_{i}$) for the same $i$.

Proof

The proof consists in checking that each of the equivalences holds, starting from the properties definition. It is easy once it is noted that, for all $i \in N$ and all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$,

$$\begin{aligned}&\displaystyle x_{i} \mathrel {\mathord {\mathrel {\succsim _{i}^{+}}}(\mathrel {\mathord {\mathrel {\mathcal {R}}}^{d}})} y_{i} \iff y_{i} \mathrel {\mathord {\mathrel {\succsim _{i}^{-}}}(\mathrel {\mathcal {R}})} x_{i},\\&\displaystyle x_{i} \mathrel {\mathord {\mathrel {\succsim _{i}^{-}}}(\mathrel {\mathord {\mathrel {\mathcal {R}}}^{d}})} y_{i} \iff y_{i} \mathrel {\mathord {\mathrel {\succsim _{i}^{+}}}(\mathrel {\mathcal {R}})} x_{i},\\&\displaystyle (x_{i}, y_{i}) \mathrel {\mathord {\mathrel {\succsim _{i}^{*}}}(\mathrel {\mathord {\mathrel {\mathcal {R}}}^{d}})} (z_{i}, w_{i}) \iff (y_{i}, x_{i}) \mathrel {\mathord {\mathrel {\succsim _{i}^{*}}}(\mathrel {\mathcal {R}})} (w_{i}, z_{i}), \end{aligned}$$

where $\mathrel {\mathord {\mathrel {\succsim _{i}^{+}}}(K)}$ (resp. $\mathrel {\mathord {\mathrel {\succsim _{i}^{-}}}(K)}$, $\mathrel {\mathord {\mathrel {\succsim _{i}^{*}}}(K)}$) denotes the relation $\mathrel {\succsim _{i}^{+}}$ (resp. $\mathrel {\succsim _{i}^{-}}$, $\mathrel {\succsim _{i}^{*}}$) using $K$ as the base relation.

A result similar to Lemma 32 can be established for the upward and downward dominance relations $\mathrel {\succsim _{i}^{+}}, \mathrel {\succsim _{i}^{-}}, \mathrel {\succsim _{i}^{\pm }}$. As in this lemma, our notation makes explicit whether the upward and downward dominance relations refer to $\mathrel {\mathcal {R}}$ or its co-dual $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$.

Lemma 52

Let $\mathrel {\mathcal {R}}$ be a binary relation on $X$ and $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ its co-dual. For all $i \in N$, for all $x_{i}, y_{i} \in X_{i}$, we have:

• 1. $x_{i} \mathrel {\mathord {\mathrel {\succsim _{i}^{+}}}(\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}})} y_{i}$ iff $x_{i} \mathrel {\mathord {\mathrel {\succsim _{i}^{-}}}(\mathrel {\mathcal {R}})} y_{i}$,

• 2. $x_{i} \mathrel {\mathord {\mathrel {\succsim _{i}^{-}}(\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}})}} y_{i}$ iff $x_{i} \mathrel {\mathord {\mathrel {\succsim _{i}^{+}}}(\mathrel {\mathcal {R}})} y_{i}$,

• 3. $x_{i} \mathrel {\mathord {\mathrel {\succsim _{i}^{\pm }}}(\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}})} y_{i}$ iff $x_{i} \mathrel {\mathord {\mathrel {\succsim _{i}^{\pm }}}(\mathrel {\mathcal {R}})} y_{i}$.

Proof

The proof follows immediately from Definition 46 and from that of $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$.$\square$

Theorem 53

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

Proof

If $\mathrel {\mathcal {R}}$ is a CR-AT, we know by Theorem 48 that it satisfies $RC 1$, $RC 2$, $AC 1$, $AC 3$, $M1$ and $M2$. $M1$ (resp. $M2$) implies $MM 1$ (resp. $MM 2$). Conversely, if $\mathrel {\mathcal {R}}$ satisfies $RC 1$, $RC 2$, $AC 1$, $AC 3$, $MM 1$ and $MM 2$, it satisfies $M1$ and $M2$ (Lemma 42) hence it is a CR-AT.

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

To prove the independence of the axioms in the set of complete relations, the examples used in the proof of Theorem 48 are also suitable here since these examples satisfy $M1_{i}$ whenever they satisfy $MM 1_{i}$ and similarly for $M2_{i}$ and $MM 2_{i}$. According with Lemma 51, the duals of these examples show that substituting $AC 1$ by $AC 2$ in the characterization preserves the independence of the axioms. The co-duals of the same examples and of their duals are asymmetric relations showing the independence of the axioms characterizing CR-AT in the class of asymmetric relations.$\square$

Corollary 54

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

Proof

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

Violated axiom	$RC 1_{i}$	$RC 2_{i}$	$AC 1_{i}$	$AC 3_{i}$	$Maj 1_{i}$	$Maj 2_{i}$
Example	$(80)^d$	77	81	82	78	83

Note that $(80)^d$ denotes the dual⁶ of the relation described in Example 80. In view of Lemma 51, this relation does not satisfy $RC 1_{1}$. It satisfies $AC 1_{1}$ but not $AC 2_{1}$. The possibility of substituting $AC 1$ by $AC 2$ and keep the independence of the axioms is shown as in Theorem 53 by taking the dual of the examples. The independence of the axioms in the set of asymmetric relations is established by taking the co-dual of the examples.$\square$

4.5 Characterizations of a CDR

In the last section we have shown that two different “dual” characterizations of concordance relations (Theorem 48 and Corollary 54) can be obtained using co-duality. The picture is not the same for concordance–discordance relations, which are significantly more complex objects than CR. As discussed in Sect. 3.6, reflexes of automatic “co-dualization” must be abandoned since the co-dual of a CDR is not a CDR but a CRB (Proposition 19). Nonetheless, two characterizations of reflexive and irreflexive CDR can be obtained from previous results.

With Theorem 29, we have recalled a characterization of a reflexive concordance-discordance relation (R-CDR). It involves axiom $M1$ and a weakening of axiom $M2$, called $M3$ (see Definition 28). Examining the proof of this result in Bouyssou and Pirlot (2009a) shows that the reflexivity of the relation plays no rôle, so that this characterization is valid both for reflexive and irreflexive CDR ’s.

A similar characterization of asymmetric CDR was given in Bouyssou and Pirlot (2006), using axiom $Maj 1$ and a weakening of $Maj 2$, that was called $Maj 3$. This axiom was constructed as $M3$ from $M2$, by adding a premise to $Maj 2$.

In the same spirit as we introduced, in the previous section, axiom $MM 1$ (resp. $MM 2$) generalizing both $M1$ and $Maj 1$ (resp. $M2$ and $Maj 2$), we now define the new axiom $MM 3$ as follows.

Definition 55

($MM 3$ and $Maj 3$) A relation $\mathrel {\mathcal {R}}$ on $X$ satisfies

$$\begin{aligned} MM 3_{i} \text { if } \left. \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i}) \\ \text {and}\\ (w_{i}, a_{-i}) \mathrel {\mathcal {R}}(z_{i}, b_{-i})\\ \text {and}\\ (y_{i}, c_{-i}) \mathrel {\mathcal {R}}(x_{i}, d_{-i})\\ \text {and}\\ (z_{i}, e_{-i}) \mathrel {\mathcal {R}}(w_{i}, f_{-i})\\ \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (y_{i}, a_{-i}) \mathrel {\mathcal {R}}(x_{i}, b_{-i}) \\ \text {or}\\ (z_{i}, a_{-i})\mathrel {\mathcal {R}}(w_{i}, b_{-i})\\ \text {or}\\ (z_{i}, c_{-i})\mathrel {\mathcal {R}}(w_{i}, d_{-i}), \end{array} \right. \end{aligned}$$

(28)

for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$ and all $a_{-i}, b_{-i}, c_{-i}$, $d_{-i}$, $e_{-i}$, $f_{-i}$ $\in$ $X_{-i}$. $Maj 3_{i}$ is the same condition as $MM 3_{i}$ except that the second conclusion has been removed. We say that $\mathrel {\mathcal {R}}$ satisfies $MM 3$ (resp. $Maj 3$) if it satisfies $MM 3_{i}$ (resp. $Maj 3_{i}$) for all $i \in N$.

Dropping the second premise in $MM 3_{i}$ yields $M3_{i}$. Removing the second conclusion yields $Maj 3_{i}$. Obviously, $M3_{i}$ (resp. $Maj 3_{i}$) entails $MM 3_{i}$. Under $RC 1_{i}$ and $RC 2_{i}$, axioms $M3_{i}$, $Maj 3_{i}$ and $MM 3_{i}$ are equivalent as shown in the following lemma.

Lemma 56

The following implications hold:

• 1. $MM 3_{i}$ and $RC 2_{i}$ entail $M3_{i}$,

• 2. $MM 3_{i}$ and $RC 1_{i}$ entail $Maj 3_{i}$,

• 3. $M3_{i}$ and $RC 1_{i}$ entail $Maj 3_{i}$,

• 4. $Maj 3_{i}$ and $RC 2_{i}$ entail $M3_{i}$.

Under $RC 1_{i}$ and $RC 2_{i}$, we have:

$$\begin{aligned} MM 3_{i} \Leftrightarrow M3_{i} \Leftrightarrow Maj 3_{i}. \end{aligned}$$

Proof

The proof, similar to that of Lemma 42, is left to the reader.$\square$

Remark 57

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

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

Theorem 58

(Characterization of CDR) The relation $\mathrel {\mathcal {R}}$ on $X$ is a concordance–discordance relation (CDR) iff $\mathrel {\mathcal {R}}$ satisfies $RC 1$, $RC 2$, $MM 1$ and $MM 3$. These axioms are independent in the set of complete relations and in the set of asymmetric relations.

Proof

By Theorem 29, we know that a relation $\mathrel {\mathcal {R}}$ that is a CDR satisfies $RC 1$, $RC 2$, $M1$ and $M2$. Since $M1$ implies $MM 1$ and $M3$ implies $MM 3$, $\mathrel {\mathcal {R}}$ also satisfies $MM 1$ and $MM 3$. Conversely, if a relation $\mathrel {\mathcal {R}}$ satisfies $RC 1$ and $RC 2$, then $MM 1$ (resp. $MM 3$) is equivalent to $M1$ (resp. $M3$) (by Lemmas 42 and 56). Hence, using Theorem 29, we have that $\mathrel {\mathcal {R}}$ is a CDR.

In the class of complete relations, the following examples (in “Appendix 2”) prove the independence of the axioms.

Violated axiom	$RC 1_{i}$	$RC 2_{i}$	$MM 1_{i}$	$MM 3_{i}$
Example	80	77	78	83

For proving the independence of the axioms in the class of asymmetric relations, we can still use co-duality arguments for obtaining part of the required examples but not all of them. Since Examples 80 and 77 satisfy $MM 1$ and $MM 2$, their co-dual also satisfy these two properties (Lemma 43), hence they satisfy $MM 3$. In addition, Example $(80)^{cd}$ satisfies $RC 2_{i}$ but not $RC 1_{i}$ and conversely for Example $(77)^{cd}$. Example 83 satisfies $RC 1$, $RC 2$, $MM 1$, $MM 2_{j}$, for $j\ne 1$ but not $MM 2_{1}$. Its co-dual satisfies $RC 1, RC 2, MM 1_{j}$ for $j\ne 1$, $MM 2$, hence $MM 3$, but not $MM 1_{1}$. It thus proves the independence of $MM 1_{1}$ for asymmetric relations. For proving the independence of $MM 3$, we need a new example. Example 84 is an asymmetric relation verifying $RC 1, RC 2, MM 1$, but not $MM 3_{1}$. To sum up, the following examples (in “Appendix 2”) prove the independence of the axioms in the class of asymmetric relations:

Violated axiom	$RC 1_{i}$	$RC 2_{i}$	$MM 1_{i}$	$MM 3_{i}$
Example	$(80)^{cd}$	$(77)^{cd}$	$(83)^{cd}$	84

$\square$

Corollary 59

The relation $\mathrel {\mathcal {R}}$ on $X$ is a concordance–discordance relation (CDR)

• 1. iff $\mathrel {\mathcal {R}}$ satisfies $RC 1$, $RC 2$, $Maj 1$ and $Maj 3$,

• 2. iff $\mathrel {\mathcal {R}}$ satisfies $RC 1$, $RC 2$, $M1$ and $M3$.

Both sets of axioms are independent in the class of complete relations and in the class of asymmetric relations.

Proof

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

4.6 CDR with attribute transitivity

A CDR with attribute transitivity (CDR-AT) is not just a CDR which admits a representation in which $\mathrel {S_{i}}$ are semiorders. A certain relationship between $\mathrel {S_{i}}$ and $\mathrel {V_{i}}$ must also be verified. CDR-AT have been studied in Bouyssou and Pirlot (2009a), Section 5.2. We first recall the definition of a CDR-AT and the characterization result obtained in Bouyssou and Pirlot (2009a).

Definition 60

(CDR with attribute transitivity) A CDR with attribute transitivity (CDR-AT) is a CDR for which, for all $i \in N$:

• $\mathrel {S_{i}}$ is a semiorder with asymmetric part $\mathrel {P_{i}}$,

• $\mathrel {V_{i}}$ is the asymmetric part of a semiorder $\mathrel {U_{i}}$ with ${\mathrel {U_{i}}} \supseteq {\mathrel {S_{i}}}$ and, hence, ${\mathrel {V_{i}}} \subseteq {\mathrel {P_{i}}}$,

• $(\mathrel {S_{i}}, \mathrel {U_{i}})$ form a homogeneous chain of semiorders.

The following is Theorem 29 in Bouyssou and Pirlot (2009a). The independence of the axioms is stated for reflexive relations.

Theorem 61

The relation $\mathrel {\mathcal {R}}$ on $X$ is a CDR-AT iff $\mathrel {\mathcal {R}}$ satisfies $RC 1$, $RC 2$, $AC 1$, $AC 2$, $AC 3$, $M1$ and $M3$. These axioms are independent in the class of reflexive relations.

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

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

Theorem 62

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

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

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

Proof

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

For complete CDR-AT, axiom $RC 1$ can be dropped from their characterization, in view of Proposition 74. In the class of complete relations, axioms $RC 2$, $AC 1$, $AC 2$, $AC 3$, $MM 1$ and $MM 3$ are independent as attested by the following examples:

Violated axiom	$RC 2_{i}$	$AC 1_{i}$	$AC 2_{i}$	$AC 3_{i}$	$MM 1_{i}$	$MM 3_{i}$
Example	77	85	86	82	78	83

In the class of asymmetric CDR-AT, the axioms $RC 1, RC 2$, $AC 1$, $AC 2$, $AC 3$, $MM 1$ and $MM 3$ are independent as shown by the examples below.

Violated axiom	$RC 1$	$RC 2_{i}$	$AC 1_{i}$	$AC 2_{i}$	$AC 3_{i}$	$MM 1_{i}$	$MM 3_{i}$
Example	90	$(77)^{cd}$	88	89	$(82)^{cd}$	87	84

$(77)^{cd}$ designates the co-dual of the relation in Example 77 and similarly for $(82)^{cd}$.$\square$

Remark 63

Substituting $MM 1$ by $M1$ or by $Maj 1$ and/or $MM 3$ by $M3$ or by $Maj 3$ in one of the characterizations in Theorem 62 leads to other characterizations of CDR-AT. The resulting sets of axioms remain independent in the class of complete relations but this is not always the case in the class of asymmetric relations, as we shall see.

• 1. The case of complete relations. The examples used in the proof of Theorem 62 for showing the independence of $RC 2_{i}$, $AC 1_{i}$, $AC 2_{i}$ and $AC 3_{i}$, namely Examples 77, 85, 86 and 82, all satisfy axioms $M1$, $Maj 1$, $M3$, $Maj 3$. Examples 78 (resp. 83) showing the independence of $MM 1$ (resp. $MM 3$) satisfies neither $M1$ nor $Maj 1$ (resp. neither $M3$ nor $Maj 3$).

• 2. The case of asymmetric relations. In view of Proposition 76 in “Appendix 1”, $RC 1_{i}$ is implied by $RC 2_{i}$, $AC 1_{i}$, $AC 2_{i}$, $AC 3_{i}$, $Maj 1_{i}$ and $Maj 3_{i}$. It is also the case when $Maj 3$ is substituted by $M3$ (since Lemma 56.4 tells us that $Maj 3_{i}$ and $RC 2_{i}$ entail $M3_{i}$). The following sets of axioms however are independent in the class of asymmetric relations:

  • (a) $RC 1$, $RC 2$, $AC 1$, $AC 2$, $AC 3$, $M1$ and $M3$,

  • (b) $RC 1$, $RC 2$, $AC 1$, $AC 2$, $AC 3$, $Maj 1$ and $M3$.

  The independence of these axioms results from the same examples as those used in Theorem 62 for asymmetric relations. Indeed, Examples 90, $(77)^{cd}$, 88, 89 and $(82)^{cd}$ all satisfy $MM 1$, $M1$, $Maj 1$, $MM 3$, $M3$ and $Maj 3$. Example 87 violates not only $MM 1$ but also $M1$ and $Maj 1$. Example 84 violates not only $MM 3$ but also $M3$ and $Maj 3$.$\square$

4.7 Concordance relations with bonus

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

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

Definition 64

(Axiom $DMM 3$) A relation $\mathrel {\mathcal {R}}$ on $X$ satisfies

$$\begin{aligned} DMM 3_{i} \text { if } \left. \begin{array}{c} (x_{i}, a_{-i}) \mathrel {\mathcal {R}}(y_{i}, b_{-i})\\ \text {and}\\ (z_{i}, a_{-i}) \mathrel {\mathcal {R}}(w_{i}, b_{-i})\\ \text {and}\\ (z_{i}, c_{-i}) \mathrel {\mathcal {R}}(w_{i}, d_{-i}) \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (y_{i}, a_{-i}) \mathrel {\mathcal {R}}(x_{i}, b_{-i})\\ \text {or}\\ (w_{i}, a_{-i})\mathrel {\mathcal {R}}(z_{i}, b_{-i})\\ \text {or}\\ (x_{i}, c_{-i})\mathrel {\mathcal {R}}(y_{i}, d_{-i})\\ \text {or}\\ (z_{i}, e_{-i}) \mathrel {\mathcal {R}}(w_{i}, f_{-i}), \end{array} \right. \end{aligned}$$

(29)

for all $x_{i}, y_{i}, z_{i}, w_{i} \in X_{i}$ and all $a_{-i}, b_{-i}, c_{-i}, d_{-i}, e_{-i}, f_{-i} \in X_{-i}$. We say that $\mathrel {\mathcal {R}}$ satisfies $DMM 3$ if it satisfies $DMM 3_{i}$ for all $i \in N$.

Note that dropping the second conclusion of $DMM 3_{i}$ yields an axiom that is the “co-dual” of $M3_{i}$ and which we call $DM 3_{i}$. In a similar way, dropping the second premise of $DMM 3_{i}$ yields an axiom that is the “co-dual” of $Maj 3_{i}$ and which we shall call $DMaj 3_{i}$. We note these results in the following lemma.

Lemma 65

The relation $\mathrel {\mathcal {R}}$ on $X$ satisfies $MM 3_{i}$ (resp. $M3_{i}, Maj 3_{i}$) iff its co-dual $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ satisfies $DMM 3_{i}$ (resp. $DM 3_{i}, DMaj 3_{i}$).

Comparing $DMM 3_{i}$ with $MM 1_{i}$, we observe that the former only differ from the latter by an additional conclusion. We thus have the following.

Lemma 66

If the relation $\mathrel {\mathcal {R}}$ on $X$ satisfies $MM 1_{i}$ then it satisfies $DMM 3_{i}$.

As compared with $MM 1_{i}$, $DMM 3_{i}$ offers a fourth possible conclusion, which interprets, under $RC 1_{i}$ and $RC 2_{i}$, as the possible existence of a “preference difference” $(z_{i}, w_{i})$ on attribute $i$ that is “so large” that we always have $(z_{i}, e_{-i}) \mathrel {\mathcal {R}}(w_{i}, f_{-i})$ whatever the levels $e_{-i}$ and $f_{-i}$ on the other attributes can be. Such a large difference of preference was called a bonus in Sect. 3.6. This interpretation is established in the next lemma.

Lemma 67

Let $\mathrel {\mathcal {R}}$ be a binary relation on $X$. If $\mathrel {\mathcal {R}}$ satisfies $RC 1_{i}$, $RC 2_{i}$ and $DMM 3_{i}$, then, for all $x_{i}, y_{i}, z_{i}, w_{i}, r_{i}, s_{i} \in X_{i}$, if $(z_{i},w_{i}) \mathrel {\succ _{i}^{*}}(x_{i},y_{i}) \mathrel {\succ _{i}^{*}}(y_{i},x_{i})$, we then have:

• 1. $(z_{i},w_{i}) \mathrel {\succsim _{i}^{*}}(r_{i},s_{i})$,

• 2. $(z_{i}, e_{-i}) \mathrel {\mathcal {R}}(w_{i}, f_{-i})$, for all $e_{-i}, f_{-i} \in X_{-i}$.

Proof

If $(z_{i},w_{i}) \mathrel {\succ _{i}^{*}}(x_{i},y_{i}) \mathrel {\succ _{i}^{*}}(y_{i},x_{i})$, there are $a_{-i}, b_{-i}, c_{-i}, d_{-i} \in X_{-i}$, such that (i) $(x_{i},a_{-i}) \mathrel {\mathcal {R}}(y_{i},b_{-i})$, (ii) $Not [(y_{i},a_{-i}) \mathrel {\mathcal {R}}(x_{i},b_{-i}) ]$, (iii) $(z_{i},c_{-i}) \mathrel {\mathcal {R}}(w_{i},d_{-i})$ and (iv) $Not [(x_{i},c_{-i}) \mathrel {\mathcal {R}}(y_{i},d_{-i}) ]$. Applying $RC 1_{i}$ to (i) and (iii), and taking (iv) into account yields (v) $(z_{i},a_{-i}) \mathrel {\mathcal {R}}(w_{i},b_{-i})$. Since (i), (iii) and (v) match the premises of $DMM 3_{i}$, we get one of the four possible conclusions. The first and the third one are in contradiction with (ii) and (iv). Due to $RC 2_{i}$ and Lemma 22.2, we obtain that $(y_{i},x_{i}) \mathrel {\succsim _{i}^{*}}(w_{i},z_{i})$. From this and (ii) we deduce that the third conclusion is not true. The only remaining possibility is thus the fourth conclusion of $DMM 3_{i}$, which establishes the second part of the lemma and implies the first part.$\square$

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

Theorem 68

(Characterization of CRB) The relation $\mathrel {\mathcal {R}}$ on $X$ is a CRB iff it satisfies $RC 1, RC 2, MM 2$ and $DMM 3$. These axioms are independent both in the class of complete and in the class of asymmetric relations.

Proof

This result is a direct consequence of two facts:

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

• $\mathrel {\mathcal {R}}$ satisfies $RC 1$, $RC 2$, $MM 2$ and $DMM 3$ iff its co-dual $\mathrel {\mathord {\mathrel {\mathcal {R}}}^{cd}}$ satisfies $RC 1$, $RC 2$, $MM 1$ and $MM 3$ (Lemmas 31, 43 and 65).

Examples showing the independence of the axioms are obtained by taking the co-dual of those used in the proof of Theorem 58 to show the independence of the axioms characterizing a CDR.$\square$

Corollary 69

The relation $\mathrel {\mathcal {R}}$ on $X$ is a CRB

• 1. iff it satisfies $RC 1, RC 2, M2$ and $DM 3$,

• 2. iff it satisfies $RC 1, RC 2, Maj 2$ and $DMaj 3$.

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

Proof

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

4.8 CRB with attribute transitivity

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

Definition 70

(CRB with attribute transitivity) A CRB with attribute transitivity (CRB-AT) is a CRB for which, for all $i \in N$:

• $\mathrel {S_{i}}$ is a semiorder with asymmetric part $\mathrel {P_{i}}$,

• $\mathrel {V_{i}}$ is the asymmetric part of a semiorder $\mathrel {U_{i}}$ with ${\mathrel {U_{i}}} \supseteq {\mathrel {S_{i}}}$ and, hence, ${\mathrel {V_{i}}} \subseteq {\mathrel {P_{i}}}$,

• $(\mathrel {S_{i}}, \mathrel {U_{i}})$ form an homogeneous chain of semiorders.

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

Theorem 71

• 1. The relation $\mathrel {\mathcal {R}}$ on $X$ is a CRB-AT iff $\mathrel {\mathcal {R}}$ satisfies $RC 1$, $RC 2$, $AC 1$, $AC 2$, $AC 3$, $MM 2$ and $DMM 3$. These axioms are independent in the class of irreflexive relations.

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

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

Proof

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

Remark 72

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

Remark 73

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

• $RC 1$, $RC 2$, $AC 1$, $AC 2$, $AC 3$, $Maj 2$ and $DM 3$,

• $RC 1$, $RC 2$, $AC 1$, $AC 2$, $AC 3$, $M2$ and $DM 3$.$\square$

5 Conclusion

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

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

• 2. This research has illustrated the interest of an axiomatic analysis by showing

  • (a) that new models (namely, concordance relations with bonus) can be defined and characterized just by using such a simple transformation as co-duality,

  • (b) that new characterizations of known models can be obtained using such a transformation,

  • (c) that axiomatic analysis allows us to present a corpus of models (reflexive and asymmetric outranking relations) in a unified framework and to better understand their inter-relations.

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

A noticeable product of our investigation using co-duality is the observation that the asymmetric part of a reflexive concordance–discordance relation is not a concordance–discordance relation since it involves both veto and bonus effects. Knowing the properties of such relations (i.e., the asymmetric part of a reflexive concordance discordance relation) is of importance since they are used in some multi-criteria sorting methods, namely the optimistic version of the Electre Tri method (Roy and Bouyssou 1993, p. 391. This version is also known as “pseudo-disjunctive”). The pessimistic version of this method (also known as “pseudo-conjunctive”) is well-understood (it is characterized in Słowiński et al. 2002; Bouyssou and Marchant 2007a, b) and methods for learning its parameters on the basis of assignment examples were developed since 1998 (see, e.g., Mousseau and Słowiński 1998; Mousseau et al. 2006; Leroy et al. 2011). It is not the case with the optimistic version. No axiomatic characterization is known. A method for learning its parameters was recently proposed (Zheng et al 2011; Zheng et al. 2014). The recent interest for this method in applications Metchebon Takougang et al. 2014 motivates further investigation. For lack of place, an axiomatic characterization of the asymmetric part of a concordance–discordance relation was not included in the present paper. This is dealt with in Bouyssou and Pirlot (2014).

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

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

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

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

Appendices

Appendix 1: Propositions 74 and 76

Proposition 74

If $\mathrel {\mathcal {R}}$ is a complete binary relation on $X$ satisfying $RC 2$, $AC 1$, $AC 2$, $AC 3$, $MM 1$ and $MM 3$, then $\mathrel {\mathcal {R}}$ satisfies $RC 1$.

For proving this proposition, we need the following lemma.

Lemma 75

Let $\mathrel {\mathcal {R}}$ be a binary relation on $X$ satisfying $RC 2_{i}$, $AC 1_{i}$, $AC 2_{i}$, $AC 3_{i}$ and $Maj 1_{i}$, on some attribute $i$. Consider four levels $x,y,z,w \in X_{i}$ such that the pairs $(x,y)$ and $(z,w)$ are not comparable w.r.t. the relation $\mathrel {\succsim _{i}^{*}}$, which we denote by $(x,y) \bowtie (z,w))$. The relative positions of these pairs and the opposite pairs are as follows:

• 1. $[(y,x) \mathrel {\sim _{i}^{*}}(w,z)] \mathrel {\succ _{i}^{*}} [(x,y)\bowtie (z,w)]$,

• 2. furthermore, one of the following configurations holds true:

  • (a) $[(y,z) \mathrel {\sim _{i}^{*}}(y,x) \mathrel {\sim _{i}^{*}}(w,z)] \mathrel {\succ _{i}^{*}} [(x,y)\bowtie (z,w)] \mathrel {\succ _{i}^{*}}(z,y)$

  • (b) $[(w,x) \mathrel {\sim _{i}^{*}}(y,x) \mathrel {\sim _{i}^{*}}(w,z)] \mathrel {\succ _{i}^{*}} [(x,y)\bowtie (z,w)] \mathrel {\succ _{i}^{*}}(x,w)$.

  In the above, the notation $[(x,y)\bowtie (z,w)]$ means that the incomparable pairs $[(x,y)$ and $(z,w)$ have the same relationships with the other pairs listed.

Proof

(of Lemma 75) 1. Let $x,y,z,w \in X_{i}$ be such that the pairs $(x,y)$ and $(z,w)$ are incomparable w.r.t. relation $\mathrel {\succsim _{i}^{*}}$, i.e., we have:

$$\begin{aligned} Not [(x,y) \mathrel {\succsim _{i}^{*}}(z,w) ] \text { and } Not [(z,w) \mathrel {\succsim _{i}^{*}}(x,y) ]. \end{aligned}$$

(30)

In view of Definition 21, this means that there are $a,b,c,d \in X_{-i}$ such that:

$$\begin{aligned} \begin{array}{cc} (x,c) \mathrel {\mathcal {R}}(y,d), &{} Not [(z,c) \mathrel {\mathcal {R}}(w,d) ], \\ (z,a) \mathrel {\mathcal {R}}(w,b), &{} Not [(x,a) \mathrel {\mathcal {R}}(y,b) ], \end{array} \end{aligned}$$

(31)

in other words, $\mathrel {\mathcal {R}}$ does not satisfy $RC 1_{i}$.

Using $RC 2_{i}$ and Lemma 22.2 imply that we have $(y,x) \mathrel {\succsim _{i}^{*}}(w,z)$ and $(w,z) \mathrel {\succsim _{i}^{*}}(y,x)$, yielding:

$$\begin{aligned} (y,x) \mathrel {\sim _{i}^{*}}(w,z) \end{aligned}$$

(32)

The same axiom and lemma entail that $(x,y)$ and $(y,x)$ are comparable w.r.t. $\mathrel {\succsim _{i}^{*}}$, i.e., we must have $(x,y) \mathrel {\succsim _{i}^{*}}(y,x)$ or $(y,x) \mathrel {\succsim _{i}^{*}}(x,y)$. The former is incompatible with $Maj 1_{i}$ as we shall see. Note that $\mathrel {\mathcal {R}}$ satisfies $Maj 1_{i}$ by Lemma 34.1.

2. We show that assuming $(x,y) \mathrel {\succsim _{i}^{*}}(y,x)$ leads to a contradiction. From $(x,y) \mathrel {\succsim _{i}^{*}}(y,x)$, we first derive the following consequences:

• 1. $(z,w) \mathrel {\succ _{i}^{*}}(w,z)$. Assuming $Not [(z,w) \mathrel {\succsim _{i}^{*}}(w,z) ]$ implies, by Lemma 22.2, that $(w,z) \mathrel {\succsim _{i}^{*}}(z,w)$. Hence we would have: $(x,y) \mathrel {\succsim _{i}^{*}}(y,x) \mathrel {\sim _{i}^{*}}(w,z) \mathrel {\succsim _{i}^{*}}(z,w)$. Using the transitivity of $\mathrel {\succsim _{i}^{*}}$ leads to $(x,y) \mathrel {\succsim _{i}^{*}}(z,w)$, a contradiction. The same contradiction can be derived if we suppose $(z,w) \mathrel {\sim _{i}^{*}}(w,z)$.

• 2. $(x,y) \mathrel {\succ _{i}^{*}}(y,x)$. Else, from $(x,y) \mathrel {\sim _{i}^{*}}(y,x)$ we would derive $(z,w) \mathrel {\succ _{i}^{*}}(w,z) \mathrel {\sim _{i}^{*}}(y,x) \mathrel {\sim _{i}^{*}}(x,y)$, from which we deduce $(z,w) \mathrel {\succ _{i}^{*}}(x,y)$, a contradiction.

• 3. $(x,y) \mathrel {\succ _{i}^{*}}(w,z)$. Assuming $Not [(x,y) \mathrel {\succsim _{i}^{*}}(w,z) ]$ implies, by Lemma 22.2, that $(y,x) \mathrel {\succsim _{i}^{*}}(z,w)$. Hence we would have: $(w,z) \mathrel {\sim _{i}^{*}}(y,x) \mathrel {\succsim _{i}^{*}}(z,w)$. Using the transitivity of $\mathrel {\succsim _{i}^{*}}$ leads to $(w,z) \mathrel {\succsim _{i}^{*}}(z,w)$, a contradiction. The same contradiction can be derived if we suppose $(x,y) \mathrel {\sim _{i}^{*}}(w,z)$.

• 4. $(z,w) \mathrel {\succ _{i}^{*}}(y,x)$ is established in a similar way as the previous item.

We thus have the following situation: $(x,y)$ and $(z,w)$ are incomparable differences w.r.t. $\mathrel {\succsim _{i}^{*}}$, both are strictly preferred to $(y,x)$ and $(w,z)$, which are indifferent pairs.

We now use $AC 1_{i}$, $AC 2_{i}$ and $AC 3_{i}$. The main consequence of these axioms is that the relations $\mathrel {\succsim _{i}^{+}}, \mathrel {\succsim _{i}^{-}}$ and $\mathrel {\succsim _{i}^{\pm }}$ are complete (Lemma 47). Moreover, we have, for all $s,t, u, v \in X_{i}$:

$$\begin{aligned} s \mathrel {\succsim _{i}^{+}}t&\Rightarrow (s,u) \mathrel {\succsim _{i}^{*}}(t,u) \end{aligned}$$

(33)

$$\begin{aligned} s \mathrel {\succsim _{i}^{-}}t&\Rightarrow (v,t) \mathrel {\succsim _{i}^{*}}(v,s) \end{aligned}$$

(34)

(direct consequence of $AC 1_{i}, AC 2_{i}$ and the definitions of $\mathrel {\succsim _{i}^{+}}, \mathrel {\succsim _{i}^{-}}$ and $\mathrel {\succsim _{i}^{*}}$).

Consider the pairs $(x,y)$ and $(z,w)$. We claim that there are $u,v \in X_{i}$ such that $(u,v) \mathrel {\succ _{i}^{*}}(x,y)$ and $(u,v) \mathrel {\succ _{i}^{*}}(z,w)$. Furthermore, $(u,v)$ is either $(x,w)$ or $(z,y)$. Observe first that we cannot have:

• 1. $x \mathrel {\succsim _{i}^{\pm }}z$ and $w \mathrel {\succsim _{i}^{\pm }}y$. Else, using (33) and (34), we would have $(x,y) \mathrel {\succsim _{i}^{*}}(z,y) \mathrel {\succsim _{i}^{*}}(z,w)$, a contradiction with the fact that $(x,y)$ and $(z,w)$ are incomparable,

• 2. $z \mathrel {\succsim _{i}^{\pm }}x$ and $y \mathrel {\succsim _{i}^{\pm }}w$. Else, using (33) and (34), we would have $(z,w) \mathrel {\succsim _{i}^{*}}(x,w) \mathrel {\succsim _{i}^{*}}(x,y)$, a contradiction with the fact that $(x,y)$ and $(z,w)$ are incomparable.

Since $\mathrel {\succsim _{i}^{\pm }}$ is complete, we thus have either $[x \mathrel {\succsim _{i}^{\pm }}z$ and $y \mathrel {\succsim _{i}^{\pm }}w]$ or $[z \mathrel {\succsim _{i}^{\pm }}x$ and $w \mathrel {\succsim _{i}^{\pm }}y]$. Consider the former case. Using (33) and (34) yields $(x,w) \mathrel {\succsim _{i}^{*}}(z,w)$ and $(x,w) \mathrel {\succsim _{i}^{*}}(x,y)$. We can have neither $(x,w) \mathrel {\sim _{i}^{*}}(z,w)$ nor $(x,w) \mathrel {\sim _{i}^{*}}(x,y)$, because this would imply that $(x,y)$ and $(z,w)$ are comparable. Our claim is thus proved with $(u,v) = (x,w)$. If the situation was such that $z \mathrel {\succsim _{i}^{\pm }}x$ and $w \mathrel {\succsim _{i}^{\pm }}y$, then we would have that $(z,y) \mathrel {\succsim _{i}^{*}}(z,w)$ and $(z,y) \mathrel {\succsim _{i}^{*}}(x,y)$. The rôle of $(u,v)$ would be played by $(z,y)$. Our claim is proved.

Assume first that $(u,v) = (x,w)$. From $(x,c) \mathrel {\mathcal {R}}(y,d)$ in (31) and $(x,w) \mathrel {\succsim _{i}^{*}}(x,y)$, we derive $(x,c)\mathrel {\mathcal {R}}(w,d)$. Similarly, $(z,a) \mathrel {\mathcal {R}}(w,b)$ and $(x,w) \mathrel {\succsim _{i}^{*}}(z,w)$ entail $(x,a)\mathrel {\mathcal {R}}(w,b)$. This allows us to derive a contradiction with $Maj 1_{i}$. Indeed, we have $(x,c)\mathrel {\mathcal {R}}(w,d)$, $(x,a)\mathrel {\mathcal {R}}(w,b)$ and $(z,a)\mathrel {\mathcal {R}}(w,b)$. Using $Maj 1_{i}$ yields either $(w,a)\mathrel {\mathcal {R}}(z,b)$ or $(z,c)\mathrel {\mathcal {R}}(w,d)$. None of this conclusions holds true. The latter is false by hypothesis (see (31)) and the former cannot be true since $(x,y)\mathrel {\succ _{i}^{*}}(w,z)$ and $Not [(x,a)\mathrel {\mathcal {R}}(y,b) ]$. The case in which we assume $(u,v) = (z,y)$ yields a similar contradiction. As a conclusion, we have established that $(y,x)\mathrel {\succ _{i}^{*}}(x,y)$.

3. We draw the consequences of the fact that $(y,x)\mathrel {\succ _{i}^{*}}(x,y)$, by adapting the ideas that we used in Part 2 of the present proof, under the opposite hypothesis.

The fact that $(y,x) \mathrel {\succsim _{i}^{*}}(x,y)$ entails the following:

• 1. $(w,z) \mathrel {\succ _{i}^{*}}(z,w)$. Assuming $Not [(w,z) \mathrel {\succsim _{i}^{*}}(z,w) ]$ implies, by Lemma 22.2, that $(z,w) \mathrel {\succsim _{i}^{*}}(w,z)$. Hence we would have: $(z,w) \mathrel {\succsim _{i}^{*}}(w,z) \mathrel {\sim _{i}^{*}}(y,x) \mathrel {\succsim _{i}^{*}}(x,y)$. Using the transitivity of $\mathrel {\succsim _{i}^{*}}$ leads to $(z,w) \mathrel {\succsim _{i}^{*}}(x,y)$, a contradiction. The same contradiction arises if we suppose $(z,w) \mathrel {\sim _{i}^{*}}(w,z)$.

• 2. $(y,x) \mathrel {\succ _{i}^{*}}(x,y)$. Else, from $(y,x) \mathrel {\sim _{i}^{*}}(x,y)$ we would derive $(x,y) \mathrel {\sim _{i}^{*}}(y,x) \mathrel {\sim _{i}^{*}}(w,z) \mathrel {\succ _{i}^{*}}(z,w)$, from which we deduce $(x,y) \mathrel {\succ _{i}^{*}}(z,w)$, a contradiction.

• 3. $(y,x) \mathrel {\succ _{i}^{*}}(z,w)$. Assuming $Not [(y,x) \mathrel {\succsim _{i}^{*}}(z,w) ]$ implies, by Lemma 22.2, that $(x,y) \mathrel {\succsim _{i}^{*}}(w,z)$. Hence we would have: $(x,y) \mathrel {\succsim _{i}^{*}}(w,z) \mathrel {\sim _{i}^{*}}(y,x)$. Using the transitivity of $\mathrel {\succsim _{i}^{*}}$ leads to $(x,y) \mathrel {\succsim _{i}^{*}}(y,x)$, a contradiction. The same contradiction can be derived if we suppose $(y,x) \mathrel {\sim _{i}^{*}}(z,w)$.

• 4. $(w,z) \mathrel {\succ _{i}^{*}}(x,y)$ is established in a similar way as the previous item.

We thus have the following situation: $(y,x)$ and $(w,z)$ are incomparable differences w.r.t. $\mathrel {\succsim _{i}^{*}}$. Both are strictly preferred to $(x,y)$ and $(z,w)$, which are indifferent pairs.

Using $AC 1_{i}$, $AC 2_{i}$ and $AC 3_{i}$, we derive exactly the same consequences as in Part 2, i.e., we have either $[x \mathrel {\succsim _{i}^{\pm }}z$ and $y \mathrel {\succsim _{i}^{\pm }}w]$ or $[z \mathrel {\succsim _{i}^{\pm }}x$ and $w \mathrel {\succsim _{i}^{\pm }}y]$.

If $[x \mathrel {\succsim _{i}^{\pm }}z$ and $y \mathrel {\succsim _{i}^{\pm }}w]$, we conclude that $(x,y) \mathrel {\succsim _{i}^{*}}(z,y)$ and $(z,w) \mathrel {\succsim _{i}^{*}}(z,y)$. We can have neither $(x,y) \mathrel {\sim _{i}^{*}}(z,y)$ nor $(z,w) \mathrel {\sim _{i}^{*}}(z,y)$, because this would imply that $(x,y)$ and $(z,w)$ are comparable. Since we have $Not [(z,y) \mathrel {\succsim _{i}^{*}}(x,y) ]$, we deduce that $(y,z) \mathrel {\succsim _{i}^{*}}(y,x)$, using Lemma 22.2. Having $(y,z) \mathrel {\succ _{i}^{*}}(y,x)$ is impossible since this would contradict $Maj 1_{i}$. Indeed, assume that there are $e, f \in X_{-i}$ such that $(y,e) \mathrel {\mathcal {R}}(z,f)$ and $Not [(y,e) \mathrel {\mathcal {R}}(x,f) ]$. Since $(y,x) \mathrel {\succ _{i}^{*}}(z,w)$ and $(z,a) \mathrel {\mathcal {R}}(w,b)$, we get $(y,a) \mathrel {\mathcal {R}}(x,b)$. From $(y,z) \mathrel {\succsim _{i}^{*}}(y,x)$ and $(y,a) \mathrel {\mathcal {R}}(x,b)$, we derive $(y,a) \mathrel {\mathcal {R}}(z,b)$. By (31), we also have $Not [(x,a) \mathrel {\mathcal {R}}(y,b) ]$ . The following configuration is not compatible with $Maj 1_{i}$: $(y,a) \mathrel {\mathcal {R}}(x,b)$, $(y,a) \mathrel {\mathcal {R}}(z,b)$, $(y,e) \mathrel {\mathcal {R}}(z,f)$, $Not [(x,a) \mathrel {\mathcal {R}}(y,b) ]$, $Not [(y,e) \mathrel {\mathcal {R}}(x,f) ]$. We have thus established that $(y,z) \mathrel {\sim _{i}^{*}}(y,x)$. Starting from $Not [(z,y) \mathrel {\succsim _{i}^{*}}(z,w) ]$, one proves similarly that $(y,z) \mathrel {\sim _{i}^{*}}(w,z)$ and we finally have that $(y,z) \mathrel {\sim _{i}^{*}}(w,z) \mathrel {\sim _{i}^{*}}(y,x)$.

In the case in which $[z \mathrel {\succsim _{i}^{\pm }}x$ and $w \mathrel {\succsim _{i}^{\pm }}y]$, one proves in an analogous way that $(x,y) \mathrel {\succ _{i}^{*}}(x,w)$, $(z,w) \mathrel {\succ _{i}^{*}}(x,w)$ and $(w,x) \mathrel {\sim _{i}^{*}}(y,x) \mathrel {\sim _{i}^{*}}(w,z)$.

This concludes the proof of Lemma 75.$\square$

Proof

(of Proposition 74) Since $\mathrel {\mathcal {R}}$ satisfies $MM 1$ and $RC 2$, it satisfies also $Maj 1$ (Lemma 42.2). Let us assume that $\mathrel {\mathcal {R}}$ does not verify $RC 1_{i}$ on some attribute $i$. We shall derive a contradiction from this assumption. If $RC 1_{i}$ is not verified by $\mathrel {\mathcal {R}}$, there exist four levels $x,y,z,w \in X_{i}$ such that $(x,y)$ and $(z,w)$ are incomparable w.r.t. relation $\mathrel {\succsim _{i}^{*}}$, or, in other words, there are $a,b,c,d \in X_{-i}$ such that:

$$\begin{aligned} \begin{array}{cc} (x,c) \mathrel {\mathcal {R}}(y,d) &{} Not [(z,c) \mathrel {\mathcal {R}}(w,d) ] \\ (z,a) \mathrel {\mathcal {R}}(w,b) &{} Not [(x,a) \mathrel {\mathcal {R}}(y,b) ] \end{array} \end{aligned}$$

(35)

Hence $\mathrel {\mathcal {R}}$ is in the conditions of application of Lemma 75. We shall assume that the configuration described in conclusion 2.(a) of the lemma holds true, i.e., we have:

$$\begin{aligned}{}[(y,z) \mathrel {\sim _{i}^{*}}(y,x) \mathrel {\sim _{i}^{*}}(w,z)] \mathrel {\succ _{i}^{*}} [(x,y) \bowtie (z,w)] \mathrel {\succ _{i}^{*}}(z,y). \end{aligned}$$

(36)

Note that case 2.(b) can be dealt with similarly. We leave it to the reader.

Since $\mathrel {\mathcal {R}}$ satisfies $MM 3$ and $RC 2$, it satisfies $M3$ (Lemma 56.1). In the configuration described by (36), $M3_{i}$ implies that the pair $(z,y)$ is a veto. Indeed, assume that there are $e,f \in X_{-i}$ such that $(z,e) \mathrel {\mathcal {R}}(y,f)$. We have $(x,y) \mathrel {\succ _{i}^{*}}(z,y)$, which means there are $g,h \in X_{-i}$ such that $(x,g) \mathrel {\mathcal {R}}(y,h)$ and $Not [(z,g) \mathrel {\mathcal {R}}(y,h) ]$. It holds true that $(y,a) \mathrel {\mathcal {R}}(x,b)$ since, by (35), $(z,a) \mathrel {\mathcal {R}}(w,b)$ and, by (36), $(y,x) \mathrel {\succ _{i}^{*}}(z,w)$. Finally, we have $Not [(x,a) \mathrel {\mathcal {R}}(y,b) ]$ by (35) and $Not [(z,a) \mathrel {\mathcal {R}}(y,b) ]$ since $(x,y) \mathrel {\succ _{i}^{*}}(z,y)$. Gathering the relevant preferences, i.e., $(y,a) \mathrel {\mathcal {R}}(x,b)$, $(x,g) \mathrel {\mathcal {R}}(y,h)$, $(z,e) \mathrel {\mathcal {R}}(y,f)$, $Not [(x,a) \mathrel {\mathcal {R}}(y,b) ]$, $Not [(z,a) \mathrel {\mathcal {R}}(y,b) ]$ and $Not [(z,g) \mathrel {\mathcal {R}}(y,h) ]$, yields a contradiction with $M3_{i}$. We thus have shown that for all $e,f \in X_{-i}$, we have

$$\begin{aligned} Not [(z,e) \mathrel {\mathcal {R}}(y,f) ] \end{aligned}$$

(37)

The fact that $\mathrel {\mathcal {R}}$ is complete enters into play in the following way. Since $\mathrel {\mathcal {R}}$ is complete, (37) entails that for all $e,f \in X_{-i}$, we have $(y,e) \mathrel {\mathcal {R}}(z,f)$. Since (36) tells us that $(y,z) \mathrel {\sim _{i}^{*}}(w,z) \mathrel {\sim _{i}^{*}}(y,x)$, we also have, for all $e,f \in X_{-i}$, $(w,e) \mathrel {\mathcal {R}}(z,f)$ and $(y,e) \mathrel {\mathcal {R}}(x,f)$. In other words, $(y,z), (w,z)$ and $(y,x)$ are bonuses as defined in Sect. 3.6.

The relation $\mathrel {\mathcal {R}}$ induces not only a relation $\mathrel {\succsim _{i}^{*}}$ comparing pairs of levels on $X_{i}$, but also a similar relation $\mathrel {\succsim _{-i}^{*}}$ on the pairs of elements of $X_{-i}$. For $e,f,g,h \in X_{-i}$, we have $(e,f) \mathrel {\succsim _{-i}^{*}} (g,h)$ iff, for all $u,v \in X_{i}$, $[(u,g) \mathrel {\mathcal {R}}(v,h)] \Rightarrow [(u,e) \mathrel {\mathcal {R}}(v,f)]$. The assumption (35) also means that the pairs $(a,b), (c,d) \in X_{-i} \times X_{-i}$ are not comparable w.r.t. $\mathrel {\succsim _{-i}^{*}}$. This relation is transitive by definition and complete iff $RC 1_{i}$ holds.

If $AC 1, AC 2$ and $AC 3$ hold, we claim that there are $g,h \in X_{-i}$ with $(a,b) \mathrel {\succsim _{-i}^{*}} (g,h)$ and $(c,d) \mathrel {\succsim _{-i}^{*}} (g,h)$. $AC 1, AC 2$ and $AC 3$ imply that $\mathrel {\succsim _{j}^{\pm }}$ is a complete weak order for all $j \in N$. We define $g$ (resp.$h$) by specifying its level $g_{j}$ (resp. $h_{j}$) for each $j \ne i$ as follows: for all $j \ne i$,

$$\begin{aligned} g_{j} = \min {\{a_{j},c_{j}\}}= \left\{ \begin{array}{cc} a_{j} &{} \text {if } c_{j} \mathrel {\succsim _{j}^{\pm }} a_{j} \\ c_{j} &{} \text {if } a_{j} \mathrel {\succsim _{j}^{\pm }} c_{j} \end{array} \right. \end{aligned}$$

(38)

$$\begin{aligned} h_{j} = \max {\{b_{j},d_{j}\}}= \left\{ \begin{array}{cc} b_{j} &{} \text {if } b_{j} \mathrel {\succsim _{j}^{\pm }} d_{j} \\ d_{j} &{} \text {if } d_{j} \mathrel {\succsim _{j}^{\pm }} b_{j} \end{array} \right. \end{aligned}$$

(39)

Starting from the trivial $(a,b) \mathrel {\succsim _{-i}^{*}} (a,b)$ and applying repeatedly (33) and (34), using $g$ and $h$, we obtain $(a,b) \mathrel {\succsim _{-i}^{*}} (g,h)$. One proves similarly that $(c,d) \mathrel {\succsim _{-i}^{*}} (g,h)$.

We finish the proof by showing that the above induces a contradiction with $M3_{i}$. We have that $Not [(x,a) \mathrel {\mathcal {R}}(y,b) ]$ entails $Not [(x,g) \mathrel {\mathcal {R}}(y,h) ]$ and $Not [(z,c) \mathrel {\mathcal {R}}(w,d) ]$ entails $Not [(z,g) \mathrel {\mathcal {R}}(w,h) ]$ (since a difference on $X_{-i}$ is substituted by a smaller one w.r.t. $\mathrel {\succsim _{-i}^{*}}$). Since $(y,x)$ is a bonus, we have in particular $(y,g) \mathrel {\mathcal {R}}(x,h)$. By (35), we have $(x,c) \mathrel {\mathcal {R}}(y,d)$ and $(z,a) \mathrel {\mathcal {R}}(w,b)$. Gathering the relevant preferences, i.e., $(y,g) \mathrel {\mathcal {R}}(x,h)$, $(x,c) \mathrel {\mathcal {R}}(y,d)$, $(z,a) \mathrel {\mathcal {R}}(w,b)$, $Not [(x,g) \mathrel {\mathcal {R}}(y,h) ]$, $Not [(z,g) \mathrel {\mathcal {R}}(w,h) ]$ and $Not [(z,c) \mathrel {\mathcal {R}}(w,d) ]$, yields a contradiction with $M3_{i}$.$\square$

The proposition below is another result, besides Proposition 74, showing that $RC 1$ has relationships with the other axioms even though the considered relations here are neither complete nor asymmetric.

Proposition 76

If $\mathrel {\mathcal {R}}$ is a relation on $X$ satisfying $RC 2_{i}$, $AC 1_{i}$, $AC 2_{i}$, $AC 3_{i}$, $Maj 1_{i}$ and $Maj 3_{i}$, for some $i \in N$, then $\mathrel {\mathcal {R}}$ satisfies $RC 1_{i}$.

Proof

Let us assume that $\mathrel {\mathcal {R}}$ does not verify $RC 1_{i}$ on some attribute $i$, i.e., there exist $x,y,z,w \in X_{i}$ and $a,b,c,d \in X_{-i}$ such that:

$$\begin{aligned} \begin{array}{cc} (x,c) \mathrel {\mathcal {R}}(y,d) &{} Not [(z,c) \mathrel {\mathcal {R}}(w,d) ] \\ (z,a) \mathrel {\mathcal {R}}(w,b) &{} Not [(x,a) \mathrel {\mathcal {R}}(y,b) ]. \end{array} \end{aligned}$$

(40)

In other words, the pairs $(x,y)$ and $(z,w)$ are incomparable w.r.t. relation $\mathrel {\succsim _{i}^{*}}$. Therefore, $\mathrel {\mathcal {R}}$ is in the conditions of application of Lemma 75 and we have $[(y,x) \mathrel {\sim _{i}^{*}}(w,z)] \mathrel {\succ _{i}^{*}} [(x,y), (z,w)]$.

The latter is not compatible with $Maj 3_{i}$ as we shall see. Since $(y,x) \mathrel {\succ _{i}^{*}}(z,w)$ and using $(z,a) \mathrel {\mathcal {R}}(w,b)$ in (40), we obtain that $(y,a) \mathrel {\mathcal {R}}(x,b)$. From $(w,z) \mathrel {\sim _{i}^{*}}(y,x)$ and $(y,a) \mathrel {\mathcal {R}}(x,b)$, we derive $(w,a) \mathrel {\mathcal {R}}(z,b)$. We also directly use the four clauses in (40). The following facts contradict $Maj 3_{i}$: $(y,a) \mathrel {\mathcal {R}}(x,b)$, $(w,a) \mathrel {\mathcal {R}}(z,b)$, $(x,c) \mathrel {\mathcal {R}}(y,d)$, $(z,a) \mathrel {\mathcal {R}}(w,b)$, $Not [(x,a) \mathrel {\mathcal {R}}(y,b) ]$ and $Not [(z,c) \mathrel {\mathcal {R}}(w,d) ]$.$\square$

Appendix 2: Examples

The examples below have been checked in order to determine whether they satisfy the following axioms:

$$\begin{aligned}&RC 1,\, RC 2, \, AC 1, \, AC 2,\, AC 3, \, UC ,\, LC ,\,M1,\,M2,\, Maj 1,\, Maj 2,\\&\qquad \qquad MM 1,\, MM 2,\,M3,\, Maj 3,\, MM 3,\, DMM 3. \end{aligned}$$

Those among these axioms that are not satisfied are mentioned below next to the example label. All axioms from the previous list that are not explicitly mentioned are proved to be satisfied. By default, the examples are complete relations. Relations that are asymmetric are explicitly labeled as such, as well as relations that are neither complete nor asymmetric.

Example 77

($Not[RC2_{i}]$) This is example 25 in Bouyssou and Pirlot (2007). Let $N= \lbrace 1,2 \rbrace$ and $X= \lbrace x, y \rbrace \times \lbrace a, b \rbrace$. Let $\mathrel {\mathcal {R}}$ on $X$ be identical to $X^{2}$ except that, $Not [(y,a) \mathrel {\mathcal {R}}(x,a) ]$ and $Not [(y,b) \mathrel {\mathcal {R}}(x,a) ]$. This relation is complete.

It is easy to check that we have:

• $[(x, y), (x, x), (y,y)] \mathrel {\succ _{1}^{*}} (y, x)$ and

• $[(a,b), (b, b)] \mathrel {\succ _{2}^{*}} [(a, a), (b, a)]$.

Using Lemma 22, it is easy to see that $RC1$ and $RC2_{1}$ hold but that $RC2_{2}$ is violated. Using Lemma 8.1 and 8.2 in Bouyssou and Pirlot (2007) it is clear that $UC$ and $LC$ hold so that the same is true for $M1$ and $M2$. As a consequence of Remark 33, we have that $\mathrel {\mathcal {R}}$ satisfies $Maj 1$ and $Maj 2$. Since $M3$ (resp. $Maj 3$) is entailed by $M2$ (resp. $Maj 2$), $\mathrel {\mathcal {R}}$ also satisfies $M3$ (resp. $Maj 3$). Since $\mathrel {\mathcal {R}}$ satisfies $M1$ (resp. $M2$) it satisfies its relaxed version $MM 1$ (resp. $MM 2)$. As $\mathrel {\mathcal {R}}$ satisfies $M2$ it fulfills $M3$ and $MM 3$. As $\mathrel {\mathcal {R}}$ satisfies $M1$ it fulfills $DMM 3$.

Finally, using Lemma 15 in Bouyssou and Pirlot (2007), it is routine to check that we have:

• $x \mathrel {\succ _{1}^{\pm }} y$,

• $a \mathrel {\succ _{2}^{\pm }} b$.

Hence $AC 1$, $AC 2$ and $AC 3$ hold.

Example 78

($Not [ UC _{i}, M1_{i}, Maj 1_{i}, MM 1_{i} ]$) This is Example 33 in Bouyssou and Pirlot (2005b). Also used in the proof of Part 5 of Bouyssou and Pirlot (2007) Lemma 11 and as Example 23 in Bouyssou and Pirlot (2007).

Let $X= \lbrace a, b \rbrace \times \lbrace x, y, z \rbrace$ and $\mathrel {\mathcal {R}}$ on $X$ be identical to the linear order:

$$\begin{aligned} (a,x) \mathrel {\mathcal {R}}(a,y) \mathrel {\mathcal {R}}(a,z) \mathrel {\mathcal {R}}(b,x) \mathrel {\mathcal {R}}(b,y) \mathrel {\mathcal {R}}(b,z), \end{aligned}$$

except that $(a,z)$ and $(b,x)$ are indifferent: $(a,z)\mathrel {\mathcal {R}}(b,x)$ and $(b,x) \mathrel {\mathcal {R}}(a,z)$ both hold true.

This is a complete relation.

We have, abusing notation,

• $(a, b) \mathrel {\succ _{1}^{*}} [(a, a), (b, b)] \mathrel {\succ _{1}^{*}} (b, a)$ and

• $(x, z) \mathrel {\succ _{2}^{*}} [(x, x), (y, y), (z, z), (x, y), (y, z)] \mathrel {\succ _{2}^{*}} [(y, x), (z, x), (z, y)]$,

• $a \mathrel {\succ _{1}^{\pm }} b$ and $x \mathrel {\succ _{2}^{\pm }} y \mathrel {\succ _{2}^{\pm }} z$.

Using Lemma 22, it is easy to check that $\mathrel {\mathcal {R}}$ satisfies $RC 1$, $RC2$, $AC 1$, $AC 2$, $AC 3$.

It is clear that $UC_{1}$, $LC_{1}$ and $LC_{2}$ hold. $UC_{2}$ is violated since we have $(x, y) \mathrel {\succ _{2}^{*}} (y, x)$ and $Not [(x, y) \mathrel {\succsim _{2}^{*}} (x, z) ]$.

Parts 1 and 2 of Lemma 11 in Bouyssou and Pirlot (2007), show that conditions $M1_{1}$ and $M2$ hold. By Part 3 of Lemma 11 in Bouyssou and Pirlot (2007), $M1_{2}$ cannot hold. Using Lemma 34 shows that $Maj 1_{1}$ and $Maj 2$ hold while $Maj 1_{2}$ does not. Using Lemma 42 shows that $MM 1_{1}$ and $MM 2$ hold while $MM 1_{2}$ does not. Since $\mathrel {\mathcal {R}}$ satisfies $M2$ (resp. $Maj 2$, $MM 2$), this implies that $M3$ (resp. $Maj 3$, $MM 3$) also holds. Since $M1_{1}$ holds, $DMM 3_{1}$ holds too. We show that $DMM 3_{2}$ also holds. Assume the contrary. Taking $RC 1_{2}$ into account, this implies that there are $x_{2}, y_{2}, z_{2}, w_{2} \in X_{1}$ such that $(z_{2},w_{2}) \mathrel {\succ _{2}^{*}} (x_{2},y_{2}) \mathrel {\succ _{2}^{*}} (y_{2},x_{2})$. Hence $(z_{2}, w_{2})$ can only be $(x,z)$. The fourth conclusion of $DMM 3_{2}$ is always true since $(u,x) \mathrel {\mathcal {R}}(v,z)$ for all $u,v \in X_{1} = \{a,b\}$.

Example 79

($Not [ RC 1_{i}, AC 2_{i}, LC _{i}, Maj 2_{i}, Maj 3_{1} ]$) This is Example 12 in Bouyssou and Pirlot (2007). Also used in Example 24 in the same paper.

Let $N= \lbrace 1,2,3 \rbrace$ and $X= \lbrace x, y, z, w \rbrace \times \lbrace a, b \rbrace \times \lbrace p, q \rbrace$. Let $\mathrel {\mathcal {R}}$ on $X$ be identical to $X^{2}$ except that, for all $\alpha _{1}, \beta _{1} \in X_{1}$, all $\alpha _{2}, \beta _{2} \in X_{2}$ and all $\alpha _{3}, \beta _{3} \in X_{3}$ the following pairs are missing:

$$\begin{aligned}&Not [(x, a, \alpha _{3}) \mathrel {\mathcal {R}}(y, b, \beta _{3}) ], \quad Not [(z, \alpha _{2}, p) \mathrel {\mathcal {R}}(w, \beta _{2}, q) ],\\&Not [(x, \alpha _{2}, p) \mathrel {\mathcal {R}}(w, \beta _{2}, q) ], \quad Not [(\alpha _{1}, a, p) \mathrel {\mathcal {R}}(\beta _{1}, b, q) ], \end{aligned}$$

There is a total of 25 such pairs that are marked by a cross in Table 1.

Table 1 Relation $\mathrel {\mathcal {R}}$ in Example 79: the missing pairs are marked by a cross

It is not difficult to check that $\mathrel {\mathcal {R}}$ is complete.

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

$$\begin{aligned}&\displaystyle [(b, a),(a,a),(b,b)] \mathrel {\succ _{2}^{*}} (a,b),\\&\displaystyle [(q, p),(p,p),(q,q)] \mathrel {\succ _{3}^{*}} (p,q),\\&\displaystyle b \mathrel {\succ _{2}^{\pm }} a, q \mathrel {\succ _{3}^{\pm }} p, \end{aligned}$$

which shows,

• using Parts 1 and 2 of Lemma 22, that $RC1_{2}$, $RC1_{3}$, $RC2_{2}$ and $RC2_{3}$ hold,

• using Lemma 47, that $AC 1_{2}$, $AC 1_{3}$, $AC 2_{2}$, $AC 2_{3}$, $AC 3_{2}$ and $AC 3_{3}$ hold.

Using Parts 1 and 2 of Lemma 8 in Bouyssou and Pirlot (2007), it is easy to check that $LC_{2}$, $LC_{3}$, $UC_{2}$ and $UC_{3}$ hold. Hence, using Parts 3 and 4 of Lemma 11 in Bouyssou and Pirlot (2007), we know that $M1_{2}$, $M1_{3}$, $M2_{2}$ and $M2_{3}$ hold. Using Lemma 34, we have also $Maj 1_{2}$, $Maj 1_{3}$, $Maj 2_{2}$ and $Maj 2_{3}$.

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

$$\begin{aligned}&\displaystyle (c_{1}, d_{1}) \mathrel {\succ _{1}^{*}} (x,y) \text { and}\\&\displaystyle (c_{1}, d_{1}) \mathrel {\succ _{1}^{*}} [(x, w),(z,w)], \end{aligned}$$

for all $(c_{1}, d_{1}) \in \Gamma = \{ (x, x), (x, z),$ $(y, x), (y, y), (y, z), (y, w),$ $(z, x),$ $(z, y),$ $(z, z),$ $(w, x),$ $(w, y),$ $(w, z),$ $(w, w) \}$. The pairs $(x, w)$ and $(z,w)$ are linked by $\mathrel {\sim _{1}^{*}}$. The pairs $(x,y)$ and $(x, w)$ are not comparable in terms of $\mathrel {\succsim _{1}^{*}}$ since $(x,a,p) \mathrel {\mathcal {R}}(y, a, q)$ and $Not [(x,a,p) \mathrel {\mathcal {R}}(w, a, q) ]$, while $(x,a,p) \mathrel {\mathcal {R}}(w, b, p)$ and $Not [(x,a,p) \mathrel {\mathcal {R}}(y, b, p) ]$. Similarly, the pairs $(x,y)$ and $(z, w)$ are not comparable in terms of $\mathrel {\succsim _{1}^{*}}$. This shows, using Part 1 of Lemma 22, that $RC1_{1}$ is violated.

Using Part 2 of Lemma 22, it is easy to see that $RC2_{1}$ holds. Using Part 1 of Lemma 8 in Bouyssou and Pirlot (2007), shows that $UC_{1}$ holds. Hence, using Part 3 of Lemma 11 in Bouyssou and Pirlot (2007), we know that $M1_{1}$ holds.

In view of Part 6 of Lemma 16 in Bouyssou and Pirlot (2005b), $LC _{1}$ does not hold (since this lemma tells us that $RC 2_{1}, UC _{1}$ and $LC _{1}$ entail $RC 1_{1}$. We now check that $M2_{1}$ holds. The two premises of $M2_{1}$ are that $(a_{1},a_{-1}) \mathrel {\mathcal {R}}(b_{1},b_{-1})$ and $(b_{1},c_{-1}) \mathrel {\mathcal {R}}(a_{1},d_{-1})$. The three possible conclusions of $M2_{1}$ are that $(b_{1},a_{-1}) \mathrel {\mathcal {R}}(a_{1},b_{-1})$ or $(c_{1},a_{-1}) \mathrel {\mathcal {R}}(d_{1},b_{-1})$ or $(c_{1},c_{-1}) \mathrel {\mathcal {R}}(d_{1},d_{-1})$.

Suppose first that $(b_{1}, a_{1}) \in \Gamma$. In this case, we have $(b_{1}, a_{1}) \mathrel {\succsim _{1}^{*}} (a_{1}, b_{1})$, so that $(a_{1},a_{-1}) \mathrel {\mathcal {R}}(b_{1},b_{-1})$ implies $(b_{1},a_{-1}) \mathrel {\mathcal {R}}(a_{1},b_{-1})$. Hence, the first conclusion of $M2_{1}$ holds.

Suppose now that $(b_{1}, a_{1}) = (x, y)$.

If $(c_{1}, d_{1})$ is distinct from $(x, w)$ and $(z,w)$, we have $(c_{1}, d_{1}) \mathrel {\succsim _{1}^{*}} (x, y)$, so that $(b_{1},c_{-1}) \mathrel {\mathcal {R}}(a_{1},d_{-1})$ implies $(c_{1},c_{-1}) \mathrel {\mathcal {R}}(d_{1},d_{-1})$ and the third conclusion of $M2_{1}$ holds.

If $(c_{1}, d_{1})=(x, w)$, it is easy to check that there are no $a_{-1}, b_{-1} \in X_{-i}$ such that $(y,a_{-1}) \mathrel {\mathcal {R}}(x, b_{-1})$, $Not [(x,a_{-1}) \mathrel {\mathcal {R}}(y,b_{-1}) ]$ and $Not [(x,a_{-1}) \mathrel {\mathcal {R}}(w,b_{-1}) ]$, so that no violation of $M2_{1}$ is possible in this case. Since $(x, w) \mathrel {\sim _{1}^{*}} (z, w)$, the same is true if $(c_{1}, d_{1})$ $=$ $(z, w)$.

This shows that $M2_{1}$ cannot be violated if $(b_{1}, a_{1}) = (x, y)$. A similar reasoning shows that $M2_{1}$ cannot be violated if $(b_{1}, a_{1}) = (x, w)$ or if $(b_{1}, a_{1}) = (z, w)$. Hence, $M2_{1}$ holds and so does $M3_{1}$.

Using Remark 33, we know that $\mathrel {\mathcal {R}}$ satisfies $Maj 1_{1}$ since $UC _{i}$ entails $Maj 1_{i}$.

Since $\mathrel {\mathcal {R}}$ satisfies $RC 2_{1}$, $M1_{1}$ but not $RC 1_{1}$, it cannot satisfy $Maj 2_{1}$, as a consequence of Lemma 35. Since $\mathrel {\mathcal {R}}$ satisfies $M1$ and $M2$, it also satisfies $MM 1$, $DMM 3$, $MM 2$, $M3$ and $MM 3$.

$Maj 3_{2}$ (resp. $Maj 3_{3}$) holds because $Maj 2_{2}$ (resp. $Maj 2_{3}$) holds but $Maj 3_{1}$ is violated as shown by the following configuration (which also confirms that $Maj 2_{1}$ is violated): $(y,a,p) \mathrel {\mathcal {R}}(x,b,p)$, $(w,a,p) \mathrel {\mathcal {R}}(z,a,p)$, $(w,a,p) \mathrel {\mathcal {R}}(z,a,q)$, $(z,a,p) \mathrel {\mathcal {R}}(w,a,p)$, $Not [(x,a,p) \mathrel {\mathcal {R}}(y,b,p) ]$, $Not [(z,a,p) \mathrel {\mathcal {R}}(w,a,q) ]$.

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

$$\begin{aligned} \{y, w\} \mathrel {\succ _{1}^{+}} z \mathrel {\succ _{1}^{+}} x. \end{aligned}$$

Hence $AC 1_{1}$ holds. Since $(x, w)$ and $(x, y)$ are not comparable w.r.t. $\mathrel {\succsim _{1}^{*}}$, $y$ and $w$ are not comparable w.r.t. $\mathrel {\succ _{1}^{-}}$, hence $AC 2_{1}$ is violated. It is easy to check, using Lemma 15 in Bouyssou and Pirlot (2007), that $AC3_{1}$ is satisfied.

Remark The co-dual of Example 79 is an asymmetric relation that satisfies all axioms but $RC 1, AC 1, UC$ and $M1$.

Example 80

($Not [ RC 1_{i}, AC 1_{i}, UC _{i}, M1_{i}, DMaj 3_{i} ]$) The co-dual of the relation $\mathrel {\mathcal {R}}$ described in Table 2 is a complete relation satisfying all properties except for $RC 1$, $AC 2$, $M1$ and $DMaj 3$. Note that this relation verifies $DM 3$ and $DMM 3$.

Table 2 Relation $\mathrel {\mathcal {R}}$ in Example 80

Let $X= \{x,y,z\}\times \{a,b\}\times \{p,q\}$ and $\mathrel {\mathcal {R}}$ consist of the set of pairs listed in Table 2. We have to show that $\mathrel {\mathcal {R}}$ satisfies all properties but $RC 1$, $AC 1$, $LC$, $Maj 2$, $Maj 3$. It is easy to check that $\mathrel {\mathcal {R}}$ is asymmetric. As for the comparison of preference differences on each attribute, we have for all $(\alpha , \beta ) \in \Gamma = \{ (x,x), (y,y), (z,z), (x,y), (x,z), (y,z), (z,y)\}$,

• $[(\alpha , \beta )] \mathrel {\succ _{1}^{*}} (y,x)$ and $[(\alpha , \beta )] \mathrel {\succ _{1}^{*}} (z,x)$, while $(y,x)$ and $(z,x)$ are incomparable in terms of $\mathrel {\succsim _{1}^{*}}$,

• $(a,b) \mathrel {\succ _{2}^{*}} [(a,a), (b,b)] \mathrel {\succ _{2}^{*}} (b,a)$,

• $(p,q) \mathrel {\succ _{3}^{*}} [(p,p), (q,q)] \mathrel {\succ _{3}^{*}} (q,p)$.

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

• $a \mathrel {\succ _{2}^{\pm }} b$,

• $p \mathrel {\succ _{3}^{\pm }} q$.

On attribute $1$, we have:

• $x \mathrel {\succ _{1}^{+}} y$, $x \mathrel {\succ _{i}^{+}}z$,

• $y$ and $z$ are not comparable w.r.t. $\mathrel {\succsim _{i}^{+}}$ since, on the one hand, $zap \mathrel {\mathcal {R}}xaq$ and $Not [yap \mathrel {\mathcal {R}}xaq ]$, and on the other hand, $yap \mathrel {\mathcal {R}}xbp$ and $Not [zap \mathrel {\mathcal {R}}xbp ]$,

• $x \mathrel {\succ _{1}^{-}} y \mathrel {\succ _{i}^{-}}z$.

For $j \in \{2,3\}$, $RC 1_{j}$, $RC 2_{j}$, $AC 1_{j}$, $AC 2_{j}$, $AC 3_{j}$, $UC _{j}$ and $LC _{j}$ are clearly satisfied, implying $M1_{j}$ and $M2_{j}$ (see Remark 26) as well as $Maj 1_{j}$ and $Maj 2_{j}$ (see Remark 33), $MM 1_{j}$ and $MM 2_{j}$. On attribute $1$ it is easy to check that $RC 2_{1}$, $AC 2_{1}$ and $AC 3_{1}$ are verified while $RC 1_{1}$ and $AC 1_{1}$ are violated. Using Lemma 8(1) in Bouyssou and Pirlot (2007), we observe that $UC _{1}$ is satisfied, implying $M1_{1}$, $Maj 1_{1}$ and $MM 1_{1}$. $LC _{1}$ does not hold but $M2_{1}$ does as we shall see.

Using the notation in condition (20), for establishing $M2_{1}$ we only have to consider the cases in which $(y_{1},x) = (y,x)$ or $(y_{1},x) = (z,x)$ (otherwise $(y_{1},x) \mathrel {\succsim _{1}^{*}} (x, y_{1})$ and consequently the first conclusion of (20) is satisfied). Assume that $(y_{1},x) = (y,x)$ and that the first conclusion is not satisfied. This means that either $a_{-1} = ap$ and $b_{-1} = aq$ or $a_{-1} = bp$ and $b_{-1} = bq$. We now distinguish two cases regarding $(z_{i},w_{i})$:

• 1. if $(z_{i}, w_{i}) \ne (z,x)$, the third conclusion is always satisfied because of the second premise and the fact that $(z_{i}, w_{i}) \mathrel {\succsim _{1}^{*}} (y,x)$,

• 2. if $(z_{i}, w_{i}) = (z,x)$ and $a_{-1} = ap$ and $b_{-1} = aq$ or $a_{-1} = bp$ and $b_{-1} = bq$, the second conclusion is satisfied because we have $zap \mathrel {\mathcal {R}}xaq$ and $zbp \mathrel {\mathcal {R}}xbq$.

The case in which $(y_{1}, x) = (z,x)$ is dealt with similarly. Consequently, $\mathrel {\mathcal {R}}$ satisfies $M2_{1}$, $MM 2_{1}$, $M3_{1}$ and $MM 3_{1}$.

For establishing that $Maj 2_{1}$ does not hold, we consider the case in which $(y_{1}, x) = (y,x)$ and use the notation of (22) in Definition 30. In the previous analysis we only need to reconsider the case in which the second conclusion of $M2_{i}$ was used, i.e., when $(z_{i}, w_{i}) = (z,x)$ and $a_{-1} = ap$ and $b_{-1} = aq$ or $a_{-1} = bp$ and $b_{-1} = bq$. We have $xap \mathrel {\mathcal {R}}yaq$, $Not [yap \mathrel {\mathcal {R}}xaq ]$, $xap \mathrel {\mathcal {R}}zaq$, $yap \mathrel {\mathcal {R}}xbp$ and $Not [zap \mathrel {\mathcal {R}}xbp ]$, which means that $Maj 2_{1}$ does not hold. Since $(z,x)$ is no veto (as we have, e.g., $zap \mathrel {\mathcal {R}}xaq$), the latter also shows that $\mathrel {\mathcal {R}}$ does not satisfy $Maj 3_{1}$.

Example 81

($Not [ AC 1_{i}, AC 2_{i} ]$) This is Example 36 in Bouyssou and Pirlot (2005b). Also used in Example 21 in Bouyssou and Pirlot (2007).

Let $X=\lbrace a, b, c, d \rbrace \times \lbrace x, y \rbrace$. We build $\mathrel {\mathcal {R}}$ as the CR in which:

• $a \mathrel {I_{1}} b$, $a \mathrel {P_{1}} c$, $a \mathrel {I_{1}} d$, $b \mathrel {I_{1}} c$, $b \mathrel {P_{1}} d$, $c \mathrel {I_{1}} d$,

• $x \mathrel {P_{2}} y$,

• $\lbrace 1, 2 \rbrace \mathrel {\rhd }\varnothing$, $\lbrace 1,2 \rbrace \mathrel {\triangleq }\lbrace 2 \rbrace$, $\lbrace 1,2 \rbrace \mathrel {\triangleq }\lbrace 1 \rbrace$, $\lbrace 2 \rbrace \mathrel {\triangleq }\lbrace 1 \rbrace$.

Therefore, $\mathrel {\mathcal {R}}$ links any two elements of $X$ except that we have: $(a, x) \mathrel {\mathcal {R}}(c, y)$ but $Not [(c, y) \mathrel {\mathcal {R}}(a, x) ]$ and $(b, x) \mathrel {\mathcal {R}}(d, y)$ but $Not [(d, y) \mathrel {\mathcal {R}}(b, x) ]$. Hence $\mathrel {\mathcal {R}}$ is a complete relation. Since it is a CR, it satisfies $RC 1$, $RC 2$, $UC$, $LC$, $M1$, $M2$, $Maj 1$, $Maj 2$, $MM 1$, $MM 2$, $M3$, $Maj 3$, $MM 3$ and $DMM 3$.

It is easy to see that $AC3$ and $AC1_{2}$ as well as $AC 2_{2}$ hold. $AC1_{1}$ is violated since $(d, y) \mathrel {\mathcal {R}}(a, x)$ and $(c, y) \mathrel {\mathcal {R}}(b, x)$ but neither $(c, y) \mathrel {\mathcal {R}}(a, x)$ nor $(d, y) \mathrel {\mathcal {R}}(b, x)$. $AC 2_{1}$ is also violated (Part 1 of Lemma 27 in Bouyssou and Pirlot 2005b).

Example 82

($Not [AC3_{i} ]$) This is Example 35 in Bouyssou and Pirlot (2005b). Also used as Example 20 in Bouyssou and Pirlot (2007).

Let $X=\lbrace a, b, c, d \rbrace \times \lbrace x, y \rbrace$. We build the CR in which:

• $a \mathrel {P_{1}} b$, $a \mathrel {I_{1}} c$, $a \mathrel {P_{1}} d$, $b \mathrel {I_{1}} c$, $b \mathrel {P_{1}} d$, $c \mathrel {I_{1}} d$,

• $x \mathrel {P_{2}} y$,

• $\lbrace 1, 2 \rbrace \mathrel {\rhd }\varnothing$, $\lbrace 1,2 \rbrace \mathrel {\triangleq }\lbrace 2 \rbrace$, $\lbrace 1,2 \rbrace \mathrel {\triangleq }\lbrace 1 \rbrace$, $\lbrace 2 \rbrace \mathrel {\triangleq }\lbrace 1 \rbrace$.

Therefore, $\mathrel {\mathcal {R}}$ links any two elements of $X$ except that we have: $(a, x) \mathrel {\mathcal {R}}(b, y)$ but $Not [(b, y) \mathrel {\mathcal {R}}(a, x) ]$, $(b, x) \mathrel {\mathcal {R}}(d, y)$ but $Not [(d, y) \mathrel {\mathcal {R}}(b, x) ]$ and $(a, x) \mathrel {\mathcal {R}}(d, y)$ but $Not [(d, y) \mathrel {\mathcal {R}}(a, x) ]$. Hence $\mathrel {\mathcal {R}}$ is a complete relation. Since it is a $CR$, it satisfies $RC 1$, $RC 2$, $UC$, $LC$, $M1$, $M2$, $Maj 1$, $Maj 2$, $MM 1$, $MM 2$, $M3$, $Maj 3$, $MM 3$ and $DMM 3$.

It is easy to see that $AC1$ holds and, hence, $AC2$ (by Part 1 of Lemma 27 in Bouyssou and Pirlot 2005b). One verifies that $AC3_{2}$ holds. $AC3_{1}$ is violated since $(c, y) \mathrel {\mathcal {R}}(a, x)$, $(d, y) \mathrel {\mathcal {R}}(c, x)$ but neither $(b, y) \mathrel {\mathcal {R}}(a, x)$ nor $(d, y) \mathrel {\mathcal {R}}(b, x)$.

Remark. The co-dual of this relation is an asymmetric relation that satisfies all axioms of a CR-AT except $AC 3_{1}$. In particular, it satisfies $M3$ and $Maj 3$ since it satisfies $M2$ and $Maj 2$.

Example 83

($Not [LC_{i}, M2_{i}, Maj 2_{i}, MM 2_{i}, M3_{i}, Maj 3_{i}, MM 3_{i} ]$) This is Example 38 in Bouyssou and Pirlot (2009b). It is used in Remark 16 in Bouyssou and Pirlot (2009a) (but erroneously referred to as Example 39 in Bouyssou and Pirlot 2009b).

Let $X= X_{1} \times X_{2} \times X_{3}$ with $X_{1} = \{x, y, z\}$, $X_{2} = \{a, b\}$ and $X_{3} = \{p, q\}$. Let us consider the relation $\mathrel {\mathcal {R}}$ such that:

$$\begin{aligned} x \mathrel {\mathcal {R}}y \iff \sum _{i=1}^{3} p_{i}(x_{i}, y_{i}) \ge 0, \end{aligned}$$

the functions $p_{i}$ being such that:

$$\begin{aligned} p_{1}(x, y)&= p_{1}(x, z) = p_{1}(y, z) = p_{1}(x, x) = p_{1}(y, y) = p_{1}(z, z) = 4, \\ p_{1}(y, x)&= p_{1}(z, y) = -1, p_{1}(z, x) = -4,\\ p_{2}(a, b)&= 2, p_{2}(a, a) = p_{2}(b, b) = 0, p_{2}(b, a) = -2,\\ p_{3}(a, b)&= 2, p_{3}(p, p) = p_{3}(q, q) = 0, p_{3}(q, p) = -2. \end{aligned}$$

This is a complete relation. Indeed if $\sum _{i=1}^{3} p_{i}(x_{i}, y_{i}) < 0$, then $p_{1}(x,y_{1}) <4$. This implies that $p_{1}(y_{1},x)=4$, hence $\sum _{i=1}^{3} p_{i}(y_{i}, x_{i}) \ge 0$.

It is easily checked that we have (with $(\alpha , \alpha )$ standing for $(x,x)$, $(y,y)$ and $(z,z)$):

$$\begin{aligned}&\displaystyle [(x,y)\mathrel {\sim _{1}^{*}} (x,z)\mathrel {\sim _{1}^{*}} (y,z)\mathrel {\sim _{1}^{*}} (\alpha ,\alpha )] \mathrel {\succ _{1}^{*}} [(y, x) \mathrel {\sim _{1}^{*}} (z, y)] \mathrel {\succ _{1}^{*}} (z, x),\\&\displaystyle x \mathrel {\succ _{1}^{\pm }} y \mathrel {\succ _{1}^{\pm }} z,\\&\displaystyle (a, b) \mathrel {\succ _{2}^{*}} [(a, a) \mathrel {\sim _{2}^{*}} (b, b)] \mathrel {\succ _{2}^{*}} (b, a),\\&\displaystyle a \mathrel {\succ _{2}^{\pm }} b,\\&\displaystyle (p, q) \mathrel {\succ _{3}^{*}} [(p, p) \mathrel {\sim _{2}^{*}} (q, q)] \mathrel {\succ _{2}^{*}} (q, p),\\&\displaystyle p \mathrel {\succ _{3}^{\pm }} q. \end{aligned}$$

This shows that $RC 1$, $RC 2$, $AC 1$, $AC 2$ and $AC 3$ are satisfied. Using Parts 1 of Lemma 8 and Lemma 11 in Bouyssou and Pirlot (2007) shows that $UC$ and $M1$ hold. Similarly, using Parts 2 of Lemma 8 and Lemma 11 in Bouyssou and Pirlot (2007) shows that $\mathrel {\mathcal {R}}$ satisfies $UC_{2}$, $UC_{3}$, $M2_{2}$ and $M2_{3}$, which implies that $M3_{2}$ and $M3_{3}$ hold. Condition $M3_{1}$ is violated since $(x, b, q) \mathrel {\mathcal {R}}(y, a, p)$, $(y, a, q) \mathrel {\mathcal {R}}(x, b, q)$ and $(z, a, p) \mathrel {\mathcal {R}}(x, b, q)$ while $Not [(y, b, q) \mathrel {\mathcal {R}}(x, a, p) ]$, $Not [(z, b, q) \mathrel {\mathcal {R}}(x, a, p) ]$ and $Not [(z, a, q) \mathrel {\mathcal {R}}(x, b, q) ]$.

Hence $M2_{1}$ is violated too. Lemma 11, Part 2, in Bouyssou and Pirlot (2007) implies that $LC_{1}$ is also violated. Using Lemmas 34, 42 and 56, we obtain that $\mathrel {\mathcal {R}}$ satisfies $Maj 1$, $MM 1$, $Maj 2_{2}$, $Maj 2_{3}$, $MM 2_{2}$, $MM 2_{3}$, $Maj 3_{2}$, $Maj 3_{3}$, $MM 3_{2}$, $MM 3_{3}$ but neither $Maj 2_{1}$ nor $Maj 3_{1}$. In view of Lemmas 56, $MM 3_{1}$ is also violated as well as $MM 2_{1}$. Since $\mathrel {\mathcal {R}}$ satisfies $M1$, it fulfills $DMM 3$.

Example 84

(Asymmetric, $Not [ LC _{i}, M2_{i}, M3_{i}, Maj 2_{i}, Maj 3_{i}, MM 2_{i}, MM 3_{i} ]$) This is Example 5 in Bouyssou and Pirlot (2006).

Let $X= \lbrace x, y, z \rbrace \times \lbrace a, b \rbrace \times \lbrace p, q \rbrace$ and $\mathrel {\mathcal {R}}$ on $X$ be as described in Table 3:

Table 3 Relation $\mathrel {\mathcal {R}}$ in Example 84

It is easy to check that $\mathrel {\mathcal {R}}$ is asymmetric. It is not difficult to see that we have, abusing notation,

• $[(x, y), (x, z), (y, z)] \mathrel {\succ _{1}^{*}} [(x, x), (y, y), (z, z), (y, x), (z, y)] \mathrel {\succ _{1}^{*}} (z, x)$,

• $(a, b) \mathrel {\succ _{2}^{*}} [(a, a), (b, b)] \mathrel {\succ _{2}^{*}} (b, a)$, and

• $(p, q) \mathrel {\succ _{3}^{*}} [(p, p), (q, q)] \mathrel {\succ _{3}^{*}} (q, p)$.

This shows that $RC 1$, $RC 2$ and $Maj 1$ hold. It is easy to see that $Maj 2_{2}$ and $Maj 2_{3}$ hold so that $Maj 3_{2}$ and $Maj 3_{3}$ are satisfied. Condition $Maj 3_{1}$ is violated since $(x,a,p)\mathrel {\mathcal {R}}(y,a,p)$, $(x,a,p)\mathrel {\mathcal {R}}(z,a,p)$, $(y,a,p)\mathrel {\mathcal {R}}(x,b,p)$ and $(z,a,p)\mathrel {\mathcal {R}}(x,b,q)$ but neither $(y,a,p)\mathrel {\mathcal {R}}(x,a,p)$ nor $(z,a,p)\mathrel {\mathcal {R}}(x,b,p)$.

Since $RC 1$ and $RC 2$ hold, Lemma 34 implies that $\mathrel {\mathcal {R}}$ satisfies $M1$, $M2_{2}$, $M2_{3}$ but not $M2_{1}$. $M3_{2}$ and $M3_{3}$ hold while $M3_{1}$ is violated (Lemma 56). By Lemma 11 in Bouyssou and Pirlot (2007), $\mathrel {\mathcal {R}}$ satisfies $UC$, $LC _{2}$, $LC _{3}$ but not $LC _{1}$. By Lemmas 42 and 56, we know that $MM 2_{1}$ and $MM 3_{1}$ are violated. $MM 2_{j}$ and $MM 3_{j}$ are satisfied for $j=2,3$. $\mathrel {\mathcal {R}}$ satisfies $MM 1$ so that it also satisfies $DMM 3$.

From relations $\mathrel {\succsim _{i}^{*}}$ described above, we infer the following:

$$\begin{aligned}&\displaystyle x \mathrel {\succ _{1}^{\pm }} y \mathrel {\succ _{1}^{\pm }} z,\\&\displaystyle a \mathrel {\succ _{2}^{\pm }} b,\\&\displaystyle p \mathrel {\succ _{3}^{\pm }} q, \end{aligned}$$

which implies that $\mathrel {\mathcal {R}}$ satisfies $AC 1$, $AC 2$ and $AC 3$.

Example 85

( $Not [ AC 1_{i}, M2_{i}, Maj 2_{i}, MM 2_{i}, LC _{i} ]$) This is Example 36 in Bouyssou and Pirlot (2009b).

Let $X= X_{1} \times X_{2}$ with $X_{1} = \{x, y, z, w \}$ and $X_{2} = \{a, b \}$. We build a CDR on $X$ with:

• $z \mathrel {P_{1}} x$, $z \mathrel {P_{1}} y$, $z \mathrel {P_{1}} w$, $x \mathrel {P_{1}} w$, $x \mathrel {I_{1}} y$, $y \mathrel {I_{1}} w$,

• the relation $\mathrel {V_{1}}$ is empty except that $z \mathrel {V_{1}} y$,

• $b \mathrel {P_{2}} a$,

• the relation $\mathrel {V_{2}}$ is empty,

• $\{1, 2\} \mathrel {\rhd }\varnothing$, $\{1, 2\} \mathrel {\triangleq }\{2\}$, $\{1, 2\} \mathrel {\triangleq }\{1\}$ and $\{1\} \mathrel {\triangleq }\{2\}$.

By construction, $\mathrel {\mathcal {R}}$ is a CDR. Hence, it satisfies $RC 1$, $RC 2$, $M1$, $Maj 1$, $MM 1$, $M3$, $Maj 3$ and $MM 3$ (Theorem 58 and Lemmas 42 and 56). It satisfies $M2_{2}$, $Maj 2_{2}$, $MM 2_{2}$, but not $M2_{1}$ (due to the veto on $X_{1}$), not $Maj 2_{1}$ (by Lemma 34) and not $MM 2_{1}$ (by Lemma 42). Since $\mathrel {\mathcal {R}}$ satisfies $M1$ it also fulfills $DMM 3$. Using Lemma 11 in Bouyssou and Pirlot (2007), we get that $UC$ and $LC _{2}$ are satisfied but $LC _{1}$ is violated.

The relation $\mathrel {\mathcal {R}}$ contains all pairs in $X\times X$ except the following ones:

• $Not [(x, b) \mathrel {\mathcal {R}}(z, a) ]$, $Not [(y, b) \mathrel {\mathcal {R}}(z, a) ]$, $Not [(w, b) \mathrel {\mathcal {R}}(z, a) ]$, $Not [(w, b) \mathrel {\mathcal {R}}(x, a) ]$, due to the fact that $Not [\varnothing \mathrel {\unrhd }\{1, 2\} ]$, and

• $Not [(y, a) \mathrel {\mathcal {R}}(z, a) ]$, $Not [(y, b) \mathrel {\mathcal {R}}(z, b) ]$, $Not [(y, b) \mathrel {\mathcal {R}}(z, a) ]$, $Not [(y, a) \mathrel {\mathcal {R}}(z, b) ]$, due to the fact that $z \mathrel {V_{1}} y$.

One pair is common to these two series of four pairs, so that $\mathrel {\mathcal {R}}$ is equal to $X\times X$ minus the seven distinct pairs in the lists above. It is a complete relation.

On $X_{2}$, it is easy to check that we have $b \mathrel {\succ _{2}^{\pm }} a$, so that $AC 1_{2}$, $AC 2_{2}$ and $AC 3_{2}$ hold.

On $X_{1}$, it is easy to check that $\mathrel {\succsim _{1}^{-}}$ is complete. We indeed have that:

$$\begin{aligned} z \mathrel {\succ _{1}^{-}} x \mathrel {\succ _{1}^{-}} [y \mathrel {\sim _{1}^{-}} w]. \end{aligned}$$

The relation $\mathrel {\succsim _{1}^{+}}$ is not complete. We have $z \mathrel {\succ _{1}^{+}} x$, $x \mathrel {\succ _{1}^{+}} y$ and $x \mathrel {\succ _{1}^{+}} w$ but neither $y\mathrel {\succsim _{1}^{+}} w$ nor $w \mathrel {\succsim _{1}^{+}} y$ since $(y, b) \mathrel {\mathcal {R}}(x, a)$ but $Not [(w, b) \mathrel {\mathcal {R}}(x, a) ]$ and $(w, a) \mathrel {\mathcal {R}}(z, a)$ but $Not [(y, a) \mathrel {\mathcal {R}}(z, a) ]$. This shows that $AC 1_{1}$ is violated. Condition $AC 3_{1}$ holds since $\mathrel {\succsim _{1}^{+}}$ and $\mathrel {\succsim _{1}^{-}}$ are not incompatible.

Example 86

( $Not [ AC 2_{i}, M2_{i}, Maj 2_{i}, MM 2_{i}, LC _{i} ]$)

This is Example 35 in Bouyssou and Pirlot (2009b). It is a slight variation on Example 85 obtained by reversing all relations $\mathrel {S_{i}}$ and $\mathrel {V_{i}}$.

Let $X= X_{1} \times X_{2}$ with $X_{1} = \{x, y, z, w \}$ and $X_{2} = \{a, b \}$. We build a CDR on $X$ with:

• $w \mathrel {P_{1}} z$, $x \mathrel {P_{1}} z$, $y \mathrel {P_{1}} z$, $w \mathrel {P_{1}} x$, $y \mathrel {I_{1}} w$, $y \mathrel {I_{1}} x$ (and all $\mathrel {I_{1}}$ loops),

• $\mathrel {V_{1}}$ is empty except that $y \mathrel {V_{1}} z$,

• $a \mathrel {P_{2}} b$ (and all $\mathrel {I_{2}}$ loops) and the relation $\mathrel {V_{2}}$ is empty,

• $\{1, 2\} \mathrel {\rhd }\varnothing$, $\{1, 2\} \mathrel {\triangleq }\{2\}$, $\{1, 2\} \mathrel {\triangleq }\{1\}$ and $\{1\} \mathrel {\triangleq }\{2\}$.

Observe that $\mathrel {S_{1}}$ is a semiorder (the weak order it induces ranks the elements of $X_{1}$ in the following order: $w, y, x, z$). The relation $\mathrel {V_{1}}$ is a strict semiorder that is included in $\mathrel {P_{1}}$. But $(\mathrel {S_{1}}, \mathrel {U_{1}})$ is not an homogeneous chain of semiorders on $X_{1}$ since the weak order induced by $\mathrel {U_{1}}$ ranks $y$ before $w$, while the weak order induced by $\mathrel {S_{1}}$ does the opposite.

By construction, $\mathrel {\mathcal {R}}$ is a CDR. Hence, it satisfies $RC 1$, $RC 2$, $M1$, $Maj 1$, $MM 1$, $M3$, $Maj 3$ and $MM 3$ (Theorem58 and Lemmas 42 and 56). It satisfies $M2_{2}$, $Maj 2_{2}$, $MM 2_{2}$, but not $M2_{1}$ (due to the veto on $X_{1}$), not $Maj 2_{1}$ (by Lemma 34) and not $MM 2_{1}$ (by Lemma 42). Since $\mathrel {\mathcal {R}}$ satisfies $M1$ it also fulfills $DMM 3$. Using Lemma 11 in Bouyssou and Pirlot (2007), we get that $UC$ and $LC _{2}$ are satisfied but $LC _{1}$ is violated.

The relation $\mathrel {\mathcal {R}}$ contains all pairs in $X\times X$ except the following ones:

• $Not [(z, b) \mathrel {\mathcal {R}}(w, a) ]$, $Not [(z, b) \mathrel {\mathcal {R}}(x, a) ]$, $Not [(z, b) \mathrel {\mathcal {R}}(y, a) ]$, $Not [(x, b) \mathrel {\mathcal {R}}(w, a) ]$, due to the fact that $Not [\varnothing \mathrel {\unrhd }\{1, 2\} ]$, and

• $Not [(z, a) \mathrel {\mathcal {R}}(y, a) ]$, $Not [(z, a) \mathrel {\mathcal {R}}(y, b) ]$, $Not [(z, b) \mathrel {\mathcal {R}}(y, a) ]$, $Not [(z, b) \mathrel {\mathcal {R}}(y, b) ]$, due to the fact that $y \mathrel {V_{1}} z$.

One pair is common to these two series of four pairs, so that $\mathrel {\mathcal {R}}$ is equal to $X\times X$ minus the seven distinct pairs in the lists above. It is clear that $\mathrel {\mathcal {R}}$ is complete.

On $X_{2}$, it is easy to check that we have $a \mathrel {\succ _{2}^{\pm }} b$, so that $AC 1_{2}$, $AC 2_{2}$ and $AC 3_{2}$ hold.

On $X_{1}$, it is easy to check that $\mathrel {\succsim _{1}^{+}}$ is complete. We indeed have that:

$$\begin{aligned}{}[y \mathrel {\sim _{1}^{+}} w] \mathrel {\succ _{1}^{+}} x \mathrel {\succ _{1}^{+}} z. \end{aligned}$$

The relation $\mathrel {\succsim _{1}^{-}}$ is not complete. We have $w \mathrel {\succ _{1}^{-}} x$, $y \mathrel {\succ _{1}^{-}} x$ and $x \mathrel {\succ _{1}^{-}} z$ but neither $y\mathrel {\succsim _{1}^{-}} w$ nor $w \mathrel {\succsim _{1}^{-}} y$ since $(z, a) \mathrel {\mathcal {R}}(w, a)$ but $Not [(z, a) \mathrel {\mathcal {R}}(y, a) ]$ and $(x, b) \mathrel {\mathcal {R}}(y, a)$ but $Not [(x, b) \mathrel {\mathcal {R}}(w, a) ]$. This shows that $AC 2_{1}$ is violated. Condition $AC 3_{1}$ holds since $\mathrel {\succsim _{1}^{+}}$ and $\mathrel {\succsim _{1}^{-}}$ are not incompatible.

Example 87

(Asymmetric, $Not [UC_{i}, M1_{i}, Maj 1_{i}, MM 1_{i} ]$) This is Example 3 in Bouyssou and Pirlot (2006).

Let $X=\lbrace a, b \rbrace \times \lbrace x, y, z \rbrace$ and $\mathrel {\mathcal {R}}$ on $X$ be identical to the strict linear order (abusing notation in an obvious way):

$$\begin{aligned} (a,x) \mathrel {\mathcal {R}}(b,x) \mathrel {\mathcal {R}}(a,y) \mathrel {\mathcal {R}}(b,y) \mathrel {\mathcal {R}}(a,z) \mathrel {\mathcal {R}}(b,z), \end{aligned}$$

except that we have also $(a,y) \mathrel {\mathcal {R}}(b,x)$.

It is easy to see that $\mathrel {\mathcal {R}}$ is asymmetric. We have, abusing notation:

• $(a, b) \mathrel {\succ _{1}^{*}} [(a, a), (b, b)] \mathrel {\succ _{1}^{*}} (b, a)$, and

• $[(x, z), (y, z)] \mathrel {\succ _{2}^{*}} (x, y) \mathrel {\succ _{2}^{*}} [(x, x), (y, y), (z, z)] \mathrel {\succ _{2}^{*}} [(y, x), (z, x), (z, y)]$.

Using Lemma 22, it is easy to check that $\mathrel {\mathcal {R}}$ satisfies $RC 1$ and $RC 2$.

It is clear that $UC_{1}$, $LC_{1}$ and $LC_{2}$ hold. This implies that $M2$, $Maj 2$, $MM 2$, $M3$, $Maj 3$, $MM 3$ hold as well as $M1_{1}$, $Maj 1_{1}$ and $MM 1_{1}$.

$Maj 1_{2}$ is violated since $(a,x)\mathrel {\mathcal {R}}(a,y)$, $(a,x)\mathrel {\mathcal {R}}(a,z)$, $(b,x)\mathrel {\mathcal {R}}(a,z)$ but neither $(a,y)\mathrel {\mathcal {R}}(a,x)$ nor $(b,x)\mathrel {\mathcal {R}}(a,y)$. As a consequence, $UC_{1}$ is also violated. Since $RC 1$ and $RC 2$ hold, Lemmas 34 and 42 imply that $M1_{2}$ and $MM 1_{2}$ are violated.

Since $M1_{1}$ holds, $DMM 3_{1}$ holds too. We show that $DMM 3_{2}$ also holds. Assume the contrary. Taking $RC 1_{2}$ into account, this implies that there are $a, b, z_{2}, w_{2} \in X_{2}$ such that $(z_{2},w_{2}) \mathrel {\succ _{2}^{*}} (a,b) \mathrel {\succ _{2}^{*}} (b,a)$. Hence $(z_{2}, w_{2})$ can only be $(x,z)$ or $(y,z)$. The fourth conclusion of $DMM 3_{2}$ is always true since $(u,x) \mathrel {\mathcal {R}}(v,z)$ and $(u,y) \mathrel {\mathcal {R}}(v,z)$ for all $u,v \in X_{1}=\{a,b\}$.

Using Lemma 47, we have:

• $a \mathrel {\succsim _{1}^{\pm }} b$ and

• $x \mathrel {\succsim _{2}^{\pm }} y \mathrel {\succsim _{3}^{\pm }} z$.

Hence $AC 1$, $AC 2$ and $AC 3$ hold.

Example 88

(Asymmetric, $Not [ AC 1_{i}, M2_{i}, Maj 2_{i}, MM 2_{i}, LC _{i} ]$) This example is an asymmetric variant of Example 85.

Let $X= X_{1} \times X_{2}$ with $X_{1} = \{x, y, z, w \}$ and $X_{2} = \{a, b \}$. We build a CDR on $X$ with:

• $z \mathrel {P^{\circ }_{1}} x$, $z \mathrel {P^{\circ }_{1}} y$, $z \mathrel {P^{\circ }_{1}} w$, $x \mathrel {P^{\circ }_{1}} w$, $y \mathrel {P^{\circ }_{1}} w$,

• the relation $\mathrel {V^{\circ }_{1}}$ is empty except that $z \mathrel {V^{\circ }_{1}} y$,

• $b \mathrel {P^{\circ }_{2}} a$,

• the relation $\mathrel {V^{\circ }_{2}}$ is empty,

• $\{1\} \mathrel {\rhd ^{\circ }}\varnothing$, $\{2\} \mathrel {\rhd ^{\circ }}\{1\}$, $\{1,2\} \mathrel {\rhd ^{\circ }}\varnothing$.

By construction, $\mathrel {\mathcal {R}}$ is an asymmetric CDR. Hence, it satisfies $RC 1$, $RC 2$, $M1$, $Maj 1$, $MM 1$, $M3$, $Maj 3$, $MM 3$ (Theorem 58 and Lemmas 42 and 56). It satisfies $M2_{2}$ but not $M2_{1}$ (due to the veto on $X_{1}$), not $Maj 2_{1}$ (by Lemma 42) and not $MM 2_{1}$ (by Lemma 42). Using Lemma 11 in Bouyssou and Pirlot (2007), we get that $UC$ and $LC_{2}$ are satisfied but $LC _{1}$ is violated.⁷

Since $\mathrel {\mathcal {R}}$ satisfies $M1$ it verifies $DMM 3$.

The relation $\mathrel {\mathcal {R}}$ contains the following pairs in $X\times X$:

• $(x, a) \mathrel {\mathcal {R}}(w, a)$, $(x, b) \mathrel {\mathcal {R}}(x, a)$, $(x, b) \mathrel {\mathcal {R}}(y, a)$, $(x, b) \mathrel {\mathcal {R}}(z, a)$, $(x, b) \mathrel {\mathcal {R}}(w, a)$,

• $(y, a) \mathrel {\mathcal {R}}(w, a)$, $(y, b) \mathrel {\mathcal {R}}(x, a)$, $(y, b) \mathrel {\mathcal {R}}(y, a)$, $(y, b) \mathrel {\mathcal {R}}(w, a)$ (but, due to $z \mathrel {V^{\circ }_{1}} y$, $Not [(y, b) \mathrel {\mathcal {R}}(z, a) ]$),

• $(z, a) \mathrel {\mathcal {R}}(x, a)$, $(z, a) \mathrel {\mathcal {R}}(y, a)$, $(z, a) \mathrel {\mathcal {R}}(w, a)$, $(z, b) \mathrel {\mathcal {R}}(x, a)$, $(z, a) \mathrel {\mathcal {R}}(x, b)$, $(z, b) \mathrel {\mathcal {R}}(y, a)$, $(z, b) \mathrel {\mathcal {R}}(y, b)$, $(z, b) \mathrel {\mathcal {R}}(z, a)$, $(z, b) \mathrel {\mathcal {R}}(w, a)$, $(z, b) \mathrel {\mathcal {R}}(w, b)$,

• $(w, b) \mathrel {\mathcal {R}}(x, a)$, $(w, b) \mathrel {\mathcal {R}}(y, a)$, $(w, b) \mathrel {\mathcal {R}}(z, a)$, $(w, b) \mathrel {\mathcal {R}}(w, a)$.

On $X_{2}$, it is easy to check that we have $b \mathrel {\succ _{2}^{\pm }} a$, so that $AC 1_{2}$, $AC 2_{2}$ and $AC 3_{2}$ hold.

On $X_{1}$, it is easy to check that $\mathrel {\succsim _{1}^{-}}$ is complete. We indeed have that:

$$\begin{aligned} z \mathrel {\succ _{1}^{-}} x \mathrel {\succ _{1}^{-}} y \mathrel {\succ _{1}^{-}} w. \end{aligned}$$

The relation $\mathrel {\succsim _{1}^{+}}$ is not complete. We have $z \mathrel {\succ _{1}^{+}} x$, $x \mathrel {\succ _{1}^{+}} y$ and $x \mathrel {\succ _{1}^{+}} w$ but neither $y\mathrel {\succsim _{1}^{+}} w$ nor $w \mathrel {\succsim _{1}^{+}} y$ since $(y, a) \mathrel {\mathcal {R}}(w, a)$ but $Not [(w, a) \mathrel {\mathcal {R}}(w, a) ]$ and $(w, b) \mathrel {\mathcal {R}}(z, a)$ but $Not [(y, b) \mathrel {\mathcal {R}}(z, a) ]$. This shows that $AC 1_{1}$ is violated. Condition $AC 3_{1}$ holds since $\mathrel {\succsim _{1}^{+}}$ and $\mathrel {\succsim _{1}^{-}}$ are not incompatible.

Each of $\mathrel {P^{\circ }_{1}}$ and $\mathrel {V^{\circ }_{1}}$ is the asymmetric part of some semiorder but these semiorders do not form an homogeneous chain of semiorders (the weak order induced by $\mathrel {P^{\circ }_{1}}$ imposes that $w$ is placed in the last position while that induced by $\mathrel {V^{\circ }_{1}}$ imposes the last position to $y$).

Example 89

(Asymmetric, $Not [ AC 2_{i}, M2_{i}, Maj 2_{i}, LC _{i} ]$) This example is an asymmetric variant of Example 86

Let $X= X_{1} \times X_{2}$ with $X_{1} = \{x, y, z, w \}$ and $X_{2} = \{a, b \}$. We build a CDR on $X$ with:

• $w \mathrel {P^{\circ }_{1}} y$, $w \mathrel {P^{\circ }_{1}} z$, $x \mathrel {P^{\circ }_{1}} z$, $y \mathrel {P^{\circ }_{1}} z$,

• the relation $\mathrel {V^{\circ }_{1}}$ is empty except that $y \mathrel {V^{\circ }_{1}} z$,

• $a \mathrel {P^{\circ }_{2}} b$,

• the relation $\mathrel {V^{\circ }_{2}}$ is empty,

• $\{1\} \mathrel {\rhd ^{\circ }}\varnothing$, $\{2\} \mathrel {\rhd ^{\circ }}\{1\}$.

By construction, $\mathrel {\mathcal {R}}$ is an asymmetric CDR. Hence, it satisfies $RC 1$, $RC 2$, $M1$, $Maj 1$, $MM 1$, $M3$, $Maj 3$, $MM 3$ (Theorem 58 and Lemmas 42 and 56). It satisfies $M2_{2}$ but not $M2_{1}$ (due to the veto on $X_{1}$), not $Maj 2_{1}$ (by Lemma 42) and not $MM 2_{1}$ (by Lemma 42). Using Lemma 11 in Bouyssou and Pirlot (2007), we get that $UC$ and $LC_{2}$ are satisfied but $LC _{1}$ is violated.⁸

Since $\mathrel {\mathcal {R}}$ satisfies $M1$ it verifies $DMM 3$.

The relation $\mathrel {\mathcal {R}}$ contains the following pairs in $X\times X$:

• $(x, a) \mathrel {\mathcal {R}}(x, b)$, $(x, a) \mathrel {\mathcal {R}}(y, b)$, $(x, a) \mathrel {\mathcal {R}}(z, a)$, $(x, a) \mathrel {\mathcal {R}}(z, b)$, $(x, a) \mathrel {\mathcal {R}}(w, b)$, $(x, b) \mathrel {\mathcal {R}}(z, b)$,

• $(y, a) \mathrel {\mathcal {R}}(x, b)$, $(y, a) \mathrel {\mathcal {R}}(y, b)$, $(y, a) \mathrel {\mathcal {R}}(z, a)$, $(y, a) \mathrel {\mathcal {R}}(z, b)$, $(y, a) \mathrel {\mathcal {R}}(w, b)$, $(y, b) \mathrel {\mathcal {R}}(z, b)$,

• $(z, a) \mathrel {\mathcal {R}}(x, b)$, $(z, a) \mathrel {\mathcal {R}}(z, b)$, $(z, a) \mathrel {\mathcal {R}}(w, b)$ (but $Not [(z, a) \mathrel {\mathcal {R}}(y, b) ]$, due to $y \mathrel {V^{\circ }_{1}} z$),

• $(w, a) \mathrel {\mathcal {R}}(x, b)$, $(w, a) \mathrel {\mathcal {R}}(y, a)$, $(w, a) \mathrel {\mathcal {R}}(y, b)$, $(w, a) \mathrel {\mathcal {R}}(z, a)$, $(w, a) \mathrel {\mathcal {R}}(z, b)$, $(w, a) \mathrel {\mathcal {R}}(w, b)$, $(w, b) \mathrel {\mathcal {R}}(y, b)$, $(w, b) \mathrel {\mathcal {R}}(z, b)$.

On $X_{2}$, it is easy to check that we have $a \mathrel {\succ _{2}^{\pm }} b$, so that $AC 1_{2}$, $AC 2_{2}$ and $AC 3_{2}$ hold.

On $X_{1}$, it is easy to check that $\mathrel {\succsim _{1}^{+}}$ is complete. We indeed have that:

$$\begin{aligned} w \mathrel {\succ _{1}^{\pm }} [x \mathrel {\sim _{1}^{+}} y] \mathrel {\succ _{1}^{+}} z. \end{aligned}$$

The relation $\mathrel {\succsim _{1}^{-}}$ is not complete. We have $w \mathrel {\succ _{1}^{-}} x$, $w \mathrel {\succ _{1}^{-}} y$, $x \mathrel {\succ _{1}^{-}} z$ and $y \mathrel {\succ _{1}^{-}} z$ but neither $x \mathrel {\succsim _{1}^{-}} y$ nor $y \mathrel {\succsim _{1}^{-}} x$ since $(z, a) \mathrel {\mathcal {R}}(x, b)$ but $Not [(z, a) \mathrel {\mathcal {R}}(y, b) ]$ and $(w, a) \mathrel {\mathcal {R}}(y, a)$ but $Not [(w, a) \mathrel {\mathcal {R}}(x, a) ]$. This shows that $AC 2_{1}$ is violated. Condition $AC 3_{1}$ holds since $\mathrel {\succsim _{1}^{+}}$ and $\mathrel {\succsim _{1}^{-}}$ are not incompatible.

Each of $\mathrel {P^{\circ }_{1}}$ and $\mathrel {V^{\circ }_{1}}$ is the asymmetric part of some semiorder but these semiorders do not form an homogeneous chain of semiorders (the weak order induced by $\mathrel {P^{\circ }_{1}}$ imposes that $w$ is placed in the first position while that induced by $\mathrel {V^{\circ }_{1}}$ imposes the first position to $y$).

Example 90

(Asymmetric $Not [ RC 1_{i}, M2_{i}, Maj 2_{i}, MM 2_{i}, Maj 3_{i} ]$)

This example was not published before.

Let $X=\{x,y,z,w\}\times \{a,b\}\times \{p,q\}$ and $\mathrel {\mathcal {R}}$ consist of the set of pairs listed in Table 4.

Table 4 Relation $\mathrel {\mathcal {R}}$ in Example 90

It is easy to see that $\mathrel {\mathcal {R}}$ is an asymmetric relation.

As for the comparison of preference differences on each attribute, we have, for all $(\alpha , \beta ) \in \Gamma = \{ (x,x), (y,y),$ $(z,z), (w,w),$ $(x,z), (x,w),$ $(y,x), (y,z),$ (y,w), (z,x),$(w,x), (w,y), (w,z) \}$,

• $(\alpha , \beta ) \mathrel {\succ _{1}^{*}} (x,y) \mathrel {\succ _{1}^{*}} (z,y)$ and $(\alpha , \beta ) \mathrel {\succ _{1}^{*}} (z,w) \mathrel {\succ _{1}^{*}} (z,y)$, while $(x,y)$ and $(z,w)$ are incomparable in terms of $\mathrel {\succsim _{1}^{*}}$,

• $(a,b) \mathrel {\succ _{2}^{*}} [(a,a), (b,b)] \mathrel {\succ _{3}^{*}} (b,a)$,

• $(p,q) \mathrel {\succ _{3}^{*}} [(p,p), (q,q)] \mathrel {\succ _{3}^{*}} (q,p)$.

The upward and downward dominance relations are as follows:

• $y \mathrel {\succ _{1}^{\pm }} w \mathrel {\succ _{1}^{\pm }} x \mathrel {\succ _{1}^{\pm }} z$,

• $a \mathrel {\succ _{2}^{\pm }} b$,

• $p \mathrel {\succ _{3}^{\pm }} q$.

$RC 1_{1}$ does not hold since the pairs $(x,y)$ and $(z,w)$ are not comparable w.r.t. $\mathrel {\succsim _{1}^{*}}$, but $RC 1_{2}$ and $RC 1_{3}$ hold true. For $j \in \{1,2,3\}$, $RC 2_{j}$, $AC 1_{j}$, $AC 2_{j}$, $AC 3_{j}$ are clearly satisfied. For $j=2$ and $j=3$, using Lemma 25, we see that $\mathrel {\mathcal {R}}$ fulfills $M1_{j}$ and $M2_{j}$ hence it satisfies $UC _{j}$ and $LC _{j}$ (by Lemma 11 in Bouyssou and Pirlot 2007), $Maj 1_{j}$ and $Maj 2_{j}$ ( by Lemma 34), $UC _{j}$ and $LC _{j}$ (by  Lemma 11 in Bouyssou and Pirlot 2007), $M3_{j}$, $Maj 3_{j}$, $MM 1_{j}$, $MM 2_{j}$ and $MM 3_{j}$ (since each of the latter is implied by one of the previously established properties of $\mathrel {\mathcal {R}}$ ).

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

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

$\mathrel {\mathcal {R}}$ satisfies $M3_{1}$. Assume to the contrary that there are $s,t,u,v \in X_{1}$ and $S,T,U,V,Q,R \in X_{-1}$ such that: (1) $(s,S)\mathrel {\mathcal {R}}(t,T)$, (2) $(t,U)\mathrel {\mathcal {R}}(s,V)$, (3) $(u,Q)\mathrel {\mathcal {R}}(v,R)$, (4) $Not [(t,S)\mathrel {\mathcal {R}}(s,T) ]$, (5) $Not [(u,S)\mathrel {\mathcal {R}}(v,T) ]$, (6) $Not [(u,U)\mathrel {\mathcal {R}}(v,V) ]$. Using (1), (4) and Lemma 22.2, we deduce that $(s,t)$ can only be one of the pairs $(y,x), (y,z)$ or $(w,z)$. If $(s,t)=(y,z)$, (2) never holds true. In case $(s,t)=(y,x)$, (1) and (4) imply $[S=ap \text { and } T= bp]$ or $[S=aq \text { and } T=bq]$. Contradicting (5), we have $(u,S) \mathrel {\mathcal {R}}(v,T)$ for all $u,v \in X_{1}$ except for $(u,v) = (z,y)$, for which (3) does not hold. The case in which $(s,t) = (w,z)$ is dealt with similarly. As a conclusion, $M3_{1}$ holds for $\mathrel {\mathcal {R}}$ .

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

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

Since $\mathrel {\mathcal {R}}$ satisfies $M1_{1}$ (resp. $M3_{1}$) it satisfies $MM 1_{1}$ (resp. $MM 3_{1}$).

Since $\mathrel {\mathcal {R}}$ satisfies $MM 1_{1}$ it satisfies $DMM 3_{1}$ (by Lemma 66).