Complexity of Solving Decision Trees with Skew-Symmetric Bilinear Utility

Hugo Gilbert, Olivier Spanjaard
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:181-190, 2017.

Abstract

We study the complexity of solving decision trees with a Skew-Symmetric Bilinear (SSB) utility function. The SSB model is an extension of Expected Utility (EU) with enhanced descriptive possibilities. Unlike EU, the optimality principle does not hold for SSB, which makes its optimization trickier. We show that determining an SSB optimal plan is NP-hard if one only considers deterministic plans while it is polynomial time if one allows randomized plans. With the Weighted EU model (a special case of SSB), the problem becomes polynomial in both settings. Our numerical tests show the operationality of the methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-gilbert17a, title = {Complexity of Solving Decision Trees with Skew-Symmetric Bilinear Utility}, author = {Gilbert, Hugo and Spanjaard, Olivier}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {181--190}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/gilbert17a/gilbert17a.pdf}, url = {https://proceedings.mlr.press/r15/gilbert17a.html}, abstract = {We study the complexity of solving decision trees with a Skew-Symmetric Bilinear (SSB) utility function. The SSB model is an extension of Expected Utility (EU) with enhanced descriptive possibilities. Unlike EU, the optimality principle does not hold for SSB, which makes its optimization trickier. We show that determining an SSB optimal plan is NP-hard if one only considers deterministic plans while it is polynomial time if one allows randomized plans. With the Weighted EU model (a special case of SSB), the problem becomes polynomial in both settings. Our numerical tests show the operationality of the methods.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Complexity of Solving Decision Trees with Skew-Symmetric Bilinear Utility %A Hugo Gilbert %A Olivier Spanjaard %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-gilbert17a %I PMLR %P 181--190 %U https://proceedings.mlr.press/r15/gilbert17a.html %V R15 %X We study the complexity of solving decision trees with a Skew-Symmetric Bilinear (SSB) utility function. The SSB model is an extension of Expected Utility (EU) with enhanced descriptive possibilities. Unlike EU, the optimality principle does not hold for SSB, which makes its optimization trickier. We show that determining an SSB optimal plan is NP-hard if one only considers deterministic plans while it is polynomial time if one allows randomized plans. With the Weighted EU model (a special case of SSB), the problem becomes polynomial in both settings. Our numerical tests show the operationality of the methods. %Z Reissued by PMLR on 04 October 2026.
APA
Gilbert, H. & Spanjaard, O.. (2017). Complexity of Solving Decision Trees with Skew-Symmetric Bilinear Utility. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:181-190 Available from https://proceedings.mlr.press/r15/gilbert17a.html. Reissued by PMLR on 04 October 2026.

Related Material