  We have shown that entanglement assisted stochastic strategies allow access
to strategic measures beyond the classically correlated measures accessible
through passive common randomness, and thus attain a quantum advantage in
decentralised control. In this two part series of articles, we investigate the
decision theoretic origins of the quantum advantage within a broad
superstructure of problem classes. Each class in our binary team superstructure
corresponds to a parametric family of cost functions with a distinct algebraic
structure. In this part, identify the only problem classes that benefit from
quantum strategies. We find that these cost structures admit a special
decision-theoretic feature -- `the coordination dilemma'. Our analysis hence
reveals some intuition towards the utility of non-local quantum correlations in
decentralised control.
