  In order to coordinate players in a game must first identify a target pattern
of behaviour. In this paper we investigate the difficulty of identifying
prominent outcomes in two kinds of binary action coordination problems in
social networks: pure coordination games and anti-coordination games. For both
environments, we determine the computational complexity of finding a strategy
profile that (i) maximises welfare, (ii) maximises welfare subject to being an
equilibrium, and (iii) maximises potential. We show that the complexity of
these objectives can vary with the type of coordination problem. Objectives (i)
and (iii) are tractable problems in pure coordination games, but for
anti-coordination games are NP-hard. Objective (ii), finding the best Nash
equilibrium, is NP-hard for both. Our results support the idea that
environments in which actions are strategic complements (e.g., technology
adoption) facilitate successful coordination more readily than those in which
actions are strategic substitutes (e.g., public good provision).
