Leaf Rewards, Deterministic | Leaf Rewards, Stochastic | Edge Rewards, Determinstic | Edge Rewards, Stochastic | |
Tree Games | Polytime for MaxUtil, MaxUtilA, MaxUtilB, Fairness | ? | Polytime by equivalence | ? |
DAG Games | ? | NP-Complete for MaxUtil, MaxUtilA, MaxUtilB, Fairness | NP-Complete for MaxUtil | NP-Complete for MaxUtil |
Cyclic Games | ? | NP-Complete by extension | NP-Complete by extension from above | NP-Complete by extension |