Emergent Intelligence in Competitive Multi-Agent Systems

by Sander M. Bohte, Han La Poutré

Getting systems with many independent participants to behave is a great challenge. At CWI, the Computational Intelligence and Multi- Agent Games research group applies principles from both the economic field of mechanism design and state-of-the-art machine-learning techniques to develop systems in which 'proper' behaviour emerges from the selfish actions of their components. With the rapid transition of the real economy to electronic interactions and markets, applications are numerous: from automatic negotiation of bundles of personalized news, to efficient routing of trucks or targeted advertisement.

Competitive multi-agent games: to each its own.

In an economic setting, an individual - or agent - is assumed to behave selfishly: agents compete with each other to acquire the most resources (utility) from their interactions. In economics, the field of mechanism design looks at interaction protocols (mechanisms). Here, the combined selfish behaviour of individual agents serves a particular purpose as an emergent property of the system: for example, the efficient allocation of scarce goods. Many computational problems can be cast as resource allocation problems. Our research transfers the emergent property of human competitive multi-agent systems to systems comprised of competing pieces of software, ie software agents.

Clearly, software agents in a multi-agent system must be intelligent and adaptive. If intelligent software agents are to work out the (local) solutions that are best for themselves, the rules of the system must be incentive compatible. That is, the rules should be such that as individual agents learn how to optimize their own reward, the system as a whole should work with increasing efficiency. Our work shows that the combination of intelligent software agents and well-designed mechanisms (markets/auctions/negotiations) can lead to the desired behaviour of the system as a whole, a kind of 'collective intelligence'.

For example, we designed a personalized recommendation system in which competing advertising agents can bid for the attention of the customer. The design of the market, combined with adaptive intelligence in the bidding agents, results in the emergent effect that only the most relevant advertisements are shown to the system user.

In a similar vein, we considered the dynamic scheduling of trucking routes and freight. We developed a dynamic spot market where a software agent in each truck continually participates in auctions to increase, change and augment the loads the truck carries. To facilitate this, we developed bidding strategies for repeated auctions where the software agents compute which combination of loads they can acquire most profitably. We show that as an agent tries to best anticipate future loads with the aim of improving its own profit, an emergent effect is that the market as a whole becomes more efficient and the cost of transport is reduced.

Within the same paradigm, we developed methods for dynamically pricing information. Electronic information can be sold to many buyers at the same time. If we demand that each buyer pays the same price, the problem is what the price should be. In our system, we show how the selling agent can deduce the pricing policy that will maximize revenue from the aggregate of negotiations between the seller and the buyers (one-to-many).

This method has been extended by integrating recommendations in a negotiation process. A shop aggregates data on customers' past purchases, and produces information on correlations on customer interest in the products on offer. For instance, which products are often bought together? We applied machine-learning techniques to the problem of online learning of the bundle combinations that optimize the revenue of a seller of information goods. When negotiating with a new customer the price of a bundle of such products, the shop uses this learned knowledge to recommend alternative, more promising bundle compositions if the negotiation process stalls. We designed and implemented a combined system for making recommendations during a negotiation. Extensive simulations with this system show superior performance on a number of benchmarks.

Related to these logistics applications is the use of emergent competitive agent systems in health-care logistics. In a project on medical information agents, we have researched the problem of patient treatment scheduling in hospitals. Scheduling complex treatment plans requires coordination between all the relevant autonomous departments. Due to the dynamic nature of a hospital, any approach must be efficient, online and flexible. In cooperation with medical experts we are investigating the use of autonomous software agents negotiating with each other in order to make (or reschedule) appointments for patient treatment. The idea is that as each agent follows its owner's interests and preferences, agreements over schedules can be reached that take into account all the individual constraints. Thus, a good schedule should emerge from the agent interactions.

Obviously, systems where many self-interested stakeholders interact pervade our society. Neglecting the strong incentive these stakeholders have to be selfish can be catastrophic for the functioning of any system that tries to bring these parties together electronically. At the same time this is also a great opportunity, since we can rely on individual agents to maximize their own utility. Thus, we can design the system to encourage 'emergent intelligence', as individual intelligent behaviour continually improves the workings of the system as a whole. There are many opportunities for smarter software agents and better mechanisms, such as emergent multi-agent scheduling. We are actively pursuing this in current research.

Link:
http://www.cwi.nl/sen4

Please contact:
Han La Poutré, CWI, The Netherlands
Tel: +31 20 592 4082
E-mail: hlpcwi.nl