*Gildas Jeantet, Olivier Spanjaard*

This paper is devoted to the computation of optimal strategies in automated sequential decision problems. We consider here problems where one seeks a strategy which is optimal for rank dependent utility (RDU). RDU generalizes von Neumann and Morgenstern's expected utility (by probability weighting) to encompass rational decision behaviors that EU cannot accomodate. The induced algorithmic problem is however more difficult to solve since the optimality principle does not hold anymore. More crucially, we prove here that the search for an optimal strategy (w.r.t. RDU) in a decision tree is an NP-hard problem. We propose an implicit enumeration algorithm to compute optimal rank dependent utility in decision trees. The performances of our algorithm on randomly generated instances and real-world instances of different sizes are presented and discussed.

*Subjects:* 15.5 Decision Theory; 9.2 Computational Complexity

*Submitted: *Jun 27, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.