Incremental Preference Elicitation with Bipolar Choquet Integrals

Abstract

Preference modeling and preference learning are crucial issues in multicriteria decision-making to formulate recommendations that are tailored to the Decision Maker. In the field of multicriteria analysis, various aggregation functions have been studied to scalarize performance vectors and compare solutions. Nonetheless, most of these models do not take into account the presence of reference points in the criteria scales. Since it has been observed that decision makers may exhibit different attitudes towards aggregation depending on whether evaluations are above or below reference values, we consider here bipolar extensions of well-known aggregation models and propose incremental preference elicitation methods based on these models. In particular, we consider the elicitation of a 2-additive bipolar Choquet Integral, of a bipolar Weighted Ordered Weighted Average (WOWA), and of a non-weighted bipolar OWA. We propose a general approach that is implemented in all these cases and provide numerical tests showing its practical efficiency.

1 Introduction

In the field of multicriteria decision support, various decision models have been proposed to determine the optimal choice within the set of Pareto optimal solutions. The most common approach is to define an overall utility value from any performance vector using an aggregation function synthesizing the advantages and weaknesses of the solution considered. This aggregation function is often parameterized by weighting coefficients allowing to control the relative importance of criteria and possibly their interaction in the aggregation. These parameters must be taylored to the value system of the Decision Maker (DM) to make personalized recommendations.

There are many contributions on preference elicitation in the recent literature, proposing to assess the parameters of a decision model. A first stream of research concerns complete elicitation methods aiming to the determination of precise weighting parameters. This approach requires much preference information from the DM but has the advantage to allow the construction of a fully specified decision model that can be used to derive personalized recommendations or predicting choices of the DM in any set of alternatives. Another approach, quite popular in the last decade, is to perform an incremental and adaptive elicitation of preferences. The goal is a bit less ambitious here, it is to obtain a sufficient amount of preference information to be able find the preferred option in a given set of alternatives. This second approach significantly reduces the elicitation burden.

Various incremental elicitation methods have been proposed in the literature. While some of them manage a probability distribution over the set of parameters and use Bayesian revisions to progressively pass from a prior distribution representing ignorance to a more specific distribution concentrated on a subregion of the parameter space (see e.g., [6]), some others proceed by a progressive reduction of the parameter space until the optimal choice can be identified without ambiguity [5, 14, 26, 28]. Both approaches are interesting but we will focus in this paper on the latter approach. In the field of multicriteria decision making, this approach is generally implemented by maintaining a set of possible parameter vectors (named the uncertainty set hereafter) defined as a convex polyedron that is progressively reduced as new (linear) constraints appear from new preference statements. This approach obviously applies to weighted sums, but more generally to any scalarizing function linear in its parameter. Assume indeed that the overall utility of any performance vector $x=(x_1, \ldots , x_n)$ is defined by $f_w(x_1, \ldots , x_n)$ where $f_w: \mathbb {R}^n \rightarrow \mathbb {R}$ is a scalarizing function parameterized by w and linear in w, then any preference statement of type “x is as least as good as y” for any two vectors x and y translates into the constraint $f_w(x) \ge f_w(y)$ which is linear in w.

This approach based on uncertainty sets defined as convex polyedra is not restricted to weighted sums. For instance it can also be applied to rank-dependent aggregation functions such as Ordered Weighted Averages (OWA) [29] and Choquet integrals [13] as shown in [2, 3]. In this paper we consider more general rank-dependent decision models recently introduced in multicriteria analysis for preference aggregation with bipolar preferences, in particular biOWA [16] and biChoquet integrals [13, 17]. The motivation for this is twofold:

• it has been observed in different contexts that DMs tend to think of outcomes relative to a certain reference point and may exhibit different attitudes towards positive evaluations (i.e. , evaluations above the reference point) and negative evaluations (i.e., evaluations below the reference point) see, e.g., [25]). The biOWA aggregator and more generally any biChoquet integral allow to model such decision behaviors and their parameters must be elicited.

• the descriptive power of bipolar models comes at a cost: bipolarity requires using more weighting parameters to keep the possibility to model different attitudes in the aggregation, depending on whether we are in the positive side or in the negative side of the evaluation space. Therefore the elicitation process is more demanding in terms of preference information and there is a need of testing the practical feasibility of incremental elicitation methods on such models.

The aim of this paper is to propose a preference elicitation method based on the biChoquet integral for multicriteria evaluation with bipolar scales. Our approach is to progressively specify the two capacities used in the model by an iterative reduction of their uncertainty sets using preference queries. We will implement this approach on the general biChoquet model and also on specific subclasses, for interactive decision support on explicit sets. The paper is organized as follows: Sect. 2 introduces some background on biChoquet integrals and on regret-based incremental elicitation methods. Section 3 introduces an incremental elicitation algorithm for the case of 2-additive biChoquet integrals. We then propose an adaptation of our elicitation algorithm to the case of bipolar weighted ordered weighted averages (biWOWA, Sect. 4), which is then further specialized in the case of bipolar weighted ordered averages (biOWA, Sect. 5). In all cases, we provide the results of numerical tests to show their performance both in terms of computation time and number of generated preference queries.

2 Background

2.1 Choquet and BiChoquet Integrals

Let $N =\{1, \ldots , n\}$ denote the set of criteria under consideration to assess the performance of a solution in the decision problem. We assume that any feasible solution is characterized by a performance vector $x=(x_1, \ldots , x_n)$ where $x_i$ represents the value of x w.r.t. the $i^{th}$ criterion. In order to model the preferences of the DM we consider here the Choquet integral which is a widely-used model in decision theory [9, 21] with various applications in multicriteria decision making [7, 10, 15, 23] and AI [1, 3, 8, 22].

The Choquet integral is a kind of weighted aggregation operator where weights are not only assigned to every criteria but also to groups of criteria. This enables to model positive or negative interactions among criteria, giving enhanced descriptive possibilities compared to linear models. The weights are defined using a set function named capacity and defined as follows;

Definition 1

A capacity on N is a set function $v: 2^N \rightarrow [0,1]$ such that $v(\emptyset ) = 0$ and for all $A, B \subseteq N, A \subseteq B \Rightarrow v(A) \le v(B)$.

Throughout the paper we will always assume that the capacities under consideration are normalized, i.e., $v(N) = 1$. Then the Choquet integral can be defined from any capacity as follows:

Definition 2

For any vector $x =(x_1, \ldots , x_n) \in \mathbb {R}^n$, the Choquet integral w.r.t. capacity v is a scalarizing function $C_v : \mathbb {R}^n \rightarrow \mathbb {R}$ defined by:

$$\begin{aligned} C_v(x) =&\sum _{i=1}^n \big [ v(X_{(i)}) - v(X_{(i+1)}) \big ] x_{(i)} \end{aligned}$$

(1)

$$\begin{aligned} =&\sum _{i=1}^n \big [ x_{(i)} - x_{(i-1)} \big ] v(X_{(i)}) \end{aligned}$$

(2)

where (.) is any permutation such that $x_{(1)} \le \ldots \le x_{(n)}$, and $X_{(i)}=\{x_{(i)}, \ldots , x_{(n)}\}$ is the set of objectives where the performance is at least as good as $x_{(i)}$, for $i =1, \ldots , n$. Furthermore we assume that $x_{(0)} = 0$ and $X_{(n+1)} = \emptyset$.

Given a capacity v we can define the dual capacity by $\bar{v}(A) = 1 - v(N \backslash A)$. For any vector $x \in \mathbb {R}^n$, we have: $C_v(x) = -C_{\bar{v}}(-x)$. Let us give an example of the use of the Choquet integral in preference modelling.

Example 1

Let $X = \{a, b, c\}$ be a set of alternatives evaluated according to 3 criteria as follows:

	a	b	c
criterion 1	$-2$	$-1$	0
criterion 2	5	2	$-2$
criterion 3	0	1	5

Assume that the DM prefers b to a and c. One can easily check that such a preference is not representable by a weighted linear aggregator. However, it is easily representable by a Choquet integral. For instance, let us consider the following capacity (Table 1):

Table 1. Capacity of the decision maker in Example 1

We have then $C_v(a) = (-2) \ v(N) + [0 - (-2)] \ v(\{2, 3\}) + [5 - 0] \ v(\{2\}) = -2 + 1 + 1 = 0$, $C_v(b) = (-1) \ v(N) + [1 - (-1)] \ v(\{2, 3\}) + [2 - 1] \ v(\{2\}) = -1 + 1 + 0.3 = 0.3$ and $C_v(c) = -2 + 0.8 + 0.5 = -0.7$, which implies that b is preferred to a and c.

Despite its descriptive appeal, the Choquet integral has itself some descriptive limits, especially when the DM uses different aggregation logics in the positive and in the negative part of the utility scale, as illustrated in Example 2.

Example 2

Let $X = \{a, b, c, d\}$ be a set of alternatives evaluated according to 2 criteria as follows:

	a	b	c	d
criterion 1	2	3	−3	−4
criterion 2	5	3	−3	−1

Assume that the value system of the DM is as follows: when performances are positive she wants to maximize the average performance. However, when some performances are negative, she adopts a more cautious behavior towards losses and favors a solution having a more balanced profile. Hence her preference order could be a, b, c, d. Any representation of this preference order by the Choquet integral should satisfy: $x \succ y \Leftrightarrow C_v(x) > C_v(y)$ for all $x, y \in X$.

The obtained contradiction demonstrates that no capacity v exists to represent the prescribed ranking. Therefore, the Choquet integral cannot model these preferences.

The observation of such behaviors motivated the development of models able to capture preferences that may vary depending on the position of the performances relatively to some reference values. In this paper we will assume that a vector of reference values $p=(p_1, \ldots , p_n)$ is known where $p_j$ is a neutral evaluation on criterion j, separating the good and the bad part of the scale. For the rest of this paper, when referring to a solution $x=(x_1, \ldots , x_n)$, we will consider that it has already been centered on p, (i.e., x = $x'$ - p where $x'$ is the original solution vector). Hence, 0 becomes the neutral value on all criteria scales. The existence of such bipolar scales has motivated the introduction of the following extension of the Choquet integral, defined for criterion values expressed on a bipolar scale [11, 12, 17].

Definition 3

Let $x \in \mathbb {R}^n$ and u and v be two capacities. The bipolar extension of the Choquet (biChoquet integral for short) is defined as follows:

$$\begin{aligned} C_{u,v}(x) = C_{u}(x^+) - C_{v}(x^-) \end{aligned}$$

(3)

where $x^+ = \max (x, 0)$ and $x^- = \max (-x, 0)$.

If we reinterpret Example 2 with this model, We obtain $u(\{2\}) > 2/6$ and $v({2}) < 2/6$ which is no longer contradictory. Actually this model can easily describe the preference order given in Example 2 due to the combination of two capacities, one for the positive side and the other for negative side. This general model includes several interesting subclasses. For example, when $u(A) = \varphi (\sum _{i \in A} p_i)$ and $v(A) = \psi (\sum _{i \in A} p_i)$ for some functions $\varphi$ and $\psi$ strictly increasing on the unit interval and such that $\varphi (0) = \psi (0)=0$ and $\varphi (1) = \psi (1)=1$, then the biChoquet integral is nothing else but the model proposed by Kahneman and Tversky in their Cumulative Prospect Theory (CPT) [25]. In the context of CPT, $p_i$ represents the probability of a state i. If we import the CPT model in the context of multicriteria aggregation, $p_i$ must be interpreted as the weight of criterion i and we obtain a bipolar version of the WOWA operator introduced by Torra [24] (when all criterion values are positive, we exactly obtain a WOWA). If we further specify the model by setting $p_i =1/n$ then capacities u and v are symmetric (their values only depend on the cardinality of the set) and the resulting model is known as biOWA [16]. We will come back to these models in the following sections.

Until now, we have made the assumption that preferences were known. This is a strong hypothesis and, in practice, the parameters of these models must be elicited. We now recall some background on incremental elicitation methods based on the minimisation of regrets.

2.2 Elicitation Based on Regret Minimization

We consider an aggregation function $f_w$ where w is the unknown weighting vector used in the model used to represent DM’s preferences. When no preference information is available the uncertainty set defined as the set of all admissible weighting vectors is defined by $\varOmega =\{w \in \mathbb {R^n_+}, \text {such that} \sum _{i=1}^n w_i = 1\}$. When a set P of preference statements is eventually observed (under the form of a list of ordered pairs of alternatives where the first is preferred to the second), the initial set $\varOmega$ can be reduced to a subset denoted $\varOmega _P$ using the linear constraints induced by the preferences in P. Hence $\varOmega _P$ is a convex polyhedron, at any step of the elicitation process.

Given an uncertainty set $\varOmega _P$, an alternative is said to be necessarily optimal in X, if $f_w(x) \ge f_w(y)$ for all $y \in X$ and all $w \in \varOmega _P$. In this context, the goal of an incremental preference elicitation method is to iteratively generate preference queries to collect preference statements and further restrict $\varOmega _P$ until a necessarily optimal element can be identified in X. In order to generate informative preference queries and to identify a necessarily optimal element as soon as possible, we can use the notion of max-regret as suggested in [27]. Let us recall the definition of regrets used in the elicitation process:

For two alternatives x and y, the Pairwise Max Regret (which quantifies the regret of choosing x instead of y) is defined by:

$$\begin{aligned} \text {PMR}(x, y, \varOmega _P) = \max \limits _{w \in \varOmega _P} (f_w(y) - f_w(x)) \end{aligned}$$

(4)

Then, the Max Regret attached to a solution $x \in X$ is defined by:

$$\begin{aligned} \text {MR}(x, \varOmega _P) = \max \limits _{y \in \chi } \text {PMR}(x, y, \varOmega _P) \end{aligned}$$

(5)

The MinMaxRegret (MMR) is then the minimal value of the MaxRegret for all elements in X.

$$\begin{aligned} \text {MMR}(x, \varOmega _P) = \min \limits _{x \in \chi } \text {MR}(x, \varOmega _P) \end{aligned}$$

(6)

A necessarily optimal solution has a Max Regret value of 0. Hence, we have to collect preference statements until the MMR drops to 0. Preference queries are generated using the current solution strategy that consists in comparing a solution $x^*$ having a minimal MR value to its strongest challenger, i.e., any solution $y^*$ maximizing $PMR(x^*, y^*, \varOmega _P)$. In practice, to save a significant number of queries, we can stop the process when MMR drops below a given $\epsilon >0$ without loosing much in the quality of the returned solution. When the set of alternatives X is finite and defined explicitly, this general elicitation process interleaving preference queries and the exploration of the set of alternatives is formalized in Algorithm 1. The computation of the PMR is specific to each aggregation function and will be discussed later in the paper.

This algorithm can be used to incrementally elicit the capacities u and v in $C_{u,v}$ (Eq. 3). In this case, the aggregator $f_w$ is the biChoquet integral and its parameter w is defined by the pair of capacities u, v. In the following sections, we introduce some computational models based on linear programming to efficiently obtain the PMR values in the simultaneous elicitation of u and v. We successively consider three different families of instances of biChoquet integrals.

3 Elicitation of a 2-Additive BiChoquet Integral

Capacities u and v are useful mathematical functions to model the interactions among criteria but their definition or approximation would require to work with $2(2^{n}-2)$ weighting coefficients where n is the number of criteria. In order to introduce more compact representations of interactions while keeping some flexibility in the model, we use the Möbius inverse of the capacities. Given a capacity v, the Möbius inverse of v is defined by $m_v(A) = \sum _{ B \subseteq A} (-1)^{|A \backslash B|} v(B)$ for all $A \subseteq N$. Then, $C_{u,v}$ can be rewritten from $m_u$ and $m_v$ as follows:

Proposition 1

Let u and v be two capacities and x a performance vector, we have:

$$\begin{aligned} C_{u,v}(x) = \sum \limits _{A \subseteq N} m_u(A) \min \limits _{i \in A} x_i^+ - \sum \limits _{A \subseteq N} m_{\bar{v}}(A) \max \limits _{i \in A} x_i^- \end{aligned}$$

(7)

with $m_u$ the Möbius inverse of u and $m_{\bar{v}}$ the Möbius inverse of $\bar{v}$ the dual capacity of v, $x^+ = \max (x, 0)$ and $x^- = \max (-x, 0)$.

Proof

We recall that $C_v(x) = -C_{\bar{v}}(-x)$ and that $C_v(x) = \sum _{A \subseteq N} m(A) \min _{i \in A} x_i$. We have then $C_{u,v}(x) = C_{u}(x^+) - C_{v}(x^-) = C_{u}(x^+) - (-C_{\bar{v}}(-x^-))$ and therefore $C_{u,v}(x) = C_{u}(x^+) - (- \sum _{A \subseteq N} m_{\bar{v}}(A) \min _{i \in A} (-x^-_i)) = \sum _{A \subseteq N} m_u(A) \min _{i \in A} x_i^+ - \sum _{A \subseteq N} m_{\bar{v}}(A) \max _{i \in A} x_i^+$.

This formulation suggests that more compact representations of subclasses of biChoquet integrals can easily be obtained. We can indeed restrict u and $\bar{v}$ to k-additive capacities. A capacity u is said to be k-additive if and only if its Möbius inverse $m_u$ verifies for all $A \subseteq N, |A| > k, m_u(A) = 0$ and it exists at least $B \subseteq N, |B| = k$ such as $m_u(B) \ne 0$. For example, a 2-additive capacity is completely characterized by $n(n+1)/2$ Möbius masses (one for every singleton and every pair). Such a capacity makes it possible to model non-linearities due to pairwise interactions between pairs of criteria while involving only a polynomial number of parameters. Moreover, by restricting u and v to 2-additive capacities, we can exploit the following result [18]:

Proposition 2

We set $\mathcal {Q} = \{A \subseteq N, ~ 1 \le |A| \le 2\}$ and $\mathcal {Q}' = \{B \subseteq N, ~ |B| = 2\}$. The class of 2-additive capacities forms a convex polytope whose extreme points are of two types:

• $\text {For all } A \in \mathcal {Q}$, we define the extreme point $M_A$ as, for all $X \subseteq N, ~M_A(X) = 1 \text { if } X = A, ~ 0 \text { otherwise.}$

• $\text {For all } B \in \mathcal {Q}'$, we define the extreme point $M'_B$ as, for all $X \subseteq N, ~M'_B(X) = -1\text { if } X = B, ~1 \text { if } \emptyset \ne X \subset B, ~ 0 \text { otherwise.}$

Every 2-additive capacity has then its Möbius inverse m defined as a convex combination of those extreme points:

$$ m = \sum \limits _{A \in Q} \alpha _A \cdot M_A + \sum \limits _{B \in Q'} \alpha '_B \cdot M'_B $$

with $\forall A \in \mathcal {Q}, \alpha _A \ge 0$, $\forall B \in \mathcal {Q}', \alpha '_B \ge 0$ and $\sum _{A \in \mathcal {Q}} \alpha _A + \sum _{B \in \mathcal {Q}'} \alpha '_B = 1$. Therefore, every 2-additive capacity is defined by an unique positive vector of size $2 \times \left( {\begin{array}{c}n\\ 2\end{array}}\right) + n$, formed by the concatenation of $\alpha$ and $\alpha '$. In our context, we consider two 2-additive capacities u and $\bar{v}$ and their Möbius inverse $m_u$ and $m_{\bar{v}}$. Their coefficients in the combination of extreme points of the polytope will be denoted ($\alpha ^u_A$, $\alpha ^{'u}_B$) and ($\alpha ^{\bar{v}}_A$, $\alpha ^{'\bar{v}}_B$) in the sequel. Using the previous notions and definitions, we present the following linear program to compute the PMR between x and y, with a set of possible parameters $\varOmega _P$, defined as the set of all possible 2-additives capacities u and $\bar{v}$ characterized by their Möbius masses $m_u$ and $m_{\bar{v}}$ and described by variables $\alpha ^u_A$,$\alpha '^u_B$, $\alpha ^{\bar{v}}_A$, $\alpha '^{\bar{v}}_B$.

$$ \begin{array}{ll} \max &{} \sum \limits _{A \subseteq \mathcal {Q}} m_u(A) (\min \limits _{i \in A} y_i^+ - \min \limits _{i \in A} x_i^+) - \sum \limits _{A \subseteq \mathcal {Q}} m_{\bar{v}}(A) (\max \limits _{i \in A} y_i^- - \max \limits _{i \in A} x_i^-)\\ (\mathcal {P}_1) &{} \left\{ \begin{array}{l} m_u(X) = \sum \limits _{A \in \mathcal {Q}} \alpha _A^u M_A(X) ~ + \sum \limits _{B \in \mathcal {Q}'} \alpha _B^{'u} M_B'(X), ~ \forall X \subseteq \mathcal {Q}\\ m_{\bar{v}}(X) = \sum \limits _{A \in \mathcal {Q}} \alpha _A^{\bar{v}} M_A(X) ~ + \sum \limits _{B \in \mathcal {Q'}} \alpha _B^{'\bar{v}} M_B(X), ~ \forall X \subseteq \mathcal {Q}\\ \sum \limits _{X \in \mathcal {Q}} \alpha _X^u + \sum \limits _{X \in \mathcal {Q'}} \alpha _X^{'u} = 1\\ \sum \limits _{X \in \mathcal {Q}} \alpha _X^{\bar{v}} + \sum \limits _{X \in \mathcal {Q'}} \alpha _A^{'\bar{v}} = 1 \\ \sum \limits _{A \subseteq \mathcal {Q}} m_u(A) \min \limits _{a_i^+ \in A} a_i^+ - m_{\bar{v}}(A) \max \limits _{a_i^- \in A}a_i^- \ge \\ ~ \sum \limits _{A \subseteq \mathcal {Q}} m_u(A) \min \limits _{b_i^+ \in A} b_i^+ - m_{\bar{v}}(A) \max \limits _{b_i^- \in A}b_i^-, ~ \forall (a,b) \in \varOmega _P \\ \end{array} \right. \\ &{} m_u(A), \ m_{\bar{v}}(A) \ge 0, ~ \forall A \subseteq N \\ &{} \alpha _A^u, \alpha _A^{\bar{v}} \ge 0, ~ \forall A \subseteq \mathcal {Q},~~ \alpha _B^{'u}, \alpha _B^{'\bar{v}} \ge 0, ~ \forall B \subseteq \mathcal {Q}' \\ \end{array} $$

Fig. 1.

Comparison of CSS and Random strategies - Average regrets evolution - 5 criteria and 25 alternatives

For any two 2-additive capacities u and $\bar{v}$, this linear program has $6 \left( {\begin{array}{c}n\\ 2\end{array}}\right) + 3n$ continuous variables and $2\left( {\begin{array}{c}n\\ 2\end{array}}\right) + 2n + |P|$ constraints, with |P| the number of added constraints induced by preferences statements. We implemented Algorithm 1 to elicit u and v in $C_{u,v}$ using program $\mathcal {P}_1$ for the computation of PMR values. To run our tests, we used Gurobi 8.1.1 solver, a cluster of computers with 252 GB of RAM and 32 Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40 GHz processors. Our elicitation algorithm has been tested on randomly generated instances with capacities randomly drawn using Proposition 2. Alternatives are randomly sampled to form a Pareto-front with a significant part of unsupported solutions (which do not belong to the frontier of the convex envelope and thus that cannot be considered optimal by a linear model). For each instance, the elicitation sequence is iterated until we observe a decrease of the MMR value of at least $90\%$ ($\epsilon =0.1$). The following Figure compares the evolution of the regret (i.e., the MMR value) throughout the elicitation process, for strategies CSS and Random (in the latter, the preference query is randomly selected at each step) (Fig. 1).

The curves reflecting the decay of MMR values show that when $\epsilon =0.1$, the elicitation algorithm stops after about 15 preference queries with the CSS whereas much more queries would be necessarily for the Random strategy. As observed for other models, CSS appears to be effective to find informative queries reducing regrets. Through the rest of this paper, we will focus on this query strategy to perform tests with different families of bipolar models.

Now, we report the average computation times and the average number of preference queries used to solve instances of different sizes (n the number of criteria varies from 5 to 10 and m, the size of the set of alternatives, varies from 50 to 100).

Even though the number of parameters is two times greater than in the monopolar case (standard 2-additive Choquet integrals), we observe that the solution times of Algorithm 1 remain reasonably low. Actually, they are in the same order of magnitude that the computation times we use to obtain for standard 2-additive Choquet integrals. Moreover, we observe that the elicitation cost in terms of number of preference queries asked to the DM does not increase drastically when considering the bipolar extension of the Choquet Integral.

4 Elicitation of a Bipolar WOWA

In this Section we consider another subclass of the general biChoquet model introduced in Eq. 3. We are no longer restricted to two additive capacities but consider all capacities that are defined as monotonic transformed of an additive measure. Formally, we assume that u and v have the following forms: $u(A) = \varphi (\sum _{i \in A} p_i)$ and $v(A) = \psi (\sum _{i \in A} p_i)$ where $p_i$ are the criteria weights. As mentioned at the end of Subsect. 2.1, the resulting subclass of biChoquet functions is a counterpart of CPT in the setting of multicriteria aggregation. The aggregators in this family can also be seen as bipolar extensions of WOWA (the weighted extension of OWA proposed in [24]). For this reason, these operators are named biWOWA hereafter. More formally they are defined as follows:

Definition 4

Let $x \in \mathbb {R}^n$ be a performance vector, $p \in \mathbb {R}^n$ an importance vector over the set of criteria, $\varphi$ and $\psi$ two increasing functions with $\varphi (0) = \psi (0) = 0$ and $\varphi (1) = \psi (1) = 1$. The Bipolar Ordered Weighted Averaging operator (biWOWA) is defined as the aggregation function $f_{\varphi , \psi }: \mathbb {R}^n \rightarrow \mathbb {R}$ such that:

$$\begin{aligned} f_{\varphi , \psi }(x) = \sum \limits _{i=1}^n \varphi (\sum \limits _{k=i}^n p_{(k)}) \big [ x_{(i)}^+ - x_{(i-1)}^+ \big ] - \sum \limits _{i=1}^n \psi (\sum \limits _{k=i}^n p_{(k)}) \big [ x_{(i)}^- - x_{(i-1)}^- \big ] \end{aligned}$$

with $x^+ = \max \{x, 0\}$, $x^- = \max \{-x, 0\}$ and (.) the permutation of criteria which sorts x in the increasing order.

We assume here that the weighting vector p is known and we focus on the elicitation of $\varphi$ and $\psi$. This is a challenging problem because we have to consider a continuous set of non-linear increasing functions. To overcome this difficulty, we use a spline representation of $\varphi$ and $\psi$. Spline functions are piecewise polynomials whose elements connect with a high level of smoothness. Further details on spline functions can be found in [19, 20], but an interesting property of these functions is that they can be generated with a linear combination of basis monotonic spline functions. This allows to reduce the elicitation of $\varphi$ and $\psi$ to their corresponding weighting vectors $b^\varphi$ and $b^\psi$ in the spline basis. More precisely, we have $\varphi (x) = \sum _{j=1}^r b_j^\varphi I_j(x)$ and $\psi (x) = \sum _{j=1}^r b_j^\psi I_j(x)$, where $I_j(x), j = \{1, \ldots , l\}$ are the basic monotonic spline functions (see Fig. 2). A similar approach, based on the use of spline functions, has been proposed for the WOWA model in [4] on the robust assignment problem.

Fig. 2.

I-spline basis of order 3

In order to compute PMR(x, y) for two alternatives x and y when preferences are represented with the biWOWA model, we propose the linear program $\mathcal {P}_2$. For any two increasing functions $\varphi$ and $\psi$, this linear program has 2r continuous variables and $2l + |P|$ constraints, with |P| the number of added constraints induced by preferences statements and l the size of the spline functions basis.

$$ \begin{array}{ll} \max &{} \big [ \sum \limits _{i = 0}^n [\sum \limits _{j=1}^l b^\varphi (j) I_j(\sum \limits _{k=i}^n p_{(k)}))] (y^+_{(i)} - y^+_{(i-1)}) - [\sum \limits _{j=1}^l b^\varphi (j) I_j(\sum \limits _{k=i}^n p_{(k)}))] (x^+_{(i)} - x^+_{(i-1)}) \big ] \\ &{} - \big [ \sum \limits _{i = 0}^n [\sum \limits _{j=1}^l b^\psi (j) I_j(\sum \limits _{k=i}^n p_{(k)})) ] (y^-_{(i)} - y^-_{(i-1)}) - [\sum \limits _{j=1}^l b^\psi (j) I_j(\sum \limits _{k=i}^n p_{(k)})) ] (x^-_{(i)} - x^-_{(i-1)})) \big ]\\ \\ (\mathcal {P}_2) &{} \left\{ \begin{array}{l} \sum \limits _{j=1}^l b^\varphi (j) = 1 \\ \sum \limits _{j=1}^l b^\psi (j) = 1 \\ f_{\varphi , \psi }(a) \ge f_{\varphi , \psi }(b), ~\forall (a,b) \in \varOmega _P \\ \end{array} \right. \\ &{} b^\varphi (j), b^\psi (j) \ge 0, ~j= 1, \ldots , l \\ \end{array} $$

We implemented Algorithm 1 using program $\mathcal {P}_2$ to compute the PMR values to elicit $\varphi$ and $\psi$ in $f_{\varphi ,\psi }$. In our tests, we used the experimental setting of Sect. 3. We simulated the DM’s answers to preferences queries using $f_{\varphi ',\psi '}$ where $\varphi '$ and $\psi '$ were randomly drawn using the basis of spline functions. The execution times and the number of queries asked to the DM are given in the tables below;

We observe that, even though computation times remain low in the bipolar case, the increase between WOWA and BiWOWA operator is significant. However, when it comes to the number of generated preference queries, we observe only a slight increment when passing from WOWA to biWOWA. The increase of computation time seems to be related to the computation of PMR using linear program $\mathcal {P}_2$.

5 Elicitation of a Bipolar OWA

In this section we consider the bipolar Ordered Weighted Averaging (biOWA), introduced in [16] to generalize OWA to the bipolar case. As mentioned before, this is an instance of the biWOWA obtained when the criteria weights are equal ($p_i=1/n$). This instance can be elicited by the general method proposed for biWOWA but we are going to introduce a more specific and direct method, taking advantage of the fact that biOWA admits a much simpler formulation when all criteria weights have the same value.

Definition 5

Let $x \in \mathbb {R}^n$ be a performance vector and $\alpha , \beta \in \mathbb {R}^n_+$ two weighting vectors, the bipolar ordered weighted averaging (biOWA) is the aggregation function $g_{\alpha ,\beta }:\mathbb {R}^n\rightarrow \mathbb {R}$ defined by:

$$\begin{aligned} g_{\alpha ,\beta }(x) = \alpha \cdot x^+_{\uparrow } - \beta \cdot x^-_{\downarrow } \end{aligned}$$

(8)

with $x^+ = \max \{x, 0\}$, $x^- = \max \{-x, 0\}$ and $x_{\uparrow }$ (resp. $x_{\downarrow }$) is the vector obtained from x by rearranging its components in the increasing (resp. decreasing) order.

In this case, the parameter of the model is defined by the pair $\alpha , \beta$ of weighting vectors defining how the DM focuses on good and bad positive (resp. negative) evaluations. As in the OWA operator, these weights are not attached to criterion values but to their rank in the ordered list of positive (resp. negative) criterion values. In order to compute the PMR values for this model, we use program $(\mathcal {P}_3)$ given below:

$$ \begin{array}{ll} &{} \max \sum \limits _{i=1}^n \alpha _i ~ (y^+_{(i)} - x^+_{(i)}) - \beta _i ~ (y^-_{(i)} - x^-_{(i)})\\ (\mathcal {P}_3) &{} \left\{ \begin{array}{l} \sum \limits _{i=1}^n \alpha _i = 1 \\ \sum \limits _{i=1}^n \beta _i = 1 \\ \sum \limits _{i=1}^n \alpha _i ~ a^+_{(i)} - \beta _i~ a^-_{(i)} \ge \sum \limits _{i=1}^n \alpha _i ~ b^+_{(i)} - \beta _i ~ b^-_{(i)}, ~ \forall (a,b) \in \varOmega _P \\ \end{array} \right. \\ &{} \alpha _i, \beta _i \ge 0, ~ \forall i \in \{1, .., n\} \\ \end{array} $$

For any two weighting vectors $\alpha$ and $\beta$, this linear program has 2n continuous variables and $2 + |P|$ constraints, with |P| the number of added constraints induced by preferences statements. We implemented Algorithm 1 using program $\mathcal {P}_3$ to compute PMR values and elicit a biOWA. We also implemented the method for the elicitation of a standard OWA in order to compare execution times and the number of asked queries. To run our tests, we used the same experimental setting as before and the DM’s answers were simulated using $g_{\alpha ',\beta '}$ where $\alpha '$ and $\beta '$ were randomly drawn weighting vectors. The results of the tests are given in the tables hereafter.

As in Sect. 3, we observe that computation times are at most two times more important when passing from OWA to biOWA. This good result can be explained by the partial elicitation of preferences and the efficient computation of PMR values due to program $\mathcal {P}_3$. The number of preference queries is similar for OWA and biOWA, which is an encouraging result for the use of biWOWA in other incremental elicitation contexts (e.g., when the alternatives are defined implicitly).

6 Conclusion

Preferences modeling and learning in multicriteria decision-making problems are crucial issues. Moreover, bipolar models are gaining importance in the field of decision theory to overcome descriptive limitations of usual aggregation functions when a reference point must be considered. For these reasons, we have proposed new computational models to perform an incremental elicitation of preferences based on a bipolar rank-dependent model. We applied our approach to biOWA, biWOWA and 2-additive biChoquet integrals, which extends our previous contributions on the elicitation of monopolar models (OWA, WOWA and Choquet).

The elicitation methods proposed here and the tests performed concern the case where the set of alternatives is defined explicitly. A natural continuation of this work would be to extend the approach to sets of alternatives that are implicitly defined (e.g., for preference-based combinatorial optimization). Another extension could be to consider the elicitation of the biChoquet model for more general classes of capacities, and the elicitation of bi-capacities for the Choquet model. The major challenge will be the increased number of parameters to be learned in the model and the efficient computation of PMR values.