Learning to coordinate: Co-evolution and correlated equilibrium

In a coordination game such as the Battle of the Sexes, agents can condition their plays on external signals that can, in theory, lead to a Correlated Equilibrium that can improve the overall payoffs of the agents. Here we explore whether boundedly rational, adaptive agents can learn to coordinate in such an environment. We find that such agents are able to coordinate, often in complex ways, even without an external signal. Furthermore, when a signal is present, Correlated Equilibrium are rare. Thus, even in a world of simple learning agents, coordination behavior can take on some surprising forms.