\documentstyle{llncs}
%\usepackage{amssymb}
%\usepackage {multicol}
\begin{document}
\title{The possible and the necessary for\\
 multiple criteria group decision}

\author{ Salvatore Greco\inst{1}, Vincent Mousseau\inst{2} and Roman S{\l }owi{\'n}ski\inst{3}}


\institute{Faculty of Economics, University
of Catania, Italy, \email{salgreco@unict.it},
\and Ecole Centrale Paris,
Industrial Engineering Laboratory, France, \email{vincent.mousseau@ecp.fr}
\and Institute of Computing
Science, Pozna{\'n} University of Technology, Pozna{\'n}, and
Systems Research Institute, Polish Academy of Sciences, 00-441
Warsaw, Poland, \email{roman.slowinski@cs.put.poznan.pl}
%\and CEG-IST, Center for Management Studies, Instituto
%Superior T\'ecnico, Technical University of Lisbon, Portugal,
%\email{figueira@ist.utl.pt},
 }
\maketitle
\begin{abstract}
%Within aggregation-disaggregation approach, \textit{ordinal regression} aims at inducing the parameters of a preference model, for example the parameters of a value function, which have to represent some holistic preference comparisons  of the Decision Maker (DM). Usually, among the many sets of parameters of a preference model representing the preference information given by the DM, only one specific set is used to give a recommendation. For example, among many value functions representing the holistic preference information of the DM, only one value function is finally used to recommend the best choice, or sorting, or ranking of actions. Since the choice of one among many sets of parameters compatible with the preference information given by the DM is rather arbitrary, \textit{robust ordinal regression} has been recently  proposed with the aim of taking into account all the sets of parameters compatible with the preference information given by the DM. In this article, we introduce the principle of robust ordinal regression  to group decision. We shall consider the main multiple criteria decision methods to which robust ordinal regression has been applied, i.e. we shall consider $UTA^{GMS}$ and GRIP methods, dealing with choice and ranking problems, $UTADIS^{GMS}$ , dealing with sorting (ordinal classification) problems and $ELECTRE^{GMS}$, being an outranking methods applying robust ordinal regfression to well known ELECTRE methods. In this way we obtain corresponding methods for group decision: $UTA^{GMS}$-Group, $UTADIS^{GMS}$-GROUP and $ELECTRE^{GMS}$-GROUP.

We introduce the principle of robust ordinal regression  to group decision. We consider the main multiple criteria decision methods to which robust ordinal regression has been applied, i.e., $UTA^{GMS}$ and GRIP methods, dealing with choice and ranking problems, $UTADIS^{GMS}$, dealing with sorting (ordinal classification) problems, and $ELECTRE^{GMS}$, being an outranking method applying robust ordinal regression to well known ELECTRE methods. In this way, we obtain corresponding methods for group decision: $UTA^{GMS}$-GROUP, $UTADIS^{GMS}$-GROUP and $ELECTRE^{GMS}$-GROUP.


\textbf{Keywords}: Robust ordinal regression, Multiple criteria choice, sorting and ranking, Additive value functions,  Outranking methods, Multiple criteria group decision.
\end{abstract}






%\vfill \newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




In Multiple Criteria Decision Analysis (MCDA - for a recent state-of-the-art see \cite{FGS2005}), an alternative $a$, belonging to a finite set
of alternatives $A=\{a,b,\ldots, \linebreak j, \ldots, m\}$ ($|A|=m$), is evaluated on $n$ criteria $g_{i} \colon A \rightarrow \textbf{R}$ belonging to a consistent family $G=\{g_1, g_2,\ldots, g_i, \ldots, g_n\}$ ($|G|=n$).  %For example, in a decision problem regarding a recruitment of a new employee, the alternatives are the candidates and the criteria are built on a certain number of characteristics of the candidates, like type and degree of education, professional experience, age and impression made during an interview,  such that it is meaningful to compare the candidates using these criteria, as well as to give a comprehensive evaluation of the candidates.
From here on, to designate an $i$-th criterion, we will use interchangeably $g_{i}$ or $i$ ($i=1, \ldots, n$).
For the sake of simplicity, but without loss of generality, we suppose that  evaluations on each criterion
are increasing with respect to preference, \textit{i.e.}, the more the better, defining a marginal weak preference relation as follows:
$$ a \,\,\mbox{is at least as good as}\,\, b \,\,\mbox{with respect to criterion}\,\, i \,\, \Leftrightarrow \,\, g_i(a) \geq g_i(b).$$

There are two main approaches to construction of decision models in MCDA: Multi-Attribute Utility Theory (MAUT)  \cite{Keeney}, \cite{Dyer:2005}, and the outranking approach \cite{Roy-1991}, \cite{RoyBo93}, \cite{Fig-Mous-Roy-2005}.


The purpose of MAUT  is to represent  preferences of a Decision Maker (DM) on a set of alternatives  $A$ by  an overall value (utility) function
$$U(g_1(a), \ldots, g_n(a)) \colon \textbf{R}^n \rightarrow \textbf{R}$$
such that:
$$ a \,\,\mbox{is at least as good as}\,\, b \,\,%\text{with respect to criterion}
%\,\, i \,\,
\Leftrightarrow \,\, U(g_1(a), \ldots, g_n(a)) \ge U(g_1(b), \ldots, g_n(b)).$$
%U(g(a)) = U(g(b)).$$

%\begin{itemize}

%\item $ a \,\,\text{is indifferent to}\,\, b     \,\, \Leftrightarrow   \,\, U(g(a)) = U(g(b)),$

%\item $ a \,\, \text{is preferred to} \,\, b \,\, \Leftrightarrow \,\, U(g(a)) > U(g(b)),$

%\end{itemize}
%where for simplicity of notation, we  used $U(g(a))$, instead of $U(g_1(a), \ldots, g_n(a))$.

%The principal aggregation model of value function  is the multiple attribute additive utility \cite{Keeney}, such that:

%$$U(g(a))=  u_1(g_1(a))+ u_2(g_2(a))+ \cdots + u_n(g_n(a)) \,\,\,\, \mbox{with}\,\,\,\,a \in A,$$

%\noindent where $u_i$ are non-decreasing marginal value functions  for $i=1,2, \cdots, n.$


The goal of the outranking approach is to represent preferences of a DM  on a set of alternatives  $A$ by a pairwise comparison function
$$S(g_1(a),g_1(b),\ldots, g_n(a),g_n(b)) \colon \textbf{R}^{2n} \rightarrow \textbf{R}$$ such that:
$$ a \,\,\mbox{is at least as good as}\,\, b     \,\, \Leftrightarrow   \,\, S(g_1(a),g_1(b),\ldots, g_n(a),g_n(b)) \ge 0$$

%\begin{itemize}

%\item $ a \,\,\text{is at least as good as}\,\, b     \,\, \Leftrightarrow   \,\, S(g(a),g(b)) \ge 0$

%\item $ a \,\, \text{is preferred to} \,\, b \,\, \Leftrightarrow \,\, U(g(a)) > U(g(b)),$

%\end{itemize}
%where for simplicity of notation, we  used $S(g(a),g(b))$, instead of $S(g_1(a), g_1(b),\linebreak \ldots, g_n(a),g_n(b))$.

%A typical pairwise comparison function is given by ELECTRE IS method:


%\begin{itemize}
%       \item $S(g_1(a),g_1(b),\cdots , g_n(a),g_n(b)=1$ if

%\begin{itemize}
%       \item \begin{equation}
%\label{concord}
%C(a,b)=\frac{\sum_{i=1}^n \phi_i(a,b) \times k_i}{\sum_{i=1}^n k_i}\ge s,
%\end{equation}
        %$      \frac{\sum_{i=1}^n{k_i} s_i(a,b)}{\sum_{i=1}^n{k_i}}>s$, and
%       \item $g_i(b) - g_i(a) <v_i$ for all $i=1, \ldots, n$
%\end{itemize}
%\item $S(g_1(a),g_1(b),\cdots , g_n(a),g_n(b))=-1$ otherwise,

%\end{itemize}



%\noindent where, for $i=1, \ldots ,n$, $k_i$ is a weight related to the importance of criterion $g_i$, $q_i\ge 0$ is an indifference threshold, $p_i, p_i\ge q_i,$ is a preference threshold, $v_i, v_i\ge p_i,$ is a veto threshold, $0.5 \le s \le 1$ is a concordance threshold and
%\begin{equation}
%\label{phi}
%\phi_j(a,b) = \left\{
%           \begin{array}{ll}
%             1, & \hbox{if \ $g_j(a) \geq g_j(b)-q_j$,} \\
%             \frac{g_j(a) - [g_j(b)-p_j]}{p_j-q_j}, & \hbox{if \ $g_j(b)-p_j \leq g_j(a) < g_j(b)-q_j$,} \\
%             0, & \hbox{if \ $g_j(a) < g_j(b)-p_j$.}
%           \end{array}
%         \right.
%\end{equation}

%\noindent Observe that $\phi_j(a,b)$ is a marginal concordance index, indicating to what extend criterion $g_j$ contributes to the concordance index $C(a,b)$. As defined by (\ref{phi}), $\phi_j(a,b)$ is a piecewise-linear function, non-decreasing with respect to $g_j(a) - g_j(b)$.


%Each decision model requires specification of some parameters. For example, using multiple attribute utility theory the parameters are related to the formulation of marginal value functions $ u_i(g_i(a))$, $i=1, \ldots, n$, while using the outranking approach  the parameters can be weights $k_i$,  indifference,  preference, and veto thresholds $q_i, p_i, v_i$, $i=1, \ldots, n$.


Each decision model requires specification of some parameters. For example, using multiple attribute utility theory, the parameters are related to the formulation of marginal value functions $ u_i(g_i(a))$, $i=1, \ldots, n$, while using the outranking approach,  the parameters can be weights,  indifference,  preference, and veto thresholds for each criterion $g_i$, $i=1, \ldots, n$.

Recently, MCDA methods based on indirect preference information and on the \emph{disaggregation paradigm}  \cite{Lagreze:2001} are considered more
interesting, because they require less cognitive effort from the DM in order to express preference information.
The DM provides some holistic preferences on a set of reference
alternatives $A^R$, and from this information the parameters of a decision model are induced using a methodology called \textit{ordinal regression}.   The resulting decision model consistent with the provided preference information is used to evaluate the alternatives from set $A$
(\emph{aggregation stage}.) Typically, ordinal regression has been applied to MAUT models, so in these cases we speak of \textit{additive ordinal regression}. For example, additive ordinal regression has been applied in the well-known method called $UTA$
(see \cite{LagrezeSiskos1982}).
The ordinal regression methodology has been applied, moreover, to some nonadditive decision models. In this case, we speak of \textit{nonadditive ordinal regression} and its typical representatives are the $UTA$ like-methods substituting the additive value function by the Choquet integral (see \cite{Choquet}, \cite{Marichal:2000}, \cite{Angilella:2004}), and the DRSA methodology using a set of decision rules as the decision model (see \cite{greco3ejor01%,sgm
}).

Usually, among the many sets of parameters of a decision model representing the preference information given by the DM, only one specific set is considered. We say that the set of parameters or the decision model is \textit{compatible} with the preference information given by the DM if it is consistent with the preference information given by the DM. For example, from among the many compatible value functions only one function is selected to rank the alternatives from set $A$. Since the choice of one among many compatible sets of parameters is arbitrary to some extent, recently \textit{robust ordinal regression} has been proposed with the aim of taking into account all compatible sets of parameters. The first robust ordinal regression method is the recently proposed generalization of the $UTA$ method, called $UTA^{GMS}$ \cite{GrecoEtAl07}. In
$UTA^{GMS}$, instead of only one compatible additive value function composed of piecewise-linear marginal functions, all compatible additive value functions composed of general monotonic marginal functions are taken into account.

As to the preference information, the $UTA^{GMS}$ method requires from a DM to make some pairwise comparisons on
a set of reference alternatives $A^R \subseteq A$. The set of all compatible decision models defines two relations in
set $A$: the \textit{necessary} weak preference relation,
which holds for any two alternatives $a,b \in A$  if and only if
all compatible value functions give to $a$  a value greater than the value given to
$b$, and the \textit{possible} weak preference relation, which
holds for this pair if and only if at least one compatible
value function gives to $a$  a value greater than the value given to
$b$.

Recently, an extension  of $UTA^{GMS}$
has been proposed and called the $GRIP$ method \cite{FigueiraGrSl07}.
The $GRIP$ method builds a set of all compatible additive value functions, taking
into  account not only a preorder on a set of alternatives, but
also the intensities of preference among some reference alternatives. This kind of preference information is required in other well-known MCDA methods, such as $MACBETH$ \cite{BanaCostaVansnick1994} and $AHP$ 
\cite{Saaty:1980}, \cite{Saaty:2005}. Both $UTA^{GMS}$
and $GRIP$ apply the robust ordinal regression to the multiple attribute additive model and, therefore, we can say that these methods apply the \textit{additive robust ordinal regression}. In the literature, the \textit{nonadditive robust ordinal regression} has been proposed, applying the approach of robust ordinal regression to a value function having the form of Choquet integral in order to represent positive and negative interactions between criteria \cite{AGM}.
The robust ordinal regression approach can be applied also to the outranking approach \cite{GMSMarrakesh}.

In this paper, we wish to consider the robust ordinal regression in a group decision context. Therefore, we consider a set of decision makers $\cal D$ $=\{d_1, %\linebreak
\ldots, d_p\}$ with each own preferences, and we use robust ordinal regression to investigate spaces of consensus between them. The article is organized as follows. Section 2 is devoted to presentation of the general scheme of robust ordinal regression for choice and ranking problems within MAUT, as well as basic principles of $UTA^{GMS}$ and $GRIP$ methods. In section 3, robust ordinal regression for group choice and ranking problems is introduced within MAUT, and the  $UTA^{GMS}$-GROUP method is presented. Section 4 presents a general scheme of robust ordinal regression for sorting problems within MAUT, as well as basic principles of $UTADIS^{GMS}$. In section 5, robust ordinal regression for group sorting problems is introduced within MAUT, and the  $UTADIS^{GMS}$-GROUP method is presented. Section 6 presents a general scheme of robust ordinal regression within the outranking approach, as well as basic principles of $ELECTRE^{GMS}$. In section 7, robust ordinal regression for group decision problems is introduced within the outranking approach, and the  $ELECTRE^{GMS}$-GROUP method is presented. The last section contains conclusions.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The robust ordinal regression approach for choice and ranking problems within MAUT}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%The preference information may be either direct or indirect, depending whether it specifies directly values of some
%parameters used in the preference model (e.g. trade-off weights, aspiration levels, discrimination thresholds, etc.)
%or, whether it specifies some examples of holistic judgments from which compatible values of the preference model
%parameters are induced. Eliciting direct preference information from the DM can be counterproductive in real-world
%decision making situations because of a high cognitive effort required. Consequently, asking directly the DM to
%provide values for the parameters seems to make the DM uncomfortable. Eliciting indirect preference is less demanding
%of the cognitive effort. Indirect preference information is mainly used in the ordinal regression paradigm. According
%to this paradigm, a holistic preference information on a subset of some reference or training alternatives is known first
%and then a preference model compatible with the information is built and applied to the whole set of alternatives in
%order to rank them.\\

%The ordinal regression paradigm is concordant with the posterior rationality postulated by March in \cite{March78}.
%It has been known for at least fifty years in the field of multidimensional analysis. It is also concordant with the
%induction principle used in machine learning. This paradigm has been applied within the two main Multiple Criteria
%Decision Analysis (MCDA) approaches mentioned above: those using a value function as preference model
%(\cite{srini2psyc73a}, \cite{peke2mana74}, \cite{LagrezeSiskos1982}, \cite{SiskosEtAl05}), and those using an
%outranking relation as preference model (\cite{kiss3dss94}, \cite{mous2jogo98}). This paradigm has also been used
%since mid nineties' in MCDA methods involving a new, third family of preference models - a set of dominance decision
%rules induced from rough approximations of holistic preference relations (\cite{Grecoetal1999}, \cite{greco3ejor01} and
%\cite{12-MErgJFigSGre2005}).\\



MAUT provides a theoretical foundation for preference modeling using a real-valued utility function, called value function, aggregating evaluations of alternatives on multiple criteria. The value function is intended to be a preference model of a particular DM. It is also a decision model, since it gives scores to alternatives which permit to order them from the best to the worst, or to choose the best alternative with the highest score. Its most popular form is additive:
\begin{equation}
  \label{value_function}
   U(a) = \sum_{i=1}^n u_i(g_i(a)),
\end{equation}
where $u_i(g_i(a)), i=1,\ldots,n$, are real-valued marginal value functions.

Ordinal regression has been known for at least fifty years in the field of multidimensional analysis. It has been applied within MAUT, first to assess weights of an additive linear value function \cite{srini2psyc73a}, \cite{peke2mana74}, and then to assess parameters of an additive piece-wise linear value function  \cite{LagrezeSiskos1982}. The latter method, called $UTA$, initiated a stream of further developments, in both theory and applications \cite{SiskosEtAl05}.


Recently, two new methods, $UTA^{GMS}$ \cite{GrecoEtAl07} and $GRIP$ (\emph{G}eneralized \emph{R}egression with \emph{I}ntensities of \emph{P}reference) \cite{FigueiraGrSl07}, have generalized the
ordinal regression approach of the $UTA$ method in several aspects, the most important of which is that they are taking into account all additive value functions (1) compatible with the preference information, while $UTA$ is using only one such function.

%\begin{itemize}
 % \item taking into account all additive value functions (1)
   %     compatible with the preference information, while UTA is using only one such function,
  %\item considering marginal value functions of (1) as general non-decreasing
    %    functions, and not piecewise-linear, as in UTA,
  %\item asking the DM for a ranking of reference alternatives which is not necessarily complete (just pairwise comparisons),
  %\item taking into account additional preference information about intensity of preference, expressed
  %both comprehensively and with respect to a single criterion,
  %\item avoiding the use of the exogenous, and not neutral for the result, parameter $\varepsilon$
  %in the modeling of strict preference between alternatives.
%\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The preference information provided by the decision maker}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The DM is expected to provide the following preference information:
\begin{itemize}
\item  a partial preorder $\succeq$ on $A^R \subseteq A$ whose meaning is: for $x,y \in A^R$
\[
 x \succeq y \Leftrightarrow    x \;  \mbox{is at least as good as} \; y,
\]
%Moreover, $\succ$ (preference) is the asymmetric part of $\succeq$ and  $\sim$ (indifference) is the symmetric part
%given by $\succeq \cap \succeq^{-1}$. ($\succeq^-1$ is the inverse of $\succeq$,  i.e. for all $x,y \in A^R$, $x
%\succeq^- y \Leftrightarrow y \succeq x$).


\item  a partial preorder $\succeq^{\ast}$ on $A^R \times A^R$, whose meaning is: for $x, y,  w, z \in A^R$,
\[
(x,y) \succeq^{\ast} (w, z)  \Leftrightarrow   \;  \mbox{$x$ is
preferred to $y$ at least as much as $w$ is preferred to $z$},
\]
%Also in this case,  $\succ^{\ast}$ is the asymmetric part of $\succeq^{\ast}$  and $\sim^{\ast}$ is the symmetric
%part  given by $\succeq^{\ast} \cap \succeq^{\ast^{-1}}$ ($\succeq^{\ast^{-1}}$ is the inverse of $\succeq^\ast$,
%i.e. for all $x,y,w,z \in A^R$, $(x,y) \succeq^{\ast^{-1}} (w,z) \Leftrightarrow (w,z) \succeq^\ast (x,y)$).

\item  a partial preorder $\succeq_{i}^{\ast}$ on $A^R \times A^R$, whose meaning is: for $x, y, w, z \in A^R$,  $(x,y) \succeq_{i}^{\ast} (w, z)$  $\Leftrightarrow$     $x$ is preferred to $y$ at least as much as $w$ is preferred to $z$ on criterion $g_i$, $i=1,\ldots,n$.
\end{itemize}

%In the following, we also consider the weak preference relation
%$\succeq_i$ being a complete preorder whose meaning is: for all
%$x,y \in A$,

%\[
% x \succeq_i y  \; \; \; \Leftrightarrow \;  \; \; \mbox{$x$ is at least as good as $y$ on criterion $g_i$}, \; \; i \in I.
%\]

%Weak preference relations $\succeq_i$, $i \in I$, are not provided by the DM, but it is obtained directly from the
%evaluation of solutions $x$ and $y$ on criterion $g_i$, i.e., $x \succeq_i y \Leftrightarrow g_i(x) \geq g_i(y)$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Possible and necessary rankings}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A compatible value function is able to restore the preference information expressed by the DM on $A^R$ and $A^R \times A^R$. Each
compatible value function induces, moreover, a complete preorder on the whole set $A$. In particular, for any two
solutions $x,y\in A$, a compatible value function orders $x$ and $y$ in one of the following ways: $x \succ y$, $y
\succ x$, $x \sim y$. With respect to $x,y\in A$, it is thus reasonable to ask the following two questions:
\begin{itemize}
    \item Are $x$ and $y$ ordered in the same way by {\it all} compatible
    value functions?
    \item Is there {\it at least one} compatible value function
    ordering
    $x$ at least as good as $y$ (or $y$ at least as good as $x$)?
\end{itemize}
In the answer to these questions, $UTA^{GMS}$ and $GRIP$ produce two rankings on the set of alternatives $A$, such that for any pair of alternatives $a,b \in A$:
\begin{itemize}
  \item in the \textit{necessary} ranking (partial preorder), $a$ is ranked at least as good as $b$
        if and only if, $U(a) \ge U(b)$ for \textit{all} value functions compatible with
        the preference information,
  \item in the \textit{possible} ranking (strongly complete
and negatively transitive relation), $a$ is ranked at least as good as $b$
        if and only if, $U(a) \ge U(b)$ for \textit{at least one} value function
        compatible with the preference information.
\end{itemize}
The necessary ranking can be considered as \textit{robust} with respect to the preference information. Such robustness of the
necessary ranking refers to the fact that any pair of alternatives compares in the same way whatever the additive value
function compatible with the preference information. Indeed, when no preference information is given, the necessary
ranking boils down to the dominance relation, and the possible ranking is a complete relation.
%Every new pairwise comparison of reference alternatives, for which the dominance relation does not hold,  is enriching the necessary ranking and it is impoverishing the possible ranking, so that they converge with the growth of the preference information.

As $GRIP$ is taking into account additional preference information in form of comparisons of intensities of preference between some pairs
of reference alternatives, the set of all compatible value functions restoring the whole preference information is also used to produce four types of relations on $A \times A$, such that for any four alternatives $a, b, c, d \in A$:
\begin{itemize}
  \item the \textit{necessary} relation $(a,b)\succeq^{\ast^{N}}$$(c,d)$ (partial preorder) holds ($a$ is preferred to $b$ \textit{necessarily} at least as much as $c$ is preferred to $d$), if and only if $U(a) - U(b) \geq U(c) - U(d)$ for \textit{all} compatible value functions,
  \item the \textit{possible} relation $(a,b)\succeq^{\ast^{P}}(c,d)$ (strongly complete and negatively transitive relation) holds ($a$ is preferred to $b$ \textit{possibly} at least as much as $c$ is preferred to $d$), if and only if $U(a) - U(b) \geq U(c) - U(d)$ for \textit{at least one} compatible value functions,
  \item the \textit{necessary} relation $(a,b)\succeq^{\ast^{N}_i}(c,d)$ (partial preorder) holds (on criterion $i$, $a$ is preferred to $b$ \textit{necessarily} at least as much as $c$ is preferred to $d$), if and only if $u_i(a) - u_i(b) \geq u_i(c) - u_i(d)$ for \textit{all} compatible value functions $(i=1,\ldots,n)$,
  \item the \textit{possible} relation $(a,b)\succeq^{\ast^{P}_i}(c,d)$ (strongly complete and negatively transitive relation) holds (on criterion $i$, $a$ is preferred to $b$ \textit{possibly} at least as much as $c$ is preferred to $d$), if and only if $u_i(a) - u_i(b) \geq u_i(c) - u_i(d)$ for \textit{at least one} compatible value functions $(i=1,\ldots,n)$.
\end{itemize}

%Let us remark that such an approach has another feature which is very appealing for MCDA. It stems from the fact
%that it gives space for interactivity with the DM. Presentation of the necessary ranking, resulting from a preference
%information provided by the DM, is a good support for generating reactions from part of the DM. Namely, (s)he could
%wish to enrich the ranking or to contradict a part of it. Such a reaction can be integrated in the
%preference information considered in the next iteration.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Robust ordinal regression for group decision about choice and ranking: the $UTA^{GMS}$-GROUP method}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


The $UTA^{GMS}$-GROUP method applies the  robust ordinal regression approach to the case of group decision, in which several DMs cooperate to make a collective decision. DMs share the same ``description'' of the decision problem (the same set of alternatives, evaluation criteria and performance matrix). Each DM provides his/her own preference information, composed of pairwise comparisons of some reference alternatives. The collective preference model accounts for the preference expressed by each DM. Although in the considered framework it is also possible to handle preference information about intensity of preference, we will skip this preference information for the lack of space.

Let us denote the set of DMs by $\cal D$$ =\{d_1, \ldots, d_p\}$. %By $\succeq^{d_h}$ we denote the preference
For each DM $d_h \in$ $\cal D'\subseteq D$, we consider all compatible value functions. Four situations are interesting for a pair $(a,b) \in A$:
\begin{itemize}
  \item $a \succeq^{N,N}_{\cal D'} b$: \ $a \succeq^N b$ \ for \textit{all} $d_h \in \cal D'$,
  \vspace{4pt}
  \item $a \succeq^{N,P}_{\cal D'} b$: \ $a \succeq^N b$ \ for \textit{at least one} $d_h \in \cal D'$,
  \vspace{4pt}
  \item $a \succeq^{P,N}_{\cal D'} b$: \ $a \succeq^P b$ \ for \textit{all} $d_h \in \cal D'$,
  \vspace{4pt}
  \item $a \succeq^{P,P}_{\cal D'} b$: \ $a \succeq^P b$ \ for \textit{at least one} $d_h \in \cal D'$.
\end{itemize}
%The  robust ordinal regression has been applied to group decision in  the $\mbox{UTA}^{\mbox{\footnotesize GMS}}$-GROUP method.

%\textbf{Theorem} The following properties hold:
%\begin{enumerate}
%       \item[1)] for $D'\subseteq  D$
%       $$ \succeq^{N,N}_{D'} \subseteq \succeq^{N,P}(D'),$$
%       $$ \succeq^{N,N}(D') \subseteq \succeq^{P,N}(D'),$$
%       $$ \succeq^{N,P}(D') \subseteq \succeq^{P,P}(D'),$$
%       $$ \succeq^{P,N}(D') \subseteq \succeq^{P,P}(D');$$
%       \item[2)] for $D_1\subseteq D_2\subseteq D$
%       $$ \succeq^{N,N}(D_1) \supseteq \succeq^{N,N}(D_2),$$
%       $$ \succeq^{N,P}(D_1) \subseteq \succeq^{N,P}(D_2),$$
%       $$ \succeq^{P,N}(D_1) \supseteq \succeq^{P,N}(D_2),$$
%       $$ \succeq^{P,N}(D_1) \subseteq \succeq^{P,P}(D_2).$$
%If the binary relations $\succeq_{d_h}$ are complete preorders then the following properties holds
%\item[3)] for $D'\subseteq D$ and for any $a,b \in A$
%       $$ a \succeq^{N,N}(D') b \mbox{ or } b \succeq^{P,P}(D') a,$$
%       $$ a \succeq^{N,P}(D') b \mbox{ or } b \succeq^{P,N}(D')a,$$
%\item[4)] $\succeq^{N,N}(D')$ is a partial preorder   on $A$ for all $D' \subseteq D$;
%\item[5)] $\succeq^{N,P}(D')$ and $\succeq^{P,N}(D')$ are reflexive binary relations on $A$ for all $D' \subseteq D$;
%\item[6)] $\succeq^{P,P}(D')$ is a strongly complete and negatively transitive binary relation on $A$ for all $D' \subseteq D$;
%\item[7)] for all $D_1, D_2\subseteq D$ and for all $a,b,c \in A$
%       $$ a \succeq^{N,N}(D_1) b \mbox{ and } b S^{N,N}(D_2) c \Rightarrow a \succeq^{N,N}(D_1 \cap D_2) c,$$
%       $$ \mbox{ not } a \succeq^{P,P}(D_1) b \mbox{ and not } b \succeq^{P,P}(D_2) c \Rightarrow \mbox{ not } a S^{N,N}(D_1 \cap D_2) c.$$

%\end{enumerate}


%In this method, each DM $d_r \in cal DM$ gives the  preferential of $UTA^{GMS}$ and GRIP method. Using this information,  possible and necessary preference relations $\succeq_{d_h}^P$ and $\succeq_{d_h}^N$ are calculated for all decision maker $d_r \in cal DM$ and then the four prefernce relations
%$\succeq_{D'}^{N,N}, \succeq_{D'}^{N,P}, \succeq_{D'}^{P,N}\succeq_{D'}^{P,P}$ can be determined for all subset of DMs $D' \subseteq       \cal DM$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Robust ordinal regression for sorting problems: \newline the $UTADIS^{GMS}$ method}%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Robust ordinal regression has also been proposed for sorting problems in the new $UTADIS^{GMS}$ method \cite{GMS2009}, considering an additive value function (\ref{value_function}) as a preference model. Let us remember that sorting procedures consider a set of $k$ predefined preference ordered classes $C_1, C_2, \ldots, C_k$ , where $C_{h+1} \gg C_h$ ($\gg$ a complete order on the set of classes),
          $h=1, \ldots, k-1$. The aim of a sorting procedure is to assign each alternative to one class or to a set of contiguous classes. The robust ordinal regression takes into account a \textit{value driven sorting procedure}, that is, it uses a value
function $U$ to decide the assignments in such a way that if $U(a) > U(b)$ then $a$ is assigned to a class not worse
than $b$.

We suppose the DM provides preference information in form of possibly imprecise assignment examples on a reference set of alternatives $A^R \subseteq A$, i.e. for $a^R\in A^R$  the DM defines a desired assignment $a^R \rightarrow [C_{L^{DM}(a^R)},  C_{R^{DM}(a^R)}]$, where $[C_{L^{DM}(a^R)}, C_{R^{DM}(a^R)}]$ is an interval of contiguous classes $C_{L^{DM}(a^R)}, \linebreak C_{L^{DM}(a^R)+1},\ldots, C_{R^{DM}(a^R)}$. An assignment example is said to be precise if \linebreak $L^{DM}(a^R)=R^{DM}(a^R)$, and imprecise, otherwise.


Given a value function $U$, a set of assignment examples is said to be \textit{consistent with} $U$ iff
\begin{equation}
  \label{Uconsistent}
  \forall a^R,b^R \in A^R, U(a^R) \ge U(b^R) \; \Rightarrow \; R^{DM}(a^R) \ge L^{DM}(b^R).
\end{equation}
%which is  equivalent to
%\begin{equation}
%  \label{Uconsistent_1}
%  \forall a^R,b^R \in A^R, L^{DM}(a^R) > R^{DM}(b^R) \Rightarrow U(a^R) > U(b^R)
%\end{equation}

Given a set $A^R$ of assignment examples and a corresponding set ${\cal U}_{A^R}$ of compatible value functions, for each $a \in A$ we define the \textit{possible assignment} $C_P(a)$ as the set of indices of classes $C_h$ for which there exist \textit{at least one} value function $U \in {\cal U}_{A^R}$ assigning $a$ to $C_h$, and the \textit{necessary assignment} $C_N(a)$ as set of indices of classes $C_h$ for which \textit{all} value functions $U \in {\cal U}_{A^R}$ assign $a$ to $C_h$.
%, that is:
 %   \begin{eqnarray}
  %      C_P(a) & = & \{ h \in H \mbox{ such that } \exists U \in {\cal U}_{A^R} \mbox{ for which } h \in \lbrack L^U(a),R^U(a)\rbrack \}, \\
   %     C_N(a) & = & \{ h \in H \mbox{ such that } \forall U \in {\cal U}_{A^R} \mbox{ it holds }  h \in \lbrack L^U(a),R^U(a)\rbrack \}.
    %\end{eqnarray}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Robust ordinal regression for group decision about sorting: the $UTADIS^{GMS}$-GROUP method}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Given a set of  DMs $\cal D$$ =\{d_1, \ldots, d_p\}$, %By $\succeq^{d_h}$ we denote the preference
for each DM $d_r \in$ $\cal D' \subseteq D$ we consider the set of all compatible value functions ${\cal U}^{d_r}_{A^R}$. Given a set $A^R$ of assignment examples, for each $a \in A$ and for each  DMs $d_r \in \cal D'$ we define his/her possible and necessary assignments as
    \begin{eqnarray}
        C_P^{d_r}(a) & = & \{ h \in H \mbox{ such that } \exists U \in {\cal U}_{A^R}^{d_r} \mbox{ assigning } a \mbox{ to } C_h  \} \\
        C_N^{d_r}(a) & = & \{ h \in H \mbox{ such that } \forall U \in {\cal U}_{A^R}^{d_r} \mbox{ assigning } a \mbox{ to } C_h \}
    \end{eqnarray}
    Moreover, for each subset of DMs $D' \subseteq \cal D$, we define the following assignments:
    \begin{eqnarray}
        C_{P,P}^{D'}(a) & = \bigcup_{d_r \in {\cal D'}}C_P^{d_r}(a) \\
        C_{N,P}^{D'}(a) & = \bigcup_{d_r \in {\cal D'}}C_N^{d_r}(a) \\
        C_{P,N}^{D'}(a) & = \bigcap_{d_r \in {\cal D'}}C_P^{d_r}(a) \\
        C_{N,N}^{D'}(a) & = \bigcap_{d_r \in {\cal D'}}C_N^{d_r}(a).
     \end{eqnarray}

Possible and necessary assignments $C_P^{d_r}(a)$ and $C_N^{d_r}(a)$ are calculated for each decision maker $d_r \in \cal D$ using $\mbox{UTADIS}^{\mbox{\footnotesize GMS}}$, and then the four assignments $C_{P,P}^{D'}(a), \ C_{N,P}^{D'}(a), \ C_{P,N}^{D'}(a)$ and $C_{P,P}^{D'}(a)$ can be calculated for all subsets of decision makers $\cal D' \subseteq \cal D$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Robust ordinal regression for outranking methods}  %%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Outranking relation is a non-compensatory preference model used in the \linebreak $ELECTRE$ family of multiple criteria decision aiding methods \cite{Roy-1991}. Its construction involves two concepts known as concordance and discordance. Outranking relation, usually denoted by $S$, is a binary relation on a set $A$ of actions. For an ordered pair of actions $(a,b) \in A$, $aSb$ means ``$a$ is at least as good as $b$''. The assertion $aSb$ is considered to be true if the coalition of criteria being in favor of this statement is strong enough comparing to the rest of criteria, and if among the criteria opposing to this statement, there is no one for which $a$ is significantly worse than $b$. The first condition is called concordance test, and the second, non-discordance test.

Let us denote by $k_j$ the weight assigned to criterion $g_j$, $j=1,\ldots,n$; it represents a relative importance of criterion $g_j$ within family $G$ of $n$ criteria. The indifference, preference and veto thresholds on criterion $g_j$ are denoted by $q_j$, $p_j$ and $v_j$, respectively. For consistency, $v_j > p_j > q_j \geq 0$, $j=1,\ldots,n$. In all formulae that follow, we suppose, without loss of generality, that all these thresholds are constant, that preferences are increasing with evaluations on particular criteria, and that criteria are identified by their indices.

The concordance test involves calculation of concordance index $C(a,b)$. It represents the strength of the coalition of criteria being in favor of $aSb$. This coalition is composed of two subsets of criteria:
\begin{itemize}
  \item subset of criteria being clearly in favor of $aSb$, i.e., such that  $g_j(a) \geq g_j(b) - q_j$,
  \item subset of criteria that do not oppose to $aSb$, while being in an ambiguous position with respect to this assertion; these are those criteria for which a weak preference relation  $bQa$ holds; i.e., such that  $g_j(b) - p_j \leq g_j(a) < g_j(b) - q_j$.
\end{itemize}

Consequently, the concordance index is defined as
\begin{equation}
\label{concord}
C(a,b)=\frac{\sum_{j=1}^n \phi_j(a,b) \times k_j}{\sum_{j=1}^n k_j},
\end{equation}


\noindent where, for $j=1, \ldots ,n$,
\begin{equation}
\label{phi}
\phi_j(a,b) = \left\{
           \begin{array}{ll}
             1, & \hbox{if \ $g_j(a) \geq g_j(b)-q_j$,} \\
             \frac{g_j(a) - [g_j(b)-p_j]}{p_j-q_j}, & \hbox{if \ $g_j(b)-p_j \leq g_j(a) < g_j(b)-q_j$,} \\
             0, & \hbox{if \ $g_j(a) < g_j(b)-p_j$.}
           \end{array}
         \right.
\end{equation}

\noindent $\phi_j(a,b)$ is a marginal concordance index, indicating to what extend criterion $g_j$ contributes to the concordance index $C(a,b)$. As defined by (\ref{phi}), $\phi_j(a,b)$ is a piecewise-linear function, non-decreasing with respect to $g_j(a) - g_j(b)$.

Remark that $C(a,b)\in[0,1]$, where  $C(a,b)=0$ if $g_j(a) \leq g_j(b) - p_j$, $j=1,\ldots,n$ ($b$ is strictly preferred to $a$ on all criteria), and $C(a,b)=1$  if $g_j(a) \geq g_j(b) - q_j$, $j=1,\ldots,n$ ($a$ outranks $b$ on all criteria).

The result of the concordance test for a pair $(a,b) \in A$ is positive if \mbox{$C(a,b) \geq \lambda$}, where $\lambda \in [0.5,1]$ is a cutting level, which has to be fixed by the DM.

Once the result of the concordance test has been positive, one can pass to the non-discordance test. Its result is positive for the pair $(a,b) \in A$ unless ``$a$ is significantly worse than $b$'' on at least one criterion, i.e., if $g_j(b) ­ g_j(a) < v_j$  for   $j=1,\ldots,n$.

It follows from above that the outranking relation for a pair $(a,b) \in A$ is true, and denoted by $aSb$ if both the concordance test and the non-discordance test are positive. On the other hand, the outranking relation for a pair $(a,b) \in A$ is false, and denoted by $aS^c b$, either if the concordance test or the non-discordance test is negative. Knowing $S$ or $S^c$ for all ordered pairs $(a,b) \in A$, one can proceed to exploitation of the outranking relation in set $A$, which is specific for the choice, or sorting or ranking problem, as described in \cite{Fig-Mous-Roy-2005}.

Experience indicates that elicitation of preference information necessary for construction of the outranking relation is not an easy task for a DM. In particular, the inter-criteria preference information concerning the weights of criteria and the veto thresholds are difficult to be expressed directly.

For this reason, some aggregation-disaggregation procedures have been proposed in the past to assist the elicitation of the weights of criteria and all the thresholds required to construct the outranking relation \cite{mous2jogo98}, \cite{mszCOR2000}, \cite{Mous-Dias-2004}. A robust ordinal regression approach to outranking methods has been presented in \cite{GMSMarrakesh}. Below, we briefly sketch this proposal.
%The most general proposal, however, has been presented in \cite{GMSMarrakesh}. It permits to asses the set of outranking relations compatible with some exemplary pairwise comparisons of few real or fictitious reference actions, using a robust ordinal regression approach. Below, we briefly sketch this proposal.

We assume that the preference information provided by the DM is a set of pairwise comparisons of some reference actions. The set of reference actions is denoted by $A^R$, and it is usually, although not necessarily, a subset of set $A$. The comparison of a pair of actions $(a,b) \in A^R$ states the truth or falsity of the outranking relation, denoted by $aSb$ or $aS^c b$, respectively. It is worth stressing that the DM does not need to provide all pairwise comparisons of reference actions, so this comparison can be confined to a small subset of pairs.

We also assume that the intra-criterion preference information concerning indifference and preference thresholds $p_j > q_j \geq 0$, $j=1,\ldots,n$, is given. The last assumption is not unrealistic because these thresholds are relatively easy to provide by an analyst who is usually aware what is the precision of criteria, and how much difference is non-significant or relevant.

In order to simplify calculations of the ordinal regression, we assume that the weights of criteria sum up to one, i.e. $\sum_{j=1}^n k_j=1$. Thus, (\ref{concord}) becomes
%\vspace{-12pt}
\begin{equation}
\label{concord+}
C(a,b)=\sum_{j=1}^n \phi_j(a,b) \times k_j= \sum_{j=1}^n \psi_j(a,b),
\end{equation}
%\vspace{-12pt}
\noindent where the marginal concordance index $\psi_j(a,b)=\phi_j(a,b) \times k_j$ is a monotone non-decreasing function with respect to $g_j(a) - g_j(b)$, such that $\psi_j(a,b) \geq 0$ for $g_j(a) - g_j(b) \geq -q_j$, $j=1,\ldots,n$, and  $\sum_{j=1}^n \psi_j(a,b)=1$ in case $g_j(a) - g_j(b)= \beta_j -\alpha_j$ for all $j=1,\ldots,n$, $\alpha_j$ and $\beta_j$ being the worst and the best evaluation on criterion $g_j$, respectively.

The ordinal regression constraints defining the set of concordance indices $C(a,b)$, cutting levels $\lambda$ and veto thresholds $v_j$, $j=1,\ldots,n$, compatible with the pairwise comparisons provided by the DM have the following form:

$$
\label{compatible}
\left.
\begin{array}{l}
             C(a,b)= \sum_{j=1}^n \psi_j(a,b) \geq \lambda \mbox{ \ and \ } g_j(b) - g_j(a) \leq v_j - \epsilon, j=1,\ldots,n, \\
             \mbox { \quad if \ } aSb, \mbox{ \ for \ } (a,b)\in A^R, \\
             C(a,b)= \sum_{j=1}^n \psi_j(a,b) \leq \lambda + \epsilon + M_0(a,b) \mbox{ \ and \ } g_j(b) - g_j(a) \leq v_j - \delta M_j(a,b),\\ M_j(a,b) \in \{0,1\}, \ \sum_{j=0}^n M_j(a,b) \leq n, \ j=1,\ldots,n,\\
             \mbox { \quad if \ } aS^cb, \mbox{ \ for \ } (a,b)\in A^R, \\
             1 \geq \lambda \geq 0.5, \quad v_j \geq p_j, \ j=1,\ldots,n,\\
             \psi_j(a,b) \geq 0 \mbox{ \ if \ } g_j(a) - g_j(b) \geq -q_j, \mbox{ \ for all\ } (a,b) \in A^R, \ j=1,\ldots,n,\\
             \sum_{j=1}^n \psi_j(a,b)=1 \mbox{ \ if \ } g_j(a) - g_j(b)= \beta_j -\alpha_j \mbox{ \ for all\ } (a,b) \in A^R, \ j=1,\ldots,n,\\
             \psi_j(a,b) \geq \psi_j(c,d)  \mbox{ \ if \ }  g_j(a) - g_j(b) \geq g_j(c) - g_j(d), \\
             \mbox{ \quad for all\ } a,b,c,d \in A^R, \ j=1,\ldots,n,
\end{array}
\right\} E(A^R)
$$

\noindent where $\epsilon$ is a small positive value and $\delta$ is a big positive value. Remark that $E(A^R)$ are constraints of a 0-1 mixed linear program.\\

Given a pair of actions $(x,y) \in A$, the following values are useful to build necessary and possible outranking relations:
$$
d(x,y) = Min \left\{ \sum_{j=1}^n \psi_j(x,y) - \lambda\right \}, D(x,y) = Max \left\{ \sum_{j=1}^n \psi_j(x,y) - \lambda\right \}.
$$

\noindent subject to constraints $E(A^R)$, where $\psi_j(a,b) \geq \psi_j(c,d)  \mbox{ \ if \ }  g_j(a) - g_j(b) \geq g_j(c) - g_j(d)$, \ for all  $a,b,c,d \in A^R\cup\{x,y\}, \ j=1,\ldots,n$, \ and $g_j(y)-g_j(x) \geq v_j$, \ $j=1,\ldots,n$.

Given a pair of actions $(x,y) \in A$, $x$ \textit{necessarily} outranks $y$, which is denoted by $xS^Ny$, if and only if $d(x,y) \geq 0$. $d(x,y) \geq 0$  means that for all compatible outranking models $x$ outranks $y$.
%Obviously, for all $(x,y) \in A^R$, $xSy \Rightarrow xS^N y$.
Analogously, given a pair of actions $(x,y) \in A$, $x$ \textit{possibly} outranks $y$, which is denoted by $xS^Py$, if and only if $D(x,y) \geq 0$. $D(x,y) \geq 0$  means that for at least one compatible outranking model $x$ outranks $y$. The necessary and the possible outranking relations are to be exploited as usual outranking relations in the context of choice, sorting and ranking problems.
 %Obviously, for all $(x,y) \in A^R$, $xSy \Rightarrow not (yS^P x)$.\\



%$$
%d(x,y) = Min \left\{ \sum_{j=1}^n \psi_j(x,y) - \lambda\right \},
%$$

%\noindent subject to constraints $E(A^R)$, where $\psi_j(a,b) \geq \psi_j(c,d)  \mbox{ \ if \ }  g_j(a) - g_j(b) \geq g_j(c) - g_j(d)$, \ for all  $a,b,c,d \in A^R\cup\{x,y\}, \ j=1,\ldots,n$, \ and $g_j(y)-g_j(x) \geq v_j$, \ $j=1,\ldots,n$.


%, where

%$$
%D(x,y) = Max \left\{ \sum_{j=1}^n \psi_j(x,y) - \lambda\right \},
%$$

%\noindent subject to constraints $E(A^R)$, where $\psi_j(a,b) \geq \psi_j(c,d)  \mbox{ \ if \ }  g_j(a) - g_j(b) \geq g_j(c) - g_j(d)$, \ for all  $a,b,c,d \in A^R\cup\{x,y\}, \ j=1,\ldots,n$, \ and $g_j(y)-g_j(x) \geq v_j$, \ $j=1,\ldots,n$.



%Moreover, for any pair of actions $(x,y) \in A$:
%$$
%xS^Ny  \Leftrightarrow not(xS^{cP}y) \quad \mbox{and} \quad
%xS^Py  \Leftrightarrow not(xS^{cN}y)
%$$
%\noindent so, only $xS^Ny$ and $xS^Py$ are to be checked.

%The necessary and the possible outranking relations are to be exploited as usual outranking relations in the context of choice, sorting and ranking problems.
%\\


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Robust ordinal regression for outranking methods in group decision problems}  %%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


The above approach can be adapted to the case of group decision. In this case, several DMs cooperate in a decision problem to make a collective decision. DMs share the same ``description'' of the decision problem (the same set of actions, evaluation criteria and performance matrix). Each DM provides his/her own preference information, composed of pairwise comparisons of some reference actions. The collective preference model accounts for the preference expressed by each DM.

Let us denote the set of DMs by $\cal D$=$\{d_1, \ldots, d_p\}$. For each DM $d_r \in D'\subseteq D$, we consider all compatible outranking models. Four situations are interesting for a pair $(x,y) \in A$:
\begin{itemize}
  \item $x\ S^{N,N}(D')\ y$: \ $x S^N y$ \ for all $d_r \in D'$,
  \item $x\ S^{N,P}(D')\ y$: \ $x S^N y$ \ for at least one $d_r \in D'$,
  \item $x\ S^{P,N}(D')\ y$: \ $x S^P y$ \ for all $d_r \in D'$,
  \item $x\ S^{P,P}(D')\ y$: \ $x S^P y$ \ for at least one $d_r \in D'$.
\end{itemize}







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusions}   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



In this article we presented basic principles of robust ordinal regression for group decision.  After recalling the robust ordinal regression methods within MAUT for choice and ranking problems ($UTA^{GMS}$ and $GRIP$), for sorting problems (($UTADIS^{GMS}$), as well as ordinal regression methods within the outranking approach ($ELECTRE^{GMS}$), we extended all these methods to group decision introducing  $UTA^{GMS}$-Group,  $UTADIS^{GMS}$-GROUP and $ELECTRE^{GMS}$ -GROUP.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\vspace{0.75cm}


%\noindent {\large{\bf Acknowledgements}} \makeatother \addcontentsline{toc}{section}{Acknowledgements} The third author wishes to acknowledge financial support from the Polish Ministry of Education and Science, grant no. N N519 314435.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%BIBLIOGRAPHY%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\begin{thebibliography}{22}


\bibitem{Angilella:2004}  Angilella, S.,  Greco, S.,  Lamantia, F.,  Matarazzo, B., 2004. Assessing
non-additive utility for multicriteria decision aid. \textit{European Journal of Operational Research}, 158, 734-744.

\bibitem{AGM} Angilella, S.,  Greco, S.,  Matarazzo, B., 2008. Nonadditive robust ordinal regression: aggregation-disaggregation approach considering all compatible fuzzy measures in a multiple criteria decision model based on the Choquet integral. Forthcoming in \textit{European Journal of Operational Research}.

%\bibitem{AGMS} Angilella, S.,  Greco, S.,  Matarazzo, B., 2008. \textit{Sorting decisions with interacting
%criteria}, presented at A.M.A.S.E.S. conference, Trento, Italy,  September 1-4, 2008.

\bibitem{BanaCostaVansnick1994}  Bana e Costa, C. A.,  Vansnick, J. C., 1994. MACBETH:
An interactive path towards the construction of cardinal value
functions. \textit{International Transactions in Operational Research}, 1 (4),  387-500.

%\bibitem{09-MErgJFigSGre2005} Bana e Costa, C. A., J.M. De Corte, Vansnick, J. C., 2005.
%On the Mathematical Foundation of MACBETH, in Figueira, J.,  Greco, S. and Ehrgott, M. (eds) \textit{Multiple
%Criteria Decision Analysis: State of the Art Surveys},  Springer, New York, pp. 409-443.

%\bibitem{BBEGMRS} Belton, V., Branke, J., Eskelinen, P., Greco, S., Molina, J., Ruiz, F.,  S{\l}owi\'{n}ski, R., 2008. Interactive Multiobjective Optimization from a Learning Perspective, chapter 15 in:  Branke, J., Deb, K., Miettinen, K., S{\l}owi\'{n}ski, R. (eds.), \textit{Multiobjective Optimization: Interactive and Evolutionary Approaches}, LNCS 5252, Springer, Berlin, pp. 405-434.

%\bibitem{BDMS} Branke, J., Deb, K., Miettinen, K., S{\l}owi\'{n}ski, R. (eds.), 2008. \textit{Multiobjective Optimization: Interactive and Evolutionary Approaches}, Springer, Berlin.

%\bibitem{BGSZ} Branke, J., Greco, S., S{\l}owi\'{n}ski, R., Zielniewicz, P. 2009. \textit{Interactive Evolutionary Multiobjective Optimization using Robust Ordinal Regression}, to be presented at 5th International Conference on Evolutionary Multi-Criterion Optimization, EMO'09, Nantes, France, April 07-10, 2009.

\bibitem{Choquet}  Choquet, G., 1953. Theory of capacities.  \textit{Annales de l'Institut  Fourier}, 5, 131-295.

%\bibitem{Deb02afast} Deb, K., Pratap, A., Agarwal, A., Meyarivan, T., 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II, \textit{IEEE Transactions on Evolutionary Computation}, 6, 182-197.


\bibitem{Dyer:2005}   Dyer, J.S., 2005. Multiattribute Utility Theory, in Figueira, J.,  Greco, S. and Ehrgott, M. (eds.) \textit{Multiple
Criteria Decision Analysis: State of the Art Surveys},  Springer, New York, pp. 265-295.

\bibitem{FGS2005} Figueira, J., Greco, S., Ehrgott, M. (eds.), 2005. \textit{Multiple Criteria Decision Analysis: State of the Art Surveys}, Springer, New York.

%\bibitem{FGMS_Dagstuhl} Figueira, J., Greco, S., Mousseau, V., S{\l}owi\'{n}ski, R., 2008.  Interactive Multiobjective Optimization using a Set of Additive Value Functions, chapter 4 in J.Branke, K.Deb, K.Miettinen, R.S{\l}owi\'{n}ski (eds.), \textit{Multiobjective Optimization: Interactive and Evolutionary Approaches}, LNCS 5252, Springer, Berlin, pp.97-120.

%\bibitem{FGMS2008} Figueira, J., Greco, S., Mousseau, V., S{\l}owi\'{n}ski, R., 2008. $UTA^{GMS}$ \textit{and GRIP methodology for multiple criteria decision problems}, presented at 19th International Conference on Multiple Criteria Decision Making, Auckland, New Zealand, January 7-12, 2008.


\bibitem{FigueiraGrSl07}  Figueira, J.,  Greco, S.,  S{\l}owi\'{n}ski, R., 2009. Building a set of additive value functions representing a reference preorder and intensities of preference: GRIP method. \textit{European Journal of Operational Research}, 195, 460-486.

%\bibitem{FGSChania2008} Figueira, J., Greco, S., S{\l }owi{\'n}ski, R., 2008. \textit{Identifying the ``most representative'' value function among all compatible value functions in the GRIP method}, presented at 68th Meeting of the European Working Group on Multiple Criteria Decision Aiding, Chania, October 2-3, 2008.

\bibitem{Fig-Mous-Roy-2005} Figueira, J., Mousseau, V., Roy, B., 2005. ELECTRE methods, chapter 4 in J. Figueira, S. Greco and M. Ehrgott (eds.), \textit{Multiple Criteria Decision Analysis: State of the Art Surveys}, Springer, New York, pp. 133-162.

%\bibitem{Grabisch:1996}   Grabisch, M., 1996.
%The application of fuzzy integrals in multicriteria decision making. \textit{European Journal of Operational Research},  89, 445-456.

 %\bibitem{Grabisch:1997}   Grabisch, M., 1997. $k$-Order additive discrete fuzzy
%measures and their representation. \textit{Fuzzy Sets and Systems}, 92, 167-189.

%\bibitem{Grabisch:2005} Grabisch, M., Labreuche, C., 2005. Fuzzy measures and integrals in MCDA, in: J. Figueira, S. Greco, M. Ehrgott (eds.), \textit{Multiple Criteria Decision Analsysis}, Springer, New York, pp. 563-608.

%\bibitem{GKS} Greco, S., Kadzi{\'n}ski, M.,  S{\l }owi{\'n}ski, R., 2008. \textit{The most represenative value function for multiple criteria sorting based on robust ordinal regression}.  Report of the Institute of Computing Science, Pozna{\'n} University of Technology, Pozna{\'n}.

%\bibitem{Grecoetal1999} Greco, S., Matarazzo, B.,  S{\l }owi{\'n}ski, R., 1999. The use of rough sets and fuzzy sets in MCDM, in: T. Gal, T. Hanne, T. and T. Stewart (eds.), \textit{Multicriteria Decision Making: Advances in {MCDM} Models, Algorithms, Theory and Applications}, Kluwer, Dordrecht, pp. 14.1-14.59.

\bibitem{greco3ejor01} Greco,  S., Matarazzo, B.,  S{\l}owi\'{n}ski, R., 2001.
 Rough sets theory for multicriteria decision analysis. \textit{European Journal of Operational Research}, 129, 1-47.

%\bibitem{12-MErgJFigSGre2005} Greco,  S., Matarazzo, B.,  S{\l}owi\'{n}ski, R., 2005. Decision Rule Approach, chapter 13 in J. Figueira, S. Greco, M. Ehrgott (eds.), \textit{Multiple Criteria Decision Analsysis}, Springer, New York, pp. 507-561.

%\bibitem{GMS2006} Greco,  S., Mousseau, V.,   S{\l}owi\'{n}ski, R., 2006. \textit{Multiple criteria sorting with a set of additive value functions}, presented at  18th International Conference on Multiple Criteria Decision Making, Chania, Greece, June 19-23, 2006.

\bibitem{GMSMarrakesh} Greco,  S., Mousseau, V.,  S{\l}owi\'{n}ski, R., 2007. \textit{The necessary and the possible in a perspective of robust decision aiding}, presented at 66th Meeting of the European Working Group on Multiple Criteria Decision Aiding,  Marrakech, Morocco, October 18-20, 2007.

\bibitem{GrecoEtAl07} Greco,  S., Mousseau, V.,   S{\l}owi\'{n}ski, R., 2008.
Ordinal regression revisited: Multiple criteria ranking with a set of additive value functions. \textit{European Journal of Operational Research}, 191, 415-435.

\bibitem{GMS2009} Greco,  S., Mousseau, V.,  S{\l}owi\'{n}ski, R., 2009. \textit{Multiple criteria sorting with a set of additive value functions}, \textit{European Journal of Operational Research}, submitted.

%\bibitem{JaBr08} Jaszkiewicz, A., Branke, J., 2008. Interactive multiobjective evolutionary algorithms, in: J. Branke, K. Deb, K. Miettinen, R. S{\l}owi\'{n}ski (eds.), \textit{Multiobjective Optimization: Interactive and Evolutionary Approaches},  LNCS 5252, Springer, Berlin, pp. 179-193.


\bibitem{kiss3dss94} Kiss, L., Martel, J.M., Nadeau, R. 1994.  ELECCALC - an interactive software for modelling the decision maker's preferences, \textit{Decision Support Systems},  12, 757-777.

\bibitem{LagrezeSiskos1982}  Jacquet-Lagr\`{e}ze, E.,   Siskos, Y., 1982.
 Assessing a set of additive utility functions for multicriteria decision-making, the UTA method.
 \textit{European Journal of Operational Research}, 10, 151-164.

 \bibitem{Lagreze:2001}  Jacquet-Lagr\`{e}ze, E.,   Siskos, Y., 2001.
Preference disaggregation: 20 years of MCDA experience.
 \textit{European Journal of Operational Research}, 130, 233-245.

\bibitem{Keeney}  Keeney, R.L.,  Raiffa, H., 1976.
\textit{Decision with Multiple Objectives - Preferences and value Tradeoffs}. Wiley, New York.

%\bibitem{Kim:1999}  Kim, S.H., Ahn, B.S., 1999. Interactive group decision making procedure under incomplete information. \textit{European Journal of Operational Research}, 116, 498-507.

%\bibitem{March78} March, J., 1978. Bounded rationality, ambiguity and the engineering of choice,    \textit{Bell Journal of Economics}, 9, 587-608.

\bibitem{Marichal:2000}   Marichal, J. L.,  Roubens, M., 2000.
Determination of weights of interacting criteria from a reference
set. \textit{European Journal of Operational Research}, 124, 641-650.

\bibitem{Mous-Dias-2004}        Mousseau, V., Dias, L., 2004. Valued outranking relations in ELECTRE providing manageable disaggregation procedures. \textit{European Journal of Operational Research}, 156, 467-482.

\bibitem{mous2jogo98} Mousseau, V., S{\l}owi\'{n}ski, R., 1998. Inferring an ELECTRE TRI model from assignment examples.
\textit{Journal of Global Optimization}, 12, 157-174.

\bibitem{mszCOR2000} Mousseau, V., S{\l}owi\'{n}ski, R., Zielniewicz, P., 2000. A user-oriented implementation of the ELECTRE-TRI method integrating preference elicitation support. \textit{Computers and Operations Research}, 27, 757-777.

\bibitem{peke2mana74} Pekelman, D., Sen, S.K., 1974. Mathematical programming models for the determination of attribute weights. \textit{Management Science}, 20, 1217-1229.

%\bibitem{Roubens}  Roubens, M., 1996. \textit{Interaction between criteria through the use
% of fuzzy measures}. Report 96.007, Institut de Math\'{e}matiques, Universit\'{e} de Li\`{e}ge, Li\`{e}ge.

\bibitem{Roy-1991} Roy, B., 1991. The outranking approach and the foundations of ELECTRE methods. \textit{Theory and Decision}, 31, 49-73.

\bibitem{RoyBo93} Roy, B., Bouyssou, D., 1993. \textit{Aide Multicrit\`ere \`a la D\'ecision : M\'ethodes et Cas}.
 Economica,  Paris.


\bibitem{Saaty:1980}  Saaty, T.L., 1980. \textit{The Analytic Hierarchy Process}. McGraw-Hill, New York.

\bibitem{Saaty:2005}   Saaty, T.L., 2005. The Analytic Hierarchy and Analytic Network Processes for the
Measurement of Intangible Criteria and for Decision-Making, in
Figueira, J.,  Greco, S. and Ehrgott, M. (eds.), \textit{Multiple
Criteria Decision Analysis: State of the Art Surveys},  Springer, New York, pp. 345-407.


\bibitem{SiskosEtAl05} Siskos, Y., Grigoroudis, V., Matsatsinis, N., 2005.
  UTA methods, in Figueira, J.,  Greco, S. and Ehrgott, M. (eds.), \textit{Multiple
Criteria Decision Analysis: State of the Art Surveys},  Springer, New York, pp. 297-343.


%\bibitem{Shapley}  Shapley, L.S., 1953. A value for n-person games. In Kuhn, H. W.,
 %Tucker, A. W., (eds) \textit{Contributions to the Theory of Games II}. Princeton University Press, Princeton, pp. 307-317.

%\bibitem{sgm} S{\l}owi\'{n}ski, R., Greco, S., Matarazzo, B., 2005. Rough set based decision support, chapter 16, in: E.K. Burke and G. Kendall (eds.), \textit{Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques}, Springer, New York, pp. 475-527.

\bibitem{srini2psyc73a} Srinivasan, V., Shocker, A.D., 1973. Estimating the weights for multiple attributes in a composite criterion using pairwise judgments. \textit{Psychometrika}, 38, 473-493.

%\bibitem{Sugeno}  Sugeno, M., 1974. \textit{Theory of fuzzy integrals and its applications}.
%PhD thesis, Tokyo Institute of Technology, Tokyo.


%\bibitem{Weber:1985}  Weber, M., 1985. A method of multiattribute decision making with incomplete information. \textit{Management Science}, 31 (11), 1365-1371.




\end{thebibliography}


\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Even if multiple attribute additive utility is the most well known aggregation model, some critics has been advanced to it because it does not permit to represent interaction between considered criteria. For example, in evaluating a car one can consider criteria such as maximum speed, acceleration and price. In this case, very often there is negative interaction (redundancy) between maximum speed and acceleration in evaluating cars: in fact a car with a high maximum speed very often has also a good acceleration and therefore, even if these two criteria can be very important for a person liking sport cars, their comprehensive importance is smaller than the importance of the two criteria considered separately. In the same decision problem about cars, very often there is positive interaction (synergy) between maximum speed and price in evaluating cars: in fact a car that with a high maximum speed, has often also a high price, and therefore a car with a high maximum speed and a not so high price is very well appreciated. So, the comprehensive importance of these two criteria is greater than the importance of the two criteria considered separately.
Within MCDA the interaction of criteria has been considered through \textit{non-additive integrals} such as Choquet integral \cite{Choquet} and Sugeno integral \cite{Sugeno} (for a comprehensive survey on the use of non-additive integrals in MCDA see \cite{Grabisch:1996, Grabisch:2005}).



\begin{itemize}
        \item $S(g_1(a),g_1(b),\cdots , g_n(a),g_n(b)=1$ if

\begin{itemize}
        \item $ \frac{\sum_{i=1}^n{k_i} s_i(a,b)}{\sum_{i=1}^n{k_i}}>s$, and
        \item $g_i(b) - g_i(a) <v_i$ for all $i=1, \ldots, n$
\end{itemize}
\item $S(g_1(a),g_1(b),\cdots , g_n(a),g_n(b)=-1$ otherwise.

\end{itemize}

where

%\begin{itemize}
%       \item $s_i(a,b)=$
%       \end{itemize}

\begin{equation}
       \begin{array}{l}
          s_i(a,b)=
          \left\{
          \begin{array}{l}
             1 \; \mbox{if } \;\;\;\;\;\;\;\;\;\;\;\;\;\; g_i(a) \ge g_i(b)-q_i \\
             \frac{g_i(a)-g_i(b)+q_i}{p_i-q_i}\\
             0 \; \mbox{if } \;\;\;\;\;\;\;\;\;\;\;\;\;\; g_i(a) < g_i(b)-p_i \\
          \end{array}
          \right.
          %\right \} \; \; \; \; \forall \; \; a,b \in A^R \\
          %\; u_i(x_i^{j+1})-u_i(x_i^j)\ge 0, \;i=1, ..., n, \;j=1, ..., \gamma_i-1\\
          %\; u_i(\alpha_i)=0, \; i=1, ..., n\\
          %\; \sum_{i=1}^n u_i(\beta_i)=1\\
          %\; u_i(x_i^j) \ge 0, i=1, ..., n,  \; j=1, ..., \gamma_i
          \end{array}
\end{equation}


\noindent where $u_i$ are non-decreasing marginal value functions  for $i=1,2, \cdots, n.$



%\begin{itemize}
%       \item $s_i(a,b)=$
%       \end{itemize}

\begin{equation}
       \begin{array}{l}
          s_i(a,b)=
          \left\{
          \begin{array}{l}
             1 \; \mbox{if } \;\;\;\;\;\;\;\;\;\;\;\;\;\; g_i(a) \ge g_i(b)-q_i \\
             \frac{g_i(a)-g_i(b)+q_i}{p_i-q_i}\\
             0 \; \mbox{if } \;\;\;\;\;\;\;\;\;\;\;\;\;\; g_i(a) < g_i(b)-p_i \\
          \end{array}
          \right.
          %\right \} \; \; \; \; \forall \; \; a,b \in A^R \\
          %\; u_i(x_i^{j+1})-u_i(x_i^j)\ge 0, \;i=1, ..., n, \;j=1, ..., \gamma_i-1\\
          %\; u_i(\alpha_i)=0, \; i=1, ..., n\\
          %\; \sum_{i=1}^n u_i(\beta_i)=1\\
          %\; u_i(x_i^j) \ge 0, i=1, ..., n,  \; j=1, ..., \gamma_i
          \end{array}
\end{equation}


\noindent where $u_i$ are non-decreasing marginal value functions  for $i=1,2, \cdots, n.$





The concordance test involves calculation of concordance index $C(a,b)$. It represents the strength of the coalition of criteria being in favor of $aSb$. This coalition is composed of two subsets of criteria:
\begin{itemize}
  \item subset of criteria being clearly in favor of $aSb$, i.e. such that  $g_j(a) \geq g_j(b) - q_j$,
  \item subset of criteria that do not oppose to $aSb$, while being in an ambiguous position with respect to this assertion; these are those criteria for which a weak preference relation  $bQa$ holds; i.e. such that  $g_j(b) - p_j \leq g_j(a) < g_j(b) - q_j$.
\end{itemize}

Consequently, the concordance index is defined as
\begin{equation}
\label{concord}
C(a,b)=\frac{\sum_{j=1}^n \phi_j(a,b) \times k_j}{\sum_{j=1}^n k_j},
\end{equation}


\noindent where, for $j=1, \ldots ,n$,
\begin{equation}
\label{phi}
\phi_j(a,b) = \left\{
           \begin{array}{ll}
             1, & \hbox{if \ $g_j(a) \geq g_j(b)-q_j$,} \\
             \frac{g_j(a) - [g_j(b)-p_j]}{p_j-q_j}, & \hbox{if \ $g_j(b)-p_j \leq g_j(a) < g_j(b)-q_j$,} \\
             0, & \hbox{if \ $g_j(a) < g_j(b)-p_j$.}
           \end{array}
         \right.
\end{equation}

\noindent $\phi_j(a,b)$ is a marginal concordance index, indicating to what extend criterion $g_j$ contributes to the concordance index $C(a,b)$. As defined by (\ref{phi}), $\phi_j(a,b)$ is a piecewise-linear function, non-decreasing with respect to $g_j(a) - g_j(b)$.


Recently, the ordinal regression paradigm has been revisited with the aim of considering the whole set of value
functions compatible with the preference information provided by the DM, instead of a single compatible value function
used, for example, in UTA-like methods (\cite{LagrezeSiskos1982}, and \cite{SiskosEtAl05}). This extension has been
implemented in a method called $UTA^{GMS}$ \cite{GrecoEtAl07},
further generalized in another method called GRIP \cite{FigueiraGrSl07}. $UTA^{GMS}$ and GRIP are not revealing to
the DM one compatible value function, but they are  using the whole set of compatible (general, not piecewise-linear
only) additive value functions to set up a necessary weak preference relation and a possible weak preference relation
in the whole set of considered solutions.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The ordinal regression method for learning one compatible additive piecewise-linear value function}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The preference information may be either direct or indirect, depending whether it specifies directly values of some
parameters used in the preference model (e.g. trade-off weights, aspiration levels, discrimination thresholds, etc.)
or, whether it specifies some examples of holistic judgments from which compatible values of the preference model
parameters are induced. Eliciting direct preference information from the DM can be counterproductive in real-world
decision making situations because of a high cognitive effort required. Consequently, asking directly the DM to
provide values for the parameters seems to make the DM uncomfortable. Eliciting indirect preference is less demanding
of the cognitive effort. Indirect preference information is mainly used in the ordinal regression paradigm. According
to this paradigm, a holistic preference information on a subset of some reference or training solutions is known first
and then a preference model compatible with the information is built and applied to the whole set of solutions in
order to rank them.\\

The ordinal regression paradigm is concordant with the posterior rationality postulated by March in \cite{March78}.
It has been known for at least fifty years in the field of multidimensional analysis. It is also concordant with the
induction principle used in machine learning. This paradigm has been applied within the two main Multiple Criteria
Decision Analysis (MCDA) approaches mentioned above: those using a value function as preference model
(\cite{srini2psyc73a}, \cite{peke2mana74}, \cite{LagrezeSiskos1982}, \cite{SiskosEtAl05}), and those using an
outranking relation as preference model (\cite{kiss3dss94}, \cite{mous2jogo98}). This paradigm has also been used
since mid nineties' in MCDA methods involving a new, third family of preference models - a set of dominance decision
rules induced from rough approximations of holistic preference relations (\cite{Grecoetal1999}, \cite{greco3ejor01} and
\cite{12-MErgJFigSGre2005}).\\

Recently, the ordinal regression paradigm has been revisited with the aim of considering the whole set of value
functions compatible with the preference information provided by the DM, instead of a single compatible value function
used, for example, in UTA-like methods (\cite{LagrezeSiskos1982}, and \cite{SiskosEtAl05}). This extension has been
implemented in a method called $UTA^{GMS}$ \cite{GrecoEtAl07},
further generalized in another method called GRIP \cite{FigueiraGrSl07}. $UTA^{GMS}$ and GRIP are not revealing to
the DM one compatible value function, but they are  using the whole set of compatible (general, not piecewise-linear
only) additive value functions to set up a necessary weak preference relation and a possible weak preference relation
in the whole set of considered solutions.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Concepts: definitions and notation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We are considering a multiple criteria decision problem where a finite set of solutions $A = \{ x, \ldots, y, \ldots $
$w, \ldots \}$ is evaluated on a family $F=\{g_1,g_2,\ldots,g_m\}$ of $m$ criteria. Let $I=\{1,2,\ldots,m\}$ denote
the set of criteria indices. We assume, without loss of generality, that the greater $g_i(x)$, the better solution $x$
on criterion $g_i$, for all $i \in I$, $x \in A$. A DM is willing to rank the solutions of $A$ from the best to the
worst, according to his/her preferences. The ranking can be complete or partial, depending on the preference
information provided by the DM and on the way of exploiting this information. The family of criteria $F$ is supposed
to satisfy consistency conditions, i.e. completeness (all relevant criteria are considered), monotonicity (the better
the evaluation of a solution on the considered criteria, the more it is preferable to another), and non-redundancy (no
superfluous criteria are considered), see \cite{RoyBo93}.\\

Such a decision-making problem statement is called {\it multiple criteria ranking problem}. It is known that the only
information coming out from the formulation of this problem is the dominance ranking. Let us recall that in the
dominance ranking, solution $x \in A$ is preferred to solution $y \in A$,  $x \succ y$, if and only if $g_i(x) \geq
g_i(y)$ for all $i \in I$, with at least one strict inequality. Moreover, $x$ is indifferent to $y$, $x \sim y$, if
and only if $g_i(x) = g_i(y)$ for all $i \in I$. Hence, for any two solutions $x, y \in A$, one of the four situations
may arise in the dominance ranking:  $x \succ y$, $y \succ x$, $x \sim y$ and $x ? y$, where the last one means that
$x$ and $y$ are incomparable. Usually, the dominance ranking is very poor, i.e. the most frequent situation is $x ?
y$.\\

In order to enrich the dominance ranking, the DM has to provide preference information which is used to construct an
aggregation model making the solutions more comparable. Such an aggregation model is called preference model. It
induces a preference structure on set $A$, whose proper exploitation permits to work out a ranking proposed to the
DM.\\

In what follows, the evaluation of each solution $x \in A$ on each criterion $g_i \in F$ will be denoted either by
$g_i(x)$ or $x_i$.

Let $G_i$ denote the value set (scale) of criterion $g_i$, $i \in I$. Consequently,

\[
G = \prod_{i \in I}G_i
\]

\noindent  represents the evaluation space, and $x \in G$ denotes a
profile of a solution in such a space. We consider a weak preference
relation $\succeq$ on $A$ which means, for each pair of vectors,
$x,y \in G$,

\[
x \succeq y \Leftrightarrow  \mbox{``$x$ is at least as good as
$y$''}.
\]

\noindent This weak preference relation can be decomposed into its asymmetric and symmetric parts, as follows,

\begin{itemize}
\item[$1)$]  $x \succ y$ $\equiv$  $[ x \succeq y \; \mbox{and not} \; y \succeq x ]$   $\Leftrightarrow$ ``$x$ is preferred to $y$'', and
\item[$2)$]  $x \sim y$  $\equiv$  $[ x \succeq y \; \mbox{and} \;    y \succeq x ]$  $\Leftrightarrow$ ``$x$ is indifferent to $y$''.
\end{itemize}

\noindent From a pragmatic point of view, it is reasonable to assume that $G_i \subseteq \Bbb{R}$, for $i=1,\ldots,m$.
More specifically, we will assume that the evaluation scale on each criterion $g_i$ is bounded, such that $G_i =
[\alpha_i, \beta_i]$, where $\alpha_i$, $\beta_i$, $\alpha_i <  \beta_i$ are the worst and the best (finite)
evaluations, respectively. Thus, $g_i \; : \; A \rightarrow G_i $, $i \in I$. Therefore, each solution $x \in A$ is
associated with an evaluation vector denoted by  $\underline{g}(x) = (x_1, x_2, \ldots, x_m) \in G$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The UTA method for a multiple criteria ranking problem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section, we recall the principle of the ordinal regression {\it via} linear programming, as proposed in the
original UTA method, see \cite{LagrezeSiskos1982}.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Preference information}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The preference information is given in the form of a complete preorder on a subset of reference solutions $A^R
\subseteq A$ (where $\vert A^R \vert = p$), called {\it reference preorder}. The reference solutions are usually those
contained in set $A$ for which the DM is able to express holistic preferences. Let  $A^R = \{a, b, c, \ldots \}$ be
the set of reference solutions.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{An additive model}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The additive value function is defined on $A$ such that for each $\underline{g}(x) \in G$,

\begin{equation}
U(\underline{g}(x)) = \sum_{i \in I}u_i(g_i(x_i)),
\end{equation}

\noindent where, $u_i$ are non-decreasing marginal value functions, $u_i: G_i \rightarrow \Bbb{R}$, $i \in I$. For the
sake of simplicity, we shall write $(1)$ as  follows,



\begin{equation}
U(x) = \sum_{i \in I}u_i(x_i).
\end{equation}

In the UTA method, the marginal value functions $u_i$ are assumed to be piecewise-linear functions. The ranges
$[\alpha_i, \beta_i]$ are divided into $\gamma_i \geq 1$ equal sub-intervals,

\[
 [x_{i}^{0}, x_{i}^{1}], [x_{i}^{1}, x_{i}^{2}], \ldots [x_{i}^{\gamma_i - 1}, x_{i}^{\gamma_i}]
\]

\noindent where,

\[
 x_{i}^{j} = \alpha_i + \frac{j}{\gamma_i}(\beta_i - \alpha_i), \; \; j = 0, \ldots, \alpha_i, \; \mbox{and} \; i \in I.
\]

The marginal value of a solution $x \in A$ is obtained by linear interpolation,

\begin{equation}
 u_i(x) =
u_i(x_{i}^{j}) + \frac{x_i - x_{i}^{j} }{x_{i}^{j+1} -
x_{i}^{j}}(u_i(x_{i}^{j+1}) - u_i(x_{i}^{j})), \; \; \mbox{for} \;
\;  x_i \in [x_{i}^{j}, x_{i}^{j+1}].
\end{equation}

The piecewise-linear additive model is completely defined by the marginal values at the breakpoints, i.e.
$u_i(x_i^0)=u_i(\alpha_i), u_i(x_i^1), u_i(x_i^2), ... , u_i(x_i^{\gamma_i})=u_i(\beta_i)$.

In what follows, the principle of the UTA method is described as it was recently presented by \cite{SiskosEtAl05}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%555

Therefore, a value function $U(x)=\sum_{i=1}^n u_i(x_i)$ is compatible if it satisfies the following set of
constraints

\begin{equation}\label{UTA-CS}
       \begin{array}{l}
          \left.
          \begin{array}{l}
             U(a) > U(b) \Leftrightarrow \; a \succ b \\
             U(a) = U(b) \Leftrightarrow \; a \sim b \\
          \end{array}
          \right \} \; \; \; \; \forall \; \; a,b \in A^R \\
          \; u_i(x_i^{j+1})-u_i(x_i^j)\ge 0, \;i=1, ..., n, \;j=1, ..., \gamma_i-1\\
          \; u_i(\alpha_i)=0, \; i=1, ..., n\\
          \; \sum_{i=1}^n u_i(\beta_i)=1\\
          %\; u_i(x_i^j) \ge 0, i=1, ..., n,  \; j=1, ..., \gamma_i
          \end{array}
\end{equation}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Checking for compatible value functions through linear programming}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

To verify if a compatible value function $U(x)=\sum_{i=1}^n u_i(x_i)$ restoring the reference preorder $\succeq$ on
$A^R$ exists, one can solve the following linear programming problem, where $u_i(x_i^j), i=1, ..., n, \;j=1, ...,
\gamma_i$, are unknown, and $\sigma^+(a), \sigma^-(a)$ $(a \in A^R)$ are auxiliary variables:

\begin{equation}\label{UTA-LP}
  \begin{array}{rl}
    Min \rightarrow & F=\sum_{a \in A^R}^m\left(\sigma^+(a) + \sigma^-(a)\right)\\
    \mbox{s.t.}\\
    &
       \begin{array}{l}
          \left.
          \begin{array}{l}
             U(a)+\sigma^+(a)-\sigma^-(a) \ge \\
             \;\;\;\;\;\; U(b)+\sigma^+(b)-\sigma^-(b)+ \varepsilon
              \; \Leftrightarrow \; a \succ b\\
             U(a)+\sigma^+(a)-\sigma^-(a) =\\
             \;\;\;\;\;\; U(b)+\sigma^+(b)-\sigma^-(b)
              \; \Leftrightarrow \; a \sim b \\
          \end{array}
          \right \} \forall a,b \in A^R  \\
          \; u_i(x_i^{j+1})-u_i(x_i^j)\ge 0, \;i=1, ..., n, \;j=1, ..., \gamma_i-1\\
          \; u_i(\alpha_i)=0, \; i=1, ..., n\\
          \; \sum_{i=1}^n u_i(\beta_i)=1\\
          \; \sigma^+(a), \; \sigma^-(a) \ge 0, \; \forall a \in A^R \\
          %\; u_i(x_i^j) \ge 0, i=1, ..., n,  \; j=1, ..., \gamma_i



       \end{array}
       \end{array}
\end{equation}

\noindent where, $\varepsilon$ is an arbitrarily small positive value so that $U(a)+\sigma^+(a)-\sigma^-(a) >
U(b)+\sigma^+(b)-\sigma^-(b)$ in case of $a \succ b$.\\

If the optimal value of the objective function of program (\ref{UTA-LP}) is equal to zero ($F^*=0$), then there exists
at least one value function $U(x)=\sum_{i=1}^n u_i(x_i)$ satisfying (\ref{UTA-CS}), i.e. compatible with the reference
preorder on $A^R$. In other words, this means that the corresponding polyhedron (\ref{UTA-CS}) of feasible solutions
for $u_i(x_i^j), \; i=1, ..., n, \; j=1, ..., \gamma_i$, is not empty.\\

Let us remark that the transition from the preorder $\succeq$ to the marginal value function exploits the ordinal
character of the criterion scale $G_i$. Note, however, that the scale of the marginal value function is a conjoint
interval scale. More precisely, for the considered additive value function $\sum_{i=1}^n u_i(x_i)$, the admissible
transformations on the marginal value functions $u_i(x_i)$ have the form $u_i^*(x_i)= k \times u_i(x_i) + h_i$,
$h_i\in \mathbb{R}, \; i=1,\ldots, n$, $k>0$, such that for all $[x_1,...,x_n], [y_1,...,y_n] \in \prod_{i=1}^n G_i$

$$
\sum_{i=1}^n u_i(x_i) \ge \sum_{i=1}^n u_i(y_i) \Leftrightarrow
\sum_{i=1}^n u_i^*(x_i) \ge \sum_{i=1}^n u_i^*(y_i).
$$

An alternative way of representing the same preference model is:

\begin{equation}\label{alternate-U-def}
  U(x)=\sum_{i \in I} w_i \hat u_i(x),
\end{equation}


\noindent where  $\; \;
  \hat{u}(\alpha_i)=0, \; \hat{u}(\beta_i)=1, \; w_i \ge 0 \; \;
  \forall i \in I, \; \; \mbox{and} \; \; \sum_{i \in I}w_i=1$.
Note that the correspondence between (\ref{alternate-U-def}) and (2) is such that $w_i=u_i(\beta_i),\; \forall i \in
G$. Due to the cardinal character of the marginal value function scale, the parameters $w_i$ can be interpreted as
tradeoff weights among marginal value functions $\hat u_i(x)$. We will use, however, the preference model (2) with
normalization constraints bounding $U(x)$ to the interval $[0,1]$.\\

When the optimal value of the objective function of the program (\ref{UTA-LP}) is greater than zero ($F^*>0$), then
there is no value function $U(x)=\sum_{i \in I} u_i(x_i)$ compatible with the reference preorder on $A^R$. In such a
case, three possible moves can be considered:

\begin{itemize}
  \item increasing the number of linear pieces $\gamma_i$ for one or several
        marginal value function $u_i$ could make it possible
        to find an additive value function compatible with the reference
        preorder on $A^R$;
  \item revising the reference preorder on $A^R$ could lead to find an additive
        value function compatible with the new preorder;
  \item searching over the relaxed domain $F \le F^*+\eta$
        could lead to an additive value function giving a preorder on $A^R$
        sufficiently close to the reference preorder (in the sense of Kendall's $\tau$).
\end{itemize}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Computational issues}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{compu-issue}

In order to conclude the truth or falsity of binary relations $\succeq^{N}$, $\succeq^{P}$, $\succeq^{\ast^{N}}$,
$\succeq^{\ast^{P}}$, $\succeq^{\ast^{N}}_i$ and $\succeq^{\ast^{P}}_i$, we have to take into account that, for all
$x,y,w,z \in A$ and $i \in I$:

\begin{itemize}
\item[$1)$] $x \succeq^{N} y  \Leftrightarrow  \inf \Big\{ U(x) - U(y) \Big\}  \geq  0$,
\item[$2)$] $x \succeq^{P} y  \Leftrightarrow  \inf \Big\{ U(y) - U(x)  \Big\}  \leq  0$,
\item[$3)$] $(x,y) \succeq^{\ast^{N}} (w,z)  \Leftrightarrow   \inf \Big\{ \Big( U(x) - U(y) \Big) - \Big(U(w) - U(z) \Big)  \Big\} \geq  0$,
\item[$4)$] $(x,y) \succeq^{\ast^{P}} (w,z)  \Leftrightarrow   \inf \Big\{ \Big( U(w) - U(z) \Big) - \Big(U(x) - U(y) \Big)  \Big\} \leq   0$,
\item[$5)$] $(x,y) \succeq^{\ast^{N}}_i (w,z) \Leftrightarrow  \inf \Big\{ \Big( u_i(x_i) - u_i(y_i) \Big) - \Big( u_i(w_i) - u_i(z_i) \Big)  \Big\} \geq  0$,
\item[$6)$] $(x,y) \succeq^{\ast^{P}}_i (w,z) \Leftrightarrow  \inf \Big\{ \Big( u_i(w_i) - u_i(z_i) \Big) - \Big( u_i(x_i) - u_i(y_i) \Big)  \Big\} \leq  0$.
\end{itemize}

\noindent with the infimum calculated on the set of value functions satisfying constraints from $a)$ to $i)$. Let us
remark, however, that the linear programming is not able to handle strict inequalities such as the above $a)$, $c)$,
and $f)$. Moreover, linear programming permits to calculate the minimum or the maximum of an objective function and
not an infimum. Nevertheless, reformulating properly the above properties $1)$ to $6)$, a result presented in
\cite{Marichal:2000} permits to use linear programming for testing the truth of binary relations,
 $\succeq^{N}$, $\succeq^{P}$, $\succeq^{\ast^{N}}$,
$\succeq^{\ast^{P}}$, $\succeq^{\ast^{N}}_i$ and
$\succeq^{\ast^{P}}_i$.

In order to use such a result, constraints $a)$, $c)$ and $f)$ have to be reformulated as follows:

\begin{itemize}
\item[$a^{\prime})$] $U(x) \geq U(y) + \varepsilon \; \; \mbox{if} \; \;  x \succ y$;
\item[$c^{\prime})$] $U(x)-U(y) \geq U(w)-U(z)+ \varepsilon \; \; \mbox{if} \; \; (x,y) \succ^{\ast} (w,z)$;
\item[$f^{\prime})$] $u_i(x)-u_i(y) \geq u_i(w)- u_i(z) + \varepsilon \; \; \mbox{if} \; \; (x,y) \succ^{\ast}_i (w,z)$.
\end{itemize}

\noindent with  $ \varepsilon > 0$.

After properties $1)-6)$ have to be reformulated such that the search of the infimum is replaced by the calculation of
the minimum value of $\varepsilon$ on the set of value functions satisfying constraints from $a)$ to $i)$, with
constraints $a)$, $c)$, and $f)$ transformed to $a^{\prime})$, $c^{\prime})$, and $f^{\prime})$, plus constraints
specific for each point:

\begin{itemize}
\item[$1^{\prime})$] $x \succeq^{N} y  \Leftrightarrow \varepsilon^\ast >
0$, \\
 where $\varepsilon^\ast = \min \; \varepsilon$, subject to
the constraints $a')$, $b)$, $c')$, $d)$, $e)$, $f')$, plus the
constraint $U(x)\ge U(y)$;
\item[$2^{\prime})$] $x \succeq^{P} y   \Leftrightarrow \varepsilon^\ast
\le 0$, \\
 where $\varepsilon^\ast = \min \; \varepsilon$, subject to
the constraints $a')$, $b)$, $c')$, $d)$, $e)$, $f')$, plus the
constraint $U(y)\ge U(x)+ \varepsilon $;
\item[$3^{\prime})$] $(x,y) \succeq^{\ast^{N}} (w,z)
\Leftrightarrow \varepsilon^\ast > 0$, \\
 where $\varepsilon^\ast = \min \; \varepsilon$, subject to
the constraints $a')$, $b)$, $c')$, $d)$, $e)$, $f')$, plus the
constraint $\Big( (U(x) - U(y) \Big) - \Big( U(w) - U(z)) \Big) \geq
0$;
\item[$4^{\prime})$] $(x,y) \succeq^{\ast^{P}} (w,z)
\Leftrightarrow \varepsilon^\ast
\le 0$, \\
 where $\varepsilon^\ast = \min \; \varepsilon$, subject to
the constraints $a')$, $b)$, $c')$, $d)$, $e)$, $f')$, plus the
constraint $\Big( (U(w) - U(z) \Big) - \Big( U(x) - U(y)) \Big) \geq
\varepsilon$;
\item[$5^{\prime})$] $(x,y) \succeq^{\ast^{N}}_i (w,z)
\Leftrightarrow \varepsilon^\ast > 0$, \\
 where $\varepsilon^\ast = \min \; \varepsilon$, subject to
the constraints $a')$, $b)$, $c')$, $d)$, $e)$, $f')$, plus the
constraint $\Big( u_i(x_i) - u_i(y_i) \Big) - \Big( u_i(w_i) -
u_i(z_i) \Big) \geq  0$;
\item[$6^{\prime})$] $(x,y) \succeq^{\ast^{P}}_i (w,z)
\Leftrightarrow \varepsilon^\ast
\le 0$, \\
 where $\varepsilon^\ast = \min \; \varepsilon$, subject to
the constraints $a')$, $b)$, $c')$, $d)$, $e)$, $f')$, plus the
constraint $\Big( (u_i(w_i) - u_i(z_i) \Big) - \Big( u_i(x_i) -
u_i(y_i) \Big) \geq \varepsilon$.
\end{itemize}


On the basis of (\ref{Uconsistent_1}), we can state that formally, a general additive compatible value function is an additive value function $U(a)=\sum_{i=1}^n u_i(a)$
satisfying the following set of constraints:
\begin{itemize}
\item[]
\begin{equation*}\label{E}
  \left .
       \begin{array}{l}
          \left .
          \begin{array}{l}
             U(a) > U(b) \; \Leftrightarrow \; L^{DM}(a^*) > R^{DM}(b^*)\\
                       \end{array}
          \right \} \forall a^*,b^* \in A^*\\
          \;u_i(g_i(a_{\tau_i(j)}))-u_i(g_i(a_{\tau_i(j-1)}))\ge 0, \;i=1, ..., n, \;j=2, ..., m\\
          \;u_i(g_i(a_{\tau_i(1)}))\ge 0, u_i(g_i(a_{\tau_i(m)}))\le u_i(\beta_i),\;i=1, ..., n, \\
          \;u_i(\alpha_i)=0, \; i=1, ..., n\\
          \;\sum_{i=1}^n u_i(\beta_i)=1, \; \\
                \end{array}
       \right \} \; (E^{A^*})
\end{equation*}\\
\end{itemize}


\noindent where $\tau_i$ is the permutation on the set of indices of alternatives from $A^*$ that reorders them
according to the increasing evaluation on criterion $g_i$, i.e.
$$
g_i(a_{\tau_i(1)}) \le g_i(a_{\tau_i(2)}) \le \ldots \le
g_i(a_{\tau_i(m-1)})\le g_i(a_{\tau_i(m)})
$$

Let us observe that the set of constraints $(E^{A^*})$ is equivalent to

\begin{itemize}
\item[]
\begin{equation*}\label{E1}
  \left .
       \begin{array}{l}
          \left .
          \begin{array}{l}
             U(a^*) \ge U(b^*)+\varepsilon \; \Leftrightarrow \; L^{DM}(a^*) > R^{DM}(b^*)\\
                       \end{array}
          \right \} \forall a^*,b^* \in A^*\\
          \;u_i(g_i(a_{\tau_i(j)}))-u_i(g_i(a_{\tau_i(j-1)}))\ge 0, \;i=1, ..., n, \;j=2, ..., m\\
          \;u_i(g_i(a_{\tau_i(1)}))\ge 0, u_i(g_i(a_{\tau_i(m)}))\le u_i(\beta_i),\;i=1, ..., n, \\
          \;u_i(\alpha_i)=0, \; i=1, ..., n\\
          \;\sum_{i=1}^n u_i(\beta_i)=1, \; \\
                \end{array}
       \right \} \; (E^{A^*})'
\end{equation*}\\
\end{itemize}
with $\varepsilon>0$.
Thus to verify that the set of all compatible value functions $\cal U_{\mbox{\textit{A}*}}$ is not empty it is sufficient to verify that $\varepsilon^*>0$, where $\varepsilon^*=max \; \varepsilon$ subject to set of constraints $(E^{A^*})'$.



To compute the the possible and the necessary assignment $C_P(a)$ and $C_N(a)$, we can consider the following indices:

\begin{itemize}
        \item minimum possible class:

\begin{equation}
\label{LNC} L^{\cal U}_P(a)  =  Max\left \{ L^{DM}(a^*) : \forall U \in{\cal{U}_A^*}, U(a^*)\le U(a), \; a^*\in A^* \right \},
\end{equation}
\item potentially minimum necessary class:

\begin{equation}
\label{LPC} L^{\cal U}_N(a) = Max\left \{ L^{DM}(a^*) : \exists U \in{\cal{U}_A^*} \mbox{ for which } U(a^*)\le U(a), \; a^*\in A^* \right \},
\end{equation}

\item potentially maximum necessary class:

\begin{equation}
\label{UPC} R^{\cal U}_N(a) = Min\left \{ R^{DM}(a^*) : \exists U \in{\cal{U}_A^*} \mbox{ for which } U(a)\le U(a^*), \; a^*\in A^* \right \},
\end{equation}

\item maximum possible class:

\begin{equation}
\label{UNC} R^{\cal U}_P(a) = Min\left \{ R^{DM}(a^*) : \forall U \in{\cal{U}_A^*}, U(a)\le U(a^*), \; a^*\in A^* \right \}.
\end{equation}


\end{itemize}

Using indices $L^{\cal U}_P(a)$, $L^{\cal U}_N(a)$, $R^{\cal U}_N(a)$ and  $R^{\cal U}_P(a)$, the possible and the necessary assignment $C_P(a)$ and $C_N(a)$ can be expressed as follows:

$$
C_P(a)=[L^{\cal U}_P(a),R^{\cal U}_P(a)]
$$

\noindent and, if  $L^{\cal U}_N(a) \le R^{\cal U}_N(a)$, then

$$
C_N(a)=[L^{\cal U}_N(a),R^{\cal U}_N(a)]
$$

\noindent while, if  $L^{\cal U}_N(a) > R^{\cal U}_N(a)$, then

$$
C_N(a)=\emptyset.
$$

On the basis of the set of all compatible value functions $\cal U_{\mbox{\textit{A}*}}$, as in the methods UTA$^{\mbox{\scriptsize GMS}}$ and GRIP, we can define two binary relations on the set of all alternatives $A$:
\begin{itemize}
        \item \textit{necessary} weak preference relation $\succeq^N$, in case $U(a) \ge U(b)$ for all compatible value functions, and
        \item \textit{possible} weak preference relation $\succeq^P$, in case $U(a) \ge U(b)$ for at least one compatible value function.
\end{itemize}

Using necessary weak preference relation $\succeq^N$ and possible weak preference relation $\succeq^P$ we can redefine indices $L^{\cal U}_P(a)$, $L^{\cal U}_N(a)$, $R^{\cal U}_N(a)$ and  $R^{\cal U}_P(a)$ as follows:


\begin{itemize}
        \item minimum possible class:

\begin{equation}
\label{LNC_1} L^{\cal U}_P(a)  =  Max\left \{ L^{DM}(a^*) : a \succeq^N a^*, a^*\in A^* \right \},
\end{equation}
\item potentially minimum necessary class:

\begin{equation}
\label{LPC_1} L^{\cal U}_N(a) = Max\left \{ L^{DM}(a^*) : a \succeq^P a^*, a^*\in A^* \right \},
\end{equation}

\item potentially maximum necessary class:

\begin{equation}
\label{UPC_1} R^{\cal U}_N(a) = Min\left \{ R^{DM}(a^*) : a^* \succeq^P a, a^*\in A^* \right \},
\end{equation}

\item maximum possible class:

\begin{equation}
\label{UNC_1} R^{\cal U}_P(a) = Min\left \{ R^{DM}(a^*) : a^* \succeq^N a, a^*\in A^* \right \}.
\end{equation}


\end{itemize}

Thus, using necessary weak preference relation $\succeq^N$ and possible weak preference relation $\succeq^P$, it is possible to deal quite simply with the sorting problem.\\



Therefore, on the basis of the above observations, the following example-based sorting procedure can be proposed:
\begin{enumerate}
        \item Asking DM exemplary sorting.
        \item Verify that the set of compatible value functions ${\cal U}_{A^*}$ is not empty.
        \item Calculate the necessary and the possible weak preference relations $a \succeq^N a^*$, $a \succeq^P a^*$,  $a^* \succeq^N a$ and  $a^* \succeq^N a$, with $a^* \in A^*$ and $a \in A$.
        \item Calculate for each $a\in A$ the indices $L^{\cal U}_P(a)$, $L^{\cal U}_N(a)$, $R^{\cal U}_N(a)$ and  $R^{\cal U}_P(a)$ using (\ref{LNC_1}), (\ref{LPC_1}),(\ref{UPC_1}) and (\ref{UNC_1}).
        \item Assign to each $a \in A$ its possible assignment $C_P(a)=[L^{\cal U}_P(a),R^{\cal U}_P(a)]$.
        \item Assign to each $a \in A$ its necessary assignment which is $C_N(a)=[L^{\cal U}_N(a),R^{\cal U}_N(a)]$ in case $L^{\cal U}_N(a)\le R^{\cal U}_N(a)$ and $C_N(a)=\emptyset$ otherwise.
\end{enumerate}


In \cite{FGMS2008} has been proposed to consider also information about intensity of preference within UTADIS$^{\mbox{\scriptsize GMS}}$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The preference information provided by the decision makers}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Each DM $d_h \in D$ is expected to provide the following preference information:
\begin{itemize}
\item  A partial preorder $\succeq^{d_h}$ on $A^R$ whose meaning is: for $a,b \in A^R$
\[
 a \succeq^{d_h} b \Leftrightarrow    a \;  \mbox{is at least as good as} \; y \mbox{ for } d_h.
\]
$\succ^{d_h}$ (preference) is the asymmetric part of $\succeq^{d_h}$ and  $\sim^{d_h}$ (indifference) is its symmetric part.


\item  A partial preorder $\succeq^{\ast d_h}$ on $A^R \times A^R$, whose meaning is: for $a, b,  c, d \in A^R$,
\[
(a,b) \succeq^{\ast} (c, d)  \Leftrightarrow   \;  \mbox{$a$ is
preferred to $b$ at least as much as $c$ is preferred to $d$} \mbox{ by } d_h .
\]
Also in this case,  $\succ^{\ast d_h}$ is the asymmetric part of $\succeq^{\ast d_h}$  and $\sim^{\ast d_h}$ is its symmetric
part.

\item  A partial preorder $\succeq_{i}^{\ast d_h}$ on $A^R \times A^R$, whose meaning is: for $a, b, c, d \in A^R$,  $(a,b) \succeq_{i}^{\ast d_h} (c, d)$  $\Leftrightarrow$     $a$ is preferred to $b$ at least as much as $c$ is preferred to $d$ on criterion $g_i$, $i \in I$,  by  $d_h$ .
\end{itemize}

As in $UTA^{GMS}$ and in GRIP, we also consider the weak preference relation
$\succeq_i$ which is not provided by the DMs, but it is obtained directly from the
evaluation of alternative $a$ and $b$ on criterion $g_i$.


Using the above preference information,  possible and necessary preference relations $\succeq_{d_h}^P$ and $\succeq_{d_h}^N$ are calculated for all decision maker $d_h \in cal DM$ and then the four prefernce relations
$\succeq_{D'}^{N,N}, \succeq_{D'}^{N,P}, \succeq_{D'}^{P,N}\succeq_{D'}^{P,P}$ can be determined for all subset of DMs $D' \subseteq        \cal DM$.









%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{An illustrative example}  %%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


In this section, we present a didactic example proposed in \cite{FGMS_Dagstuhl} illustrating how robust ordinal regression can support the DM to specify his/her preferences in a multiobjective optimization problem.   In this didactic example, we shall imagine an interaction with a fictitious DM so as to
exemplify and illustrate the type of interaction proposed in our methodology. \\

{\small
\begin{table}
 \label{TableEffSolution}
 \caption{The whole set of Pareto optimal solutions for the example MOO problem}
\[
\begin{array}{clclc}\hline
 ~~ & s_{1 }  ~=~ ( 14.5 , 147 , 4 , 1014 , 5.25 )           & ~~~ &  s_{11} ~=~ ( 15.75 , 164.375 , 41.5 , 311 , 6.5 )    & ~~ \\
 ~~ & s_{2 }  ~=~ ( 13.25 , 199.125 , 4 , 1014 , 4 )         & ~~~ &  s_{12} ~=~ ( 13.25 , 181.75 , 41.5 , 311 , 4 )       & ~~ \\
 ~~ & s_{3 }  ~=~ ( 15.75 , 164.375 , 16.5 , 838.25 , 5.25 ) & ~~~ &  s_{13} ~=~ ( 12 , 199.125 , 41.5 , 311 , 2.75 )      & ~~ \\
 ~~ & s_{4 }  ~=~ ( 12 , 181.75 , 16.5 , 838.25 , 4 )        & ~~~ &  s_{14} ~=~ ( 17 , 147 , 16.5 , 662.5 , 5.25 )        & ~~ \\
 ~~ & s_{5 }  ~=~ ( 12 , 164.375 , 54 , 838.25 , 4 )         & ~~~ &  s_{15} ~=~ (15.75 , 199.125 , 16.5 , 311 , 6.5 )     & ~~ \\
 ~~ & s_{6 }  ~=~ ( 13.25 , 199.125 , 29 , 662.5 , 5.25 )    & ~~~ &  s_{16} ~=~ ( 13.25 , 164.375 , 54 , 311 , 4 )        & ~~ \\
 ~~ & s_{7 }  ~=~ ( 13.25 , 147 , 41.5 , 662.5 , 5.25 )      & ~~~ &  s_{17} ~=~ ( 17 , 181.75 , 16.5 ,486.75 , 5.25 )     & ~~ \\
 ~~ & s_{8 }  ~=~ ( 17 , 216.5 , 16.5 , 486.75 , 1.5 )       & ~~~ &  s_{18} ~=~ ( 14.5 , 164.375 , 41.5 , 838.25 , 4)     & ~~ \\
 ~~ & s_{9 }  ~=~ ( 17 , 147 , 41.5 , 486.75 , 5.25 )        & ~~~ &  s_{19} ~=~ ( 15.75 , 181.75 , 41.5 , 135.25 , 5.25 ) & ~~ \\
 ~~ & s_{10 } ~=~ ( 15.75 , 216.5 , 41.5 , 662.5 , 1.5 )     & ~~~ &  s_{20} ~=~ ( 15.75 , 181.75 , 41.5 , 311 , 2.75 )    & ~~ \\ \hline
\end{array}
\]
\end{table}
}

We consider a MOO problem that involves five objectives that are to be maximized. Let us consider a subset $A$ of the
Pareto Frontier of a MOO problem consisting of 20 solutions (see Table \ref{TableEffSolution}). Note that this set $A$
is be computed using MOO or EMO algorithms (see e.g. \cite{BDMS}). Let us suppose that the reference sample $A^R$
of solutions from set $A$ is the following: $A^R~=~\{ s_1, s_2, s_4, s_5, s_8, s_{10} \}$. For the sake of simplicity,
we shall consider the set $A^R$ constant across iterations (although the interaction scheme permits $A^R$ to evolve
during the process). For the same reason, we will suppose that the DM expresses preference information only in terms
of pairwise comparisons of solutions in $A^R$ (intensity of preference
will not be expressed in the preference information).\\

The DM does not see any satisfactory solution in the reference sample $A^R$ ($s_1$, $s_2$, $s_4$ and $s_5$ have too
weak evaluations on the first criterion, while $s_8$ and $s_{10}$ have the worst evaluation in $A$ on the last
criterion), and wishes to find a satisfactory solution in $A$. Obviously, solutions in $A$ are not comparable unless
preference information is expressed by the DM. In this perspective, he/she provides a first
comparison: $s_1 \succ s_2$. \\

Considering the provided preference information, we can compute the necessary and possible rankings on set $A$
(computation of this example were performed using the GNU-UTA software package \cite{gnu-uta}; note that the
$UTA^{GMS}$ and $GRIP$ methods are also implemented in the Decision Deck software platform \cite{decision-deck}). The
DM decided to consider the necessary ranking only, as it has more readable graphical representation than the possible
ranking at the stage of relatively poor preference information. The partial preorder of the necessary ranking is
depicted in Fig. \ref{it1} and shows the comparisons that hold for all additive value functions compatible with the
information provided by the DM (i.e., $s_1 \succ s_2$). It should be observed that the computed partial preorder
contains the preference information provided by the DM (dashed arrow), but also additional comparisons that result
from the initial information (continuous arrows); for instance, $s_{3} \succ^N s_{4}$ holds as $U(s_{3})>U(s_{4})$
holds for each compatible value function.

          \begin{center}
            \begin{figure}[h]
              \begin{center}
              \unitlength=1cm
              \begin{pspicture}(0,0)(7,2)
                \psset{linewidth=0.5pt}
                \psset{arcangle=0}
                \psset{arrows=->,labelsep=2pt}
                \cnodeput(0,2){s1}{$s_1$}
                \cnodeput(0,0){s2}{$s_2$}
                \cnodeput(1,2){s3}{$s_3$}
                \cnodeput(1,0){s4}{$s_4$}
                \cnodeput(4,2){s5}{$s_5$}
                \cnodeput(5,2){s6}{$s_6$}
                \cnodeput(6,2){s7}{$s_7$}
                \cnodeput(7,2){s8}{$s_8$}
                \cnodeput(2,2){s9}{$s_{9}$}
                \cnodeput(4,1){s10}{$s_{10}$}
                \cnodeput(3,2){s11}{$s_{11}$}
                \cnodeput(2,0){s12}{$s_{12}$}
                \cnodeput(3,0){s13}{$s_{13}$}
                \cnodeput(5,1){s14}{$s_{14}$}
                \cnodeput(6,1){s15}{$s_{15}$}
                \cnodeput(7,1){s16}{$s_{16}$}
                \cnodeput(4,0){s17}{$s_{17}$}
                \cnodeput(5,0){s18}{$s_{18}$}
                \cnodeput(6,0){s19}{$s_{19}$}
                \cnodeput(7,0){s20}{$s_{20}$}
                \psset{labelsep=1pt,nrot=:U}
                \ncarc[arcangle=0,linewidth=1pt,linestyle=dashed]{->}{s1}{s2}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s3}{s4}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s9}{s12}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s9}{s13}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s11}{s12}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s11}{s13}%\naput{{\tiny [0,10]}}
             \end{pspicture}
             \end{center}
             \caption{Necessary partial ranking at the first iteration}
             \label{it1}
            \end{figure}
         \end{center}

Analyzing this first result, the DM observes that the necessary ranking is still very poor which makes it difficult to
discriminate among the solutions in $A$. He/she reacts by stating that $s_{4}$ is preferred to $s_{5}$. Considering
this new piece of preference information, the necessary ranking is computed again and shown in Fig. \ref{it2}. At this
second iteration, it should be observed that the resulting necessary ranking has been enriched as compared to the
first iteration (bold arrows), narrowing the set of ``best choices'', i.e., solutions that are not preferred by any
other solution in the necessary ranking: \{$s_1$, $s_3$,
$s_6$, $s_8$, $s_{10}$, $s_{14}$, $s_{15}$, $s_{17}$, $s_{18}$, $s_{19}$, $s_{20}$ \}.\\

          \begin{center}
            \begin{figure}[h]
              \begin{center}
              \unitlength=1cm
              \begin{pspicture}(0,0)(6,5)
                \psset{linewidth=0.5pt}
                \psset{arcangle=0}
                \psset{arrows=->,labelsep=2pt}
                \cnodeput(0,1.5){s1}{$s_1$}
                \cnodeput(0,0){s2}{$s_2$}
                \cnodeput(1,3){s3}{$s_3$}
                \cnodeput(1,1.5){s4}{$s_4$}
                \cnodeput(1,0){s5}{$s_5$}
                \cnodeput(2,3){s6}{$s_6$}
                \cnodeput(2,1.5){s7}{$s_7$}
                \cnodeput(5,4.5){s8}{$s_8$}
                \cnodeput(3,3){s9}{$s_{9}$}
                \cnodeput(6,4.5){s10}{$s_{10}$}
                \cnodeput(4,3){s11}{$s_{11}$}
                \cnodeput(3,1.5){s12}{$s_{12}$}
                \cnodeput(4,1.5){s13}{$s_{13}$}
                \cnodeput(5,3){s14}{$s_{14}$}
                \cnodeput(4,4.5){s15}{$s_{15}$}
                \cnodeput(2,0){s16}{$s_{16}$}
                \cnodeput(3,4.5){s17}{$s_{17}$}
                \cnodeput(6,3){s18}{$s_{18}$}
                \cnodeput(5,1.5){s19}{$s_{19}$}
                \cnodeput(6,1.5){s20}{$s_{20}$}
                \psset{labelsep=1pt,nrot=:U}
                \ncarc[arcangle=0,linewidth=1pt,linestyle=dashed]{->}{s1}{s2}%\naput{{\tiny [0,10]}}
                \ncarc[arcangle=0,linewidth=1pt,linestyle=dashed]{->}{s4}{s5}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s3}{s4}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s9}{s12}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s9}{s13}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s11}{s12}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s11}{s13}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0,linewidth=1pt]{->}{s3}{s16}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0,linewidth=1pt]{->}{s6}{s7}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=25,linewidth=1pt]{->}{s6}{s16}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0,linewidth=1pt]{->}{s17}{s9}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0,linewidth=1pt]{->}{s15}{s11}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0,linewidth=1pt]{->}{s12}{s16}%\naput{{\tiny [0,10]}}
             \end{pspicture}
             \end{center}
             \caption{Necessary partial ranking at the second iteration}
             \label{it2}
            \end{figure}
         \end{center}

The DM believes that this necessary ranking is still insufficiently decisive and adds a new comparison: $s_{8}$ is
preferred to $s_{10}$. Once again, the necessary ranking is computed and shown in Fig. \ref{it3}.


          \begin{center}
            \begin{figure}[h]
              \begin{center}
              \unitlength=1cm
              \begin{pspicture}(0,0)(8,5)
                \psset{linewidth=0.5pt}
                \psset{arcangle=0}
                \psset{arrows=->,labelsep=2pt}
                \cnodeput(0,1.5){s1}{$s_1$}
                \cnodeput(0,0){s2}{$s_2$}
                \cnodeput(1,3){s3}{$s_3$}
                \cnodeput(1,1.5){s4}{$s_4$}
                \cnodeput(1,0){s5}{$s_5$}
                \cnodeput(2,3){s6}{$s_6$}
                \cnodeput(3,1.5){s7}{$s_7$}
                \cnodeput(0,4.5){s8}{$s_8$}
                \cnodeput(4,3){s9}{$s_{9}$}
                \cnodeput(0,3){s10}{$s_{10}$}
                \cnodeput(7,3){s11}{$s_{11}$}
                \cnodeput(4,1.5){s12}{$s_{12}$}
                \cnodeput(6,1.5){s13}{$s_{13}$}
                \cnodeput(5.5,4.5){s14}{$s_{14}$}
                \cnodeput(7,4.5){s15}{$s_{15}$}
                \cnodeput(2,0){s16}{$s_{16}$}
                \cnodeput(4,4.5){s17}{$s_{17}$}
                \cnodeput(2,4.5){s18}{$s_{18}$}
                \cnodeput(3,3){s19}{$s_{19}$}
                \cnodeput(6,3){s20}{$s_{20}$}
                \psset{labelsep=1pt,nrot=:U}
                \ncarc[arcangle=0,linewidth=1pt,linestyle=dashed]{->}{s1}{s2}%\naput{{\tiny [0,10]}}
                \ncarc[arcangle=0,linewidth=1pt,linestyle=dashed]{->}{s4}{s5}%\naput{{\tiny [0,10]}}
                \ncarc[arcangle=0,linewidth=1pt,linestyle=dashed]{->}{s8}{s10}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s3}{s4}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s9}{s12}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s9}{s13}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s11}{s12}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s11}{s13}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s3}{s16}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s6}{s7}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s6}{s16}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s17}{s9}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s15}{s11}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0]{->}{s12}{s16}%\naput{{\tiny [0,10]}}
% \ncarc[linecolor=black,arcangle=0]{->}{s17}{s7}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0,linewidth=1pt]{->}{s17}{s19}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0,linewidth=1pt]{->}{s17}{s20}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=20,linewidth=1pt]{->}{s14}{s7}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=10,linewidth=1pt]{->}{s14}{s12}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=-20,linewidth=1pt]{->}{s14}{s13}%\naput{{\tiny [0,10]}}
                \ncarc[linecolor=black,arcangle=0,linewidth=1pt]{->}{s9}{s7}%\naput{{\tiny [0,10]}}
             \end{pspicture}
             \end{center}
             \caption{Necessary partial ranking at the third iteration}
             \label{it3}
            \end{figure}
         \end{center}


At this stage, the set of possible ``best choices'' has been narrowed down to a limited number of solutions, among
which $s_{14}$ and $s_{17}$ are judged satisfactory by the DM. In fact, these two solutions have a very good
performance on the first criterion without any ``dramatic'' evaluation on the other criteria.\\

The current example stops at this step, but the DM could then decide to provide further preference information to
enrich the necessary ranking. He/she could also compute new Pareto optimal solution ``close'' to $s_{14}$ and $s_{17}$
to zoom investigations in this area. In this example we have shown that the proposed interactive process supports the
DM in choosing most satisfactory solutions, without imposing any strong cognitive effort, as the only information
required is a holistic information.



%\begin{center}
%  \begin{figure}[h!]
%    \begin{center} %\unitlength=1cm
% \resizebox{13cm}{!}{\includegraphics*[0pt,0pt][1288pt,774pt]{Dagtsuhl32b.jpg}}%\textwidth
%    \end{center}
%  \caption{Partial preorder on the set of Pareto optimal solutions at the second iteration} \label{iter2}
%  \end{figure}
%\end{center}




%\vfill\newpage



Another interesting decision model permitting to represent interactions between criteria is the Dominance-based Rough Set Approach (DRSA) \cite{greco3ejor01}, which represents DM's preferences by means of decision rules, i.e. easily understandable "if..., then..." statements, such as "if the maximum speed is at least 200Km/h and the price is not larger than  70,000 \$, then the car is good". In general, we shall call the decision models which, differently from multiple attribute additive utility, permit to represent the interaction between criteria  \textit{non-additive decision models}.

Within MCDA, many methods have been proposed to determine the parameters characterizing the considered decision model in a direct way, i.e. asking them directly to the DM,  or in an indirect way, i.e. inducing the values of such parameters from some holistic preference comparisons of alternative supplied by the DM. In general, this is a difficult task for several reasons, for example because it is acknowledged that  the DM's preference information is often  incomplete, since the DM is not fully aware of the multicriteria approach adopted or the DM's preference structure
is not well defined in her mind (see \cite{Kim:1999} and  \cite{Weber:1985}).


More precisely, we applied an aggregation-disaggregation methodology taking inspiration from the
$\mbox{UTA}^{\mbox{\footnotesize GMS}}$  and the GRIP method, but including also
some preference information on the sign and intensity of interaction among couples of criteria.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Linear programming constraints}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this subsection, we present a set of constraints that interprets the preference information in terms of conditions
on the compatible value functions.

The value function $U : A \rightarrow [0, 1]$ should satisfy the following constraints corresponding to DM's
preference information,

\begin{itemize}
\item[$a)$] $U(w) > U(z)$ if $w \succ z$
\item[$b)$] $U(w) = U(z)$ if $w \sim z$
\item[$c)$] $U(w) - U(z) > U(x) - U(y)$ if $(w,z) \succ^{\ast} (x, y)$
\item[$d)$] $U(w) - U(z) = U(x) - U(y)$ if $(w,z) \sim^{\ast} (x, y)$
\item[$e)$] $u_i(w) \geq u_i(z)$ if $w \succeq_i z$, $i \in I$
\item[$f)$] $u_i(w) - u_i(z) > u_i(x) - u_i(y)$ if $(w,z) \succ^{\ast}_{i} (x, y)$, $i \in I$
\item[$g)$] $u_i(w) - u_i(z) = u_i(x) - u_i(y)$ if $(w,z) \sim^{\ast}_{i} (x, y)$, $i \in I$
\end{itemize}

Let us remark that within UTA-like methods, constraint $a)$ is written as $U(w) \geq U(z)+ \varepsilon$, where
$\varepsilon > 0$ is a threshold exogenously introduced. Analogously, constraints $c)$ and $f)$ should be written as,

\[
U(w) - U(z) \geq U(x) - U(y) + \varepsilon
\]
\noindent and
\[
u_i(w)- u_i(z) \geq u_i(x)- u_i(y) + \varepsilon.
\]

However, we would like to avoid the use of any exogenous  parameter and, therefore, instead of setting an arbitrary
value of $\varepsilon$, we consider it as an auxiliary variable, and we test the feasibility of constraints $a)$,
$c)$, and $f)$, see \ref{compu-issue}. This permits to take into account all possible value functions, even those
having a very small preference threshold $\varepsilon$. This is safer also from the viewpoint of ``objectivity'' of
the used methodology. In fact,  the value of $\varepsilon$ is not meaningful in itself and it is useful only because
it permits to discriminate preference from indifference.

Moreover, the following normalization constraints should also be taken into account:

\begin{itemize}
\item[$h)$] $u_i(x_{i}^{\ast}) = 0$, where $x_{i}^{\ast}$ is such that $x_{i}^{\ast} = \min\{ g_i(x) \; : \; x \in A
\}$; \vspace{0.3cm}
\item[$i)$] $\sum_{i \in I}u_i(y_{i}^{\ast}) = 1$, where $y_{i}^{\ast}$ is such that $y_{i}^{\ast} = \max\{ g_i(x) \; : \; x \in A \}$
\end{itemize}

\noindent If the constraints from $a)$ to $i)$ are fulfilled, then the partial preorders $\succeq$ and
$\succeq^{\ast}$ on $A^R$ can be extended on $A$.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The preference information provided by the decision makers}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Each DM $d_h \in D$ is expected to provide the following preference information:
\begin{itemize}
\item  A partial preorder $\succeq^{d_h}$ on $A^R$ whose meaning is: for $a,b \in A^R$
\[
 a \succeq^{d_h} b \Leftrightarrow    a \;  \mbox{is at least as good as} \; y \mbox{ for } d_h.
\]
$\succ^{d_h}$ (preference) is the asymmetric part of $\succeq^{d_h}$ and  $\sim^{d_h}$ (indifference) is its symmetric part.


\item  A partial preorder $\succeq^{\ast d_h}$ on $A^R \times A^R$, whose meaning is: for $a, b,  c, d \in A^R$,
\[
(a,b) \succeq^{\ast} (c, d)  \Leftrightarrow   \;  \mbox{$a$ is
preferred to $b$ at least as much as $c$ is preferred to $d$} \mbox{ by } d_h .
\]
Also in this case,  $\succ^{\ast d_h}$ is the asymmetric part of $\succeq^{\ast d_h}$  and $\sim^{\ast d_h}$ is its symmetric
part.

\item  A partial preorder $\succeq_{i}^{\ast d_h}$ on $A^R \times A^R$, whose meaning is: for $a, b, c, d \in A^R$,  $(a,b) \succeq_{i}^{\ast d_h} (c, d)$  $\Leftrightarrow$     $a$ is preferred to $b$ at least as much as $c$ is preferred to $d$ on criterion $g_i$, $i \in I$,  by  $d_h$ .
\end{itemize}

As in $UTA^{GMS}$ and in GRIP, we also consider the weak preference relation
$\succeq_i$ which is not provided by the DMs, but it is obtained directly from the
evaluation of alternative $a$ and $b$ on criterion $g_i$.



- More in detail we considered
robust ordinal regression for MAUT approach in choice and ranking problems, We recalled the main multiple criteria decision methods to which it has been applied, in particular $UTA^{GMS}$ and GRIP dealing with choice and ranking problems, and $UTADIS^{GMS}$ dealing with sorting (ordinal classification) problems. We presented also robust ordinal regression  applied  to Choquet integral for choice, ranking and sorting problems, with the aim of representing interactions between criteria. Moreover, we described an interactive multiobjective optimization methodology based on robust ordinal regression, and an evolutionary multiobjective optimization method, called NEMO, which is also using the principle of robust ordinal regression. In order to show that robust ordinal regression is a general paradigm, independent of the type of preference model involved, we described the robust ordinal regression methodology for outranking methods and multiple criteria group decision. Finally, we presented an exemplary application of robust ordinal regression methodology. Future research will be related to the development of a user friendly software and to specialization of robust ordinal regression methodology to specific real life problems such us environmental management, financial planning, bankruptcy evaluation, and so on.



Let us remark that preference relations $\succeq^N$ and $\succeq^P$ are meaningful only if there exists at least one
compatible value function. Observe also that in this case, for any $x,y \in A^R$,

\[
x \succeq y \Rightarrow x \succeq^N y
\]

and

\[
x \succ y \Rightarrow \; \mbox{not } (y \succeq^P x).
\]

In fact, if $x \succeq y$, then for any compatible value function, $U(x) \ge U(y)$ and, therefore, $x \succeq^N y$.
Moreover, if $x \succ y$, then for any compatible value function, $U(x) > U(y)$ and, consequently, there is no
compatible value function such that $U(y) \ge U(x)$, which means not($y \succeq^P x$)  

