Complexity of Solving Decision Trees with Skew-Symmetric Bilinear Utility

Hugo Gilbert, Olivier SpanjaardUAI 2017

Abstract

Standard Expected Utility (EU) models often fail to capture human decision-making nuances like intransitive preferences or the Allais paradox. This paper investigates the computational complexity of planning in decision trees using more flexible models: Skew-Symmetric Bilinear (SSB) utility and Weighted Expected Utility (WEU). We demonstrate that while finding optimal deterministic plans under SSB is NP-hard, the problem becomes polynomial-time solvable when allowing for randomized strategies or when using the WEU model.

Introduction

In classical decision theory, Expected Utility (EU) is the bedrock of planning under risk. However, EU's reliance on the independence axiom and transitivity makes it descriptively inadequate for many real-world behaviors. Models like SSB and WEU offer greater flexibility but at a cost: they violate the Bellman optimality principle. Without this principle, standard dynamic programming ("rolling back") cannot be directly applied, necessitating a deeper look into the algorithmic complexity of these non-standard models.

Decision Models and Strategies

The research focuses on two primary utility frameworks:

  1. Skew-Symmetric Bilinear (SSB) Utility: A general model capable of representing both intransitive and non-independent preferences.
  2. Weighted Expected Utility (WEU): A transitive subset of SSB that still accounts for violations of the independence axiom, such as the Allais paradox.

The paper evaluates these models across decision trees, which represent finite-horizon sequential decision problems.

A typical decision tree structure with decision nodes (squares) and chance nodes (circles).

Agents can employ two types of strategies:

  • Deterministic: Choosing a single action at each decision point.
  • Randomized: Choosing a probability distribution over actions.

The authors adopt a "resolute" behavior model: instead of recalculating the best move at every step (which can lead to "money pump" cycles in these models), the agent commits to a plan that is optimal from the perspective of the starting point (the root).

Computational Complexity and Key Results

The core contribution of this work is the classification of the computational difficulty of finding optimal strategies. The authors prove that the jump from deterministic to randomized plans in the SSB model represents a shift from NP-hardness to polynomial-time solvability.

Complexity of finding optimal strategies across utility models and plan types.

Key findings include:

  • SSB Complexity: Finding an optimal deterministic SSB plan is NP-hard (proven via a reduction from 3-SAT). However, randomized SSB plans can be found in polynomial time using a Linear Programming (LP) formulation. While effective, the LP approach's variable count grows exponentially with tree depth.
  • WEU as a "Sweet Spot": WEU is identified as a computationally efficient middle ground. It can handle the Allais paradox while remaining solvable in polynomial time for both deterministic and randomized plans. The authors propose using fractional programming methods (Megiddo’s and Dinkelbach’s) to solve WEU trees by iteratively applying standard EU "rolling back" procedures.

Empirical Evaluation

To test these theoretical findings, the authors conducted experiments on:

  • Synthetic Binary Trees: Scaling up to 20 levels deep (~350,000 nodes). Dinkelbach’s method (DIN) proved exceptionally fast, solving depth-20 trees in under a second on a standard laptop.
  • "Who Wants to Be a Millionaire?": A real-world model with up to 80 million nodes. Both DIN and Megiddo’s (MEG) algorithms successfully found optimal strategies with very few iterations, demonstrating the practical viability of these approaches for large-scale problems.

Conclusion

This research clarifies the algorithmic landscape for non-standard utility models in sequential decision-making. By showing that randomization or the use of the WEU model can restore computational tractability, the authors provide a path forward for more behaviorally accurate automated planning. Future work involves extending these results to infinite-horizon Markov Decision Processes (MDPs) and addressing the challenges of eliciting model parameters from human subjects.

Summary updated

BibTeX
@inproceedings{gilbert2017complexity,
  author = {Hugo Gilbert and Olivier Spanjaard},
  title = {{Complexity of Solving Decision Trees with Skew-Symmetric Bilinear Utility}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2017},
}
Figure