If we have some collection of decision trees with single-variable splits and a constant value at each leaf node, the average over all trees gives some function from $\mathbb{R}^n \to \mathbb{R}$. Is it possible to efficiently find the subspace on which this function achieves its maximum? Enumerating all intersections could take exponential time in e.g. the case where each tree is a stump which bisects a different dimension.
It is possible to do better by computing bounds and doing some pruning, but I wonder whether a polynomial-time solution is possible.
If the leaf values are taken from $\{0, 1\}$ then this is a restricted max-clique problem, but I suspect it should be possible to exploit the decision-tree structure to create a faster algorithm.
Any thoughts?