Friday, September 14, 2007


David H. Wolpert and David H. Wolpert's paper on collective intelligence emerging from simple agent is very illuminating.
The paper can be downloaded here.


This paper surveys the emerging science of how to design a “COllective INtelli-
gence” (COIN). A COIN is a large multi-agent system where:
i) There is little to no centralized communication or control.
ii) There is a provided world utility function that rates the possible histories of the
full system.
In particular, we are interested in COINs in which each agent runs a reinforce-
ment learning (RL) algorithm. The conventional approach to designing large dis-
tributed systems to optimize a world utility does not use agents running RL al-
gorithms. Rather, that approach begins with explicit modeling of the dynamics
of the overall system, followed by detailed hand-tuning of the interactions between
the components to ensure that they “cooperate” as far as the world utility is con-
cerned. This approach is labor-intensive, often results in highly nonrobust systems,
and usually results in design techniques that have limited applicability.
In contrast, we wish to solve the COIN design problem implicitly, via the “adaptive”
character of the RL algorithms of each of the agents. This approach introduces an
entirely new, profound design problem: Assuming the RL algorithms are able to
achieve high rewards, what reward functions for the individual agents will, when
pursued by those agents, result in high world utility? In other words, what reward
functions will best ensure that we do not have phenomena like the tragedy of the
commons, Braess’s paradox, or the liquidity trap?
Although still very young, research specifically concentrating on the COIN design
problem has already resulted in successes in artificial domains, in particular in
packet-routing, the leader-follower problem, and in variants of Arthur’s El Farol
bar problem. It is expected that as it matures and draws upon other disciplines re-
lated to COINs, this research will greatly expand the range of tasks addressable by
human engineers. Moreover, in addition to drawing on them, such a fully developed
science of COIN design may provide much insight into other already established
scientific fields, such as economics, game theory, and population biology.

No comments: