摘要：SummaryGlobal coordination is required to solve a wide variety of challenging collective action problems from network colorings to the tragedy of the commons. Recent empirical study shows that the presence of a few noisy autonomous agents can greatly improve collective performance of humans in solving networked color coordination games. To provide analytical insights into the role of behavioral randomness, here we study myopic artificial agents attempting to solve similar network coloring problems using decision update rules that are only based on local information but allow random choices at various stages of their heuristic reasonings. We show that the resulting efficacy of resolving color conflicts is dependent on the implementation of random behavior of agents and specific population characteristics. Our work demonstrates that distributed greedy optimization algorithms exploiting local information should be deployed in combination with occasional exploration via random choices in order to overcome local minima and achieve global coordination.Graphical abstractDisplay OmittedHighlights•Local information makes solving distributed network coloring problems difficult•Greedy agents can become gridlocked, making it difficult to find a global solution•Agents making random choices can facilitate the finding of a global coloring•Randomness can be finely tuned to a specific underlying population structureComputer Science; Artificial Intelligence; Human-Computer Interaction
