Agent-Based Systems
(in SICS Strategic Research Program 1999-2002)

1 Background: Software agents, Self-Interest, and Electronic Markets

Distributed systems and component technologies have been thoroughly investigated for several decades, but until very recently with the unspoken underlying assumption that systems are owned and controlled by single individuals or organizations. This means that all components of a system are thought to be working cooperatively towards a common goal and that they may safely do what they are told and trust whomever requests them to supply information or perform services.

On the Internet, this assumption is no longer true. There, Mary's software may meet and be required to interact with, e.g., Acme Inc's software. Mary's goals may be quite different from Acme Inc's, perhaps even conflicting and her only safe assumption will be that Acme Inc's software is designed to act in Acme Inc's best interests. She should obviously likewise make sure that her software acts in her best interests.

In the following, the term software agent (or just agent) refers to a software component that acts on our behalf, with our authority, and that is intended to do so in our best interests.

What does it mean for an agent to act in our interests? How free are our agents to act in our interests given existing technological constraints and limitations? How free could we make them if we design future information society technologies with this in mind? How do we make these technologies robust against errors and intentional misuse? These questions form the foundation of the research proposed below.

Our main focus is on how to automate participation in electronic markets. Through automated trading by software agents, we expect improvements in the quality of existing markets, such as consumer goods markets, service markets, and the emerging information markets, and to reap the benefits of markets as effective instruments of resource allocation also in non-traditional domains, such as fine-grained markets for electric power and communication bandwidth. Agents have the capacity to consider more information, e.g., evaluate thousands of offers for a new car and hundreds of recommendations from various sources, and may also act in domains where we are disqualified due to speed requirements, e.g., buying the bandwidth we need packet by packet or the additional electricity needed when we turn on a light switch.

The research proposed here falls into four main lines of investigation:

• Decentralized coordination with resource markets
• Recommender systems based on decentralized collaborative filtering
• Internet commerce infrastructures, with the subtopics
  • Dynamic component architectures for evolvable electronic markets
  • Matchmaking based on explicit interests
• Service access architectures

2 Needs of Industry and Society

The widespread use of information technology will enable people to work together in new and very different ways. Coordinating the work of several independently working individuals and organizations through electronic markets can enable new services and rapid development of new projects.

It is strongly desirable that future software infrastructures based on the Internet are open and decentralized. Decentralization avoids giving single actors total control over shared resources, while openness encourages competition and efficiency.

To realize this vision we need to understand the behavior of computational systems based on self-interested components, agents, and to explore systems based on this fundamental principle.

3 State of the art

Resource Markets

Decentralized coordination of shared resources has been an important topic in computer research for att least two decades. From the work on the Contract Net that uses local decision making, it became apparent that distributed algorithms need to handle resource negotiation in parallell.

In agent-oriented programming, such local decision makers are called agents, and several research labs have built negotiation frameworks for agents that maintain sets of partial plans, commitments, etc., to allow agents to negotiate several resources in parallell.

Market-oriented programming is an alternative approach to solving distributed coordination problems. The resource users are represented by agents, software that decides which resources to obtain based on the current market prices rather than individual negotiation. In a true market-oriented setting the prices are generated by the current supply and demand of the available resources. Many quasi-market-oriented systems, where prices are dicated by the algorithm, are also often grouped into this category. Among the hybrids we can find TRACONET where ContractNet contracts are trade at market price.

Recent hot topics of research include combinatorial auctions, price dynamics in agent markets, and "almost zero" intelligence bidding strategies for agents. The domain of application ranges from information trading, CPU load balancing and intelligent web caching to network load balancing, configuration and Quality-of-Service establishment.

Recommender Systems

As people search, browse or publish information their actions, explicit or implicit, can be used by information brokering services to guide other users or to filter information irrelevant to the user. Systems that attempt to make use of this kind of data are usually termed Recommender Systems.

Several recommender systems have been designed for collecting user feedback and/or finding and sub-groups of users with related needs (e.g., FAB, GroupLens, Tapestry]. Other recommender systems mine information about relations between people or documents from publically available data sources e.g the web, usenet news or bibliographic information (e.g., ReferralWeb, PHOAKS, ParaSite).

There has traditionally been two main ways of estimating what a person is interested in; content based methods that examine the contents of the data the user accesses and collaborative methods which focus on similarities in behavior among groups of users.

In the Recommender Systems community there is today a trend towards combining the approaches of content based and collaborative filtering to hybrid methods to provide good novelty of the recommendations (as provided by collaborative methods) while at the same time reducing the risk that no advice can be given if no similar use-pattern was found.

Several recommender systems are implemented as multiagent systems to improve scaling properties, share work or separate functionality.

Internet Commerce

A commerce model typically includes activities such as advertising, searching, negotiating, ordering, delivering, paying, using, and servicing.

Storefronts and search engines offer Internet-wide search and negotiation, although not with much precision. Future developments of metadata, e.g., based on the W3C RDF/XML (Resource Description Framework mapped onto XML), will increase precision. But to facilitate automation, and offer sufficient expressiveness, the metadata framework has to be based on uniform design principles.

Progress can be made without metadata. The web-based service (shopbot) Jango (now part of Excite) provides a simple interface for searching and ordering from a number of storefronts, thus serving as a kind of an integrating "meta-store". Its operators use tools that automate the creation of interfaces to the web based storefronts, to simplify this otherwise arduous task. If information and interaction were standardized, the creation of a Jango-like service would be a much simpler, almost trivial, task, and more attention could instead be placed on domain specific value-adding services.

Other services, e.g., auctions, also include negotiation mechanisms. If this trend is taken further, a single site could provide for all activities desired, a one site globally accessible marketplace, owned and controlled by a single participant. This is clearly strongly in conflict with the ideals of free markets. While EDI (Electronic Document Interchange) offers standards for information and interaction between trading partners, current EDI standards are intended for use in static longterm relationships on the basis of detailed trading partner agreements, not for spontaneous commerce on the Internet.

A number of object-oriented platforms have been proposed for building distributed commerce applications integrated with the web. The most ambitious proposal to date is perhaps the CommerceNet eCo System project [eCo], which was aimed to develop an architectural framework compatible with all major Internet commerce platforms. Pattie Maes, et al, at MIT Media Lab have developed an agent-based (single site) marketplace called Kasbah. Users may assign the task of buying or selling a specified good to an agent, which then performs negotiation and settlement of deals, fully automatically, according to the users' choice of predefined strategy.

The Stanford and University of Michigan Digital Library projects both employ agent-based architectures. These are strongly influenced by a top-down hierarchical view of system design, a priori subdividing responsibilities into a number of components. Our goal is to provide the minimum possible glue to enable automation of a market of self-interested participants, who are free to assume the rôles of buyers, sellers, or various forms of mediators.

We have previously developed an agent-based framework for Internet market automation (SICS MarketSpace). Agent provide assistance to a wide range of market activities by interacting with the agents of other participants. Agents share a common language, a formalized subset of commerce communication, but are otherwise unrestricted.

Service Architectures

The technological context for access to services is changing, from standard multimedia PC-based access via wired connections, to a range of new devices connected in wire-less mode. How will the service providers be able to offer services that can be accessed via this multitude of disparate technologies?

The growth of the importance of services on the net causes new categories of users to access services. The traditional service-centered view, whereby services are presented entirely based on a view of what the service is about, is gradually being replaced by a client-centered view, where the presentation of a service should be strongly influenced by the goals and tasks of the user that accesses the service. Practically this means that the concrete interaction between the user and the service depends on two sources of knowledge, knowledge about the user, and knowledge about the service.

This requires that service models are available, models that adequately describe what the service is about. A model of the user covers areas as; general user preferences, situation-specific tasks and goals, and the technological characteristics that enable or constrain the form an interaction can take (how a presentation can be rendered.

Availability of service models also enables service discovery and service matchmaking. By service discovery we mean identification of services that may be relevant for a specific user task, and by service matchmaking we mean finding combinations of service providers that provide support for a current task of the user. Service discovery in this sense is related to trader/broker services, as well as to recommendations like RDF. Results have emerged from work on matchmaking among agents, aiming at high-level descriptions of agent-provided services. In specific areas, highly detailed proposals exist, e.g. the Dublin Core recommendation for meta-data concerning document retrieval, but what is required is a more generic descriptive model.

Models of multimedia service interaction have been explored in the KIMSAC project, and also adaptation of the service presentations and dialogues based on user models.

SMIL, WAMP and WML are early examples of environment models for web-presentations, but the adequacy of these when taking service models into account remains to be investigated.

To enable seamless service-access, mechanisms and models as mentioned above should be embedded into a service architecture where agents can mediate between users and service providers, assisting the user in finding the best ways of performing tasks and satisfying goals.

4 Research Issues

Resource Markets

The use of shared resources (e.g., wires and equipment for power distribution or data communication) needs to be coordinated. We argue that such coordination should be done in a decentralized manner, partly for efficiency and to avoid single points of failure, but not least since competitors have different opinions about which resource allocations are preferred.

Our goal is to develop and analyse decentralized coordination algorithms from the point of resource efficiency and fairness. Instead of designing cooperative algorithms, i.e., algorithms that assume that everyone works toward the same goal, we assume that people will choose actions that makes them better off, even on the expense of others. We call this self-interested behaviour. This is an important characteristic of open systems where competing companies offer resources to consumers.

The focus will be on market-oriented coordination, wherein software agents trade the shared resources for their clients. The negotiation takes place by placing bids on an exchange. The prices are not decided by the allocation algorithm, but by the agents themselves. Some programs may act as speculators and earn money by investing temporarily in resources. Agents with clients can earn additional money by buying resources that their client wants.

One domain under our consideration is telecom routing, in which agents trade the scarce routing capacity in the routers between the source and destination node. All trading takes place concurrently, and an agent that wants to buy a complete route has to handle the problem of buying a combination of resources, which only are valuable as a complete set.

We are designing a formalism for agent reasoning that incorporates user models, world knowledge and negotiation as resource price distributions. In this formalism, and agent makes its decision to acquire or sell resources based on finding the portfolio (set of possessed resources) that maximises the agents future profit. The formalism will deal with uncertain knowledge and will be able to be risk averse. We are also working with genetic programming algorithms to investigate its potential for finding clever trading behaviour.

Trading agents of these kinds are being implemented in a software simulation of a telecom network, and this simulation will be used as a platform for comparing different agent systems to each other.

Another domain is railroad track scheduling with carriers competing for delivery tasks. Each locomotive is a potential freelance carrier that wants to maximise its income by selling transportation between two locations. Similar to the telecom agent, the locomotive agent is confronted with "all-or-nothing" problems when it needs to reserve/buy access to the all tracks on one path connecting the two locations. If it can not reserve a particular subtrack at a certain time, all other subtracks on the path will be worthless to the locomotive. It is still not known how to construct an efficient automated market that allows "all-or-nothing" demands, but as market-oriented systems have many useful properties (i.e., decentralisation, simple communication, risk reduction provision, etc.) they will surely be used a lot, and that makes this an important problem to solve.

Aim of this activity

• Finding good criteria for a "good" resource allocation. Markets implicitly promote allocations with high "turn-over" and do not maximise the total "utility". This has implications of the allocation fairness.
• Creating agents that incorporate speculation in reasoning on vague information. Speculative/risk averse behaviour and it's relation to implicitly coordinated groups, like unions or oligopolies.
• Limits on how sophisticated reasoning that is necessary for good performance. Earlier work has indicated that quite unsophisticated reasoning is necessary, but the simple agents have only been tested against other simple agents.

Recommender Systems

In any recommender system it is crucial that enough incentive is provided for the participants to participate in, and continue to use, the system.

E.g a system that relies on ratings or votes from the participants must provide them with enough added value for the invested work.

In our research we will simulate populations of users participating in a decentralized recommender system. By simulating e.g interest groups, changing interests and gratification from good recomendations we try to understand the parameters that govern the performance of a recommender system.

Changing interests and changed characteristics may for instance affect the negotiated communication patterns. Under what conditions will subgroups dissolve or form as response to changing interests in the community? Will a decrease in the quality of information disperse previously functioning communitues, similarily to the way newsgroups tend to be abandonded when the traffic increases to much?

The aim with this research is do find guidelines for how to design this kind of decentralized systems and to increase the understanding of what trade-offs and assumptions that must be made.

Insights from these simulations may be used to understand if a recommender system is suitable for a particular domain and, if so, estimate the potential gains and understand the impact of changes in the recommender system algorithms, e.g in the group-formation strategy or in the reward mechanisms.

We will also experiment with an email-centered personal recommender agent. The agent makes use of the implicit information about a user's interests that can be extracted through the user's use of email, mailinglists etc. The agent may use this information e.g to recommend information or improve the process of searching for information.

Aim of this activity

• What mechanisms, if generally adopted, give good precision and recall while minimizing communication?
• What are the incentives to share recommendations in specific circumstances, e.g., in markets with different properties? In what specific circumstances do individual advantages arise that rationally justify the use of a recommender system?
• What are the properties of a decentralized recommender system in which the participants optimize for their own utility?
• Could the system become more flexible by pricing recommendations, e.g., creating a recommendation market?
• How vulnerable is the model to intentional misuse, e.g., sending false recommendations with the purpose to cause confusion or to direct interest to specific items? Can the risk be reduced, e.g., by also sharing recommendations of other user's recommendations?

Dynamic component architectures for evolvable electronic markets

We have previously introduced and explored the SICS MarketSpace framework for agent-based markets. In MarketSpace, agents provide assistance to a range of market activities by interacting with the agents of other participants in the market, helping buyers and sellers find matching interests and negotiate and close deals. Results include the AgentBase development platform for agent-based markets.

Based on these results, we have developed prototype applications and demonstrators in the context of two projects with Telia Research AB (AMP):

• An agent-based marketplace for consumer goods and services, complementing, and emphasizing integration with, web-based commerce
• An agent-based workflow system for market-based organizations, which supports the dynamic generation of workflows from a market of available activities and competencies

Aim of this activity

• openness to new market mechanisms, which involves introducing new interaction protocols and agent behaviors, and exploring appropriate interfaces between interaction protocols and the "core" agent
• openness to new information formats, which involves introducing more expressive representations of market information (contracts and interests) and pertaining algorithms, while keeping the interfaces constant
• openness to new information interfaces, which involves changing the type of market information, e.g., from unprioritized interests to prioritized interests

• What are the appropriate interfaces between dynamic components and the "core" agent in agent-based market applications?
• Which mechanisms will enable a sufficient degree of trust in dynamically downloaded components, e.g., such as proof-carrying code and recommender/reputation mechanisms?

Matchmaking based on explicit interests

The MarketSpace information model is based on the assumption that the goal of the activities of participants in a market is to close deals. As our basic information unit we have chosen the contract, for our purposes a structured document. To assist the process of identifying which deals are possible, participants will, through their agents, exchange interests, which are (representations of) sets of contracts. Participants can use interests to advertise their true goals of buying or selling, or just reveal approximations of their true goals to enable an initial contact. Interests can be used both for communication and for the user models of user agents.

Interests that can be expressed in this way include: "buying a new car", "buy things cheaper than $1", "sell books on software agents", "buy pizza within an hour". More general interests, such as "buying environmentally friendly goods" and "liking whatever Joe/Jill likes", can also be captured, but as relations to other agents (e.g., GreenPeace's agent and Joe's/Jill's agent), which can be asked if they share a certain interest.

The current information model and associated formats are expressive enough to capture basic requirements, but lack the precision and conceptual expressiveness for more sophisticated market applications. For example, an interest in a certain combination of goods at a maximum total price or that one combination is preferred to another cannot currently be expressed.

Aim of this activity

• more powerful, constraint-based, formats for describing sets of contracts, allowing increased precision in the descriptions of contracts
• extending the expressiveness of interests to include priorities between contracts, using utility functions and (Bayesian) uncertainty

• What are the expected effects of increased precision and expressiveness of interests on the precision, recall, and efficiency of matchmaking in a typical consumer goods market?
• How complex notions of interest can be used without risking compromising the comprehension and personal integrity of non-specialist users?

Service Architectures

At the user interface, the user should be able to interact with a number of services, potentially at the same time, and the interaction should have a look-and-feel that more reflects the user's preferences than the service provider's preferences. The user's preferences depend not only on personal taste, but also on factors like the characteristics of the interaction device being used. Interaction devices can range from simple but widespread devices like mobile phones, to multimodal multimedia environments.

Ideally the interaction between the user and the service should be rendered by applying presentation policies to a semantical description of the service. This would enable the user to access familiar services via different devices, without requiring the information provider to prepare presentations for all possible constraints regarding presentations.

The user's goal may not be able to be satisfied by a single information provider. E.g. when planning a travel, one may need to access airline information as well as accommodation information. The task of the user would be simplified if the information offered by one provider could be related to the information offered by another provider. The actual correlation can be performed by a personal agent if the available information providers can semantically describe the kind of information they offer. Such a personal agent will also be able to assist the user in locating information providers.

To liberate the user from having to be repeatedly re-visit services to check for new offerings, we see personal agents as a mechanism to off-load tasks from the user. Through delegation, the user can release personal agents to monitor services for interesting events, and such agents can then inform the user if something interesting has happened. We are restricting the work to information providers, specifically providers with time-varying information.

This work build upon results, experiences and insights from earlier and ongoing projects about knowledge-based agent-mediated service access (projects KIMSAC and MAPPA). Results to be extend and refined include service models, mechanisms for brokering of agent-based service provisioning, models of user goals and tasks, and the adaptation of user-service dialogues to constraints imposed by user preferences, service characteristics and device characteristics.

Aims of this activity:

• to enable the user to control the way services are presented, by defining policies that take personal preferences into account as well as characteristics of interaction devices.
• to enable the user to easily navigate in the space of services, and to locate the services appropriate for the current tasks, by being assisted by personal agents that build up knowledge of services.
• to enable information from independent providers to be correlated, thereby off-loading from the user the task of matching information, and from matching service providers.
• to enable the user to delegate monitoring tasks to personal agents, and to define policies for how these agents should behave.
• to define service architectures that enables agents to provide added-value to services provided.

• what are the requirements on models of services, users, and devices, so that the interaction actually rendered can be optimally influenced by these models.
• what are the models and protocols that enables querying and accessing services based on a model of the user's needs.
• what are the requirements on service models that would enable services to be correlated/matched.
• what are the requirements on and architectures of environments where agents, on behalf of their users, take on the tasks of locating services matching needs, and of monitoring the offerings of service providers.

5 Demonstration Projects, National/International programs

• Telematics (KFB)
• PROMODIS (NUTEK)
• SIRIS (SSF proposal)
• MAPPA (EU)
• iCities (EU FET, accepted proposal)

6 Cooperation

• Telia Research
• Telia Business Innovation
• Ericsson Radio
• Ellemtel
• Compaq (in MAPPA)
• Independent Telecoms Group (in MAPPA)
• Nortel (in MAPPA)

• Department of Information Technology, Uppsala University
• Department of Teleinformatics, KTH.
• Department of Computer and Systems Sciences, Stockholm University.
• Imperial College of Science Technology and Medicine (in MAPPA)
• Trinity College Dublin (in MAPPA)

7 References