Emergence of anti-coordination through reinforcement learning in generalized minority games

摘要

In this paper we propose adaptive strategies to solve coordination failures in a prototype generalized minority game model with a multi-agent, multi-choice environment. We illustrate the model with an application to large scale distributed processing systems with a large number of agents and servers. In our set up, agents are assigned responsibility to complete tasks that require unit time. They request servers to process these tasks. Servers can process only one task at a time. Agents have to choose servers independently and simultaneously, and have access to the outcomes of their own past requests only. Coordination failure occurs if more than one agent simultaneously requests the same server to process tasks at the same time, while other servers remain idle. Since agents are independent, this leads to multiple coordination failures. In this paper, we propose strategies based on reinforcement learning that minimize such coordination failures. We also prove a null result that a large category of probabilistic strategies which attempts to combine information about other agents' strategies, asymptotically converge to uniformly random choices over the servers.