Nawal Benabbou

Christophe Gonzales

Patrice Perny

Paolo Viappiani

Minimax Regret Approaches for Preference Elicitation with Rank-Dependent Aggregators

published or not. The documents may come

Introduction

Human decision support and automated decision processes often rely on a mathematical decision model allowing the comparison of the possible alternatives and the selection of a proper solution. This is typically the case in Multicriteria Decision Making where an aggregation function is often used to synthesize different viewpoints into aggregated values representing the overall utilities of the alternatives for the Decision Maker (DM). The aggregation function must be sufficiently expressive to fit DM's preferences in human decision support, but also to model and simulate a prescribed decision behavior in automated decision systems. This explains the diversity of decision models available in the literature but also the increasing interest for sophisticated parameterized models such as the Choquet integral model [START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid[END_REF] that can encompass, in the same general formula, various preference value systems, depending on the choice of its preference parameters. The Choquet integral model is indeed very flexible as it subsumes many different aggregation models, including linear models, leximin and lexicographic aggregators, the Ordered Weighted Average operator and its weighted extensions such as the Weighted Ordered Weighted Average aggregator.

A key question is, however, how to assess the preference parameters of such aggregation functions in order to model DM's preferences. For the Choquet integral model, in particular, one needs to assess a capacity, a function defined on the power set of the criteria, so as to control the importance attached to all subsets of criteria, and possibly positive or negative synergies between criteria; thus the number of preference parameters is exponential in the number of criteria. Even if further assumptions are made (e.g. k-additive capacity) to reduce the number of parameters in the model, parameter learning is still challenging; in general, only limited information about the DM's preferences will be available (e.g. in the form of partial ranking of alternatives or qualitative statements on the quality of concrete alternatives). Preference handling and elicitation with limited available information is acknowledged to be a crucial task in many application domains, including recommender systems, interface customization and personal assistants [START_REF] Peintner | Preferences in interactive systems: Technical challenges and case studies[END_REF].

Most of previous works on the elicitation of Choquet integral parameters consider a "static" preference database as input, and focus on the determination of a set of preference parameters that best fits the available preferences. For example, one can minimize a quadratic error between Choquet values and target utility values prescribed by the DM. Alternatively, one can impose some constraints on Choquet values to enforce the decision model to be compatible with a partial or total order available on a subset of alternatives. These approaches are illustrated in many papers see, e.g. [START_REF] Grabisch | Fundamentals of Uncertainty Calculi, with Applications[END_REF][START_REF] Grabisch | A review of methods for capacity identification in Choquet integral based multi-attribute utility theory[END_REF][START_REF] Marichal | Determination of weights of interacting criteria from a reference set[END_REF][START_REF] Meyer | On the use of the Choquet integral with fuzzy numbers in multiple criteria decision support[END_REF][START_REF] Angilella | Non-additive robust ordinal regression: A multiple criteria decision model based on the Choquet integral[END_REF] and [START_REF] Grabisch | Aggregation Functions. Encyclopedia of Mathematics and its Applications[END_REF] (Chapter 11), and implemented in decision support softwares such as TOMASO [START_REF] Marichal | Sorting multi-attribute alternatives: the TOMASO method[END_REF], MYRIAD [START_REF] Fabien | Integration and propagation of a multi-criteria decision making model in constraint programming[END_REF] and KAPPALAB [START_REF] Grabisch | A review of methods for capacity identification in Choquet integral based multi-attribute utility theory[END_REF].

Departing from these standard approaches, we are advocating in this paper an incremental elicitation process in which preference queries are selected one by one, to be as informative as possible, so as to progressively reduce the set of possible parameters of a rank-dependent aggregation function until a robust recommendation can be made. This approach relies on previous works on the incremental elicitation of linear aggregation functions (see e.g. ISMAUT method [START_REF] White | A model of multiattribute decisionmaking and trade-off weight determination under uncertainty[END_REF]) and exploits recent advances in Artificial Intelligence techniques such as adaptive utility elicitation [START_REF] Braziunas | Elicitation of factored utilities[END_REF] based on a principled decision-theoretic approach. The system maintains an explicit representation of the possible aggregation functions (sometimes called "belief") that are consistent with the DM's behavior, and that is updated whenever new information about the DM is available. Such representation can be useful in order to identify informative queries that can be asked to the DM with the goal of reducing uncertainty as much as possible with a limited number of queries (limiting the DM's effort). The second central aspect is the robustness in face of utility uncertainty, that means the capability of offering guarantees on the quality of the recommended alternative, given the current available information.

A solution to this is represented by the approach of Boutilier et. al. [START_REF] Boutilier | Constraint-based Optimization and Utility Elicitation using the Minimax Decision Criterion[END_REF] based on the minimax regret criterion allowing robust recommendations under utility uncertainty with guarantees with respect to the worst case loss. Furthermore, minimax regret computation can also be used to generate effective queries asking to choose the preferred alternative in a subset of alternatives (for a set of two elements, they are called comparison queries) [START_REF] Viappiani | Regret-based optimal recommendation sets in conversational recommender systems[END_REF]; regret-based elicitation has been successfully demonstrated with real users (DMs) in a prototype for decision support (UT-pref) and validated in a user study [START_REF] Braziunas | Assessing regret-based preference elicitation with the UT-PREF recommendation system[END_REF].

However, adapting minimax regret optimization to non-linear utility models is not trivial. The large parameter space associated to Choquet integrals, as well as the necessity of handling the induced constraints (set monotonicity of the underlying capacity measure), means that particular care has to be given to the optimization. Furthermore, the decision space might be very large, this is often the case in recommender spaces where the possible alternatives can be thousands. We therefore need methodologies that can optimize the proposed criterion in an effective way. We will focus on the case where the possible decisions are given explicitly (as in a database of products) given. This paper aims at proposing some algorithmic methods for assessing rank-dependent aggregation functions by a progressive collect of preference statements using the minimax regret criterion.

The paper is organized as follows: in Section 2, we recall some useful notions related to rank-dependent aggregation functions. In Section 3, we recall the principle of incremental elicitation methods in which queries are selected using the minimax regret criterion and we explain how this approach can be carried out in the case of rank-dependent aggregation functions. Section 4 discusses some methodological points so as to compute efficiently minimax regret values during the elicitation process, and provides numerical tests. Section 5 provides and discusses experimental results concerning incremental elicitation sessions for the aggregation functions considered in the paper.

Rank-dependent Aggregation Functions

Let X be the set of alternatives (items, products, candidates...) that must be evaluated to make a decision. We consider here a multicriteria evaluation problem and denote N = {1, . . . , n} the set of criteria. Every alternative x ∈ X is characterized by a performance vector (x 1 , . . . , x n ) where x i ∈ [0, 1] represents the utility of alternative x with respect to criterion i, with i ∈ N . For simplicity, x will indifferently denote the alternative or its performance vector. In this framework, rank-dependent aggregation functions are scalarizing functions that sort criterion utility values by increasing order before mapping the performance vector into a scalar value (or overall utility value). This allows to assign weights to ranks rather than to components in the aggregation process, so as to control the importance attached to the bottom performance, to the top performance or to any other order statistics. In order to specify such rank-dependent aggregation functions, we will often make use of the permutation (.) defined on N and such that x (1) ≤ ... ≤ x (n) (sorting the components of x from the smallest to the largest).

Ordered Weighted Average

Ordered Weighted Averages (OWA) [START_REF] Yager | On Ordered Weighted Averaging aggregation operators in multicriteria decision making[END_REF] is one of the simplest families of rank-dependent aggregation functions used in multicriteria aggregation. It is defined as a weighted sum of the components of x, once reordered from the worst to the best. OWA is specified by a vector of weights w = (w 1 , . . . , w n ) ∈ [0, 1] n such that i∈N w i = 1, where w k is the weight associated to the component of x ranked in the k-th position (i.e. x (k) ). More formally, for any alternative x ∈ X , the OWA value is defined as follows:

Definition 1. OWA(x; w) = n i=1 w i x (i)
In other words, OWA is the scalar product between the vector of weights w and the sorted vector (x (1) , . . . , x (n) ). Note that OWA are symmetric functions as the weights do not address the components of x, but those of the sorted vector. This family of rank-dependent aggregators includes the minimum, maximum, median and all order statistics as a special case (just use a vector of weights whose all components except one are null). OWA is often used with decreasing weights in Social Choice theory as a measure of inequalities incorporated in Social Evaluation functions [START_REF] Weymark | Generalized Gini inequality indices[END_REF] due to the following property:

Proposition 1. ∀x ∈ R n , ∀i, k ∈ N, i < k s.t x k < x i , ∀ε ∈ (0, x i -x k ), [∀i ∈ {1, . . . , n -1}, w i > w i+1 ] ⇒ OWA(x; w) < OWA(x ε ; w) where x ε = (x 1 , . . . , x i -ε, . . . , x k + ε, . . . , x n ).
Thus, if weights w i are strictly decreasing as i increases, any move from an alternative to another, resulting in a utility transfer of size ε that reduces inequality between satisfaction of criteria i and k, will increase the OWA value. Such transfers are known as Pigou-Dalton transfers in Economics where they are used to express the idea of fairness, see e.g. [START_REF] Shorrocks | Ranking income distributions[END_REF][START_REF] Weymark | Generalized Gini inequality indices[END_REF]. Besides this fairness property, OWA operators are monotonically increasing with respect to every component. The conjunction of these two properties shows that solutions maximizing an OWA function are those Pareto-optimal solutions that cannot be improved in terms of Pigou-Dalton transfer. Hence OWA maximization using strictly decreasing weights helps promoting balanced solutions while ensuring overall efficiency. The tradeoff between efficiency and fairness is controlled by the weights. Playing with these decreasing weights leaves room for various attitudes. Another way to see the treatment of inequalities by OWA is to remark that choosing decreasing weights gives more importance to the least satisfied criterion, then a less emphasis is given to the second least satisfied criterion and so on. To give an example, if one wishes to compare vectors x = (0.25, 0.5, 0.75) and y = (0.5, 0.6, 0.4) with OWA using the vector of weights w = (0.5, 0.33, 0.17), one gets OWA(x; w) = 0.42 < 0.47 = OWA(y; w), and so y is preferred to x. OWA aggregators often appear in fair allocation problems, see e.g. [START_REF] Ogryczak | Inequality measures and equitable approaches to location problems[END_REF][START_REF] Lesca | LP Solvable Models for Multiagent Fair Allocation problems[END_REF] but, beside the fact that we should use decreasing weights, very few information is given on the determination of these weights to model a specific attitude of the DM towards fairness.

Hybrid Weighted Average

As we noted in the previous subsection, a feature of OWA is to be a family of symmetric aggregation functions. This property seems natural when the criteria are individual points of views in a collective decision problem but it may not be desired in Multicriteria Decision Making, especially when certain criteria are considered more important than others. It is then interesting to consider weighted extensions of OWA, the initial weights of OWA only serving to control the importance that we give to good and bad performances. A solution for that is resorting to two vectors of weights, one for the OWA weights, the other to weight criteria. A first solution in this direction is given by the weighted OWA also known as Weighted Ordered Weighted Average [START_REF] Vincenc ¸torra | The weighted OWA operator[END_REF]. However, although this solution extends the descriptive possibilities of OWA, it does not allow a sufficient flexibility and control for exploring easily the Pareto set. The impact of criterion weights is quite complex and may be sometimes counter-intuitive [START_REF] Ogryczak | On WOWA Rank Reversal[END_REF]. Hence we consider here another weighted variant of OWA named the Hybrid Weighted Average (HWA) [START_REF] Llamazares | On generalizations of weighted means and OWA operators[END_REF].

HWA is an operator that makes use of two different sets of weights. The first vector of weights, denoted p = (p 1 , . . . , p n ) ∈ [0, 1] n , is a normalized vector impacting on the importance attached to criteria. The second, denoted w = (w 1 , . . . , w n ), is a vector of rank-dependent weights like in the OWA operator. However, unlike in the original OWA, the ranked components are obtained by multiplication with the weights of p. More precisely, for any alternative x ∈ X , the HWA value is given by: Definition 2.

HWA(x; p, w) = OWA(η

• p • x; w)
where • denotes element-by-element multiplication (a.k.a. Hadamard product) and η = (n, . . . , n).

Operators HWA and OWA are exactly equivalent when p = (1/n, . . . , 1/n), while HWA is equivalent to the weighted sum when w = (1/n, . . . , 1/n). The insertion of weighting vector p enables to scale up or down components, depending on their importance, before performing the aggregation with OWA. For instance, let us come back to the example provided at the end of section 2.1 to compare x = (0.25, 0.5, 0.75) and y = (0.5, 0.6, 0.4) with OWA using the vector of weights w = (0.5, 0.33, 0.17). If p = (0.6, 0.3, 0.1), we get η •p•x = (0.45, 0.45, 0.225) and η •p•y = (0.9, 0.54, 0.12). Then, we obtain HWA(x; p, w) = OWA((0.45, 0.45, 0.225); w) = 0.3375 < 0.3912 = OWA((0.9, 0.54, 0.12); w) = HWA(y; p, w) and so y is better than x. This is mainly due to the importance attached to the first component. Conversely, if we use another weighting vector p = (0.1, 0.3, 0.6), putting more importance on the third component, we obtain the reversed preference: HWA(x; p, w) = OWA((0.075, 0.45, 1.35); w) = 0.4155 > 0.3756 = OWA((0.15, 0.54, 0.72); w) = HWA(y; p, w). The above example shows that the use of weighting vector p in HWA provides some additional flexibility compared to OWA so as to control the optimal profile.

Choquet Integral

We consider now a more general family of aggregators known as Choquet integrals [START_REF] Schmeidler | Integral representation without additivity[END_REF][START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid[END_REF] which is appealing because it offers a wider flexibility due to a greater number of preference parameters. These parameters are weights attached to every subset of criteria. They allow a fine control of interactions between criteria and take the form of a capacity function on the power set 2 N .

Definition 3. v : 2 N → R is a normalized capacity if v(∅) = 0, v(N ) = 1 and v(A) ≤ v(B) whenever A ⊂ B (monotonicity).
A capacity v is said to be convex or supermodular when

v(A ∪ B) + v(A ∩ B) ≥ v(A) + v(B) for all A, B ⊆ N , additive when v(A ∪ B) + v(A ∩ B) = v(A) + v(B) for all A, B ⊆ N , and concave or submodular when v(A ∪ B) + v(A ∩ B) ≤ v(A) + v(B) for all A, B ⊆ N .
We now use the notion of capacity to define the Choquet integral model. Recall that (.) denotes the permutation of N that sorts the components of x in increasing order. Let X (i) denote the subset of criteria with respect to which x has a utility greater or equal to x (i) (i.e. X (i) = {(i), . . . , (n)}). Note that X (i+1) ⊂ X (i) for all i ∈ {1, . . . , n-1}. In the following, the nested sequence of sets X (i) , i = 1, . . . , n, are said to be the level sets of x. Similarly, Y (i) will denote the i-th level set of an alternative y. Using these notations, for any alternative x ∈ X , the Choquet integral value is defined as follows:

Definition 4. C v (x) = n i=1 x (i) -x (i-1) v(X (i) ) with x (0) = 0.
In the definition of the Choquet integral model, the use of a capacity v instead of an arbitrary set-function enforces compatibility with Pareto-dominance (x Pareto-dominates y if x i ≥ y i for all i ∈ N and x j > y j for some j ∈ N ) due to the monotonicity of v with respect to set inclusion. In other words, it ensures that C v (x) ≥ C v (y) whenever x Pareto-dominates y. Function C v is known to be convex whenever v is concave (submodular). Conversely, C v is concave whenever v is convex (supermodular) [START_REF] Lovász | Submodular functions and convexity[END_REF]. The concavity of C v and therefore the use of a convex capacity has an interpretation in terms of preferences. More precisely, it is shown (see [START_REF] Chateauneuf | Diversification, convex preferences and non-empty core in the Choquet expected utility model[END_REF]) that if v is convex, then ∀x 1 , x 2 , . . . x m ∈ R n and ∀λ = (λ 1 , . . . , λ m ) ∈ [0, 1] m such that m i=1 λ i = 1:

C v (x 1 ) = C v (x 2 ) = . . . = C v (x m ) ⇒ ∀k ∈ {1, 2, . . . , m}, C v ( m i=1 λ i x i ) ≥ C v (x k ) .
For example, when using a convex capacity, if one is indifferent between performance vectors (0, 1) and (1, 0), one will prefer solution (0.5, 0.5), which corresponds to the average of the two vectors (λ 1 = 0.5, λ 2 = 0.5), to any of the two initial vectors. Hence using a convex capacity is a way of promoting equity within the Choquet integral model. Obviously, we would obtain reverse preferences with a concave capacity since the associated Choquet integral is convex. Capacity v may both be concave and convex (i.e. it is additive) and in this case, the Choquet integral boils down to a weighted sum. Alternatively, v could be neither convex nor concave to model more complex preferences (for more details see [START_REF] Grabisch | Aggregation Functions. Encyclopedia of Mathematics and its Applications[END_REF]). Note also that if v is defined by v(A) = ϕ( i∈A p i ) for some positive weights p i and a non-decreasing function ϕ such that ϕ(0) = 0 and ϕ(1) = 1, then the Choquet integral is a WOWA operator (see [START_REF] Vincenc ¸torra | The weighted OWA operator[END_REF]). Whenever all p i are equal, we obtain an OWA operator as introduced before, and more generally, any Choquet integral used with a symmetric capacity (i.e. v(A) = f (|A|) for all A ⊆ N ) is an OWA and vice-versa.

Another useful formulation of the Choquet integral exists, using Möbius masses attached to the capacity [START_REF] Chateauneuf | Some characterizations of lower probabilities and other monotone capacities through the use of Möbius inversion[END_REF]. Any set-function v admits indeed an alternative representation in terms of the Möbius inverse:

Definition 5. To any set-function v : 2 N → R is associated m : 2 N → R a mapping called Möbius inverse, defined by:

∀A ⊆ N, m(A) = B⊆A (-1) |A\B| v(B).
The capacity v can be reconstructed from its Möbius inverse as follows:

∀A ⊆ N, v(A) = B⊆A m(B).
Coefficients m(B) for B ⊆ A are called Möbius masses. Interestingly, a set-function whose Möbius masses are non-negative (also known as belief function) is necessarily convex [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. Using the Möbius inverse, we can define the notion of k-additive capacities as follows [START_REF] Grabisch | Aggregation Functions. Encyclopedia of Mathematics and its Applications[END_REF]: Definition 6. A capacity is said to be k-additive when its Möbius inverse vanishes for any A ⊆ N such that |A| > k, and there exists at least one subset A of exactly k elements such that m(A) = 0. More formally:

∀A ⊆ N, |A| > k ⇒ m(A) = 0 ∃A ⊆ N, |A| = k and m(A) = 0.
If k = 1 we get an additive capacity. For small values of k greater than 1, k-additive capacities are very useful because in practical situations, they offer a sufficient expressivity to model positive or negative interactions among criteria with a reduced number of parameters. For example, when k = 2 the capacity is completely characterized by (n 2 + n)/2 coefficients (one Möbius mass for every singleton and every pair). For any alternative x ∈ X , the Choquet integral value can be rewritten in function of Möbius masses as follows:

C v (x) = B⊆N m(B) min i∈B x i = m • x (1)
where m is the vector of all Möbius masses m(B), B ⊆ N , and x is the vector whose components are all xB = min i∈B x i , B ⊆ N . This makes explicit another interpretation of C v : it is a linear aggregator in a feature space including 2 n components. This weighted linear combination is much more compact when v is k-additive because terms corresponding to null Möbius masses vanish. For 1-additive capacities, it boils down to a simple weighted sum in the initial space.

Regret-based Elicitation of Rank-dependent Aggregators

In this section, we first review the idea of minimax regret for decision-making under utility uncertainty (traditionally used only in linear models) and then, we explain how it can be used within an incremental elicitation procedure to make robust recommendation for rank-dependent aggregators. In the following, we assume the DM needs to make a choice among the dataset of possible alternatives X .

Minimax Regret

Minimax regret [START_REF] Savage | The Foundations of Statistics[END_REF] is a decision criterion that has been advocated as a mean for robust optimization in the presence of data uncertainty [START_REF] Kouvelis | Robust Discrete Optimization and Its Applications[END_REF] and has been used for decision making with utility function uncertainty [START_REF] Boutilier | UCP-Networks: A directed graphical representation of conditional utilities[END_REF][START_REF] Salo | Preference ratios in multiattribute evaluation (PRIME)elicitation and decision procedures under incomplete information[END_REF][START_REF] Boutilier | Constraint-based Optimization and Utility Elicitation using the Minimax Decision Criterion[END_REF].

Consider a set of preference statements obtained from the DM. These statements could be of different kinds; a common form are answers to comparison queries or prior knowledge. Let P be the set gathering all pairs of alternatives (x, y) such that x is known to be preferred to y. Let F be the family of aggregation functions considered as potential candidates to approximate the DM's preferences. Let F P be the subset of F containing all aggregation functions f consistent with the set of observed preference statements P, i.e. such that f (x) ≥ f (y) for all (x, y) ∈ P. The problem is now to determine the most promising alternative under uncertainty over the DM's aggregation function represented by the set F P . To this end, the minimax regret approach is based on the following definitions.

Definition 7. The Pairwise Max Regret (PMR) of alternative x ∈ X with respect to y ∈ X is:

PMR(x, y; P) = max f ∈F P f (y)-f (x)
The pairwise max regret PMR(x, y; P) is the worst case regret that the recommender system (RS) imposes to the DM when recommending the alternative x instead of the alternative y. Note that the PMR concept bears some relations with the notion of possible and necessary preferences as introduced in robust ordinal regression [START_REF] Greco | Ordinal regression revisited: Multiple criteria ranking using a set of additive value functions[END_REF]. More precisely, when PMR(y, x; P) is strictly positive, then x is possibly strictly preferred to y (i.e. there exists f ∈ F P such that f (x) > f (y)); if PMR(y, x; P) = 0, then x is possibly equally preferred to y (i.e. there exists f ∈ F P such that f (x) = f (y)). If PMR(x, y; P) is strictly negative, then x is necessarily strictly preferred to y (i.e. for all f ∈ F P , f (x) > f (y)). When PMR(x, y; P) = 0, x is necessarily weakly preferred to y (i.e. for all f ∈ F P , f (x) ≥ f (y)). Finally, if PMR(x, y; P) = PMR(y, x; P) = 0 then x is necessarily equally preferred to y, (i.e. for all f ∈ F P , f (x) = f (y)).

Definition 8. The Max Regret (MR) of alternative x ∈ X is:

MR(x, X ; P) = max y∈X PMR(x, y; P) = max y∈X max f ∈F P f (y)-f (x)
The max regret MR(x, X ; P) is the worst case regret associated with recommending alternative x instead of any other alternative in X .

Remark that the use of rank-dependent aggregation functions like OWA, HWA and Choquet assumes that utilities x i are expressed on a common interval scale. This scale is unique up to any positive affine transformation (of type αx + β, α > 0). As a consequence, the order induced by max regret (MR) over alternatives is meaningful since pairwise max regret (PMR) values are independent of β and the order of regret values is independent on α as well.

Now, the MR-optimal value (called Minimax Regret) is defined as follows:

Definition 9. The Minimax Regret (MMR) over X is:

MMR(X ; P) = min x∈X MR(x, X ; P)
Recommending any MR-optimal alternative (i.e. any x ∈ X such that MR(x, X ; P) = MMR(X ; P)) allows the RS to guarantee that the worst case regret of not choosing the true optimal alternative for the DM is minimized. The minimax regret criterion is natural in this decision context where the RS has to select an alternative while the aggregation function of the DM is still imprecisely known. Given an alternative x chosen by the RS, using this decision criterion amounts to considering a fictitious DM (the "adversary") that will always choose the function f ∈ F P that maximizes the utility gap max y∈X f (y)f (x) over F P . In the sequel, MR-optimal solutions will be referred to as MMR-alternatives.

When F is the set of linear or piece-wise linear aggregators, F P is defined by a number of constraints approximately equal to the size of P and so PMR can be computed exactly quite efficiently by solving a simple linear program. This approach is more tractable than probabilistic models of utility that rely on computationally expensive Bayes updates [START_REF] Boutilier | A POMDP Formulation of Preference Elicitation Problems[END_REF][START_REF] Chajewska | Making Rational Decisions Using Adaptive Utility Elicitation[END_REF]. In our setting, we assume that alternatives are evaluated according to n different criteria, and the performance vectors are known and available to the system. When instead alternatives are constructed by solving a configuration problem, optimization over product space X can be formulated as a CSP or a mixed integer program (MIP) [START_REF] Boutilier | Constraint-based Optimization and Utility Elicitation using the Minimax Decision Criterion[END_REF][START_REF] Braziunas | Minimax Regret-based Elicitation of Generalized Additive Utilities[END_REF].

Remark that MMR cannot increase by adding preference constraints (i.e. by asking new preference queries to the DM) and it usually decreases (see [START_REF] Braziunas | Decision-theoretic elicitation of generalized additive utilities[END_REF], pages 194-202).

Observation 1. Given two sets of statements P, P s.t. P ⊆ P , the following inequalities hold:

• PMR(x, y; P ) ≤ PMR(x, y; P), ∀x, y ∈ X

• MR(x, X ; P ) ≤ MR(x, X ; P), ∀x ∈ X • MMR(X ; P ) ≤ MMR(X ; P)

We present now the general principle of incremental elicitation procedures based on this observation.

Incremental Elicitation

As proposed in [START_REF] Wang | Incremental Utility Elicitation with the Minimax Regret Decision Criterion[END_REF][START_REF] Boutilier | Constraint-based Optimization and Utility Elicitation using the Minimax Decision Criterion[END_REF][START_REF] Braziunas | Assessing regret-based preference elicitation with the UT-PREF recommendation system[END_REF], the minimax regret criterion can be used within an incremental elicitation process that progressively asks queries to the DM in order to assess preference parameters until the MMR (or worst case regret when recommending any MMR-alternative) drops below a given threshold; thanks to Observation 1, when the DM answers an additional query, we know that MMR cannot increase (and it will usually decrease), so asking new queries will make possible to make better recommendations by reducing the regret due to not choosing the true optimal alternative for the DM; therefore, regret-based elicitation supports a principled termination condition.

In order to better interpret regret values, MR can be normalized so as to belong to the [0,1] interval, 1 corresponding to the initial MR obtained before asking any query, and 0 being the ultimate goal when the uncertainty on parameters is sufficiently reduced to be able to identify the preferred alternative with certainty. With such normalized values, a minimax regret (MMR) value of 0.1, at a given step of the incremental elicitation process, simply means that the initial utility gap due to uncertainty has been reduced to 10% of its initial value. An interpretation of regret with practical use can be made in domains where utility can be expressed in equivalent monetary values. The monetary equivalent of MMR can be displayed to the DM, together with an explanation of the kind "if you buy the recommended product now, instead of continuing the elicitation process, the most you can loose is this dollar amount". This idea has been demonstrated in a prototype of a rental recommendation systems and validated with user experiments in [START_REF] Braziunas | Assessing regret-based preference elicitation with the UT-PREF recommendation system[END_REF].

Queries can be of different types. For instance, bound queries ask if the overall utility (aggregate value) of an alternative is higher or lower than a given reference value (they might be cognitively hard to answer).

Comparison queries are relatively easy to ask as they require the DM to compare a pair of alternatives and state which one is preferred among the two. Even assuming that the type of the query is fixed, there are of course several queries that one can ask at each step. Notice that some queries will be more informative than others. For instance, asking to compare an alternative with one that is Pareto-dominated by the former will provide no value (MMR will not change); instead asking to compare two potentially good alternatives will possibly constitute a good query. Choosing good queries is therefore essential in order to be able to provide good recommendations reasonably quickly (asking only few queries).

Assume that, at a given point in the interaction, P is the set gathering all pairs of alternatives (x, y) such that x is known to be preferred to y and F P is the set of aggregation functions consistent with P. Assuming a query q and all its possible responses R q , we can consider the space F P∪{r} in the scenario that the DM answers r, for any r ∈ R q . One can judge that a good query will significantly reduce MMR in each of the scenarios (recall that, for any r ∈ R q , MMR(X ; P ∪ {r}) can only be lower or equal to MMR(X ; P) from Observation 1). Thus, a (non probabilistic) notion of myopic value of information [START_REF] Viappiani | Regret-based optimal recommendation sets in conversational recommender systems[END_REF] when the aggregation function must lie in F P can be defined as follows:

Definition 10. The Worst Case Minimax Regret (WMMR) one step ahead of a query q is:

WMMR(q; P) = max r∈Rq MMR(X ; P ∪ {r}).
The optimal query according to this measure is then q * P = arg min q WMMR(q; P). Notice that a query can have significantly different WMMR values depending on F P (i.e. the currently known preferences P and the assumption about the family of aggregation functions that can model the DM's preferences F may have a strong impact on the value of the query). Thus, when considering comparison queries, in order to determine q * P , we have to compute for any two alternatives x and y the MMR value in the two spaces corresponding to possible answers (in one x has higher utility than y, in the other the reverse is true). One can equivalently look for the query maximizing the worst case regret reduction, i.e. min r∈Rq [MMR(X ; P)-MMR(X ; P ∪ {r})]. The optimization of comparison queries (and choice queries, that extend comparison queries to a set of elements) is thoroughly discussed in [START_REF] Viappiani | Regret-based optimal recommendation sets in conversational recommender systems[END_REF]. Since computing the myopically optimal query q * P is computationally intensive, we mainly focus here on a very efficient query strategy (though not optimal in general) called the Current Solution Strategy (CSS) [START_REF] Boutilier | Constraint-based Optimization and Utility Elicitation using the Minimax Decision Criterion[END_REF]. At a given step of the interaction, as next query, the CSS asks the DM to compare a MMRalternative x * P (arbitrarily chosen in arg min x∈X MR(x, X ; P)) to an alternative y * P arbitrarily chosen in arg max y∈X PMR(x * P , y; P). If the DM states that x * P is preferred to y * P , then (x * P , y * P ) is inserted in P. Otherwise, (y * P , x * P ) is inserted instead. In both cases, F P is updated accordingly. This elicitation scheme is very frequent in practice, see e.g. [START_REF] Boutilier | Constraint-based Optimization and Utility Elicitation using the Minimax Decision Criterion[END_REF][START_REF] Braziunas | Assessing regret-based preference elicitation with the UT-PREF recommendation system[END_REF][START_REF] Lu | Robust approximation and incremental elicitation in voting protocols[END_REF][START_REF] Drummond | Elicitation and approximately stable matching with partial preferences[END_REF][START_REF] Argyris | CUT: A multicriteria approach for concavifiable preferences[END_REF].

The CSS is often a good heuristic for the following reason: if x * P is preferred to y * P , when computing MMR(X ; P ∪ {(x * P , y * P )}) in the next cycle of the incremental elicitation procedure, y * P will not maximize PMR(x * P , y; P ∪ {(x * P , y * P )}) over X (unless the maximum is zero, but in that case, x * P is necessarily the preferred alternative for the DM). Therefore, if y * P was the unique alternative achieving MR(x * P , X ; P), we will necessarily have MR(x * P , X ; P ∪ {(x * P , y * P )}) < MR(x * P , X ; P). Hence, if x * P was the unique MMR-alternative given P, then we will have MMR(X ; P ∪{(x * P , y * P )}) < MMR(X ; P). Conversely, if y * P is stated to be preferred to x * P , now the latter is dominated by the former and so MR(y * P , X ; P ∪{(y * P , x * P )}) ≤ MR(x * P , X ; P ∪{(y * P , x * P )}). Moreover, if y * P was the unique alternative achieving MR(x * P , X ; P), then the expression above is necessarily strict: MR(y * P , X ; P ∪{(y * P , x * P )}) < MR(x * P , X ; P ∪ {(y * P , x * P )}). Therefore, in practice, the MMR will often decrease significantly. Proposition 2. Asking queries according to the CSS cannot lead to inconsistencies; F P cannot become empty during the incremental elicitation procedure.

Proof. Let P be a set of preference statements such that F P = ∅. We want to show that F P will not vanish after adding the preference statement (y * P , x * P ) or (x * P , y * P ) to P. We assume here that MMR(X ; P) > 0, otherwise x * P is necessarily one of the preferred alternatives and there is no need to ask further queries. Since MMR(X ; P) > 0, we can deduce that PMR(x * P , y * P ; P) > 0, and so we know that there exists an aggregation function in F P such that y * P is preferred to x * P (see Definition 7), i.e. F P∪{(y * P ,x * P )} = ∅. Assume now that there is no aggregation function in F P such that x * P is preferred to y * P . In that case, we have f (x * P ) < f (y * P ) for all f ∈ F P . Then, we can deduce that MR(y * P , X ; P) < MR(x * P , X ; P), i.e. x * P ∈ arg min x∈X MR(x, X ; P) which contradicts the fact that x * P is among MMR-alternatives. Thus, we can conclude that there exists an aggregation function in F P such that x * P is preferred to y * P , i.e. F P∪{(x * P ,y * P )} = ∅. Therefore, asking to compare x * P to y * P cannot lead to inconsistencies.

In the following subsections, we address how regret-based optimization can handle rank-dependent operators. We focus on PMR computation (as in this optimization lie the specific difficulties of treating rank-dependent operators) and we delay computation of the MMR to section 4.1 (as the latter is computed as a series of PMR and can be presented in a general way for all models). To do so, we will assume to be at a given point in the incremental elicitation procedure, and P is the current set gathering all pairs of alternatives (x, y) such that x is known to be preferred to y. We will also denote Θ P the set of parameters consistent with P (defining the space of aggregation functions F P ); for instance, whenever F is the set of Choquet integrals, then Θ P is the set of capacities consistent with P.

Application to OWA and HWA

To address how regret-based optimization can handle the OWA and HWA operators, we start by quickly reminding how PMR is computed in the (simpler) case of a linear utility model, where criteria are aggregated using a weighted sum.

Weighted Sum In the case of linear utility models, for a given vector of weights w, the utility (aggregate value) of x ∈ X is simply the scalar product w • x. Consequently, for any two alternatives x, y ∈ X , the pairwise max regret of x with respect to y with a linear utility model assumption is then:

PMR W S (x, y; P) = max w∈Θ P [y • w -x • w]
Note that we make now the assumption about the utility model (or family of aggregators) explicit and so Θ P is here the set of vectors of weights compatible with the known preferences P.

The computation of PMR W S (x, y; P) can be done efficiently with a linear program; constraints given by DM's preference statements (such as alternative x is preferred to alternative y) are encoded by linear constraints (w • x ≥ w • y) and do not pose particular problems.

We are now interested in the cases where the DM's aggregation function is represented by either OWA or HWA. The uncertainty is on the weights w (for OWA) or for both the weights w and p (for HWA).

In particular, the computation of PMR between option x and option y for the OWA and HWA operators consists in the following maximizations:

• PMR OWA (x, y; P) = max w∈Θ P OWA(y; w) -OWA(x; w) where Θ P is for OWA the set of weight vectors compatible with P,

• PMR HWA (x, y; P) = max (p,w)∈Θ P HWA(y; p, w) -HWA(x; p, w) where Θ P is for HWA the Cartesian product of the set of criterion weights and the set of rank-dependent weights compatible with P.

OWA PMR OWA can be easily optimized by using the standard methods by a simple manipulation of the dataset. Let x ↑ denote the vector whose components are those of the alternative x rearranged from the worst to the best (i.e. x ↑ = (x (1) , . . . , x (n) )) and let X ↑ be the set {x ↑ | x ∈ X }. Thus, we have the following equality: PMR OWA (x, y; P) = PMR W S (x ↑ , y ↑ ; P)

The preceding observation enables us to solve PMR OWA (x, y; P) by using linear programming by simply sorting the components of x and y:

max w w • y ↑ -w • x ↑ s.t. w i ≥ 0 ∀i ∈ N w i ≥ w i+1 ∀i ∈ {1, . . . , n -1} (2)
i∈N

w i = 1 w • a ↑ ≥ w • b ↑ ∀ (a, b) ∈ P
Note that constraints (2) are used to obtain strictly decreasing weights so as to favor well-balanced solutions. This equation can be dropped if we do not want to require decreasing weights.

HWA In the case of HWA, pairwise max regret computation consists in maximizing over (p, w) ∈ Θ P the value

n i=1 w i n[(p • y) (i) -(p • x) (i) ]
. This is not easily solvable using linear programming, neither it is easy to represent the constraints arising from the set of preference statements P.

Our solution for PMR HWA maximization relies on a hybrid technique involving sampling and linear programming. Notice that the difficulty relies on not knowing the order of the elements induced by the multiplication with the components of the p vector: if p was known, then the elements could be sorted and PMR HWA could have been computed with a linear program like for OWA (see Definition 2).

Given two performance vectors x and y, we aim at estimating PMR HWA (x, y; P). To do so, we sample (uniformly at random) a set of l normalized weighting vectors denoted p i , i ∈ {1, . . . , l}, representing possible values for p. For all i ∈ {1, . . . , l}, we construct the vectors η • p i • x and η • p i • y, where η = (n, . . . , n), and cast the problem as one of PMR OWA computation where the set Θ P of feasible rankdependent weights for OWA is constructed from P and p i . The estimated value of PMR HWA (x, y; P) is then the maximum obtained with each of these surrogate optimizations. More formally:

p i ∼ U [0, 1] n s.t. n j=1 p i j = 1, i ∈ {1, . . . , l} PMR HWA (x, y; P) ≈ max i∈{1,...,l} PMR OWA (η • p i • x, η • p i • y; P)
where η = (n, . . . , n).

Obviously, the quality of the approximation relies on the number of samples (and with a large enough number of samples, the estimated value will converge to the true value of PMR HWA (x, y; P)).

Application to Choquet integrals

For the Choquet integral model, the uncertainty is on the capacity v and so Θ P is the set of all capacities compatible with the known preferences P. Letting v B be the variable used for the capacity v(B) for any set B ⊆ N , for any two alternatives x and y in X , the computation of PMR Cv (x, y; P) (i.e.

max v∈Θ P C v (y) -C v (x)
) can be done as follows:

max v n i=1 y (i) -y (i-1) v Y (i) - n i=1 x (i) -x (i-1) v X (i) (3)
s.t. v ∅ = 0, v N = 1 v A ≤ v A∪{i} ∀i ∈ N, ∀A ⊆ N \{i} (4)
n i=1 a (i) -a (i-1) v A (i) ≥ n i=1 b (i) -b (i-1) v B (i) ∀(a, b) ∈ P (5)
where X (i) , Y (i) , A (i) and B (i) respectively denote the i-th level set of x, y, a and b (see Definition 4). Note that x and y being known, C v (x) and C v (y) are linear functions of capacities values v B , B ⊆ N , hence the objective function is linear. Constraints of type (4) are used to enforce monotonicity with respect to set inclusion. However, the number of such constraints is exponential in the number of criteria. Moreover the number of variables is also exponential in the number of criteria. This linear problem remains solvable easily for any two alternatives x and y as long as the number of criteria is kept reasonably small; then, MR Cv (x, X ; P) is derived from Definition 8. Note that another approach to compute MR Cv (x, X ; P) is proposed in [START_REF] Timonin | Robust optimization of the Choquet integral[END_REF]. It relies on the fact that MR Cv (x,

X ; P) = max v i ∈Θ * P G(v i ) where G(v) = max y∈X C v (y) -C v (x)
and Θ * P are the extreme points of Θ P . However, using this approach within an incremental elicitation procedure seems prohibitive for general capacities due to the large size of Θ * P . Another formulation of interest is the one obtained using the vector of Möbius masses m, whose components being decision variables instead of capacity values, taking advantage of the fact that C v (x) = m • x (recall that x is the vector whose components are xB = min i∈B x i , for all B ⊆ N , see ( 1)). Letting m B be the variable used for m(B) for any set B ⊆ N , the computation of PMR Cv (x, y; P) can be achieved by solving the following linear program:

max m m • ỹ -m • x s.t. m ∅ = 0, B⊆N m B = 1 B:{i}⊆B⊆A m B ≥ 0 ∀A ⊆ N, ∀i ∈ A (6) m • ã ≥ m • b ∀(a, b) ∈ P
Here, monotonicity with respect to set inclusion is guaranteed by the constraints given in Equation ( 6) that are the direct translation of constraints (4), as already observed in previous works [START_REF] Chateauneuf | Some characterizations of lower probabilities and other monotone capacities through the use of Möbius inversion[END_REF][START_REF] Meyer | On the use of the Choquet integral with fuzzy numbers in multiple criteria decision support[END_REF]. Their number still grows exponentially with the number of criteria. The number of variables is also exponential in the number of criteria. Fortunately, whenever the number of criteria is large, more compact LP formulations can be derived for some particular subclasses of capacities. For example, we consider now the case of 2-additive capacities and the case of belief functions before considering general capacities.

2-Additive Capacities

Recall that a 2-additive capacity has non-null Möbius masses only on subsets having at most two elements. Hence we have only (n 2 + n)/2 variables, one Möbius mass m {i} for every singleton and one denoted indifferently m {i,j} or m {j,i} for every subset {i, j} of size two. Using these notations, the previous linear program simplifies as follows:

max m B⊆N :|B|≤2 m B (ỹ B -xB ) s.t. m ∅ = 0, i∈N m {i} + i,j∈N :i<j m {i,j} = 1 (7) j∈B m {i,j} ≥ 0 ∀i ∈ N, ∀B ⊆ N : {i} ⊆ B ( 8
) B⊆N :|B|≤2 m B (ã B -bB ) ≥ 0 ∀(a, b) ∈ P
As stated above, the general exact method to optimize PMR Cv (x, y; P) requires handling the monotonicity constraints. This requires n2 n-1 constraints (due to [START_REF] Braziunas | Minimax Regret-based Elicitation of Generalized Additive Utilities[END_REF]) and two constraints for ensuring a normalized capacity [START_REF] Braziunas | Decision-theoretic elicitation of generalized additive utilities[END_REF]. This results in a number of constraints which is exponential in the number of criteria, even assuming a 2-additive capacity with a quadratic number of variables! In the 2-additive case, Hüllermeier et al. [START_REF] Fallah Tehrani | Learning monotone nonlinear models using the Choquet integral[END_REF] proposed to reduce the number of constraints by using the fact that normalized (monotonic) capacities form a convex polytope. As a consequence, all normalized (monotonic) capacities can be written as convex combinations of its n 2 extreme points given below:

m A 1 (X) = 1 if X = A 0 otherwise A ∈ Z 1 and m A 2 (X) =      1 if X = ∅ and X ⊂ A -1 if X = A 0 otherwise A ∈ Z 2
where

Z 1 = {A ⊆ N | 1 ≤ |A| ≤ 2} and Z 2 = {A ⊆ N | |A| = 2}
. Thus, at the expense of adding a quadratic number of variables, which are the weights of the convex combination, the monotonicity (8) and normalization [START_REF] Braziunas | Decision-theoretic elicitation of generalized additive utilities[END_REF] constraints can be replaced by the following (3n 2 +n+2)/2 constraints:

m B = A∈Z1 α A 1 m A 1 (B) + A∈Z2 α A 2 m A 2 (B) ∀B ⊆ N s.t |B| ≤ 2 α A 1 ≥ 0 ∀A ∈ Z 1 α A 2 ≥ 0 ∀A ∈ Z 2 A∈Z1 α A 1 + A∈Z2 α A 2 = 1
Therefore, for 2-additive capacities, this LP-formulation based on Möbius masses is more compact and can be solved efficiently to compute PMR Cv (x, y; P) and therefore MR Cv (x, X ; P). Moreover the approach proposed in [START_REF] Timonin | Robust optimization of the Choquet integral[END_REF] to compute MR Cv (x, X ; P) may also be pratically feasible, as observed by the author, since the number of extreme points of 2-additive capacities is quadratic in the number of criteria. However, using this approach within an incremental elicitation procedure may be prohibitive, since the size of Θ * P becomes larger as the size of P increases.

Belief Functions Belief functions are a subclass of convex capacities characterized by positive Möbius masses. We have seen in the previous section that convex capacities might be a natural choice to model the preference for balanced solutions within the Choquet integral model. Hence, we may want to use belief functions for that purpose. Whenever we restrict the set of capacities to belief functions, monotonicity constraints are naturally satisfied due to the non-negativity of Möbius masses. In this case, constraints in ( 6) are no longer necessary for monotonicity and can be replaced by all non-negativity constraints m B ≥ 0, B ⊆ N . Moreover, if we further restrict the analysis to 2-additive set-functions, we get:

max m B⊆N :|B|≤2 m B (ỹ B -xB ) s.t. m {i} ≥ 0 ∀i ∈ N m {i,j} ≥ 0 ∀i, j ∈ N : i < j i∈N m {i} + i,j∈N :i<j m {i,j} = 1 B⊆N :|B|≤2 m B (ã B -bB ) ≥ 0 ∀(a, b) ∈ P
For 3-additive capacities, one needs to account for masses m {i,j,k} but the principle is the same.

General capacities As mentioned above, in the general case, the computation of any PMR Cv (x, y; P) involves exponentially many constraints so as to guarantee the monotonicity of capacities considered in the elicitation process. We have shown above that, for some subclasses of capacities (i.e. 2-additive, belief functions), the number of such constraints that are actually needed to formulate the PMR optimization problem, is much lower. Unfortunately, these subclasses correspond to specific attitudes that do not necessarily match with the DM's preferences. We present now another incremental elicitation procedure without prior assumption on the capacity (for more details, the reader is referred to [START_REF] Benabbou | Incremental elicitation of Choquet capacities for multicriteria decision making[END_REF]). To do so, we first focus on the PMR-optimization problem and then, we present the associated query strategy.

This procedure is based on a different type of queries involving binary alternatives of type 1A0 where 1A0 represents, for any subset of criteria A, a fictitious alternative with a top utility on all criteria in A and a bottom utility on all other criteria. Precisely, the DM will be asked to compare such alternatives to constant utility profiles of type Λ = (λ, . . . , λ). Let P be a set of preference statements obtained by only asking this type of queries to the DM.

Note that with the Choquet integral model, for any v ∈ Θ P , we have C v (Λ) = λ for any Λ ∈ [0, 1] n and C v (1A0) = v(A) for any A ⊆ N . Consequently, if the DM states that 1A0 (resp. Λ) is preferred to Λ (resp. 1A0), then adding the pair (1A0, Λ) (resp. (Λ, 1A0)) to P amounts to imposing the constraint v(A) ≥ λ (resp. v(A) ≤ λ) to all capacities v ∈ Θ P . Thus, all constraints given by Equation ( 5) can be replaced by boundary constraints over variables by updating the boundaries of an interval [l A , u A ] whenever a preference statement involving 1A0 is observed, A ⊆ N (i.e. at any step of the elicitation procedure, [l A , u A ] defines the set of admissible values of v(A) according to the observed preferences).

Moreover, for all v ∈ Θ P , we know that v is monotonic by Definition 3, and so v(A) ≥ λ (resp. v(A) ≤ λ) implies that v(B) ≥ λ (resp. v(B) ≤ λ) for all B ⊇ A (resp. B ⊆ A). Assume now that, whenever a pair of type (1A0, Λ) (resp. (Λ, 1A0)) is inserted in P, the boundaries of all intervals [l B , u B ] are updated accordingly, B ⊇ A (resp. B ⊆ A). Then, the following proposition holds:

Proposition 3. Any set-function v : A → [0, 1], with A ⊂ 2 N , such that: 1. v(A) ∈ [l A , u A ] for all A ∈ A (boundary constraints) 2. v(A) ≤ v(B) for all A, B ∈ A s.t. A ⊂ B (monotonicity constraints)
can be completed into a capacity in Θ P .

Proof. We can construct a complete capacity by setting first v({i}) to l {i} for all i ∈ N such that {i} ∈ A; then, we can set iteratively the value of v(A) to max{l A , max {i∈A} v(A\{i})}, for all A proper subset of N such that A ∈ A and v(A\{i}) is known for all i ∈ A. Thus, the constructed set-function defined on 2 N satisfies monotonicity and preference constraints by construction of all boundary intervals.

Finally, thanks to the latter proposition, we can remove from Equation (4) and Equation (5) all monotonicty and preference constraints involving any subset of criteria that is not in the objective function [START_REF] Benabbou | Incremental elicitation of Choquet capacities for multicriteria decision making[END_REF]. Thus, recalling that X (i) (resp. Y (i) ) denotes the i-th level set of x (resp. y) used in the computation of its Choquet value (see Definition 4), the optimization of PMR Cv (x, y; P) for any two alternatives x, y ∈ X can be achieved by solving the following simpler linear program:

max v n i=1 y (i) -y (i-1) v Y (i) - n i=1 x (i) -x (i-1) v X (i) (9)
s.t. v X (i+1) ≤ v X (i) ∀i ∈ {1, . . . , n -1} (10)
v Y (i+1) ≤ v Y (i) ∀i ∈ {1, . . . , n -1} (11) v X (i) ≤ v Y (j) ∀i, j ∈ N s.t X (i) ⊂ Y (j) (12)
v

Y (i) ≤ v X (j) ∀i, j ∈ N s.t Y (i) ⊂ X (j) (13)
l X (i) ≤ v X (i) ≤ u X (i) ∀i ∈ N (14) l Y (i) ≤ v Y (i) ≤ u Y (i) ∀i ∈ N (15)
where Equations (10-13) and Equations (14-15) are respectively the new monotonicity and preference constraints. In this linear program, there are at most 2n -1 variables (all level sets of x and y) instead of 2 n (all subsets of criteria). However, some monotonicity constraints are redundant or unnecessary, meaning that this linear program can be further simplified. More precisely, for all decision variables v A , let w A denote its coefficient in the objective function [START_REF] Braziunas | Elicitation of factored utilities[END_REF] given below:

• ∀i ∈ N, [X (i) = Y (i) ] ⇒ [w X (i) = -(x (i) -x (i-1) ) ≤ 0 and w Y (i) = y (i) -y (i-1) ≥ 0] • ∀i ∈ N, [X (i) = Y (i) ] ⇒ [w X (i) = y (i) -y (i-1) -(x (i) -x (i-1) )]
Consequently, since the objective function has to be maximized, we know that v A will be as small (resp. large) as possible for all A ∈ {X (i

) | i ∈ N, X (i) = Y (i) } (resp. A ∈ {Y (i) | i ∈ N, Y (i) = X (i) })
and so Equation ( 12) is not necessary to solve the PMR Cv optimization problem. Besides, the number of constraints given by Equation ( 13) can be reduced by noting that if there exists i, j ∈ N such that Y (i) ⊂ X (j) , then we also have Y (i) ⊂ X (k) for all k ∈ [[1; j]], which imposes redundant constraints with Equation [START_REF] Braziunas | Assessing regret-based preference elicitation with the UT-PREF recommendation system[END_REF]. Consequently, the constraint v

Y (i) ≤ v X (j) should be imposed only if Y (i) ⊂ X (j)
and Y (i) ⊆ X (j+1) . However, if Y (i+1) ⊆ X (j) is also satisfied, then there is still a redundancy but with Equation ( 11) this time. Thus, the constraint v

Y (i) ≤ v X (j) should be imposed only if Y (i) ⊂ X (j) , Y (i) ⊆ X (j+1)
and Y (i-1) ⊆ X (j) . Finally, the number of monotonicity constraints that are actually needed to solve this optimization problem is now below 3(n -1). This simpler linear program can be solved using an iterative procedure (see [START_REF] Benabbou | Incremental elicitation of Choquet capacities for multicriteria decision making[END_REF] for further details).

Example 1. Consider a problem defined on 5 criteria, i.e. N = {1, 2, 3, 4, 5}, and two performance vectors x = (0.3, 0.1, 0.6, 0.5, 0.8) and y = (0.1, 0.2, 0.3, 0.5, 0.4). The linear program associated with PMR Cv (x, y; P) computation is the following:

max v 0.1v {2,3,4,5} + 0.1v {4,5} + 0.1v {4} -0.2v {1,3,4,5} -0.1v {3,4,5} -0.1v {3,5} -0.2v {5} s.t. v {5} ≤ v {3,5} , v {3,5} ≤ v {3,4,5} , v {3,4,5} ≤ v {1,3,4,5} , v {1,3,4,5} ≤ v N (16) v {4} ≤ v {4,5} , v {4,5} ≤ v {3,4,5} , v {3,4,5} ≤ v {2,3,4,5} , v {2,3,4,5} ≤ v N (17) l {5} ≤ v {5} ≤ u {5} , l {3,5} ≤ v {3,5} ≤ u {3,5} , l {3,4,5} ≤ v {3,4,5} ≤ u {3,4,5} l {1,3,4,5} ≤ v {1,3,4,5} ≤ u {1,3,4,5} , l N ≤ v N ≤ u N , l {4} ≤ v {4} ≤ u {4} l {4,5} ≤ v {4,5} ≤ u {4,5} , l {2,3,4,5} ≤ v {2,3,4,5} ≤ u {2,3,4,5}
where the constraints in [START_REF] Gonzales | GAI networks for utility elicitation[END_REF] are those given by Equation [START_REF] Braziunas | Assessing regret-based preference elicitation with the UT-PREF recommendation system[END_REF] and the constraints in [START_REF] Grabisch | A review of methods for capacity identification in Choquet integral based multi-attribute utility theory[END_REF] correspond to Equation [START_REF] Chajewska | Making Rational Decisions Using Adaptive Utility Elicitation[END_REF]; the other constraints are those associated with Equations (14-15). Thus, there are only eight monotonicity constraints [START_REF] Gonzales | GAI networks for utility elicitation[END_REF][START_REF] Grabisch | A review of methods for capacity identification in Choquet integral based multi-attribute utility theory[END_REF].

Since the procedure focuses on a specific type of queries, we cannot use the CSS to choose the next query in the elicitation procedure. The WMMR criterion (see Definition 10) is used instead, i.e. we are looking for a query involving a pair (A * ⊆ N, λ * ∈ [l A * , u A * ]) that minimizes the minimax regret in the worst scenario of answers. More formally, the pair (A * ⊆ N, λ * ∈ [l A * , u A * ]) minimizes max{MMR Cv (X ; P ∪ {(1A0, Λ)}), MMR Cv (X ; P ∪ {(Λ, 1A0)})}. In order to determine such a pair, we have to compute, for all A ⊆ N :

min λ∈[l A ,u A ] max{MMR Cv (X ; P ∪ {(1A0, Λ)}), MMR Cv (X ; P ∪ {(Λ, 1A0)})} (18)
Then, A * is the set minimizing ( 18) and λ * is the value in [l A * , u A * ] achieving this minimum. Similarly to what is observed for utility functions over consequences [START_REF] Wang | Incremental Utility Elicitation with the Minimax Regret Decision Criterion[END_REF], we observe here that, given a set A ⊆ N , the two functions MMR Cv (X ; P ∪ {(1A0, Λ)}) and MMR Cv (X ; P ∪ {(Λ, 1A0)}) necessarily intersect because the former is a decreasing function of λ, the latter is an increasing one, and they have the same maximum (MMR Cv (X ; P)). Thus, for any set A ⊆ N , the intersection of these functions gives the value of λ achieving the minimum [START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid[END_REF]; it can be easily computed by a bisection algorithm relying on the relative positions of the two curves at two distinct points. However, it may happen that the value defined in [START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid[END_REF] decreases below MMR(X ; P) for no set A ⊆ N , which means that the WMMR optimal query will not necessarily induce a minimax regret reduction. In such cases, to decide between all possible queries, a less conservative criterion than WMMR can be used (for example, see [START_REF] Benabbou | Incremental elicitation of Choquet capacities for multicriteria decision making[END_REF]).

Note however that the determination of the next query implies to select A within the 2 n -2 possible proper subsets of N , which becomes cumbersome as the number of criteria increases. To make this selection step more efficient, we focus on sets directly involved in the computation of MMR Cv (X ; P) as a heuristic and so of PMR Cv (x * P , y * P ; P), where x * P is an arbitrarily chosen MMR-alternative and y * P is arbitrarily chosen in arg max y∈X PMR(x * P , y; P). These sets are all level sets of x * P and y * P . By doing so, the heuristic will further constrain utility parameters involved in MMR Cv (X ; P), thus intuitively reducing MMR Cv (a fact that has already been observed in [START_REF] Benabbou | Incremental elicitation of Choquet capacities for multicriteria decision making[END_REF]). Thus, at most 2n -2 sets are investigated (all level sets of x * P and y * P , excluding N ) instead of 2 n -2.

Observations

We are interested in comparing the behavior of MMR under the different family of aggregators considered here. We have noted above that constraining the set of feasible aggregation functions by asking queries leads to lower regrets (see Observation 1). The same observation can be done whenever constraining the set of aggregation functions by assuming a more restricted family of aggregation functions.

Observation 2. Given the same set of preference statements P, OWA with monotone weights (OWA m ) is associated with lower minimax regret than OWA with (arbitrary) positive weights (OWA p ).

MMR OWAm (X ; P) ≤ MMR OWAp (X ; P)

Similarly, a linear utility model is associated with lower regret than a model based on Choquet (the latter having more flexibility and including linear utility as a special case), when considering the same set of preference statements. The same can be stated comparing OWA and Choquet integral model.

Observation 3. Given the same set of preference statements P, the linear utility model is associated with lower minimax regret than the Choquet integral model.

MMR WS (X ; P) ≤ MMR Cv (X ; P)

Given the same set of preference statements P, OWA is associated with lower minimax regret than the Choquet integral model. MMR OWA (X ; P) ≤ MMR Cv (X ; P)

The set of linear utility models and OWA models are disjoint (excluding degenerate cases), therefore there is no strong relation between regrets in these two cases. However, as we shall see in the experimental section, we observe that minimax regret is often lower in practice when assuming OWA rather than the linear utility model. One intuition of why this happens is the following. The rearrangement of criteria for computing minimax regret under the assumption of a OWA utility model, induces a mapping into a more compact space. In particular, notice that the dominance relation P according to Pareto will still hold if we re-arrange the criteria of each, sorting them in increasing order of satisfaction.

Observation 4. For any two alternatives x, y ∈ X :

x P y ⇒ x ↑ P y ↑
where vector x ↑ (resp. y ↑ ) is obtained by sorting the components of x (resp. y) from the worst to the best.

Therefore it follows that ND(X ↑ ), the non dominated set (all alternatives for which there is no other alternative that P -dominates them) of the data set

X ↑ = {x ↑ | x ∈ X }, is a subset of ND(X ), the non dominated set of X . Observation 5. ND(X ↑ ) ⊆ ND(X )
Since a dominated alternative cannot be among MMR-alternatives and neither will be chosen by the DM, they can be pruned (we need to maintain only alternatives in ND(X ↑ )). This means that, in many instances, the RS and the DM will have to choose among a more restricted set of choices.

Minimax Regret Optimization

In this section, we consider how to address the computation of MMR. In Section 4.1, we describe how a MMR-alternative can be found using search methods, solving a reduced number of PMR optimizations (thoroughly discussed in the previous section). Then, we perform a number of numerical tests and report computation times in a number of different settings in Section 4.2.

Implementation with Search Methods

PMR computation constitutes the main building block for regret-based optimization; in order to determine a MMR-alternative, a series of PMR computations has to be performed to identify the alternative that has the smallest PMR against all other possible alternatives (i.e. the smallest MR). The minimax regret criterion is essentially a game between the recommender system (RS) and an adversary, a fictitious decision maker, whose most preferred choice is always the alternative that maximizes the pairwise max regret (PMR) of the RS's choice.

In order to compute MMR, the naive approach would test all n(n-1) combinations of choices for the RS and for the adversary by computing PMR for each of these combinations. Notice that only non dominated alternatives (ND(X )) need to be checked; indeed, Pareto-dominated alternatives can be removed as they will never be chosen by either the RS (alternatives that Pareto-dominate them always have smaller PMR) or the adversary (alternatives that Pareto-dominate them will induce larger regrets).

A better idea is to implement a search problem [START_REF] Braziunas | Decision-theoretic elicitation of generalized additive utilities[END_REF]. The optimization is a search process in an extremely broad but shallow tree; the root corresponds to the RS's choice of the recommendation and for each possible choice, the adversary can respond with an alternative (aimed at maximizing PMR). The leafs of the tree correspond to PMR computations between the corresponding RS's choice and the adversary's.

During the search, the following bounds are maintained:

• U (X ): an upper bound on MMR, consisting in the MR of the best option found so far for the RS's choice, initialized to positive infinity.

• L(x i ): a lower bound on MR associated with x i ∈ X initialized to negative infinity.

After computing PMR(x i , x j ; P), the pairwise max regret of x i against x j , the lower bound L(x i ) is updated to max{L(x i ), PMR(x i , x j ; P)}. Whenever it happens that L(x i ) ≥ U (X ), the RS can prune option x i (because its MR can only be higher than L(x i ) and the RS has already found an alternative with lower MR).

This method results in a significant reduction of PMR computations. It is however important to carefully choose the evaluation order of RS's choices in order to prune as much as possible. This can result that (empirically) only almost a linear number of PMR optimizations is needed instead of a quadratic number. In our implementation, following [START_REF] Viappiani | Optimal set recommendations based on regret[END_REF], we augment the tree search optimization of [START_REF] Braziunas | Decision-theoretic elicitation of generalized additive utilities[END_REF] considering the following strategy that appears to be very efficient. Before starting the search, we improve the lower bound L(x i ) for all x i ∈ X as follows. We consider k instances of weights (these represent a standard weight vector for WS, OWA and HWA models and a vector of Möbius masses for Choquet integral model; however the treatment is identical in all these cases), that we call reference vectors and we denote them with w 1 , . . . , w k . These are obtained by finding, for each component j of these vectors, the compatible vector of weights that maximizes the component j (i.e. w j = arg max w∈Θ P w j where Θ P is the set of parameters consistent with P); k is therefore the number of parameters of our problem (e.g. n for WS and OWA, 2n for HWA and n (n+1) 2 for 2-additive Choquet). For each alternative x i ∈ X , we update the value of L(x i ) (initialized to negative infinity) k times. More precisely, for each reference vector w j , we first evaluate the regret, when assuming w j represents DM's preferences, of choosing x instead of the best item according to w j (i.e. x * w j = arg max x∈X w j • x). Then, we update as follows:

L(x i ) = max{w j • x * w j -w j • x i , L(x i )} (19)
Using this method (that only involves standard vector multiplications), it is not unusual that a large number of alternatives are immediately discarded from RS's choices without any PMR computation (L(x i ) being larger than the current value of U (X )).

We also consider the following enhancements in the search evaluation:

• To determine the order for evaluating RS's choices, we sort alternatives by L(x i ) values computed thanks to reference vectors [START_REF] Grabisch | Aggregation Functions. Encyclopedia of Mathematics and its Applications[END_REF].

• Whenever we evaluate a new candidate x i for the RS's choice, if L(x i ) < U (X ), we solve the optimization problem w -= min w∈Θ P w • x i before starting the series of PMR computations. The weights w -are the one minimizing the value of x i over the set of aggregation functions consistent with P. We then use w -to check if option x i can be pruned: that happens if the regret between the best alternative according to w -and x i , when assuming w -represents DM's preferences, exceeds the current bound U (X ). Since w -is the less favorable instance to x i , it is often the case.

• Moreover, if x i has not been pruned after considering the previous pruning rule, we use w -for establishing in which order to evaluate the possible choices of the adversary. More precisely, we sort the alternatives according to w -from the best to the worst. The intuition is that alternatives that have high aggregate value with w -have the potential of achieving high PMR against the chosen x i (and hence x i will be pruned sooner when comparing L(x i ) to U (X )).

Experiments

In the following experiments, we aim at quantifying computation time for optimizing MMR, for the different aggregation models, in different settings (varying dataset size, the number of criteria n and the number of preference statements). In these experiments, we consider the following datasets X :

• two datasets of a hundred random alternatives (n = 10 and n = 20) sampled uniformly in [0, 1] n .

• datasets consisting of the Pareto set obtained by solving randomly generated instances of the multiobjective Knapsack problem:

max x ( m i=1 x i v 1 i , . . . , m i=1 x i v n i ) s.t. m i=1 w i x i ≤ W x i ∈ {0, 1} ∀i ∈ {1, . . . , m}
where the max operator represents the Pareto-dominance, m is the number of items, w i is the mass of item i, x i is the decision variable associated with the item i, v j i is the value of item i on the criterion j and W is the knapsack's capacity.

And we consider the following different aggregation models:

• OWA m : OWA model with decreasing positive weights.

• OWA p : OWA model with positive weights.

• Linear: Weighted sum model without any restriction on the set of weights.

• C2A p : 2-additive Choquet integral model with positive Möbius masses.

• HWA: HWA model with positive p weights and decreasing positive w weights.

• Cv: Choquet integral without any restriction on the capacity.

Note that we will consider HWA and Cv separately as PMR HWA can not be optimized exactly using mathematical programming and PMR Cv is not based on comparison queries (preference statements must compare fictitious alternatives). In Table 1, we report computation times1 in seconds (time) for the optimization of MMR and the number of PMR computations (checks) to show the effectiveness of the pruning techniques described in Section 4.1. In order to evaluate how the number of preference statements (preferences) impacts on the two previous quantities, we report computational results at different steps of the incremental elicitation procedure (varying the number of preference statements). Results have been obtained by averaging over 30 runs and preference statements have been generated by randomly choosing two alternatives in the datasets.

From Table 1, we can notice that the number of PMR computations is usually much lower than n(n -1), thanks to the very efficient pruning technique. In fact, when no preference statement is present, the alternative that is tested first is the minimax optimal alternative (thanks to the efficient ordering produced by the reference vectors). Moreover, MMR optimization with the C2A p model is more computationally intense (due to the larger number of parameters) but all computations are relatively fast and require less than a minute almost all the time. Finally, as expected, the computation time increases with the number of preference statements (however this is not a general rule) for all considered models. This is due to the fact that adding a preference statement amounts to adding a constraint in the linear program optimizing PMR. We now focus on the optimization method that can elicit a Choquet integral with a general capacity (see Section 3.4). In the experiments, we consider the Pareto set of multiobjective Knapsack problems restricted to 150 and 1000 alternatives. Results have been obtained by averaging over 50 runs 2 and random preferences are imposed of the type 1A0 Λ or Λ 1A0.

From Table 2, we can see that the higher the number of preference statements, the lower the computation time of MMR Cv optimization, unlike the previous models; in this case, a new preference statement involving a set of criteria A ⊆ N reduces the space of feasible values of the decision variable v(A). Results are given in Table 3 and have been obtained by averaging over 30 runs 3 .

Our technique for PMR HWA optimization relies on sampling a set of criterion weights p i , computing the corresponding PMR OWA for each of them and finally taking the highest value (see Section 3.3). In our simulations, as expected, computation time of heavily depends on the number of samples used; the larger computation time is due to repeating PMR OWA optimizations with different p i , multiplying the running time by a large constant factor.

Incremental Elicitation Experiments

In a series of experiments, we consider how our regret optimization methods can be used for incremental elicitation; we make use of these optimizations in order to decide the next query to ask (e.g. for the CSS, an arbitrarily chosen MMR-alternative x * P has to be compared to an alternative arbitrarily chosen in arg max y∈X PMR(x * P , y; P)) and measure MMR in function of the number of queries asked. First, we aim at comparing the incremental elicitations based on the following preference models: OWA model with decreasing positive weights (OWA m ), OWA model with positive weights (OWA p ), HWA model with positive p weights and decreasing positive w weights (HWA), linear model using a weighted sum (Linear) and 2-additive Choquet with positive Möbius masses (C2A p ). While there are different types of queries that could be asked to the DM, such as comparisons and bound queries (local/global), we consider here comparison queries dictated by the very efficient CCS (see Section 3.2), that are holistic comparisons between two alternatives.

For each of these preference model assumptions (that is the assumption made by the RS when computing the MMR-alternative), we experiment with simulated DMs that answer queries according to an aggregation functions from the same family of aggregators with random parameters (the weights of Linear, 2 Linear optimizations are done using the Gurobi library of Java. 3 Linear optimizations are done under MatLab using the Gurobi solver on a machine with an Intel Core i7 CPU 3.60GHz with 16 GB of memory. OWA m and OWA p , the weights p and w for HWA and the Möbius masses for C2A p ). To randomly generate the weights of simulated DMs, we consider different generative models:

• a set of "uniform" weights that are randomly sampled (for each criterion) from an uniform distribution between 0 and 1, and then normalized so that each vector sums up to 1.

• a set of "extreme" weights that are generated by sampling, for each criterion, a value 0 with probability 0.4, a value 1 with probability 0.1, a value sampled from U [0, 0.3] with probability 0.3 and a value sampled U [0, 1] with probability 0.2; each vector of weights is then normalized.

The second generative model has been considered in order to avoid experimenting only with aggregation functions that score too similarly the different criteria when considering a large number of criteria. We consider a simulated setting where the DM answers comparison queries by indicating which alternative is preferred according to his/her sampled aggregation function. We start from an empty set of preferences and we compute MMR at each step of the incremental elicitation process. We plot on the same graphs the results obtained with different models in order to explicitly compare the difference in the values of regret. Results have been obtained by averaging over 30 runs. Figure 1 shows the reduction of MMR and the real regret (computed with the DM's sampled aggregation function) for a simulated incremental elicitation process with a random dataset composed of 150 alternatives and 10 criteria (analogously to the tests described in Section 4.2). Figures 1a,1b refer to a DM with an "uniform" aggregation function, while Figure 1c, 1d report results for an "extreme" aggregation function. Figure 2 shows the same kind of experiments but for the Knapsack dataset with 10 criteria described in Section 4.2 and restricted to 150 alternatives.

From these two figures, we can see first how the MR of the MMR-alternative (or MMR) reduces reasonably quickly during the interaction procedure. The real regret, computed with the DM simulated aggregation function, is significantly lower than MMR; in fact, the true optimal alternatives are always (in all runs of the experiments) found in a number of iterations much lower than 50.

Then, we empirically observe that MMR OWAp and MMR OWAm are lower than MMR WS and that the incremental elicitation procedure based on OWA requires fewer queries to identify the true best alternative (null real regret). When assuming monotonicity for the weights (MMR OWAm ), favoring well-balanced alternatives, this is even more striking. Finally, the greater flexibility of Choquet models means that MMR C2Ap is higher (than MMR WS , MMR OWAm and MMR OWAp ), but still, the real regret plot shows that the incremental elicitation process converges to the best alternative reasonably fast. Figure 3 includes in the comparison the more demanding model HWA in reduced instances of the bicriteria Knapsack problem with only 40 alternatives. As we only consider two criteria, there is no need to consider the case of "extreme" weights. Moreover, in this setting, 100 particles are sufficient to well approximate the MMR value. From Figure 3, we can notice that, in all cases, the recommended item very quickly converges to the optimal choice in a couple of queries, even if HWA is associated with highest minimax regret. In the second experiments, we perform a kind of "cross-evaluation" of interactive elicitation with different preference model assumptions, meaning that MMR is calculated according to a model (Linear, OWA m , OWA p and C2A p ) that might be different from the DM underlying model that dictates his/her answers. The results of this experimentation setting are presented in Table 4 and Table 5 (the numbers correspond to the real regrets after 0, 5, 10 and 15 queries). The first table considers 150 alternatives of the Knapsack problem with 3 criteria (with "extreme" weights) and the second one considers 150 alternatives of the Knapsack problem with 6 criteria (with "extreme" weights). Results are averaged over 100 runs.

Not surprisingly, the real regret is generally lowest when the preference model assumed by the RS coincides with the "true" model of the DM (lowest numbers are around the diagonal). However, we notice a certain degree of robustness in using a more general model (C2A p ) even when the DM is making decision using a more specialized model as OWA m , OWA p or the weighted sum. The situation is severely bad (high real regret) when assuming OWA m or OWA p but the DM is making decisions using a linear model. For the kind of weights used in the experiments, we noticed a (surprising) relatively good performance in some settings of assuming OWA p when tested against C2A p ; however in other settings, this assumption results in a very significant real regret. Further studies with plausible weights learned from real users (DMs) are needed to make stronger conclusions about the robustness of the models in practical contexts.

Finally, we consider the method that is able to elicit a general capacity by asking queries about fictitious alternatives (see paragraph "General capacities" in Section 3.4). These last experiments allow elicitations without making prior assumptions on the type of the capacity; in the simulation we consider here, different preference models (Linear, OWA, Choquet integral) are used to represent the true underlying model of DM preferences (but the RS assumes a general Choquet integral as preference model). The simulated DM is asked to answer queries of type 1A0 Λ chosen in order to ensure the highest myopic reduction of MMR Cv in the worst case of answer. In order to randomly generate general capacities satisfying the set monotonicity constraints to model DM's preferences, we considered a recursive method where capacity values are sampled recursively starting from the bottom of the set-inclusion lattice. The capacity of singletons are sampled from U [0, 0.5]; then, iteratively, for the set of criteria A of size d > 1, we sample from U [max i∈A v(A\{i}), 1], the uniform distribution between the maximum of capacity values of its subsets of size d-1, and the value 1; the capacity of the set containing all criteria is imposed to be 1. By construction, the resulting capacity is monotone and normalized. We also consider an alternative method where the capacity value of a set of size d is sampled between the maximum capacity of its subsets of size d-1 and the latter quantity plus 0.1. The second preference simulation has been used to model preferences somewhat more difficult to elicit. The results on the multiobjective Knapsack problem with 10 criteria (restricted to 150 alternatives for Figure 4 and 1000 alternatives for Figure 5) have been obtained by averaging over 200 runs (100 runs for each different ways to simulate DM).

Here again, from these two figures, we can see that the MMR reduces reasonably quickly during the incremental elicitation process. Since the RS is given no information about the type of the capacity, MMR Cv necessarily decreases more slowly (than when making a specific assumption about the type of the capacity); this can be seen by comparing Figure 4a with Figures 2a and2c. Figure 4b and Figure 5b show that the recommended alternative is approximately as good as the true optimal alternative; the real regret is much smaller than MMR Cv .

Discussion and Conclusions

A large variety of systems need to handle preferences [START_REF] Peintner | Preferences in interactive systems: Technical challenges and case studies[END_REF]; these include recommender systems and systems for decision support [START_REF] Viappiani | Preference-based search using example-critiquing with suggestions[END_REF]. Preference or utility assessment is therefore critical for these systems. Preference elicitation and preference learning are currently active areas of research, as shown by a recently edited book [START_REF]Preference Learning[END_REF].

A key idea, adopted by a number of researchers, for acquiring decision maker's preferences is that of eliciting in an adaptive way, meaning to focus on asking relevant queries for the given decision problem. An introduction to some fundamental ideas of learning the preferences adaptively can be found in [START_REF] Braziunas | Elicitation of factored utilities[END_REF]; minimax regret criterion has been proposed as a tool for utility elicitation and recommendation by [START_REF] Boutilier | Constraint-based Optimization and Utility Elicitation using the Minimax Decision Criterion[END_REF]. The problem of choosing the "best" query selection strategy (limiting the number of queries) for regretbased elicitation is addressed in [START_REF] Viappiani | Regret-based optimal recommendation sets in conversational recommender systems[END_REF].

Additive utility functions suffer from limited flexibility. In order to overcome the limitations of additive models, generalized additivity has been considered [START_REF] Gonzales | GAI networks for utility elicitation[END_REF]. Alternatively, non linear aggregation functions such as Choquet have been advocated; a thorough review of the use of Choquet integrals can be found in [START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid[END_REF]. This article contributes to the state of the art by proposing methods for incrementally learning complex preference models from decision maker's responses. In our work, we adopted the minimax regret approach of Boutilier et. al. [START_REF] Boutilier | Constraint-based Optimization and Utility Elicitation using the Minimax Decision Criterion[END_REF] allowing robust recommendations under uncertainty with guarantees with respect to the worst case loss. Furthermore, minimax regret can be used as a driver for choosing the next query to ask [START_REF] Viappiani | Regret-based optimal recommendation sets in conversational recommender systems[END_REF] allowing efficient interactive elicitation; regret-based elicitation has been validated in a user study [START_REF] Braziunas | Assessing regret-based preference elicitation with the UT-PREF recommendation system[END_REF].

We considered regret-based optimization assuming different utility models: OWA, HWA and Choquet integrals. The optimization is encoded as a search tree as in [START_REF] Braziunas | Decision-theoretic elicitation of generalized additive utilities[END_REF], where at each step, a pairwise max regret maximization is performed; computation of pairwise max regret values differs for each model. We provided efficient methods for regret optimization when considering OWA and restricted Choquet models assuming positive Möbius masses, and a method for HWA using sampling. We have also presented a very efficient method to elicit a Choquet integral without making any restrictive assumption on the capacity. Note that efficiency and generality are obtained at the expense of restricting queries to the comparison of fictitious alternatives rather than using actual alternatives. However, adapting minimax regret optimization to non linear utility models proved to be not trivial, due to the large parameter space associated with the Choquet integral, as well as the necessity of handling the induced constraints (set monotonicity of the underlying capacity measure, see [START_REF] Fallah Tehrani | Learning monotone nonlinear models using the Choquet integral[END_REF]). This means that particular care has to be given to the optimization part as future work. For instance, in [START_REF] Benabbou | Incremental elicitation of Choquet capacities for multicriteria decision making[END_REF], the authors overcome this issue by asking a specific type of queries to the DM and propose an algorithm in O(n 2 ) to solve the PMR Cv optimization problem. Another challenge is computational efficiency when computing MMR, as the decision space might be very large (this is often the case in recommender spaces, where the possible alternatives can be of several thousands.); we proposed here an efficient search method and provided experimental results.

In order to facilitate the use of our methodologies in practical contexts, a number of research questions still needs to be addressed: how to identify the type of utility model in the first place? How to choose the type of query (comparison, bound query, etc) appropriately? Our hope is that our contribution is a step forward a wider adoption of these aggregation methods. We also stress that there are also challenges related to the conceptual design of the interface of an interactive system from the point of view of user interaction, and behavioral issues related to preference assessment [START_REF] Viappiani | Preference-based search using example-critiquing with suggestions[END_REF][START_REF] Morton | Behavioural decision theory for multi-criteria decision analysis: a guided tour[END_REF][START_REF] Korhonen | Choice behavior in interactive multiplecriteria decision making[END_REF].

Figure 1 :

 1 Figure 1: Elicitation with the CSS: uniformly randomly generated datasets (150 alternatives, n = 10).

Figure 2 :

 2 Figure 2: Elicitation with the CSS: multiobjective Knapsack problem (150 alternatives, n = 10).

Figure 3 :

 3 Figure 3: Elicitation with CSS; Knapsack problem (40 alternatives, n = 2, "uniform" weights).

Figure 4 :

 4 Figure 4: Elicitation with queries of type "1A0 preferred to Λ ?": multiobjective Knapsack problem with 150 alternatives and n = 10 (simulated DMs answering according to a linear, OWA or general Choquet).

Figure 5 :

 5 Figure 5: Elicitation with queries of type "1A0 preferred to Λ ?": multiobjective Knapsack problem with 1000 alternatives and n = 10 (simulated DMs answering according to a linear, OWA or general Choquet).

Table 1 :

 1 Comparison of MMR optimizations under different aggregation models.

					OWAm	OWAp	Linear	C2Ap
	Dataset	n	size	preferences	time	checks	time	checks	time	checks	time	checks
	Uniform	10 100	0	0.16	101	0.13	101	0.13	101	0.21	101
	Uniform	10 102	5	0.19	101	0.16	101	0.21	101	0.36	202
	Uniform	10 100	10	0.21	101	0.19	101	0.24	101	0.48	101
	Uniform	10 102	20	0.25	101	0.25	101	0.28	102	0.61	101
	Uniform	20 100	0	0.19	99	0.15	99	0.15	99	0.59	99
	Uniform	20 100	5	0.21	99	0.18	99	0.21	198	0.92	99
	Uniform	20 100	10	0.24	99	0.21	99	0.26	100	1.07	206
	Uniform	20 100	20	0.28	99	0.26	99	0.29	99	1.49	99
	Knapsack 5	1000	0	1.47	999	1.21	999	1.19	999	1.21	999
	Knapsack 5	1000	5	1.71	999	1.72	999	2.61	999	2.65	999
	Knapsack 5	1000	10	1.88	999	2.09	999	2.61	2997	3.61	2997
	Knapsack 5	1000	20	2.26	999	2.55	999	2.97	2040	4.74	1191
	Knapsack 5	5353	0	8.04	5352	6.38	5352	6.32	5352	6.57	5352
	Knapsack 5	5353	5	9.17	5352	8.52	5352	13.01	5352	15.71	5352
	Knapsack 5	5353	10	10.68	5352	12.59	5352	15.35	5352	20.56	5352
	Knapsack 5	5353	20	12.30	5352	13.28	5352	17.41	5352	32.42	14401
	Knapsack 10 1000	0	1.58	999	1.21	999	1.21	999	1.46	999
	Knapsack 10 1000	5	2.02	999	2.49	1998	2.97	999	3.24	1266
	Knapsack 10 1000	10	2.03	999	2.40	999	3.27	999	3.93	999
	Knapsack 10 1000	20	2.44	999	3.21	999	3.09	1864	4.67	2085
	Knapsack 10 6518	0	10.14	6517	7.77	6517	7.71	6517	9.74	6517
	Knapsack 10 6518	5	12.52	6517	15.75	13034	35.90	13034	28.47	6517
	Knapsack 10 6518	10	13.00	6517	20.12	6517	30.94	6517	54.19	6517
	Knapsack 10 6518	20	15.89	6517	21.45	11067	29.47	6517	50.17	25413

Table 2 :

 2 MMR optimizations under Choquet integral model.

	Dataset	n	size preferences time	Dataset	n	size	preferences	time
	Knapsack 5	150	0	3.72	Knapsack 5	1000	0	34.59
	Knapsack 5	150	5	2.79	Knapsack 5	1000	5	34.37
	Knapsack 5	150	10	3.00	Knapsack 5	1000	10	27.58
	Knapsack 5	150	20	2.68	Knapsack 5	1000	20	28.89
	Knapsack 6	150	0	3.27	Knapsack 6	1000	0	26.22
	Knapsack 6	150	5	2.37	Knapsack 6	1000	5	29.93
	Knapsack 6	150	10	2.36	Knapsack 6	1000	10	28.64
	Knapsack 6	150	20	2.13	Knapsack 6	1000	20	28.42
	Knapsack 7	150	0	5.07	Knapsack 7	1000	0	87.09
	Knapsack 7	150	5	3.70	Knapsack 7	1000	5	34.73
	Knapsack 7	150	10	2.97	Knapsack 7	1000	10	25.19
	Knapsack 7	150	20	2.67	Knapsack 7	1000	20	22.37
	Knapsack 8	150	0	4.89	Knapsack 8	1000	0	28.59
	Knapsack 8	150	5	4.36	Knapsack 8	1000	5	34.98
	Knapsack 8	150	10	4.14	Knapsack 8	1000	10	26.24
	Knapsack 8	150	20	3.98	Knapsack 8	1000	20	22.05
	Knapsack 9	150	0	8.46	Knapsack 9	1000	0	59.54
	Knapsack 9	150	5	5.18	Knapsack 9	1000	5	38.87
	Knapsack 9	150	10	3.69	Knapsack 9	1000	10	29.40
	Knapsack 9	150	20	2.76	Knapsack 9	1000	20	23.42
	Knapsack 10 150	0	2.67	Knapsack 10 1000	0	31.12
	Knapsack 10 150	5	1.82	Knapsack 10 1000	5	18.19
	Knapsack 10 150	10	1.95	Knapsack 10 1000	10	15.19
	Knapsack 10 150	20	1.62	Knapsack 10 1000	20	13.01

Table 3 :

 3 MMR optimizations under HWA model. Finally, we consider computation time of MMR HWA optimization. To do so, we consider the Pareto set of multiobjective Knapsack problems (restricted to 40 and 150 alternatives); here again, considering preference statements amounts to adding constraints in the linear program used for computing PMR.

				HWA	HWA
				100 particles	1000 particles
	Dataset	n size preferences time	checks	time	checks
	Knapsack 2 40	0	22.56	40600	266.63	482000
	Knapsack 2 40	20	9.12	3900	80.21	39000
	Knapsack 3 150	0	113.04 152700	1253.19 702000
	Knapsack 3 150	20	148.55	14900	1578.94 149000

Table 4 :

 4 Cross-evaluation of elicitation processes -150 alternatives (Knapsack n = 3).

			RS model assumption
	DM true model	OWAm	OWAp	Linear	C2Ap
	No query
	OWAm	0.0213	0.3234 0.0804 0.0804
	OWAp	0.2633	0.2260	0.2326 0.2326
	Linear	0.3081	0.2844	0.2857 0.2857
	C2Ap	0.1131	0.1896 0.1197 0.1197
	After 5 queries
	OWAm	0.0000	0.0014 0.1666 0.1214
	OWAp	0.1265	0.0030	0.1546 0.1280
	Linear	0.2000	0.0772	0.0277	0.0283
	C2Ap	0.0592	0.0219	0.0609 0.0427
	After 10 queries
	OWAm	0.0000	0.0000	0.0949 0.0254
	OWAp	0.1265	0.0000	0.0963 0.0767
	Linear	0.2000	0.0759	0.0012	0.0019
	C2Ap	0.0592	0.0203 0.0216	0.0062
	After 15 queries
	OWAm	0.0000	0.0000	0.0944 0.0235
	OWAp	0.1265	0.0000	0.0955 0.0723
	Linear	0.2000	0.0759	0.0000	0.0000
	C2Ap	0.0592	0.0203 0.0107	0.0026

Table 5 :

 5 Cross-evaluation of elicitation processes -150 alternatives (Knapsack n = 6).

			RS model assumption
	DM true model	OWAm	OWAp	Linear	C2Ap
	No query
	OWAm	0.0000	0.2269 0.1993 0.1993
	OWAp	0.1676	0.1370	0.1737 0.1737
	Linear	0.2811	0.2079	0.2363	0.2363
	C2Ap	0.0459	0.1393 0.1603	0.1603
	After 5 queries
	OWAm	0.0000	0.0711 0.1588 0.0727
	OWAp	0.0592	0.0118	0.1325 0.0724
	Linear	0.1148	0.0865	0.0733	0.1119
	C2Ap	0.0186	0.0535	0.1221 0.0870
	After 10 queries
	OWAm	0.0000	0.0000 0.0036 0.0727
	OWAp	0.0592	0.0008	0.0617 0.0576
	Linear	0.1148	0.0373	0.0132	0.0266
	C2Ap	0.0186	0.0065	0.0391	0.0595
	After 15 queries
	OWAm	0.0000	0.0000 0.0000 0.0000
	OWAp	0.0592	0.0000	0.0420 0.0338
	Linear	0.1148	0.0328	0.0000	0.0063
	C2Ap	0.0186	0.0000	0.0018	0.0088

Linear optimizations are done under MatLab using the Gurobi solver on a machine with an Intel Core i7 CPU 3.60GHz with 16 GB of memory.

Acknowledgments

This work is part of the ELICIT project supported by the French National Research Agency through the Idex Sorbonne Universités under grant ANR-11-IDEX-0004-02.