On the Variation of Max Regret with Respect to the Scaling of the Objectives

In a multi-objective optimisation problem, when there is uncertainty regarding the correct user preference model, max regret is a natural measure for how far an alternative is from being necessarily optimal (i.e., optimal with respect to every candidate preference model). It can be used for recommending a relatively safe choice to the user, or used in the generation of an informative query, and in the decision to terminate the user interaction, because an alternative is sufficiently close to being necessarily optimal. We consider a common and simple form of user preference model: a weighted average over the objectives (with unknown weights). However, changing the scale of an objective by a linear factor leads to an essentially different set of preference models, and this changes the max regret values (and potentially their relative ordering), sometimes very considerably. Since the scaling of the objectives is often partly subjective and somewhat arbitrary, it is important to be aware of how sensitive the max regret values are to the choices of scaling of the objectives. We give mathematical results that characterise and enable computation of this variability, along with an asymptotic analysis.