Eur. Phys. J. B (2016) 89: 266
https://doi.org/10.1140/epjb/e2016-70464-0

Regular Article

Self-organization in a distributed coordination game through heuristic rules

¹ Indian Institute of Technology, 600036 Chennai, India
² Production & Quantitative Methods Area, Indian Institute of Management, Ahmedabad 380015, India
³ Economics Area, Indian Institute of Management, Ahmedabad 380015, India

^a e-mail: anindyac@iima.ac.in

Received: 4 August 2016
Received in final form: 20 September 2016
Published online: 7 December 2016

Abstract

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