Multiple criteria sorting models and methods—Part I: survey of the literature

Abstract

Multiple criteria sorting methods assign objects into ordered categories while objects are characterized by a vector of n attributes values. Categories are ordered, and the assignment of the object is monotonic w.r.t. to some underlying order on the attributes scales (criteria). Our goal is to offer a survey of the literature on multiple criteria sorting methods, since the origins, in the 1980s, focusing on the underlying models. Our proposal is organized into two parts. In Part I, we start by recalling two main models, one based on additive value functions (UTADIS) and the other on an outranking relation (Electre Tri). Then we draw a (structured) picture of multiple criteria sorting models and the methods designed for eliciting their parameters or learning them based on assignment examples. In Part II (to appear in a forthcoming issue of this journal), we attempt to provide a theoretical view of the field and position some existing models within it. We then discuss issues related to imperfect or insufficient information.

Appendices

Appendix A: The outranking relation in Electre  III

We give below, for the reader’s convenience a definition of the outranking relation used in Electre  III, which is the one involved in the classical version of Electre Tri (Roy and Bouyssou 1993).

Its definition involves the computation of a concordance index, a discordance index and a degree of credibility of outranking.

Let x, y be two objects whose evaluations on criterion i are, respectively, $x_i, y_i$ for $i=1, \ldots , n$. The concordance index c(x, y) is defined by $c(x,y) = \sum _{i=1}^{n} w_i c_i(x_i, y_i)$, where $w_i \ge 0$ is the importance weight of criterion i (we assume w.l.o.g. that weights sum up to 1) and $c_i(x_i, y_i)$ is a function represented in Fig. 1. Its definition involves the determination of $q_i$ (resp. $p_i$), the indifference (resp. preference) threshold.

Fig. 1

Shapes of the single criterion concordance index $c_i(x_i, y_i)$ and the discordance index $d_i(x_i, y_i)$ in Electre III and Electre Tri

The discordance index $d_i(x_i, y_i)$, also represented in Fig. 1, uses an additional parameter $v_i$, the veto threshold⁷.

The outranking credibility index $\sigma (x,y)$ is computed as follows:

$$\begin{aligned} \sigma (x,y)= c(x,y) \prod _{i: d_i(x_i, y_i) > c(x,y)} \frac{1-d_i(x_i, y_i)}{1-c(x,y)}. \end{aligned}$$

(7)

The outranking relation S can now be defined. Object x outranks object y, i.e., xSy, if $\sigma (x,y) \ge \lambda$, with the threshold $\lambda$ verifying $.5 \le \lambda \le 1$.

In order that x outranks y, c(x, y) has to be greater than or equal to $\lambda$. This index is “locally compensatory” in the sense that, for each i, there is an interval (namely, $[-p_i, -q_i]$) for the differences $x_i - y_i$ on which the single criterion concordance index increases linearly and these indices are aggregated using a weighted sum. Discordance also is gradual in a certain zone (namely $[-v_i, -p_i]$); it comes into play only when the discordance index $d_i(x_i , y_i)$ is greater than the overall concordance index c(x, y).

Appendix B: The outranking relation in Electre  I

A simpler, more ordinal, version of the construction of an outranking relation stands in the spirit of Electre I. It is the version used in MR-Sort (which does not use vetoes). It differs from the outranking relation in Electre  III mainly by the shapes of the single criterion concordance and discordance indices.

Fig. 2

Shapes of the single criterion concordance index $c_i(x_i ,y_i)$ and the discordance index $d_i(x_i,y_i)$ in the style of Electre I. Empty (resp. filled) circles indicate excluded (resp. included) values

The preference and indifference thresholds are confounded, which implies that there is no linear “compensatory” part in $c_i(x_i ,y_i)$; discordance only occurs in an all-or-nothing manner. The overall concordance index is defined by $c(x,y) = \sum _{i=1}^{n} w_i c_i(g_i(x) ,g_i(y))$, as above. In this construction, x outranks y, i.e., xSy, if $\sigma (x,y) \ge \lambda$, with

$$\begin{aligned} \sigma (x,y)= c(x,y) \prod _{i=1}^{n} (1-d_i(x_i ,y_i)), \end{aligned}$$

(8)

i.e., xSy if $c(x,y) \ge \lambda$ and $d_i(x_i ,y_i) =0$, for all i. Note that

$$\begin{aligned} c(x,y) = \sum _{i:x_i \ge y_i-q_i} w_i. \end{aligned}$$

We thus have $c(x,y) \ge \lambda$ if the sum of the weights of the criteria on which x is indifferent or strictly preferred to y is at least equal to $\lambda$.

Appendix C: List of abbreviations

For the reader’s convenience, we list below, in alphabetic order, the acronyms used in the text, except for acronyms of sorting methods.

• AVF: Additive Value Function

• CAI: Class Acceptability Index

• DM: Decision Maker

• DRSA: Dominance based Rough Sets Approach

• LP: Linear Program

• MCDM/A: Multiple Criteria Decision Making / Aiding

• MCS: Multiple Criteria Sorting

• MILP: Mixed Integer Linear Program

• ML: Machine Learning

• MOP: Monotone Ordered Partition

• PL: Preference Learning

• ROR: Robust Ordinal Regression

• SMAA: Stochatic Multicriteria Acceptability Analysis

• VF: Value Function

Appendix D: Complements

1.1 D.1 Complements to Sect. 3.5

Selecting a “central” model in the set of models compatible with assignment examples is a default rule that is supported by intuition. Experimental studies (Doumpos et al. 2014) show that the “centrality option” implicitly implements an idea of robustness. For a model, being “central” means that its parameters are far from violating the constraints induced by the assignment examples. However, this default option is not univocally defined (because centrality is not a totally clear notion) and sounds partly arbitrary (because the robustness principle is not made explicit).

In contrast, the principle of the robust approaches is to take into account all compatible models and to qualify the recommended assignments as being shared by all compatible models (necessary assignments), by some of these models (possible assignments) or by a fraction of them (probabilistic assignments). Although these ideas of robustness are appealing and likely useful in practice, they are not as unquestionable as they look at first glance. The following observations are in order.

Regarding the possibility/necessity approach, note that:

• Relying only on possible and necessary assignments for the recommendations will often be inefficient in practice (because, often, the range of possible assignments is large, and the set of necessary assignments may be empty). Using Greco et al. “representative value function” requires interactions with a DM, while the behavior of Kadziński and Tervonen’s representative model, which does not require interaction, has not been tested experimentally.

• The sets of possible and necessary assignments depend on the more or less general character of the model considered. They differ when we restrict the additive value function model to have linear marginals (i.e., when the model is a weighted sum) or to have piecewise linear marginals with a fixed number of segments or if we do not impose any restriction on the marginals. Obviously, the more general the model considered in the indirect elicitation process, the larger the set of possible assignments and the smaller the necessary assignments (for a given set of assignment examples). Therefore, the idea of necessary and possible assignments is not self-evident and should never be discussed without explicitly mentioning the precise underlying model.

Regarding the probabilistic approach to robustness (SMAA), in addition to being dependent on the general character of the model, there is an additional dependence of the simulation results on the choice of a probability distribution on the set of feasible parameters. Doumpos et al. (2014) postulate a uniform distribution and make their simulations accordingly. They experiment with the elicitation of an AVF with linear marginals and of the more general model using piecewise linear marginals (while the set of assignment examples and the test sets are generated by random models with linear marginals). They observe that the assignment accuracy degrades for all rules, including the two rules based on simulation (CAI-based and centroid) when a more general model (using piecewise linear marginals) is used.

From a purely experimental point of view, Doumpos et al.’s study tends to establish that the CAI-based and centroid rules (resulting from simulation with uniform distribution) show (slightly) better performance than the models implementing the centrality paradigm, in particular w.r.t. assignment accuracy on test sets. However, the following reservations can be made.

• In general, there is no single Additive Value Function (AVF) model producing the same assignments as the CAI-based rule. Therefore, assignment accuracy comparisons with rules corresponding to such a model are biased. The performance of the centroid rule is close to that of the CAI rule, but there is no clearcut experimental evidence that the centroid model beats the most accurate central rules. Experimental comparisons involving the “representative value function” are not available to date.

• Doumpos et al. (2014) conclusions rely on artificial assignment data generated by random additive value functions with linear marginals. One may wonder whether the same conclusions would emerge from experiments based on real assignment data, artificial data generated by another model, or noisy artificial data (i.e., assignments generated by a known model subsequently altered by random errors).

From a practical point of view, if a DM is available for interactions, the model instance elicited on the basis of assignments known or provided by the DM can be useful for triggering DM’s reactions and providing additional information. Elements such as possible and necessary assignments or indices such as CAI may help too. However, there is no evidence that proposing “representative” additive value function models would stimulate interactions more efficiently or accurately than the central or centroid models. Obtaining such evidence appears to be quite challenging.

Ending up an interactive process with a singled out model aiming to reflect the DM’s assignment mechanism is desirable. Such a model provides a compact representation of the assignment rule used by the DM and allows the generation of new assignments. It also provides a form of explanation or justification for the assignments (e.g., “this object is assigned to that category because its value is good enough for that; to be assigned to a better category, its value should be improved by at least this amount”). This is an advantage compared to a rule, such as the CAI-based rule, whose interpretation is more opaque to the DM.

The above discussion has focused on the additive value function model. The investigations relative to the Electre Tri model are much more limited, probably due to the algorithmic complexity eliciting the parameters of such a model. Note that the idea of robust assignment, in the guise of a range of possible assignments, was already present in Dias et al. (2002).

1.2 D.2 Complements to Sect. 4.1.1

Three examples of a sorting method derived from a ranking method:

• AHPsort (Ishizaka et al. 2012) builds on AHP, the “Analytic Hierarchy Process”, Saaty (1977, 1980)). AHP is a method for evaluating multi-dimensional objects using pairwise comparison judgments. These are supposed to be made in reference to underlying ratio scales of measurement (for assessing objects w.r.t. criteria and the relative importance of criteria). The result of the procedure is an evaluation, called priority, of each object in the form of a weighted sum of measurements on each criterion⁸. AHPSort characterizes categories either by limiting profiles or by central profiles. In both cases, for each object, the priorities of the object and all the profiles are computed through pairwise comparisons. The priorities of the limiting profiles define intervals of the real line. Each object is assigned to the category corresponding to the interval where its priority belongs. When using central profiles, the central profile having its priority closest to that of the object determines the category assigned to the object.

• MACBETHSort (Ishizaka and Gordon 2017) elaborates on the ranking method MACBETH (Bana e Costa and Vansnick 1994; Bana e Costa et al. 2005). The latter is a method for building an additive value function that is cardinal, i.e., the value differences represent the difference of preferences. In contrast, the value function used in UTADIS is ordinal because it allows one to rank the objects but not to assess the difference of preference between them. The model underlying MACBETH is thus much more constrained (i.e., a particular case of the additive value function model). MACBETHSort uses either limiting or central profiles. The MACBETH method is used to assess objects and profiles by an additive value function. The assignment to categories follows the same idea as in AHPSort.

• DEA-based sorting (Karasakal and Aker 2017) is a more complex proposal mixing techniques from AHP and DEA (Data Envelopment Analysis). A version of AHP using interval evaluations in pairwise comparisons yields interval values for criteria weights. One idea taken from DEA is to assess objects by using the set of weight values that is most favorable for them. Reference profiles are used for sorting. DEASort (Ishizaka et al. 2018) seems to have been developed independently. It is based on similar ideas (AHP and DEA). Classification thresholds on object evaluations are obtained by training a decision tree on reference assignments.

Three examples of sorting methods derived from an ideal point ranking method:

• TOPSIS-Sort (Sabokbar et al. 2016) adapts TOPSIS (Hwang and Yoon 1981) to sorting. TOPSIS ranks objects by computing their (Euclidean) distance to an ideal point and from an anti-ideal point. The closest to the ideal and the farthest to the anti-ideal, the better. Computing these distances for limiting profiles allows sorting objects in ordered categories (same way as in AHPSort).

• VIKORSORT (Demir et al. 2018) builds upon the ranking method VIKOR (Opricovic and Tzeng 2004; Duckstein and Opricovic 1980) relying on compromise programming (Zeleny 1973). VIKOR establishes a “compromise ranking” through the use of (a mixture of) two different distances (L$_1$, L$_{\infty }$) of objects from an ideal point. The assignment rule in VIKORSORT assigns objects to categories by comparing them to limiting profiles in terms of distance to an ideal point.

• The “case-based distance model for sorting” (Chen et al. 2007) requires that the DM provides assignment examples (cases) for each category. The centroid of the cases assigned to the best category furnishes an ideal point. The idea is that the cases assigned to the same category should be approximately equidistant from the ideal point, and the closer the category is to the ideal point, the better the category. The method aims at finding criteria weights and thresholds on the weighted (Euclidean) distance to the ideal point such that objects are assigned to the same category whenever their distance to the ideal point falls between two consecutive thresholds. The preference order on the categories is the succession order of the intervals between consecutive thresholds. Criteria weights and distance thresholds are obtained by solving an optimization problem that minimizes the sum of slack variables needed to enforce the application of the assignment rule on the set of available cases. This method is much in the spirit of UTADIS. The underlying model assumes that categories can be defined as the sets of objects whose distance from an ideal point is comprised between two thresholds. The method consists of eliciting the parameters of such a model based on assignment examples.

1.3 D.3 Complements to Sect. 4.1.2

Examples of PROMETHEE-based sorting methods PROMETHEE (Brans and Vincke 1985) is a ranking method based on a valued outranking relation $\sigma (x,y)$ ($x,y \in A$, where A is a finite set of objects). The $\sigma$ values are computed in a different way as in Electre. They represent the intensity of preference of x over y. Using matrix $\sigma$, three scores can be obtained. The out-flow (resp. in-flow) of object x is the sum in row (resp. column) of matrix $\sigma$, i.e., the sum over y of the values $\sigma (x,y)$ (resp. $\sigma (y,x)$). The net-flow is defined as the out-flow minus the in-flow. The following rule obtains a partial preorder on the objects in A: x is at least as preferred as y if the out-flow of x is not smaller than the out-flow of y and the other way around for their in-flows (PROMETHEE I). A complete preorder is obtained using the net flow (PROMETHEE II).

FlowSort (Nemery and Lamboray 2008) uses either limiting or central profiles. For each object x, one considers the set A containing x and all the profiles. Computing the three flows and using them as scores allows sorting objects in categories based on the profiles’ scores. The net flow score assigns objects to a category in-between those assigned by the in-flow and the out-flow. PromSort (Araz and Ozkarahan 2007) and PROMETHEE TRI (De Smet 2019; Figueira et al. 2004) also rely on the PROMETHEE flows. They differ by the way they use them in assignment rules.

Assignment rules applicable to valued preference relations Some papers formulate principles of assignment rules that can be applied to valued (or fuzzy) preference relations, such as those built in Electre or Promethee methods. Perny (1998) assigns an object to the category that maximizes a membership degree. The latter combines, by means of fuzzy logic operators, degrees of concordance and non-discordance of an object w.r.t. to limit profiles of the categories.

THESEUS (Fernández and Navarro 2011) starts from an unspecified valued binary relation $\sigma (x,y)$ and a threshold $\lambda$. The valued (or fuzzy) relation $\sigma$ may be constructed as in Electre or in Promethee, or otherwise. Five crisp binary relations are defined using $\sigma$ and $\lambda$ (outranking, strict preference, weak preference, indifference and incomparability). A set of reference profiles (at least one per category, possibly many) is assumed to be available. THESEUS assigns an object by taking into account the five possible relations between the object and all reference profiles.

1.4 D.4 Complements to Sect. 4.6

1.4.1 D.4.1 Incremental elicitation/active learning

In case the parameters of a model (in particular, a sorting model) have to be elicited by asking questions to a DM, it is of interest to optimize the sequence of questions. This generally means maximizing the expected information obtained from each question (which consists of asking the DM to assign an object to a category). Benabbou et al. (2017) apply a min max regret approach to elicit a capacity for models based on the Choquet integral in choice, ranking and sorting problems.

In the framework of AVF model with thresholds, Kadziński and Ciomek (2021) propose and test empirically a number of heuristic strategies to choose the next object that the DM will be asked to assign. The DM may answer by assigning the object to a category interval. After each answer, the “robust approach” is applied in order to determine the set of possible category assignments for each object. The SMAA approach is possibly also applied to compute each object’s class acceptability index (CAI). One of the tested heuristics selects an object whose current assignment is maximally imprecise; another chooses an object for which the entropy of the CAI probability distribution is maximal. The general idea of these heuristics is to reduce as much as possible the assignment indeterminacy at each step.

1.4.2 D.4.2 Constrained sorting problems

Constraints on the cardinality of categories have already been considered in Sect. 4.4. Besides modelling possible wishes of the DM, it is also a means for limiting the indeterminacy of the model in order to obtain more precise assignments in the robust approach. Kadziński and Słowiński (2013), Köksalan et al. (2017) deal with such constraints in the framework of the additive value function model; Özpeynirci et al. (2018) do the same for MRSort and the additive value function model too.

1.4.3 D.4.3 Group decision

For addressing multiple criteria sorting problems in a group decision-making context, it is pretty natural to start by building sorting models reflecting the views of each group member. In the second step, tools aiding in reaching a consensus are developed.

Damart et al. (2007) and Greco et al. (2012) do so in the framework of the AVF model. The group members provide assignment examples. In both papers, the consensus-seeking process takes advantage of the fact that the provided assignment examples do not fully determine the group members’ AVF models. Assignments to category intervals (Damart et al. 2007) or necessary and possible assignments (Greco et al. 2012) computed for each group member help in building a consensus.

de Morais Bezerra et al. (2017) elicit an Electre Tri model for each group member. They use a graphical interface (VICA) to compare the assignments produced by the group members sorting models. They try to reach a consensus by identifying assignments supported by a majority of the group members.

Chen et al. (2011) rely on assignment examples provided by each group member. They use DRSA to induce rules from the assignment examples and Dempster-Shafer theory of evidence to aggregate these rules. The most plausible assignments based on aggregated rules are selected.

Contributions to group decision for sorting are relatively scarce. Some further references are listed in Alvarez et al. (2021).

1.4.4 D.4.4 Non-monotone criteria or attributes

The preference is not always monotone (nondecreasing or nonincreasing) with the evaluations. For instance, in evaluating patients before surgery, the doctors’ preference about glycemia is neither “the more, the better” nor “, the less, the better”. There is an optimal value range; preference decreases above and below it. The assignment may not be monotone w.r.t. the value of some evaluations. However, in the case considered here, it is possible to reorder or re-code the evaluations in such a way that the assignment is monotone w.r.t. re-coded evaluations.

Guo et al. (2019) propose a method for progressively constructing an AVF sorting model with non-necessarily monotonic marginals. The non-monotone dimensions are single-peaked. The DM is asked to reveal her most preferred value on the scale. The first approximation of the corresponding marginal is linear nondecreasing up to the most preferred value and nonincreasing thereafter. The shape of the marginal is further refined in the following steps. In the same framework of AVF-based sorting models, Liu et al. (2019) learn non necessarily monotonic piecewise linear marginals. In order to limit overfitting, they add a regularization term to the loss function they want to minimize. Such a term may for instance aim at minimizing the slope variations at the breakpoint of the piecewise linear marginals.

Minoungou et al. (2022) address non-monotone criteria in outranking-based sorting, namely, using the MR-Sort model. They propose a MIP formulation for eliciting the parameters of MR-Sort based on assignment examples with non-necessarily monotone criteria. Their formulation recognizes cost, gain, single-peaked and single-valley criteria.

We come back on this, at the end of Sect. 2.1 in Part II (Belahcène et al. 2022), situating the criteria non-monotonicity issue in a general picture of sorting models.

1.4.5 D.4.5 Trichotomic forerunners

Sorting in three ordered categories (sometimes called trichotomic segmentation) has attracted particular attention before general MCS methods started to develop. Sorting requests for credit in a bank is an often cited example. Banks may want to make an initial rough rating of loan applicants by categorizing them into three categories: acceptable, refused and an intermediate category for which there is an hesitation on the decision, thus requiring further inquiry. The papers by Moscarola and Roy (1977) and Roy (1981), relying on an outranking relation à la Electre, were already cited in Sect. 1. In a similar vein, relying on an Electre-III outranking relation, Massaglia and Ostanello (1991) proposed nTOMIC, a method for segmenting objects in three categories with further refinement of the intermediate categories in five subcategories. The method was implemented in a software tool supporting all stages of the segmentation process (including the reference profiles, i.e., limiting profiles as in Electre Tri⁹.)

ABC analysis Another segmentation in three categories has been used for a long in inventory management, known as ABC analysis. The principle of classifying goods in storage into three categories is inspired by the famous 80–20 Pareto rule, in which a small percentage of a country’s population (typically 20%) generates the largest part of its output (typically 80%). Applied to inventory management, this idea leads to apply of tight control on goods in category A, which contains a small percentage (10 to 20%) of the inventory responsible for 60 to 80% of the total dollar usage (the annual dollar usage of a good is its cost time the annual volume of the demand). Category B (resp. C) is constituted of the goods responsible for about 30% (resp. 5 to 15%) of the total dollar usage; they represent 20 to 25% (resp. 50 to 60%) of the inventory. Category B receives less control than category A, and category C receives low control.

It was soon realized that dollar usage was not the sole criterion to take into account to assign goods into categories A, B or C. For instance, flexibility in production, scheduling, and reducing costs including costs of shortage and storage, may be important factors. Starting with Flores and Whybark (1986), a number of methods have been proposed to classify items in categories A, B or C, taking into account several criteria. Many MCS models have been adapted to that particular context, in which category A should collect a small number of items the control of which is crucial and category C a large number of items whose control may be relaxed (such requirements echo constraints on category cardinality, see Sect. D.4.2). Papers on ABC classification based on MCDM/A methods include e.g., Liu et al. (2016), based on Electre-III, and Kheybari et al. (2019), based on TOPSIS and goal programming (see also the references therein). Chen et al. (2008) propose a method for eliciting an ABC categorization on the basis of assignment examples (“case-based learning”). They use their “case-based distance model for sorting” (see last item in Sect. D.2).

1.4.6 D.4.6 Around sorting

Multiple Criteria Sorting (MCS) is a particular case of classification in which (i) categories are known a priori, in particular, their number is fixed, (ii) categories are totally ordered in terms of preference, (iii) assignment to categories respects the dominance relation, i.e., an object at least as good as another w.r.t. all criteria is not assigned to a worse category. This specification makes MCS close to Monotone Classification. However, the notion of a model is more central in MCS. Historically, model parameters had to be elicited by questioning a DM. In contrast, learning from cases is typical of (monotone) classification. Therefore, classification literature focuses on algorithms. A recent review on monotonic classification (Cano et al. 2019) does not mention any model within the two main families analyzed in the present paper (i.e., AVF- and outranking-based); only DRSA and the methods in Sect. 4.5.3 are discussed.

Some work done in the MCDA community falls within the field of classification or clustering but departs from MCS. Some of these relate to clustering. Usually, clustering algorithms are unsupervised techniques that form clusters of objects characterized by a n-tuple of attribute values. A cluster contains objects that are similar and as dissimilar as possible from the objects in the other clusters. The number of clusters may be fixed or not.

1.4.7 D.4.7 Multiple-criteria clustering

In Multiple Criteria Clustering (MCC), there is a preference direction on all attributes. Rosenfeld et al. (2021) distinguish three types of MCC : nominal, relational or ordered.

An early example of nominal clustering (De Smet and Montano Guzmán 2004) is based on a binary preference relation (neither necessarily complete nor transitive, such as a crisp outranking relation). A distance is defined: for any pair of objects, the more similar the sets of other objects they are preferred to, the smaller their distance. Based on such a distance, clusters are formed using a k-means algorithm.

De Smet et al. (2012) present an example of ordered clustering algorithm. The number of clusters is fixed, and the result is an ordered partition (yet it is not made clear whether the clustering algorithm always respects the dominance relation). Given a valued preference relation on objects (as those obtained using Promethee or Electre  III, for instance), an inconsistency matrix is associated with each ordered partition (into a fixed number of categories). The clustering algorithm finds an ordered partition minimizing inconsistency in a certain (lexicographic) sense.

In the intermediate type of MCC, i.e., relational clustering, a binary relation on clusters is obtained, which is a partial order. Eppe et al. (2014), Rocha et al. (2012) are examples of papers in that vein.

MCC exhibits characteristics that contrast with MCS, even in case the clusters are totally ordered. MCC pertains to data analysis. Existing MCC methods identify groups in a given dataset (with the peculiarity that there is a preference order on the attributes scales). They do not end up with a model that could predict the assignment of new objects to one of the clusters.

1.4.8 D.4.8 Nominal classification

Some methods for assigning objects to predefined unordered categories have been proposed within the MCDA community.

Multicriteria filtering We referred to Perny (1998) in Sect. 4.1.2. The principles exposed in this paper apply to ranking, sorting in ordered categories and assigning to unordered categories on the basis of fuzzy relations, implementing a concordance and non-discordance principle (as in the ELECTRE methods). In case of assigning to unordered categories, the fuzzy relation models indifference between an object and prototypes in each category. The membership of an object to a category is obtained by taking the maximum of the indifference degrees between the object and the prototypes characterizing the category (or more generally, by applying a t-conorm operator to these indifference degrees).

PROAFTN While Perny (1998) mainly describes and illustrates principles, Belacel (2000) proposes an instantiation of these principles in a method called PROAFTN. A valued indifference degree between objects and prototypes is built in the spirit of the outranking relation in Electre III. The degree of membership of an object to a category is the largest indifference degree between the object and the prototypes in the category. Each object is assigned to the category maximizing its membership degree.

In contrast with nominal clustering (e.g., De Smet and Montano Guzmán 2004), PROAFTN builds a model allowing to assign any new object. Originally, the user had to set the parameters defining the valued indifference degree (weights and thresholds). Several approaches for eliciting the model parameters have been proposed since then (see, e.g., Belacel et al. (2007), who design a variable neighborhood search heuristic).

CAT-SD As compared to PROAFTN, Costa et al. (2018) propose a more general way of constructing a membership degree (called degree of likeness) of an object to a category. This membership degree combines (again, in the style of ELECTRE III) an overall similarity and an overall dissimilarity functions¹⁰. Interactions between criteria can be modelled. The category assigned to an object is not necessarily unique. An object is assigned to all categories in which it has a membership degree above some threshold (such an assignment rule was already in Perny (1998). The resulting method is called CAT-SD. Costa et al. (2020) add further ingredients: a hierarchical structure of the criteria and the application of a SMAA methodology to obtain assignment probabilities. A deterministic assignment rule minimizing a loss function is also computed.