The Azimuth Project
Pareto front (Rev #2)

Pareto front

Idea

The Pareto front (or Pareto frontier) is a framework for partially evaluting a set of “actions” with multi-dimensional outputs assuming a very weak “desirability” partial ordering which only applies only when one processes is better (or at least as good) for all the outputs. It is useful for reducing a set of candidates prior to further analysis.

Details

Suppose we’re trying to acheive something which is can be parameterised by a vector v=(v 0,,v N)\vec{v}=(v_0,\dots,v_N) of real-valued output variables, where for each variable a bigger value is “better”. (Note that by negating “obvious variables” we can convert to a problem where for each variable a larger value is better than a smaller value.)

As an example, consider a very, very simplified view of “improving the environment”. This might have the following variables

varinterpretation
v 0v_0money saved
v 1v_1average human standard of living
v 2v_2expected number of flooding events
v 3v_3number of species saved

For any particular action we can assign it a value for each of these variables (or at least a value estimated from a model). Note that one might expect v 0v_0 is almost always negative as most actions will involve spending money; the “obvious” variable to use would be money spent, but with that choice better corresponds to decreasing.

It would be generally agreed that for each variable a higher value is better, but the framework hasn’t assigned relative importances to each variable (e.g., we haven’t said know how much money it is worth spending to save 1 species, or even that this value is linear). Just about the only ordering that can be done without further specification is

  • strict dominance: v\vec{v} strictly dominates w\vec{w} (or vwv\succ w) if v iw iv_i\ge w_i for every ii and at least one inequality is strict.

Then given a set SS of possible actions (which might be a process, a technology, etc) one can discard any actions which are strictly dominated by another element of SS to get a reduced set of actions SS' which is called the Pareto front. This name is inspired by the way that, in NN-dimensions, the remaining points are the “outer shell” of SS with the discarded points on the interior. This is shown in 22-D in the following plot:

<embed src='http://upload.wikimedia.org/wikipedia/commons/b/b7/Front_pareto.svg'></embed><object data='http://upload.wikimedia.org/wikipedia/commons/b/b7/Front_pareto.svg' type='image/svg+xml'></object>

(Image from wikipedia page referenced below.) Another description of the Pareto front is as the set of maximal elements under the partial order \succ.

The intuitive meaning of the Pareto front is that elements which are not on the front are never the best choice, because there’s some element on the front which is at least as good on all variables. In contrast, elements which are on the front could be the best choice, depending how the user depends to trade-off the weights of the various variables.

(Note that this page describes a small subset of the ideas and mathematics based on Pareto efficiency which are relevant to Azimuth. Further details can be found on the wikipedia page.)

Usefulness of the Pareto front

The intuitive way of approaching dealing with multidimensional outputs would be to define a scalar score function s: Ns:\mathbb{R}^N \leftarrow \mathbb{R} and then use a standard optimisation technique to find the best element of SS (which is possibly non-unique). This has two problems:

  1. If multiple interested parties are performing the analysis, they are likely to disagree on the precise form of ss, blocking any progress.

  2. Even with only one analyser, it is often difficult to formalise scalar mapping that reflects all the different “intuitive values”. In particular, experience in other fields of use is that often the optimal s(v)s(\vec{v}) will be at some extreme point of the space that is, upon reflection of the “intuitive values”, actually a poor choice. For example, given a numerical weighting between money saved and species saved, a scalar optimisation function may have a minimum of 0 money saved and no species saved. In contrast, the Pareto front gives a reduced set of possible candidates which can be analysed further.

Questions

  1. Visualising the Pareto front is obviously very informative, but for greater than 3 dimensions this isn’t directly possible. Are there good ways to project to a viewable dimension preserving useful features?

  2. The Pareto front is one way to make “partial decisions” based on weak ordering: are there other ways that are also useful for decision making.

  3. There are other mathematical optimisation problems, e.g., linear programming, with other attractive properties. Are there any connections/extensions to other problems.

References