  We investigate the difficulty of finding economically efficient solutions to
coordination problems on graphs. Our work focuses on two forms of coordination
problem: pure-coordination games and anti-coordination games. We consider three
objectives in the context of simple binary-action polymatrix games: (i)
maximizing welfare, (ii) maximizing potential, and (iii) finding a
welfare-maximizing Nash equilibrium. We introduce an intermediate, new
graph-partition problem, termed Maximum Weighted Digraph Partition, which is of
independent interest, and we provide a complexity dichotomy for it. This
dichotomy, among other results, provides as a corollary a dichotomy for
Objective (i) for general binary-action polymatrix games. In addition, it
reveals that the complexity of achieving these objectives varies depending on
the form of the coordination problem. Specifically, Objectives (i) and (ii) can
be efficiently solved in pure-coordination games, but are NP-hard in
anti-coordination games. Finally, we show that objective (iii) is NP-hard even
for simple non-trivial pure-coordination games.
