Agent model yields leadership
By Kimberly Patch, Technology Research NewsComplicated systems that involve many agents making independent decisions -- like the stock market -- are difficult to predict. Game theory quantitatively captures interactions among a few autonomous agents, but is unable to describe more complicated systems because adding agents to the system causes possibilities to expand exponentially, putting system models beyond the computing reach of today's technology.
One way to gain at least a moderate ability to predict is to start in the middle -- construct a system using quantitative representations for agent-level behavior and interactions observed from real life, let the simulation evolve according to a set of rules, then compare the system to qualitative observations from real life to see how close the model has come to representing the behavior of a real system.
Researchers from Los Alamos National Laboratory, the University of Houston, and Rensselaer Polytechnic Institute have developed a quantitative model of software agents competing for limited resources that is representative of more complex systems.
The model is a simple, expandable framework that accounts for social behavior in agent-based markets, said Marian Anghel, a technical research staff member at Los Alamos National Laboratory. It could eventually be used to study financial markets, behavioral economics, and quantitative sociology, and to optimize agent communications networks, including robot collectives, said Anghel.
The researchers based their system on an existing multi-agent-competition model dubbed the minority game: agents choose between two possibilities with the aim of being in the minority in that choice, and agents use their most successful strategy at each round to make the choice. In that model, when only a small number of strategies are possible, many agents are forced to use the same strategy and thus they behave as a group, said Anghel.
This classic game-theory model follows deductive reasoning by completely rational players. In real life, however, extreme complexity leads to a breakdown of the reasoning process, said Zoltan Toroczkai, a technical research staff member at Los Alamos National Laboratory. In these situations, "the way humans attempt to optimize their choices is... inductive," he said.
The researchers' modifications allowed the model to take into account the observation that no agent can have complete information about all other players' choices and plans, and that agents can make "bounded rationality choices", which can turn out to be mistakes, when choosing an action, said Anghel.
The classic minority game model assumes that all agents have access to the same common information, said Toroczkai. In reality, social networks play an important role in disbursing game-relevant information among selected acquaintances, he said.
The researchers added a network of acquaintances that give advice to each other based on the agents' predictions about the best move in the game at any given moment. Each agent chooses the highest-scoring strategy from its own and its immediate neighbors' experience. This allows agents to become smarter by having access to their neighbors' experience so they can select from a larger information pool, said Anghel.
The problem was how to introduce a simple model describing the influence of this social network in the decision-making process of the agents, said Anghel. "The conceptual breakthrough came when... Toroczkai realized that the same reinforcement learning mechanism which provides the inductive principle behind simple adaptive processes of imitation and social learning can actually be used as a mechanism to include selection [of] information coming from the social network," he said.
Every agent must decide what to do with the information received. Typically an agent will base a decision on its own experience or another source of information based on the selection mechanism of reinforcement learning, said Toroczkai. "For example if I have five broker acquaintances telling me whether I should buy or sell a particular stock, I will naturally listen to the broker which in the past gave me the best advice," he said.
"If John happened to be the most successful in the recent past at predicting the behavior of a particular stock, my relationship with John will generate a financial action," said Toroczkai. When John's advice begins causing losses, however, the agent will stop following John's advice and instead rely on the judgment of a neighbor who has been more successful in predicting the market in the recent past, he said.
When this happens, the influence link from that agent to John disappears and a new one appears pointing to the agent whose advice is more beneficial at the moment. "The collection of these... links forms the influence network," said Toroczkai. "It is highly dynamic, and it represents the instantaneous substructure along which information exchange drives the competition game."
"The grouping in effect generates a large motility in the ordinary minority game model," said Anghel. Through the influence network, however, an agent, even if it shares the same strategy as others, has the opportunity to listen to other agents including agents choosing different strategies. This breaks the grouping effect, said Anghel.
The researchers' model showed that the influence network is scale-free, meaning it has a few leadership agents that have many connections, and many agents that have only a few connections. The scale-free character of the influence network is a non-obvious consequence of the reinforcement learning mechanism, and is also related to the efficiency of information-processing, said Toroczkai.
It also showed that the size of this leadership structure depends more on the connectivity of the social network than the size of the agent society or the complexity of the possible strategies. "If the number of agents is increased, the leadership structure and its size... will hardly change," said Anghel.
The leadership forms only a small subset of about 1 percent of the whole society. Real-life leadership is similar, said Anghel. "For example the total number of U.S. government officials is about 0.5 million, leading a population of over 250 million."
The model also showed behavior that was smarter and therefore more adaptive than classic models that do not contain the social network information, said Anghel. "Our results show that when underlying social network structure is introduced, it offers the agents more flexibility to adapt," he said. This results in more efficient market behavior.
The research is interesting, but the leadership structure of the network is not quite as clear as the researchers imply, said Duncan Watts, an associate professor of sociology at Columbia University. "While it does seem to be the case that the reinforcement learning mechanism generates skewed distributions of leader popularity, globally there is always a strict cut-off to this distribution, which is defined by the connectivity of the underlying network," he said.
In addition, scale is very important to the performance of the system, Watts added. The researchers make it clear that the network should not be too densely connected, otherwise leaders will get too popular and their opinions will have so much effect that they will destabilize the system, he said. "So one could equally interpret the results as implying that scale-free networks... would generate high volatility," he said.
The researchers are aiming to eventually produce artificial agent systems that perform optimally as a collective, said Toroczkai. "Specific tasks could include exploration, detection [and] intervention."
Improving collective performance by designing adaptive rules for interaction and information exchange through a communication network has important implications for designing autonomous multi-agent systems such as robot collectives, he said.
Such systems are highly desirable in situations where manual control by humans is not feasible, like exploring Mars, said Toroczkai. The technology could be ready for this type of use 10 to 20 years, he said.
Anghel and Toroczkai's research colleagues were Kevin E. Bassler from the University of Houston and Gyorgy Korniss from Rensselaer Polytechnic Institute. The work appeared in the February 6, 2004 issue of Physical Review Letters. The research was funded by the Department of Energy (DOE), the National Science Foundation (NSF), the Alfred P. Sloan Foundation and and the Research Corporation.
Timeline: 2-3 years, 10-20 years
Funding: Government, Private
TRN Categories: Physics; Applied Technology; Theory
Story Type: News
Related Elements: Technical paper, "Competition-Driven Network Dynamics: Emergence of a Scale-Free Leadership Structure and Collective Efficiency," Physical Review Letters, February 6, 2004
Advertisements:
September 22/29, 2004
Page One
Fuel cell converts waste to power
Bank transfer demos quantum crypto
Agent model yields leadership
Flexible sensors make robot skin
Briefs:
Microscope etches ultrathin lines
Nanowire makes standup transistor
Plastics ease nanotube circuits
Virus forms nano template
Photo molecules flip current
Nanotubes on cloth fire electrons
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
