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

Olivier Sobrie, Nicolas Gillis, Vincent Mousseau, Marc Pirlot

TL;DR

This paper introduces UTA-poly and UTA-splines, novel methods for eliciting additive value functions in multi-criteria decision analysis. By replacing traditional piecewise linear marginal functions with polynomials and splines, these methods offer more interpretable and flexible models, leveraging semidefinite programming for efficient inference.

What Problem Does This Paper Address?

In multi-criteria decision analysis (MCDA), an additive value function is often used to represent a decision-maker's preferences. This function aggregates scores from individual criteria to assign a single value to each alternative. A key challenge is determining the shape of the "marginal value functions" – how a decision-maker values performance on each criterion. Traditional methods like UTA (Unicriteria Decision Aid) approximate these marginals using piecewise linear functions, which can be rigid and lack interpretability, especially when breakpoints are arbitrarily chosen. This paper addresses this by proposing methods that use smoother, more flexible functional forms (polynomials and splines) for these marginals, aiming for better interpretability and descriptive power.

Methods

The core innovation lies in replacing piecewise linear marginal functions with more flexible forms and employing semidefinite programming (SDP) for inference.

  • UTA-poly: This method infers marginal value functions that are polynomials of a chosen degree. To ensure these polynomials are non-negative and monotone (as required for value functions), the authors leverage SDP. Monotonicity is enforced by ensuring the derivative of the polynomial is a sum of squares, a condition that can be formulated within an SDP framework.
  • UTA-splines: This approach further generalizes UTA-poly by allowing marginals to be composed of multiple polynomial pieces (splines). This allows for more complex shapes while maintaining continuity of derivatives at the connection points (breakpoints), leading to smoother overall marginal functions. Again, SDP is used to learn the parameters of these splines, ensuring non-negativity and monotonicity on the relevant criterion domains.

The authors frame the problem as an optimization task, minimizing deviations from stated preferences, while imposing constraints on the shape of the marginal functions (non-negativity, monotonicity) using SDP.

Datasets

The paper uses artificial datasets generated for experimental purposes. These datasets are constructed by defining hypothetical additive value function models (with varying marginal shapes like sigmoids, exponentials, and polynomials) and then simulating a decision-maker's ranking of alternatives based on these models. These simulated rankings form the basis for learning.

Key Insights and Ideas

  • Smoothness Enhances Interpretability: Replacing abrupt piecewise linear functions with smooth polynomials and splines makes the inferred marginal value functions more intuitive and easier for decision-makers to understand and accept.
  • SDP as a Powerful Tool for MCDA: The paper demonstrates that semidefinite programming is a capable and efficient tool for learning complex, constrained functional forms (polynomials and splines) in MCDA, extending beyond the traditional linear programming used in UTA.
  • Flexibility vs. Simplicity: While more flexible models (higher-degree polynomials, more spline pieces) generally improve the accuracy of ranking retrieval, there's a trade-off with model complexity. The authors explore this trade-off through experiments.
  • Generalization of UTA: UTA-splines is presented as a generalization of both standard UTA and UTA-poly, offering a unified framework for learning additive value functions with increasingly sophisticated marginal representations.

Key Results

The experimental results, conducted on artificial datasets, show that:

  • Improved Ranking Accuracy: Both UTA-poly and UTA-splines generally achieve better ranking accuracy (measured by Spearman distance and Kendall Tau) compared to standard UTA, especially when the underlying true marginal functions are non-linear.
  • Degree Matters: For UTA-poly, increasing the degree of the polynomials generally leads to better model retrieval, up to a certain point.
  • Splines Offer More Flexibility: UTA-splines, by using multiple polynomial pieces, can better approximate complex marginal functions, especially when the number of pieces increases.
  • Computational Efficiency: Despite using SDP, the inference process is computationally efficient, with solving times typically in the order of seconds, making it suitable for interactive use with decision-makers.

Limitations and Future Work

  • Uniqueness of Solutions: Similar to standard UTA, the learned models might not be unique. The authors acknowledge that it would be interesting to characterize these situations and select solutions that are most suited to the DM, potentially by introducing regularization terms.
  • Complexity of Spline Placement: While UTA-splines offers flexibility, the placement of breakpoints can influence results. The current implementation uses equally spaced breakpoints, and future work could explore adaptive breakpoint selection.
  • Comparison with Classical UTA: While the paper demonstrates the superiority of UTA-poly and UTA-splines in certain scenarios, a more extensive experimental comparison with classical UTA methods across a wider range of problems and datasets would be valuable.
  • Robust Ordinal Regression: Extending these methods to the paradigm of Robust Ordinal Regression is suggested as a promising future direction.

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