A theoretical look at Electre Tri-nB and related sorting models

We often abbreviate Electre Tri as ETri in what follows.

Let us also mention that Fernández et al. (2017) is the last paper on Electre methods published by Bernard Roy, the founding father of Electre methods, before he passed away at the end of 2017.

For the sake of simplicity, the thresholds \(qt_i, pt_i\) and \(vt_i\) are taken as constant. Nothing in the sequel depends on this option. They could be considered as variable provided appropriate conditions are enforced, actually ensuring that the corresponding weak preference, preference and veto relations form an homogenous chain of semiorders (see Roy and Bouyssou 1993, p. 56 and pp. 140–141 for details).

The (weak) dominance relation \(\ge \) is a reflexive and transitive relation on the set of alternatives, that is defined as follows: \(x \ge y\) if \(g_i(x) \ge _i g_i(y)\), for all i. This is the relation denoted \(\Delta _F\) by Roy and Bouyssou (1993, p. 61), F referring to a family of criteria.

In fact our framework allows us to deal with some infinite sets of objects: all that is really required is that the set of equivalence classes of each set \(X_{i}\) under the equivalence \(\sim _{i}\) is finite, see below.

Note that, in contrast with Sect. 2, the sets \(X_i\) are not necessarily sets of real numbers. They also need not be the range of a function \(g_i\) evaluating the alternatives w.r.t. criterion i. The set \(X_i\) can be any finite set, not necessarily ordered a priori.

We use a standard vocabulary for binary relations. For the convenience of the reader, all terms that are used in the main text are defined in Appendix A, given as supplementary material. See also, e.g.,  Aleskerov et al. (2007), Doignon et al. (1988), Pirlot and Vincke (1992), Roubens and Vincke (1985).

In Model (D1), notice that we could have chosen to replace the strict inequality by a nonstrict one. The two versions of the model are equivalent, as shown in Bouyssou and Marchant (2007a)[Rem. 8, p. 222]. The same is true for Model (D2).

When \(X\) is finite, it is clear that the variant of Model (Add) in which the strict inequality is replaced by a nonstrict one is equivalent to Model (Add).

We omit details and the reader is invited to check this example using, e.g.,  his/her favorite spreadsheet software.

With such models, even with one limiting profile, the number of minimally acceptable alternatives (i.e.,  the number of limiting profiles in the equivalent unanimous model) can be large. In the simplest case of ETri-nB-I-pc with one limiting profile and no veto, a minimally acceptable alternative takes the values of the limiting profile minus the indifference threshold \(qt_i\) on a minimal winning coalition of criteria and the minimal value in \(X_i\) on all other criteria. If the model is such that a coalition is winning whenever it contains at least n/2 criteria (this is obtained by setting all criteria weights to 1/n and the cutting level \(\lambda \) to 1/2), then the number of minimal winning coalitions is maximal and is equal to the Sperner number \(n\atopwithdelims ()\lceil n/2\rceil \) (see, e.g.,  Caspard et al. 2012, pp. 116-118). Therefore, for such a model, the maximal number of minimally acceptable alternatives is equal to this number.

Incidentally, we came across the recent paper by Silva et al. (2021) in which the decision rule approach (DRSA) is applied to the rating of sovereign risk; the results are then compared with those obtained using an additive model and MR-Sort. Unfortunately, the dataset involved is a small one (36 countries).

In Bouyssou et al. (2021b), we give the proof of a result that has already appeared in the grey literature but for which no proof was available. It states that if the chain on \(X_{i}\) has \(m_{i}\) elements, the maximal size of an antichain in \(X= \prod _{i=1}^{n} X_{i}\) partially ordered by \(\succsim \) iswhere \(m_{I} = \sum _{i \in I} m_{i}\) andThe reader will check that this number grows fast with the vector \((m_{i})_{i\in N}\).