Simple ranking method using reference profiles:
incremental elicitation of the preference parameters

Arwa Khannoussi, Alexandru-Liviu Olteanu, Christophe Labreuche, Patrick

Meyer

<figure><img src="image_1.png" /></figure>

To cite this version:

Arwa Khannoussi, Alexandru-Liviu Olteanu, Christophe Labreuche, Patrick Meyer. Simple rank-
ing method using reference profiles: incremental elicitation of the preference parameters. 4OR: A
Quarterly Journal of Operations Research, 2021, 20, pp.499-530. 10.1007/s10288-021-00487-w . hal-
03346687

HAL Id: hal-03346687

https://imt-atlantique.hal.science/hal-03346687

Submitted on 29 Mar 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
Simple ranking method using reference profiles:
incremental elicitation of the preference parameters

Arwa Khannoussi, Alexandru-Liviu Olteanu, Christophe Labreuche, Patrick

Meyer

► To cite this version:

Arwa Khannoussi, Alexandru-Liviu Olteanu, Christophe Labreuche, Patrick Meyer. Simple rank-
ing method using reference profiles: incremental elicitation of the preference parameters. 4OR: A
Quarterly Journal of Operations Research, 2021, 20, pp.499-530. 10.1007/s10288-021-00487-w . hal-
03346687

HAL Id: hal-03346687

https://imt-atlantique.hal.science/hal-03346687v1

Submitted on 29 Mar 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# Simple Ranking Method using Reference Profiles : Incremental elicitation of the preference parameters

Arwa Khannoussi · Alexandru-Liviu Olteanu · Christophe Labreuche · Patrick Meyer

Received: date / Accepted: date

**Abstract** The Simple Ranking Method using Reference Profiles (or SRMP) is a Multi-Criteria Decision Aiding (MCDA) technique based on the outranking paradigm, which allows to rank decision alternatives according to the preferences of a decision maker (DM). Inferring the preference parameters of such a model can lead to a cognitive fatigue of the DM, who is often asked to express several preferential statements about pairs of alternatives during the elicitation process. To limit the DM’s effort, we propose in this work an incremental elicitation process to select informative pairs of alternatives to be presented to the DM sequentially with the aim of refining the SRMP model until a robust recommendation can be made. We study several different heuristics for selecting the pair of alternatives to be submitted to the DM at each step. Following extensive numerical experiments we identify one of the proposed heuristics as performing significantly better than the others and we provide several guidelines for its use in practice.

**Keywords** Multi-Criteria Decision Aiding · Incremental elicitation process · Selection heuristic · Reference profiles · Pairwise comparisons

## 1 Introduction

Multi-Criteria Decision Aiding (MCDA) [31] is a methodology to support decision makers (DMs) when multiple criteria have to be taken into consideration, whether

<footnote>A. Khannoussi (corresponding author)</footnote>

<footnote>ERIC EA 3083, Université de Lyon, Université Lumière Lyon 2, France</footnote>

<footnote>E-mail: arwa.khannoussi@univ-lyon2.fr</footnote>

<footnote>A-L. Olteanu</footnote>

<footnote>Lab-STICC, Université Bretagne Sud, Lorient, France</footnote>

<footnote>E-mail: alexandru.olteanu@univ-ubs.fr</footnote>

<footnote>C. Labreuche</footnote>

<footnote>Thales Group, France</footnote>

<footnote>E-mail: christophe.labreuche@thalesgroup.com</footnote>

<footnote>P. Meyer</footnote>

<footnote>IMT Atlantique, Lab-STICC, UMR CNRS 6285, Brest F-29238, France</footnote>

<footnote>E-mail: patrick.meyer@imt-atlantique.fr</footnote>
# Simple Ranking Method using Reference Profiles : Incremental elicitation of the preference parameters

Arwa Khannoussi · Alexandru-Liviu Olteanu · Christophe Labreuche · Patrick Meyer

Received: date / Accepted: date

**Abstract** The Simple Ranking Method using Reference Profiles (or SRMP) is a Multi-Criteria Decision Aiding (MCDA) technique based on the outranking paradigm, which allows to rank decision alternatives according to the preferences of a decision maker (DM). Inferring the preference parameters of such a model can lead to a cognitive fatigue of the DM, who is often asked to express several preferential statements about pairs of alternatives during the elicitation process. To limit the DM’s effort, we propose in this work an incremental elicitation process to select informative pairs of alternatives to be presented to the DM sequentially with the aim of refining the SRMP model until a robust recommendation can be made. We study several different heuristics for selecting the pair of alternatives to be submitted to the DM at each step. Following extensive numerical experiments we identify one of the proposed heuristics as performing significantly better than the others and we provide several guidelines for its use in practice.

**Keywords** Multi-Criteria Decision Aiding · Incremental elicitation process · Selection heuristic · Reference profiles · Pairwise comparisons

## 1 Introduction

Multi-Criteria Decision Aiding (MCDA) [31] is a methodology to support decision makers (DMs) when multiple criteria have to be taken into consideration, whether

<footnote>A. Khannoussi (corresponding author)</footnote>

<footnote>ERIC EA 3083, Université de Lyon, Université Lumière Lyon 2, France</footnote>

<footnote>E-mail: arwa.khannoussi@univ-lyon2.fr</footnote>

<footnote>A-L. Olteanu</footnote>

<footnote>Lab-STICC, Université Bretagne Sud, Lorient, France</footnote>

<footnote>E-mail: alexandru.olteanu@univ-ubs.fr</footnote>

<footnote>C. Labreuche</footnote>

<footnote>Thales Group, France</footnote>

<footnote>E-mail: christophe.labreuche@thalesgroup.com</footnote>

<footnote>P. Meyer</footnote>

<footnote>IMT Atlantique, Lab-STICC, UMR CNRS 6285, Brest F-29238, France</footnote>

<footnote>E-mail: patrick.meyer@imt-atlantique.fr</footnote>
the goal is to choose among a set of decision alternatives, sort them into predefined categories, or rank them from the “best” to the “worst” one. A large variety of MCDA techniques have been proposed to help the DM solve complex decision problems by taking into account his/her preferences and are roughly classified into three approaches [7, 14] (1) Multi-Attribute Value Theory (MAVT) [20], (2) outranking-based approaches [15] and (3) rule-based models [18].

Whatever the type of the method, the preferences of the DM have to be elicited (by learning or inferring the model parameters).

An indirect elicitation approach can be used in practice, where the DM is only asked to express holistic judgments on alternatives (like assignment examples, a partial pre-order on the alternatives, pairwise comparisons of alternatives, ...). In the literature, the indirect approach can be divided into two categories [23]: the first, where the learning data are given prior to the learning algorithm as a *batch* [7], and the second, called *incremental elicitation* [4, 10], in which the learning data arrives sequentially and the preference model is improved iteratively.

A standard setting in incremental elicitation is to start from a predefined set of alternatives and present queries to a DM typically in the form of pairwise comparisons of alternatives from this set. One can mention configuration problems in which the DM has to choose a product among many defined in a combinatorial space [5,2].

Compared to a batch setting, incremental preference elicitation should first of all decrease the number of necessary holistic judgements that the DM has to provide. Second, by decreasing this number, it should decrease the overall cognitive effort of the DM (even if certain of the judgements might be harder to make).

We consider, in this paper, the topic of incremental learning of the parameters of the Simple Ranking Method using Reference Profiles (SRMP) [6,29]. This method is based on the outranking paradigm and allows to rank decision alternatives according to the preferences of a DM. It is very useful in real-world applications as it can easily handle heterogeneous evaluation scales, while at the same time constructing a transitive global weak preference relation. Its similarity to normative outranking-based sorting approaches also helps to justify the decision recommendations [8]. SRMP constructs a ranking of alternatives by comparing them in pairs to a set of reference profiles [29,28].

Through this contribution, we first propose an incremental elicitation process of SRMP models and guidelines for selecting pairs of alternatives to present to the DM during this process with the aim of reducing his/her cognitive effort. We then study various selection heuristics, and determine experimentally, on a very large number of artificially generated data, which ones perform best on average. We show that, when adopting the proposed selection heuristic, it is possible to reduce the number of iterations of the incremental elicitation process, compared to a random selection strategy.

The rest of this article is structured in the following way: Section 2 introduces the SRMP model and presents a state of the art on incremental elicitation. Section 3 presents the proposed incremental elicitation process of SRMP models, detailing the selection heuristics for selecting learning pairs of alternatives and the generation of intermediate SRMP models. Section 4 provides an experimental analysis, using generated data, of several process components (learning set heuristics and SRMP model generation). We finish with the concluding remarks and perspectives for future work in Section 5.
the goal is to choose among a set of decision alternatives, sort them into predefined categories, or rank them from the “best” to the “worst” one. A large variety of MCDA techniques have been proposed to help the DM solve complex decision problems by taking into account his/her preferences and are roughly classified into three approaches [7, 14] (1) Multi-Attribute Value Theory (MAVT) [20], (2) outranking-based approaches [15] and (3) rule-based models [18].

Whatever the type of the method, the preferences of the DM have to be elicited (by learning or inferring the model parameters).

An indirect elicitation approach can be used in practice, where the DM is only asked to express holistic judgments on alternatives (like assignment examples, a partial pre-order on the alternatives, pairwise comparisons of alternatives, ...). In the literature, the indirect approach can be divided into two categories [23]: the first, where the learning data are given prior to the learning algorithm as a *batch* [7], and the second, called *incremental elicitation* [4, 10], in which the learning data arrives sequentially and the preference model is improved iteratively.

A standard setting in incremental elicitation is to start from a predefined set of alternatives and present queries to a DM typically in the form of pairwise comparisons of alternatives from this set. One can mention configuration problems in which the DM has to choose a product among many defined in a combinatorial space [5,2].

Compared to a batch setting, incremental preference elicitation should first of all decrease the number of necessary holistic judgements that the DM has to provide. Second, by decreasing this number, it should decrease the overall cognitive effort of the DM (even if certain of the judgements might be harder to make).

We consider, in this paper, the topic of incremental learning of the parameters of the Simple Ranking Method using Reference Profiles (SRMP) [6,29]. This method is based on the outranking paradigm and allows to rank decision alternatives according to the preferences of a DM. It is very useful in real-world applications as it can easily handle heterogeneous evaluation scales, while at the same time constructing a transitive global weak preference relation. Its similarity to normative outranking-based sorting approaches also helps to justify the decision recommendations [8]. SRMP constructs a ranking of alternatives by comparing them in pairs to a set of reference profiles [29,28].

Through this contribution, we first propose an incremental elicitation process of SRMP models and guidelines for selecting pairs of alternatives to present to the DM during this process with the aim of reducing his/her cognitive effort. We then study various selection heuristics, and determine experimentally, on a very large number of artificially generated data, which ones perform best on average. We show that, when adopting the proposed selection heuristic, it is possible to reduce the number of iterations of the incremental elicitation process, compared to a random selection strategy.

The rest of this article is structured in the following way: Section 2 introduces the SRMP model and presents a state of the art on incremental elicitation. Section 3 presents the proposed incremental elicitation process of SRMP models, detailing the selection heuristics for selecting learning pairs of alternatives and the generation of intermediate SRMP models. Section 4 provides an experimental analysis, using generated data, of several process components (learning set heuristics and SRMP model generation). We finish with the concluding remarks and perspectives for future work in Section 5.
# 2 State of the art

## 2.1 Simple Ranking Method using Reference Profiles: SRMP

In outranking methods, an “at least as good as” relation is built between alternatives evaluated on multiple criteria. This binary relation, called “outranking relation” [30] is often denoted by $\succ$. An alternative $a$ outranks an alternative $b$ when a weighted majority of criteria validates the fact that $a$ is performing at least as good as $b$ and there is no criterion where $b$ seriously outperforms $a$. The majority-related condition is usually called concordance, whereas the second condition is called discordance or veto principle. From a computational point of view, various implementations of these conditions, and their combination, have been proposed in the literature (see, e.g., [31]). These various implementations result most of the time in a valued outranking relation, where the value represents the strength of the “at least as good as” statement.

Comparing all the alternatives pair-wisely according to such a relation does not necessarily generate a transitive relation, and may also result in cycles, thus making it impossible to create a complete ranking [15]. It has therefore been proposed by Rolland [29] to use a so-called reference point in the comparison of two alternatives: $a$ is considered as strictly preferred to $b$ if and only if the outranking relation between $a$ and the reference point is stronger than the outranking relation between $b$ and the reference point. Let us now show how this is implemented more formally.

We denote with $\mathcal{A}$ a set of $n$ alternatives and with $\mathcal{M} = \{1, \dots, m\}$ the indexes of $m$ criteria. The evaluation of an alternative $a \in \mathcal{A}$ on criterion $j \in \mathcal{M}$ is denoted with $a_j$. $a$ can therefore be identified with its performance tuple $a = (a_1, \dots, a_m)$. With each criterion is associated a preorder $\succ_j$, s.t. if the DM considers that $a$ is at least as good as $b$ on $j$ then $a_j \succ_j b_j$.

SRMP [29] is an outranking method defined by several parameters, whose values may differ from one DM to another :

- the set of reference profiles $\mathcal{P} = \{p^h, \forall h \in 1..k\}$. These reference profiles dominate each other, i.e. if $p^h \equiv (p_1^h, \dots, p_j^h, \dots, p_m^h)$ and $p^l \equiv (p_1^l, \dots, p_j^l, \dots, p_m^l)$, then $p_j^h \succ_j p_j^l, \forall h, l \in 1..k, h > l, \forall j \in \mathcal{M}$;

- the lexicographic order of the profiles $\sigma$. This corresponds to a permutation on $1..k$ and represents the order in which the profiles will be used when comparing alternatives;

- the criteria weights $w_j \ge 0, \forall j \in \mathcal{M}$, where $\sum_{j \in \mathcal{M}} w_j = 1$.

When comparing two alternatives of $\mathcal{A}$ with respect to a profile $p^h, h \in 1..k$, two situations can arise :

- one alternative (say $a$) is preferred to the other one (say $b$) with respect to $p^h$, i.e. $a \succ_{p^h} b$, which arises if and only if

$$ \sum_{j \in C(a, p^h)} w_j > \sum_{j \in C(b, p^h)} w_j, $$

- the two alternatives (say $a$ and $b$) are indifferent with respect to $p^h$, i.e. $a \sim_{p^h} b$, which arises if and only if

$$ \sum_{j \in C(a, p^h)} w_j = \sum_{j \in C(b, p^h)} w_j, $$
## 2 State of the art

### 2.1 Simple Ranking Method using Reference Profiles: SRMP

In outranking methods, an “at least as good as” relation is built between alternatives evaluated on multiple criteria. This binary relation, called “outranking relation” [30] is often denoted by $\succ$. An alternative $a$ outranks an alternative $b$ when a weighted majority of criteria validates the fact that $a$ is performing at least as good as $b$ and there is no criterion where $b$ seriously outperforms $a$. The majority-related condition is usually called concordance, whereas the second condition is called discordance or veto principle. From a computational point of view, various implementations of these conditions, and their combination, have been proposed in the literature (see, e.g., [31]). These various implementations result most of the time in a valued outranking relation, where the value represents the strength of the “at least as good as” statement.

Comparing all the alternatives pair-wisely according to such a relation does not necessarily generate a transitive relation, and may also result in cycles, thus making it impossible to create a complete ranking [15]. It has therefore been proposed by Rolland [29] to use a so-called reference point in the comparison of two alternatives: $a$ is considered as strictly preferred to $b$ if and only if the outranking relation between $a$ and the reference point is stronger than the outranking relation between $b$ and the reference point. Let us now show how this is implemented more formally.

We denote with $\mathcal{A}$ a set of $n$ alternatives and with $\mathcal{M} = \{1, \dots, m\}$ the indexes of $m$ criteria. The evaluation of an alternative $a \in \mathcal{A}$ on criterion $j \in \mathcal{M}$ is denoted with $a_j$. $a$ can therefore be identified with its performance tuple $a = (a_1, \dots, a_m)$. With each criterion is associated a preorder $\succ_j$, s.t. if the DM considers that $a$ is at least as good as $b$ on $j$ then $a_j \succ_j b_j$.

SRMP [29] is an outranking method defined by several parameters, whose values may differ from one DM to another :

- the set of reference profiles $\mathcal{P} = \{p^h, \forall h \in 1..k\}$. These reference profiles dominate each other, i.e. if $p^h \equiv (p_1^h, \dots, p_j^h, \dots, p_m^h)$ and $p^l \equiv (p_1^l, \dots, p_j^l, \dots, p_m^l)$, then $p_j^h \succ_j p_j^l, \forall h, l \in 1..k, h > l, \forall j \in \mathcal{M}$;

- the lexicographic order of the profiles $\sigma$. This corresponds to a permutation on $1..k$ and represents the order in which the profiles will be used when comparing alternatives;

- the criteria weights $w_j \ge 0, \forall j \in \mathcal{M}$, where $\sum_{j \in \mathcal{M}} w_j = 1$.

When comparing two alternatives of $\mathcal{A}$ with respect to a profile $p^h$, $h \in 1..k$, two situations can arise :

- one alternative (say $a$) is preferred to the other one (say $b$) with respect to $p^h$, i.e. $a \succ_{p^h} b$, which arises if and only if

$$ \sum_{j \in C(a, p^h)} w_j > \sum_{j \in C(b, p^h)} w_j, $$

- the two alternatives (say $a$ and $b$) are indifferent with respect to $p^h$, i.e. $a \sim_{p^h} b$, which arises if and only if

$$ \sum_{j \in C(a, p^h)} w_j = \sum_{j \in C(b, p^h)} w_j, $$
where $C(a, p^h) = \{j \in M : a_j \succsim_j p_j^h\}$ is the set of criteria on which alternative $a \in A$ is at least as good as profile $p^h$.

To rank $a, b \in A$ using the SRMP procedure, we sequentially consider the profiles $p^{\sigma(1)}, p^{\sigma(2)}, \dots, p^{\sigma(k)}$ according to the lexicographic order. Intuitively, a preference between $a$ and $b$ is formed as soon as we encounter a profile in the lexicographic order for which $a$ is preferred to $b$ or vice-versa. Otherwise, $a$ and $b$ are considered as indifferent, which means that no profile has been able to discriminate between them. More formally, for any two alternatives $a, b \in A$, we say that:

- $a$ is strictly preferred to $b$, denoted by $a \succ b$, if and only if:

$$ \exists h \in \{1, \dots, k\} \text{ s.t. } a \succ_{p^{\sigma(h)}} b \text{ and } \forall l < h, a \sim_{p^{\sigma(l)}} b \quad (1) $$

- $a$ is indifferent to $b$, denoted by $a \sim b$, if and only if:

$$ \forall h \in \{1, \dots, k\}, a \sim_{p^{\sigma(h)}} b \quad (2) $$

## 2.2 Illustrative example

To explain how the SRMP ranking method works, we present an illustrative example. We consider a decision problem where different job offers have to be ranked according to a candidate's preferences. Let us consider three job offers x, y and z which are evaluated on three criteria: the *salary* (S) (in k€, the higher, the better), the *location* (L) (in km, the lower, the better) and the *job appeal* (J) (good ≳$_J$ fair ≳$_J$ poor ≳$_J$ very poor). The evaluations of the alternatives on these three criteria are presented in Table 1, along with the preference parameters, which have been previously elicited from the candidate.

<table><caption>**Table 1** Evaluations of the alternatives and SRMP parameters</caption><thead><tr><th></th><th>S</th><th>L</th><th>J</th></tr></thead><tbody><tr><td>x</td><td>41</td><td>2</td><td>good</td></tr><tr><td>y</td><td>46</td><td>4</td><td>poor</td></tr><tr><td>z</td><td>43</td><td>5.5</td><td>fair</td></tr><tr><td>p<sup>1</sup></td><td>42</td><td>5</td><td>poor</td></tr><tr><td>p<sup>2</sup></td><td>45</td><td>3</td><td>good</td></tr><tr><td>w</td><td>1/3</td><td>1/3</td><td>1/3</td></tr><tr><td>σ</td><td colspan="3">(1, 2)</td></tr></tbody></table>

The two reference profiles allow to define three segments on the performances on each criterion: better than $p^2$; between $p^1$ and $p^2$; worse than $p^1$. In other terms, the reference profiles allow to identify an ordered encoding for each criterion defined by three ordered intervals of performances (A, B, and C) as illustrated in Figure 1, such that:

A performances above $p^2$ on each criterion are denoted A (which can be interpreted as “good”).

B performances between $p^1$ and $p^2$ on each criterion are denoted B (which can be interpreted as “intermediate” or “fair”).
where $C(a, p^h) = \{j \in M : a_j \succsim_j p_j^h\}$ is the set of criteria on which alternative $a \in A$ is at least as good as profile $p^h$.

To rank $a, b \in A$ using the SRMP procedure, we sequentially consider the profiles $p^{\sigma(1)}, p^{\sigma(2)}, \dots, p^{\sigma(k)}$ according to the lexicographic order. Intuitively, a preference between $a$ and $b$ is formed as soon as we encounter a profile in the lexicographic order for which $a$ is preferred to $b$ or vice-versa. Otherwise, $a$ and $b$ are considered as indifferent, which means that no profile has been able to discriminate between them. More formally, for any two alternatives $a, b \in A$, we say that:

- $a$ is strictly preferred to $b$, denoted by $a \succ b$, if and only if:

$$ \exists h \in \{1, \dots, k\} \text{ s.t. } a \succ_{p^{\sigma(h)}} b \text{ and } \forall l < h, a \sim_{p^{\sigma(l)}} b \quad (1) $$

- $a$ is indifferent to $b$, denoted by $a \sim b$, if and only if:

$$ \forall h \in \{1, \dots, k\}, a \sim_{p^{\sigma(h)}} b \quad (2) $$

## 2.2 Illustrative example

To explain how the SRMP ranking method works, we present an illustrative example. We consider a decision problem where different job offers have to be ranked according to a candidate's preferences. Let us consider three job offers x, y and z which are evaluated on three criteria: the *salary* (S) (in k€, the higher, the better), the *location* (L) (in km, the lower, the better) and the *job appeal* (J) (good ≳$_J$ fair ≳$_J$ poor ≳$_J$ very poor). The evaluations of the alternatives on these three criteria are presented in Table 1, along with the preference parameters, which have been previously elicited from the candidate.

<table><caption>**Table 1** Evaluations of the alternatives and SRMP parameters</caption><thead><tr><th></th><th>S</th><th>L</th><th>J</th></tr></thead><tbody><tr><td>x</td><td>41</td><td>2</td><td>good</td></tr><tr><td>y</td><td>46</td><td>4</td><td>poor</td></tr><tr><td>z</td><td>43</td><td>5.5</td><td>fair</td></tr><tr><td>p<sup>1</sup></td><td>42</td><td>5</td><td>poor</td></tr><tr><td>p<sup>2</sup></td><td>45</td><td>3</td><td>good</td></tr><tr><td>w</td><td>1/3</td><td>1/3</td><td>1/3</td></tr><tr><td>σ</td><td colspan="3">(1, 2)</td></tr></tbody></table>

The two reference profiles allow to define three segments on the performances on each criterion: better than $p^2$; between $p^1$ and $p^2$; worse than $p^1$. In other terms, the reference profiles allow to identify an ordered encoding for each criterion defined by three ordered intervals of performances (A, B, and C) as illustrated in Figure 1, such that:

A performances above $p^2$ on each criterion are denoted A (which can be interpreted as “good”).

B performances between $p^1$ and $p^2$ on each criterion are denoted B (which can be interpreted as “intermediate” or “fair”).
C performances below $p^1$ on each criterion are denoted C (interpreted as “insufficient”).

The evaluations of the alternatives through this encoding are presented in Table 2.

<table><caption>**Table 2** Encoding of the evaluations of the alternatives</caption><thead><tr><th></th><th>S</th><th>L</th><th>J</th></tr></thead><tbody><tr><th>x</th><td>A</td><td>A</td><td>C</td></tr><tr><th>y</th><td>B</td><td>B</td><td>A</td></tr><tr><th>z</th><td>B</td><td>C</td><td>B</td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>**Fig. 1** SRMP example</figcaption></figure>

To rank the three alternatives according to this SRMP model, we first compare each of the alternatives to the others using the profiles in the lexicographic order $\sigma = (1, 2)$. For $p^1$:

$$ \left. \begin{array}{l} \sum_{j \in C(x, p^1)} w_j = 0 + 1/3 + 1/3 = 2/3 \\ \sum_{j \in C(y, p^1)} w_j = 1/3 + 1/3 + 1/3 = 1 \\ \sum_{j \in C(z, p^1)} w_j = 1/3 + 0 + 1/3 = 2/3 \end{array} \right\} \begin{array}{l} y \succcurlyeq p^1 x \\ y \succcurlyeq p^1 z \\ x \sim p^1 z \end{array} $$

Profile $p^1$ is not able to discriminate between $x$ and $z$, and therefore we continue with profile $p^2$, respecting the lexicographic order.

For $p^2$:

$$ \left. \begin{array}{l} \sum_{j \in C(x, p^2)} w_j = 0 + 1/3 + 1/3 = 2/3 \\ \sum_{j \in C(z, p^2)} w_j = 0 + 0 + 0 = 0 \end{array} \right\} \Rightarrow x \succcurlyeq p^2 z $$

The final ranking is thus $y \succ x \succ z$, hence $y$ is considered as globally the best alternative, followed by $x$ and then by $z$.
C performances below $p^1$ on each criterion are denoted C (interpreted as “insufficient”).

The evaluations of the alternatives through this encoding are presented in Table 2.

<table><caption>**Table 2** Encoding of the evaluations of the alternatives</caption><thead><tr><th></th><th>S</th><th>L</th><th>J</th></tr></thead><tbody><tr><th>x</th><td>A</td><td>A</td><td>C</td></tr><tr><th>y</th><td>B</td><td>B</td><td>A</td></tr><tr><th>z</th><td>B</td><td>C</td><td>B</td></tr></tbody></table>

<figure><img src="image_1.png" /><figcaption>**Fig. 1** SRMP example</figcaption></figure>

To rank the three alternatives according to this SRMP model, we first compare each of the alternatives to the others using the profiles in the lexicographic order $\sigma = (1, 2)$. For $p^1$:

$$ \left. \begin{array}{l} \sum_{j \in C(x, p^1)} w_j = 0 + 1/3 + 1/3 = 2/3 \\ \sum_{j \in C(y, p^1)} w_j = 1/3 + 1/3 + 1/3 = 1 \\ \sum_{j \in C(z, p^1)} w_j = 1/3 + 0 + 1/3 = 2/3 \end{array} \right\} \begin{array}{l} y \succcurlyeq p^1 x \\ y \succcurlyeq p^1 z \\ x \sim p^1 z \end{array} $$

Profile $p^1$ is not able to discriminate between $x$ and $z$, and therefore we continue with profile $p^2$, respecting the lexicographic order.

For $p^2$:

$$ \left. \begin{array}{l} \sum_{j \in C(x, p^2)} w_j = 0 + 1/3 + 1/3 = 2/3 \\ \sum_{j \in C(z, p^2)} w_j = 0 + 0 + 0 = 0 \end{array} \right\} \Rightarrow x \succcurlyeq p^2 z $$

The final ranking is thus $y \succcurlyeq x \succcurlyeq z$, hence $y$ is considered as globally the best alternative, followed by $x$ and then by $z$.
## 2.3 Learning the parameters of an SRMP model

The DM's preferences are usually transformed into values or constraints on the parameters of the MCDA model at hand (e.g. criteria weights, profiles and their lexicographic order for SRMP models). They can be given directly by the DM through a direct preference elicitation approach, however, such an approach is usually too difficult in practice, as the DM needs to have a very good understanding of the MCDA model [25]. Therefore, a second approach, known as indirect elicitation, starts from partial knowledge on the output of the method, such as, for example, pair-wise comparisons of alternatives in the ranking context and infers a set of model parameters that satisfy them. A third option is a mix between the direct and the indirect approaches, where parts of the preference parameters are given directly by the DM, whereas others are inferred through an indirect approach. For example, in the case of an SRMP model, the reference profiles and their lexicographic order could be given directly by the DM, while the criteria weights can be inferred from pairwise comparisons of alternatives.

Recent works propose an indirect elicitation approach for SRMP models where the DM expresses his/her preference through pair-wise comparisons of alternatives that will be used to infer the model's parameters (e.g. criteria weights, profiles and their lexicographic order). In [27], Olteanu et al. formulate the SRMP preference elicitation as a mixed integer linear optimization problem (MIP) defined by a set of linear constraints related to the set of alternatives, the criteria, the number of profiles and the binary comparisons (preference / indifference) of alternatives provided by the DM. Belahcène et al. [1] propose another approach using the Boolean satisfiability (SAT) formulation which consists of a set of boolean variables and logical propositions about these variables. Compared to the previous proposition, this approach is faster and can handle larger sets of pairwise comparisons of alternatives. Liu et al. [22] propose a metaheuristic to elicit the parameters of an SRMP model which is faster than the MIP approach but it does not guarantee that the best model which would perfectly match the provided pair-wise comparisons will be found.

## 2.4 Active learning and incremental preference elicitation

Classically, machine learning methods are defined as algorithms which infer structural information from given data. Some of these techniques restrict themselves to a classical batch setting, where data is given in bulk prior to model training. However, in many applications, data arrives through a constant stream, which requires the model to be adapted continuously.

Active learning [33] focuses on learning in such a streaming setting and where an oracle is used during the process. More precisely, unlike the traditional framework where data is known and imposed, in active learning, it is the learning algorithm that asks for information for specific data. More precisely, these algorithms receive learning data sequentially, one by one or chunk by chunk, and use this data, together with the previously learned model and the oracle's input to produce a new, better model. These algorithms come in three forms in the literature [33]: generation of instances, online and offline learning algorithms. In the first case, new instances that need to be labelled are generated so as to be as informative as
## 2.3 Learning the parameters of an SRMP model

The DM's preferences are usually transformed into values or constraints on the parameters of the MCDA model at hand (e.g. criteria weights, profiles and their lexicographic order for SRMP models). They can be given directly by the DM through a direct preference elicitation approach, however, such an approach is usually too difficult in practice, as the DM needs to have a very good understanding of the MCDA model [25]. Therefore, a second approach, known as indirect elicitation, starts from partial knowledge on the output of the method, such as, for example, pair-wise comparisons of alternatives in the ranking context and infers a set of model parameters that satisfy them. A third option is a mix between the direct and the indirect approaches, where parts of the preference parameters are given directly by the DM, whereas others are inferred through an indirect approach. For example, in the case of an SRMP model, the reference profiles and their lexicographic order could be given directly by the DM, while the criteria weights can be inferred from pairwise comparisons of alternatives.

Recent works propose an indirect elicitation approach for SRMP models where the DM expresses his/her preference through pair-wise comparisons of alternatives that will be used to infer the model's parameters (e.g. criteria weights, profiles and their lexicographic order). In [27], Olteanu et al. formulate the SRMP preference elicitation as a mixed integer linear optimization problem (MIP) defined by a set of linear constraints related to the set of alternatives, the criteria, the number of profiles and the binary comparisons (preference / indifference) of alternatives provided by the DM. Belahcène et al. [1] propose another approach using the Boolean satisfiability (SAT) formulation which consists of a set of boolean variables and logical propositions about these variables. Compared to the previous proposition, this approach is faster and can handle larger sets of pairwise comparisons of alternatives. Liu et al. [22] propose a metaheuristic to elicit the parameters of an SRMP model which is faster than the MIP approach but it does not guarantee that the best model which would perfectly match the provided pair-wise comparisons will be found.

## 2.4 Active learning and incremental preference elicitation

Classically, machine learning methods are defined as algorithms which infer structural information from given data. Some of these techniques restrict themselves to a classical batch setting, where data is given in bulk prior to model training. However, in many applications, data arrives through a constant stream, which requires the model to be adapted continuously.

Active learning [33] focuses on learning in such a streaming setting and where an oracle is used during the process. More precisely, unlike the traditional framework where data is known and imposed, in active learning, it is the learning algorithm that asks for information for specific data. More precisely, these algorithms receive learning data sequentially, one by one or chunk by chunk, and use this data, together with the previously learned model and the oracle's input to produce a new, better model. These algorithms come in three forms in the literature [33]: generation of instances, online and offline learning algorithms. In the first case, new instances that need to be labelled are generated so as to be as informative as
possible for the learning algorithm, whereas in the second case, the learning data
arrives sequentially, and the learning algorithm decides whether it is necessary
to present it to the oracle or not. Offline learning algorithms suppose that there
exists a database of such instances, and select which instances will be presented
to oracle. A few examples of the use of active learning techniques can be found
for the incremental construction of decision trees for classification or regression
[13,17,32] and several incremental SVM models are presented in [35]. Syed Shakib
Sarwar et al. [34] present an approach for active learning in Deep Convolutional
Neural Networks.

In our context, where the decision algorithm is an MCDA algorithm, the ac-
tive learning topic has mostly been tackled from the offline learning point of view,
and is usually called *incremental preference elicitation* [16]. In the MAVT context,
Holloway et al. [19] show the importance of the order of the pair-wise comparisons
in decreasing the number of questions in order to reduce the cognitive effort of
the DM. Ciomek et al. [11] present a set of heuristics to minimize the number
of elicitation questions and prioritize them in the context of *single choice* deci-
sion problems. They conclude that the best performing heuristic depends on the
problem settings (e.g. number of criteria and alternatives). In the same context,
Benabbou et al. [2] select a set of pair-wise questions using a min-max regret strat-
egy. This strategy reduces the number of pair-wise questions but the performance
guarantee is weakened (with some acceptable bounds to the ideal situation). Based
on the min-max regret, it is possible to relax the impossibility for the user to make
mistakes when answering to the queries, thanks to the use of a Bayesian frame-
work [3]. Finally, Olteanu [26] presents strategies for generating alternatives for
an incremental elicitation of majority-rule sorting models.

Inspired by the machine learning field and the previously mentioned work in
MCDA, we choose to study in this work the incremental elicitation of SRMP
models in order to reduce the cognitive effort of the DM during the preference
elicitation process. We therefore propose heuristics to select pairs of alternatives
from an existing database, which the DM has to compare. To our knowledge, no
previous work deals with incremental elicitation for ranking problems and more
specifically with the Simple Ranking Method Using Reference Profiles (SRMP).

**3 Incremental elicitation of SRMP models**

3.1 Incremental elicitation process

In order to decrease the cognitive effort of the DM during the preference elicitation
process, we propose to reduce the number of learning examples which are presented
to him/her, while ensuring at the same time that the learned preference model
represents well enough his/her real preferences.

Therefore, we propose an incremental elicitation process for the SRMP model
which is illustrated in Figure 2. As mentioned in Section 2.4, the classical setting
for incremental elicitation is the existence of a database of alternatives. In the
case of SRMP, the information provided by the DM is under the form of pairwise
comparisons of alternatives. Consequently, here we have as input a database of
pairs of alternatives $\mathcal{D} \subseteq \mathcal{A} \times \mathcal{A}$.
possible for the learning algorithm, whereas in the second case, the learning data arrives sequentially, and the learning algorithm decides whether it is necessary to present it to the oracle or not. Offline learning algorithms suppose that there exists a database of such instances, and select which instances will be presented to oracle. A few examples of the use of active learning techniques can be found for the incremental construction of decision trees for classification or regression [13, 17, 32] and several incremental SVM models are presented in [35]. Syed Shakib Sarwar et al. [34] present an approach for active learning in Deep Convolutional Neural Networks.

In our context, where the decision algorithm is an MCDA algorithm, the active learning topic has mostly been tackled from the offline learning point of view, and is usually called *incremental preference elicitation* [16]. In the MAVT context, Holloway et al. [19] show the importance of the order of the pair-wise comparisons in decreasing the number of questions in order to reduce the cognitive effort of the DM. Ciomek et al. [11] present a set of heuristics to minimize the number of elicitation questions and prioritize them in the context of *single choice* decision problems. They conclude that the best performing heuristic depends on the problem settings (e.g. number of criteria and alternatives). In the same context, Benabbou et al. [2] select a set of pair-wise questions using a min-max regret strategy. This strategy reduces the number of pair-wise questions but the performance guarantee is weakened (with some acceptable bounds to the ideal situation). Based on the min-max regret, it is possible to relax the impossibility for the user to make mistakes when answering to the queries, thanks to the use of a Bayesian framework [3]. Finally, Olteanu [26] presents strategies for generating alternatives for an incremental elicitation of majority-rule sorting models.

Inspired by the machine learning field and the previously mentioned work in MCDA, we choose to study in this work the incremental elicitation of SRMP models in order to reduce the cognitive effort of the DM during the preference elicitation process. We therefore propose heuristics to select pairs of alternatives from an existing database, which the DM has to compare. To our knowledge, no previous work deals with incremental elicitation for ranking problems and more specifically with the Simple Ranking Method Using Reference Profiles (SRMP).

# 3 Incremental elicitation of SRMP models

## 3.1 Incremental elicitation process

In order to decrease the cognitive effort of the DM during the preference elicitation process, we propose to reduce the number of learning examples which are presented to him/her, while ensuring at the same time that the learned preference model represents well enough his/her real preferences.

Therefore, we propose an incremental elicitation process for the SRMP model which is illustrated in Figure 2. As mentioned in Section 2.4, the classical setting for incremental elicitation is the existence of a database of alternatives. In the case of SRMP, the information provided by the DM is under the form of pairwise comparisons of alternatives. Consequently, here we have as input a database of pairs of alternatives $\mathcal{D} \subseteq \mathcal{A} \times \mathcal{A}$.
<figure><img src="image_3.png" /><figcaption>**Fig. 2** Incremental elicitation process (the numbers next to the boxes correspond to the sections of this article in which further details are given).</figcaption></figure>

Once the process is started, the *knowledge base* $\mathcal{L}$ is first set to the empty set. During the process it will contain the pairs of alternatives for which the DM has expressed his / her preferences. At each iteration of the process a heuristic selects a pair of alternatives $(x, y)$ (box (3.2) in Figure 2) from the database $\mathcal{D}$ that will be proposed to the DM. He/she then expresses his/her preferences on this pair of alternatives by comparing them, either in the form of an indifference or of a preference of one alternative over the other. This information is then added to the knowledge base $\mathcal{L}$ containing the comparisons from the previous iterations, which is then used to construct a new SRMP model. When inferring the model (box (3.3) in Figure 2) we may have two outcomes: either i) an SRMP model compatible with $\mathcal{L}$ is found; or ii) no feasible SRMP model is found. In the first case we continue the incremental elicitation process. In the second one, the DM's
<figure><img src="image_2.png" /><figcaption>**Fig. 2** Incremental elicitation process (the numbers next to the boxes correspond to the sections of this article in which further details are given).</figcaption></figure>

Once the process is started, the *knowledge base* $\mathcal{L}$ is first set to the empty set. During the process it will contain the pairs of alternatives for which the DM has expressed his / her preferences. At each iteration of the process a heuristic selects a pair of alternatives $(x, y)$ (box (3.2) in Figure 2) from the database $\mathcal{D}$ that will be proposed to the DM. He/she then expresses his/her preferences on this pair of alternatives by comparing them, either in the form of an indifference or of a preference of one alternative over the other. This information is then added to the knowledge base $\mathcal{L}$ containing the comparisons from the previous iterations, which is then used to construct a new SRMP model. When inferring the model (box (3.3) in Figure 2) we may have two outcomes: either i) an SRMP model compatible with $\mathcal{L}$ is found; or ii) no feasible SRMP model is found. In the first case we continue the incremental elicitation process. In the second one, the DM's
preferences expressed on the last pair of alternatives turn out to be incompatible
with his/her preferences expressed previously. It is then important to solve this
problem in order to continue the incremental elicitation process and have at the
end an SRMP model compatible with all expressed preferences. We propose in the
context of this work to determine the set of subsets of incompatible comparisons
.box (3.4) in Figure 2) and present them to the DM. The DM may change some
of his / her prior comparisons so that all of them are compatible with an SRMP
model or may decide to remove some of them from $\mathcal{L}$ and continue the elicitation
process (box (3.3) in Figure 2). If the DM decides to delete one of the subsets then
he/she agrees that the inferred SRMP model does not take into consideration
this preference information and if later, the obtained model is faced with this
subset of pairs of alternatives, it will generate a different recommendation from
the preferences that he/she initially expressed. After that, the process returns to
the step of finding an SRMP model compatible with $\mathcal{L}$. In the case where the
DM does not agree to change one of the subset comparisons or delete it then the
incremental process stops. Other ways of solving this compatibility problem could
be imagined, as for example adding a missing criterion, or changing the preference
model. However this is beyond the scope of this research.

This procedure is repeated and stops when a “good enough” preference model
is obtained (i.e. the stop condition is verified). It is obvious that “good enough”
might have different definitions, depending on the context of the application, or the
DM. Later in this work (in Section 4.4) we give some advice on how to determine
in practice when to stop the process.

We detail how to select a pair of alternatives at each iteration (box (3.2) in
the Figure 2) in Section 3.2. In Section 3.3 we present the method used to find
a compatible SRMP model with the DM’s preferences. The methodology used to
find the incompatible evaluations (box (3.4) in Figure 2) is detailed in Section 3.4.

## 3.2 Selecting pairs of alternatives

We begin by describing in more detail the second step of the elicitation process,
consisting in selecting the pair of alternatives to present to the DM at each iteration
of the process (the first being the initialization of the knowledge base $\mathcal{L}$ to the
empty set).

As this is an exploratory research topic, we present below several heuristics
which we will evaluate in Section 4 in order to recommend the solution that min-
imizes the number of iterations needed by the proposed elicitation process.

To simplify the notation, we will suppose here, without any loss of general-
ity, that all the evaluations are numerical, and that all the criteria have to be
maximized. The proposed heuristics can easily be adapted to the case where the
criteria have heterogeneous scales. We also denote with $max_j$ (resp. $min_j$) the
highest (resp. lowest) evaluation on criterion $j$.

These heuristics can be divided into two sub-groups: those using only the set
of alternatives and those also using the SRMP model that was built during the
previous iteration of the elicitation process.
preferences expressed on the last pair of alternatives turn out to be incompatible
with his/her preferences expressed previously. It is then important to solve this
problem in order to continue the incremental elicitation process and have at the
end an SRMP model compatible with all expressed preferences. We propose in the
context of this work to determine the set of subsets of incompatible comparisons
.box (3.4) in Figure 2) and present them to the DM. The DM may change some
of his / her prior comparisons so that all of them are compatible with an SRMP
model or may decide to remove some of them from $\mathcal{L}$ and continue the elicitation
process (box (3.3) in Figure 2). If the DM decides to delete one of the subsets then
he/she agrees that the inferred SRMP model does not take into consideration
this preference information and if later, the obtained model is faced with this
subset of pairs of alternatives, it will generate a different recommendation from
the preferences that he/she initially expressed. After that, the process returns to
the step of finding an SRMP model compatible with $\mathcal{L}$. In the case where the
DM does not agree to change one of the subset comparisons or delete it then the
incremental process stops. Other ways of solving this compatibility problem could
be imagined, as for example adding a missing criterion, or changing the preference
model. However this is beyond the scope of this research.

This procedure is repeated and stops when a “good enough” preference model
is obtained (i.e. the stop condition is verified). It is obvious that “good enough”
might have different definitions, depending on the context of the application, or the
DM. Later in this work (in Section 4.4) we give some advice on how to determine
in practice when to stop the process.

We detail how to select a pair of alternatives at each iteration (box (3.2) in
the Figure 2) in Section 3.2. In Section 3.3 we present the method used to find
a compatible SRMP model with the DM’s preferences. The methodology used to
find the incompatible evaluations (box (3.4) in Figure 2) is detailed in Section 3.4.

## 3.2 Selecting pairs of alternatives

We begin by describing in more detail the second step of the elicitation process,
consisting in selecting the pair of alternatives to present to the DM at each iteration
of the process (the first being the initialization of the knowledge base $\mathcal{L}$ to the
empty set).

As this is an exploratory research topic, we present below several heuristics
which we will evaluate in Section 4 in order to recommend the solution that min-
imizes the number of iterations needed by the proposed elicitation process.

To simplify the notation, we will suppose here, without any loss of general-
ity, that all the evaluations are numerical, and that all the criteria have to be
maximized. The proposed heuristics can easily be adapted to the case where the
criteria have heterogeneous scales. We also denote with $max_j$ (resp. $min_j$) the
highest (resp. lowest) evaluation on criterion $j$.

These heuristics can be divided into two sub-groups: those using only the set
of alternatives and those also using the SRMP model that was built during the
previous iteration of the elicitation process.
### 3.2.1 $\mathcal{H}_{\text{rnd}}$: random choice

This heuristic belongs to the first group and is mainly used as a baseline to assess the efficiency of the other heuristics. A random pair of alternatives is selected from the database $\mathcal{D}$ of possible pairs, using a uniform distribution. Consequently, $\mathcal{H}_{\text{rnd}}$ returns the pair $(a, b)_{\text{rnd}}$ such that:

$$ (a, b)_{\text{rnd}} = \text{random}(\mathcal{D}) $$

### 3.2.2 $\mathcal{H}_{\text{sim}}$: similar alternatives

The idea behind this heuristic is to make the DM compare alternatives which are very “similar”. In this particular case, we use an adapted L1 norm $d$, however, other types of distances may be used. Consequently, $\mathcal{H}_{\text{sim}}$ returns the pair $(a, b)_{\text{sim}}$ such that:

$$ (a, b)_{\text{sim}} = \underset{(x,y) \in \mathcal{D}}{\operatorname{argmin}} d(x, y), \quad \text{where } d(x, y) = \frac{1}{m} \sum_{j=1}^{m} \frac{|x_j - y_j|}{\max_j - \min_j}, \quad \forall (x, y) \in \mathcal{D}. $$

### 3.2.3 $\mathcal{H}_{\text{dis}}$: dissimilar alternatives

This heuristic is opposite to the previous one and uses the L1 norm to determine the dissimilarity of pairs of alternatives. Consequently, $\mathcal{H}_{\text{dis}}$ returns the pair $(a, b)_{\text{dis}}$ such that:

$$ (a, b)_{\text{dis}} = \underset{(x,y) \in \mathcal{D}}{\operatorname{argmax}} d(x, y) $$

### 3.2.4 $\mathcal{H}_{\text{cp}}$: alternatives close to a profile

This heuristic belongs to the second class of heuristics and uses the SRMP model from the previous iteration in order to select the following pair of alternatives. During the first iteration we fix a number of pairs (e.g. 10% of the total number of pairs) which are chosen randomly from $\mathcal{D}$ in order to construct a first SRMP model and then iteratively select the following pair using the heuristic detailed below. This initial step will be performed for all heuristics that we will present further.

The concept of using a distance is also maintained here, however we compare an alternative $a \in \mathcal{A}$ to a profile $p^h \in \{p^1, p^2, ..., p^k\}$ of the SRMP model as follows:

$$ d_w(a, p^h) = \frac{1}{m} \sum_{j=1}^{m} \frac{w_j |a_j - p_j^h|}{\max_j - \min_j}, $$

where $w = (w_1, ..., w_m)$ corresponds to the criteria weights of the current SRMP model. This corresponds to a weighted L1 norm between an alternative and a reference profile.

$\mathcal{H}_{\text{cp}}$ selects the pair of alternatives which is closest to the profiles. $\mathcal{H}_{\text{cp}}$ returns the pair $(a, b)_{\text{cp}}$ such that:
### 3.2.1 $\mathcal{H}_{\text{rnd}}$: random choice

This heuristic belongs to the first group and is mainly used as a baseline to assess the efficiency of the other heuristics. A random pair of alternatives is selected from the database $\mathcal{D}$ of possible pairs, using a uniform distribution. Consequently, $\mathcal{H}_{\text{rnd}}$ returns the pair $(a, b)_{\text{rnd}}$ such that :

$$ (a, b)_{\text{rnd}} = \text{random}(\mathcal{D}) $$

### 3.2.2 $\mathcal{H}_{\text{sim}}$: similar alternatives

The idea behind this heuristic is to make the DM compare alternatives which are very “similar”. In this particular case, we use an adapted L1 norm $d$, however, other types of distances may be used. Consequently, $\mathcal{H}_{\text{sim}}$ returns the pair $(a, b)_{\text{sim}}$ such that :

$$ (a, b)_{\text{sim}} = \underset{(x,y) \in \mathcal{D}}{\operatorname{argmin}} d(x, y), \quad \text{where } d(x, y) = \frac{1}{m} \sum_{j=1}^{m} \frac{|x_j - y_j|}{\max_j - \min_j}, \quad \forall (x, y) \in \mathcal{D}. $$

### 3.2.3 $\mathcal{H}_{\text{dis}}$: dissimilar alternatives

This heuristic is opposite to the previous one and uses the L1 norm to determine the dissimilarity of pairs of alternatives. Consequently, $\mathcal{H}_{\text{dis}}$ returns the pair $(a, b)_{\text{dis}}$ such that :

$$ (a, b)_{\text{dis}} = \underset{(x,y) \in \mathcal{D}}{\operatorname{argmax}} d(x, y) $$

### 3.2.4 $\mathcal{H}_{\text{cp}}$: alternatives close to a profile

This heuristic belongs to the second class of heuristics and uses the SRMP model from the previous iteration in order to select the following pair of alternatives. During the first iteration we fix a number of pairs (e.g. 10% of the total number of pairs) which are chosen randomly from $\mathcal{D}$ in order to construct a first SRMP model and then iteratively select the following pair using the heuristic detailed below. This initial step will be performed for all heuristics that we will present further.

The concept of using a distance is also maintained here, however we compare an alternative $a \in \mathcal{A}$ to a profile $p^h \in \{p^1, p^2, ..., p^k\}$ of the SRMP model as follows:

$$ d_w(a, p^h) = \frac{1}{m} \sum_{j=1}^{m} \frac{w_j |a_j - p_j^h|}{\max_j - \min_j}, $$

where $w = (w_1, ..., w_m)$ corresponds to the criteria weights of the current SRMP model. This corresponds to a weighted L1 norm between an alternative and a reference profile.

$\mathcal{H}_{\text{cp}}$ selects the pair of alternatives which is closest to the profiles. $\mathcal{H}_{\text{cp}}$ returns the pair $(a, b)_{\text{cp}}$ such that :
$$ (a, b)_{\text{cp}} = \underset{(x,y) \in \mathcal{D}}{\operatorname{argmin}} \frac{1}{k} \sum_{h=1}^{k} \min(d_{w}(x, p^{h}), d_{w}(y, p^{h})) $$

### 3.2.5 $H_{mp}$: alternatives maximizing the number of profiles needed to discriminate between them

For this heuristic, we look for pairs of alternatives that are ideally indifferent when using the SRMP model previously generated, or which require as many profiles as possible in order to denote a preference of one over the other. Our intuition is that confronting the DM with such a pair of alternatives will induce additional constraints reducing as much as possible the search space of feasible SRMP models.

We begin by looking for pairs of alternatives $(a, b) \in \mathcal{D}$ that are indifferent using the previously generated SRMP model. If no such pair can be found, we then look for pairs where a preference is expressed using the last profile in the lexicographic order. If again no such pair can be found we consider the pairs discriminated by the previous profile in the lexicographic order and so on, until reaching pairs discriminated using the first profile.

To model this more formally, let us associate an integer penalty score with the logical propositions of Table 3. With each pair $(a, b) \in \mathcal{D}$ we associate the penalty of the first proposition which is true in the sequence from Table 3. Finally, the $H_{mp}$ heuristic selects a pair $(a, b)$ from $\mathcal{D}$ that minimizes this penalty.

<table><caption>**Table 3** $H_{mp}$ penalty function</caption><thead><tr><th>Penalty</th><th>Proposition</th></tr></thead><tbody><tr><td>1</td><td>(a ~ <sub>p<sup>σ</sup>(1)</sub><sup>b</sup> and ... and a ~ <sub>p<sup>σ</sup>(k)</sub><sup>b</sup>)</td></tr><tr><td>2</td><td>(a ~ <sub>p<sup>σ</sup>(1)</sub><sup>b</sup> and ... and a ~ <sub>p<sup>σ</sup>(k-1)</sub><sup>b</sup> and a ~ <sub>p<sup>σ</sup>(k)</sub><sup>b</sup>)</td></tr><tr><td>...</td><td>...</td></tr><tr><td>k</td><td>(a ~ <sub>p<sup>σ</sup>(1)</sub><sup>b</sup> and a ~ <sub>p<sup>σ</sup>(2)</sub><sup>b</sup>)</td></tr><tr><td>k+1</td><td>(a ~ <sub>p<sup>σ</sup>(1)</sub><sup>b</sup>)</td></tr></tbody></table>

## 3.3 Finding compatible SRMP models

After selecting a pair $(a, b)$ of alternatives and receiving the result of the comparison from the DM, we add it to $\mathcal{L}$. More precisely, $\mathcal{L}$ is composed of two subsets $\mathcal{L}_>$ and $\mathcal{L}_\sim$ s.t. $\mathcal{L} = \mathcal{L}_> \cup \mathcal{L}_\sim$. We add the pair to $\mathcal{L}_>$ either as $(a, b)$ if the DM prefers $a$ to $b$, or as $(b, a)$ if the DM prefers $b$ to $a$. Alternatively, this pair is added to $\mathcal{L}_\sim$ if the DM considers $a$ to be indifferent to $b$. Using this information, which is accumulated following each iteration, we then try to find an SRMP model that is compatible with it.

As multiple SRMP models may represent the same preference information expressed by the DM, we explore here several ways in which to generate such a model, if one exists. In all cases, we will be using exact approaches using Mixed-Integer Linear programs, or MIPs.
$$ (a, b)_{\text{cp}} = \underset{(x,y) \in \mathcal{D}}{\operatorname{argmin}} \frac{1}{k} \sum_{h=1}^{k} \min(d_{w}(x, p^{h}), d_{w}(y, p^{h})) $$

### 3.2.5 $H_{mp}$: alternatives maximizing the number of profiles needed to discriminate between them

For this heuristic, we look for pairs of alternatives that are ideally indifferent when using the SRMP model previously generated, or which require as many profiles as possible in order to denote a preference of one over the other. Our intuition is that confronting the DM with such a pair of alternatives will induce additional constraints reducing as much as possible the search space of feasible SRMP models.

We begin by looking for pairs of alternatives $(a, b) \in \mathcal{D}$ that are indifferent using the previously generated SRMP model. If no such pair can be found, we then look for pairs where a preference is expressed using the last profile in the lexicographic order. If again no such pair can be found we consider the pairs discriminated by the previous profile in the lexicographic order and so on, until reaching pairs discriminated using the first profile.

To model this more formally, let us associate an integer penalty score with the logical propositions of Table 3. With each pair $(a, b) \in \mathcal{D}$ we associate the penalty of the first proposition which is true in the sequence from Table 3. Finally, the $H_{mp}$ heuristic selects a pair $(a, b)$ from $\mathcal{D}$ that minimizes this penalty.

<table><caption>**Table 3** $H_{mp}$ penalty function</caption><thead><tr><th>Penalty</th><th>Proposition</th></tr></thead><tbody><tr><td>1</td><td>(a ~ <sub>p<sup>σ</sup>(1)</sub><sup>b</sup> and ... and a ~ <sub>p<sup>σ</sup>(k)</sub><sup>b</sup>)</td></tr><tr><td>2</td><td>(a ~ <sub>p<sup>σ</sup>(1)</sub><sup>b</sup> and ... and a ~ <sub>p<sup>σ</sup>(k-1)</sub><sup>b</sup> and a ~ <sub>p<sup>σ</sup>(k)</sub><sup>b</sup>)</td></tr><tr><td>...</td><td>...</td></tr><tr><td>k</td><td>(a ~ <sub>p<sup>σ</sup>(1)</sub><sup>b</sup> and a ~ <sub>p<sup>σ</sup>(2)</sub><sup>b</sup>)</td></tr><tr><td>k+1</td><td>(a ~ <sub>p<sup>σ</sup>(1)</sub><sup>b</sup>)</td></tr></tbody></table>

### 3.3 Finding compatible SRMP models

After selecting a pair $(a, b)$ of alternatives and receiving the result of the comparison from the DM, we add it to $\mathcal{L}$. More precisely, $\mathcal{L}$ is composed of two subsets $\mathcal{L}_>$ and $\mathcal{L}_\sim$ s.t. $\mathcal{L} = \mathcal{L}_> \cup \mathcal{L}_\sim$. We add the pair to $\mathcal{L}_>$ either as $(a, b)$ if the DM prefers $a$ to $b$, or as $(b, a)$ if the DM prefers $b$ to $a$. Alternatively, this pair is added to $\mathcal{L}_\sim$ if the DM considers $a$ to be indifferent to $b$. Using this information, which is accumulated following each iteration, we then try to find an SRMP model that is compatible with it.

As multiple SRMP models may represent the same preference information expressed by the DM, we explore here several ways in which to generate such a model, if one exists. In all cases, we will be using exact approaches using Mixed-Integer Linear programs, or MIPs.
### 3.3.1 *MIP*<sub>first</sub>: first feasible SRMP model

This first approach uses a MIP inspired from [27]. The MIP is simplified by removing the objective function (replacing it with a constant value) in order to find the first feasible SRMP model. The parameters of this model are given in Table 4.

<table><caption>**Table 4** Parameters of *MIP*<sub>first</sub>.</caption><tr><td>A</td><td>the set of alternatives (n in total)</td></tr><tr><td>M</td><td>the set of criteria indices (m in total)</td></tr><tr><td>k</td><td>the number of reference profiles</td></tr><tr><td>min<sub>j</sub></td><td>the smallest evaluation on each criterion j ∈ M</td></tr><tr><td>max<sub>j</sub></td><td>the largest evaluation on each criterion j ∈ M</td></tr><tr><td>dir<sub>j</sub></td><td>the preference direction of each criterion j ∈ M (1 for increasing and -1 for decreasing)</td></tr><tr><td>G</td><td>the alternatives evaluations, or performance table, given as a matrix of size n × m (with g<sub>a,j</sub> ∈ [0, 1] containing the evaluation of alternative a ∈ A on criterion j ∈ M)</td></tr><tr><td>L<sub>~</sub></td><td>set of ordered pairs (a, b) ∈ A × A where a is preferred to b by the DM</td></tr><tr><td>L<sub>~</sub></td><td>set of pairs (a, b) ∈ A × A where a and b are indifferent to the DM</td></tr><tr><td>σ</td><td>a k-tuple encoding a permutation of 1, ..., k corresponding to a lexicographic order of the reference profiles</td></tr><tr><td>γ</td><td>a small constant used to model strict inequalities</td></tr></table>

The variables of the model are presented in Table 5.

<table><caption>**Table 5** Variables of *MIP*<sub>first</sub>.</caption><tr><td>w<sub>j</sub></td><td>continuous</td><td>:</td><td>the criteria weights of the SRMP model, ∀j ∈ M</td></tr><tr><td>p<sup>h</sup><sub>j</sub></td><td>continuous</td><td>:</td><td>the performance of the reference profiles of the SRMP model<br/>∀j ∈ M, ∀h ∈ 1, ..., k</td></tr><tr><td>δ<sup>h</sup><sub>a,j</sub></td><td>binary</td><td>:</td><td>1 if alternative a outranks profile h on criterion j and 0 otherwise<br/>∀a ∈ A, ∀j ∈ M, ∀h ∈ 1, ..., k</td></tr><tr><td>ω<sup>h</sup><sub>a,j</sub></td><td>continuous</td><td>:</td><td>equal to w<sub>j</sub> if δ<sup>h</sup><sub>a,j</sub> = 1 and to 0 otherwise, ∀a ∈ A, ∀j ∈ M, ∀h ∈ 1, ..., k</td></tr><tr><td>s<sup>h</sup><sub>a,b</sub></td><td>binary</td><td>:</td><td>1 if alternative a is preferred to alternative b w.r.t. reference profile h<br/>and 0 if alternative a is indifferent to alternative b w.r.t. reference profile h<br/>∀(a, b) ∈ L<sub>~</sub>, ∀h ∈ 0, ..., k</td></tr></table>

The formulation of the MIP is thus as follows:

$$ \max 0 $$

s.t.:

$$ w_j \geq \gamma \qquad \forall j \in M \qquad (3) $$

$$ \sum_{j=1}^{m} w_j = 1 \qquad (4) $$

$$ \max_j \geq p_j^h \geq \min_j \qquad \forall j \in M, \forall h \in 1, \dots, k \qquad (5) $$

$$ \mathrm{dir}_j \cdot p_j^{h+1} \geq \mathrm{dir}_j \cdot p_j^h \qquad \forall j \in M, \forall h \in 1, \dots, k-1 \qquad (6) $$
### 3.3.1 *MIP*<sub>first</sub>: first feasible SRMP model

This first approach uses a MIP inspired from [27]. The MIP is simplified by removing the objective function (replacing it with a constant value) in order to find the first feasible SRMP model. The parameters of this model are given in Table 4.

<table><caption>**Table 4** Parameters of *MIP*<sub>first</sub>.</caption><tr><td>A</td><td>the set of alternatives (n in total)</td></tr><tr><td>M</td><td>the set of criteria indices (m in total)</td></tr><tr><td>k</td><td>the number of reference profiles</td></tr><tr><td>min<sub>j</sub></td><td>the smallest evaluation on each criterion j ∈ M</td></tr><tr><td>max<sub>j</sub></td><td>the largest evaluation on each criterion j ∈ M</td></tr><tr><td>dir<sub>j</sub></td><td>the preference direction of each criterion j ∈ M (1 for increasing and -1 for decreasing)</td></tr><tr><td>G</td><td>the alternatives evaluations, or performance table, given as a matrix of size n × m (with g<sub>a,j</sub> ∈ [0, 1] containing the evaluation of alternative a ∈ A on criterion j ∈ M)</td></tr><tr><td>L<sub>~</sub></td><td>set of ordered pairs (a, b) ∈ A × A where a is preferred to b by the DM</td></tr><tr><td>L<sub>~</sub></td><td>set of pairs (a, b) ∈ A × A where a and b are indifferent to the DM</td></tr><tr><td>σ</td><td>a k-tuple encoding a permutation of 1, ..., k corresponding to a lexicographic order of the reference profiles</td></tr><tr><td>γ</td><td>a small constant used to model strict inequalities</td></tr></table>

The variables of the model are presented in Table 5.

<table><caption>**Table 5** Variables of *MIP*<sub>first</sub>.</caption><tr><td>w<sub>j</sub></td><td>continuous</td><td>:</td><td>the criteria weights of the SRMP model, ∀j ∈ M</td></tr><tr><td>p<sup>h</sup><sub>j</sub></td><td>continuous</td><td>:</td><td>the performance of the reference profiles of the SRMP model<br/>∀j ∈ M, ∀h ∈ 1, ..., k</td></tr><tr><td>δ<sup>h</sup><sub>a,j</sub></td><td>binary</td><td>:</td><td>1 if alternative a outranks profile h on criterion j and 0 otherwise<br/>∀a ∈ A, ∀j ∈ M, ∀h ∈ 1, ..., k</td></tr><tr><td>ω<sup>h</sup><sub>a,j</sub></td><td>continuous</td><td>:</td><td>equal to w<sub>j</sub> if δ<sup>h</sup><sub>a,j</sub> = 1 and to 0 otherwise, ∀a ∈ A, ∀j ∈ M, ∀h ∈ 1, ..., k</td></tr><tr><td>s<sup>h</sup><sub>a,b</sub></td><td>binary</td><td>:</td><td>1 if alternative a is preferred to alternative b w.r.t. reference profile h<br/>and 0 if alternative a is indifferent to alternative b w.r.t. reference profile h<br/>∀(a, b) ∈ L<sub>~</sub>, ∀h ∈ 0, ..., k</td></tr></table>

The formulation of the MIP is thus as follows:

$$ \max 0 $$

s.t.:

$$ w_j \geq \gamma \qquad \forall j \in M \qquad (3) $$

$$ \sum_{j=1}^{m} w_j = 1 \qquad (4) $$

$$ \max_j \geq p_j^h \geq \min_j \qquad \forall j \in M, \forall h \in 1, \dots, k \qquad (5) $$

$$ \mathrm{dir}_j \cdot p_j^{h+1} \ge \mathrm{dir}_j \cdot p_j^h \qquad \forall j \in M, \forall h \in 1, \dots, k-1 \qquad (6) $$
$$ dir_j \cdot (g_{a,j} - p_j^h) \geq (max_j - min_j + 1) \cdot (\delta_{a,j}^h - 1) \quad \forall a \in A, \forall j \in M, \forall h \in 1, \dots, k \tag{7} $$

$$ (max_j - min_j + 1) \cdot \delta_{a,j}^h \geq dir_j \cdot (g_{a,j} - p_j^h) + \gamma \quad \forall a \in A, \forall j \in M, \forall h \in 1, \dots, k \tag{8} $$

$$ w_j \geq \omega_{a,j}^h \quad \forall a \in A, \forall j \in M, \forall h \in 1, \dots, k \tag{9} $$

$$ \omega_{a,j}^h \geq 0 \quad \forall a \in A, \forall j \in M, \forall h \in 1, \dots, k \tag{10} $$

$$ \delta_{a,j}^j \geq \omega_{a,j}^h \quad \forall a \in A, \forall j \in M, \forall h \in 1, \dots, k \tag{11} $$

$$ \omega_{a,j}^h \geq \delta_{a,j}^j + w_j - 1 \quad \forall a \in A, \forall j \in M, \forall h \in 1, \dots, k \tag{12} $$

$$ \sum_{j=1}^{m} \omega_{a,j}^{\sigma(h)} \geq \sum_{j=1}^{m} \omega_{b,j}^{\sigma(h)} + \gamma - (1 + \gamma) \cdot (1 - s_{a,b}^{\sigma(h)} + s_{a,b}^{\sigma(h-1)}) \quad \forall (a, b) \in \mathcal{L}_{\succ}, \forall h \in 1, \dots, k \tag{13} $$

$$ \sum_{j=1}^{m} \omega_{a,j}^{\sigma(h)} \geq \sum_{j=1}^{m} \omega_{b,j}^{\sigma(h)} - s_{a,b}^{\sigma(h)} - s_{a,b}^{\sigma(h-1)} \quad \forall (a, b) \in \mathcal{L}_{\succ}, \forall h \in 1, \dots, k \tag{14} $$

$$ \sum_{j=1}^{m} \omega_{a,j}^{\sigma(h)} \leq \sum_{j=1}^{m} \omega_{b,j}^{\sigma(h)} + s_{a,b}^{\sigma(h)} + s_{a,b}^{\sigma(h-1)} \quad \forall (a, b) \in \mathcal{L}_{\succ}, \forall h \in 1, \dots, k \tag{15} $$

$$ s_{a,b}^{\sigma(0)} = 0 \quad \forall (a, b) \in \mathcal{L}_{\succ} \tag{16} $$

$$ s_{a,b}^{\sigma(k)} = 1 \quad \forall (a, b) \in \mathcal{L}_{\succ} \tag{17} $$

$$ \sum_{j=1}^{m} \omega_{a,j}^{h} \geq \sum_{j=1}^{m} \omega_{b,j}^{h} \quad \forall (a, b) \in \mathcal{L}_{\sim}, \forall h \in 1, \dots, k \tag{18} $$

$$ \sum_{j=1}^{m} \omega_{a,j}^{h} \leq \sum_{j=1}^{m} \omega_{b,j}^{h} \quad \forall (a, b) \in \mathcal{L}_{\sim}, \forall h \in 1, \dots, k \tag{19} $$

The objective function only seeks to find a model compatible with the given pair-wise comparisons, therefore it is fixed to a constant. Constraints (3) and (4) normalize the criteria weights, make them sum up to 1 and ensure they have non-zero values. Constraints (5) and (6) are used to bound the profiles evaluations and maintain the dominance constraint between them, given the direction of preferences on each criterion. Constraints (7) and (8) model $\delta_{a,j}^h$ as mentioned in Table 5, while constraints (9), (10), (11) and (12) model $\omega_{a,j}^h$ as the minimum value between $w_j$ and $\delta_{a,j}^h$. Constraints (13), (14) and (15) model the preference relation between alternatives a and b following their comparison to a reference profile $p^{\sigma(h)}$, when a is preferred to b. Constraint (13) models a strict preference in favor of alternative a over alternative b w.r.t. profile $p^{\sigma(h)}$. Constraints (14) and (15)
$$ dir_j \cdot (g_{a,j} - p_j^h) \geq (max_j - min_j + 1) \cdot (\delta_{a,j}^h - 1) \quad \forall a \in A, \forall j \in M, \forall h \in 1, \dots, k \tag{7} $$

$$ (max_j - min_j + 1) \cdot \delta_{a,j}^h \geq dir_j \cdot (g_{a,j} - p_j^h) + \gamma \quad \forall a \in A, \forall j \in M, \forall h \in 1, \dots, k \tag{8} $$

$$ w_j \geq \omega_{a,j}^h \quad \forall a \in A, \forall j \in M, \forall h \in 1, \dots, k \tag{9} $$

$$ \omega_{a,j}^h \geq 0 \quad \forall a \in A, \forall j \in M, \forall h \in 1, \dots, k \tag{10} $$

$$ \delta_{a,j}^j \geq \omega_{a,j}^h \quad \forall a \in A, \forall j \in M, \forall h \in 1, \dots, k \tag{11} $$

$$ \omega_{a,j}^h \geq \delta_{a,j}^j + w_j - 1 \quad \forall a \in A, \forall j \in M, \forall h \in 1, \dots, k \tag{12} $$

$$ \sum_{j=1}^{m} \omega_{a,j}^{\sigma(h)} \geq \sum_{j=1}^{m} \omega_{b,j}^{\sigma(h)} + \gamma - (1 + \gamma) \cdot (1 - s_{a,b}^{\sigma(h)} + s_{a,b}^{\sigma(h-1)}) \quad \forall (a, b) \in \mathcal{L}_{>}, \forall h \in 1, \dots, k \tag{13} $$

$$ \sum_{j=1}^{m} \omega_{a,j}^{\sigma(h)} \geq \sum_{j=1}^{m} \omega_{b,j}^{\sigma(h)} - s_{a,b}^{\sigma(h)} - s_{a,b}^{\sigma(h-1)} \quad \forall (a, b) \in \mathcal{L}_{>}, \forall h \in 1, \dots, k \tag{14} $$

$$ \sum_{j=1}^{m} \omega_{a,j}^{\sigma(h)} \leq \sum_{j=1}^{m} \omega_{b,j}^{\sigma(h)} + s_{a,b}^{\sigma(h)} + s_{a,b}^{\sigma(h-1)} \quad \forall (a, b) \in \mathcal{L}_{>}, \forall h \in 1, \dots, k \tag{15} $$

$$ s_{a,b}^{\sigma(0)} = 0 \quad \forall (a, b) \in \mathcal{L}_{>} \tag{16} $$

$$ s_{a,b}^{\sigma(k)} = 1 \quad \forall (a, b) \in \mathcal{L}_{>} \tag{17} $$

$$ \sum_{j=1}^{m} \omega_{a,j}^{h} \geq \sum_{j=1}^{m} \omega_{b,j}^{h} \quad \forall (a, b) \in \mathcal{L}_{>}, \forall h \in 1, \dots, k \tag{18} $$

$$ \sum_{j=1}^{m} \omega_{a,j}^{h} \leq \sum_{j=1}^{m} \omega_{b,j}^{h} \quad \forall (a, b) \in \mathcal{L}_{>}, \forall h \in 1, \dots, k \tag{19} $$

The objective function only seeks to find a model compatible with the given pair-wise comparisons, therefore it is fixed to a constant. Constraints (3) and (4) normalize the criteria weights, make them sum up to 1 and ensure they have non-zero values. Constraints (5) and (6) are used to bound the profiles evaluations and maintain the dominance constraint between them, given the direction of preferences on each criterion. Constraints (7) and (8) model $\delta_{a,j}^h$ as mentioned in Table 5, while constraints (9), (10), (11) and (12) model $\omega_{a,j}^h$ as the minimum value between $w_j$ and $\delta_{a,j}^h$. Constraints (13), (14) and (15) model the preference relation between alternatives a and b following their comparison to a reference profile $p^{\sigma(h)}$, when a is preferred to b. Constraint (13) models a strict preference in favor of alternative a over alternative b w.r.t. profile $p^{\sigma(h)}$. Constraints (14) and (15)
model an indifference between a and b w.r.t. profile $p^{\sigma(h)}$. The binary variables that can be found in these three sets of constraints together with constraints (16) and (17) are needed to enforce that at least one profile discriminates between the two alternatives and that all prior profiles in the lexicographic order do not. When a profile $p^{\sigma(h)}$ models a preference between a and b, i.e. $s^{\sigma(h)} = 1$, the constraints for the following profile, $p^{\sigma(h+1)}$, are relaxed. If on the other hand profile $p^{\sigma(h)}$ does not model a preference of a over b then $s^{\sigma(h)} = 0$ and an indifference relation between a and b w.r.t. this profile is enforced. Furthermore, the constraints on the following profile, $p^{\sigma(h+1)}$, are not relaxed, and therefore either a preference of a over b or an indifference between them will be modeled using this profile. This constraint enforcement propagation is stopped by forcing the constraints for the last profile to model a preference ($s^{\sigma(k)} = 1$) between a and b. If this is not possible, we observe a propagation in the opposite direction as $s^{\sigma(k-1)}$ needs to become 1 in order to relax the constraints modeling a preference using the last profile. Again, this propagation is stopped by setting $s^{\sigma(0)} = 0$ so that the first set of constraints cannot be relaxed without modeling a preference between a and b.

Finally, constraints (18) and (19) model the indifference relation between all pairs of alternatives $(a, b) \in \mathcal{L}_{\sim}$, where a and b need to be considered as indifferent for all reference profiles $p^h, h \in 1, ..., k$.

### 3.3.2 *MIP*<sub>close</sub>: closest SRMP model to the previous one

A second configuration seeks to find an SRMP model that is as close as possible, in terms of the distance between its parameters, to the model that was extracted during the previous iteration of our incremental process. This is important to ensure stability in the interactive process with the DM.

We adapt the MIP from the previous subsection by adding several additional parameters (Table 6), variables (Table 7), constraints and by changing the objective function.

<table><caption>**Table 6** Additional parameters of *MIP*<sub>close</sub>.</caption><tr><td>w'<sub>j</sub></td><td>the weights of the previous SRMP model, $\forall j \in M$</td></tr><tr><td>p'<sub>j</sub><sup>h</sup></td><td>the profiles of the previous SRMP model, $\forall j \in M, \forall h \in 1, ..., k$</td></tr></table>

<table><caption>**Table 7** Additional variables of *MIP*<sub>close</sub>.</caption><tr><td>dw<sub>j</sub></td><td>continuous</td><td>: the distance between w<sub>j</sub> and w'<sub>j</sub>, $\forall j \in M$</td></tr><tr><td>dp<sub>j</sub><sup>h</sup></td><td>continuous</td><td>: the distance between p<sub>j</sub><sup>h</sup> and p'<sub>j</sub><sup>h</sup>, $\forall j \in M, \forall h \in 1, ..., k$</td></tr></table>

The *MIP*<sub>close</sub> model is presented below :

$$ \min \frac{1}{m} \sum_{j \in M} dw_j + \frac{1}{k} \sum_{h=1}^{k} \sum_{j \in M} \frac{dp_j^h}{max_j - min_j} $$
model an indifference between a and b w.r.t. profile $p^{\sigma(h)}$. The binary variables that can be found in these three sets of constraints together with constraints (16) and (17) are needed to enforce that at least one profile discriminates between the two alternatives and that all prior profiles in the lexicographic order do not. When a profile $p^{\sigma(h)}$ models a preference between a and b, i.e. $s^{\sigma(h)} = 1$, the constraints for the following profile, $p^{\sigma(h+1)}$, are relaxed. If on the other hand profile $p^{\sigma(h)}$ does not model a preference of a over b then $s^{\sigma(h)} = 0$ and an indifference relation between a and b w.r.t. this profile is enforced. Furthermore, the constraints on the following profile, $p^{\sigma(h+1)}$, are not relaxed, and therefore either a preference of a over b or an indifference between them will be modeled using this profile. This constraint enforcement propagation is stopped by forcing the constraints for the last profile to model a preference ($s^{\sigma(k)} = 1$) between a and b. If this is not possible, we observe a propagation in the opposite direction as $s^{\sigma(k-1)}$ needs to become 1 in order to relax the constraints modeling a preference using the last profile. Again, this propagation is stopped by setting $s^{\sigma(0)} = 0$ so that the first set of constraints cannot be relaxed without modeling a preference between a and b.

Finally, constraints (18) and (19) model the indifference relation between all pairs of alternatives $(a, b) \in \mathcal{L}_{\sim}$, where a and b need to be considered as indifferent for all reference profiles $p^h, h \in 1, ..., k$.

### 3.3.2 *MIP*<sub>close</sub>: closest SRMP model to the previous one

A second configuration seeks to find an SRMP model that is as close as possible, in terms of the distance between its parameters, to the model that was extracted during the previous iteration of our incremental process. This is important to ensure stability in the interactive process with the DM.

We adapt the MIP from the previous subsection by adding several additional parameters (Table 6), variables (Table 7), constraints and by changing the objective function.

<table><caption>**Table 6** Additional parameters of *MIP*<sub>close</sub>.</caption><tr><td>$w_j'$</td><td>the weights of the previous SRMP model, $\forall j \in M$</td></tr><tr><td>$p_j^h$</td><td>the profiles of the previous SRMP model, $\forall j \in M, \forall h \in 1, ..., k$</td></tr></table>

<table><caption>**Table 7** Additional variables of *MIP*<sub>close</sub>.</caption><tr><td>$dw_j$</td><td>continuous</td><td>: the distance between $w_j$ and $w_j'$, $\forall j \in M$</td></tr><tr><td>$dp_j^h$</td><td>continuous</td><td>: the distance between $p_j^h$ and $p_j'^h$, $\forall j \in M, \forall h \in 1, ..., k$</td></tr></table>

The *MIP*<sub>close</sub> model is presented below :

$$ \min \frac{1}{m} \sum_{j \in M} dw_j + \frac{1}{k} \sum_{h=1}^{k} \sum_{j \in M} \frac{dp_j^h}{max_j - min_j} $$
s.t.:

Constraints (3) to (19) from *MIP*<sub>first</sub>

$$dw_j \geq w_j - w_j' \qquad \forall j \in M \qquad (20)$$

$$dw_j \geq w_j - w_j' \qquad \forall j \in M \qquad (21)$$

$$dp_j^h \geq p_j^h - p_j'^h \qquad \forall j \in M, \forall h \in 1, \dots, k \qquad (22)$$

$$dp_j^h \geq p_j'^h - p_j^h \qquad \forall j \in M, \forall h \in 1, \dots, k \qquad (23)$$

The objective function seeks to minimize the distance between the parameters of the SRMP model inferred during the previous iteration and the one currently being inferred, namely the criteria weights and the reference profiles. The two terms are normalized and equally weighted by the objective function.

All of the constraints from *MIP*<sub>first</sub> are also present in *MIP*<sub>close</sub>, with the addition of four constraints needed to model the distances between the model parameters. The first pair of constraints (20) and (21) are used to model the absolute value of the difference between the weights on any criterion. The following two constraints (22) and (23) model the absolute value of the difference between the evaluations of profiles on any criterion.

### 3.3.3 *MIP*<sub>center</sub>: an SRMP model equally distanced from limit models

A third configuration seeks to find a model that is somewhat centered within the search space of feasible SRMP models, with the aim that, subsequent input from the DM will manage to reduce this search space as much as possible. In order to achieve this, we first search for the two most distant SRMP models compatible with the current input of the DM and then, using them, search for a third model that is equally and most closely distanced from them. Finding the two most distant

<table><caption>**Table 8** Variables of *MIP*<sub>distant</sub>.</caption><tr><td>w<sup>l</sup><sub>j</sub></td><td>continuous</td><td>: the criteria weights of each of the two SRMP models, &forall;l &isin; {1, 2}, &forall;j &isin; M</td></tr><tr><td>p<sup>l,h</sup><sub>j</sub></td><td>continuous</td><td>: the performance of the reference profiles of each of the two SRMP models, &forall;l &isin; {1, 2}, &forall;j &isin; M, &forall;h &isin; 1, ..., k</td></tr><tr><td>&delta;<sup>l,h</sup><sub>a,j</sub></td><td>binary</td><td>: 1 if alternative a outranks profile h on criterion j and 0 otherwise &forall;l &isin; {1, 2}, &forall;a &isin; A, &forall;j &isin; M, &forall;h &isin; 1, ..., k</td></tr><tr><td>&omega;<sup>l,h</sup><sub>a,j</sub></td><td>continuous</td><td>: equal to w<sub>j</sub> if &delta;<sup>h</sup><sub>a,j</sub> = 1 and to 0 otherwise &forall;l &isin; {1, 2}, &forall;a &isin; A, &forall;j &isin; M, &forall;h &isin; 1, ..., k</td></tr><tr><td>s<sup>l,h</sup><sub>a,b</sub></td><td>binary</td><td>: 1 if alternative a is preferred to alternative b w.r.t. reference profile h and 0 if alternative a is indifferent to alternative b w.r.t. reference profile h &forall;l &isin; {1, 2}, &forall;(a, b) &isin; L<sub>&gt;</sub>, &forall;h &isin; 1, ..., k</td></tr><tr><td>dw<sub>j</sub></td><td>continuous</td><td>: the distance between w<sup>l</sup><sub>j</sub> and w<sup>2</sup><sub>j</sub>, &forall;j &isin; M</td></tr><tr><td>dp<sup>h</sup><sub>j</sub></td><td>continuous</td><td>: the distance between p<sup>l,h</sup><sub>j</sub> and p<sup>2,h</sup><sub>j</sub>, &forall;j &isin; M, &forall;h &isin; 1, ..., k</td></tr><tr><td>uw<sub>j</sub></td><td>binary</td><td>: 1 if w<sup>l</sup><sub>j</sub> &gt;= w<sup>2</sup><sub>j</sub>, &forall;j &isin; M, and 0 otherwise</td></tr><tr><td>up<sup>h</sup><sub>j</sub></td><td>binary</td><td>: 1 if p<sup>l,h</sup><sub>j</sub> &gt;= p<sup>2,h</sup><sub>j</sub>, &forall;j &isin; M, &forall;h &isin; 1, ..., k, and 0 otherwise</td></tr></table>

SRMP models is done using the *MIP*<sub>distant</sub> mathematical model. This model has the same parameters as *MIP*<sub>first</sub> but adds an additional index *l* &isin; {1, 2} to
s.t.:

Constraints (3) to (19) from $\mathcal{MIP}_{\text{first}}$

$$dw_j \geq w_j - w_j' \qquad \forall j \in M \qquad (20)$$

$$dw_j \geq w_j - w_j' \qquad \forall j \in M \qquad (21)$$

$$dp_j^h \geq p_j^h - p_j^{h'} \qquad \forall j \in M, \forall h \in 1, \dots, k \qquad (22)$$

$$dp_j^h \geq p_j^{h'} - p_j^h \qquad \forall j \in M, \forall h \in 1, \dots, k \qquad (23)$$

The objective function seeks to minimize the distance between the parameters of the SRMP model inferred during the previous iteration and the one currently being inferred, namely the criteria weights and the reference profiles. The two terms are normalized and equally weighted by the objective function.

All of the constraints from $\mathcal{MIP}_{\text{first}}$ are also present in $\mathcal{MIP}_{\text{close}}$, with the addition of four constraints needed to model the distances between the model parameters. The first pair of constraints (20) and (21) are used to model the absolute value of the difference between the weights on any criterion. The following two constraints (22) and (23) model the absolute value of the difference between the evaluations of profiles on any criterion.

### 3.3.3 $\mathcal{MIP}_{\text{center}}$: an SRMP model equally distanced from limit models

A third configuration seeks to find a model that is somewhat centered within the search space of feasible SRMP models, with the aim that, subsequent input from the DM will manage to reduce this search space as much as possible. In order to achieve this, we first search for the two most distant SRMP models compatible with the current input of the DM and then, using them, search for a third model that is equally and most closely distanced from them. Finding the two most distant

<table><caption>**Table 8** Variables of $\mathcal{MIP}_{\text{distant}}$.</caption><tr><td>w<sub>j</sub><sup>l</sup></td><td>continuous</td><td>: the criteria weights of each of the two SRMP models, &forall;l &isin; {1, 2}, &forall;j &isin; M</td></tr><tr><td>p<sub>j</sub><sup>l,h</sup></td><td>continuous</td><td>: the performance of the reference profiles of each of the two SRMP models, &forall;l &isin; {1, 2}, &forall;j &isin; M, &forall;h &isin; 1, ..., k</td></tr><tr><td>&delta;<sub>a,j</sub><sup>l,h</sup></td><td>binary</td><td>: 1 if alternative a outranks profile h on criterion j and 0 otherwise &forall;l &isin; {1, 2}, &forall;a &isin; A, &forall;j &isin; M, &forall;h &isin; 1, ..., k</td></tr><tr><td>&omega;<sub>a,j</sub><sup>l,h</sup></td><td>continuous</td><td>: equal to w<sub>j</sub> if &delta;<sub>a,j</sub><sup>h</sup> = 1 and to 0 otherwise &forall;l &isin; {1, 2}, &forall;a &isin; A, &forall;j &isin; M, &forall;h &isin; 1, ..., k</td></tr><tr><td>s<sub>a,b</sub><sup>l,h</sup></td><td>binary</td><td>: 1 if alternative a is preferred to alternative b w.r.t. reference profile h and 0 if alternative a is indifferent to alternative b w.r.t. reference profile h &forall;l &isin; {1, 2}, &forall;(a, b) &isin; L<sub>&gt;</sub>, &forall;h &isin; 1, ..., k</td></tr><tr><td>dw<sub>j</sub></td><td>continuous</td><td>: the distance between w<sub>j</sub><sup>1</sup> and w<sub>j</sub><sup>2</sup>, &forall;j &isin; M</td></tr><tr><td>dp<sub>j</sub><sup>h</sup></td><td>continuous</td><td>: the distance between p<sub>j</sub><sup>1,h</sup> and p<sub>j</sub><sup>2,h</sup>, &forall;j &isin; M, &forall;h &isin; 1, ..., k</td></tr><tr><td>uw<sub>j</sub></td><td>binary</td><td>: 1 if w<sub>j</sub><sup>1</sup> &ge; w<sub>j</sub><sup>2</sup>, &forall;j &isin; M, and 0 otherwise</td></tr><tr><td>up<sub>j</sub><sup>h</sup></td><td>binary</td><td>: 1 if p<sub>j</sub><sup>1,h</sup> &ge; p<sub>j</sub><sup>2,h</sup>, &forall;j &isin; M, &forall;h &isin; 1, ..., k, and 0 otherwise</td></tr></table>

SRMP models is done using the $\mathcal{MIP}_{\text{distant}}$ mathematical model. This model has the same parameters as $\mathcal{MIP}_{\text{first}}$ but adds an additional index $l \in \{1, 2\}$ to
all of its variables. Additional variables are also needed in order to measure the distance between the two generated SRMP models. As the objective function of this model will be to maximize the distance between the two models, instead of minimizing it like in the case of MIP<sub>close</sub>, the variables measuring the distance between the criteria weights and the profiles evaluations need to be both lower and upper bounded. For this reason, binary variables indicating which of the two models parameters (criteria weights and profiles evaluations) is larger, also need to be added. We depict the variables of MIP<sub>distant</sub> in Table 8.

The MIP<sub>distant</sub> model is presented below :

$$ \max \quad \frac{1}{m} \sum_{j \in M} dw_j + \frac{1}{k} \sum_{h=1}^{k} \sum_{j \in M} \frac{dp_j^h}{max_j - min_j} $$

s.t. :

$$ \text{Constraints (3) to (19) from MIP<sub>first</sub> with the } l \text{ index} \quad \forall l \in \{1, 2\} \\ dw_j \ge 0 \quad \forall j \in M \quad (24) $$

$$ dw_j \ge w_j^1 - w_j^2 - (1 - uw_j) \quad \forall j \in M \quad (25) $$

$$ dw_j \le w_j^1 - w_j^2 + (1 - uw_j) \quad \forall j \in M \quad (26) $$

$$ dw_j \ge w_j^2 - w_j^1 - uw_j \quad \forall j \in M \quad (27) $$

$$ dw_j \le w_j^2 - w_j^1 + uw_j \quad \forall j \in M \quad (28) $$

$$ dp_j^h \ge 0 \quad \forall j \in M, \forall h \in 1, \dots, k \quad (29) $$

$$ dp_j^h \ge p_j^{1,h} - p_j^{2,h} - (1 - up_j^h) \quad \forall j \in M, \forall h \in 1, \dots, k \quad (30) $$

$$ dp_j^h \le p_j^{1,h} - p_j^{2,h} + (1 - up_j^h) \quad \forall j \in M, \forall h \in 1, \dots, k \quad (31) $$

$$ dp_j^h \ge p_j^{2,h} - p_j^{1,h} - up_j^h \quad \forall j \in M, \forall h \in 1, \dots, k \quad (32) $$

$$ dp_j^h \le p_j^{2,h} - p_j^{1,h} + up_j^h \quad \forall j \in M, \forall h \in 1, \dots, k \quad (33) $$

The objective function of this model maximizes the distance between the weights of the two generated SRMP models and the distance between their profiles.

Constraints (3) to (19) from MIP<sub>first</sub> are replicated for each set of SRMP model parameters, i.e. $\forall l \in \{1, 2\}$. In this way, both models are compatible with the currently expressed preference information of the DM. Constraints (24) to (28) model the distance between the weights of the two models, while constraints (29) to (33) model the distance between their profiles.

With the two found SRMP models, we then look for another model which is equally distanced from these two models but also as close as possible. This corresponds to a bi-objective problem however we reduce it to a mono-objective problem by linearly combining the two objectives in order to facilitate its resolution.
all of its variables. Additional variables are also needed in order to measure the distance between the two generated SRMP models. As the objective function of this model will be to maximize the distance between the two models, instead of minimizing it like in the case of MIP<sub>close</sub>, the variables measuring the distance between the criteria weights and the profiles evaluations need to be both lower and upper bounded. For this reason, binary variables indicating which of the two models parameters (criteria weights and profiles evaluations) is larger, also need to be added. We depict the variables of MIP<sub>distant</sub> in Table 8.

The MIP<sub>distant</sub> model is presented below :

$$ \max \quad \frac{1}{m} \sum_{j \in M} dw_j + \frac{1}{k} \sum_{h=1}^{k} \sum_{j \in M} \frac{dp_j^h}{max_j - min_j} $$

s.t. :

$$ \text{Constraints (3) to (19) from MIP<sub>first</sub> with the } l \text{ index} \quad \forall l \in \{1, 2\} \\ dw_j \ge 0 \quad \forall j \in M \quad (24) $$

$$ dw_j \ge w_j^1 - w_j^2 - (1 - uw_j) \quad \forall j \in M \quad (25) $$

$$ dw_j \le w_j^1 - w_j^2 + (1 - uw_j) \quad \forall j \in M \quad (26) $$

$$ dw_j \ge w_j^2 - w_j^1 - uw_j \quad \forall j \in M \quad (27) $$

$$ dw_j \le w_j^2 - w_j^1 + uw_j \quad \forall j \in M \quad (28) $$

$$ dp_j^h \ge 0 \quad \forall j \in M, \forall h \in 1, \dots, k \quad (29) $$

$$ dp_j^h \ge p_j^{1,h} - p_j^{2,h} - (1 - up_j^h) \quad \forall j \in M, \forall h \in 1, \dots, k \quad (30) $$

$$ dp_j^h \le p_j^{1,h} - p_j^{2,h} + (1 - up_j^h) \quad \forall j \in M, \forall h \in 1, \dots, k \quad (31) $$

$$ dp_j^h \ge p_j^{2,h} - p_j^{1,h} - up_j^h \quad \forall j \in M, \forall h \in 1, \dots, k \quad (32) $$

$$ dp_j^h \le p_j^{2,h} - p_j^{1,h} + up_j^h \quad \forall j \in M, \forall h \in 1, \dots, k \quad (33) $$

The objective function of this model maximizes the distance between the weights of the two generated SRMP models and the distance between their profiles.

Constraints (3) to (19) from MIP<sub>first</sub> are replicated for each set of SRMP model parameters, i.e. $\forall l \in \{1, 2\}$. In this way, both models are compatible with the currently expressed preference information of the DM. Constraints (24) to (28) model the distance between the weights of the two models, while constraints (29) to (33) model the distance between their profiles.

With the two found SRMP models, we then look for another model which is equally distanced from these two models but also as close as possible. This corresponds to a bi-objective problem however we reduce it to a mono-objective problem by linearly combining the two objectives in order to facilitate its resolution.
A new model, called *MIPcenter* is therefore defined. The parameters of this model contain again those of *MIPfirst*. We also take the results given by *MIPdistant* in the form of $w_j^l, \forall l \in \{1, 2\}, j \in M$ and $p_j^{l,h}, \forall l \in \{1, 2\}, j \in M, h \in 1..k$, which are added as parameters to *MIPcenter*.

The variables of *MIPcenter* contain the variables of *MIPfirst*, plus a few additional variables given in Table 9.

<table><caption>**Table 9** Additional variables of *MIPcenter*.</caption><tr><td>dw<sup>l</sup><sub>j</sub></td><td>continuous</td><td>: the distance between w<sub>j</sub> and w<sup>l</sup><sub>j</sub>, ∀l ∈ {1, 2}, ∀j ∈ M</td></tr><tr><td>dp<sup>l,h</sup><sub>j</sub></td><td>continuous</td><td>: the distance between ph<sub>j</sub> and p<sup>l,h</sup><sub>j</sub>, ∀l ∈ {1, 2}, ∀j ∈ M, ∀h ∈ 1, ..., k</td></tr><tr><td>DW<sub>j</sub></td><td>continuous</td><td>: the distance between dw<sup>l</sup><sub>j</sub> and dw<sup>2</sup><sub>j</sub>, ∀j ∈ M</td></tr><tr><td>DP<sup>h</sup><sub>j</sub></td><td>continuous</td><td>: the distance between dp<sup>l,h</sup><sub>j</sub> and dp<sup>2,h</sup><sub>j</sub>, ∀j ∈ M, ∀h ∈ 1, ..., k</td></tr></table>

The *MIPcenter* model is presented below :

$$ \min \frac{1}{2} \sum_{l \in \{1,2\}} \left( \sum_{j \in M} \frac{dw_j^l}{m} + \sum_{h=1}^{k} \sum_{j \in M} \frac{dp_j^{l,h}}{k(max_j - min_j)} \right) + \left( \sum_{j \in M} \frac{DW_j}{m} + \sum_{h=1}^{k} \sum_{j \in M} \frac{DP_j^h}{k(max_j - min_j)} \right) $$

s.t. :

Constraints (3) to (19) from *MIPfirst*

$$ dw_j^l \ge w_j - w_j^l \qquad \forall j \in M, \forall l \in \{1, 2\} \qquad (34) $$

$$ dw_j^l \ge w_j^l - w_j \qquad \forall j \in M, \forall l \in \{1, 2\} \qquad (35) $$

$$ dp_j^{l,h} \ge p_j^h - p_j^{l,h} \qquad \forall j \in M, \forall h \in 1, ..., k, \forall l \in \{1, 2\} \qquad (36) $$

$$ dp_j^{l,h} \ge p_j^{l,h} - p_j^h \qquad \forall j \in M, \forall h \in 1, ..., k, \forall l \in \{1, 2\} \qquad (37) $$

$$ DW_j \ge dw_j^1 - dw_j^2 \qquad \forall j \in M \qquad (38) $$

$$ DW_j \ge dw_j^2 - dw_j^1 \qquad \forall j \in M \qquad (39) $$

$$ DP_j^h \ge dp_j^{1,h} - dp_j^{2,h} \qquad \forall j \in M, \forall h \in 1, ..., k \qquad (40) $$

$$ DP_j^h \ge dp_j^{2,h} - dp_j^{1,h} \qquad \forall j \in M, \forall h \in 1, ..., k \qquad (41) $$

The objective function takes into account, in equal measure, two distances: (i) the average distance between the weights and profiles of the SRMP model it generates and the two previously generated models and (ii) the difference between these two distances. The first part ensures that the SRMP model is as close as possible to the two models, while the second part ensures that it is evenly distanced from them.

Constraints (3) to (19) from *MIPfirst* are used to ensure that the generated SRMP model is compatible with the preference information expressed by the DM. Constraints (34) to (35) and (36) to (37) are used to model the distances between
A new model, called *MIP*<sub>center</sub> is therefore defined. The parameters of this model contain again those of *MIP*<sub>first</sub>. We also take the results given by *MIP*<sub>distant</sub> in the form of $w_j^l, \forall l \in \{1, 2\}, j \in M$ and $p_j^{l,h}, \forall l \in \{1, 2\}, j \in M, h \in 1..k$, which are added as parameters to *MIP*<sub>center</sub>.

The variables of *MIP*<sub>center</sub> contain the variables of *MIP*<sub>first</sub>, plus a few additional variables given in Table 9.

<table><caption>**Table 9** Additional variables of *MIP*<sub>center</sub>.</caption><tr><td>$dw_j^l$</td><td>continuous</td><td>: the distance between $w_j$ and $w_j^l, \forall l \in \{1, 2\}, \forall j \in M$</td></tr><tr><td>$dp_j^{l,h}$</td><td>continuous</td><td>: the distance between $p_j^{l,h}, \forall l \in \{1, 2\}, \forall j \in M, \forall h \in 1, ..., k$</td></tr><tr><td>$DW_j$</td><td>continuous</td><td>: the distance between $dw_j^l$ and $dw_j^{l,h}, \forall j \in M$</td></tr><tr><td>$DP_j^h$</td><td>continuous</td><td>: the distance between $dp_j^{l,h}$ and $dp_j^{l,h}, \forall j \in M, \forall h \in 1, ..., k$</td></tr></table>

The *MIP*<sub>center</sub> model is presented below :

$$ \min \quad \frac{1}{2} \sum_{l \in \{1, 2\}} \left( \sum_{j \in M} \frac{dw_j^l}{m} + \sum_{h=1}^{k} \sum_{j \in M} \frac{dp_j^{l,h}}{k(max_j - min_j)} \right) + \\ + \left( \sum_{j \in M} \frac{DW_j}{m} + \sum_{h=1}^{k} \sum_{j \in M} \frac{DP_j^h}{k(max_j - min_j)} \right) $$

s.t. :

Constraints (3) to (19) from *MIP*<sub>first</sub>

$$ dw_j^l \geq w_j - w_j^l \qquad \forall j \in M, \forall l \in \{1, 2\} \qquad (34) $$

$$ dw_j^l \geq w_j^l - w_j \qquad \forall j \in M, \forall l \in \{1, 2\} \qquad (35) $$

$$ dp_j^{l,h} \geq p_j^h - p_j^{l,h} \qquad \forall j \in M, \forall h \in 1, ..., k, \forall l \in \{1, 2\} \qquad (36) $$

$$ dp_j^{l,h} \geq p_j^{l,h} - p_j^h \qquad \forall j \in M, \forall h \in 1, ..., k, \forall l \in \{1, 2\} \qquad (37) $$

$$ DW_j \geq dw_j^l - dw_j^2 \qquad \forall j \in M \qquad (38) $$

$$ DW_j \geq dw_j^2 - dw_j^1 \qquad \forall j \in M \qquad (39) $$

$$ DP_j^h \geq dp_j^{l,h} - dp_j^{l,h} \qquad \forall j \in M, \forall h \in 1, ..., k \qquad (40) $$

$$ DP_j^h \geq dp_j^{l,h} - dp_j^{l,h} \qquad \forall j \in M, \forall h \in 1, ..., k \qquad (41) $$

The objective function takes into account, in equal measure, two distances: (i) the average distance between the weights and profiles of the SRMP model it generates and the two previously generated models and (ii) the difference between these two distances. The first part ensures that the SRMP model is as close as possible to the two models, while the second part ensures that it is evenly distanced from them.

Constraints (3) to (19) from *MIP*<sub>first</sub> are used to ensure that the generated SRMP model is compatible with the preference information expressed by the DM. Constraints (34) to (35) and (36) to (37) are used to model the distances between
the criteria weights and the reference profiles of the generated SRMP model and each of the two models generated by MIP<sub>distant</sub>. The following constraints (38) and (39) (resp. (40) and (41)) are similar, and model the distance between these criteria weights (resp. reference profiles) distances.

### 3.4 Finding incompatible comparisons

During the elicitation process, when no valid SRMP model can be found using either of the three previously presented approaches, we need to identify and resolve any situation where the DM's input is inconsistent with an SRMP model. For this reason, we use an approach very similar to the one in [24], where we adapt MIP<sub>first</sub> in order to detect all inconsistently compared single pairs of alternatives, one after the other, then all sets of two pairs of alternatives and so on, until the DM accepts to change or remove one of them. We do not consider currently the number and the order of the pairs of alternatives that should be presented to the DM, nevertheless, this would be an important topic for a future study.

We outline the process of extracting sets of inconsistent comparisons in Algorithm 1. This algorithm makes use of an adapted MIP. We update the MIP<sub>first</sub> program by adding a set of binary variables $t_{(a,b)}$, which are set to 1 if the comparison between alternatives a and b is enforced $\forall (a, b) \in \mathcal{L}$. To do this, we add the expression $-(1 - t_{(a,b)})$ to the right-hand side of constraints (13), (14) and (18), and the expression $(1 - t_{(a,b)})$ to the right-hand side of constraints (15) and (19). When $t_{(a,b)} = 0$, all of these constraints are relaxed and no longer enforce the preference or indifference comparison between alternatives a and b. We denote this program as MIP<sub>inc</sub>.

<caption>**Algorithm 1:** Finding inconsistent sets of pair-wise comparisons</caption>

1. $S \leftarrow \{(x, y)\}$, with $(x, y)$ last pair from $\mathcal{L}$
2. Add constraint $t_{(x,y)} = 1$ to MIP<sub>inc</sub>
3. **while** stop condition not met **do**
4. &nbsp;&nbsp;&nbsp;&nbsp; $\mathcal{T} \leftarrow \{(a, b) \in \mathcal{L} | t_{(a,b)} = 0\}$
5. &nbsp;&nbsp;&nbsp;&nbsp; $S \leftarrow S \cup \{\mathcal{T}\}$
6. &nbsp;&nbsp;&nbsp;&nbsp; Add constraint $\sum_{(a,b) \in \mathcal{T}} t_{(a,b)} \ge 1$ to MIP<sub>inc</sub>
7. **return** $S$

Algorithm 1 starts with a set containing the last pair of alternatives from $\mathcal{L}$. This is due to the fact that we only use this algorithm if MIP<sub>first</sub> does not find a feasible SRMP model following the inclusion of the DMs preferences on the last pair of alternatives $(x, y)$. We can therefore assume that the expressed preference on the last pair of alternatives is incompatible with an SRMP model.

The MIP<sub>inc</sub> program seeks to maximize the number comparisons that it enforces (by setting the $t$ variables to 1). Hence, for the last pair of alternatives $(x, y)$, we add a constraint fixing its $t_{(x,y)}$ variable to 1, so that any subsequent execution of MIP<sub>inc</sub> does not find it as an incompatible comparison again.
the criteria weights and the reference profiles of the generated SRMP model and each of the two models generated by *MIP*<sub>distant</sub>. The following constraints (38) and (39) (resp. (40) and (41)) are similar, and model the distance between these criteria weights (resp. reference profiles) distances.

### 3.4 Finding incompatible comparisons

During the elicitation process, when no valid SRMP model can be found using either of the three previously presented approaches, we need to identify and resolve any situation where the DM's input is inconsistent with an SRMP model. For this reason, we use an approach very similar to the one in [24], where we adapt *MIP*<sub>first</sub> in order to detect all inconsistently compared single pairs of alternatives, one after the other, then all sets of two pairs of alternatives and so on, until the DM accepts to change or remove one of them. We do not consider currently the number and the order of the pairs of alternatives that should be presented to the DM, nevertheless, this would be an important topic for a future study.

We outline the process of extracting sets of inconsistent comparisons in Algorithm 1. This algorithm makes use of an adapted MIP. We update the MIP<sub>first</sub> program by adding a set of binary variables $t_{(a,b)}$, which are set to 1 if the comparison between alternatives a and b is enforced $\forall (a, b) \in \mathcal{L}$. To do this, we add the expression $-(1 - t_{(a,b)})$ to the right-hand side of constraints (13), (14) and (18), and the expression $(1 - t_{(a,b)})$ to the right-hand side of constraints (15) and (19). When $t_{(a,b)} = 0$, all of these constraints are relaxed and no longer enforce the preference or indifference comparison between alternatives a and b. We denote this program as MIP<sub>inc</sub>.

<caption>**Algorithm 1:** Finding inconsistent sets of pair-wise comparisons</caption>

1. $S \leftarrow \{(x, y)\}$, with $(x, y)$ last pair from $\mathcal{L}$
2. Add constraint $t_{(x,y)} = 1$ to MIP<sub>inc</sub>
3. **while** stop condition not met **do**
4. &nbsp;&nbsp;&nbsp;&nbsp; $\mathcal{T} \leftarrow \{(a, b) \in \mathcal{L} | t_{(a,b)} = 0\}$
5. &nbsp;&nbsp;&nbsp;&nbsp; $S \leftarrow S \cup \{\mathcal{T}\}$
6. &nbsp;&nbsp;&nbsp;&nbsp; Add constraint $\sum_{(a,b) \in \mathcal{T}} t_{(a,b)} \ge 1$ to MIP<sub>inc</sub>
7. **return** $S$

Algorithm 1 starts with a set containing the last pair of alternatives from $\mathcal{L}$. This is due to the fact that we only use this algorithm if MIP<sub>first</sub> does not find a feasible SRMP model following the inclusion of the DMs preferences on the last pair of alternatives $(x, y)$. We can therefore assume that the expressed preference on the last pair of alternatives is incompatible with an SRMP model.

The MIP<sub>inc</sub> program seeks to maximize the number comparisons that it enforces (by setting the *t* variables to 1). Hence, for the last pair of alternatives $(x, y)$, we add a constraint fixing its $t_{(x,y)}$ variable to 1, so that any subsequent execution of MIP<sub>inc</sub> does not find it as an incompatible comparison again.
The main loop of the algorithm repeats more or less the same process, by executing MIP<sub>inc</sub> and extracting the set of pairs of alternatives that could not be enforced (*T*). These pairs will have their corresponding *t* variables set to 0. This set is then added to *S* and a constraint stating that at least one of its comparisons need to be fulfilled during the following executions is added. In this way, other sets of comparisons partially overlapping with the currently found one will not be excluded.

The stopping condition may be linked to the size of *S* or to the cardinality of *T*. As previously mentioned, we do not currently consider the topic of the order, the number or size of inconsistent sets of pairs of alternatives that are presented to the DM.

# 4 Empirical validation

The goal of this section is to study empirically which combination of heuristic / MIP configuration leads to the “best” SRMP model with the fewest possible pairwise comparisons.

In order to limit the number of computational experiments needed for this study we initially carry out an experiment seeking to study the relevance of having fewer or more reference profiles in an SRMP model. Given these limits, we then proceed to testing the aforementioned strategies.

## 4.1 Expressiveness of the SRMP model

We define the expressiveness of the SRMP model by its ability to reproduce the DM's preferences. The purpose of our experiment is to find the number of profiles necessary to achieve a good expressiveness of the SRMP models for problems with up to 7 criteria.

We begin by generating a set of 100 models for each of the three cases where the number of criteria $m \in \{3, 5, 7\}$. For simplicity, we consider the evaluation scales to be in the [0, 1] interval with higher values being considered preferable to lower ones. We also fix the number of profiles $k$ to 10, which we consider to be a reasonably large number of profiles that a DM would be willing to consider in practice. For each model we :

- construct the $k$ profiles by drawing $k$ values from a uniform distribution on the [0, 1] interval on each criterion and then assigning them in increasing order to each profile;

- randomly generate the $m$ criteria weights using the approach of Butler et al. [9];

- randomly generate a permutation of the sequence {1, ..., $k$} as the lexicographic order.

We then construct a total of 5,000 pairs of alternatives with randomly generated criteria evaluations (again using uniform distributions in the [0, 1] interval for each criterion) for each of the three scenarios where $m \in \{3, 5, 7\}$. These alternatives are then compared pair-wisely using each of the 100 generated SRMP models. For each model, we report the percentage of pairs of alternatives that
The main loop of the algorithm repeats more or less the same process, by
executing MIP<sub>inc</sub> and extracting the set of pairs of alternatives that could not be
enforced (*T*). These pairs will have their corresponding *t* variables set to 0. This
set is then added to *S* and a constraint stating that at least one of its comparisons
need to be fulfilled during the following executions is added. In this way, other
sets of comparisons partially overlapping with the currently found one will not be
excluded.

The stopping condition may be linked to the size of S or to the cardinality of T. As previously mentioned, we do not currently consider the topic of the order, the number or size of inconsistent sets of pairs of alternatives that are presented to the DM.

4 Empirical validation

The goal of this section is to study empirically which combination of heuristic
/ MIP configuration leads to the “best” SRMP model with the fewest possible
pairwise comparisons.

In order to limit the number of computational experiments needed for this
study we initially carry out an experiment seeking to study the relevance of having
fewer or more reference profiles in an SRMP model. Given these limits, we then
proceed to testing the aforementioned strategies.

4.1 Expressiveness of the SRMP model

We define the expressiveness of the SRMP model by its ability to reproduce the
DM's preferences. The purpose of our experiment is to find the number of profiles
necessary to achieve a good expressiveness of the SRMP models for problems with
up to 7 criteria.

We begin by generating a set of 100 models for each of the three cases where
the number of criteria $m \in \{3, 5, 7\}$. For simplicity, we consider the evaluation
scales to be in the [0, 1] interval with higher values being considered preferable to
lower ones. We also fix the number of profiles $k$ to 10, which we consider to be
a reasonably large number of profiles that a DM would be willing to consider in
practice. For each model we :

- construct the *k* profiles by drawing *k* values from a uniform distribution on the [0, 1] interval on each criterion and then assigning them in increasing order to each profile;

- randomly generate the *m* criteria weights using the approach of Butler et al. [9];

- randomly generate a permutation of the sequence {1, ..., *k*} as the lexicographic order.

We then construct a total of 5,000 pairs of alternatives with randomly gen-
erated criteria evaluations (again using uniform distributions in the [0, 1] interval
for each criterion) for each of the three scenarios where m ∈ {3, 5, 7}. These al-
ternatives are then compared pair-wisely using each of the 100 generated SRMP
models. For each model, we report the percentage of pairs of alternatives that
<figure><img src="image_4.png" /><figcaption>**Fig. 3** Percentage of pairs of alternatives distributions as a function of the lexicographic order index of the discriminating reference profile.</figcaption></figure>

were discriminated using the first profile in the lexicographic order, then using the second one, and so on until considering all 10 reference profiles. Figure 3 presents these distributions as boxplots.

We observe that in all scenarios, the first profile is able to discriminate between the largest proportion of pairs of alternatives. This proportion increases as the number of criteria increases. When considering problems containing 3 criteria, we observe that the second and third profiles in the lexicographic order are used, to lower extents, in order to model a preference between pairs of alternatives. However, we may easily state that from the fourth profile onward the added benefit of including these profiles in the model is marginal. When considering 5 criteria, the first two profiles model the large majority or preference relations, while when considering 7 criteria even the second profile becomes somewhat unnecessary.
<figure><img src="image_3.png" /><figcaption>**Fig. 3** Percentage of pairs of alternatives distributions as a function of the lexicographic order index of the discriminating reference profile.</figcaption></figure>

were discriminated using the first profile in the lexicographic order, then using the second one, and so on until considering all 10 reference profiles. Figure 3 presents these distributions as boxplots.

We observe that in all scenarios, the first profile is able to discriminate between the largest proportion of pairs of alternatives. This proportion increases as the number of criteria increases. When considering problems containing 3 criteria, we observe that the second and third profiles in the lexicographic order are used, to lower extents, in order to model a preference between pairs of alternatives. However, we may easily state that from the fourth profile onward the added benefit of including these profiles in the model is marginal. When considering 5 criteria, the first two profiles model the large majority or preference relations, while when considering 7 criteria even the second profile becomes somewhat unnecessary.
Nevertheless, while very few randomly generated pairs of alternatives require more than two or three reference profiles in order to model a preference between them, real case scenarios may include a larger proportion of such alternatives. Therefore an incremental approach where the elicitation process starts with an SRMP model with fewer reference profiles which are then increased when a significant proportion of pairs of alternatives cannot be properly modeled, may be considered.

## 4.2 Design of experiments

Our second set of experiments follows the incremental elicitation process presented in Section 3.1 with an additional phase to test the quality of the obtained SRMP model. A database $D$ of 100 pairs of alternatives generated randomly from a uniform distribution, is used as input for all the proposed heuristics of Section 3.2, combined with the 3 possible MIP configurations of Section 3.3. The chosen heuristic selects a pair of alternatives from $D$ at each iteration $i$. The DM is replaced for our experiments with a randomly generated SRMP model $M_{DM}$ (using the same approach as the one presented in the previous section), which is used to compare pairs of alternatives. Consequently this leads to the case where there is no incompatibility in the DM's preferences. The comparisons from each iteration $i$ generate new constraints for the model that needs to be determined, which we denote as $M_i$.

To test the quality of a model, we use a test database $D_{test}$ composed of 5000 pairs of alternatives (generated in the same way as in the previous section). Two ranking are constructed, one using the original SRMP model $M_{DM}$ and another using the currently generated SRMP model $M_i$. The quality of $M_i$ is evaluated using Kendall's rank correlation [21] $\tau$ between the two rankings. $\tau$ varies between 1 and -1, with $\tau = 1$ indicating that the two rankings are identical and $\tau = -1$ indicating that they are completely reversed.

We repeat this process for 100 different DM (i.e. randomly generated SRMP models $M_{DM}$) and 100 different artificial databases $D$, composed each of 100 pairs of alternatives, evaluated on different numbers of criteria ($m \in \{3, 5, 7\}$). We also fix the number of profiles of the SRMP models to 2.

The calculations are performed on multiple servers configured with 20 CPUs (which allow the MIP solver CPLEX to reach a parallelism of 20 for the resolution of the MIP) and 30 GB of RAM.

## 4.3 Experimental results and discussion

Figure 4 depicts the mean value of the *Kendall's tau* and its standard deviation for each iteration of the proposed approach (one additional pair of alternatives selected at each iteration) when considering problems with 3 criteria and SRMP models with 2 profiles (*2P 3C*) and using the $H_{rnd} / MIP_{first}$ configuration. The results show an expected trend in which the value of *Kendall's tau* increases with the number of pairs of alternatives used to learn the SRMP model and increases towards 1. This means that the more learning pairs are used, the closer $M_i$ is to $M_{DM}$. The standard deviations associated with the average values depicted in this
Nevertheless, while very few randomly generated pairs of alternatives require more than two or three reference profiles in order to model a preference between them, real case scenarios may include a larger proportion of such alternatives. Therefore an incremental approach where the elicitation process starts with an SRMP model with fewer reference profiles which are then increased when a significant proportion of pairs of alternatives cannot be properly modeled, may be considered.

## 4.2 Design of experiments

Our second set of experiments follows the incremental elicitation process presented in Section 3.1 with an additional phase to test the quality of the obtained SRMP model. A database $D$ of 100 pairs of alternatives generated randomly from a uniform distribution, is used as input for all the proposed heuristics of Section 3.2, combined with the 3 possible MIP configurations of Section 3.3. The chosen heuristic selects a pair of alternatives from $D$ at each iteration $i$. The DM is replaced for our experiments with a randomly generated SRMP model $M_{DM}$ (using the same approach as the one presented in the previous section), which is used to compare pairs of alternatives. Consequently this leads to the case where there is no incompatibility in the DM's preferences. The comparisons from each iteration $i$ generate new constraints for the model that needs to be determined, which we denote as $M_i$.

To test the quality of a model, we use a test database $D_{test}$ composed of 5000 pairs of alternatives (generated in the same way as in the previous section). Two ranking are constructed, one using the original SRMP model $M_{DM}$ and another using the currently generated SRMP model $M_i$. The quality of $M_i$ is evaluated using Kendall's rank correlation [21] $\tau$ between the two rankings. $\tau$ varies between 1 and -1, with $\tau = 1$ indicating that the two rankings are identical and $\tau = -1$ indicating that they are completely reversed.

We repeat this process for 100 different DM (i.e. randomly generated SRMP models $M_{DM}$) and 100 different artificial databases $D$, composed each of 100 pairs of alternatives, evaluated on different numbers of criteria ($m \in \{3, 5, 7\}$). We also fix the number of profiles of the SRMP models to 2.

The calculations are performed on multiple servers configured with 20 CPUs (which allow the MIP solver CPLEX to reach a parallelism of 20 for the resolution of the MIP) and 30 GB of RAM.

## 4.3 Experimental results and discussion

Figure 4 depicts the mean value of the Kendall's tau and its standard deviation for each iteration of the proposed approach (one additional pair of alternatives selected at each iteration) when considering problems with 3 criteria and SRMP models with 2 profiles (2P 3C) and using the $H_{rnd} / MIP_{first}$ configuration. The results show an expected trend in which the value of Kendall's tau increases with the number of pairs of alternatives used to learn the SRMP model and increases towards 1. This means that the more learning pairs are used, the closer $M_i$ is to $M_{DM}$. The standard deviations associated with the average values depicted in this
<figure><img src="image_5.png" /><figcaption>**Fig. 4** Mean and standard deviation Kendall's tau for 2P 3C using $H_{rnd} / MIP_{first}$</figcaption></figure>

figure are small and they also decrease with the addition of more learning pairs. They correspond on average to a value of ~ 0.095.

Figure 5 represents the mean value of *Kendall's tau* using the different proposed heuristics and the *MIP*_{first} configuration. We notice different trends while at the same time increasing in all cases towards a value of 1. Initially, during the first iterations, all heuristics have somewhat similar and poor performances due to the small number of pairs of alternatives considered leading to not very expressive SRMP models. As more information is gathered, we observe a clear separation in favor of *H*_{mp}. During the last final iterations, the heuristics again reach similar performances. This can be explained by the fact that the set of learning pairs becomes mostly identical for all of them as we deplete pairs of alternatives in *D* (which contains 100 pairs of alternatives, the same as the number of performed iterations).

In order to validate these observations, we use the *Kolmogorov-Smirnov* statistical test [12] in order to compare the average performance of any two heuristics across all iterations of the elicitation protocol. A significant difference occurs when the p-value reported by this test is less then 0.05.

Following this test, we confirm that the *H*<sub>mp</sub> has a significantly different performance in terms of its reported *Kendall's tau* when compared to the other tested
<figure><img src="image_4.png" /><figcaption>**Fig. 4** Mean and standard deviation Kendall's tau for 2P 3C using $H_{rnd} / MIP_{first}$</figcaption></figure>

figure are small and they also decrease with the addition of more learning pairs. They correspond on average to a value of ~ 0.095.

Figure 5 represents the mean value of *Kendall's tau* using the different proposed heuristics and the *MIP*_{first} configuration. We notice different trends while at the same time increasing in all cases towards a value of 1. Initially, during the first iterations, all heuristics have somewhat similar and poor performances due to the small number of pairs of alternatives considered leading to not very expressive SRMP models. As more information is gathered, we observe a clear separation in favor of *H*_{mp}. During the last final iterations, the heuristics again reach similar performances. This can be explained by the fact that the set of learning pairs becomes mostly identical for all of them as we deplete pairs of alternatives in *D* (which contains 100 pairs of alternatives, the same as the number of performed iterations).

In order to validate these observations, we use the *Kolmogorov-Smirnov* statistical test [12] in order to compare the average performance of any two heuristics across all iterations of the elicitation protocol. A significant difference occurs when the p-value reported by this test is less then 0.05.

Following this test, we confirm that the *H*<sub>mp</sub> has a significantly different performance in terms of its reported *Kendall's tau* when compared to the other tested
<figure><img src="image_6.png" /><figcaption>Fig. 5 Mean Kendall's tau for 2P 3C using the different heuristics and *MIP*<sub>first</sub> configuration</figcaption></figure>

heuristics. Table 10 shows the corresponding p-values of the *Kolmogorov-Smirnov*, which are all below 0.05.

<table><caption>Table 10 *Kolmogorov-Smirnov* test results (p-values) for 2P 3C using *MIP*<sub>first</sub> configuration</caption><thead><tr><th></th><th><i>H</i><sub>rnd</sub></th><th><i>H</i><sub>sim</sub></th><th><i>H</i><sub>dis</sub></th><th><i>H</i><sub>cp</sub></th></tr></thead><tbody><tr><th><i>H</i><sub>mp</sub></th><td>0.00193</td><td>0.01216</td><td>4.785e-06</td><td>0.00193</td></tr></tbody></table>

Figure 6 depicts the mean value of the *Kendall's tau* for the three possible MIP configurations (*MIP*<sub>first</sub>, *MIP*<sub>close</sub> and *MIP*<sub>center</sub>) and two different problem sizes: 2 profiles 3 criteria (2P 3C) and 2 profiles 5 criteria (2P 5C). The results show an expected trend in which the *Kendall's tau* values increase together with the number of pairs of alternatives used to learn the SRMP model and tend towards 1. We observe also that if the number of criteria increases, the maximum value for *Kendall's tau* that can be reached decreases, indicating that more learning examples are needed. The results also show that the heuristic *H*<sub>mp</sub> (depicted in black) seems to perform better than the others regardless of the considered MIP configuration and problem size. This is again validated using the *Kolmogorov-Smirnov* test. We also observe that *H*<sub>mp</sub> reaches a higher *Kendall's tau* value faster (i.e. with fewer learning examples). For example for the first graph in Figure 6 (2P 3C / *MIP*<sub>first</sub>), *H*<sub>mp</sub> reaches a *Kendall's tau* value of 0.9 around
<figure><img src="image_5.png" /><figcaption>Fig. 5 Mean Kendall's tau for 2P 3C using the different heuristics and *MIP*<sub>first</sub> configuration</figcaption></figure>

heuristics. Table 10 shows the corresponding p-values of the *Kolmogorov-Smirnov*, which are all below 0.05.

<table><caption>Table 10 *Kolmogorov-Smirnov* test results (p-values) for 2P 3C using *MIP*<sub>first</sub> configuration</caption><thead><tr><th></th><th><i>H</i><sub>rnd</sub></th><th><i>H</i><sub>sim</sub></th><th><i>H</i><sub>dis</sub></th><th><i>H</i><sub>cp</sub></th></tr></thead><tbody><tr><th><i>H</i><sub>mp</sub></th><td>0.00193</td><td>0.01216</td><td>4.785e-06</td><td>0.00193</td></tr></tbody></table>

Figure 6 depicts the mean value of the *Kendall's tau* for the three possible MIP configurations (*MIP*<sub>first</sub>, *MIP*<sub>close</sub> and *MIP*<sub>center</sub>) and two different problem sizes: 2 profiles 3 criteria (2P 3C) and 2 profiles 5 criteria (2P 5C). The results show an expected trend in which the *Kendall's tau* values increase together with the number of pairs of alternatives used to learn the SRMP model and tend towards 1. We observe also that if the number of criteria increases, the maximum value for *Kendall's tau* that can be reached decreases, indicating that more learning examples are needed. The results also show that the heuristic *H*<sub>mp</sub> (depicted in black) seems to perform better than the others regardless of the considered MIP configuration and problem size. This is again validated using the *Kolmogorov-Smirnov* test. We also observe that *H*<sub>mp</sub> reaches a higher *Kendall's tau* value faster (i.e. with fewer learning examples). For example for the first graph in Figure 6 (2P 3C / *MIP*<sub>first</sub>), *H*<sub>mp</sub> reaches a *Kendall's tau* value of 0.9 around
<figure><img src="image_7.png" /><figcaption>Fig. 6 Mean Kendall's tau for 2P 3C and 2P 5C</figcaption></figure>

iteration 50, while the other heuristics need more than 80 iterations pairs to reach the same value.

These observations serve to choose the $H_{mp}$ heuristic but not the MIP configuration ($MIP_{first}$, $MIP_{close}$ and $MIP_{center}$). As shown in Figure 7 it is not easy to choose specially between the $MIP_{first}$ and $MIP_{center}$ configurations. For that we have decided to consider the computation time (including selecting the learning pairs using a heuristic and solving the MIP) as a deciding factor.
<figure><img src="image_6.png" /><figcaption>Fig. 6 Mean Kendall's tau for 2P 3C and 2P 5C</figcaption></figure>

iteration 50, while the other heuristics need more than 80 iterations pairs to reach the same value.

These observations serve to choose the $H_{mp}$ heuristic but not the MIP configuration ($MIP_{first}$, $MIP_{close}$ and $MIP_{center}$). As shown in Figure 7 it is not easy to choose specially between the $MIP_{first}$ and $MIP_{center}$ configurations. For that we have decided to consider the computation time (including selecting the learning pairs using a heuristic and solving the MIP) as a deciding factor.
<figure><img src="image_8.png" /><figcaption>Fig. 7 Mean Kendall's tau of $H_{mp}$ for 2P 3C and 2P 5C</figcaption></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 8 Execution time for 2P 3C</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Fig. 7 Mean Kendall’s tau of $H_{mp}$ for 2P 3C and 2P 5C</figcaption></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 8 Execution time for 2P 3C</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>Fig. 9 Execution time for 2P 5C</figcaption></figure>

Figures 8 and 9 depict at each iteration the number of tests that have an execution time *below one, two, five, ten and thirty minutes, below and above one hour* for all the different combinations (heuristics and MIP configurations) for *2P 3C* and *2P 5C* respectively. For example in Figure 8 for *Hmp* / *MIPfirst* we can see that for 30 cases out of 100 the computation time to learn an SRMP model with 50 learning pairs is less than 1 minute while for the same configuration of *2P 5C* (Figure 9) for 20 cases out of 80 the computation time is less than 30 minutes.

We observe that the more the problem is complex the more the computation time increases and the *MIPfirst* configuration takes significantly less time compared to *MIPclose* and *MIPcenter* (for both problem sizes).

As a consequence, for both problem sizes, the best combination of a heuristic and a MIP configuration is identified as *Hmp* / *MIPfirst*.

In order to expand our study, a more complex problem (i.e. 2 profiles and 7 criteria) is tested but as shown in Table 11 the time needed for an exhaustive test of 2P 5C problems is about one year with more than twenty server instances with 20 CPUs and 30GB RAM each. Also, the trend observed in Figures 8 and 9 shows that computation time increases significantly with the number of criteria. Because of this, for problems containing 7 criteria, we decided to study only the *MIPfirst* configuration and compare the *Hmp* heuristic with the *Hrnd* one.

Figure 10 depicts the mean *Kendall's tau* at each iteration of *Hmp* and *Hrnd* for 2P 7C problems. We confirm our previous observation that *Hmp* performs better than *Hrnd* by using the *Kolmogorov-Smirnov* test.

We have also considered problems with SRMP models containing 3 profiles. However, due to the execution time (which is significantly higher than for models
<figure><img src="image_10.png" /><figcaption>Fig. 9 Execution time for 2P 5C</figcaption></figure>

Figures 8 and 9 depict at each iteration the number of tests that have an execution time *below one, two, five, ten and thirty minutes, below and above one hour* for all the different combinations (heuristics and MIP configurations) for *2P 3C* and *2P 5C* respectively. For example in Figure 8 for *Hmp* / *MIPfirst* we can see that for 30 cases out of 100 the computation time to learn an SRMP model with 50 learning pairs is less than 1 minute while for the same configuration of *2P 5C* (Figure 9) for 20 cases out of 80 the computation time is less than 30 minutes.

We observe that the more the problem is complex the more the computation time increases and the *MIPfirst* configuration takes significantly less time compared to *MIPclose* and *MIPcenter* (for both problem sizes).

As a consequence, for both problem sizes, the best combination of a heuristic and a MIP configuration is identified as *Hmp* / *MIPfirst*.

In order to expand our study, a more complex problem (i.e. 2 profiles and 7 criteria) is tested but as shown in Table 11 the time needed for an exhaustive test of 2P 5C problems is about one year with more than twenty server instances with 20 CPUs and 30GB RAM each. Also, the trend observed in Figures 8 and 9 shows that computation time increases significantly with the number of criteria. Because of this, for problems containing 7 criteria, we decided to study only the *MIPfirst* configuration and compare the *Hmp* heuristic with the *Hrnd* one.

Figure 10 depicts the mean *Kendall's tau* at each iteration of *Hmp* and *Hrnd* for 2P 7C problems. We confirm our previous observation that *Hmp* performs better than *Hrnd* by using the *Kolmogorov-Smirnov* test.

We have also considered problems with SRMP models containing 3 profiles. However, due to the execution time (which is significantly higher than for models
<table><caption>**Table 11** Rounded global execution time in days for an exhaustive test of 2P 5C</caption><thead><tr><th></th><th>Random</th><th>Similar</th><th>Dissimilar</th><th>CloseProfile</th><th>MaxProfiles</th></tr></thead><tbody><tr><td>First feasible</td><td>223</td><td>331</td><td>135</td><td>190</td><td>450</td></tr><tr><td>Min Distance</td><td>616</td><td>689</td><td>600</td><td>517</td><td>828</td></tr><tr><td>Center</td><td>793</td><td>1001</td><td>556</td><td>659</td><td>1151</td></tr></tbody></table>

<figure><img src="image_12.png" /><figcaption>**Fig. 10** Mean Kendall's tau of $H_{mp}$ and $H_{rnd}$ for 2P 7C</figcaption></figure>

with 2 profiles), we only tested the incremental process with a subset of the 100 problems for 3 profiles and 3 criteria (3P 3C. These results show again that $H_{mp}$ is significantly different from all the other heuristics, and provides better values for Kendall's tau with fewer iterations.

## 4.4 In practice

In this section we present how our results can be used in a practical context and give an answer to one of our research questions corresponding to the number of learning pairs / iterations that are needed to achieve a “good enough” SRMP model with an objective to reduce the cognitive effort of the DM.

An SRMP model is considered to be “good” by the DM if this model can reach a given Kendall's tau value. Once this is given, we use the mean Kendall's tau results from our experiments in order to find the number of pairs that would be required to reach this value. For example, Figure 11 depicts the mean Kendall's tau of $H_{mp} / MIP_{first}$ on the left, and the cumulative execution time on the right for 2P 3C, where the DM fixes $\tau = 0.8$. We observe that we need about 30 learning pairs and it would take about 18 minutes in total (on the left of Figure
<table><caption>**Table 11** Rounded global execution time in days for an exhaustive test of 2P 5C</caption><thead><tr><th></th><th>Random</th><th>Similar</th><th>Dissimilar</th><th>CloseProfile</th><th>MaxProfiles</th></tr></thead><tbody><tr><td>First feasible</td><td>223</td><td>331</td><td>135</td><td>190</td><td>450</td></tr><tr><td>Min Distance</td><td>616</td><td>689</td><td>600</td><td>517</td><td>828</td></tr><tr><td>Center</td><td>793</td><td>1001</td><td>556</td><td>659</td><td>1151</td></tr></tbody></table>

<figure><img src="image_11.png" /><figcaption>**Fig. 10** Mean Kendall's tau of $H_{mp}$ and $H_{rnd}$ for 2P 7C</figcaption></figure>

with 2 profiles), we only tested the incremental process with a subset of the 100 problems for 3 profiles and 3 criteria (3P 3C. These results show again that $H_{mp}$ is significantly different from all the other heuristics, and provides better values for Kendall's tau with fewer iterations.

## 4.4 In practice

In this section we present how our results can be used in a practical context and give an answer to one of our research questions corresponding to the number of learning pairs / iterations that are needed to achieve a “good enough” SRMP model with an objective to reduce the cognitive effort of the DM.

An SRMP model is considered to be “good” by the DM if this model can reach a given Kendall's tau value. Once this is given, we use the mean Kendall's tau results from our experiments in order to find the number of pairs that would be required to reach this value. For example, Figure 11 depicts the mean Kendall's tau of $H_{mp} / MIP_{first}$ on the left, and the cumulative execution time on the right for 2P 3C, where the DM fixes $\tau = 0.8$. We observe that we need about 30 learning pairs and it would take about 18 minutes in total (on the left of Figure
11). For the 2P 5C problem the DM fixes $τ = 0.8$ and we find that around 56 learning pairs (on the left of Figure 12) are required while around 1600 minutes of execution time would be required in total (on the right of Figure 12).

<figure><img src="image_13.png" /><figcaption>Fig. 11 Mean Kendall's tau and cumulative mean execution time of $H_{mp} / MIP_{first}$ for 2P 3C</figcaption></figure>

## 5 Conclusion

In this paper, we propose an incremental elicitation process for SRMP models in which we use a heuristic to select a pair of alternative at each iteration of the process. Different heuristics and MIP configurations have been studied in order to choose the combination that would reduce the most the cognitive effort of the DM. This corresponds to the $H_{mp} / MIP_{first}$ combination, due to its efficiency in both quality of the provided solution and reduced execution time.

The experiments show the limits of our proposal in terms of execution time. First it was not possible for us to perform more exhaustive tests for the more complex problems (more than 2 profiles and 7 criteria) due to the total expected time for these tests (despite the amount of computation resources used). Second, for a real-word use of this elicitation process, computing time is still an issue because at each iteration it could potentially take a lot of time to solve the MIP, specially if the number of learning examples increases, or the number of profiles and criteria become large.

To solve this last issue, we will pursue the study of a metaheuristic approach for inferring an SRMP model in a reasonable computing time. In real-world decision problems, another option could also be to use a SAT solver instead of the MIP
11). For the 2P 5C problem the DM fixes $τ = 0.8$ and we find that around 56 learning pairs (on the left of Figure 12) are required while around 1600 minutes of execution time would be required in total (on the right of Figure 12).

<figure><img src="image_12.png" /><figcaption>Fig. 11 Mean Kendall's tau and cumulative mean execution time of $H_{mp} / MIP_{first}$ for 2P 3C</figcaption></figure>

## 5 Conclusion

In this paper, we propose an incremental elicitation process for SRMP models in which we use a heuristic to select a pair of alternative at each iteration of the process. Different heuristics and MIP configurations have been studied in order to choose the combination that would reduce the most the cognitive effort of the DM. This corresponds to the $H_{mp} / MIP_{first}$ combination, due to its efficiency in both quality of the provided solution and reduced execution time.

The experiments show the limits of our proposal in terms of execution time. First it was not possible for us to perform more exhaustive tests for the more complex problems (more than 2 profiles and 7 criteria) due to the total expected time for these tests (despite the amount of computation resources used). Second, for a real-word use of this elicitation process, computing time is still an issue because at each iteration it could potentially take a lot of time to solve the MIP, specially if the number of learning examples increases, or the number of profiles and criteria become large.

To solve this last issue, we will pursue the study of a metaheuristic approach for inferring an SRMP model in a reasonable computing time. In real-world decision problems, another option could also be to use a SAT solver instead of the MIP
<figure><img src="image_14.png" /><figcaption>**Fig. 12** Mean Kendall's tau and cumulative mean execution time of *Hmp* / *MIP*<sub>first</sub> for 2P
5C</figcaption></figure>

one. We will additionally consider new heuristics for learning pairs selection and
expand our tests to more complex problems.

**Compliance with Ethical Standards**

The authors of this paper conform to the Springer Publishing Ethics Statement.
**Conflict of interest** The authors declare that they have no conflict of interest.
**Ethical approval** This article does not contain any studies with human par-
ticipants or animals performed by any of the authors.

**References**

1. Belahcène, K., Mousseau, V., Ouerdane, W., Pirlot, M., Sobrie, O.: Ranking with multiple reference points: Efficient elicitation and learning procedures (2018). URL https://hal.archives-ouvertes.fr/hal-01956128. In Proceedings from multiple criteria Decision aid to Preference Learning (DA2PL)

2. Benabbou, N., Perny, P., Viappiani, P.: Incremental elicitation of Choquet capac-
ities for multicriteria choice, ranking and sorting problems. Artificial Intelligence **246**, 152 – 180 (2017). DOI https://doi.org/10.1016/j.artint.2017.02.001. URL http://www.sciencedirect.com/science/article/pii/S0004370217300152

3. Bourdache, N., Perny, P., Spanjaard, O.: Incremental Elicitation of rank-dependent aggregation Functions based on Bayesian linear regression. In: IJCAI-19 - Twenty-Eighth International Joint Conference on Artificial Intelligence, pp. 2023–2029. International Joint Conferences on Artificial Intelligence Organization, Macao, China (2019). URL https://hal.archives-ouvertes.fr/hal-02202468

4. Boutilier, C., Patrascu, R., Poupart, P., Schuurmans, D.: Constraint-based optimization and utility elicitation using the minimax decision criterion. Artificial Intelligence
<figure><img src="image_13.png" /><figcaption>**Fig. 12** Mean Kendall's tau and cumulative mean execution time of *Hmp* / *MIP*<sub>first</sub> for 2P
5C</figcaption></figure>

one. We will additionally consider new heuristics for learning pairs selection and
expand our tests to more complex problems.

Compliance with Ethical Standards

The authors of this paper conform to the Springer Publishing Ethics Statement.
**Conflict of interest** The authors declare that they have no conflict of interest.
**Ethical approval** This article does not contain any studies with human par-
ticipants or animals performed by any of the authors.

References

1. Belahcène, K., Mousseau, V., Ouerdane, W., Pirlot, M., Sobrie, O.: Ranking with multiple reference points: Efficient elicitation and learning procedures (2018). URL https://hal.archives-ouvertes.fr/hal-01956128. In Proceedings from multiple criteria Decision aid to Preference Learning (DA2PL)

2. Benabbou, N., Perny, P., Viappiani, P.: Incremental elicitation of Choquet capac-
ities for multicriteria choice, ranking and sorting problems. Artificial Intelligence **246**, 152 – 180 (2017). DOI https://doi.org/10.1016/j.artint.2017.02.001. URL http://www.sciencedirect.com/science/article/pii/S0004370217300152

3. Bourdache, N., Perny, P., Spanjaard, O.: Incremental Elicitation of rank-dependent aggregation Functions based on Bayesian linear regression. In: IJCAI-19 - Twenty-Eighth International Joint Conference on Artificial Intelligence, pp. 2023–2029. International Joint Conferences on Artificial Intelligence Organization, Macao, China (2019). URL https://hal.archives-ouvertes.fr/hal-02202468

4. Boutilier, C., Patrascu, R., Poupart, P., Schuurmans, D.: Constraint-based optimization and utility elicitation using the minimax decision criterion. Artificial Intelligence
170(8), 686 – 713 (2006). DOI https://doi.org/10.1016/j.artint.2006.02.003. URL http://www.sciencedirect.com/science/article/pii/S0004370206000245

5. Boutilier, C., Patrascu, R., Poupart, P., Schuurmans, D.: Constraint-based optimization and utility elicitation using the minimax decision criterion. Artificial Intelligence **170**(8-9), 686–713 (2006)

6. Bouyssou, D., Marchant, T.: Multiattribute preference models with reference points. European Journal of Operational Research **229**(2), 470 – 481 (2013). DOI https://doi.org/10.1016/j.ejor.2013.02.046. URL http://www.sciencedirect.com/science/article/pii/S0377221713001951

7. Bouyssou, D., Marchant, T., Pirlot, M., Tsoukiàs, A., Vincke, P.: Evaluation and decision models with multiple criteria: Stepping stones for the analyst, 1st edn. International Series in Operations Research and Management Science, Volume 86. Boston (2006). URL http://www.springer.com/sgw/cda/frontpage/0,11855,4-40521-22-116132747-0,00.html

8. Bouyssou, D., Pirlot, M.: An axiomatic analysis of concordance discordance relations. European Journal of Operational Research **199**(2), 468 – 477 (2009). DOI https://doi.org/10.1016/j.ejor.2008.11.011. URL http://www.sciencedirect.com/science/article/pii/S0377221708009946

9. Butler, J., Jia, J., Dyer, J.: Simulation techniques for the sensitivity analysis of multicriteria decision models. European Journal of Operational Research **103**, 531–546 (1997)

10. Chajewska, U., Koller, D., Parr, R.: Making rational decisions using adaptive utility elicitation. AAAI Press / The MIT Press (2000). URL http://www.aaai.org/Library/AAAI/2000/aaai00-056.php

11. Ciomek, K., Kadziński, M., Tervonen, T.: Heuristics for selecting pair-wise elicitation questions in multiple criteria choice problems. European Journal of Operational Research **262**(2), 693 – 707 (2017). DOI https://doi.org/10.1016/j.ejor.2017.04.021. URL http://www.sciencedirect.com/science/article/pii/S0377221717303545

12. Dodge, Y.: Kolmogorov-Smirnov Test, pp. 283–287. Springer New York, New York, NY (2008)

13. Fan, J., Zhang, J., Mei, K., Peng, J., Gao, L.: Cost-sensitive learning of hierarchical tree classifiers for large-scale image classification and novel category detection. Pattern Recogn. **48**(5), 1673–1687 (2015). DOI 10.1016/j.patcog.2014.10.025. URL http://dx.doi.org/10.1016/j.patcog.2014.10.025

14. Figueira, J., Greco, S., Ehrgott, M. (eds.): Multiple Criteria Decision Analysis: State of the Art Surveys. Second edition. Kluwer Acad. Publ. (2016)

15. Figueira, J., Mousseau, V., Roy, B.: ELECTRE methods. In: J. Figueira, S. Greco, M. Ehrgott (eds.) Multiple Criteria Decision Analysis: State of the Art Surveys, pp. 133–162. Springer Verlag, Boston, Dordrecht, London (2005). URL http://www.springeronline.com/sgw/cda/frontpage/0,11855,5-165-22-34954528-0,00.html

16. Fürnkranz, J., Hüllermeier, E.: Preference learning and ranking by pairwise comparison, pp. 65–82. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)

17. Gholipour, A., Hosseini, M.J., Beigy, H.: An adaptive regression tree for non-stationary data streams. In: Proceedings of the 28th Annual ACM Symposium on Applied Computing, SAC ’13, pp. 815–817. ACM, New York, NY, USA (2013). DOI 10.1145/2480362.2480519. URL http://doi.acm.org/10.1145/2480362.2480519

18. Greco, S., Matarazzo, B., Slowinski, R.: Rough sets theory for multicriteria decision analysis. European Journal of Operational Research **129**(1), 1 – 47 (2001). DOI https://doi.org/10.1016/S0377-2217(00)00167-3. URL http://www.sciencedirect.com/science/article/pii/S0377221700001673

19. Holloway, H., White III, C.C.: Question selection for multi-attribute decision-aiding. European Journal of Operational Research **148**(3), 525 – 533 (2003). DOI https://doi.org/10.1016/S0377-2217(02)00436-8. URL http://www.sciencedirect.com/science/article/pii/S0377221702004368

20. Keeney, R., Raiffa, H.: Decisions with Multiple Consequences: Preferences and Value Tradeoffs. New York, NY: John Wiley & Sons (1976)

21. Kendall, M.G.: A new measure of rank correlation. Biometrika **30**(1/2), 81–93 (1938)

22. Liu, J., Ouerdane, W., Mousseau, V.: Metaheuristic approach for preference learning in multicriteria ranking based on reference points (2014). In Proceeding of the 2nd wokshop from multiple criteria Decision aid to Preference Learning (DA2PL)

23. Mousseau, V.: Eliciting information concerning the relative importance of criteria. In: P. Pardalos, Y. Siskos, C. Zopounidis (eds.) Advances in Multicriteria Analysis, pp. 17–43. Kluwer Academic, Dordrecht (1995)
170(8), 686 – 713 (2006). DOI https://doi.org/10.1016/j.artint.2006.02.003. URL http://www.sciencedirect.com/science/article/pii/S0004370206000245

5. Boutilier, C., Patrascu, R., Poupart, P., Schuurmans, D.: Constraint-based optimization and utility elicitation using the minimax decision criterion. Artificial Intelligence **170**(8-9), 686–713 (2006)

6. Bouyssou, D., Marchant, T.: Multiattribute preference models with reference points. European Journal of Operational Research **229**(2), 470 – 481 (2013). DOI https://doi.org/10.1016/j.ejor.2013.02.046. URL http://www.sciencedirect.com/science/article/pii/S0377221713001951

7. Bouyssou, D., Marchant, T., Pirlot, M., Tsoukiàs, A., Vincke, P.: Evaluation and decision models with multiple criteria: Stepping stones for the analyst, 1st edn. International Series in Operations Research and Management Science, Volume 86. Boston (2006). URL http://www.springer.com/sgw/cda/frontpage/0,11855,4-40521-22-116132747-0,00.html

8. Bouyssou, D., Pirlot, M.: An axiomatic analysis of concordance discordance relations. European Journal of Operational Research **199**(2), 468 – 477 (2009). DOI https://doi.org/10.1016/j.ejor.2008.11.011. URL http://www.sciencedirect.com/science/article/pii/S0377221708009946

9. Butler, J., Jia, J., Dyer, J.: Simulation techniques for the sensitivity analysis of multicriteria decision models. European Journal of Operational Research **103**, 531–546 (1997)

10. Chajewska, U., Koller, D., Parr, R.: Making rational decisions using adaptive utility elicitation. AAAI Press / The MIT Press (2000). URL http://www.aaai.org/Library/AAAI/2000/aaai00-056.php

11. Ciomek, K., Kadziński, M., Tervonen, T.: Heuristics for selecting pair-wise elicitation questions in multiple criteria choice problems. European Journal of Operational Research **262**(2), 693 – 707 (2017). DOI https://doi.org/10.1016/j.ejor.2017.04.021. URL http://www.sciencedirect.com/science/article/pii/S0377221717303545

12. Dodge, Y.: Kolmogorov-Smirnov Test, pp. 283–287. Springer New York, New York, NY (2008)

13. Fan, J., Zhang, J., Mei, K., Peng, J., Gao, L.: Cost-sensitive learning of hierarchical tree classifiers for large-scale image classification and novel category detection. Pattern Recogn. **48**(5), 1673–1687 (2015). DOI 10.1016/j.patcog.2014.10.025. URL http://dx.doi.org/10.1016/j.patcog.2014.10.025

14. Figueira, J., Greco, S., Ehrgott, M. (eds.): Multiple Criteria Decision Analysis: State of the Art Surveys. Second edition. Kluwer Acad. Publ. (2016)

15. Figueira, J., Mousseau, V., Roy, B.: ELECTRE methods. In: J. Figueira, S. Greco, M. Ehrgott (eds.) Multiple Criteria Decision Analysis: State of the Art Surveys, pp. 133–162. Springer Verlag, Boston, Dordrecht, London (2005). URL http://www.springeronline.com/sgw/cda/frontpage/0,11855,5-165-22-34954528-0,00.html

16. Fürnkranz, J., Hüllermeier, E.: Preference learning and ranking by pairwise comparison, pp. 65–82. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)

17. Gholipour, A., Hosseini, M.J., Beigy, H.: An adaptive regression tree for non-stationary data streams. In: Proceedings of the 28th Annual ACM Symposium on Applied Computing, SAC ’13, pp. 815–817. ACM, New York, NY, USA (2013). DOI 10.1145/2480362.2480519. URL http://doi.acm.org/10.1145/2480362.2480519

18. Greco, S., Matarazzo, B., Slowinski, R.: Rough sets theory for multicriteria decision analysis. European Journal of Operational Research **129**(1), 1 – 47 (2001). DOI https://doi.org/10.1016/S0377-2217(00)00167-3. URL http://www.sciencedirect.com/science/article/pii/S0377221700001673

19. Holloway, H., White III, C.C.: Question selection for multi-attribute decision-aiding. European Journal of Operational Research **148**(3), 525 – 533 (2003). DOI https://doi.org/10.1016/S0377-2217(02)00436-8. URL http://www.sciencedirect.com/science/article/pii/S0377221702004368

20. Keeney, R., Raiffa, H.: Decisions with Multiple Consequences: Preferences and Value Tradeoffs. New York, NY: John Wiley & Sons (1976)

21. Kendall, M.G.: A new measure of rank correlation. Biometrika **30**(1/2), 81–93 (1938)

22. Liu, J., Ouerdane, W., Mousseau, V.: Metaheuristic approach for preference learning in multicriteria ranking based on reference points (2014). In Proceeding of the 2nd wokshop from multiple criteria Decision aid to Preference Learning (DA2PL)

23. Mousseau, V.: Eliciting information concerning the relative importance of criteria. In: P. Pardalos, Y. Siskos, C. Zopounidis (eds.) Advances in Multicriteria Analysis, pp. 17–43. Kluwer Academic, Dordrecht (1995)
24. Mousseau, V., Figueira, J., Dias, L., Gomes da Silva, C., Climaco, J.: Resolving inconsistencies among constraints on the parameters of an MCDA model. European Journal of Operational Research 147(1), 72–93 (2003). DOI https://doi.org/10.1016/S0377-2217(02)00233-3

25. Mousseau, V., Pirlot, M.: Preference elicitation and learning. EURO Journal on Decision Processes 3(1-2), 1 (2015)

26. Olteanu, A.: Strategies for the incremental inference of majority-rule sorting models (2018). URL https://hal.archives-ouvertes.fr/hal-01947853. In Proceeding from multiple criteria Decision aid to Preference Learning (DA2PL)

27. Olteanu, A.L., Belahcène, K., Mousseau, V., Ouerdane, W., Rolland, A., Zheng, J.: Preference elicitation for a ranking method based on multiple reference profiles (2018). URL https://hal.archives-ouvertes.fr/hal-01862334. Working paper or preprint

28. Perny, P., Rolland, A.: Reference-dependent qualitative models for decision making under uncertainty. In: Proceedings of the 2006 Conference on ECAI 2006: 17th European Conference on Artificial Intelligence August 29 – September 1, 2006, Riva Del Garda, Italy, p. 422426. IOS Press, NLD (2006)

29. Rolland, A.: Reference-based preferences aggregation procedures in multi-criteria decision making. European Journal of Operational Research 225(3), 479–486 (2013). DOI 10.1016/j.ejor.2012.10.013. URL https://doi.org/10.1016/j.ejor.2012.10.013

30. Roy, B.: The outranking approach and the foundations of ELECTRE methods. Theory and Decision 31(1), 49–73 (1991). URL https://doi.org/10.1007/BF00134132

31. Roy, B.: Multicriteria Methodology for Decision Aiding. Kluwer Academic, Dordrecht (1996)

32. Salperwyck, C., Lemaire, V.: Incremental decision tree based on order statistics. In: The 2013 International Joint Conference on Neural Networks (IJCNN), pp. 1–8 (2013). DOI 10.1109/IJCNN.2013.6706907

33. Settles, B.: Active learning, volume 6 of synthesis lectures on artificial intelligence and machine learning. Morgan & Claypool (2012)

34. Syed, S.S., Aayush, A., Kaushik, R.: Incremental learning in deep convolutional neural networks using partial network sharing. CoRR abs/1712.02719 (2017). URL http://arxiv.org/abs/1712.02719

35. Wen, Y., Lu, B.: Incremental learning of support vector machines by classifier combining. In: Z. Zhou, H. Li, Q. Yang (eds.) Advances in Knowledge Discovery and Data Mining, pp. 904–911. Springer Berlin Heidelberg, Berlin, Heidelberg (2007)
24. Mousseau, V., Figueira, J., Dias, L., Gomes da Silva, C., Climaco, J.: Resolving inconsistencies among constraints on the parameters of an MCDA model. European Journal of Operational Research 147(1), 72–93 (2003). DOI https://doi.org/10.1016/S0377-2217(02)00233-3

25. Mousseau, V., Pirlot, M.: Preference elicitation and learning. EURO Journal on Decision Processes 3(1-2), 1 (2015)

26. Olteanu, A.: Strategies for the incremental inference of majority-rule sorting models (2018). URL https://hal.archives-ouvertes.fr/hal-01947853. In Proceeding from multiple criteria Decision aid to Preference Learning (DA2PL)

27. Olteanu, A.L., Belahcène, K., Mousseau, V., Ouerdane, W., Rolland, A., Zheng, J.: Preference elicitation for a ranking method based on multiple reference profiles (2018). URL https://hal.archives-ouvertes.fr/hal-01862334. Working paper or preprint

28. Perny, P., Rolland, A.: Reference-dependent qualitative models for decision making under uncertainty. In: Proceedings of the 2006 Conference on ECAI 2006: 17th European Conference on Artificial Intelligence August 29 – September 1, 2006, Riva Del Garda, Italy, p. 422426. IOS Press, NLD (2006)

29. Rolland, A.: Reference-based preferences aggregation procedures in multi-criteria decision making. European Journal of Operational Research 225(3), 479–486 (2013). DOI 10.1016/j.ejor.2012.10.013. URL https://doi.org/10.1016/j.ejor.2012.10.013

30. Roy, B.: The outranking approach and the foundations of ELECTRE methods. Theory and Decision 31(1), 49–73 (1991). URL https://doi.org/10.1007/BF00134132

31. Roy, B.: Multicriteria Methodology for Decision Aiding. Kluwer Academic, Dordrecht (1996)

32. Salperwyck, C., Lemaire, V.: Incremental decision tree based on order statistics. In: The 2013 International Joint Conference on Neural Networks (IJCNN), pp. 1–8 (2013). DOI 10.1109/IJCNN.2013.6706907

33. Settles, B.: Active learning, volume 6 of synthesis lectures on artificial intelligence and machine learning. Morgan & Claypool (2012)

34. Syed, S.S., Aayush, A., Kaushik, R.: Incremental learning in deep convolutional neural networks using partial network sharing. CoRR abs/1712.02719 (2017). URL http://arxiv.org/abs/1712.02719

35. Wen, Y., Lu, B.: Incremental learning of support vector machines by classifier combining. In: Z. Zhou, H. Li, Q. Yang (eds.) Advances in Knowledge Discovery and Data Mining, pp. 904–911. Springer Berlin Heidelberg, Berlin, Heidelberg (2007)