Alexandru-Liviu Olteanu

Khaled Belahcène

Vincent Mousseau
email: vincent.mousseau@centralesupelec.fr

Wassila Ouerdane

Antoine Rolland

Jun Zheng

Preference Elicitation for a Ranking Method based on Multiple Reference Profiles

Keywords: multi-criteria decision aiding, preference elicitation, ranking problem, reference profiles

Multiple Criteria Decision Aid (MCDA) metholodolgies support decision makers (DM) facing decisions involving conflicting objectives. DM's preferences should be captured to provide meaningful recommendations. Preference elicitation aims at incorporating DM's preferences in decision models. We propose preference elicitation tool for a new ranking model based on reference points (S-RMP). Our methodology infers an S-RMP model from a list of pairwise comparisons provided by the DM. The inference algorithm makes use of a Mixed Integer mathematical programming formulation. We prove the applicability by performing extensive numerical experiments on datasets whose size corresponding to real-world problem.

Introduction

In the field of Multiple Criteria Decision Aiding (MCDA), real world decision problems can be modeled using three classes of problems formulations (see for instance [START_REF] Roy | Multicriteria Methodology for Decision Aiding[END_REF]): choice, ranking and sorting. Choice refers to the selection of the best alternative(s), ranking seeks to order all of the alternatives from the best one to the worst, whereas sorting aims at assigning each alternative to one of the predefined ordered categories. In this paper, we consider the ranking problem.

Several aggregation methods have been proposed in the literature to rank order a set of alternatives (see for instance [START_REF] Figueira | Multiple Criteria Decision Analysis:State of the Art Surveys[END_REF][START_REF] Figueira | ELECTRE methods. Multiple Criteria Decision Analysis: State of the Art Surveys[END_REF][START_REF] Keeney | Decision with multiple objectives: preference and values tradeoffs[END_REF]). In this paper, we are interested in a recently proposed method based on outranking relations, called Ranking based on Multiple reference Profiles (RMP) [START_REF] Rolland | Reference-based preferences aggregation procedures in multi-criteria decision making[END_REF][START_REF] Bouyssou | Multiattribute preference models with reference points[END_REF], which provides a ranking of alternatives by comparing alternatives to a set of reference profiles. More precisely, we focus on a simplified version of this RMP ranking model, named S-RMP. This ranking method is based on pairwise comparisons, but instead of directly comparing alternatives one to each other, it rather compares each alternative to a set of predefined external reference profiles. The idea is to construct a preference relation on the set of alternatives based on the way each alternative compares with the specified reference profiles.

When used in context with a specific Decision Maker (DM), the S-RMP ranking model should be tuned so that it accurately reflects the DM viewpoints. Preference elicitation is the process by which an analyst and a decision maker interact in order to set the values for the preference parameters. The direct elicitation approach requires the DM to give explicitly numerical values for the model parameters, whereas the indirect approach uses holistic information provided by the decision maker in order to infer the model parameters (see e.g. [START_REF] Jacquet-Lagrèze | Preference disaggregation: 20 years of MCDA experience[END_REF][START_REF] Mousseau | Preference elicitation and learning EURO Journal of Decision Processes[END_REF]). The direct elicitation approach is generally considered too difficult to apply in practice, as the DM has no clear understanding of the link between the parameters values and the resulting ranking [START_REF] Bouyssou | Evaluation and decision models with multiple criteria : stepping stones for the analyst[END_REF]. The indirect approach, on the other hand, reduces the cognitive effort required from DM who is asked to express holistic judgments on alternatives only (e.g. pairwise comparisons of alternatives).

In this work we propose an indirect approach to elicit the parameters of the S-RMP model from pairwise comparisons expressed by the decision maker. We formulate the elicitation algorithm as a mixed linear optimization problem. In this optimization program, the variables are the parameters of the S-RMP method, the constraints represents the binary comparisons expressed by the decision maker, and the objective function maximizes the number of restored comparisons.

The paper is structured in the following way: Section 2 presents a state of the art on multicriteria ranking method in general and reference-based methods in particular. Section 3 introduces the reader to the S-RMP method through a simple example. In Section 4 we provide the technical details on the preference elicitation algorithm in order to infer an S-RMP model. Section 5 provides a numerical analysis of the behavior of the inference algorithm. We finish with the concluding remarks and perspectives for future work in Section 6.

State-of-the-art

MCDA methods are generally classified into two families. The first one concerns methods based on multi-attribute value theory (MAVT) (see [START_REF] Keeney | Decision with multiple objectives: preference and values tradeoffs[END_REF]), while the second includes pairwise comparison methods based (so called outranking methods, see [START_REF] Roy | The outranking approach and the foundations of ELECTRE methods[END_REF]). In this paper, we are interested in a ranking method based on the construction of an outranking relation.

In outranking methods, a preference relation called outranking relation is built between pairs of alternatives evaluated on multiple criteria. It is defined as a weak preference relation on the set of alternatives whose meaning is "at least as good as". An alternative a outranks another one b, i.e. a b, if there are strong enough arguments to declare that a is at least as good as b, and if there is no essential reason to refute the statement. Outranking methods includes methods like ELECTRE [START_REF] Roy | The outranking approach and the foundations of ELECTRE methods[END_REF], PROMETHEE [START_REF] Brans | PROMETHEE: a new family of outranking methods in multicriteria analysis[END_REF], TACTIC [START_REF] Vansnick | On the problem of weights in multiple criteria decision making (the noncompensatory approach)[END_REF]. The popularity of such methods lies in their ability to deal with ordinal scales, limited input data and to represent non-compensatory preferences [START_REF] Bouyssou | Evaluation and decision models with multiple criteria : stepping stones for the analyst[END_REF][START_REF] Figueira | ELECTRE methods. Multiple Criteria Decision Analysis: State of the Art Surveys[END_REF].

The S-RMP ranking method is an outranking method which involves the use of external profiles to rank alternatives. Numerous studies report psychological evidence that decision makers make decisions based on some references, which can be the current status or their expectations (see for more details [START_REF] Knetsch | The endowment effect and evidence of nonreversible indifference curves[END_REF][START_REF] Tversky | Loss aversion in riskless choice: A reference-dependent model[END_REF][START_REF] Samuelson | Status quo bias in decision making[END_REF][START_REF] Köszegi | A model of reference-dependent preferences[END_REF]). The use of reference profiles in preference relations has been already studied in the MCDA literature. For instance, several multi-criteria optimization methods are based on the use of an ideal point. The TOPSIS (the Technique for Order of Preference by Similarity to Ideal Solution) method [START_REF] Hwang | A new approach for multiple objective decision making[END_REF] evaluates an alternative by maximizing the distance between the alternative and an anti-ideal point while minimizing the distance to the ideal point. MACBETH [START_REF] Bana E Costa | Cl Vansnick MACBETH: an interactive path towards the construction of cardinal value functions[END_REF] uses two fictitious reference levels on criteria ("good " and "neutral ") to support in the elicitation of a value based model. Reference profiles are also used in sorting problems. For instance, the ELECTRE TRI sorting method [START_REF] Roy | The outranking approach and the foundations of ELECTRE methods[END_REF][START_REF] Figueira | ELECTRE methods. Multiple Criteria Decision Analysis: State of the Art Surveys[END_REF] compares alternatives to ordered reference profiles which represent the lower and upper bound of categories. The assignment rules of ELECTRE TRI are very similar to S-RMP. However their output differs; S-RMP provides a weak ranking of the alternatives while ELECTRE TRI produces a partition of alternatives into predefined categories. Therefore the result can be more discriminative for S-RMP than for ELECTRE TRI. S-RMP is a method which makes use of pairwise comparisons to derive a ranking. It is well known that multicriteria methods which rely on pairwise comparisons to compute a ranking face a structural difficulty: the presence of Condorcet cycles in the outranking relation. Indeed, the preference relation over alternatives resulting from a weighted majority voting of criteria is not necessarily transitive (see [START_REF] Condorcet | Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix[END_REF]). This is why most ranking methods that rely on an outranking relation transform this relation into a transitive ranking, using a so-called exploitation procedure (see e.g. [START_REF] Brans | PROMETHEE: a new family of outranking methods in multicriteria analysis[END_REF][START_REF] Figueira | ELECTRE methods. Multiple Criteria Decision Analysis: State of the Art Surveys[END_REF]). To circumvent the issue of Condorcet cycles, the S-RMP method proceeds in a slightly different way: pairwise comparisons are not used to compare alternatives one to each other, but to compare alternatives to external profiles (as it is done in Electre Tri [START_REF] Figueira | ELECTRE methods. Multiple Criteria Decision Analysis: State of the Art Surveys[END_REF]). Hence, no outranking relation is build on the set A of alternatives; the outranking relation considered in S-RMP compares alternatives in A with the reference profiles in P, i.e, ⊆ A × P ∪ P × A. As S-RMP imposes a dominance structure on the profiles (see Section 3.2), the relation will have no cycles.

Apart from S-RMP1 , outranking based ranking methods rank (order) alternatives according to the way each alternative compare to others. This means that the presence or absence of an alternative c can impact the relative rank of two other alternatives a and b (for instance if a is prefered to c, and c is prefered to b). In other words, these outranking methods do not fulfill the property of the Independence of Irrelevant Alternative (IIA), see e.g. for ELECTRE III [START_REF] Figueira | ELECTRE methods. Multiple Criteria Decision Analysis: State of the Art Surveys[END_REF], [START_REF] Wang | Ranking irregularities when evaluating alternatives by using some ELECTRE methods[END_REF]. Note that fulfilling the IIA property (or not) is neither positive nor negative (one can argue that when a is prefered to c, and c is prefered to b, it grants a comparative advantage of a over b, or not). This observation has however an important implication concerning indirect preference elicitation with outranking based ranking methods. Suppose we want to rank alternatives in a set A using an outranking based ranking method called M ; we would like to infer the parameters values of this ranking method M from a list of pairwise comparisons provided by the decision maker. Let us denote A * ⊂ A the alternatives involved in these comparisons, and suppose that two of these alternatives a, b ∈ A * are judged by the decision maker such that a is prefered to b. If the IIA property is not fulfilled by M , there is no formal guaranty that the ranking on A resulting from the use of the method M using the parameters inferred from the pairwise comparisons of alternatives in A * will rank a better than b. Indeed b could be ranked better than a, and this would be difficult to understand from the decision maker perspective. This is why it is usually difficult to use outranking based ranking method using indirect preference elicitation.

Therefore, the S-RMP method has a unique advantage over the other outranking based ranking methods, as it is, up to our knowledge, the only outranking based ranking method which fulfills the IIA property. Therefore, this ranking method can meaningfully be used in an indirect elicitation perspective. In what follows, we propose a preference elicitation algorithm to learn the parameters of the S-RMP method from pairwise comparisons provided by the decision maker.

S-RMP: a Simple Ranking model based on Multiple Profiles

Illustrative example

In order to provide an overview of how the S-RMP ranking method proceeds, we provide a small didactic example. Let us consider a decision problem in which cars should be ranked, based on their attractiveness from a buyer's perspective. For the sake of the example, we consider three cars: x, y and z. Each car is evaluated on four criteria: the price (in ke, to be minimized), the confidence in the brand ([0,100] scale, the greater the better), the fuel consumption (liters per 100 km to be minimized), and acceleration (time in seconds to accelerate from 0 to 100 km/h to be minimized). The performance of cars are presented in Table 1.

In order to model the judgment of the decision-maker, the S-RMP method makes use of the following preference parameters: (i) reference profiles, (ii) a lexicographic order on these profiles and (iii) criteria weights.

In our example, we use two reference profiles denoted with p 1 and p 2 (which are vectors of evaluations), such that p 2 j is better that p 1 j on each criterion j. The value of these two profiles are provided in Table 1. The dominance structure on these two profiles (p 2 dominates p 1 ) allows to define, on each criterion, three segments on the evaluation scales: better than p 2 (which can be interpreted as "good"), between p 1 and p 2 (which can be interpreted as "intermediate or fair"), and worse than p 1 (which can be interpreted as "insufficient").

In other terms, the reference profiles specify 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 better than p 2 on each criterion are denoted A, B performances between p 1 and p 2 on each criterion are denoted B, C performances worse than p 1 on each criterion are denoted C. The S-RMP method ranks cars based on how they compare to profiles p 1 and p2 . Table 2 shows the encoding of the three cars considered in our example. In addition, a lexicographic order is considered among the reference profiles; this order defines the order by which each car is compared to the profiles. In our case, this order can either be "compare cars to p 1 then to p 2 " or "compare cars to p 2 then p 1 ". We consider in this example the first one ("compare cars to p 1 then to p 2 "). To compute a ranking, alternatives are not compared one to each other but each one is compared to the reference profiles. First, alternatives are compared to the first profile in the lexicographic order (here p 1 ). Considering two alternatives a and b, a is prefered to b, denoted (a b), if the number 2 of criteria for which alternative a is evaluated A or B (i.e. better than p 1 ) is greater than the number of criteria for which alternative b is evaluated A or B. If a and b cannot be distinguished with respect to their comparison to p 1 , then a and b are compared to p 2 (the second reference profile in the lexicographic order). If the number of criteria for which alternative a is evaluated A (i.e. better than p 2 ) is greater than the number of criteria for which alternative is evaluated A, then a is prefered to b, otherwise a and b are indifferent. In our example, we have thus the following:

Price Confidence in the brand Consumption Acceleration

x B A B A y B B A C z B C A A
• Car x is better than car y because, x is evaluated A or B on all criteria while y is evaluated A or B on three criteria only (x compares better to p 1 than y does).

• Car x is better than car z because, x has evaluations A or B on all criteria while z has evaluations A or B on three criteria only (x compares better to p 1 than z does).

• Car z is better than car y because z and y are both evaluated A or B on three criteria (they compare equally to p 1 ), but z is evaluated A on two criteria while y is evaluated A once only (z compares better to p 2 than y does).

The final ranking is thus: x is the best car, followed by z and then y.

The S-RMP ranking method

Let us consider a finite set of alternatives A evaluated on m criteria. We denote M = {1, 2, . . . , j, . . . , m} the set of criteria indices, while a j denotes the evaluation of alternative a ∈ A on criterion j (in what follows we will consider, without loss of generality, that preferences increase with the evaluation on each criterion, i.e. the greater the better). Thus, X = j∈M X j denotes the Cartesian product of evaluations scales X j . The S-RMP method makes use of three different types of parameters:

• P = {P h , h = 1, . . . , k} a set of k profiles, with p h = {p h 1 , . . . , p h j , . . . , p h m }
, where p h j denotes the evaluation of profile p h on criterion j; we pose without loss of generality3 a dominance structure on the set of profiles, i.e, p h j ≤ p h+1 j , ∀h = 1..k -1, ∀j ∈ M .

• σ, a lexicographic order on the reference profiles, i.e., a permutation on {1, . . . , k}. Note that the lexicographic order σ can be any total order on profiles.

• criteria weights w 1 , w 2 , . . . , w m , where w j ≥ 0 and j∈M w j = 1 S-RMP proceeds by using a three-step procedure:

1. compute C(a, p h ) = {j ∈ M : a j ≥ p h j } with a ∈ A, h = 1, . . . , k, the set of criteria on which alternative a is at least as good as profile p h . 2. compare alternatives one to each other in order to define k preference relations p h , relative to each reference profile such that a p h b iff j∈C(a,p h ) w j ≥ j∈C(b,p h ) w j . In other words, a p h b holds when a compares better to p h than b does. We will denote p h (∼ p h , respectively) the asymmetric part (the symmetric part, respectively) of the relation

The preference elicitation algorithm

In order to set the parameters of an aggregation method, it is necessary to interact with the decision maker, so as to integrate her preferences. A first approach (referred as direct elicitation in the literature) assumes that the DM understands very well the model and is at ease with expressing the values of its parameters. However, such approach is not always recommended as the DM has usually not a clear understanding of the semantics attached to the preference parameters. Therefore, the literature frequently proposes indirect elicitation (see e.g. [START_REF] Mousseau | Inferring an ELECTRE TRI model from assignment examples[END_REF][START_REF] Leroy | Learning the parameters of a multiple criteria sorting method[END_REF]), in which the decision maker expresses holistic preferences (i.e. pairwise comparisons on real or fictitious alternatives) from which the values of the parameters are inferred.

We propose to infer, from pairwise comparisons expressed by the DM, the parameters of a S-RMP model involving:

• the k reference profiles P = {p h , h = 1, . . . , k}, with p h = {p h 1 , . . . , p h j , . . . p h m };

• the criteria weights w j , j ∈ M , , where w j ≥ 0 and j∈M w j = 1;

• the lexicographic order on reference profiles σ.

Principle

We propose an indirect elicitation procedure for the S-RMP model, in which the decision maker provides a list BC of binary comparisons of alternatives (a partial ranking), from which the S-RMP preference parameters (weights, reference profiles, and the lexicographic order on reference profiles) are inferred. More precisely, two sets are considered BC and BC ∼ , such that BC = BC ∪ BC ∼ where BC represents the pairs (x, y) for which the decision maker stated that x is prefered to y, while BC ∼ includes the pairs which are indifferent. We will denote A * the set of alternatives involved in BC.

With a given number of profiles k, we examine all the k! possible lexicographic orders 4 to identify the S-RMP model that best matches BC. Given an order on reference profiles (i.e., for a given lexicographic order σ), determining whether an S-RMP model fulfilling the preference relations in BC and the indifference relations in BC ∼ amounts to solve a Mixed Integer Program (MIP). The formulation of this MIP is presented below.

Mathematical Program for the elicitation algorithm

We begin by modeling whether or not an alternative a ∈ A * is at least as good as a reference profile p h , h = 1, . . . , k on a given criterion j ∈ M . We use the binary variables δ j (a, p h ) defined on the left, and the linear constraints on the right, in order to do this:

δ j (a, p h ) = 1 , if a j p h j 0 , otherwise.      δ j (a, p h ) a j -p h j + γ a j -p h j δ j (a, p h ) -1 δ j (a, p h ) ∈ {0, 1} (1)
where γ > 0 is a very small value used for modeling strict inequalities. The first constraint restricts δ j (a, p h ) to 1 when a j p h j , while the second constraint restricts it to 0 when a j < p h j . In order to construct the weighted support of a p h , we define another variable ω j (a, p h ). We define this variable below, along with the linear constraints needed to model it:

ω j (a, p h ) = w j , if a j p h j 0 , otherwise.          ω j (a, p h ) 0 δ j (a, p h ) ω j (a, p h ) w j ω j (a, p h ) ω j (a, p h ) δ j (a, p h ) + w j -1 (2)
The linear constraints serve the purpose of giving ω j (a, p h ) the minimum value between w j and δ j (a, p h ), therefore making ω j (a, p h ) equal to w j if a j p h and 0 otherwise.

Using the previously presented variables and constraints, given a lexicographic order on the profiles σ, we may now proceed to modeling the input of the DM in the form of a b for a given pair of alternatives (a, b) ∈ BC . For such a preference to be modeled, we need to find a profile p σ(i) , i = 1 . . . k, such that:

     j∈M ω j (a, p σ(i) ) > j∈M ω j (b, p σ(i) ) j∈M ω j (a, p σ(h) ) = j∈M ω j (b, p σ(h) ), ∀h ∈ 1..i -1 (3)
We will use a set of k -1 binary variables s(a, b, p h ), ∀(a, b) ∈ BC , ∀ p h ∈ P in order to model this. If we consider the first profile in the lexicographic order, p σ(1) , we define the following linear constraints:

           j∈M ω j (a, p σ(1) ) j∈M ω j (b, p σ(1) ) + γ -s(a, b, p σ(1) ) • (1 + γ) j∈M ω j (a, p σ(1) ) j∈M ω j (b, p σ(1) ) -(1 -s(a, b, p σ(1) )) j∈M ω j (a, p σ(1) ) j∈M ω j (b, p σ(1) ) + (1 -s(a, b, p σ(1) )) (4)
The first constraint is used to model that j∈M ω j (a, p σ(1) ) > j∈M ω j (b, p σ(1) ) whereas the following two constraints model that j∈M ω j (a, p σ(1) ) = j∈M ω j (b, p σ(1) ). The s(a, b, p σ(1) ) variable acts as a switch between the two statements, with the first being true for s(a, b, p σ(1) ) = 0 and the second statement being true for s(a, b, p σ(1) ) = 1.

We may extend these constraints to the subsequent reference profiles with respect to the lexicographic order, however, we additionally need to relax them for all profiles in this order which follow the profile which is able to discriminate between a and b, i.e. p σ(i) . We achieve this by generalizing Equation (4), ∀h ∈ 2 . . . k -1 as follows:

           j∈M ω j (a, p σ(h) ) j∈M ω j (b, p σ(h) ) + γ -s(a, b, p σ(h) ) • (1 + γ) -(1 -s(a, b, p σ(h-1) )) j∈M ω j (a, p σ(h) ) j∈M ω j (b, p σ(h) ) -(1 -s(a, b, p σ(h) )) -(1 -s(a, b, p σ(h-1) )) j∈M ω j (a, p σ(h) ) j∈M ω j (b, p σ(h) ) + (1 -s(a, b, p σ(h) )) + (1 -s(a, b, p σ(h-1) )) (5)
By adding the s(a, b, p σ(h-1) ) variables at the end of all three constraints, only when the previous profile in the lexicographic order (p σ(h-1) ), was not able to model the preference relation between a and b (i.e. s(a, b, p σ(h-1) ) = 1) the constraints on profile p σ(h) are kept. On the other hand, if the previous profile was able to model the preference relation (i.e. s(a, b, p σ(h-1) ) = 0) then the constraints on p σ(h) are relaxed. We have not included in the previous equations the last profile in the lexicographic order, as in this case we only need the following constraint:

j∈M ω j (a, p σ(k) ) j∈M ω j (b, p σ(k) ) + γ -s(a, b, p σ(k-1) ) • (1 -γ) (6)
This constraint forces the last profile in the lexicographic order to model that a b when all of the previous profiles were not able to do so (i.e. s(a, b, p σ(k-1) ) = 0).

Modeling the input of the DM in the form of a ∼ b for a given pair of alternatives (a, b) ∈ BC ∼ is done using only one constraint for each reference profile and no binary variables:

j∈M ω j (a, p σ(h) ) = j∈M ω j (b, p σ(h) ), ∀h ∈ 1, . . . , k (7)
We present the full mixed-integer linear program in Table 3. Constraints ( 8) and ( 9) are used to fix the sum of the weights to 1 and to make them non-null. The following three constraints limit the evaluations of the reference profiles to the [0, 1] interval as well as enforce the dominance constraints between them. Constraints ( 13) and ( 14) correspond to Eq. ( 1), whereas constraints [START_REF] Keeney | Decision with multiple objectives: preference and values tradeoffs[END_REF] to [START_REF] Leroy | Learning the parameters of a multiple criteria sorting method[END_REF] correspond to Eq. ( 2). The subsequent five constraints simplify those from Eq. ( 4), ( 5) and ( 6) by adding two dummy s variables, s 0 and s k . s 0 is fixed to 1 so that Eq. ( 4) is accurately modeled, whereas s k is fixed to 0 in order to model Eq. [START_REF] Bouyssou | Multiattribute preference models with reference points[END_REF]. Note that σ has also been extended in order to properly model these constraints with σ(0) = 0 and σ(k) = k. Finally, constraint ( 24) is used to model the pairs of indifferent alternatives in In.

The mixed integer linear program from Table 3 is used to find a S-RMP model only when the preference and indifference relations provided by the DM on the alternatives in A * allow for such a model to be constructed. In order to account for inconsistent pair-wise comparisons, the presented program may be easily converted to maximize the number of fulfilled pair-wise comparisons. First of all, constraint [START_REF] Liu | Preference Elicitation for Multi-Criteria Ranking with Multiple Reference Points[END_REF] needs to be removed, whereas constraint [START_REF] Roy | Multicriteria Methodology for Decision Aiding[END_REF] needs to be replaced by the following two constraints:

     j∈M ω j (a, p σ(h) ) j∈M ω j (b, p σ(h) ) -(1 -s * (a, b)), ∀a, b ∈ BC ∼ , ∀h ∈ 1..k j∈M ω j (b, p σ(h) ) j∈M ω j (a, p σ(h) ) -(1 -s * (a, b)), ∀a, b ∈ BC ∼ , ∀h ∈ 1..k
The two constraints model the equality from constraint [START_REF] Roy | Multicriteria Methodology for Decision Aiding[END_REF], however, we also have added a single binary variable s * for each pair of alternatives in In in order to relax these constraints when the constructed S-RMP model is not able to represent it. In order to finish the MIP, we only need to add an objective function as: maximize a,b∈BC s(a, b, p σ(0) ) + a,b∈BC s * (a, b). The resulting program will therefore seek to maximize the number of fulfilled pair-wise comparisons.

Parameters:

A * , BC , BC∼, M, k, σ, γ (1) aj ∈ [0, 1] ∀a ∈ A, ∀j ∈ M (2) Variables: wj ∈ [0, 1] ∀j ∈ M (3)
p h j ∀h ∈ 1..k, ∀j ∈ M (4) δj(a, p h ) ∈ {0, 1} ∀a ∈ A * , ∀h ∈ 1..k, ∀j ∈ M (5) ωj(a, p h ) ∈ [0, 1] ∀a ∈ A * , ∀h ∈ 1..k, ∀j ∈ M (6) s(a, b, p h ) ∈ {0, 1} ∀a, b ∈ BC , ∀h ∈ 0..k (7)
Constraints:

s.t. j∈M wj = 1 (8) wj γ ∀j ∈ M (9) p 1 j 0 ∀j ∈ M (10) 1 p k j ∀j ∈ M (11)
p h+1 j p h j ∀h ∈ 1..k -1, ∀j ∈ M (12) aj -p h j δj(a, p h ) -1 ∀a ∈ A * , ∀h ∈ 1..k, ∀j ∈ M (13) δj(a, p h ) aj -p h j + γ ∀a ∈ A * , ∀h ∈ 1..k, ∀j ∈ M (14) wj ωj(a, p h ) ∀a ∈ A * , ∀h ∈ 1..k, ∀j ∈ M (15) ωj(a, p h ) 0 ∀a ∈ A * , ∀h ∈ 1..k, ∀j ∈ M (16) δj(a, p h ) ωj(a, p h ) ∀a ∈ A * , ∀h ∈ 1..k, ∀j ∈ M (17) ωj(a, p h ) δj(a, p h ) + wj -1 ∀a ∈ A * , ∀h ∈ 1..k, ∀j ∈ M (18)
s(a, b, p 0

) = 1 ∀a, b ∈ BC (19)
s(a, b, p k

) = 0 ∀a, b ∈ BC (20)
j∈M ωj(a, p σ(h)

) j∈M ωj(b, p σ(h) ) + γ -s(a, b, p σ(h) ) • (1 + γ) -(1 -s(a, b, p σ(h-1) )) ∀a, b ∈ BC , ∀h ∈ 1..k (21)
j∈M ωj(a, p σ(h)

) j∈M ωj(b, p σ(h) ) -(1 -s(a, b, p σ(h) )) -(1 -s(a, b, p σ(h-1) )) ∀a, b ∈ BC , ∀h ∈ 1..k (22) j∈M ωj(b, p σ(h) ) + (1 -s(a, b, p σ(h) )) + (1 -s(a, b, p σ(h-1)
))

j∈M ωj(a, p σ(h) ) ∀a, b ∈ BC , ∀h ∈ 1..k (23)
j∈M ωj(a, p σ(h)

) = j∈M ωj(b, p σ(h) ) ∀a, b ∈ BC∼, ∀h ∈ 1..k (24)
Table 3: Mixed integer linear program for inferring the parameters of an S-RMP model given a lexicographic order σ;

Numerical Analysis

We propose in this section to study the performances of the proposed elicitation algorithm for the S-RMP model. We begin by describing our experimental protocol. Then, we provide the results concerning (i) the computation time, (ii) the ability of the proposed approach to restore the provided binary comparisons, and (iii) its ability to handle noisy data.

Experiment Design and implementation details

To test our algorithm we follow the experimental design depicted in Figure 2. We randomly draw an initial S-RMP model, denoted with M o :

• the criteria weights are first randomly generated using the method described in [START_REF] Butler | Simulation techniques for the sensitivity analysis of multi-criteria decision models[END_REF][START_REF] Zheng | Learning criteria weights of an optimistic Electre Tri sorting rule[END_REF],

• the reference profiles are drawn as follows: on each criterion j ∈ M , randomly we generate k o evaluations in X j and order them. These ordered evaluations on all criteria are used to specify the k o profiles, so as to respect the dominance structure on profiles.

• we randomly select a lexicographic order on profiles. We randomly generate a training set (denoted A tr ) of n tr alternatives defined by their evaluations on the m criteria. We then construct a set of n bc pairwise comparisons, by randomly selecting pairs of alternatives from A tr (we discard pairs of alternatives involving dominance); we use M o define preference on the selected pairs.

Then we compute M e , the S-RMP model that best match the n bc pairwise comparisons, with a fixed number of profiles k e using the algorithm proposed in Section 4. To appreciate the distance between M e and M o , we randomly generate A te , a test set of te alternatives (A te is constructed in the same way as A tr ). A te is used with both the original model and the elicited one in order to construct two rankings of the alternatives. Kendall's rank correlation is then used in order to measure the closeness between the elicited model M e and the original one M o .

We have set the following values for the experiments' parameters (from Figure 2): n tr ∈ {10, 20, . . . 100}, m ∈ {3, 5, 7}, k o = 10, k e ∈ {1, 2, 3} and n te = 5000. We have generated 100 S-RMP models (M o ) for each combination of values for these parameters. The experiments we have been performed using the solver IBM ILOG CPLEX 12.6.3 on an AMD Opteron TM 6176 SE machine with 250GB RAM and the possibility of launching up to 18 threads in parallel. We have set a 60mn timeout for each computation.

Moreover, when inferring an S-RMP model, in order to remove any bias caused by the sequence in which the lexicographic orders of profiles were chosen, we have adapted the approach so that multiple parallel executions are launched, one for each lexicographic order. Therefore, when k = 1 we launch a single instance of the approach, allowing CPLEX to reach a parallelism of 18, when k = 2 we launch two instances with a parallelism of 9 each, and when k = 3 we launch six instances with a parallelism of 3 each. In this way, all executions of this algorithm, regardless of the sought number of profiles, will have access to the same amount of resources and the final result will not be biased by the order in which the lexicographic orders have been chosen.

Experiments results

Computing time

Our first experiment aims to analyze the computation time of the proposed algorithm. Figure 3 depicts the average execution times and standard deviations for the problem instances that were solved within a one hour time limit. We observe that the execution time increases with the number of considered binary comparisons at an exponential rate. The computation time also increases significantly with the number of profiles.

Note that the exponential trend of the computing time seems "weaken" for more than 70 comparisons. This may be due to the one hour limit imposed for computing M e ; indeed, this timeout occurs more often for large instances. Finally, the differences in execution time when computing S-RMP models with one, two or three profiles (k e = 1, 2, or 3) seem to reduce when more criteria are considered (m = 7).

We can conclude that, for data sets whose size corresponds to real instances (up to 100 comparisons,

Inferring from noise free data

This section concerns the ability of elicited S-RMP models to restore a set of noise free binary comparisons. We study the proportion of comparisons restored when the number of comparisons, number of criteria and number of profiles vary. • Ability of the inferred model to restore the training set. Figure 4 depicts the mean value and standard deviation for the input data restoration rate, i.e, the proportion of the input pairwise comparisons that are correctly restored by the inferred model M e (as compared to the ground truth M o ).

Note that, in our experiment, the binary comparisons are generated an S-RMP model M o using k o = 10 profiles whereas the inferred models M e use a number of profiles k e varying from 1 to 3. Therefore, there is no guaranty that the inferred models fully restore the set of pairwise comparisons.

With 7 criteria (m = 7), and for small numbers of binary comparisons (n bc ≤ 40), it is possible to restore all comparisons generated from M o even with S-RPM models with a S-RMP model with a single profile (k e = 1). Decreasing the number of criteria leads to a less flexible model M e , therefore leads to a reduced restoration rate. Similarly, increasing the number of profiles (k e = 2 or even 3) improves the flexibility of M e , and consequently improves the restoration rate.

For five criteria or more, it is enough to use two profiles to represent preferences generated from more complex S-RMP model (with k o = 10 profiles) up to 100 comparisons. Note that with three profiles, it is always possible to restore the whole 100 binary comparisons5 .

• Ability of the inferred model M e to restore the original one M o . In this situation, we test the ability of the elicitation algorithm to compute a model M e which is as close as possible to the original one M o . More precisely, we compute the Kendall tau rank correlation between the rankings of the test set A te obtained using M e and M o ; the higher the rank correlation, the closer M e is to M o . With 2 or 3 profiles, we do not observe the asymptote, but we can expect it for a higher number of comparisons. Similarly, as the number of criteria increases, the model gains flexibility, and we observe that more comparisons are required to faithfully elicit the model.

There are configurations (e.g. m = 7) in which one would need more comparisons to reach an asymptote and accurately assess the model. This would be computationally costly. However, one should keep in mind that the comparisons are chosen randomly, without any consideration concerning the amount of information provided. To overcome such difficulty, it would be wise to follow an "active learning" approach in which comparisons are carefully selected to provide effective information.

Results on the ability of the inferred model to restore the original one with noisy data

In the previous experiments, input data was assumed to be noise free. In what follows, we study the effects of introducing a percentage of errors within the input comparisons. By errors, we mean that, after generating a set of binary comparisons with the original model (M 0 ), we reverse the preference between a proportion of pairs of alternatives. More precisely, we study the situations in which we introduce 5%, 10%, and 15% of "errors" in the set of pairwise comparisons used to infer the model M e .

Figure 6 depicts the mean value and the standard deviation of the Kendall tau between M e and M o ranks for m = 5, k e = 1, and m = 5, k e = 2, with a proportion of 5%, 10%, and 15% of "errors". The situation with 0% errors corresponds to the case presented in Figure 5 for m = 5.

We observe that, despite the introduction of errors in the input comparisons (event for 15% errors), the algorithms takes advantage of additional comparisons, and the elicited model M e gets closer to the original one M o (the Kendall tau increases). This denotes a positive behavior of the algorithm, even with noisy data.

Obviously, a greater proportion of errors requires a larger number of comparisons to faithfully elicit the model. For instance, we can observe in Figure 6 that, for m = 5 and k e = 1, an average number of 60 noise free comparisons leads to a Kendall tau equal to ∼0.8; with 5% errors (with 15%, respectively), 80 comparisons (100 comparisons, respectively) are necessary to obtain a similar result. With noisy data, the computing time increases as compared to noiseless situations. This is illustrated in Table 4 by the percentage of instances that were not solved within a one hour execution time. For k e = 1 (except for n bc = 100), all instances were solved in less than 60mn; however, for k e = 2, starting from n bc = 60, more than half of the considered experiments did not provide a solution when errors were included in the binary comparisons.

Figure 1 :

 1 Figure 1: Graphical interpretation of Table 1

  p h . 3. rank two alternatives a, b ∈ A by sequentially considering the relations p σ(1) , p σ(2) , . . . , p σ(k) (according to the lexicographic order σ); a is prefered to b if a p σ(1) b, or if a ∼ p σ(1) b and a p σ(2) b, or . . . Hence, a and b are indifferent iff a ∼ p σ(h) b, for all h = 1, . . . , k.

Figure 2 :

 2 Figure 2: Design of experiments;

Figure 3 :

 3 Figure 3: Average execution times on a logarithmic scale.

Figure 4 :

 4 Figure 4: Proportion of restored binary comparisons on the training data.

Figure 5

 5 Figure5depicts the mean value and the standard deviation of the Kendall tau between M e and M o ranks for m = 3, 5 and 7, and k e = 1, 2 and 3. The experimental results show an expected trend in which increasing the number of input comparisons results in an improvement in the Kendall Tau. The increasing curves of the Kendall Tau values as the number of comparisons increases seem to reach an asymptote: for example, beyond 50 comparisons, in the the case k e = 1, m = 3, the Kendall Tau reaches a "plateau" (∼ 0.75), and in the the case k e = 1, m = 5, the Kendall Tau reaches a "plateau" beyond 80 comparisons (∼ 0.85).

Figure 5 :

 5 Figure 5: Kendal Tau between the M 0 and Me rankings on the test set.

Figure 6 :

 6 Figure 6: Kendal Tau between M 0 and Me rankings on the test set in presence of errors.

Table 1 :

 1 Data involved in the illustrative example.

		Price Confidence in the Consumption Acceleration
		(ke)	brand ([0,100])	(lit./100km)	(sec.)
	x	18	95	9	24
	y	16	66	6	32
	z	13	25	6	22
	p 1	20	50	10	30
	p 2	12	75	7	25
	weight 0.25	0.25	0.25	0.25

Table

Table 2 :

 2 Results of the encoding procedure for the illustrative example

S-RMP defines the ranking based on the comparisons of alternatives to profiles

In this example, as criteria are equally weighted, we just count the number of criteria, but they could be weighted differently.

for any S-RMP model, there exist an equivalent S-RMP model with a dominance structure on profiles, see[START_REF] Rolland | Reference-based preferences aggregation procedures in multi-criteria decision making[END_REF].

Note that in this reference based ranking model, the number of reference points is usually limited to 3.

criteria), the computation time is compatible with a working session mode (see for instance[START_REF] Ferretti | Reference-based ranking procedure for environmental decision making: Insights from an ex-post analysis[END_REF]) in which preference statements are collected from the decision maker, and results are shown after at most 20-30mn computation. It is however difficult to envisage an interactive trial and error mode with datasets of real world size.

The experiments were made with m = 3, 5 and 7 but they are not displayed on the plots for sake of clarity

Conclusion and perspectives

In this paper, we propose an indirect approach for the elicitation of the parameters of an S-RMP model. This approach aims to offer an operational tool to support the use of S-RMP in real world applications (see e.g. [START_REF] Ferretti | Reference-based ranking procedure for environmental decision making: Insights from an ex-post analysis[END_REF]). Moreover, the proposed method has been implemented in R as part of the library of MCDA methods proposed by [START_REF] Bigaret | Olteanu Supporting the multi-criteria decision aiding process: R and the MCDA package[END_REF], and is therefore available for use.

For an effective use in real-world applications, computing time can still be an issue for instances of large size, or for situation in which the preference data collected from the decision maker is highly noisy. For such situations, the metaheuristic developed in [START_REF] Liu | Preference Elicitation for Multi-Criteria Ranking with Multiple Reference Points[END_REF] could be suitable as it makes it possible to infer in a reasonable computing time an S-RMP model; such approach does not however guaranty optimality.

An interesting research direction is to develop more efficient inference tools. For instance, a promising path is to express the inference problem as a Boolean Satisfiability Problem (SAT) in order to find a model fully consistent with the learning set (whenever it exists). Such approach has already been proposed for reference point based multicriteria sorting models, and has proved to be computationally more efficient than optimization approaches [START_REF] Kh | An Efficient SAT Formulation for Learning Multicriteria Non-Compensatory Sorting Models[END_REF][START_REF] Kh | An Efficient SAT Formulation for Learning Multicriteria Non-Compensatory Sorting Models[END_REF].

Ethical Statement

The authors of this paper conform to the Springer Publishing Ethics Statement.