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