Solving complex problems, from biodiversity conservation to reducing inequality, requires large scale collective action among diverse stakeholders to achieve a common goal. Research relevant to meeting this challenge must model the interaction of stakeholders with diverse cognitive capabilities and the complexity of the problem faced by stakeholders to predict the success of collective action in various contexts. Here, we build a model from first principles of cognitive abilities, diversity, and socio-environmental complexity to identify the sets of conditions under which groups most effectively engage in collective action to solve governance problems. We then fit the model to small groups, U.S. states, and countries. Our model illustrates the fundamental importance of understanding the interaction between cognitive abilities, diversity, and the complexity of socio-environmental challenges faced by stakeholders today. Our results shed light on the ability of groups to solve complex problems and open new avenues of research into the interrelationship between cognition, institutions, and the environments in which they co-evolve.