--- title: "Incremental Elicitation of Rank-Dependent Aggregation Functions based on Bayesian Linear Regression" authors: - "Nadjet Bourdache" - "Patrice Perny" - "Olivier Spanjaard" doi: "10.24963/ijcai.2019/280" url: "https://ijcai.org/proceedings/2019/280" pdf: "https://ijcai.org/proceedings/2019/0280.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "2023-2029" track: "Main track" keywords: - "Knowledge Representation and Reasoning: Knowledge Representation and Decision ; Utility Theory" - "Machine Learning: Learning Preferences or Rankings" - "Multidisciplinary Topics and Applications: Recommender Systems" --- # Incremental Elicitation of Rank-Dependent Aggregation Functions based on Bayesian Linear Regression Nadjet Bourdache, Patrice Perny, Olivier Spanjaard *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 2023-2029. DOI: [10.24963/ijcai.2019/280](https://doi.org/10.24963/ijcai.2019/280) ## Abstract We introduce a new model-based incremental choice procedure for multicriteria decision support, that interleaves the analysis of the set of alternatives and the elicitation of weighting coefficients that specify the role of criteria in rank-dependent models such as ordered weighted averages (OWA) and Choquet integrals.  Starting from a prior distribution on the set of weighting parameters, we propose an adaptive elicitation approach based on the minimization of the expected regret to iteratively generate preference queries. The answers of the Decision Maker are used to revise the current distribution until a solution can be recommended with sufficient confidence. We present numerical tests showing the interest of the proposed approach. ## Full text ## 1 Introduction Designing efficient preference elicitation methods is one of the major challenges of computer-aided decision support. Various preference models have been proposed and studied in Decision Theory for modeling individual values and generating personalized recommendations. These models use preference parameters that must be tuned to the value system of the Decision Maker (DM). In multicriteria decision support, the key parameters that must be elicited to perform the preference aggregation are weighting coefficients that specify the role of criteria in the aggregation, in particular their relative importance and sometimes also their level of interaction, see e.g., [Tehrani et al., 2012]. Weighting coefficients can be elicited in a preliminary step and used for several recommendation tasks or can alternatively be elicited on the fly during the exploration of the set of alternatives. The latter approach, said to be incremental, has been widely investigated in AI in order to reduce the elicitation burden. Several utility elicitation methods are now available, see e.g., [Ha and Haddawy, 1997; Chajewska et al., 2000; Blythe, 2002; Wang and Boutilier, 2003; Braziunas and Boutilier, 2007]. The incremental approach makes it possible to concentrate the elicitation effort on the part of the preferential information that is sufficient to determine an optimal choice. It also makes it possible to adapt the questionnaire to DM's answers, to quickly dispel the uncertainty attached to incomparable alternatives. One key aspect of interactive preference elicitation is to limit the number of preference queries without downgrading the quality of recommendations. To this end, efficient adaptive elicitation strategies have been proposed allowing a fast reduction of the space of possible parameters until it becomes sufficiently small to be able to determine the optimal choice without ambiguity. For example, this is the case of incremental elicitation methods based on the minimization of the maximum regret proposed in [Wang and Boutilier, 2003; Boutilier et al., 2006; Benabbou and Perny, 2015; Benabbou et al., 2017]. Preference queries are generated to reduce the imprecision of parameters and the regrets attached to the possible decisions. The responses are translated into hard constraints limiting the space of admissible parameters and allowing sharper preferences to be derived. No opportunity is nevertheless given to the DM to contradict herself. In these approaches relying on a progressive and backtrack-free reduction of the uncertainty set, the efficiency comes at the cost of a relative lack of robustness in recommendation tasks, as illustrated by the following example. Example 1 We consider a set A of alternatives in a bicriteria decision problem containing 101 elements characterized by their performance vectors ai = (i, 100 - i), i = 0, . . . , 100. We assume here that the DM's preferences can be represented by an ordered weighted average (OWA) of the form: uw(ai ) = wmin{ai1 , ai2 }+(1 - w)max{ai1 , ai2 } with w = 0.6. Hence, u0.6(ai ) = 40+0.2i, ∀i ∈ J0, 50K and u0.6(ai ) = 60-0.2i, ∀i ∈ J51, 100K and the u0.6-optimal solution is a50 = (50, 50) with utility 50. We remark here the interest of OWA aggregation that selects the better balanced vector in A. Such a selection could not be performed with a linear model. Assume now that w is unknown and must be elicited. Hence the set of possible values for w is W =[0, 1]. Assume that the DM first declares that ak is at least as good as ai for some i < k ≤ 50. From uw(ak ) ≥ uw(ai ) we obtain w≥0.5 and therefore W =[1/2, 1]. After this reduction, the optimal solution in A is necessarily a50 . We indeed have uw(a50 )-uw(ak )=(50 - k)(2w - 1)≥0 for all k∈J0, 50K and w∈ [1/2, 1], and uw(a50 ) - uw(ak )=50 - 100w+i≥0 for all k∈J51, 100K and w∈[1/2, 1]. If the DM answers that ai is strictly better than ak for some i < k ≤ 50, a similar treatment would lead to conclude that W =[0, 1/2) and that a0 and a100 are necessarily optimal in A. In both cases, an optimum is found after one preference query. This example shows the efficiency of incremental preference elicitation in a simple case of bi-criteria decision making using an OWA. The optimal choice can be determined while the uncertainty about criteria weights remains very large. This example also illustrates the high sensitivity of the method to possible errors made by the DM in expressing her preferences. If the DMunfortunately declares that she strictly prefers ai to ak for some i < k ≤ 50 while its utility function is u0.6, we may recommend a0 which is actually the worst option. This lack of robustness is due to definitive reductions of the uncertainty set W resulting from hard constraints derived from the observed preferences at every step. In case of a wrong answer, the uncertainty set will definitely exclude the correct value of the hidden parameters and reduce the relevance of recommendations. In this paper we keep unchanged the uncertainty set, and maintain a probability density function over it. The distribution is updated in a Bayesian manner. ## 2 Preliminaries ## 2.1 Rank-dependent Aggregation Functions Let A be the set of alternatives that need to be compared in order to make a decision. Any alternative a ∈ A is evaluated with respect to a set of p criteria denoted by C = {1, . . . , p}, and is characterized by a performance vector a = (a1, . . . , ap), where ai ∈ [0, 1] represents the utility of a with respect to criterion i. All utilities ai are expressed on the same scale; the utility functions must be defined from the input data (criterion or attribute values), as proposed by, e.g., Grabisch and Labreuche [2010]. From now on, for simplicity, we will consider the image of A in the criteria space, denoted by abuse of notation A={a1 , . . . , an}, and indifferently use the terms "alternative" and "performance vector". A standard way to model preferences between performance vectors consists in using an aggregation function that maps vectors to scalar values. The function is called rankdependent if the vector is sorted in nondecreasing order before being mapped into a scalar value. This enables to assign weighting coefficients to components of the performance vector according to their ranks. Given a vector a, we denote by (·) a permutation on C such that a(1)≤. . .≤a(p). We will consider two families of rank-dependent aggregation functions, namely ordered weighted averages (OWA) and Choquet integrals. These aggregation functions are known to be monotonic with respect to weak Pareto dominance (a weakly dominates b if ai ≥ bi for i∈{1, . . . , p}). ## Ordered Weighted Averages This family of aggregation functions has been introduced by Yager (1988). Let λ = (λ1, . . . , λp) be a weighting vector (∑pi=1 λi = 1 and λi ≥ 0 ∀i). The OWA defined by λ reads: Note that the OWA aggregator includes the min, the max and the arithmetic mean as special cases. The OWA function is concave if λ1 ≥ . . . ≥ λp. The subclass of concave OWA functions is of particular interest in fair optimization because OWA((a1, . . . , ai-ε, . . . , aj+ε, . . . , ap))≥OWA(a) for all i, j, ε such that ai-aj ≥ε>0. It thus favors well-balanced performances. While instances of OWA range from the min (λ1 = 1 and λi = 0 ∀i > 0) to the max (λp = 1 and λi = 0 ∀i < p) depending on the weights, instances of concave OWA range from the min to the arithmetic mean (λi =1/p ∀i). Example 2 Let a = (0.3, 0.5, 0.8) and b = (0.5, 0.6, 0.4). For λ = (0.5, 0.3, 0.2), we have OWAλ(a) = 0.46 < 0.47 = OWAλ(b), thus b is preferred to a. ## Choquet Integrals The Choquet integral [Schmeidler, 1986; Grabisch et al., 2009] is an aggregation function that generalizes the notion of average, by defining a capacity on the criteria set. A capacity is a set function from 2C to R such that v(∅) = 0, v(C)=1 and v(X)≤v(Y ) for all X⊆Y ⊆C. In multicriteria analysis, v(X) represents the weight attached to coalition X, for any X ⊆ C. The Choquet integral defined by v reads: where A(i) = {(i), . . . , (p)} (i.e., the criteria whose performance is greater or equal to a(i)), v(A(p+1))=0 and a(0)=0. Note that the Choquet integral includes the weighted sum as a special case: if v is additive, i.e., v(X) = ∑i∈X λi for some positive coefficients λi, then Equation 2 leads to Cv(a) = ∑i λiai. The Choquet integral also includes the OWA function as special case. Indeed, if we use a symmetric capacity v in Equation 2, i.e., v(X) only depends on |X|, then λi =v(A(i))-v(A(i+1)) only depends on i and not on the elements in A(i) and A(i+1), thus we recognize an OWA. Example 3 Let us come back to Example 2. Consider the capacity v defined by v(∅) = 0, v(C) = 1 and: | X | {1} {2} | {3} | {1, 2} | {1, 3} | {2, 3} | |------|-----------|---------|----------|----------|----------| | v(X) | 0.1 | 0.2 0.3 | 0.5 | 0.5 | 0.6 | The evaluations of a and b using Equation 3 are: We now recall a useful representation of capacities in terms of M¨obius inverse. The M¨obius inverse of a capacity v is a mapping mv : 2C → R defined by mv(X) = ∑Y⊆X (-1)|X\Y | v(Y ) ∀X ⊆ C. The quantity mv(X) is called the M¨obius mass of X. The capacity can be derived from its M¨obius inverse as follows: ∀X ⊆ C, v(X) = ∑Y⊆X mv(X). The M¨obius inverse yields an alternative formulation of the Choquet integral: A capacity v is said to be k-additive if mv(X) = 0 for all X⊆C such that |X|>k and there exists at least one subset X such that |X|=k andmv(X)>0. For instance, the capacity v considered in Example 3 is at most 2-additive because: m({1, 2, 3})=v({1, 2, 3})-∑i̸=j v({i, j})+∑i v({i})=0. The main interest of Choquet integrals for multicriteria decision making stems from the fact that they can represent interaction between criteria [Grabisch and Labreuche, 2010], as can be witnessed by the M¨obius masses. For instance, by definition, mv({i, j}) = v({i, j})-v({i})-v({j}). There is a positive interaction between i and j if mv({i, j}) > 0, and negative if mv({i, j}) < 0. The k-additive capacities for small values of k greater than 1 are very useful because in practical situations, they offer a sufficient expressivity to model positive or negative synergies between criteria with a reduced number of parameters. For example, when k = 2 the capacity is completely characterized by (p2 +p)/2 coefficients (one M¨obius mass for every singleton and every pair). The aggregation functions introduced above are intended to be used to describe the preferences of the DM, thus their parameters (i.e., the weighting vector or the capacity) must be inferred from preference statements provided by the DM. ## 2.2 RelatedWorks Regarding the Bayesian incremental elicitation of an aggregation function from pairwise preference queries, the previous works in the literature can be divided in two categories: nonparametric approaches and parametric approaches. Following a nonparametric approach, Chu and Ghahramani [2005] proposed to use Gaussian Processes (GP) for preference learning. To approximate any possible aggregation function, the idea is to assume that each overall utility value follows a normal distribution. The joint distribution defines a GP. This distribution is characterized by a mean function and a covariance matrix, and can be seen as an infinitedimensional extension of a multivariate Gaussian distribution (the domain of the aggregation function can indeed be infinite). The covariance matrix is used to ensure that alternatives with similar performance vectors yield similar overall utility values. Building on this work, Brochu et al. [2007] proposed an active learning procedure that does not require to accurately model the entire aggregation function to determine an optimal alternative. Their approach is based on pairwise comparison queries. Zintgraf et al. [2018] recently extended it to other query types, like asking the user to rank or cluster alternatives. In this paper, we investigate a parametric approach where one imposes a rank-dependent aggregation function to ensure appealing normative properties. A parametric approach consists indeed in learning the parameters of a given aggregation function. This kind of approaches was well introduced and illustrated in [Chajewska et al., 2000] for the adaptive elicitation of utility values over a finite set of outcomes in decision making under uncertainty. While their approach used standard gamble queries (pairwise preference queries between probability distributions over outcomes), Guo and Sanner [2010] proposed a variant that only requires the users to state their preference under certainty, so as to reduce the cognitive load. Recently, for the adaptive elicitation of the parameters of a multiattribute utility function, Saur´e and Vielma [2018] proposed an approach that updates an ellipsoidal credibility region computed from a multivariate normal distribution over the space of parameters, and showed how to use mixed integer programming to determine queries that are likely to reduce the volume of the credibility region. Nonetheless, none of these works is concerned with learning the parameters of a rank-dependent aggregation function, which is the aim of the present paper. Most of the works aiming at determining the parameters of rank-dependent aggregation functions consider a static preference database as input, and focus on the determination of parameter values that best fit the available preferences. For learning the parameters of a Choquet integral, Marichal and Roubens [2000] presented a linear programming formulation, Tehrani et al. [2012] proposed a generalization of logistic regression, and Rowley et al. [2015] used a principal component analysis. Departing from these works, incremental elicitation procedures have recently been proposed [Benabbou et al., 2017; Bourdache and Perny, 2019], but they assume no response-error. Yet, as illustrated in Example 1, the recommendation made can be severely impacted by errors in responses. To overcome this drawback, we introduce in the next section some useful linear and compact reformulations of OWA and Choquet aggregators in new multidimensional spaces, that makes it possible to implement Bayesian linear regression techniques with rank-dependent models. ## 3 Basis Functions for OWA and Choquet A way to extend Bayesian linear regression to a nonlinear function f is to reformulate f as a linear combination of (nonlinear) basis functions g1, . . . , gq [Bishop, 2006]. Formally: where w=(w1, . . . ,wq)T is a weighting vector and g(a)= (g1(a), . . . , gq(a))T . Thus, f is a linear function in the space of features g1, . . . , gq. We now introduce suitable basis functions for the rank-dependent aggregators studied here. ## Ordered Weighted Averages Obviously, any OWA function is a linear combination of functions gi(a)=a(i) for i =1, . . . , p (see Equation 1). Given a weighting vector λ for OWA, the corresponding parameters for the basis functions are wi =λi for i = 1, . . . , p. For the OWA function to be nondecreasing in every component, we impose wi ≥ 0 for i = 1, . . . , p. ## Concave Ordered Weighted Averages In the context of fair optimization, the constraint w1 ≥. . .≥ wp is required to favor solutions having balanced profile [Weymark, 1981], which makes the linearization more tricky. In this case we get a concave OWA function. To overcome the problem, we shall use cumulative functions defined by gi(a) = ∑ik=1 a(k). It can easily be checked that: where wi =λi-λi+1 for i<p and wp =λp. Conversely, given parameters wk, the corresponding weights for OWA are λi = ∑pk=i wk. Note that to enforce constraint λ1 ≥. . .≥λp ≥0, we only have to impose wi ≥ 0 for i = 1, . . . , p. Example 4 For λ = (0.5, 0.3, 0.2) (as in Example 2), the expression OWAλ(a) reformulates as 0.2g1(a)+0.1g2(a) + 0.2g3(a). If a=(0.3, 0.5, 0.8), we have g(a)=(0.3, 0.8, 1.6) and OWAλ(a)=0.2×0.3+0.1×0.8+0.2×1.6=0.46. ## 2-additive Choquet Integrals To express a Choquet integral as a linear combination of basis functions, we consider a decomposition of v under the form v=∑qi=1 wivi, where vi's are basis capacity functions. Indeed, if v=∑qi=1 wivi, then Cv(a)=∑qi=1 wiCvi (a) because Cv is linear in v. For the class of at most 2-additive capacities, a decomposition of v with q = p2 basis functions is known. This class can be characterized by a polytope, the extreme points of which are defined by two families of 0-1 capacities: - the unanimity games for singletons and pairs defined by where Yi ⊆ C is any nonempty subset of size at most 2; - the conjugates of unanimity games for pairs defined by This characterization of extreme points directly follows from [Grabisch, 2016, Theorem 2.65, p.89]. Hence, for any at most 2-additive capacity, there exists p2 coefficients wi≥0 adding up to 1 such that Cv(a)= ∑i wiCvi (a). Note that a similar result, formulated in terms of M¨obius inverse, has also been used in [H¨ullermeier and Tehrani, 2013]. Example 5 Any capacity v on three criteria can be written as a convex combination of vi's in the table below (the unanimity games are v1, . . . , v6, the conjugates are v7, v8, v9). | X | {1} | {2} | {3} | {1, 2} | {1, 3} | {2, 3} | |-------|-------|-------|-------|----------|----------|----------| | v1(X) | 1 | 0 | 0 | 1 | 1 | 0 | | v2(X) | 0 | 1 | 0 | 1 | 0 | 1 | | v3(X) | 0 | 0 | 1 | 0 | 1 | 1 | | v4(X) | 0 | 0 | 0 | 1 | 0 | 0 | | v5(X) | 0 | 0 | 0 | 0 | 1 | 0 | | v6(X) | 0 | 0 | 0 | 0 | 0 | 1 | | v7(X) | 1 | 1 | 0 | 1 | 1 | 1 | | v8(X) | 1 | 0 | 1 | 1 | 1 | 1 | | v9(X) | 0 | 1 | 1 | 1 | 1 | 1 | For a = (0.3, 0.5, 0.8), we have Cv1 (a) = 0.3, Cv2 (a) = 0.5, Cv3 (a) = 0.8, Cv4 (a) = 0.3, Cv5 (a) = 0.3, Cv6 (a) = 0.5, Cv7 (a)=0.5, Cv8 (a)=0.8, Cv9 (a)=0.8. Besides, v=0.1v2 +0.3v3+0.3v4+0.1v5+0.1v6+0.1v7, thus Cv(a)=0.51. ## 4 Incremental Elicitation Process We now introduce an incremental Bayesian elicitation procedure taking advantage of the above linear reformulations. We consider a non-linear aggregation function admitting a linear representation fw(a)=wT g(a), where values gi(a) are computed as shown in Section 3. Incremental decision making consists in implementing an adaptive elicitation procedure based on fw to iteratively collect preference statements so as to reduce the uncertainty about w until an alternative can be recommended with sufficient confidence. We propose a Bayesian approach where a prior density function over the parameter space is iteratively updated with new preference statements. The incremental decision process is based on the progressive minimization of expected regrets attached to possible decisions. The expected regrets are defined as follows. Definition 1 Given a density function p on the possible values of w, the pairwise expected regret of an alternative a with respect to an alternative b is defined as follows: In other words, the pairwise expected regret of a with respect to b represents the expected utility loss when recommending a instead of b. Definition 2 Given a set A of alternatives and a density function p on the possible values of w, the max expected regret of a ∈ A and the minimax expected regret are defined by: In other words, the max expected regret 1 of a is the maximum expected utility loss incurred in selecting a in A. ## Incremental Elicitation We denote by a(k) an alternative achieving the MMER(A, p) value at iteration k. This alternative is worth recommending if no further preferential information can be obtained because it minimizes the expect opportunity loss. Otherwise, we ask the DM to compare a(k) and any adversarial choice b(k) in argmaxb∈APER(a(k) , b, p), as suggested by Boutilier et al. (2006) in the context of max regret minimization (current solution strategy). The DM's answer allows us to update the current distribution p for the next iteration. This process can be iterated until the MMER value drops below a given acceptance threshold δ. The resulting incremental decision procedure is more formally described in Algorithm 1. ## Algorithm 1 Incremental decision making ``` Input: A: alternatives; δ: threshold; p(w): density function. Output: a∗ : best recommendation in A. 1 i ← 1; 2 repeat 3 a(i) ← argmina∈AMER(a,A, p) 4 b(i) ← argmaxb∈APER(a(i) , b, p) 5 Ask the DM if a(i) is preferred to b(i) 6 y(i) ← 1 if the answer is yes and 0 otherwise 7 p(w) ←p(w|y(i) ) ∀w (see Algorithm 2) 8 i ← i + 1 9 until MMER(A, p) ≤ δ 10 return a∗ selected in argmina∈AMER(a,A, p) ``` ## Bayesian Inference In Line 7, the density function p(w) is updated using the latent variable approach introduced by Albert and Chib (1993) for binary probit regression. Let y(i) represent the answer to a comparison query i between a(i) and b(i) , with y(i) =1 if a(i) is preferred, y(i) =0 otherwise. In our setting, the probit model is used to predict the value of y(i) based on the vector d(i) =g(a(i) )-g(b(i) ) of explanatory variables. The answer y(i) is assumed to depend on a latent variable z(i) representing preference intensity and defined by: where ε(i) ∼N(0, 1) is a Gaussian noise accounting for possible errors in the answers and for descriptive limitations of the preference model. If z(i) ≥0, then y(i) =1, else y(i) =0. Following the sequential Bayesian approach of Algorithm 1, a prior density function p(w) is defined on the parameter space. In the probit model, p(w) is multivariate Gaussian. After each query, the current density function p(w) 1 Note that there exists similar definitions of expected regrets in the literature (see, e.g., Guo and Sanner [2010]). is revised according to answer y(i) . The main interest of resorting to the probit model is to obtain a computationally efficient procedure to estimate the posterior p(w|y(i) ). The revised density function p(w|y(i) ) can indeed be formulated as a marginal density of p(w, z|y(i) ): However, p(z|y(i) ) depends, in turn, on p(w|y(i) ) because: We use an iterative method to approximate the density function p(w|y(i) ) that solves the fixed point equation obtained by replacing p(z|y(i) ) by (6) in Equation (5), as suggested by Tanner and Wong (1987). They proved that it should converge to the true posterior p(w|y(i) ). The method is detailed in Algorithm 2, where the upper bound K on the number of iterations depends on the compromise sought between speed and accuracy. At each iteration k, an approximation pk(w) of p(w|y(i) ) is refined. The for loop in Line 3 aims at sampling m values z1, . . . , zm from p(z|y(i) ). The density function p(z|ω, y(i) ) used in line 5 is truncated Gaussian: From sampled values zj, a tighter approximation pk+1(w) is computed in Line 6. Note that 1m ∑mj=1 pk(w|zj) is multivariate Gaussian because each pk(w|zj ) is multivariate Gaussian. It is indeed well-known (see e.g. Bishop, 2006) that if pk(w)=N(µk, Sk), then pk(w|zj)=N(µj , S) where: Coming back to the interpretation of w as weights in a linear reformulation fw, the conditions ∑i λi = 1 (for OWA) and v(C) = 1 (for Choquet) turn into normalisation constraints ∑i i·wi =1 (for concave OWA) and ∑i wi =1 (for general OWA and Choquet). As functions fw are linear in w (thus the induced preferences are invariant by rescaling of w), the normalisation constraints can be dropped, which considerably simplifies the sampling. In the calculation of regrets in Algorithm 1, we use nonetheless normalised weights to compare regrets from one iteration to another. Besides, we use a truncated normal density function p(w) to ensure wi ≥0 ∀i. ## Algorithm 2 Approximating density function p(w|y(i) ) ``` Input: p(w): density function; m: sample size; K: #iterations. Output: p(w|y(i) ): posterior density function. 1 k ← 0; p0(w)←p(w) ∀w 2 repeat /* pk(w) approximates p(w|y(i) ) */ 3 for j=1 to m do 4 draw ω from pk(w) 5 draw zj from p(z|ω, y(i) ) 6 pk+1(w) ← 1m ∑mj=1 pk(w|zj) ∀w 7 k ← k + 1 8 until pk stabilizes or k=K 9 return pk ``` ## 5 Numerical Tests Before coming to the results of numerical tests 2 we conducted on randomly generated instances to evaluate the behavior of Algorithm 1, we illustrate this behavior on Example 1. Example 1 (continued). Assume that Algorithm 1 is launched with an acceptance threshold δ = 0.02. We first obtain MMER=0.05>δ. The DM is then asked to compare a24 and a50 (this is not necessarily a50 , it may be a close neighbor depending on the sample drawn for w). Assume that the DM makes a mistake and declares that she prefers a24 to a50 . Using this information the probability density function over weights is revised and MMER is recomputed. Now, MMER = 0.04 > δ so a second query is generated. The DM compares a11 and a50 and correctly declares that she prefers a50 . We obtain MMER = 0.05 > δ, and afterwards four additional queries are needed to conclude. The DM is asked to compare a28 , a34 , a43 and a46 to a0 respectively and the DM never chooses a0 . After the six answers, we obtain MMER = 0.01 < δ and the algorithm stops recommending arg mina∈A MER(a, A, p) = a47 , which is very close to the actual optimal solution a50 . We thus observe that a47 is now recommended while a0 or a100 was recommended using a deterministic approach with the same wrong initial answer. For the hidden utility u0.6 of the DM, we have u0.6(a50 )=40+0.2×50=50 and u0.6(a47 )=40+0.2×47=49.4. The actual regret in recommending a47 instead of a50 is therefore 50-49.4=0.6, which represents 1.2% of the utility value of an optimal alternative. ## Random Generation of Instances We generate instances with 5 criteria and 100 Pareto optimal alternatives. Every alternative a in each generated set A is drawn as follows: a first vector v of size p - 1 is uniformly drawn in [0, 1]p-1 , then a is obtained by setting ai=v(i)-v(i-1) for i=1, . . . , p, where v(0)=0 and v(p)=1. To avoid that all generated alternatives share the same hyperplane ∑i ai =1 in the utility space, we apply the square root function on all components ai of each performance vector a ∈ A. Finally, for each instance, a hidden weight vector w is uniformly drawn over the simplex. For the elicitation of OWA parameters, the prior is set to N((10, . . . , 10), 100I), where I is the identity matrix. For Choquet parameters, the prior is set to N(µ, 100I), where µi =10 if |Yi| = 1 and µi =0 otherwise (we recall that Cv(a) = ∑i wiCvi (a), where each vi is attached to a subset Yi of size at most 2). In this way, the prior density function is centered around a parameter vector for which there is no interaction between criteria. ## Simulation of the Interactions with the DM To simulate the DM's answers, we use the model given in Equation 4 with ε(i) ∼N(0, σ2 ) for σ∈{0, 0.1, 0.2}, in order to test the tolerance of the approach to wrong answers (none for σ=0). Setting σ=0.1 (resp. 0.2) led to 19% (resp. 26%) of wrong answers on the considered runs of the algorithm for OWA, and 10% (resp. 17%) for 2-additive Choquet. 2 Implementation in Python using the tmvtnorm R's library to draw vectors according to multivariate truncated normal densities, running on an Intel(R) Core(TM) i7-4790 CPU with 15GB of RAM. Figure 1: Mean MMER value (OWA) ![Image](https://ijcai.org/proceedings/2019/fulltext/280/image_000000_38ea23a6d6b8129911bf11fc21703079999824f4cebdf7f981d1f19694b51365.png) Figure 2: Mean rank of the recommendation (OWA) ![Image](https://ijcai.org/proceedings/2019/fulltext/280/image_000001_93a5a2f5b62a31a926b64e03d4c6607722b2d9f6ca70b088ed6b385a06849db7.png) Figure 3: Rank of the recommendation (OWA) ![Image](https://ijcai.org/proceedings/2019/fulltext/280/image_000002_4af9a8cca39500cfccbd31e1cac4be60c278b3b0b0631bde8d2fbf9daf0cbe8b.png) Figure 4: Mean rank of the recommendation (Choquet) ![Image](https://ijcai.org/proceedings/2019/fulltext/280/image_000003_1e98963894368e8f278a34357942b9e05fe34f5c31560f655f4fd04514c59413.png) ## Analysis of the Results We evaluated the efficiency of Algorithm 1 with respect to the value of σ (results averaged over 50 instances). We first observed the evolution of the MMER value in the course of Algorithm 1, in percentage of the initial MMER value (the curves for OWA and 2-additive Choquet are very similar, thus only the former are provided), as well as the evolution of the actual rank in A of the current MMER alternative according to the hidden DM preference model. The obtained curves for OWA and at most 2-additive Choquet integrals are represented in Figure 1, 2 and 4. We observe that the mean MMER value drops below 3% of the initial MMER value in a dozen queries. The value of σ mainly impacts the quality of the recommendation, measured by the rank of the recommended alternative in the hidden ranking of the DM, that deteriorates when the value of σ increases. Nevertheless, the average rank of the recommended alternative is never beyond 5 (over 100 alternatives), except for OWA with σ=0.2 where it is around 6.5. Regarding the computation times between two queries, it takes about 5 seconds for OWA, and about 35 seconds for 2-additive Choquet. This difference can be explained by the respective sizes of parameter spaces. We next compared the performance of Algorithm 1 to a deterministic approach based on the minimization of the max regret, that reduces the parameter space after each query instead of updating a probability density function (see e.g., [Bourdache and Perny, 2019]). For both methods, we considered two performance criteria: the number of queries for making a recommendation, and the quality of the recommendation itself, measured in terms of actual rank of the recommended solution at termination. Regarding the number of queries, as can be seen in Figure 2 and 4, the quality of the recommendation does not significantly improve after a dozen query, which is similar to the number of queries in the deterministic approach. Regarding the quality of the recommendation, the histogram in Figure 3 shows the distribution of the ranks of the recommendations over the 50 randomly generated instances, for OWA with σ=0.2. The Bayesian approach recommends the best alternative in 50% of cases while it happens in 36% of cases for the deterministic approach. ## 6 Conclusion Our work differentiates from previous works on incremental decision making with OWA and Choquet integrals in proposing a probabilistic approach that is tolerant to response-errors of the DM. It also differentiates from previous work on active preference learning with Bayesian methods in implementing an approach that applies to well-known rank-dependent decision criteria. Our contribution on the Choquet integral concerns the case of 2-additive capacities, that are known to provide sufficient flexibility to model very diverse preference systems including positive and negative interactions between criteria. However, it would be interesting to extend our approach to elicit larger classes of capacities to make even better use of the descriptive possibilities offered by the Choquet integral. This is a challenging problem because the polytope of at most k-additive capacities for k>2 admits many other extreme points than 0-1 capacities [Miranda et al., 2006]. ## References 1. [Albert and Chib, 1993] James H Albert and Siddhartha Chib. Bayesian analysis of binary and polychotomous re- sponse data. J. Am. Stat. Assoc., 88(422):669-679, 1993. 2. [Benabbou and Perny, 2015] Nawal Benabbou and Patrice Perny. Incremental weight elicitation for multiobjective state space search. In AAAI-15, pages 1093-1099, 2015. 3. [Benabbou et al., 2017] Nawal Benabbou, Patrice Perny, and Paolo Viappiani. Incremental elicitation of Choquet ca- pacities for multicriteria choice, ranking and sorting prob- lems. Artificial Intelligence, 246:152-180, 2017. 4. [Bishop, 2006] Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. 5. [Blythe, 2002] Jim Blythe. Visual exploration and incremen- tal utility elicitation. In AAAI-02, pages 526-532, 2002. 6. [Bourdache and Perny, 2019] Nadjet Bourdache and Patrice Perny. Active preference elicitation based on generalized gini functions: Application to the multiagent knapsack problem. In AAAI 2019, 2019. 7. [Boutilier et al., 2006] Craig Boutilier, Relu Patrascu, Pas- cal Poupart, and Dale Schuurmans. Constraint-based opti- mization and utility elicitation using the minimax decision criterion. Artificial Intelligence, 170(8-9):686-713, 2006. 8. [Braziunas and Boutilier, 2007] Darius Braziunas and Craig Boutilier. Minimax regret based elicitation of generalized additive utilities. In Proc. of UAI-07, pages 25-32, 2007. 9. [Brochu et al., 2007] Eric Brochu, Nando D Freitas, and Ab- hijeet Ghosh. Active preference learning with discrete choice data. In NIPS 2007, pages 409-416, 2007. 10. [Chajewska et al., 2000] Urszula Chajewska, Daphne Koller, and Ronald Parr. Making rational decisions using adaptive utility elicitation. In Proceedings of AAAI-00, pages 363-369, 2000. 11. [Chu and Ghahramani, 2005] Wei Chu and Zoubin Ghahra- mani. Preference learning with gaussian processes. In ICML-05, pages 137-144, 2005. 12. [Grabisch and Labreuche, 2010] Michel Grabisch and Christophe Labreuche. A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid. Annals of OR, 175(1):247-286, 2010. 13. [Grabisch et al., 2009] Michel Grabisch, Jean-Luc Marichal, Radko Mesiar, and Endre Pap. Aggregation Functions. Camb. U. Press, 2009. 14. [Grabisch, 2016] Michel Grabisch. Set functions, games and capacities in decision making, volume 46. Springer, 2016. 15. [Guo and Sanner, 2010] Shengbo Guo and Scott Sanner. Multiattribute bayesian preference elicitation with pair- wise comparison queries. In NIPS, pages 396-403, 2010. 16. [Ha and Haddawy, 1997] Vu Ha and Peter Haddawy. Problem-focused incremental elicitation of multi-attribute utility models. In Proc. of UAI-97, pages 215-222, 1997. 17. [Hüllermeier and Tehrani, 2013] Eyke Hüllermeier and Ali Fallah Tehrani. Efficient learning of classifiers based on the 2-additive Choquet integral. In Comp. Intelligence in Intelligent Data Analysis, pages 17-29. Springer, 2013. 18. [Marichal and Roubens, 2000] Jean-Luc Marichal and Marc Roubens. Determination of weights of interacting criteria from a reference set. European Journal of Operational Research, 124(3):641-650, 2000. 19. [Miranda et al., 2006] Pedro Miranda, Elías F. Combarro, and Pedro Gil. Extreme points of some families of non- additive measures. European Journal of Operational Re- search, 174(3):1865-1884, 2006. 20. [Rowley et al., 2015] Hazel V Rowley, Arne Geschke, and Manfred Lenzen. A practical approach for estimating weights of interacting criteria from profile sets. Fuzzy Sets and Systems, 272:70-88, 2015. 21. [Sauré and Vielma, 2018] Denis Sauré and Juan Pablo Vielma. Ellipsoidal methods for adaptive choice-based conjoint analysis. Operations Research, 2018. 22. [Schmeidler, 1986] David Schmeidler. Integral representa- tion without additivity. Proceedings of the American math- ematical society, 97(2):255-261, 1986. 23. [Tanner and Wong, 1987] Martin A Tanner and Wing Hung Wong. The calculation of posterior distributions by data augmentation. J. Am. Stat. Asso., 82(398):528-540, 1987. 24. [Tehrani et al., 2012] Ali Fallah Tehrani, Weiwei Cheng, Krzysztof Dembczynski, and Eyke Hüllermeier. Learn- ing monotone nonlinear models using the Choquet inte- gral. Machine Learning, 89(1-2):183-211, 2012. 25. [Wang and Boutilier, 2003] Tianhan Wang and Craig Boutilier. Incremental utility elicitation with the minimax regret decision criterion. In IJCAI-03, pages 309-318, 2003. 26. [Weymark, 1981] John A Weymark. Generalized gini in- equality indices. Mathematical Social Sciences, 1(4):409- 430, 1981. 27. [Yager, 1988] Ronald R Yager. On ordered weighted aver- aging aggregation operators in multicriteria decisionmak- ing. IEEE Transactions on Systems, Man, and Cybernet- ics, 18(1):183-190, 1988. 28. [Zintgraf et al., 2018] Luisa M Zintgraf, Diederik M Roi- jers, Sjoerd Linders, Catholijn M Jonker, and Ann Nowé. Ordered preference elicitation strategies for supporting multi-objective decision making. In Proceedings of AAMAS-18, pages 1477-1485, 2018.