Picking a Representative Set of Solutions in Multiobjective Optimization: Axioms, Algorithms, and Experiments

AI summary

Overview

Research area: Multiobjective optimization, Pareto pruning, computational social choice (multiwinner voting), and computational geometry.

Technical level: Advanced. The paper assumes familiarity with NP-hardness reductions, axiomatic social choice, and multiobjective optimization terminology, though the central ideas are explained discursively.

Scope: The paper analyzes quality measures used to select a small representative subset of Pareto optimal solutions, providing an axiomatic comparison of existing and new measures alongside a complexity classification and an experimental evaluation on three benchmark datasets.

What This Paper Is About

When a decision problem has multiple conflicting objectives, there is no single best solution: every Pareto optimal solution is a legitimate candidate, each reflecting a different tradeoff. Because the Pareto front is often too large for a decision maker to review, the "Pareto pruning" problem asks for a fixed-size subset of solutions that best represents the full front according to some quality measure.

This paper asks which quality measures are actually sensible, how hard it is to compute optimal subsets for each of them, and how the resulting slates differ in practice. The authors reframe Pareto pruning as a multiwinner voting problem, in which solutions are candidates and objectives are voters.

Key Contributions

1. An axiomatic analysis of Pareto pruning measures. The authors propose five axioms (monotonicity, ε-split proofness, extremism monotonicity, standout consistency, and outlier consistency) and determine which of the three measures under study satisfy each one, using these results to expose unintuitive behaviors of two widely used measures.

2. A new quality measure, directed coverage. Motivated by the flaws the axioms reveal in uniformity and coverage, the authors introduce directed coverage, which evaluates how well one solution covers another using only the objectives in which the covered solution is better, rather than the symmetric Manhattan distance.

3. A complexity classification. The authors prove NP-hardness for uniformity and coverage for three objectives (previously known to be tractable for two), prove NP-hardness for directed coverage for three objectives, extend all three to ordinal and approval objectives, and show that approval objectives make all three problems polynomial-time solvable for any fixed number of objectives. Along the way they supply a missing proof that Discrete k-Center for the Manhattan distance is NP-hard in two dimensions.

4. An experimental comparison. The authors compare slates produced by optimizing each of the three measures across three datasets, evaluating them with five different measures.

Main Findings

• Existing measures fail natural consistency conditions. Uniformity and coverage both violate monotonicity, meaning that strictly improving a selected solution's performance on one or more objectives can cause it to be dropped from the slate. Directed coverage satisfies monotonicity, because improving a solution can only increase its lead over others and decrease how well others lead it.

• Only uniformity resists splitting. Uniformity satisfies ε-split proofness, so no solution can be replaced by two arbitrarily close solutions that both get selected. Coverage and directed coverage both violate this axiom, since it can be beneficial for them to select two nearly identical solutions that cover different halves of the space.

• Uniformity satisfies extremism monotonicity; the other two do not. Pushing a solution that is already most extreme in some objective further away from the others cannot cause its exclusion under uniformity. Coverage and directed coverage both violate this axiom.

• Only directed coverage is standout consistent. The authors define a standout alternative as one whose weakest lead over any other alternative exceeds the strongest lead any other alternative has against it. Directed coverage always selects such an alternative; uniformity and coverage do not, because they ignore which of two solutions is more efficient when deciding between them.

• Only coverage is outlier consistent. If a solution is farther from every other solution than any two non-outlier solutions are from each other, coverage guarantees its selection for any k ≥ 2, while uniformity and directed coverage do not.

• Two objectives are tractable, three are hard. Uniformity and coverage Pareto pruning are polynomial-time solvable for two objectives (a result of Vaz et al. [2015]), and directed coverage pruning is solvable in O(|A|k + |A| log |A|) for at most two objectives. All three become NP-hard at three objectives.

• Approval objectives change the picture. With approval objectives, the number of pairwise non-equivalent alternatives is at most 2^d, so all three problems are solvable in polynomial time for any fixed number of objectives. This extends to ℓ-valued objectives for fixed ℓ. When the number of approval objectives is unbounded, all three problems are NP-hard.

• Ordinal objectives remain partly unresolved. All three problems are NP-hard for ordinal objectives when the number of objectives is unbounded, but the complexity for a fixed number of three or more ordinal objectives is left open.

• Coverage and uniformity are related. The authors show that the optimal coverage value with k points and the optimal uniformity value with k + 1 points differ by a factor of at most 2.

• Different measures produce distinctly different slates. In experiments on ZDT, DTLZ, and PGMORL, each of the three methods yields different results. Uniformity-optimized slates score at 100.0% on uniformity but reach coverage values between 74.7% (ZDT, k = 25%) and 144.8% (PGMORL, k = 25%), and directed coverage values as high as 254.7% (PGMORL, k = 25%).

• Directed coverage selects more efficient solutions. On ZDT, directed coverage reaches hypervolume of 99.3%, 99.8%, and 99.9% at k = 5%, 10%, and 25%, and average sum objective of 99.1%, 99.5%, and 99.6%. On PGMORL it reaches 100.0% on both measures at all three values of k. Coverage-optimized slates also depend on the setting: on ZDT its directed coverage rises from 201.0% at k = 5% to 182.3% at k = 25%.

Methodology in Plain English

The authors begin with a formal problem statement. A multiobjective optimization instance is preprocessed down to its Pareto optimal alternatives, each treated as a point in ℝ^d. The task is to pick a size-k subset, called a slate, that represents the whole set well. Three desiderata guide this: diversity (selected solutions should not resemble each other), representativity (every unselected solution should be near a selected one), and efficiency (the slate should contain high-quality solutions).

They then translate the problem into the language of multiwinner voting, where solutions play the role of candidates and each objective plays the role of a voter. This lets them import axiomatic reasoning from social choice: they state five formal properties a quality measure might have and check which measures satisfy them, with proofs deferred to an appendix.

For the algorithmic part, they draw on classical problems from computational geometry — Discrete k-Center, which minimizes the maximum distance from any point to its nearest selected point, and p-Dispersion, which maximizes the minimum pairwise distance among selected points. They observe that coverage and uniformity are essentially these problems restricted to Pareto optimal points, then build hardness reductions for three objectives by embedding two-dimensional constructions into a specially chosen hyperplane in three dimensions, where no point dominates another. For directed coverage they need a triangular grid and an embedding that preserves directed distances exactly.

For the experiments, the authors formulate each optimization problem as an integer linear program and solve it with Gurobi. They use three datasets: ZDT (six instances, two objectives), DTLZ (seven instances, three objectives), and PGMORL (six instances, two objectives, based on simulated agents). For the six instances whose Pareto front exceeds 200 alternatives, they randomly sample 200 alternatives to keep the problems tractable. They test three slate sizes, expressed as percentages of the front size (5%, 10%, and 25%), and evaluate the resulting slates with five measures, normalizing each at the instance level against the best solution found.

Why This Matters

Impact on research. Pareto pruning has accumulated many quality measures but little formal comparison between them. This paper supplies explicit criteria for judging such measures, shows that two of the most widely used ones behave unintuitively, establishes a sharp tractability boundary at three objectives, and connects multiobjective optimization to social choice and computational geometry. It also offers a new perspective on multiwinner voting by focusing on "satisfying" candidates rather than voters.

Real-world applications.

• Systems design and engineering, where design teams must choose among many tradeoff configurations of cost, performance, and reliability.
• Operations research and scheduling, where planners need a small menu of schedules balancing competing criteria.
• Healthcare decision-making, where treatment plans trade off efficacy against side effects and cost.
• Reinforcement learning with multiple rewards, as in the PGMORL benchmark, where trained agents correspond to different tradeoff policies.

Industry relevance. Any workflow that generates a large set of non-dominated solutions — multiobjective evolutionary algorithms, multiobjective integer programming, or multiobjective reinforcement learning — needs a principled way to shrink that set before presenting it to a human. The paper's complexity results tell practitioners when an exact optimizer is realistic (two objectives, or approval objectives) and when heuristics are needed (three or more objectives), and its GitHub repository provides the code and additional results.

Future Directions

• Resolve the ordinal case for fixed numbers of objectives. The complexity of all three pruning problems with three or more ordinal (ranking-based) objectives remains open; the paper explicitly notes that the bijection constraint is hard to exploit algorithmically but too restrictive for controlling distances in reductions.
• Extend the axiomatic framework. The five axioms are not an exhaustive catalog, and the authors note that the desirability of extremism monotonicity, standout consistency, and outlier consistency is more subjective, tied to which desideratum a decision maker prioritizes.
• Analyze additional quality measures. The framework could be applied to the broader family of measures catalogued in prior surveys rather than just uniformity, coverage, and directed coverage.
• Connect the theoretical guarantees to practice more tightly. The paper reports that the choice of measure drives the properties of the selected slate; further work could characterize which measure suits which class of multiobjective problem, or how the measures behave on fronts with more than the 200 alternatives sampled here for feasibility.

Target Audience

Researchers and graduate students in multiobjective optimization, computational social choice, and algorithmic game theory who are interested in the theory of solution-set selection. It is also relevant to practitioners who deploy multiobjective evolutionary or reinforcement learning methods and need to justify how they reduce a Pareto front before presenting it to a decision maker. Readers without a background in complexity theory or axiomatic social choice will need to work through the appendix material to follow the proofs in detail.

Authors’ abstract

Many real-world decision-making problems involve optimizing multiple objectives simultaneously, rendering the selection of the most preferred solution a non-trivial problem: All Pareto optimal solutions are viable candidates, and it is typically up to a decision maker to select one for implementation based on their subjective preferences. To reduce the cognitive load on the decision maker, previous work has introduced the Pareto pruning problem, where the goal is to compute a fixed-size subset of Pareto optimal solutions that best represent the full set, as evaluated by a given quality measure. Reframing Pareto pruning as a multiwinner voting problem, we conduct an axiomatic analysis of existing quality measures, uncovering several unintuitive behaviors. Motivated by these findings, we introduce a new measure, directed coverage. We also analyze the computational complexity of optimizing various quality measures, identifying previously unknown boundaries between tractable and intractable cases depending on the number and structure of the objectives. Finally, we present an experimental evaluation, demonstrating that the choice of quality measure has a decisive impact on the characteristics of the selected set of solutions and that our proposed measure performs competitively or even favorably across a range of settings.