UTA-poly and UTA-splines: Additive value functions with polynomial marginals

Olivier Sobrie, Nicolas Gillis, Vincent Mousseau, Marc Pirlot

Introduction

Multiple Criteria Decision Analysis (MCDA) provides a framework for ranking alternatives based on multiple, often conflicting, criteria. A cornerstone of this field is the UTA method, which constructs an additive value function from a set of preference rankings provided by a decision-maker. Traditionally, these models rely on piecewise linear marginal value functions. While computationally efficient, these functions often fail to capture the smooth, continuous nature of human preferences and economic utility.

The Limitations of Piecewise Linear Models

The standard UTA approach models marginal value functions as a series of straight lines connected at specific breakpoints. This methodology presents two significant challenges:

  1. Interpretability: Human utility typically follows smooth curves, such as those representing diminishing marginal returns. The "sharp corners" of piecewise linear models are often economically unjustifiable and do not reflect natural human reasoning.
  2. Flexibility: Capturing complex preference shapes, such as sigmoids or plateaus, requires an impractical number of breakpoints in a linear model. Without sufficient breakpoints, the model may fail to differentiate between distinct alternatives.

Methodology: UTA-poly and UTA-splines

To address these issues, this paper introduces UTA-poly and UTA-splines. These methods replace piecewise linear segments with smooth polynomial curves.

  • UTA-poly: Models each marginal as a single polynomial of degree $d$.
  • UTA-splines: A generalization that models each marginal as a spline (a sequence of piecewise polynomials) that is mathematically forced to be smooth (continuous up to the 1st or 2nd derivative) at the connection points.
Marginal value functions $u_1$ and $u_2$ modeled with smooth curves (solid) versus piecewise linear approximations (dashed).

A critical requirement for these functions is monotonicity—ensuring that a higher value in a criterion always results in a higher or equal score. To enforce this, the authors employ Hilbert's Sum of Squares (SOS) theorem. By constraining the derivative of the polynomial to be an SOS, they guarantee monotonicity. This formulation shifts the optimization from Linear Programming to Semidefinite Programming (SDP), a powerful class of convex optimization.

Key Results

The proposed methods were tested against artificial datasets designed to simulate complex preference models. The results demonstrate that increasing the polynomial degree or the number of spline pieces significantly improves the model's ability to recover the "true" ranking of alternatives, as measured by Spearman distance and Kendall Tau correlation.

Comparison of UTA and UTA-poly scores, demonstrating how UTA-poly provides better differentiation between alternatives.

As shown in the comparison above, traditional UTA scores can fail to differentiate between alternatives that have distinct underlying values (all scoring 0.5 in this example), whereas UTA-poly provides a more nuanced and accurate scoring system. Furthermore, despite the increased complexity of SDP, the methods remain computationally efficient, with even large-scale problems solving in under six seconds.

Conclusion

UTA-poly and UTA-splines offer a significant advancement in preference modeling by providing a smooth, flexible, and economically intuitive alternative to traditional piecewise linear methods. By leveraging SOS polynomials and SDP, the authors have created a unified framework that generalizes existing UTA methods while improving accuracy and interpretability. Future work will focus on regularization to prevent overfitting and validation against real-world datasets.

Summary updated

Abstract

Additive utility function models are widely used in multiple criteria decision analysis. In such models, a numerical value is associated to each alternative involved in the decision problem. It is computed by aggregating the scores of the alternative on the different criteria of the decision problem. The score of an alternative is determined by a marginal value function that evolves monotonically as a function of the performance of the alternative on this criterion. Determining the shape of the marginals is not easy for a decision maker. It is easier for him/her to make statements such as "alternative $a$ is preferred to $b$". In order to help the decision maker, UTA disaggregation procedures use linear programming to approximate the marginals by piecewise linear functions based only on such statements. In this paper, we propose to infer polynomials and splines instead of piecewise linear functions for the marginals. In this aim, we use semidefinite programming instead of linear programming. We illustrate this new elicitation method and present some experimental results.
BibTeX
@article{sobrie2018uta,
  author = {Olivier Sobrie and Nicolas Gillis and Vincent Mousseau and Marc Pirlot},
  title = {{UTA-poly and UTA-splines: Additive value functions with polynomial marginals}},
  journal = {Eur. J. Oper. Res.},
  year = {2018},
  url = {https://openreview.net/forum?id=8UD3MEoJr4pG},
}
Figure