TL;DR
This paper introduces "biOWA," a novel aggregation function that extends the standard Ordered Weighted Averaging (OWA) to handle bipolar scales (positive and negative values). This allows for fairer decision-making in complex scenarios, particularly in combinatorial optimization problems like multi-winner elections and robust pathfinding, by better reflecting nuanced preferences.
What Problem Does This Paper Address?
Traditional decision-making models often treat positive and negative outcomes symmetrically, which doesn't always align with how humans perceive gains and losses. For instance, people often care more about avoiding losses than achieving equivalent gains. This is particularly relevant in multicriteria decision-making and collective choice, where evaluations can be on a bipolar scale (e.g., -5 to +5). Standard aggregation methods like OWA, while useful for fairness by balancing outcomes, struggle to capture these asymmetric preferences when dealing with both positive and negative evaluations. The paper addresses this gap by proposing biOWA, an extension that allows for distinct treatment of positive and negative evaluations, leading to more nuanced and fair optimization in complex decision problems.
Methods
The core contribution is the biOWA (bipolar Ordered Weighted Averaging) aggregation function. It's defined as the difference between two standard OWA aggregations: one for positive components of the input vector and one for negative components. This allows for separate weighting schemes for gains and losses.
Key methodological contributions include:
- Formal Definition of biOWA: A precise mathematical definition is provided, showing how it generalizes standard OWA.
- Monotonicity Properties: The paper establishes conditions under which biOWA is monotonic with respect to weak Pareto dominance and Mean-Preserving Transfers Reducing Inequalities (MPTRI), which are crucial for ensuring fair optimization.
- Linearization for Optimization: A significant technical contribution is the linearization of the biOWA function. This is achieved by expressing it as a minimum over permutations of weighted sums, which can then be formulated as a linear program (LP). This linearization is essential for solving biOWA optimization problems using standard Mixed-Integer Programming (MIP) solvers.
- Two Applications: The authors demonstrate the practical utility of biOWA by applying it to two combinatorial optimization problems:
- Multi-Winner Elections: Modeling fair election outcomes where voters can express approval and disapproval with varying intensity.
- Robust Pathfinding: Finding paths in graphs that are optimal under a bipolar scale, considering both gains and losses across different scenarios.
Datasets
Not discussed in the paper. The paper uses synthetic data generated for experiments in the context of the proposed applications.
Key Insights and Ideas
- Beyond Symmetry: The paper highlights that simply averaging or using standard OWA on bipolar scales can lead to suboptimal or unfair outcomes because it ignores the psychological asymmetry in how people perceive gains and losses.
- biOWA as a Flexible Tool: biOWA offers a principled way to incorporate this asymmetry by allowing different weights for positive and negative evaluations, leading to more "balanced" and "fair" solutions in complex decision scenarios.
- Bridging Theory and Practice: The linearization of biOWA into an LP formulation is a critical step, enabling the use of powerful existing MIP solvers to tackle previously intractable biOWA optimization problems in combinatorial domains.
- Fairness in Elections and Robustness: The applications demonstrate that biOWA can lead to more satisfactory outcomes in scenarios like elections (where voter satisfaction is key) and robust decision-making (where avoiding worst-case scenarios is important).
Key Results
The paper demonstrates the practical efficiency of the proposed biOWA models through numerical tests:
- Multi-Winner Election (biOWA-MWE): Using MIP, the model solved instances with up to 100 voters and 100 candidates within reasonable time limits (average times ranging from 0.04s to 342.24s depending on problem size, with a 1200s timeout).
- Robust Paths: The MIP formulation for biOWA-optimal paths was also efficient, solving instances with up to 4000 nodes and 7 scenarios in average times ranging from 1.08s to 444.50s (with a 1200s timeout).
- Path Ranking Algorithm: A path-ranking algorithm was also proposed and tested for the robust path problem, showing faster average performance than the MIP approach on many instances, though it was more sensitive to specific problem structures.
Limitations and Future Work
- Symmetry Assumption: The current biOWA formulation assumes symmetry in how the aggregation is applied to positive and negative components (i.e., the same set of permutations is used). The authors note that future work could extend this to weighted OWA or other aggregation functions to handle situations where different weights or probabilities must be attached to components, breaking this symmetry.
- Computational Complexity: While the MIP formulations are effective, biOWA optimization in combinatorial domains remains NP-hard in general. The paper focuses on specific applications and efficient linearization techniques.
- Further Applications: The authors suggest that the proposed computational models (MIP and ranking algorithm) are general enough to be applied to many other combinatorial optimization problems involving bipolar scales.
- Alternative Linearizations: The paper briefly mentions exploring alternative linearizations of OWA (and by extension, biOWA) but found one approach less efficient. Further research into optimal linearization strategies could be beneficial.
Summary updated