Self-organization in a distributed coordination game through heuristic rules

In this paper, we consider a distributed coordination game played by a large number ofagents with finite information sets, which characterizes emergence of a single dominantattribute out of a large number of competitors. Formally, N agents play acoordination game repeatedly, which has exactly N pure strategy Nash equilibria, and all of theequilibria are equally preferred by the agents. The problem is to select one equilibriumout of Npossible equilibria in the least number of attempts. We propose a number of heuristicrules based on reinforcement learning to solve the coordination problem. We see that theagents self-organize into clusters with varying intensities depending on the heuristicrule applied, although all clusters but one are transitory in most cases. Finally, wecharacterize a trade-off in terms of the time requirement to achieve a degree of stabilityin strategies versus the efficiency of such a solution.