A note on ELECTRE TRI-nB with few limiting profiles

Abstract

ELECTRE TRI-nB is a method designed to sort alternatives evaluated on several attributes into ordered categories. It is an extension of ELECTRE TRI-B that uses several limiting profiles, instead of one, to delimit each category. In a previous paper we have characterized the ordered partitions that can be obtained with ELECTRE TRI-nB, using a simple axiom called linearity. The simplicity of this characterization crucially rests on the possibility to use as many limiting profiles as we like to delimit a category. This is not completely realistic and there is a need to study models in which the number of limiting profiles delimiting each category is restricted. This note starts the investigation of such models. We specifically study the case of models using one or two profiles together with an outranking relation based on unanimity.

1 Introduction

This paper is about ELECTRE TRI (often abbreviated as ETRI in what follows). The original method called ETRI-B (Yu 1992; Roy and Bouyssou 1993) uses one limiting profile to delimit each category. Fernández et al. (2017) have suggested an extension of this method, called ETRI-nB, that uses several limiting profiles to delimit each category¹.

In a previous paper (Bouyssou et al. 2021), we have given a theoretical look at ETRI-nB. We presented a simple characterization of the partitions that can be obtained using the pseudo-conjunctive version of ETRI-nB (ETRI-nB-pc). This characterization uses a condition, linearity, that is familiar (Goldstein 1991; Greco et al. 2001; Słowiński et al. 2002; Bouyssou and Marchant 2007a) in the study of sorting models and that has a transparent interpretation. This allowed us to precisely position ETRI-nB-pc within the larger family of sorting models for alternatives evaluated on several attributes.

A limitation of the analysis in Bouyssou et al. (2021) is that the simple characterization is obtained when there is no restriction on the number of profiles delimiting each category. If practical applications of ETRI-nB are sought for, this is problematic. Hence, it is useful to study models in which the number of profiles used to delimit each category is constrained: such constraints will surely facilitate the elicitation of the parameters of the model (Fernández et al. 2019). Such models with a constraint on the number of profiles are the subject of this note. Specifically, we study, from an axiomatic point of view, models that use one or two profiles, together with an outranking relation that is based on unanimity. The choice of this particular case is motivated by the special status of models using an outranking relation that is based on unanimity, as uncovered in Bouyssou et al. (2021).

The rest of this text is organized as follows. Section 2 introduces our notation and framework. Section 3 presents some background results on ETRI-B and ETRI-nB. Section 4 presents our main results. A final section discusses our findings.

2 Notation and framework

As in Bouyssou et al. (2021), we will restrict our attention to the case of two categories. This allows us to use a simple framework while not concealing any important difficulty. For the same reasons, we suppose throughout that the set of objects to be sorted is finite. Our setting and vocabulary is exactly as in Bouyssou et al. (2021). It is briefly recalled below.

2.1 The setting

Let $n\ge 2$ be an integer and $X= X_{1} \times X_{2} \times \cdots \times X_{n}$ be a finite set of objects. Elements $x, y, z,\ldots$ of $X$ are interpreted as alternatives evaluated on a set $N= \lbrace 1, 2, \ldots , n \rbrace$ of attributes. For $x,y \in X$, $i \in N$ and $J \subseteq N$, we use $X_{J}$, $X_{-J}$, $X_{i}$, $X_{-i}$, $(x_{J}, y_{-J})$, and $(x_{i}, y_{-i})$, as is usual.

Our primitives consist in a twofold partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ of the set $X$. We interpret the set ${\mathcal {A}}$ as containing sAtisfactory objects, while ${\mathcal {U}}$ contains Unsatisfactory ones.

We say that an attribute $i \in N$ is influential for $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ if there are $x_{i}, y_{i}\in X_{i}$ and $a_{-i}\in X_{-i}$ such that $(x_{i}, a_{-i}) \in {\mathcal {A}}$ and $(y_{i}, a_{-i}) \in {\mathcal {U}}$. We say that an attribute is degenerate if it is not influential. Suppressing, if necessary, degenerate attributes, it is not restrictive to suppose that all attributes are influential for $\langle {\mathcal {A}},{\mathcal {U}}\rangle$. We do so in what follows ².

Remark 1

Suppose that I is a proper nonempty subset of $N$ and $i \in I$. It is clear that, if $i \in N$ is influential, then I is influential, i.e., there are $x_{I}, y_{I} \in X_{I}$ and $a_{-I} \in X_{-i}$ such that $(x_{I}, a_{-I}) \in {\mathcal {A}}$ and $(y_{I}, a_{-I}) \in {\mathcal {U}}$. Our hypothesis concerning the influence of each attribute $i\in N$ therefore implies that all proper nonempty subsets I of attributes are influential.

A twofold partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ induces on each $i \in N$ a binary relation defined letting, for all $i \in N$ and all $x_{i}, y_{i} \in X_{i}$,

$$\begin{aligned} x_{i} {\sim }_{i}y_{i} \text { if }\left[ \forall a_{-i} \in X_{-i}, \left( y_{i},a_{-i}\right) \in {\mathcal {A}}\iff (x_{i},a_{-i}) \in {\mathcal {A}}\right] . \end{aligned}$$

This relation is always reflexive, symmetric and transitive, i.e., is an equivalence ³. As in Bouyssou et al. (2021), it is not restrictive to suppose that all equivalence classes of ${\sim }_{i}$ are trivial, i.e., reduced to a single element.

2.2 Models $(E)$, $(E^{c})$, and $(E^{u})$

The following definition is taken from Bouyssou et al. (2021, Def. 6) to which we refer for further discussion and comments. It considers partitions built as follows. On each attribute $i \in N$ there is a linear arrangement of the elements in $X_{i}$ interpreted as an “at least as good as” relation (the relation $\mathrel {S_{i}}$). The elements of $X_{i}$ are compared using a threshold (hence, the idea of semiorder), so that indifference is not necessarily transitive. There is another linear arrangement of the elements in $X_{i}$ to single out which differences between these elements are “very large” (the veto relation $\mathrel {V_{i}}$). This second linear arrangement is compatible with the previous one (hence, the idea of homogeneous family of semiorders). The model singles out a number of profiles (the set ${\mathcal {P}}$). In order to belong to category ${\mathcal {A}}$, an object $x \in X$ must outrank at least one of the profiles and, moreover, no profile should be strictly preferred to x. Outranking is defined via a classical concordance / non-discordance mechanism. An object x outranks another object y if the set of attributes for which x is at least as good as y is “sufficiently important” (as determined by the set ${\mathcal {F}}$) and there si no attribute for which y is “far better” than x.

Definition 1

We say that a partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ has a representation in Model $(E)$ if:

• for all $i \in N$, there is a semiorder $\mathrel {S_{i}}$ on $X_{i}$ (with asymmetric part $\mathrel {P_{i}}$ and symmetric part $\mathrel {I_{i}}$),

• for all $i \in N$, there is a strict semiorder $\mathrel {V_{i}}$ on $X_{i}$ that is included in $\mathrel {P_{i}}$ and is the asymmetric part of a semiorder $\mathrel {U_{i}}$,

• for all $i \in N$, $(\mathrel {S_{i}}, \mathrel {U_{i}})$ is a homogeneous nested chain of semiorders and ${\mathrel {W_{i}}} = {\mathrel {S}_{i}^{wo}} \cap {\mathrel {U}_{i}^{wo}}$ is a weak order that is compatible with both $\mathrel {S_{i}}$ and $\mathrel {U_{i}}$,

• there is a set of subsets of attributes ${\mathcal {F}}\subseteq 2^{N}$ such that, for all $I, J \in 2^{N}$, $[I \in {\mathcal {F}}$ and $I \subseteq J]$ $\Rightarrow J \in {\mathcal {F}}$,

• there is a binary relation $\mathrel {S}$ on X (with symmetric part I and asymmetric part P) defined by:

  $$\begin{aligned} x \mathrel {S}y \iff \left[ S(x,y) \in {\mathcal {F}}\text { and } V(y,x) = \varnothing \right] , \end{aligned}$$

• there is a finite set ${\mathcal {P}}= \{p^{1}, \ldots , p^{k}\} \subseteq X$ of profiles, such that for all $p, q \in {\mathcal {P}}$, ${\textit{Not}}[p \mathrel {P}q ]$,

such that

$$\begin{aligned} x \in {\mathcal {A}}\iff {\left\{ \begin{array}{ll} x \mathrel {S}p &{}\text { for some } p \in {\mathcal {P}}\quad \text {and}\\ {\textit{Not}}[q \mathrel {P}x ] &{}\text { for all } q \in {\mathcal {P}}, \end{array}\right. }\qquad \qquad \qquad (E) \end{aligned}$$

where,

$$\begin{aligned} S(x, y) = \{i \in N: x_{i} \mathrel {S_{i}}y_{i}\}, \end{aligned}$$

and

$$\begin{aligned} V(x, y) = \{i \in N: x_{i} \mathrel {V_{i}}y_{i}\}. \end{aligned}$$

We then say that $\langle (\mathrel {S_{i}}, \mathrel {V_{i}})_{i\in N}, {\mathcal {F}}, {\mathcal {P}}\rangle$ is a representation of $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ in Model $(E)$. Model $(E^{c})$ is the particular case of Model $(E)$, in which there is a representation that shows no discordance effects, i.e., in which all relations $\mathrel {V_{i}}$ are empty. Model $(E^{u})$ is the particular case of Model $(E)$, in which there is a representation that requires unanimity, i.e., such that ${\mathcal {F}}= \{N\}$.

We say that a partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ can be represented in Model $(E_{\le k})$ (resp. $(E_{k})$) if it has a representation in Model $(E)$ that uses no more than k (resp. exactly k) profiles. We define Models $(E^{c}_{\le k})$, $(E^{c}_{k})$, $(E^{u}_{\le k})$ and $(E^{u}_{k})$ accordingly.

The relations between Model $(E)$ and ETRI-nB-pc were analyzed in detail in Bouyssou et al. (2021, Remarks 8 and 17). To keep this note short, we do not repeat this analysis here. Basically, any partition that can be obtained with ETRI-nB-pc can also be obtained using Model $(E)$, and vice versa.

A long term objective would be to characterize Model $(E_{\le k})$ for all “small” values of k. Clearly, we expect models using a small number of profiles to be assessed more easily than models using a larger number of profiles. Our hope is that this characterization would help us understand the expressiveness gain that is obtained when using 1, 2, 3, ...profiles.

We begin this investigation here by characterizing Model $(E^{u}_{\le 2})$, i.e., the particular case of Model $(E)$ based on unanimity and using no more than two profiles. Before we do so, it will be useful to recall a number of background results.

3 Background results

This section presents a few existing results that will later be helpful.

3.1 A characterization of model $(E)$

Following Bouyssou et al. (2021), we define on each $X_{i}$ the binary relation ${\succsim }_{i}$ letting, for all $x_{i}, y_{i}\in X_{i}$,

$$\begin{aligned} x_{i} {\succsim }_{i}y_{i} \text { if }\left[ \text{ for } \text{ all } a_{-i} \in X_{-i}, \left( y_{i}, a_{-i}\right) \in {\mathcal {A}}\Rightarrow \left( x_{i}, a_{-i}\right) \in {\mathcal {A}}\right] . \end{aligned}$$

This relation is, by construction, reflexive and transitive. The symmetric part of the relation ${\succsim }_{i}$ clearly coincides with the relation ${\sim }_{i}$ defined above.

Definition 2

We say that the partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ is linear on attribute $i \in N$ (condition $i$-linear) if, for all $x_{i}, y_{i} \in X_{i}$ and all $a_{-i}, b_{-i}\in X_{-i}$,

$$\begin{aligned} \left. \begin{array}{c} (x_{i}, a_{-i}) \in {\mathcal {A}}\\ \text{ and }\\ (y_{i}, b_{-i}) \in {\mathcal {A}}\end{array} \right\} \Rightarrow \left\{ \begin{array}{c} (y_{i}, a_{-i}) \in {\mathcal {A}},\\ \text{ or }\\ (x_{i}, b_{-i}) \in {\mathcal {A}}. \end{array} \right. \qquad \qquad \qquad \qquad (i{\text {-linear}}) \end{aligned}$$

The partition is said to be linear if it is $i$-linear, for all $i \in N$.

The above condition was first proposed in Goldstein (1991) and generalized in Greco et al. (2001) and Słowiński et al. (2002). It is easy to check that a partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ is $i\text {-linear}$ iff the relation ${\succsim }_{i}$ is complete.

Let us define the relation ${\succsim }$ on $X$ letting, for all $x,y \in X$,

$$\begin{aligned} x {\succsim }y \iff x_{i} {\succsim }_{i}y_{i}, \text { for all } i \in N. \end{aligned}$$

Let ${\mathcal {A}}_{*}= \mathrm{Min}({\mathcal {A}}, {\succsim })$ be the set of minimal elements in ${\mathcal {A}}$ for ${\succsim }$.

The main result in Bouyssou et al. (2021) is as follows.

Proposition 1

Let $X= \prod _{i=1}^{n} X_{i}$ be a finite set and $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ be a twofold partition of $X$. The partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ has a representation in Model $(E)$ iff it is linear. This representation can always be taken to be $\langle ({\succsim }_{i})_{i \in N}, {\mathcal {F}}= \{N\}, {\mathcal {P}}= {\mathcal {A}}_{*}\rangle$. Hence, Models $(E)$, $(E^{c})$ and $(E^{u})$ are equivalent.

The logic of the proof of this result is simple. The relation ${\succsim }$ is a partial order, being reflexive, antisymmetric and transitive. Because $X$ is finite and ${\mathcal {A}}$ is nonempty, we know that the set ${\mathcal {A}}_{*}$ is nonempty. Our proof consists in taking ${\mathcal {P}}= {\mathcal {A}}_{*}$ and ${\mathcal {F}}= \{N\}$. All elements in ${\mathcal {A}}_{*}$ are taken as profiles. But the cardinality of this set may be high (Bouyssou et al. 2020). Hence, it is interesting to have a characterization of model $(E)$ with a limited number of profiles. This note starts with Model $(E^{u}_{\le 2})$.

3.2 A characterization of Models $(E_{1})$, $(E^{c}_{1})$ and $(E^{u}_{1})$

Models $(E_{1})$, $(E^{c}_{1})$ and $(E^{u}_{1})$ have been studied in Bouyssou and Marchant (2007a). Model $(E_{1})$ is the noncompensatory sorting model with veto. Model $(E^{c}_{1})$ is the noncompensatory sorting model. Model $(E^{u}_{1})$ is the particular case of the noncompensatory sorting model in which ${\mathcal {F}}= \{N\}$, called the conjunctive sorting model.

3.2.1 Model $(E^{c}_{1})$

Definition 3

We say that a partition is strongly 2-graded on attribute $i \in N$ (condition $i$-s-2-graded) if

$$\begin{aligned} \left. \begin{array}{c} \left( x_{i}, a_{-i}\right) \in {\mathcal {A}}\\ \text{ and }\\ \left( y_{i}, b_{-i}\right) \in {\mathcal {A}}\\ \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} \left( x_{i}, b_{-i}\right) \in {\mathcal {A}}\\ \text{ or }\\ \left( z_{i}, a_{-i}\right) \in {\mathcal {A}},\\ \end{array} \right. \qquad \qquad ({{\text {{ i}-s-2-graded}}}) \end{aligned}$$

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

The above condition was introduced in Bouyssou and Marchant (2007a). Bouyssou and Marchant (2007a) have shown that condition $i$-s-2-graded implies i-linearity and the fact that the relation ${\succsim }_{i}$ has at most two equivalence classes (and, hence, two equivalence classes, since a relation ${\succsim }_{i}$ with a single equivalence class means that this attribute is not influential). They also show how to factorize this condition so as to make i-linearity appear explicitly. We will not use this factorization in the present paper.

Bouyssou and Marchant (2007a, Th. 21, p. 230) have shown the following.

Proposition 2

A partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ has a representation in the noncompensatory sorting model $(E^{c}_{1})$ iff it is strongly 2-graded on all $i \in N$.

3.2.2 Model $(E_{1})$

Definition 4

We say that the partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ is strongly 3-graded with veto on attribute $i \in N$ (condition $i$-s-3v-graded) if, for all $x_{i}, y_{i}, z_{i} \in X_{i}$ and all $a_{-i}, b_{-i}, c_{i}\in X_{-i}$,

$$\begin{aligned} \left. \begin{array}{c} \left( x_{i}, a_{-i}\right) \in {\mathcal {A}}\\ \text{ and }\\ \left( z_{i}, c_{-i}\right) \in {\mathcal {A}}\\ \text{ and }\\ \left( y_{i}, b_{-i}\right) \in {\mathcal {A}}\\ \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} \left( x_{i}, b_{-i}\right) \in {\mathcal {A}}\\ \text{ or }\\ \left( z_{i}, a_{-i}\right) \in {\mathcal {A}}\end{array} \right. \qquad \qquad \qquad ({\text {{ i}-s-3v-graded}}) \end{aligned}$$

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

The above condition was introduced in Bouyssou and Marchant (2007a). Bouyssou and Marchant (2007a) have shown that condition $i$-s-3v-graded implies i-linearity and the fact that the relation ${\succsim }_{i}$ has at most three equivalence classes. When the relation ${\succsim }_{i}$ has exactly three equivalence classes, the last one acts as a veto, i.e., when an object has an evaluation in this equivalence class, it cannot belong to ${\mathcal {A}}$. They also show how to factorize this condition so as to make i-linearity appear explicitly. This factorization will not be useful here.

The following definition, taken from Bouyssou and Marchant (2007a), will be useful.

Definition 5

Let

$$\begin{aligned} Z_{i} = \lbrace x_{i} \in X_{i}: \left( x_{i}, a_{-i}\right) \in {\mathcal {U}}, \text { for all } a_{-i}\in X_{-i} \rbrace . \end{aligned}$$

Let $Y_{i} = X_{i}\setminus Z_{i}$. Consider the set $Y = \prod _{i=1}^{n}Y_{i}$ and let ${\mathcal {A}}' = \AA \cap Y$ and ${\mathcal {U}}' = {\mathcal {U}}\cap Y$.

Since $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ is a partition, we have $\AA \ne \varnothing$ so that Y cannot be empty. It is easy to see that if condition $i$-s-3v-graded holds for $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ on X, then condition $i$-s-2-graded holds for the partition $\langle {\mathcal {A}}',{\mathcal {U}}'\rangle$ of Y.

Bouyssou and Marchant (2007a, Th. 35, p. 237) have shown the following.

Proposition 3

A partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ has a representation in the noncompensatory sorting model with veto $(E_{1})$ iff it is strongly 3v-graded on all $i \in N$.

3.2.3 Model $(E^{u}_{1})$

We say $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ is i-strongly$^{*}$-conjunctive (condition $i$-s$^{*}$-conj) if

$$\begin{aligned} \left. \begin{array}{c} \left( x_{i}, a_{-i}\right) \in {\mathcal {A}}\\ \text{ and }\\ \left( y_{i}, b_{-i}\right) \in {\mathcal {A}}\\ \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} \left( x_{i}, b_{-i}\right) \in {\mathcal {A}}\\ \text{ and }\\ \left( y_{i}, a_{-i}\right) \in {\mathcal {A}}\\ \end{array} \right. \end{aligned}$$

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

Bouyssou and Marchant (2007a) have shown that this condition implies $i\text {-linear}$ and $i$-s-2-graded. They also show how to factorize this condition so as to make i-linearity appear explicitly. This factorization will not be useful here.

Bouyssou and Marchant (2007a, Prop. 32, p. 235) prove the following:

Proposition 4

A partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ has a representation in the conjunctive sorting model $(E^{u}_{1})$ iff it satisfies $i$-s$^{*}$-conj, for all $i \in N$.

4 A characterization of model $(E^{u}_{\le 2})$

Proposition 1 shows that, if k is taken large enough, a partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ that has a representation in model $(E^{c})$ or, more generally, in model $(E)$, also has a representation in model $(E^{u}_{\le k})$. This seems to call for the study of Models $(E^{u}_{\le k})$ with small values of k. We start here with the characterization of Model $(E^{u}_{\le 2})$.

4.1 Observations and conventions

In Model $(E^{u}_{1})$, all relations ${\succsim }_{i}$ have at most two equivalence classes. The second equivalence class plays the role of a veto: an alternative that has an evaluation belonging to the second equivalence class on any attribute cannot belong to ${\mathcal {A}}$. In Model $(E^{u}_{1})$, it is easy to see that it is not restrictive to take ${\mathrel {S}_{i}} = {{\succsim }_{i}}$.

In Model $(E^{u}_{2})$, all relations ${\succsim }_{i}$ can have at most three equivalence classes: (i) strictly below the two profiles, (ii) above the lower profile and strictly below the upper profile (iii) above the upper profile. Moreover, when the relation ${\succsim }_{i}$ has three distinct equivalence classes, the last class acts as a veto: an object that is below the two profiles on some attribute cannot belong to ${\mathcal {A}}$. In Model $(E^{u}_{2})$, it is easy to see that it is not restrictive to take ${\mathrel {S}_{i}} = {{\succsim }_{i}}$.

In Model $(E^{u}_{2})$, it is easy to check that, on each attribute $i \in N$, the following three situations may happen:

• 1. the relation ${\succsim }_{i}$ has exactly three distinct equivalence classes. This means that the two profiles have distinct (i.e., not belonging to the same equivalence class of ${\sim }_{i}$) values on attribute i and that something is below the lower profile.

• 2. the relation ${\succsim }_{i}$ has exactly two distinct equivalence classes and the last class does not correspond to a veto. This means that the two profiles have distinct values on attribute i but that there is nothing below the lower profile.

• 3. the relation ${\succsim }_{i}$ has exactly two distinct equivalence classes and the last class corresponds to a veto. This means that the two profiles have identical values on attribute i.

The treatment of the third case (in view of our convention regarding ${\sim }_{i}$, if p and q are the two profiles, the third case corresponds to an attribute for which $p_{i} = q_{i}$) is not difficult but it complicates things. Henceforth, we suppose that the third case does not happen. To avoid any misunderstanding, let us call $(E^{u^{*}}_{2})$ the particular case of Model $(E^{u}_{2})$ in which case 3 is excluded. Model $(E^{u^{*}}_{\le 2})$ is defined accordingly as either Model $(E^{u}_{1})$ or Model $(E^{u^{*}}_{2})$.

Using notation introduced in Definition 5, working with $(E^{u^{*}}_{2})$ instead of $(E^{u}_{2})$ implies that all attributes are influential for the partition $\langle {\mathcal {A}}',{\mathcal {U}}'\rangle$ of Y.

Remark 2

Suppose that $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ has a representation in Model $(E^{u^{*}}_{2})$ with ${\mathcal {P}}= \{p, q\}$. This defines a partition of the set of all attributes into $N^{p} = \{i \in N: p_{i} {\succ }_{i}q_{i}\}$, the set of attribute for which p is above q and $N^{q} = \{i \in N: q_{i} {\succ }_{i}p_{i}\}$, the set of attributes for which q is above p. We have $N^{p} \ne \varnothing$, $N^{q} \ne \varnothing$, $N^{p} \cap N^{q} = \varnothing$ and $N^{p} \cup N^{q} = N$.

Remark 3

As already mentioned, our main motivation for studying Model $(E^{u}_{2})$ is linked to the fact that Model $(E^{u})$ is equivalent to Model $(E)$, when the number of profiles is not constrained. Besides this theoretical motivation, Model $(E^{u}_{2})$ may have an interest in itself because it relates to already familiar models.

For instance, a partition that can be represented in the noncompensatory sorting model (Model $(E^{c}_{1})$, using the notation of this paper) studied in Bouyssou and Marchant (2007a) can sometimes be represented in Model $(E^{u}_{\le 2})$.

In Model $(E^{c}_{1})$, all relations ${\succsim }_{i}$ have two distinct equivalence classes. Define ${\mathcal {F}}_{*}= \mathrm{Min}({\mathcal {F}}, \supseteq )$ as the set of all minimal winning coalitions w.r.t. set inclusion. When $\left| {\mathcal {F}}_{*} \right| = 2$, such a model can also be represented in Model $(E^{u}_{\le 2})$. A simple example of such a situation is the following. Take $N=\{1,2,3,4\}$ and, for all $i \in N$, $X_{i} = \{0,10\}$. Let $x \in {\mathcal {A}}$ iff $x_{i} = 10$ on, at least, either the first two or the last two attributes. This partition has a representation in Model $(E_{1})$ with the profile $p = (10,10,10,10)$, ${\mathcal {F}}_{*}= \{\{1,2\}, \{3,4\}\}$, and ${\mathrel {S_{i}}} = {\ge }$, for all $i \in N$. It can also be represented in Model $(E^{u}_{\le 2})$, keeping the same relations ${\mathrel {S_{i}}}$, with ${\mathcal {F}}= \{N\}$ and the two profiles (10, 10, 0, 0) and (0, 0, 10, 10).

However, it is clear there are partitions that can be represented in Model $(E^{c}_{1})$ but that cannot be represented in Model $(E^{u}_{\le 2})$, see Example 3 below. This happens, in particular, when $\left| {\mathcal {F}}_{*} \right| > 2$.

Let us finally observe that there are some noncompensatory sorting models with veto, as defined in Bouyssou and Marchant (2007a) (Model $(E_{1})$, using the notation in the present paper) that can be represented in Model $(E^{u}_{\le 2})$. A simple example of such a situation is the following. Take $N=\{1,2,3,4\}$ and, for all $i \in N$, $X_{i} = \{0,5,10\}$. Let $x \in {\mathcal {A}}$ iff $x_{i} \ge 10$ on either the first two or the last two attributes and, for all $i \in N$, $x_{i} \ne 0$. This partition has a representation in Model $(E_{1})$ with the profile $p = (10,10,10,10)$, ${\mathcal {F}}_{*}= \{\{1,2\}, \{3,4\}\}$, ${\mathrel {S_{i}}} = {\ge }$, for all $i \in N$, and $10 \mathrel {V_{i}}0$, for all $i \in N$. It can also be represented in Model $(E^{u^{*}}_{\le 2})$, keeping the same relations $\mathrel {S_{i}}$ and $\mathrel {V_{i}}$, with ${\mathcal {F}}= \{N\}$ and the two profiles (10, 10, 5, 5) and (5, 5, 10, 10),

4.2 Axioms

We introduce several conditions that are simple adaptations of already encountered conditions to the case of a nonempty subset $I \subseteq N$ of attributes, instead of just a single attribute $i \in N$.

4.2.1 I-linearity

Definition 6

We say that $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ satisfies I-linearity (condition $I\text {-linear}$) if

$$\begin{aligned} \left. \begin{array}{c} \left( x_{I}, a_{-I}\right) \in {\mathcal {A}}\\ \text{ and }\\ \left( y_{I}, b_{-I}\right) \in {\mathcal {A}}\\ \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} \left( x_{I}, b_{-I}\right) \in {\mathcal {A}}\\ \text{ or }\\ \left( y_{I}, a_{-I}\right) \in {\mathcal {A}}\end{array} \right. \qquad \qquad \qquad \qquad ({I\text {-linear}}) \end{aligned}$$

for all $x_{I}, y_{I} \in X_{I}$ and all $a_{-I}, b_{-I} \in X_{-I}$.

This condition is familiar (e.g., Bouyssou and Marchant 2009, 2010; Vind 1991, 2003). Its interpretation is similar to that of condition $i\text {-linear}$. It ensures that on the Cartesian product of the sets $X_{i}$ for the attributes i belonging to I, one can define a weak order that is compatible with the partition. The relation ${\succsim }_{I}$ on $X_{I}$ is defined letting

$$\begin{aligned} x_{I} {\succsim }_{I} y_{I} \Leftrightarrow \left[ (y_{I}, a_{-I}) \in {\mathcal {A}}\Rightarrow (x_{I}, a_{-I}) \in {\mathcal {A}}\right] , \end{aligned}$$

for all $x_{I}, y_{I} \in X_{I}$ and all $a_{-I} \in X_{-I}$. We use ${\succ }_{I}$ and ${\sim }_{I}$ as is usual.

It is clear that the relation ${\succsim }_{I}$ is always transitive but may not be complete. We leave to the reader the simple proof of the following lemma.

Lemma 1

A partition is $I\text {-linear}$ iff ${\succsim }_{I}$ is complete.

4.2.2 $I$-s-3v-graded

Definition 7

We say that $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ is strongly 3-graded with veto on I (condition $I$-s-3v-graded) if

$$\begin{aligned} \left. \begin{array}{c} \left( x_{I}, a_{-I}\right) \in {\mathcal {A}}\\ \text{ and }\\ \left( y_{I}, b_{-I}\right) \in {\mathcal {A}}\\ \text{ and }\\ \left( z_{I}, c_{-I}\right) \in {\mathcal {A}}\\ \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} \left( x_{I}, b_{-I}\right) \in {\mathcal {A}}\\ \text{ or }\\ \left( z_{I}, a_{-I}\right) \in {\mathcal {A}}\end{array} \right. \qquad \qquad \qquad \qquad ({{I\text {-s-3v-graded}}}) \end{aligned}$$

for all $x_{I}, y_{I}, z_{I} \in X_{I}$ and all $a_{-I}, b_{-I} \in X_{-I}$.

The above condition is apparently new. It generalizes condition $i$-s-3v-graded to subsets of attributes. The interpretation of this condition is exactly similar to that of condition $i$-s-3v-graded. When $I$-s-3v-graded holds, the relation ${\succsim }_{I}$ is a weak order that can have at most three equivalence classes. When it has three equivalence classes, the bottom class acts as a veto: an object that has on the attributes in I an evaluation belonging to this equivalence class cannot be in ${\mathcal {A}}$.

Remark 4

Following the analysis in Bouyssou and Marchant (2007a), it is easy to factorize Condition $I$-s-3v-graded so as to make $I\text {-linear}$ appear explicitly. This factorization will not be used in the present paper.

We leave to the reader the simple proofs of the following two lemmas.

Lemma 2

Condition $I$-s-3v-graded implies Condition $I$-linear.

Lemma 3

Condition $I$-s-3v-graded is equivalent to saying that ${\succsim }_{I}$ is a weak order having at most three equivalence classes and that, moreover, if ${\succsim }_{I}$ has exactly three distinct equivalence classes and if $x_{I}$ belongs to the last equivalence class of ${\succsim }_{I}$ then $(x_{I}, a_{-I}) \in {\mathcal {U}}$, for all $a_{-I}\in X_{-I}$.

Let us also notice the following: when I and J partition $N$, their roles are symmetric in the expression of $I$-s-3v-graded.

Lemma 4

Let I, J be a partition of $N$. The partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ satisfies Condition $I$-s-3v-graded iff it satisfies Condition $J$-s-3v-graded.

Proof

Suppose that $I$-s-3v-graded is violated. Hence, we have, for some $x_{I}, y_{I}, z_{I} \in X_{I}$ and some $a_{J}, b_{J}, c_{J} \in X_{J}$, $(x_{I}, a_{J}) \in {\mathcal {A}}$, $(y_{I}, b_{J}) \in {\mathcal {A}}$, $(z_{I}, c_{J}) \in {\mathcal {A}}$, $(x_{I}, b_{J}) \in {\mathcal {U}}$, $(z_{I}, a_{J}) \in {\mathcal {U}}$. This implies $c_{J} {\succ }_{J} a_{J} {\succ }_{J} b_{J}$, while $b_{J}$ is not a veto level. This is equivalent to saying that $J$-s-3v-graded is violated, as shown in Lemma 3. $\square$

4.2.3 $I$-s-2-graded

Definition 8

We say that $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ is strongly 2-graded on I (condition $I$-s-2-graded) if

$$\begin{aligned} \left. \begin{array}{c} \left( x_{I}, a_{-I}\right) \in {\mathcal {A}}\\ \text{ and }\\ \left( y_{I}, b_{-I}\right) \in {\mathcal {A}}\\ \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} \left( x_{I}, b_{-I}\right) \in {\mathcal {A}}\\ \text{ or }\\ \left( z_{I}, a_{-I}\right) \in {\mathcal {A}}\end{array} \right. \qquad \qquad \quad ({I {\text {-s-2-graded}}}) \end{aligned}$$

for all $x_{I}, y_{I}, z_{I} \in X_{I}$ and all $a_{-I}, b_{-I} \in X_{-I}$.

The above condition is apparently new. It generalizes condition $i$-s-2-graded to subsets of attributes. The interpretation of this condition is exactly similar to that of condition $i$-s-2-graded. When $I$-s-2-graded holds, the relation ${\succsim }_{I}$ is a weak order that can have at most two equivalence classes.

Remark 5

Following the analysis in Bouyssou and Marchant (2007a), it is easy to factorize Condition $I$-s-2-graded so as to make $I\text {-linear}$ appear explicitly. This factorization will not be used in the present paper.

We leave to the reader the simple proof of the following two lemmas.

Lemma 5

Condition $I$-s-2-graded implies Condition $I$-s-3v-graded and, hence, $I$-linear.

Lemma 6

A partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ satisfies $I$-s-2-graded iff ${\succsim }_{I}$ is a weak order with at most two equivalence classes.

Remark 6

Let us notice here that Lemma 4 does not hold when $I$-s-3v-graded is replaced with $I$-s-2-graded. It is easy to build examples such that $I$-s-2-graded holds but $J$-s-2-graded fails while $J$-s-3v-graded holds.

4.2.4 $I$-s-conj

Definition 9

We say that $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ is I-strongly-conjunctive (condition $I$-s-conj) if

$$\begin{aligned} \left. \begin{array}{c} \left( x_{i}, z_{J}, a_{-I}\right) \in {\mathcal {A}}\\ \text{ and }\\ \left( y_{i}, w_{J}, a_{-I}\right) \in {\mathcal {A}}\\ \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} \left( y_{i}, z_{J}, a_{-I}\right) \in {\mathcal {A}}\\ \text{ and }\\ \left( x_{i}, w_{J}, a_{-I}\right) \in {\mathcal {A}}\\ \end{array} \right. \qquad \qquad \qquad \qquad ({I {\text {-s-conj}}}) \end{aligned}$$

for all $i \in I$ (and defining $J = I \setminus \{i\}$), for all $x_{i}, y_{i} \in X_{i}$, all $z_{J}, w_{J} \in X_{J}$, and all $a_{-I} \in X_{-I}$.

The above condition is apparently new. It uses condition $i$-s$^{*}$-conj on the attributes $i \in I$ keeping everything fixed for the attributes outside I. Notice that Condition $N$-s-conj is nothing but condition $i$-s$^{*}$-conj, for all $i \in N$, as defined above.

4.3 Main result

Theorem 1 will use conditions $I$-s-3v-graded, $I$-s-conj and $J$-s-conj for a given partition I, J of $N$. The logic of the proof will be as follows. First we show that veto effects on I only occur if there is a veto effect on $i \in I$. Restricting our attention to the case in which there are no veto effects, we show that the aggregation within the attributes in I is conjunctive. The same is true for the attributes in J. Hence, it remains to study how the aggregation of the attributes in I and J is performed. This is easily done.

Our main result is as follows.

Theorem 1

Let $X= \prod _{i=1}^{n} X_{i}$ be a finite set and $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ be a twofold partition of $X$. The partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ has a representation in Model $(E^{u^{*}}_{\le 2})$ iff there is a partition I, J of $N$ such that $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ satisfies $I$-s-3v-graded, $I$-s-conj and $J$-s-conj.

The proof appears below in 4.6 and 4.7, after some preparatory lemmas in 4.4 and 4.5 . The independence of our conditions is discussed in 4.8. Notice that our conditions involve an existential statement (“there is a partition I, J of $N$ such that”). Hence, they may not be easy to test. This is discussed below in 4.9.

4.4 Lemmas with $I$-s-3v-graded and $I$-s-conj

In all lemmas in 4.4 and 4.5 , I is a proper nonempty subset of $N$. The common premise of all lemmas in 4.4 is that Conditions $I$-s-3v-graded and $I$-s-conj hold.

Lemma 7

If $i \in I$, the partition is $i$-linear.

Proof

Take $J = I \setminus \{i\}$. Suppose that $(x_{i}, a_{J}, a_{-I}) \in {\mathcal {A}}$, $(y_{i}, b_{J}, b_{-I}) \in {\mathcal {A}}$, $(y_{i}, a_{J}, a_{-I}) \in {\mathcal {U}}$, $(x_{i}, b_{J}, b_{-I}) \in {\mathcal {U}}$, violating i-linearity. Since $I$-s-3v-graded implies $I$-linear, we have either $(x_{i}, a_{J}) {\succsim }_{I} (y_{i}, b_{J})$ or $(y_{i}, b_{J}) {\succsim }_{I} (x_{i}, a_{J})$.

In the first case, $(y_{i}, b_{J}, b_{-I}) \in {\mathcal {A}}$ implies $(x_{i}, a_{J}, b_{-I}) \in {\mathcal {A}}$. We now apply $I$-s-conj to the pair $(y_{i}, b_{J}, b_{-I}) \in {\mathcal {A}}$ and $(x_{i}, a_{J}, b_{-I}) \in {\mathcal {A}}$. This implies $(x_{i}, b_{J}, b_{-I}) \in {\mathcal {A}}$, a contradiction.

In the second case, $(x_{i}, a_{J}, a_{-I}) \in {\mathcal {A}}$ implies $(y_{i}, b_{J}, a_{-I}) \in {\mathcal {A}}$. We now apply $I$-s-conj to the pair $(y_{i}, b_{J}, a_{-I}) \in {\mathcal {A}}$ and $(x_{i}, a_{J}, a_{-I}) \in {\mathcal {A}}$. This implies $(y_{i}, a_{J}, a_{-I}) \in {\mathcal {A}}$, a contradiction. $\square$

Lemma 8

If $i \in I$, the partition satisfies $i$-s-3v-graded.

Proof

Take $J = I \setminus \{i\}$. Suppose that $(x_{i}, a_{J}, a_{-I}) \in {\mathcal {A}}$, $(y_{i}, b_{J}, b_{-I}) \in {\mathcal {A}}$, $(z_{i}, c_{J}, c_{-I}) \in {\mathcal {A}}$, $(x_{i}, b_{J}, b_{-I}) \in {\mathcal {U}}$, and $(z_{i}, a_{J}, a_{-I}) \in {\mathcal {U}}$, violating $i$-s-3v-graded. Using $I$-s-3v-graded, $(x_{i}, a_{J}, a_{-I}) \in {\mathcal {A}}$, $(y_{i}, b_{J}, b_{-I}) \in {\mathcal {A}}$, $(z_{i}, c_{J}, c_{-I}) \in {\mathcal {A}}$, imply $(x_{i}, a_{J},b_{-I}) \in {\mathcal {A}}$, or $(z_{i}, c_{J}, a_{-I}) \in {\mathcal {A}}$.

If $(x_{i}, a_{J}, b_{-I}) \in {\mathcal {A}}$, $(y_{i}, b_{J}, b_{-I}) \in {\mathcal {A}}$ together with $I$-s-conj imply $(x_{i}, b_{J}, b_{-I}) \in {\mathcal {A}}$, a contradiction. If $(z_{i}, c_{J}, a_{-I}) \in {\mathcal {A}}$, $(x_{i}, a_{J}, a_{-I}) \in {\mathcal {A}}$ together with $I$-s-conj imply $(z_{i}, a_{J}, a_{-I}) \in {\mathcal {A}}$, a contradiction. $\square$

Since $I$-s-3v-graded holds, we know that ${\succsim }_{I}$ has at most three equivalence classes. Its last equivalence class may correspond to a veto situation. Since $i$-s-3v-graded holds, for all $i \in I$, the same is true for ${\succsim }_{i}$. Let us now show that the class of ${\succsim }_{I}$ corresponding to a veto is exclusively composed of all elements $c_{I}$, for which we know that, for some $i \in I$, $c_{i}$ corresponds to a veto.

Let $T_{I} = \lbrace x_{I} \in X_{I}: (x_{I}, a_{-I}) \in {\mathcal {U}}, \text { for all } a_{-I}\in X_{-I} \rbrace$. Remember (see Definition 5) that we have $Z_{i} = \lbrace x_{i} \in X_{i}: (x_{i}, a_{-i}) \in {\mathcal {U}}, \text { for all } a_{-i}\in X_{-i} \rbrace$.

Lemma 9

$x_{I} \in T_{I} \iff x_{i} \in Z_{i}$, for some $i \in I$.

Proof

[$\Leftarrow$]. Take $J = I \setminus \{i\}$. It is clear that if $x_{i} \in Z_{i}$, then $(x_{i}, a_{J}) \in T_{I}$, for all $a_{J} \in X_{J}$.

[$\Rightarrow$]. Suppose that $x_{I} \in T_{I}$ and, for all $i \in I$, $x_{i} \notin Z_{i}$, i.e., $(x_{i}, a_{J}, a_{-I}) \in {\mathcal {A}}$, for some $a_{J} \in X_{J}, a_{-I} \in X_{-I}$.

Let us sketch the proof in the particular case in which $I= \{i,j,k\}$. By construction, we know that $(x_{i}, \alpha _{j}, \alpha _{k}, \alpha _{-I}) \in {\mathcal {A}}$, $(\beta _{i}, x_{j}, \beta _{k}, \beta _{-I}) \in {\mathcal {A}}$, $(\gamma _{i}, \gamma _{j}, x_{k},$ $\gamma _{-I}) \in {\mathcal {A}}$, for some $\beta _{i}, \gamma _{i} \in X_{i}$, some $\alpha _{j}, \gamma _{j} \in X_{j}$ and some $\alpha _{k}, \beta _{k}$ $\in X_{k}$.

Because $(x_{i}, \alpha _{j}, \alpha _{k}, \alpha _{-I}) \in {\mathcal {A}}$ and $(\beta _{i}, x_{j}, \beta _{k}, \beta _{-I}) \in {\mathcal {A}}$, using $I$-linear, we obtain either $(x_{i}, \alpha _{j}, \alpha _{k}, \beta _{-I}) \in {\mathcal {A}}$ or $(\beta _{i}, x_{j}, \beta _{k}, \alpha _{-I}) \in {\mathcal {A}}$.

• 1. Suppose first that $(x_{i}, \alpha _{j}, \alpha _{k}, \beta _{-I}) \in {\mathcal {A}}$. Using $I$-s-conj and $(\beta _{i}, x_{j}, \beta _{k}, \beta _{-I}) \in {\mathcal {A}}$, we obtain $(x_{i}, x_{j}, \alpha _{k},$ $\beta _{-I}) \in {\mathcal {A}}$. Using $(x_{i}, x_{j}, \alpha _{k}, \beta _{-I}) \in {\mathcal {A}}$ and $(\gamma _{i}, \gamma _{j},$ $x_{k}, \gamma _{-I}) \in {\mathcal {A}}$, I-linearity implies either $(x_{i}, x_{j}, \alpha _{k},$ $\gamma _{-I}) \in {\mathcal {A}}$ or $(\gamma _{i}, \gamma _{j},$ $x_{k},$ $\beta _{-I}) \in {\mathcal {A}}$.

  If $(x_{i}, x_{j}, \alpha _{k}, \gamma _{-I}) \in {\mathcal {A}}$, using $I$-s-conj and $(\gamma _{i}, \gamma _{j}, x_{k}, \gamma _{-I}) \in {\mathcal {A}}$, we obtain $(x_{i}, x_{j}, x_{k}, \gamma _{-I}) \in {\mathcal {A}}$, violating the fact that $x_{I} \in T_{I}$.

  If $(\gamma _{i}, \gamma _{j}, x_{k}, \beta _{-I}) \in {\mathcal {A}}$, using $I$-s-conj and $(x_{i}, x_{j}, \alpha _{k}, \beta _{-I}) \in {\mathcal {A}}$, we obtain $(x_{i}, x_{j}, x_{k}, \beta _{-I}) \in {\mathcal {A}}$, violating the fact that $x_{I} \in T_{I}$.

• 2. Suppose now that $(\beta _{i}, x_{j}, \beta _{k}, \alpha _{-I}) \in {\mathcal {A}}$. Using $I$-s-conj and $(x_{i}, \alpha _{j}, \alpha _{k}, \alpha _{-I}) \in {\mathcal {A}}$, we obtain $(x_{i}, x_{j}, \beta _{k}, \alpha _{-I}) \in {\mathcal {A}}$. Using $(x_{i}, x_{j}, \beta _{k}, \alpha _{-I}) \in {\mathcal {A}}$ and $(\gamma _{i}, \gamma _{j},$ $x_{k}, \gamma _{-I}) \in {\mathcal {A}}$, I-linearity implies either $(x_{i}, x_{j}, \beta _{k},$ $\gamma _{-I}) \in {\mathcal {A}}$ or $(\gamma _{i}, \gamma _{j},$ $x_{k},$ $\alpha _{-I}) \in {\mathcal {A}}$.

  If $(x_{i}, x_{j}, \beta _{k}, \gamma _{-I}) \in {\mathcal {A}}$, using $I$-s-conj and $(\gamma _{i}, \gamma _{j}, x_{k}, \gamma _{-I}) \in {\mathcal {A}}$, we obtain $(x_{i}, x_{j}, x_{k}, \gamma _{-I}) \in {\mathcal {A}}$, violating the fact that $x_{I} \in T_{I}$.

  If $(\gamma _{i}, \gamma _{j}, x_{k}, \alpha _{-I}) \in {\mathcal {A}}$, using $I$-s-conj and $(x_{i}, x_{j}, \beta _{k}, \alpha _{-I}) \in {\mathcal {A}}$, we obtain $(x_{i}, x_{j}, x_{k}, \alpha _{-I}) \in {\mathcal {A}}$, violating the fact that $x_{I} \in T_{I}$.

The extension to the general case proceeds by an induction argument on the cardinality of I. It uses the above reasoning based on repeated applications of $I$-s-conj and $I$-linear, which is implied by $I$-s-3v-graded. We skip the cumbersome details. $\square$

The following remark shows, using the above lemma, that when condition $I$-s-3v-graded holds, we can define a subset of $X_{I}$ on which condition $I$-s-2-graded holds.

Remark 7

Let $S_{I} = X_{I} \setminus T_{I}$. It follows from the above lemma that, using notation introduced in Definition 5, we have:

$$\begin{aligned} S_{I} = \prod _{i \in I} Y_{i}. \end{aligned}$$

It is easy to check that the relation ${\succsim }_{I}$ on $S_{I}$ is a weak order having at most two indifference classes. Indeed, we know that ${\succsim }_{I}$ can have at most three equivalence classes and, by construction, $x_{I} \in S_{I}$ implies that $(x_{I}, a_{-I}) \in {\mathcal {A}}$, for some $a_{-I}\in X_{-I}$, so that $x_{I}$ cannot belong to the third equivalence class, corresponding to a veto.

Our next result generalizes Lemma 8 to subsets of attributes included in I.

Lemma 10

Let $J \subseteq I$. Condition $J$-s-3v-graded holds.

Proof

Suppose that $I$-s-3v-graded and $I$-s-conj hold. Let J, K be a partition of I. Suppose that $J$-s-3v-graded is violated, so that $(x_{J}, a_{K}, a_{-I}) \in {\mathcal {A}}$, $(y_{J}, b_{K}, b_{-I}) \in {\mathcal {A}}$, and $(z_{J}, c_{K}, c_{-I}) \in {\mathcal {A}}$, while $(x_{J}, b_{K}, b_{-I}) \in {\mathcal {U}}$ and $(z_{J}, a_{K}, a_{-I}) \in {\mathcal {U}}$.

Using $I$-s-3v-graded, $(x_{J}, a_{K}, a_{-I}) \in {\mathcal {A}}$, $(y_{J}, b_{K}, b_{-I}) \in {\mathcal {A}}$, and $(z_{J}, c_{K}, c_{-I}) \in {\mathcal {A}}$, imply $(x_{J}, a_{K}, b_{-I}) \in {\mathcal {A}}$ or $(z_{J}, c_{K}, a_{-I}) \in {\mathcal {A}}$.

Suppose first that $(x_{J}, a_{K}, b_{-I}) \in {\mathcal {A}}$. Using $(y_{J}, b_{K}, b_{-I}) \in {\mathcal {A}}$ and $(x_{J}, a_{K},$ $b_{-I}) \in {\mathcal {A}}$, repeated uses of $I$-s-conj imply $(x_{J}, b_{K}, b_{-I}) \in {\mathcal {A}}$, a contradiction.

Suppose now that $(z_{J}, c_{K}, a_{-I}) \in {\mathcal {A}}$. Using $(x_{J}, a_{K}, a_{-I}) \in {\mathcal {A}}$ and $(z_{J}, c_{K},$ $a_{-I}) \in {\mathcal {A}}$ repeated uses of $I$-s-conj imply $(z_{J}, a_{K}, a_{-I}) \in {\mathcal {A}}$, a contradiction. $\square$

Remark 8

The above lemma implies that, for all $J \subseteq I$, Condition J-linear holds. Hence, under the hypothesis that $I$-s-3v-graded and $I$-s-conj hold, we know that for all partition J, K of I, J-linearity and K-linearity hold, so that both ${\succsim }_{J}$ and ${\succsim }_{K}$ are weak orders. It is easy to check that these three weak orders combine as expected, e.g.,

$$\begin{aligned} \begin{aligned} \left( x_{K}, x_{J}\right) {\succsim }_{I} y_{I} \text { and } z_{K} {\succsim }_{K} x_{K}&\Rightarrow \left( z_{K}, x_{J}\right) {\succsim }_{I} y_{I},\\ \left( x_{K}, x_{J}\right) {\sim }_{I} y_{I} \text { and } z_{K} {\sim }_{K} x_{K}&\Rightarrow \left( z_{K}, x_{J}\right) {\sim }_{I} y_{I},\\ \left( x_{K}, x_{J}\right) {\succ }_{I} y_{I} \text { and } z_{K} {\succsim }_{K} x_{K}&\Rightarrow \left( z_{K}, x_{J}\right) {\succ }_{I} y_{I}. \end{aligned} \end{aligned}$$

We will use such implications freely in what follows.

The proof of these implications is easy. For instance, suppose that $(x_{K}, x_{J}) {\succsim }_{I} y_{I}$, so that, for all $a_{-I} \in X_{-I}$, $(y_{I}, a_{-I}) \in {\mathcal {A}}$ implies $(x_{J}, x_{K}, a_{-I}) \in {\mathcal {A}}$. Since $z_{K} {\succsim }_{K} x_{K}$, $(x_{K}, x_{J}, a_{-I}) \in {\mathcal {A}}$ implies $(z_{K}, z_{J}, a_{-I}) \in {\mathcal {A}}$, so that $(z_{K}, x_{J}) {\succsim }_{I} y_{I}$.

4.5 Lemmas with $I$-s-2-graded and $I$-s-conj

The common premise of all lemmas in 4.5 is that Conditions $I$-s-2-graded and $I$-s-conj hold.

Lemma 11

For all $J \subseteq I$, ${\succsim }_{J}$ is a weak order that has at most two equivalence classes, so that $J$-s-2-graded holds.

Proof

Suppose that $I$-s-2-graded and $I$-s-conj hold. Let J, K be a partition of I. Suppose that $x_{J} {\succ }_{J} y_{J}$ and $y_{J} {\succ }_{J} z_{J}$.

Hence, there are $a_{K}, b_{K} \in X_{K}$ and $a_{-I}, b_{-I} \in X_{-I}$ such that $(x_{J}, a_{K}, a_{-I}) \in {\mathcal {A}}$, $(y_{J}, a_{K}, a_{-I}) \in {\mathcal {U}}$, and $(y_{J}, b_{K}, b_{-I}) \in {\mathcal {A}}$, $(z_{J}, b_{K}, b_{-I}) \in {\mathcal {U}}$.

Because $I$-s-2-graded holds, we know that ${\succsim }_{I}$ has at most two equivalence classes. Hence, we know that both $(x_{J}, a_{K})$ and $(y_{J}, b_{K})$ belong to the first equivalence class of ${\succsim }_{I}$. Hence, we have $(x_{J}, a_{K}) {\sim }_{I} (y_{J}, b_{K})$, so that we have $(y_{J}, b_{K}, a_{-I}) \in {\mathcal {A}}$ and $(x_{J}, a_{K}, b_{-I}) \in {\mathcal {A}}$. Repeated uses of $I$-s-conj allows to permute $a_{K}$ and $b_{K}$ between the expressions $(y_{J}, b_{K}, a_{-I}) \in {\mathcal {A}}$ and $(x_{J}, a_{K}, b_{-I}) \in {\mathcal {A}}$. This leads to $(y_{J}, a_{K}, a_{-I}) \in {\mathcal {A}}$, a contradiction. $\square$

The next lemma is crucial. It shows how the information is aggregated with the attributes in I.

Lemma 12

Let $x_{I} \in X_{I}$. Then $x_{I}$ belongs to the first equivalence class of ${\succsim }_{I}$ iff $x_{i}$ belongs to the first equivalence class of ${\succsim }_{i}$, for all $i \in I$.

Proof

Proving that if $x_{i}$ belongs to the first equivalence class of ${\succsim }_{i}$, for all $i \in I$, then $x_{I}$ belongs to the first equivalence class of ${\succsim }_{I}$ is easy. Indeed, with $i \in I$ and $J = I \setminus \{i\}$, if $x_{i} {\succsim }_{i}y_{i}$ then we have $(x_{i}, z_{J}) {\succsim }_{I} (y_{i}, z_{J})$, for all $z_{J} \in X_{J}$. Let us prove the reverse implication.

Let $i \in I$ and $J = I \setminus \{i\}$. In the rest of this proof, we use the convention that on each $i \in N$, we have $a_{i} {\succ }_{i}b_{i}$. It is clear that $(a_{i}, a_{J})$ is a top element (i.e., an element belonging to the first equivalence class) of ${\succsim }_{I}$ and that $(b_{i}, b_{J})$ is a bottom element (i.e., an element belonging to the second equivalence class) of ${\succsim }_{I}$. This follows from the fact that ${\succsim }_{I}$ has two equivalence classes and the monotonicity relations noted in Remark 8.

Suppose, in contradiction with the thesis, that $(a_{i}, a_{J}) {\sim }_{I} (b_{i}, a_{J})$, for some $i \in I$ and letting $J = I \setminus \{i\}$.

Since $a_{i} {\succ }_{i}b_{i}$, we have $(a_{i}, x_{J}, x_{-I}) \in {\mathcal {A}}$ and $(b_{i}, x_{J}, x_{-I}) \in {\mathcal {U}}$, for some $x_{J} \in X_{J}$ and some $x_{-I} \in X_{-I}$. This implies $(a_{i}, x_{J}) {\succ }_{I} (b_{i}, x_{J})$.

It is impossible that $x_{J} {\sim }_{J} a_{J}$ because we have supposed that $(a_{i}, a_{J}) {\sim }_{I} (b_{i}, a_{J})$. Hence, we know that $x_{J} {\sim }_{J} b_{J}$, so that $(a_{i}, b_{J}, x_{-I}) \in {\mathcal {A}}$ and $(b_{i}, b_{J}, x_{-I}) \in {\mathcal {U}}$.

Because $a_{J} {\succ }_{J} b_{J}$, we know that $(y_{i}, a_{J}, y_{-I}) \in {\mathcal {A}}$ and $(y_{i}, b_{J}, y_{-I}) \in {\mathcal {U}}$, for some $y_{J} \in X_{J}$ and some $y_{i} \in X_{i}$. This implies that $(y_{i}, a_{J})$ is a top element of ${\succsim }_{I}$, so that $(y_{i}, a_{J}) {\sim }_{I} (b_{i}, a_{J})$. By hypothesis, $(b_{i}, b_{J})$ is a bottom element. Hence, we obtain $(b_{i}, a_{J}, y_{-I}) \in {\mathcal {A}}$ and $(b_{i}, b_{J}, y_{-I}) \in {\mathcal {U}}$.

Since we have $(b_{i}, a_{J}, y_{-I}) \in {\mathcal {A}}$ and $(a_{i}, b_{J}, x_{-I}) \in {\mathcal {A}}$, I-linearity implies $(a_{i}, b_{J}, y_{-I}) \in {\mathcal {A}}$ or $(b_{i}, a_{J}, x_{-I}) \in {\mathcal {A}}$.

It is impossible to have $(a_{i}, b_{J}, y_{-I}) \in {\mathcal {A}}$ since $I$-s-conj, together with $(b_{i}, a_{J}, y_{-I}) \in {\mathcal {A}}$, imply $(b_{i}, b_{J}, y_{-I}) \in {\mathcal {A}}$, a contradiction.

Similarly, it is impossible to have $(b_{i}, a_{J}, x_{-I}) \in {\mathcal {A}}$, since $I$-s-conj, together with $(a_{i}, b_{J}, x_{-I}) \in {\mathcal {A}}$ imply $(b_{i}, b_{J}, x_{-I}) \in {\mathcal {A}}$, a contradiction. $\square$

Using Lemma 12, we know that if $I$-s-2-graded and $I$-s-conj hold, ${\succsim }_{I}$ has two equivalence classes, ${\succsim }_{i}$ has two equivalence classes, for all $i \in I$, and that the aggregation of ${\succsim }_{i}$ into ${\succsim }_{I}$ is conjunctive.

4.6 Proof of Theorem 1: necessity

Lemma 13

Suppose that $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ has a representation in Model $(E^{u}_{1})$. Let I, J be any partition of $N$. Then $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ satisfies Conditions $I$-s-3v-graded, $I$-s-conj, and $J$-s-conj.

Proof

By hypothesis, we know that $x \in \AA \iff [x_{i} {\succsim }_{i}p_{i}$, for all $i \in N]$.

Suppose that $(x_{I}, a_{-I}) \in {\mathcal {A}}$, $(y_{I}, b_{-I}) \in {\mathcal {A}}$, $(z_{I}, c_{-I}) \in {\mathcal {A}}$, while $(x_{I}, b_{-I}) \in {\mathcal {U}}$ and $(z_{I}, a_{-I}) \in {\mathcal {U}}$. By construction, $(x_{I}, b_{-I}) \in {\mathcal {U}}$ implies that either $p_{i} {\succ }_{i}x_{i}$, for some $i \in I$ or $p_{j} {\succ }_{j} b_{j}$, for some $j \notin I$. This implies either $(x_{I}, a_{-I}) \in {\mathcal {U}}$ or $(y_{I}, b_{-I}) \in {\mathcal {U}}$, a contradiction. Hence, $I$-s-3v-graded holds.

Suppose now that $(x_{i}, z_{J}, a_{-I}) \in {\mathcal {A}}$, $(y_{i}, w_{J}, a_{-I}) \in {\mathcal {A}}$, and $(y_{i}, z_{J}, a_{-I}) \in {\mathcal {U}}$ (the case in which $(x_{i}, w_{J}, a_{-I}) \in {\mathcal {U}}$ is dealt with similarly). Now, $(x_{i}, z_{J}, a_{-I}) \in {\mathcal {A}}$, and $(y_{i}, z_{J}, a_{-I}) \in {\mathcal {U}}$ imply that $x_{i} {\succsim }_{i}p_{i}$, while $p_{i} {\succ }_{i}y_{i}$. But this contradicts $(y_{i}, w_{J}, a_{-I}) \in {\mathcal {A}}$. Hence, $I$-s-conj holds. A similar proof shows that $J$-s-conj holds. $\square$

The following lemma makes use of the sets $N^{p}$ and $N^{q}$ partitioning $N$ that were defined in Remark 2, at the end of Sect. 4.1.

Lemma 14

Suppose that $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ has a representation in Model $(E^{u^{*}}_{2})$. Let I, J be the partition of $N$ induced by the two profiles p and q, i.e., $I = N^{p}$ and $J = N^{q}$. Then $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ satisfies $I$-s-3v-graded, $I$-s-conj, and $J$-s-conj.

Proof

Suppose that $(x_{I}, a_{J}) \in {\mathcal {A}}$, $(y_{I}, b_{J}) \in {\mathcal {A}}$, $(z_{I}, c_{J}) \in {\mathcal {A}}$, while $(x_{I}, b_{J}) \in {\mathcal {U}}$ and $(z_{I}, a_{J}) \in {\mathcal {U}}$. By hypothesis, we know that $x_{i} {\succsim }_{i} q_{i}$, $y_{i} {\succsim }_{i} q_{i}$ and $z_{i} {\succsim }_{i} q_{i}$, for all $i \in I$. Similarly, we know that $a_{j} {\succsim }_{j} p_{j}$, $b_{j} {\succsim }_{j} p_{j}$ and $c_{j} {\succsim }_{j} p_{j}$, for all $j \in J$.

If $a_{j} {\succsim }_{j} q_{j}$, for all $j \in J$, this would imply $(z_{I}, a_{J}) \in {\mathcal {A}}$, a contradiction. Hence, it must be true that $x_{i} {\succsim }_{j} p_{i}$, for all $i \in I$. This contradicts the fact that $(x_{I}, b_{J}) \in {\mathcal {U}}$. Hence, $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ satisfies $I$-s-3v-graded.

Let $K = I \setminus \lbrace i \rbrace$ and suppose that $(x_{i}, z_{K}, a_{J}) \in {\mathcal {A}}$, $(y_{i}, w_{K}, a_{J}) \in {\mathcal {A}}$, together with either $(y_{i}, z_{K}, a_{J}) \in {\mathcal {U}}$, or $(x_{i}, w_{K}, a_{J}) \in {\mathcal {U}}$. By hypothesis, we know that $x_{i} {\succsim }_{i} q_{i}$ and $y_{i} {\succsim }_{i} q_{i}$. Moreover, $z_{k} {\succsim }_{k} q_{k}$ and $w_{k} {\succsim }_{k} q_{k}$, for all $k \in K$. Similarly, we know that $a_{j} {\succsim }_{j} p_{j}$, for all $j \in J$.

We have either $(y_{i}, z_{K}, a_{J}) \in {\mathcal {U}}$, or $(x_{i}, w_{K}, a_{J}) \in {\mathcal {U}}$. Suppose that $(y_{i}, z_{K}, a_{J}) \in {\mathcal {U}}$, the other case being similar. It is clearly impossible that $a_{j} {\succsim }_{j} q_{j}$, for all $j \in J$. Hence, we must have: $x_{i} {\succsim }_{i} p_{i}$, $y_{i} {\succsim }_{i} p_{i}$, $z_{k} {\succsim }_{k} p_{k}$ and $w_{k} {\succsim }_{k} p_{k}$, for all $k \in K$. This implies $(y_{i}, z_{K}, a_{J}) \in {\mathcal {A}}$ and $(x_{i}, w_{K}, a_{J}) \in {\mathcal {A}}$, a contradiction. Hence, $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ satisfies $I$-s-conj. A similar proof shows that $J$-s-conj holds. $\square$

4.7 Proof of Theorem 1: sufficiency

Suppose that there is a partition I, J of $N$ such that $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ satisfies $I$-s-3v-graded, $I$-s-conj and $J$-s-conj. Using Lemma 4, we know that $J$-s-3v-graded holds.

As above, define $Z_{i} = \lbrace x_{i} \in X_{i}: (x_{i}, a_{-i}) \in {\mathcal {U}}, \text { for all } a_{-i}\in X_{-i} \rbrace$, $Y_{i} = X_{i}\setminus Z_{i}$, $T_{I} = \lbrace x_{I} \in X_{I}: (x_{I}, a_{-I}) \in {\mathcal {U}}, \text { for all } a_{-I}\in X_{-I} \rbrace$ and $T_{J} = \lbrace x_{J} \in X_{J}: (x_{J}, a_{-J}) \in {\mathcal {U}}, \text { for all } a_{-J}\in X_{-J} \rbrace$. $S_{I} = X_{I}\setminus T_{I}$ and $S_{J} = X_{J}\setminus T_{J}$.

We know from Lemma 9 that $S_{I} = \prod _{i \in I} Y_{i}$ and $S_{J} = \prod _{j \in J} Y_{j}$. Consider the set $Y = \prod _{i=1}^{n}Y_{i}$ and let ${\mathcal {A}}' = \AA \cap Y$ and ${\mathcal {U}}' = {\mathcal {U}}\cap Y$.

By construction, Condition $I$-s-2-graded and $J$-s-2-graded hold for $\langle {\mathcal {A}}',{\mathcal {U}}'\rangle$. Let us show that $\langle {\mathcal {A}}',{\mathcal {U}}'\rangle$ has a representation in Model $(E^{u^{*}}_{\le 2})$, which will complete the proof.

Using Lemma 12, we know that both ${\succsim }_{I}$ and ${\succsim }_{J}$ are weak orders having at most two equivalence classes. Moreover, we know that $x_{I}$ belongs to the first equivalence class of ${\succsim }_{I}$ iff $x_{i}$ belongs to the first equivalence class of ${\succsim }_{i}$, for all $i \in I$, a similar conclusion holding for J. Our conventions imply that all attributes are influential for $\langle {\mathcal {A}}',{\mathcal {U}}'\rangle$.

We use the convention that on each $i \in N$, we have $a_{i} {\succ }_{i}b_{i}$.

There are two equivalence classes of elements in $X_{I}$ and two equivalence classes of elements in $X_{J}$. We know (see Lemma 12) that a top element (i.e., an element in the top equivalence class) of ${\succsim }_{I}$ (resp. ${\succsim }_{J}$) consists exclusively of top elements of ${\succsim }_{i}$, for all $i \in I$ (resp. $j \in J$). Hence, there are four cases to consider, using the convention that $a_{I}$ (resp. $b_{I}$) is a top element of ${\succsim }_{I}$, a similar convention holding for J.

• 1. $(a_{I}, a_{J}) \in {\mathcal {A}}'$, $(a_{I}, b_{J}) \in {\mathcal {A}}'$, $(b_{I}, a_{J}) \in {\mathcal {A}}'$, $(b_{I}, b_{J}) \in {\mathcal {U}}'$. This is exactly Model $(E^{u^{*}}_{2})$, with p (resp. q) consisting of any element in the first (resp. second) equivalence class of ${\succsim }_{i}$, for $i \in I$ and the second (resp. first) equivalence class of ${\succsim }_{j}$, for $j \in J$.

• 2. $(a_{I}, a_{J}) \in {\mathcal {A}}'$, $(a_{I}, b_{J}) \in {\mathcal {U}}'$, $(b_{I}, a_{J}) \in {\mathcal {U}}'$, $(b_{I}, b_{J}) \in {\mathcal {U}}'$. This is exactly Model $(E^{u}_{1})$, with p consisting of any element in the first equivalence class of each ${\succsim }_{i}$.

• 3. $(a_{I}, a_{J}) \in {\mathcal {A}}'$, $(a_{I}, b_{J}) \in {\mathcal {A}}'$, $(b_{I}, a_{J}) \in {\mathcal {U}}'$, $(b_{I}, b_{J}) \in {\mathcal {U}}'$. The attributes in J are not influential for $\langle {\mathcal {A}}',{\mathcal {U}}'\rangle$, which is impossible.

• 4. $(a_{I}, a_{J}) \in {\mathcal {A}}'$, $(a_{I}, b_{J}) \in {\mathcal {U}}'$, $(b_{I}, a_{J}) \in {\mathcal {A}}'$, $(b_{I}, b_{J}) \in {\mathcal {U}}'$. The attributes in I are not influential for $\langle {\mathcal {A}}',{\mathcal {U}}'\rangle$, which is impossible.

This completes the proof. $\square$

4.8 Independence of the axioms: examples

The following examples show that the three conditions used in Theorem 1 are independent.

Example 1

Let $N= \{1,2,3,4\}$ and $X_{i}= \{a, b\}$, for all $i \in N$. Consider the partition given below, abusing notation in an obvious way:

$$\begin{aligned} \begin{array}{cccccc} aaaa \in {\mathcal {A}}, &{} abaa \in {\mathcal {A}}, &{} baaa \in {\mathcal {A}}, &{} bbaa \in {\mathcal {A}},\\ aaab \in {\mathcal {A}}, &{} abab \in {\mathcal {A}}, &{} baab \in {\mathcal {U}}, &{} bbab \in {\mathcal {U}},\\ aaba \in {\mathcal {A}}, &{} abba \in {\mathcal {U}}, &{} baba \in {\mathcal {U}}, &{} bbba \in {\mathcal {U}},\\ aabb \in {\mathcal {A}}, &{} abbb \in {\mathcal {U}}, &{} babb \in {\mathcal {U}}, &{} bbbb \in {\mathcal {U}}. \end{array} \end{aligned}$$

It is easy to check that both $\{1,2\}$-s-conj and $\{3,4\}$-s-conj are satisfied. $\{1,2\}$-s-3v-graded (and, consequently, $\{3,4\}$-s-3v-graded) is violated since we have, using obvious notation, $aa {\succ }_{12} ab {\succ }_{12} [ba {\sim }_{12} bb]$, while $(b,b,a,a) \in {\mathcal {A}}$ (see Lemma 3).

Notice that this example also shows that we cannot replace in our characterization $I$-s-3v-graded by $i$-s-3v-graded, for all $i \in I$. Indeed, in the above example, $i$-s-3v-graded trivially holds, for all $i \in N$ (since each $X_{i}$ has only 2 elements).

The next example shows that $I$-s-3v-graded, $J$-s-3v-graded and $J$-s-conj do not imply $I$-s-conj. A similar example shows that the same conclusion holds, permuting the role of I and J.

Example 2

Let $N= \{1, 2, 3, 4, 5, 6\}$ and $X_{i} = \{a, b\}$, for all $i \in N$. Let $I = \{1, 2, 3\}$ and $J = \{4, 5, 6\}$. The partition $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ is such that $x \in {\mathcal {A}}$ iff $x_{j} = a$, for all $j \in J$ or $\left| \{i \in I ; x_{i} = a\} \right| \ge 2$.

It is clear that $J$-s-3v-graded holds: either an element of $X_{J}$ is a top element of ${\succsim }_{J}$ (being a top element of ${\succsim }_{j}$, for all $j \in J$) or not. The same is true for $I$-s-3v-graded: either an element of $X_{I}$ is a top element of ${\succsim }_{I}$ (being a top element of ${\succsim }_{i}$, for at least two elements $i \in I$) or not. Condition $J$-s-conj clearly holds. Condition $I$-s-conj is violated since $(a, a, b, b, b, b) \in {\mathcal {A}}$, $(a, b, a, b, b, b) \in {\mathcal {A}}$, while $(a, b, b, b, b, b) \in {\mathcal {U}}$.

4.9 Testing the conditions

The conditions used in Theorem 1 involve an existential clause: “there is a partition I, J of $N$ such that $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ satisfies $I$-s-3v-graded, $I$-s-conj and $J$-s-conj ”. Testing such conditions may not be easy. The following results aim at simplifying this test.

Lemma 15

Suppose that $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ satisfies $I$-s-conj and let $J = I \setminus \{i\}$. Then $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ satisfies $J$-s-conj.

Proof

$J$-s-conj applies to all pairs of alternatives that have common evaluations on $N\setminus J$. But since $J \subsetneq I$, having common evaluation on $N\setminus J$ implies having common evaluations on $N\setminus I$. Hence $I$-s-conj implies $J$-s-conj. $\square$

Lemma 16

Condition $\{i\}$-s-conj is trivial.

Proof

Condition $\{i\}$-s-conj says that $(x_{i}, a_{-i}) \in {\mathcal {A}}$ and $(y_{i}, a_{-i}) \in {\mathcal {A}}$ imply $(x_{i}, a_{-i}) \in {\mathcal {A}}$ and $(y_{i}, a_{-i}) \in {\mathcal {A}}$. $\square$

Lemma 17

Suppose that $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ has a representation in Model $(E^{u^{*}}_{2})$ with the two profiles p and q. Let $I = N^{p}$ and $J = N^{q}$. Let $j \in J$. Then $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ does not satisfy $I\cup \{j\}$-s-conj.

Proof

In this proof, we use the convention that on each $i \in N$, we have $a_{i} {\succ }_{i}b_{i} {\succ }_{i}c_{i}$. Consider the following two alternatives: $(a_{I}, b_{j}, b_{K})$ and $(b_{I}, a_{j}, a_{K})$, with $K = J \setminus \lbrace j \rbrace$. These two alternatives are in ${\mathcal {A}}$. Indeed, by construction, $(a_{I}, b_{j}, b_{K})$ dominates the profile p and $(b_{I}, a_{j}, a_{K})$ dominates the profile q. However, it is clear that $(b_{I}, b_{j}, a_{K}) \in {\mathcal {U}}$, since it does not dominate p and q. Hence, condition $I\cup \{j\}$-s-conj is violated. $\square$

Lemma 18

Suppose that $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ has a representation in Model $(E^{u^{*}}_{2})$ with the two profiles p and q. Let $I = N^{p}$ and $J = N^{q}$. Let $i \in I$ and $j \in J$. Then $\langle {\mathcal {A}},{\mathcal {U}}\rangle$ does not satisfy $\{i,j\}$-s-conj.

Proof

In this proof, we use the convention that on each $i \in N$, we have $a_{i} {\succ }_{i}b_{i} {\succ }_{i}c_{i}$. Consider the following two alternatives: $(a_{K}, a_{i}, b_{j}, a_{L})$ and $(a_{K}, b_{i}, a_{j}, a_{L})$, with $K = I \setminus \lbrace i \rbrace$ and $L = J \setminus \lbrace j \rbrace$. While both alternatives are in ${\mathcal {A}}$, it is clear that $(a_{K}, b_{j}, b_{i}, a_{L}) \in {\mathcal {U}}$, so that $\{i,j\}$-s-conj is violated. $\square$

Hence the test of $I$-s-conj could proceed as follows in a greedy-like way. Choose a pair $\{i,j\}$ of attributes such that $\{i,j\}$-s-conj holds. If such a pair does not exist, Model $(E^{u^{*}}_{\le 2})$ does not hold. If such a pair exists, try to iteratively enlarge it until this is no longer possible. This gives rise to a maximal set I such that $I$-s-conj holds. If $I = N$, then Model $(E^{u}_{1})$ applies (remember that $N$-s-conj implies $i$-s$^{*}$-conj, for all $i \in N$, see Proposition 4). Otherwise, test if $(N\setminus I)$-s-conj holds. If yes both conditions $I$-s-conj and $J$-s-conj are satisfied. Otherwise, Model $(E^{u^{*}}_{\le 2})$ does not hold (see Lemma 14).

A similar reasoning does not apply starting with the test of $I$-s-3v-graded. Hence, after having applied the above procedure, we test if $I$-s-3v-graded applies with the set I that we have obtained above. If not, Model $(E^{u^{*}}_{\le 2})$ does not hold. If yes, then the conditions of Theorem 1 are satisfied and Model $(E^{u^{*}}_{\le 2})$ holds.

5 Discussion

The original version of ELECTRE TRI-B uses one profile to delimit each category. It was characterized in a conjoint measurement framework in Bouyssou and Marchant (2007a, 2007b). The version of ELECTRE TRI-B that uses several profiles to delimit each category was characterized in the same framework in Bouyssou et al. (2021), when there is no restriction on the number of profiles that can be used. These characterizations show that there is huge gain of expressiveness when going from one profile to many profiles. Is that gain of expressiveness obtained with only a few profiles?

This paper wishes to be a first contribution to this research question. We have proposed, in a conjoint measurement framework, a characterization of the partitions that can be obtained using an outranking relation based on unanimity and no more than two profiles.

The results in this paper nevertheless suffer from two limitations. First, comparing Theorem 1 with Propositions 1 and 4 shows that the case of at most two limiting profiles is more complex than the case of many limiting profiles (Proposition 1) and the case of one profile (Proposition 4).

Second ⁴, it does not seem obvious to extend our results to cover the case of Model $(E^{c}_{\le 2})$. As shown below, the conditions we use seem to be specific to Model $(E^{u^{*}}_{\le 2})$ (or $(E^{u}_{\le 2})$). This is in contrast with the results in Bouyssou et al. (2021) in which restricting the attention to outranking relations based on unanimity is innocuous. Let us illustrate this point with the following example.

Example 3

The example has $n= 4$ and $X_{1} = X_{2} = X_{3} = X_{4} = \{0, 5, 10\}$. The partition is built in Model $(E^{c}_{\le 2})$ with the following two profiles (10, 10, 5, 5) and (5, 5, 10, 10) together with ${\mathcal {F}}= \lbrace \{2,3,4\}, \{1,3,4\}, \{1,2,4\}, \{1,2,3\}, \{1,2,3,4\} \rbrace$.

It is simple to check that on all attributes, we have $10 {\succ }_{i}5 {\succ }_{i}0$. For instance, we have with $i=1$,

$$\begin{aligned} \begin{aligned} (10, 0, 5, 10) \in {\mathcal {A}},&(5, 0, 5, 10) \in {\mathcal {U}},\\ (5, 0, 10, 10) \in {\mathcal {A}},&(0, 0, 10, 10) \in {\mathcal {U}}. \end{aligned} \end{aligned}$$

The two profiles partition the set of attributes into two subsets $I = \{1, 2\}$ and $J = \{3, 4\}$.

Observe that $i$-s-3v-graded does not hold since 0 is not a veto level. Indeed, we have, e.g., $(0, 5, 10, 10) \in {\mathcal {A}}$, $(10, 0, 5, 10) \in {\mathcal {A}}$, $(10, 5, 0, 10) \in {\mathcal {A}}$, and $(10, 5, 10, 0) \in {\mathcal {A}}$.

On $I = \{1, 2\}$, the partition is not $I$-s-3v-graded. Indeed, we have, using obvious notation,

$$\begin{aligned} (10,10) {\succ }_{12} [(10,5), (5,10)] {\succ }_{12} (5,5) {\succ }_{12} [(5,0), (0,5)] {\succ }_{12} (0,0). \end{aligned}$$

Indeed, we have

$$\begin{aligned} \begin{aligned} (10, 10, 5, 0) \in {\mathcal {A}},&(10, 5, 5, 0) \in {\mathcal {U}},\\ (10, 5, 5, 5) \in {\mathcal {A}},&( 5, 5, 5, 5) \in {\mathcal {U}},\\ ( 5, 5, 10, 0) \in {\mathcal {A}},&( 5, 0, 10, 0) \in {\mathcal {U}},\\ ( 5, 0, 10, 10) \in {\mathcal {A}},&( 0, 0, 10, 10) \in {\mathcal {U}}. \end{aligned} \end{aligned}$$

It is simple to find similar examples for J.

Finally, it is clear that $I$-s-conj does not hold. We have, e.g., $(10, 0, 5, 10) \in {\mathcal {A}}$ and $( 0, 10, 5, 10) \in {\mathcal {A}}$, while $( 0, 0, 5, 10) \in {\mathcal {U}}$. It is simple to find similar examples for J.

This shows that the axioms used for the characterization of Model $(E^{u^{*}}_{\le 2})$ do not hold with $(E^{c}_{\le 2})$, i.e., when we have two profiles but ${\mathcal {F}}\ne \{N\}$.

Hence, we do not have a complete answer to the research question that was at the origin of our work, i.e., the study of the gain in expressiveness brought by increasing the size of the set of profiles in ETRI-nB. We nevertheless think that this question is important and deserves further study. Our results show that it is somewhat unlikely that a purely axiomatic investigation will allow us to obtain clear answers to this research question. Hence, this is also a plea to combine axiomatic work with other types of work, e.g., based on computer simulation.