An Information-Theoretic Analysis of Memory Bounds in a Distributed Resource Allocation Mechanism

Ricardo Araujo, Luis Lamb

Multiagent distributed resource allocation requires that agents act on limited, localized information with minimum communication overhead in order to optimize the distribution of available resources. When requirements and constraints are dynamic, learning agents may be needed to allow for adaptation. One way of accomplishing learning is to observe past outcomes, using such information to improve future decisions. When limits in agents' memory or observation capabilities are assumed, one must decide on how large should the observation window be. We investigate how this decision influences both agents' and system's performance in the context of a special class of distributed resource allocation problems, namely dispersion games. We show by numerical experiments over a specific dispersion game (the Minority Game) that in such scenario an agent's performance is non-monotonically correlated with her memory size when all other agents are kept unchanged. We then provide an information-theoretic explanation for the observed behaviors, showing that a downward causation effect takes place.

Subjects: 7. Distributed AI; 12.1 Reinforcement Learning

Submitted: Oct 11, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.