Using evolutionary game theory to understand scalability in task allocation

Cooperation is an important challenge in multi-agent systems. Decentralised learning of cooperation is difficult because interactions between agents make the environment non-stationary, and the reward structure tempts agents to act selfishly. A centralised solution bypasses these challenges, but may scale poorly with system size. Understanding this trade-off is important, but systematic comparisons have been limited to tasks with fully aligned incentives. We introduce a new task for studying cooperation: agents can solve the task by working together and specialising in different sub-tasks, or by working alone. Using neuroevolution, we empirically investigate scalability comparing centralised and decentralised approaches. A mathematical model based on the replicator dynamics allows us to further study how the task's social dynamics affect the emergent behaviour. Our results show that the task's unique social features, in particular the challenge of agents' physical coordination, causes both centralised and decentralised approaches to scale poorly. We conclude that mitigating this coordination challenge can improve scalability more than the choice of learning type.