BiOWA for Preference Aggregation with Bipolar Scales: Application to Fair Optimization in Combinatorial Domains

1 Introduction

Decision making is often a matter of balancing pros and cons of possible choices. This is the case in multcriteria decision problems where the solutions are generally assessed w.r.t partially conflicting criteria. This also holds in collective decision making when agents have contrasted opinions about candidates. This happens too in decision under uncertainty where the utility of an action can vary drastically from one scenario to another. Very often, positive and negative perceptions co-exist in individual values and are represented using a bipolar utility scale in which 0 acts as a landmark separating the positive and negative sides [Dubois and Prade, 2008].

Yet, most normative decision methods use the same aggregation logic regardless the sign of outcomes under consideration. The utility scale is often treated as an interval scale and preferences are not impacted by positive affine transformations of the utility scale. For example, many aggregation functions f : Rn → R used in multicriteria analysis are such that f(ax + b) = af(x) + b for all x ∈ Rn , a ∈ R+, b ∈ R. Hence if f(x) > f(y) we also have f(ax+b) = af(x)+b > af(y) + b = f(ay + b). In this case, 0 has no specific status.

It has been observed in different contexts that decision makers tend to think of outcomes relative to a certain reference point (often the status quo). They may exhibit different attitudes towards gains (i.e. outcomes above the reference point) and losses (i.e. outcomes below the reference point) and care generally more about negative outcomes than positive ones. In the field of decision under risk, this observation is at the origin of Prospect Theory [Kahneman and Tversky, 1979] and Cumulative Prospect Theory (CPT) [Tversky and Kahneman, 1992] that provide decision models able to incorporate the observed behaviors. Similarly, in the field of multicriteria analysis, extensions of various decision models have been proposed for handling bipolar scales and explaining observed preferences [Labreuche and Grabisch, 2006; Grabisch et al., 2008; Grabisch et al., 2009]. In particular, a generalization of the discrete Choquet integral is proposed for aggregating criterion values expressed on bipolar scales. The model is a kind of sophisticated weighted average that assigns different weights to criteria and coalitions of criteria depending on the nature of criterion values being positive or negative. This model formally includes the CPT model as special case [Labreuche and Grabisch, 2006].

In this paper we study a bipolar extension of the Ordered Weighted Averaging (OWA), with the aim of proposing new tools for fair optimization in combinatorial domains. The standard OWA operator is an aggregation function introduced in [Yager, 1998] formally defined, for all x ∈ Rn , by the dot product fw(x) = w · x↑ where w ∈ Rn+ is a weighting vector and x↑ is the vector obtained by rearranging the components of x in ascending order. It is therefore a weighted sum of the components xi, each component representing the utility of solution x w.r.t a given point of view (e.g., a criterion, an agent, a scenario). However, we remark that the weights are not attached to criteria but to ranks of satisfaction due to the sorting of components. Function fw is symmetric and weights only serve to control the importance attached to good or bad evaluations in the aggregation. OWA is often used with decreasing weights (wi ≥ wi+1, i = 1, . . . , n - 1) in fair optimization because its maximization favors solutions with well-balanced profiles (a greater weight is assigned to lower components). More precisely, when w has decreasing components fw is monotonically increasing w.r.t Mean-Preserving Transfers Reducing Inequalities (MPTRI), i.e., any transfer moving from x = (x1, . . . , xn)

to (x1, . . . , xi - λ, . . . , xj + λ, . . . , xn) for some i, j, λ such that xi - xj > λ > 0 (see Example 1). This property participates to the axiomatic justification of OWA for inequality measurement. Generalized Gini social-evaluation Functions defined in Social Choice [Blackorby and Donalson, 1978; Weymark, 1981] are nothing else but an OWA of individual utilities using decreasing weights. For similar reasons, OWA is also used in robust optimization because OWA-optimal solutions tend to have well-balanced profiles (providing good outcomes in all scenarios) [Perny and Spanjaard, 2003].

Example 1. If w = ( 2 3 , 13 ) we have fw(30, 0) = fw(0, 30) = 10 < 15 = fw(15, 15), therefore (15, 15) is better than (30, 0) and (0, 30). Modeling this preference for the balanced solution could not be possible with a linear aggregator.

However, the standard OWA is not always sufficient to describe rational behaviors in a fair optimization context, especially when utilities are expressed on a bipolar scale and preferences are impacted by the reference point under consideration. Let us consider the following example:

Example 2. A research lab would like to hire a new engineer. Two teams are interested by the recruitment and the new engineer will possibly interact with both teams. Candidates are evaluated by the two teams and the final decision will be made by the director of the lab. Let us consider two different cases, involving two candidates {a, b} and {c, d} respectively. The teams express their evaluation on the scale [-5, +5] where 0 is the neutral element. The evaluations are given below:

In case 1, evaluations of candidates are positive for both teams, and in this case, according to the director, the best candidate will be the one having the best average evaluation. Therefore a is preferred to b. In case 2 the situation is different due to the existence of negative evaluations. In that case the director of the lab may adopt a more cautious attitude to avoid frustration and conflicts. For this reason he prefers d to c because d has a better balanced profile.

If we look for a symmetric aggregator f : R2 → R to describe the observed preferences (symmetric to guarantee an equal treatment of the two teams), we must satisfy the following constraints: f(0, 5) > f(2, 2) and f(-2, 1) > f(4,-4). Function f cannot be an average nor an OWA. An OWA would indeed have the following form: f(x, y) = wmin{x, y} + (1 - w)max{x, y} with w ∈ [0, 1]. Thus, preferring a to b implies w < 35 . Moreover preferring d to c implies w > 35 which yields a contradiction.

This example shows that one cannot model the director's preferences with an OWA. A more general aggregation function is needed, making it possible to model different attitudes in the aggregation depending on whether evaluations are on the positive or on the negative side. Our aim here is to increase the range of possible applications of OWA optimization by extending OWA and related computational models to cope with bipolar evaluation scales and preferences depending on a reference point.

The paper is organized as follows: In Section 2 we propose a brief review of related work. In Section 3 we introduce the biOWA and establish useful monotonicity properties for this aggregation function. Then we study the use of biOWA in the context of multi-winner election with approval and disapproval ballots (Section 4) and in the context of the robust shortest paths problem (Section 5).

2 RelatedWork

The model of CPT [Tversky and Kahneman, 1992] and the extension of the Choquet integral to the bipolar case [Labreuche and Grabisch, 2006] clearly provide a formal canvas to extend OWA to the bipolar case since OWA is a symmetric instance of the Choquet integral [Grabisch et al., 2009]. We will develop this idea in Section 3.

Another attempt to extend OWA to the case of bipolar scales was proposed in [Grzegorzewski and Ł ˛ acka, 2015] for preference modeling in the context of recommender systems. The proposed criterion named BOWA uses a single weighting vector and applies weights to components reordered according to their absolute value. This definition does not allow the use of distinct weighting systems for positive and negative components. Moreover it is not monotonic w.r.t Pareto dominance. Alternative combinations of OWA operations have also been studied in a more general setting [Mesiar et al., 2018], leading to more complex models. However, none of the contributions mentioned above tackles computational issues relative to optimization on implicit sets.

Besides, various computational models have been proposed for OWA optimization on unipolar scales, either relying on linear programming techniques [Ogryczak, 2003; Chassein and Goerigk, 2015] or based on specialized implicit enumeration methods, e.g., [Galand and Spanjaard, 2007]. These techniques have been widely used in AI and operations research, in various contexts such as multiagent assignment problems (resource or task allocation) [Lesca and Perny, 2010; Heinen et al., 2015; Lesca et al., 2019], multiobjective state-space search [Galand and Spanjaard, 2007], multiagent knapsack problems [Bourdache and Perny, 2019] and also in facility location problems [Ogryczak, 2009]. However, none of these contributions considers the case of bipolar scales.

Let us finally mention that a multiobjective linear programming approach exploiting OWA and a bipolar view of preferences is proposed in [Dubey and Mehra, 2012]. However, OWA is only used to aggregate positive evaluations. Negative evaluations are only used to check admissibility constraints.

In this paper we keep the approach adopted in CPT and consider a bipolar version of OWA named biOWA, defined as a difference of two OWA separately aggregating the positive and negative arguments. Beyond the definition of this aggregator and the study of some properties, we propose and test several computational models for biOWA optimization.

3 BiOWA: an OWA for Bipolar Scales

A natural extension of OWA to bipolar scales, in the style of CPT, is the following;

Definition 1. Let x ∈ Rn be an evaluation vector and α, β ∈ Rn+ two weighting vectors, the bipolar ordered weighted averaging (biOWA for short) is the aggregation function gα,β : Rn → R defined by:

where x+ = max{x, 0}, x- = max{-x, 0} and x↑ (resp. x↓) is a vector derived from x by rearranging its components in ascending (resp. descending) order.

We observe that, when x ∈ Rn+ then x+ = x and x- = 0 therefore gα,β(x) = fα(x). In this case biOWA reduces to a standard OWA. More generally, for any fixed x ∈ Rn , there exists w ∈ Rn+ such that gα,β(x) = fw(x). The weighting vector w depends on x and is given by:

Hence any biOWA can be seen as a generalization of OWA using a non-constant weighting vector that may vary with x. Coming back to Example 2 we see that gα,β used with α = ( 12 , 12 ) and β = (1, 0) describes the observed preferences:

Then, a natural question is whether biOWA is monotonic w.r.t weak Pareto-dominance. The answer is given below:

Proposition 1. Let x, y ∈ Rn such that xi ≥ yi, for i = 1, . . . , n, one of these inequalities being strict. Let α, β ∈ Rn+ be two weighting vectors with decreasing and strictly positive components, then gα,β(x) > gα,β(y).

Proof. Since α and β have decreasing components, we have:

where Π is the set of all permutations defined on (1, . . . , n). Moreover, since x+i ≥ y+ i for all i we have, for all π ∈ Π, απ(i)x+i ≥ απ(i)y+ i and therefore ∑ni=1 απ(i)x+i ≥ ∑ni=1 απ(i)y+ i . Hence, taking the minimum over all π ∈ Π we obtain α·x+↑ ≥ α·y+ ↑ (a) by (3). Similary, since yi ≥ x-i for all i we have, for all π ∈ Π, βπ(i)yi ≥ βπ(i)x-i and therefore ∑ni=1 βπ(i)yi ≥ ∑ni=1 βπ(i)x-i . Hence, taking the maximum over all π ∈ Π we obtain -β · x-↓ ≥ -β · y↓ (b) by (4). Moreover, xi > yi holds for some i by hypothesis. Therefore at least one inequality (a) or (b) is strict. Then the result follows by summing (a) and (b) term by term.

A nice consequence of this proposition is that maximizing gα,β with positive weights necessary leads to a Pareto-optimal solution. Yet, this does not mean that gα,βoptimization favors well balanced solutions. Let us determine a set of necessary and sufficient conditions on (α, β) for gα,β to be monotonic w.r.t MPTRI.

Proposition 2. gα,β is monotonic w.r.t MPTRI if and only if α and β have decreasing components and βl ≥ αl+1 for all l ∈ {1, . . . , n - 1}.

Proof. ⇐We assume that α and β have decreasing components and that for all l ∈ {1, ...n - 1} αl ≥ βl+1. Let us consider any x ∈ Rn with xi < xj for some pair (i, j). Let x′ = [x1, .., xi + λ, .., xj - λ, .., xn] with λ ∈ (0, xj - xi) the vector derived from x using a MPTRI. Let w and w′ be the weighting vectors respectively derived from x and x′ using Equation (2). If xi and xj are of the same sign, or if λ > max(-xi, xj) or if λ < min(-xi, xj), then x and x′ have the same number of positive (resp. negative) components. Hence we have w = w′ and therefore gα,β(x′ ) = fw(x′ ). Moreover fw(x′ ) ≥ fw(x) = gα,β(x) (the inequality is due to the fact that w has decreasing components). Therefore gα,β(x′ ) ≥ gα,β(x). Now let us consider the case where x and x′ have a different number of negative components (this occurs when xi < 0 < xj and min(-xi, xj) ≤ λ ≤ max(-xi, xj)). This means that either component i or component j (not both) has a different sign when passing from x to x′ . In the sequel we assume that the sign changes for component j (a symmetric proof could be done for the other case). Hence we can decompose the transfer into two successive ones: the first transfer decreases component j to 0 and the second transfer completes the first one by decreasing component j from 0 to xj -λ. Let x′′ = (x1, .., xi + xj , .., xj - xj , .., xn) the vector we obtain after the first transfer and w′′ the associated weighting vector using Equation (2). Then we have:

• Since x′′ j = 0, component j is still non-negative after the first transfer, and then w′′ = w. Hence we have gα,β(x′′ ) = fw(x′′ ). Moreover fw(x′′ ) ≥ fw(x) = gα,β(x) (the inequality is due to the fact that w has decreasing components) and therefore gα,β(x′′ ) ≥ gα,β (x).
• Since x′′ j = 0, the component j does not impact the calculation of gα,β(x′′ ), which implies that fw′′(x′′ ) = fw′(x′′ ). Therefore we have gα,β(x′ ) = fw′(x′ ) ≥ fw′(x′′ ) = gα,β(x′′ ) (the inequality is due to the fact that w′ has decreasing components).

Finally, we have gα,β(x′ ) ≥ gα,β(x) in all cases. This shows that gα,β is monotonic w.r.t MPTRI.

⇒ Let x′ be a solution obtained from x by a MPTRI. We can distinguish two possible cases where (α, β) do not fulfill the required conditions:

• Either α or β does not have decreasing components. In the former case we can consider a non-constant vector x with no negative component. Then gα,β(x) = fα(x) is an OWA, known to be non-monotonic w.r.t MPTRI since components of α are not in the right order. The same reasoning applies to the latter case considering any other x with no positive component.
• ∃ l ∈ {1, .., n - 1} with βl < αl+1. Let us consider x such that x1 < . . . < xl < 0 < xl+1 < . . . < xn and x′ the solution obtained from x by a MPTRI between xl+1 and xl of size λ chosen sufficiently small

to preserve in x′ the element's order of x. We have gα,β(x′ ) - gα,β(x) = βl (xl + λ) + αl+1 (xl+1 - λ) - βl xl - αl+1 xl+1 = λ(βl - αl+1) < 0. Then, gα,β is not monotonic w.r.t MPTRI.

The conditions are therefore necessary and sufficient.

Proposition 2 characterizes the set of admissible parameters (α, β) for performing a fair optimization with a biOWA. Now, we study two applications of fair biOWA optimization, first in social choice and then in robust optimization.

4 Multi-Winner Election with Approval and Disapproval Ballots

Approval balloting is an evaluation system used in voting procedures in which each voter submits a ballot including the candidates he approves. It can be extended to richer systems involving approval and disapproval ballots [Felsenthal, 1989]. Such systems are often used in single-winner elections but can be extended to the multi-winner case [Kilgour, 2010]. We consider here a refinement of such voting systems where voters assign positive or negative grades to candidates to modulate approval and disapproval intensities.

More formally, let V be a set of n voters and C a set of m candidates. Let vij ∈ J-T, T K be the grade assigned to candidate j by voter i, T being the maximal admissible grade. We assume that preferences are additive over bundles and therefore the value of any subset S ⊆ C for voter i is defined by ∑j∈S vij . Assume we want to elect a committee of k candidates maximizing the voters' satisfaction, while paying a particular attention to unsatisfied voters (with negative satisfactions). We propose to use a biOWA to model the overall value of any subset. Hence we can formulate the biOWA MultiWinner Election Problem (biOWA-MWE Problem) with the following mixed integer program:

where yj is the decision variable relative to the selection of candidate j, j = 1, . . . ,m. For any fixed k, the biOWAMWE problem is polynomial. Indeed, we can enumerate the (mk ) subsets of size k and return the gα,β-optimal subset. The general problem is NP-hard because biOWA optimization includes min-max optimization and the min-max version of the problem, a.k.a the minimum selecting items problem, is known to be NP-hard for two scenarios and strongly NPhard for an unbounded number of scenarios [Kasperski and Zieli´nski, 2015]. In order to solve the biOWA-MWE problem using mixed-integer programming, we establish a useful result for linearizing gα,β:

Proposition 3. For all x ∈ Rn , and all α, β ∈ Rn+ two weighting vectors having decreasing components we have:

with Π the set of permutations on {1, .., n}.

Proof. Due to Equations (3) and (4) we have:

Now we establish the reverse inequality. Let π∗ a permutation such that α · x+↑ = ∑ni=1 απ∗(i)x+i and π′∗ a permutation such that β · x-↓ = ∑ni=1 βπ′∗ (i)x-i . Now, let us consider any permutation τ∗ of (1, . . . , n) such that τ∗(i) = π∗(i) if xi > 0 and τ∗(i) = π′∗ (i) if xi < 0, τ∗(i) being chosen arbitrarily for all i such that xi = 0 to complete the permutation. By construction we have:

Proposition 3 shows that gα,β(x) can be computed, for any fixed x ∈ Rn , by solving the following linear program:

In the above program, variables pij are used to model permutations of (1, . . . , n). Let us first assume that pij are boolean variables. In this case they are able to model any permutation π ∈ Π by setting pij = 1 if π(i) = j and 0 otherwise. Now, if we relax variables pij, these permutations are represented by the vertices of the convex polyhedron defined by variables pij (vertices are integral). Hence, due to the linearity of the objective function w.r.t variables pij, one can relax the integrity of variable pij without changing the optimal value of the problem. This argument is used in [Chassein and Goerigk, 2015] to model permutations of OWA and still applies to permutations used in biOWA. The dual formulation of the above linear program (7) reads as follows:

Using this formulation, we propose a mixed integer program (P) to maximize gα,β(x) over a set X:

The integer variables ti, i = 1, . . . , n are used to decide whether xi is positive or not. The M constant is used as usual to model disjunctive constraints depending on the sign of xi.

Program P for biOWA optimization can be specialized to solve the biOWA-MWE problem. It is sufficient to insert m boolean variables yj modeling elementary decisions on candidates (yj = 1 iff the candidate is selected in the current solution). Then x ∈ X must be replaced by the constraints xi = ∑mj=1 vijyj , i = 1, . . . , n and ∑nj=1 yj = k. We obtain a mixed-integer program with n + m boolean variables, 5n real variables and n2 + 4n + 1 linear constraints. Note that proposition 3 enables to reduce both the number of variables and constraints in this program. We indeed used only one set of permutation variables instead of the two needed if biOWA were only seen as a difference of two OWAs.

We have implemented the above model using the Gurobi 7.5.2 solver on a computer with 12GB of RAM, a Intel(R) Core(TM) i7 CPU 950 @ 3.07GHz processor. We used instances of the BiOWA-MWE problem of different sizes, the number of candidates (m) ranging from 20 to 100 and the number of voters (n) ranging from 10 to 100. Votes vij are randomly generated in the range J-10, 10K and k = m2 . Vectors α and β are randomly drawn and satisfy the conditions of Proposition 2. For each pair (n,m), the average time given in Table 2 is expressed in seconds and computed over 20 runs, with a timeout set to 1200 seconds.

Another linearization of biOWA could be obtained by exploiting a linearization of OWA due to Ogryczack [Ogryczak, 2003]. We have implemented and tested this second option but it appears to be less efficient. Its presentation has been omitted here to save space.

5 Robust Paths with Gains and Losses

The ability of OWA or biOWA optimization to generate solutions having a balanced utility vector can also be exploited in the context of robust optimization. The need of robustness appears in decision problems under uncertainty, when a number of plausible scenarios must be considered, each scenario impacting differently the values of solutions. In such contexts, uncertainty aversion leads to prefer robust solutions, i.e., solutions having a balanced profile over scenarios. In this context, the use of OWA-optimization has been closely investigated [Perny and Spanjaard, 2003; Kasperski and Zieli´nski, 2015]; It is therefore natural to study the use of biOWA when positive and negative values are present. For example, let us consider the robust path problem on a graph valued in a bipolar scale, modeling gains or losses induced by transitions between nodes.

More formally, let G = (V, E) be an acyclic directed graph where V is a finite set of nodes and E the set of arcs representing possible transitions between nodes. For all i = 1, . . . , n, let ui : E → R be a valuation function defined on E, ui(e) representing the gain (or loss) attached to e in scenario i. Valuations of arcs are supposed to be additive along a path and we want to find a biOWA-optimal path from s to t in G. This problem is NP-hard because biOWA includes OWA as special case and the OWA optimal path is known to be NP-hard for 2 scenarios and strongly NP-hard for an unbounded number of scenarios [Kasperski and Zieli´nski, 2015].

Program P introduced in Section 4 can be specialized to determine a biOWA-optimal path problem using standard max flow formulations of paths problems. To define the feasible set of solutions X let us introduce I(v) (resp. O(v)) the set of edges entering in v (resp. leaving v) for any v ∈ V and ye a boolean variable (set to 1 if e is selected in the path), for all e ∈ E. Then we add the following constraints:

We implemented the above model using the Gurobi solver on the computer described in Section 4. We made tests on random instances including up to m = 4000 nodes and n = 7 scenarios (in robust paths problems with a finite set of scenarios, one generally considers only a small number of scenarios, but 2 are sufficient to obtain a NP-hard problem). To generate instances, nodes are uniformly distributed on 25 different layers and arcs are randomly generated between nodes of consecutive layers, with a probability 1 2 . Valuations of arcs are generated within J-100, 100K with an uniform distribution. Weights α and β are randomly generated and satisfy the conditions of Proposition 2. Table 3 gives the average computational times obtained over 20 runs, with a timeout set to 1200 seconds for each run.

We can see that this new specialization of program P introduced in Section 4 can solve all instances in very reasonable time. To go further on the biOWA optimal path problem, we also investigated combinatorial algorithms in graphs. First, it is important to remark that it is not possible to construct a biOWA-optimal path with a simple dynamic programming algorithm progressively extending biOWA-optimal subpaths. This is due to the fact that preferences induced by a biOWA do not satisfy the Bellman principle. This phenomenon is already known for OWA and can be illustrated by the following:

We look for the gα,β-maximal path from 1 to 5 with α = ( 23 , 13 ) and β = ( 34 , 14 ). Subpath 1-2-4 leads to outcomes (5, 0) and gα,β(5, 0) = 53 . Subpath 1-3-4 leads to outcomes (2, 3) and gα,β(2, 3) = 7 3 . Therefore 1-3-4 is the best path from 1 to 4 according to biOWA valuations. Moreover, 1-34-5 yields (2, 3) + (0, 5) = (2, 8) and gα,β(2, 8) = 10 3 while 1-2-4-5 yields (5, 0) + (0, 5) = (5, 5) and gα,β(5, 5) = 5. Hence the biOWA-optimal path from 1 to 5 is 1-2-4-5 although the subpath 1-2-4 was not optimal from 1 to 4. This violation of the Bellman principle prevents local pruning of subpaths based on gα,β values in a constructive algorithm.

To overcome the problem we use a path-ranking algorithmic scheme which has been successfully used to solve multiobjective optimization problems in graphs under nonlinear scalarization models [Galand and Perny, 2007]. Let g be a non-linear function defining the scalar value of a path from its outcome vector, and assume that we can approximate g by a linear function h such that, for all x ∈ Rn verifies g(x) ≤ h(x). Then the path-ranking scheme consists in 1) scalarizing outcome vectors attached to arcs using the h function and 2) launching the enumeration of paths by decreasing values of h. To implement this approach, we need an efficient path-ranking algorithm. We use here an improved version of Eppstein algorithm proposed in [Jiménez and Marzal, 2003].

At any step of the ranking process, let x be the current solution and x∗ the solution with the highest g-value among those obtained so far. Whenever g(x∗ ) ≥ h(x), we know that x∗ is the optimal solution for this instance. Indeed, we have, for any y that will be enumerated after x in the ranking algorithm, g(x∗ ) ≥ h(x) ≥ h(y) ≥ g(y). Hence y cannot improve x∗ and the ranking process can be stopped, x∗ is the g-optimal solution.

To apply this scheme to g = gα,β we need a proper function h. To this end, we establish the following inequality:

Proposition 4. Let α and β be two positive vectors having decreasing components such that ∑ni=1 αi = ∑ni=1 βi = 1, then for all x ∈ Rn we have: gα,β(x) ≤ 1n ∑ni=1 xi.

Proof. It is well known that: α·x↑ ≤ 1n ∑ni=1 xi when α has decreasing components. As a direct consequence, we also have: β · x↓ ≥ 1n ∑ni=1 xi when β has decreasing components. Hence we have: gα,β = α·x+↑ -β·x-↓ ≤ 1n ∑ni=1 x+i - 1n ∑ni=1 x-i = 1n ∑ni=1 (x+i -x-i ) = 1n ∑ni=1 xi Thus, the average can be used as a valid h function in the ranking scheme, provided we use normalized vectors α and β. Table 4 provides the results obtained with the pathranking algorithm for the biOWA-optimal path problem. The instances are generated as before, using layered graphs. Computational times are obtained by averaging over 20 runs, with a timeout set to 1200 second for each run.

If we compare the results given in Table 4 with previous results obtained using Gurobi and the MIP model (Table 3), we observe that the ranking-path algorithm is faster on average. A deeper analysis shows that this is due to the fact that the gα,β-optimal path is often very well ranked according to the average (h). On the other hand, there exist instances where the gα,β-optimal path appears much later in the ranking process, yielding worse computational times. The previous approach based on MIP is less sensitive to this phenomenon.

6 Conclusion

In this paper we have identified the conditions under which a biOWA is monotonic w.r.t mean-preserving transfers reducing inequalities. This justifies its use in multiobjective optimization contexts when one wants to favor the determination of balanced Pareto-optimal solutions. Then we have proposed and tested computational models allowing to effectively determine biOWA-optimal solutions on combinatorial domains. We presented two possible applications, first in the context of fair multiagent optimization and then in the context of robust optimization. Many other problems could be considered as well due to generality of the proposed computational models (MIP and ranking algorithm).

One specifity of biOWA is to perform a symmetric aggregation of its arguments. Although this property is highly desirable in Social Choice (when every agent has the same importance) or in robust optimization under total uncertainty (when all scenarios are equally likely), there are other situations where different weights or probabilities must be attached to components (criteria, scenarios or individual values), thus breaking the symmetry. The computational models proposed in this paper could very likely be extended to the case of weighted OWA [Torra, 1997], CPT and other classes of general Choquet integrals [Grabisch et al., 2009] to perform weighted aggregation on bipolar valuation scales in optimization problems.

Acknowledgements

This work is supported by the ANR project CoCoRICoCoDec ANR-14-CE24-0007-01.