Sorted Pareto Dominance: An Extension to Pareto Dominance and Its Application in Soft Constraints

The Pareto dominance relation compares decisions with each other over multiple aspects, and any decision that is not dominated by another is called Pareto optimal, which is a desirable property in decision making. However, the Pareto dominance relation is not very discerning, and often leads to a large number of non-dominated or Pareto optimal decisions. By strengthening the relation, we can narrow down this nondominated set of decisions to a smaller set, e.g., for presenting a smaller number of more interesting decisions to a decision maker. In this paper, we look at a particular strengthening of the Pareto dominance called Sorted-Pareto dominance, giving some properties that characterise the relation, and giving a semantics in the context of decision making under uncertainty. We then examine the use of the relation in a Soft Constraints setting, and explore some algorithms for generating Sorted-Pareto optimal solutions to Soft Constraints problems.