Decision Support
A new approach to multi-criteria sorting based on fuzzy outranking relations: The THESEUS method

https://doi.org/10.1016/j.ejor.2011.03.036Get rights and content

Abstract

In this paper, we propose the THESEUS method, a new approach based on fuzzy outranking relations to multi-criteria sorting problems. Compared with other outranking-based methods, THESEUS is inspired by another view of multi-criteria classification problems. It utilizes a new way of evaluating the assignment of an object to an element of the set of ordered categories that were previously defined. This way is based on comparing every possible assignment with the information from various preference relations that are derived from a fuzzy outranking relation defined on the universe of objects. The appropriate assignment is determined by solving a simple selection problem.

The capacity of a reference set for making appropriate assignments is related to a good characterization of the categories. A single reference action characterizing a category may be insufficient to achieve well-determined assignments. In this paper, the reference set capacity to perform appropriate assignments is characterized by some new concepts. This capacity may be increased when more objects are added to the reference set. THESEUS is a method for handling the preference information contained in such larger reference sets.

Introduction

This paper addresses the multi-criteria sorting problem, which is considered a particular case of classification problems involving preferences (cf. Greco et al., 1999, Greco et al., 2001, Doumpos and Zopounidis, 2002).

Many multi-criteria decision aiding methods have been developed for multi-criteria sorting problems. Usually, a multi-criteria sorting method attempts to capture the decision policy that is implicit in a reference or training set T of examples, previously classified by a decision-maker (DM). T may be obtained from different sources: past decisions; decisions made for a limited set of real or fictitious objects; or decisions taken for a subset of the objects under consideration for which the DM can easily make an assignment. Once the model of that policy has been built, it will be used for sorting new objects.

Most multi-criteria sorting methods can be classified as follows (cf. Doumpos et al., 2009):

  • Those based on the development of value functions (e.g. Zopounidis and Doumpos, 2002, Bugera et al., 2002, Köksalan and Ulu, 2003, Dembczyński et al., 2006, Köksalan and Özpeynirci, 2009, Greco et al., 2010);

  • Symbolic models based on decision rules (e.g. Greco et al., 2001, Błaszczyński et al., 2007, Fortemps et al., 2008, Dembczyński et al., 2009);

  • Outranking approaches (e.g. Massaglia and Ostanello, 1989/1991, Yu, 1992, Perny, 1998, Belacel, 2000, Doumpos and Zopounidis, 2004, Fernandez et al., 2008, Tervonen et al., 2009).

In the framework of outranking approaches, the most widely used method is ELECTRE TRI (Yu, 1992, Mousseau et al., 2000, Roy, 2001). Many applications of this method have been reported in the last few years (e.g. Dimitras et al., 1995, Raju et al., 2000, Arondel and Girardin, 2000, Joerin et al., 2001, Zopounidis and Doumpos, 2002, Mavrotas et al., 2003, Georgopoulou et al., 2003, Merad et al., 2004, Siskos et al., 2007, Xidonas et al., 2009, Brito et al., 2010). In ELECTRE TRI, the categories are assumed to be ordered from the worst to the best. A boundary alternative (reference profile) is introduced to establish the boundary between adjacent categories. Such reference profiles can be assigned in a co-construction interactive process between the analyst and the decision-maker. ELECTRE TRI develops an outranking relation, which is used to decide whether the object to be assigned (xj) outranks a reference profile or not.

ELECTRE TRI has been criticized because defining the reference profiles is often a difficult task, especially when the decision-maker has only a vague idea about the boundary between two consecutive categories. The existence of such boundaries is doubtful in many real-world problems (cf. Köksalan et al., 2009, Almeida-Dias et al., 2010). This issue has been addressed recently. Köksalan et al. (2009) proposed a method which requires the decision-maker to assign a subset of reference objects to the categories. In fact, this is a way to construct a reference set with some good properties. The new objects are compared with reference elements and assigned by solving a mathematical programming problem. The objective function of such a problem contains certain measure of the so-called ‘outranking violation’ (cf. Köksalan et al., 2009). However, discordance and veto effects are not handled by this method. Almeida-Dias et al. (2010) proposed the ELECTRE TRI-C method, in which each category is defined through a single characteristic reference action. As in ELECTRE TRI, the set of characteristic actions should be co-constructed through an interactive process by a DM-decision analyst.

One can question if a single reference action is sufficient for an acceptable characterization of its related category. As stated by Figueira et al. (2010), if each category is defined by a set of several reference actions, it enriches the definition of categories and allows more narrow ranges of categories to which an action can be assigned. In order to illustrate this point, let us consider the following trivial example. Table 1 shows a reference set composed of characteristic actions.

Let us accept that the ELECTRE III model parameters (weights, indifference thresholds, preference thresholds, veto thresholds) are set to: wi = 0.25; qi = 0; pi = 1; vi = 2; (i = 1,  , 4). Consider a new object x1 = (2, 2, 2, 6) to be sorted. Let σ(x, y) denote the credibility of ‘x outranks y’ calculated as in ELECTRE III (cf. Roy, 1991). Note that σ(bi, x1) = 0, i = 1, 2, 3, σ(x1, b1) = 0.25, σ(x1, bi)=0, i=2, 3. So, x1 is incomparable with any reference action. Hence, there is no information for a well-determined assignment of (2, 2, 2, 6). Now, suppose that the reference set is expanded by introducing b1,2 = (2, 2, 3, 5), assigned to C1. Note that σ(x1, b1,2) = 0.75 = σ(b1,2, x1). The valued indifference relation proposed by Fernandez et al., 2008, Fernandez et al., 2009 i(x1, b1,2) = min(σ(x1, b1,2), σ(b1,2, x1)) suggests assigning x1 to C1. So, the new reference element introduced new information that is useful for a well-determined assignment. The characterization of C1 was improved.

Under outranking-based sorting methods, and as a consequence of incomparability, the capacity of a reference set for making well-determined assignments (a sufficiently narrow range of categories to which an object can be assigned) is related to an appropriate characterization of the categories. If a reference set should characterize the decision policy from the DM, a single reference action representing each category may be insufficient (cf. Figueira et al., 2010). This issue should be considered in each particular sorting context. Sometimes, the DM can identify many assignment examples coming from past decisions. If a subset of these assignments is consistent, it may contain useful information for a better characterization of categories. In our view, each new element in the reference set is a piece of information which may contribute to a better characterization of its category, and the sorting method should be able to take advantage of this additional information.

In the present paper, we propose the THESEUS method, which is a new outranking-based sorting approach, based simultaneously on another view of multi-criteria sorting problems. THESEUS’ original view of multi-criteria sorting problems is presented in Section 2. Against this background, the THESEUS method is described in Section 3 and some properties are given in Section 4. Such properties are illustrated by a didactic example. In Section 5, THESEUS is tested using an example analysed by other papers. Finally, we present some conclusions in Section 6. Mathematical proofs and additional information about test examples have been separated into appendices to the on-line version of this paper.

Section snippets

Multi-criteria sorting seen as a selection problem

In this paper the term decision-maker (or decision agent) refers to those actors in whose name, or for whom, the decision-aiding process is performed. Often, the DM interacts with a facilitator of the decision-aiding process, who will be called ‘the analyst’.

Let us accept the following premises:

  • (i)

    There is a set of completely ordered categories Ct = {C1,  , CM}(M2);CM is assumed to be the preferred category. The term ‘preferred’ is related to each particular sorting problem.

  • (ii)

    There is a universe U of

Notation and basic concepts

Let σ(x, y) be a fuzzy outranking relation defined on U × U, and let us consider a real value λ > 0.5.

Definition 1

The following crisp binary relations are given on the universe:

  • (x, y)  S(λ) iff σ(x, y)  λ (λ-outranking)

  • (x, y)  P(λ) iff σ(x, y)  λ  σ(y, x) < 0.5 (λ-strict preference)

  • (x, y)  Q(λ) iff σ(x, y)  λ  0.5  σ(y, x) < λ (λ-weak preference)

  • (x, y)  I(λ) iff σ(x, y)  λ  σ(y, x)  λ (λ-indifference).

  • (x, y)  R(λ) iff σ(x, y) < λ  σ(y, x) < λ (λ-incomparability).

Definition 2

We say that a reference set T covers Ct if for each Ck  Ct there is at least one b  T

Some properties of THESEUS solutions

In Problem (5), (N1, N2)  (0, 0) for all Ek suggests inconsistent information in (xj, σ, λ, T).

In the following, a statement Ek with nP(Ek)=nQ(Ek)=n1I(Ek)=n2I(Ek)=0 will be called a consistent solution of Problems (4), (4’), (5).

Definition 4

A reference set T will be called (σ, λ)-consistent with respect to xj if there is a consistent solution of (4, 4′, 5) for this particular object.

When several consistent solutions exist, the THESEUS prescription is not free of ambiguity. The existence and uniqueness of

An example working on random reference sets

As in Fernandez et al., 2008, Fernandez et al., 2009, we considered a R& D project evaluation problem in which the decision attribute was the aggregate global impact and the description attributes included dimensions varying from economic, social, scientific, and improvement of research competence-formation of human resources points of view. 81 projects were evaluated by an actual decision-maker. The decision categories were {Exceptional, Very High, High, Above Average, Average, Below Average,

Final conclusions

The THESEUS approach is based on transforming the sorting problem into a particular case of the selection problem. The assignment of a new object to the defined categories in the reference set is suggested here using a multidimensional measure that contains the inconsistencies between the possible assignment and the information of the preference relations that could be strict, weak, or indifference, and are obtained from a fuzzy outranking relation. This proposal has the benefit of taking

Acknowledgements

We acknowledge support from CONACyT project No. 57255. We also acknowledge the helpful suggestions from three anonymous reviewers.

References (39)

  • Ph. Fortemps et al.

    Multicriteria decision support using rules that represent rough-graded preference relations

    European Journal of Operational Research

    (2008)
  • E. Georgopoulou et al.

    A multiple criteria decision-aid approach in defining national priorities for greenhouse gases emissions reduction in the energy sector

    European Journal of Operational Research

    (2003)
  • S. Greco et al.

    Rough sets theory for multicriteria decision analysis

    European Journal of Operational Research

    (2001)
  • S. Greco et al.

    Multiple criteria sorting with a set of additive value functions

    European Journal of Operational Research

    (2010)
  • M. Köksalan et al.

    An interactive approach for placing alternatives in preference classes

    European Journal of Operational Research

    (2003)
  • M. Köksalan et al.

    An interactive sorting method for additive utility functions

    Computers & Operations Research

    (2009)
  • V. Mousseau et al.

    A user-oriented implementation of the ELECTRE TRI method integrating preference elicitation support

    Computers & Operations Research

    (2000)
  • V. Mousseau et al.

    Valued outranking relations in ELECTRE providing manageable disaggregation procedures

    European Journal of Operational Research

    (2004)
  • Y. Siskos et al.

    A multicriteria accreditation system for information technology skills and qualifications

    European Journal of Operational Research

    (2007)
  • Cited by (57)

    • A generalized approach to ordinal classification based on the comparison of actions with either limiting or characteristic profiles

      2023, European Journal of Operational Research
      Citation Excerpt :

      The rule system paradigm, mainly related to rough sets theory (e.g., Błaszczyński et al., 2007; Dembczyński et al., 2009; Fortemps et al., 2008; Greco et al., 2001). The relational paradigm, where a so-called outranking relation is constructed and exploited (e.g., Almeida-Dias et al., 2010; Bouyssou & Marchant, 2015, Meyer & Olteanu, 2019; Bouyssou et al., 2020; Fernandez & Navarro, 2011; Perny, 1998; Yu, 1992). Classes can be described in three different main ways:

    • A Stochastic Multi-criteria divisive hierarchical clustering algorithm

      2021, Omega (United Kingdom)
      Citation Excerpt :

      The classification is done via means of comparing the performance of the alternatives to that of the reference profiles that act as a representation of that very class. Several MCDA techniques have been developed to solve sorting problems; see, for example, UTADIS [20], Electre-Tri [21], Electre-Tri-C [22], Electre-Tri-nC [23], FlowSort [24], PromSort [25], Theseus method [26], AHPSort [27], MACBETHSort [28], DEASort [29], ELECTRESort [30], VIKORSORT [31]. Turning to the second broad category of grouping techniques, clustering refers to a set of unsupervised techniques that group alternatives of similar calibre into the same object (called cluster).

    View all citing articles on Scopus
    View full text