Heterogeneous Populations of Learning Agents in Minority Games

We study the combination of co-evolution and individual learning in minority games (MGs). Minority games are simple models of distributed resource allocation. They are repeated conflicting interest games involving a large number of agents. In most of the literature, learning algorithms and parameters are evaluated under self-play. In this article, we want to explore by means of an evolutionary algorithm (EA) whether agents that are free to choose or change their learning parameters can improve their individual welfare. Furthermore, we are interested to see whether an increase of the agents' strategy space is beneficial to the entire population. I.e., can such agents use the available resources more efficiently or will the price of anarchy increase? Experiments show that the heterogeneous setting can achieve outcomes which are good from the viewpoint of the system, as well as for the individual users. The average of the evolved learning parameters are mostly reasonable values for the homogeneous setting. More importantly we show that algorithms which achieve better results in a homogeneous setting may be outcompeted when confronting other algorithms directly in a heterogeneous setting.

Publication year:2011

Keywords:minority games, congestion games, adaptation, reinforcement learning, co-evolution, evolutionary algorithm