Building Electronic Marketplaces with the ZEUS Agent Toolkit

Building Electronic Marketplaces with the ZEUS Agent Toolkit

Jaron C. Collis and Lyndon C. Lee

Intelligent Systems Research Unit, MLB1, PP12, BT Laboratories,

Martlesham Heath, Suffolk, United Kingdom, IP5 3RE

Email: {jaron, lyndon}@info.bt.co.uk

WWW: http://www.labs.bt.com/projects/agents/

Abstract

There is an emerging desire amongst agent researchers to move away from point solutions in favour of developing methodologies and tool-kits for building distributed multi-agent systems. This philosophy has led researchers at BT Labs to develop the ZEUS Agent Building Tool-kit, which facilitates the engineering of future agent applications through a library of agent-level components.

The ZEUS tool-kit is currently being used to create a prototype distributed multi-agent electronic marketplace within our local area network. By employing the ZEUS agent class library this application has been implemented rapidly by two developers. ZEUS agents were not specifically designed for electronic commerce applications and so new functionality has been added that enables our agents to participate in auctions, and enables users to communicate information about transactions to their agents.

Our experimental marketplace shares many features with existing agent-based auction systems, such as the dynamic setting of pricing strategies, and the ability to participate in two-way bargaining. Where our market differs from web-based auctions is by consisting of client-side agents that are distributed across a network, and which are capable of both buying and selling.

Using our agents people have been able to buy and sell virtual commodities by interactively customising their trading strategies. Initial experiences with our electronic marketplace have raised some interesting issues relating to the trading protocols used by the agents, and the potential benefits of agent autonomy. As the intelligence of our current agents is limited, automated trading has only been made possible by restricting trade to a limited ontology of items. Although limiting the ontology makes the marketplace easier to implement, it also reduces the scope for merchant differentiation.

Our marketplace prototype is still far from complete however, but it will soon be extended to include brokers: dedicated agents that will facilitate trade between interested parties. The introduction of brokers raises new issues, such as the potential for calculating an accurate market price, the effect of brokering on vendor profits, and the robustness of the market.

Keywords

Agent building tool-kit, prototype electronic marketplace, agent-based auction

1. Introduction

Ideally developers should spend less time worrying about the intricacies of a particular technology, and more time implementing solutions to their problems. So as new technologies mature, generic application-independent platforms are developed to aid their users. Witness for instance the proliferation of class libraries of user- customisable components that are now available for users of the Java programming language. As the quantity of code written for a software platform increases, there is a corresponding increase in the opportunity for code reuse. This increase is complemented by the emergence of better-engineered solutions and new methodologies. Consequently development times tend to fall as the underlying technology becomes established.

Agent technology is no exception to this principle, and there is an emerging consensus amongst agent researchers of the need to develop methodologies and tool-kits for building distributed agent systems, [Ndumu & Nwana 97]. As the libraries of programming languages tend not to include the high-level constructs and concepts needed for agent applications, many tool-kits and frameworks of varying degrees of sophistication have recently been created to aid agent development. Some examples are: the Agent Building Environment (ABE)1, the Agent Development Tools (ADT)2, Aglets3: a Java-based mobile agent tool-kit, dMARS4: a ‘BDI’ agent building system, the Java-based Agent Framework for Multi-Agent Systems (JAFMAS)5 and Kaos6.

The philosophy of moving away from point solutions to general frameworks, architectures and methodologies has motivated researchers at BT Labs to develop the ZEUS Agent Building Tool-kit. Our intention has been to facilitate the engineering of future agent applications by providing a library of agent-level components. In this paper we describe how the ZEUS tool-kit is currently being used to create a prototype distributed multi-agent electronic marketplace. This prototype was conceived under the following assumptions:

• the scope of our electronic marketplace is restricted to the process of buying and selling undifferentiated commodities via electronic media;

• the process of buying and selling involves the exchange of information between one initiating-agent and a number of responding-agents;

• the focus of our experiments concerns how agents negotiate to arrive at joint decisions on the exchange of commodities; issues such as security and auditing are currently ignored;

• the only criterion on which agents evaluate commodities is on price;

As we are implementing an electronic marketplace with agents it is reasonable to ask what makes software agents suitable for such applications. After all, it would be perfectly feasible to implement an on-line market using a network of distributed objects. What benefits are to be gained by the use of agents? It is felt that of the agent characteristics listed in [Nwana 96] those that make agents well suited for e-commerce applications are:

• Autonomy – Agents are processes that work independently and proactively without the need for human intervention. This can be used to advantage by employing agents to visit all relevant vendors attempting to find the best deal. Agents can also behave reactively, waiting for a good deal without needing to divert the user’s attention; in fact an agent could conceivably operate 24 hours a day.

• Personalisation – Agents operate on behalf of their users, and hence can be equipped with a personal profile to better reflect their owners’ preferences. Consequently it is desirable that each agent in the marketplace will have been customised according to its owner’s agenda.

• Social Ability – Agents are able to communicate with one another, and in an electronic commerce scenario this ability can be used to facilitate agent negotiation on prices, services and transactions. We have already been able to facilitate transactions using a generic agent communication language.

• Intelligence – Agents can be differentiated from distributed objects by their intelligence, such as the ability to learn as they react or interact with their environment and other agents. An agent capable of learning should perform better over time, and in an electronic commerce scenario this should equate to making more money for its user.

1 http://www.networking.ibm.com/iag/iagsoft.htm 2 http://www.ai.sri.com/~oaa/adt.html 3 http://www.trl.ibm.co.jp/aglets/index.html 4 http://www.aaii.oz.au/proj/dmars_tech_overview/dMARS-1.html 5 http://www.ececs.uc.edu/~abaker/JAFMAS/JAFMAS.html 6 http://www.seattleu.edu/~baha/kaos-java.html

The next section outlines some of the features of the ZEUS tool-kit, and in particular the facilities that make it suitable for the development of agent-based marketplaces. This is followed by a description of an experiment currently running at BT Labs, this consists of a society of agents that can buy and sell items on behalf of their owners. This is followed by a brief discussion of some interesting aspects of the experiment. As one of these issues is the role of brokers, our future plans involving the introduction of brokers are also discussed. Finally we end with a comparison of some related agent-based marketplace systems.

2. Introducing the ZEUS Tool-Kit

The ZEUS tool-kit was motivated by the need to provide a generic, customisable, and scaleable industrial- strength collaborative agent building tool-kit. The tool-kit itself is a package of classes implemented in the Java programming language, allowing it to run on a variety of hardware platforms. Java is an excellent choice for the development of distributed agent applications because it is object-oriented, multi-threaded (each agent consists of several threads), has a rich class library supporting network communication, as well as being portable across operating systems.

In creating ZEUS, our design philosophy has been to delineate the domain-level problem-solving abilities from the agent-level functionality. In other words, we provide classes that implement communication, co-operation, co-ordination, task execution and monitoring, and exception handling, leaving developers to provide the code that implements their agents’ domain-specific problem-solving abilities.

A detailed description of the ZEUS agent development methodology is beyond the scope of this paper1, but we shall explain how agents are created using the tool-kit. The first stage is for the developers to specify the attributes of individual agents through a visual editor. Once an agent is defined, another editor facilitates the definition of each task the agent is capable of performing. At this point the developer only needs to specify each task in terms of what facts are produced and consumed. Once all the agents, tasks and facts have been specified, the Generator tool can be invoked, this creates a Java source code implementation for each agent, and a stub for each task. The individual agent source programs can be compiled into executable agents, and so the developer’s sole task is to provide an implementation for each task.

2.1 The Components of the ZEUS Tool-Kit

The ZEUS tool-kit is a collection of Java class libraries that can categorised into three functional groups, as shown in Figure 1.

1 More details on this methodology can be found at : http://www.labs.bt.com/projects/agents/research/collaborative.htm

• Figure 1 – The Components of the ZEUS Agent Building Tool-Kit

The Agent Component Library

This is a package of Java classes that implement the functionality of collaborative agents; i.e. these classes are the ‘building blocks’ of the agents created during the generation process. The most significant of these are described in Section 2.2. Also included in the class library are: a set of co-ordination strategies, such as the contract-net protocol; a number of predefined organisational relationships, such as peer and superior; and a performative-based agent communication language with a comprehensive instruction set.

In order to maximise future compatibility the components of the ZEUS tool-kit utilise ‘standardised’ technology whenever possible; for instance, communication takes place through TCP/IP sockets using a language based on the Knowledge Query Management Language (KQML), [Finin and Labrou 97]. In this spirit we plan to adopt the Agent Communication Language (ACL) that has recently been specified by the Foundation for Intelligent Physical Agents (FIPA)1.

The component library also provides full implementations for the three types of standard utility agents: the Agent Name Server, the Facilitator and the Visualiser. The utility agents fulfil a support role in their society and can be used in any application without modification. The Agent Name Server provides a white pages service, matching agent names to network address just like the Domain Name Servers of the Internet. The Facilitator provides a ‘yellow pages’ service similar to the ‘Yahoo!’ index; it is used by agents looking for others who are capable of a particular task or service. The role of the Visualiser agent is discussed next.

The Visualisation Tools

An inherent problem of a distributed system like an agent society is attempting to visualise its behaviour. This is because the data, control and active processes are all distributed across the society. Consequently the analysis and debugging of multi-agents systems is difficult, as each agent has only a local view of the whole. This puts the onus on the user to integrate the large amounts of limited information each agent generates into a coherent whole.

The Visualiser Agent provides a solution to this problem by asking every agent to forward a copy of every message they send to other agents. The messages received can then be collated, interpreted and used to create an up-to-date picture of the agents’ collective behaviour. The user interacts with the Visualiser agent through the five Visualisation Tools listed in Figure 1, with each tool visualising a different aspect of agent society. For instance, the Society Viewer shows all agents known, and the type and frequency of the messages they send; whilst the Reports Tool shows the state of agent tasks and sub-tasks.

The Agent Building Software

These components implement the editors that enable users to interactively create agents by visually specifying their attributes and strategies. In order to generate the code for a specific application system, the Generator tool inherits code from the Agent Component library, and integrates the data from the various visual editors. The resulting Java program code is then compiled and executed normally. Existing systems can be linked to the agents using the Application Programmers’ Interface (API) of the wrapper class that is also part of the tool-kit.

Used together these components facilitate the engineering of intelligent collaborative agent systems. The developer describes the intended agents with the Agent Creation tools, which generates the source code using classes from the component library. Once their tasks have been implemented the agents can be executed, and observed using the visualisation tools provided.

2.2 The Anatomy of a ZEUS Agent

The logical model of a ZEUS agent comprises a definition layer, an organisational layer and a co-ordination layer. The Definition Layer comprises the agent’s reasoning (and learning) abilities, its goals, resources, skills, beliefs, preferences, etc. The organisation layer describes the agent’s relationships with other agents, e.g. what agencies it belongs to, what abilities it knows other agents possess, and what authority relationships exist. At the co-ordination layer each agent is modelled as a social entity, i.e. in terms of the co-ordination and negotiation techniques it possesses. Built on top of the co-ordination layer are the protocols that implement inter-agent

1 More information on the FIPA’97 Specification is available at: http://drogo.cselt.it/fipa/spec/fipa97/fipa97.htm

communication; whilst beneath the definition layer is the application programmer’s interface (API) that links the agent to the physical realisations of its resources and skills.

Figure 2 shows how this logical agent model is realised using the classes of the ZEUS Agent Component library. Communication is handled by the classes of the Mailbox, which is a complex entity consisting of several other objects; one of these is a Server object that runs in its own thread, accepting and storing incoming messages. Another object that runs in its own thread is the Message Handler, which periodically checks for new messages, parses their contents, and when necessary forwards the instructions to the Co-ordination Engine for action. The role of the Co-ordination Engine is to manage interaction with other agents, making possible the co-ordination and delegation of tasks.

• Figure 2 – The flow of information between the components of a ZEUS Agent

Like the Co-ordination Engine the Planner/Scheduler component is an active thread; its role is to maintain a record of the agent’s commitments, and launch tasks when necessary. Another thread, the Execution Monitor then informs other internal components of the progress of tasks. Finally there are several static databases that do not run in their own threads, their role is merely one of storage.

Central to the feasibility of the ZEUS tool-kit is the notion that all agents are composed of the same components. Where individual agents differ is in the strategies that are executed by their Co-ordination Engines, the acquaintances known, the resources held, and the tasks they are capable of performing. But how useful are the generic ZEUS agent components to a marketplace application? Some components are not currently being exploited to their full potential; (for instance the Planner and Scheduler is under employed now, although it may soon be used to plan a supply chain by negotiating for the necessary resources). On the other hand, the features offered by the Co-ordination Engine have been fundamental to the rapid development of our marketplace; this is one of the issues discussed next.

2.3 The Benefits of Building Electronic Marketplaces with ZEUS

The components in Figure 2 illustrate the complexity of a typical collaborative agent. This inherent complexity means there are considerable benefits to be gained by using a tool-kit, as every agent created using ZEUS comes with each of these components fully implemented. For instance, complex components like the Co-ordination Engine are the result of many man-months of implementation and testing. The reuse of such components has already facilitated the rapid development of agent applications in various domains, [Nwana et al 98].

Hence it is worth emphasising that whilst the ZEUS tool-kit was not specifically designed for electronic commerce applications, it was generic enough to create our marketplace agents. In order to evaluate the benefit of using ZEUS to build electronic marketplace applications it is worth considering what makes building agent- based marketplaces so difficult.

• The Information Discovery Problem. In a marketplace agents need some means of discovering what is on offer, and where on the network the vendor can be found. Given the dynamic nature of the market it is not sensible to hard-code this information into the agents, but rather to provide an index of agents and current offers that can be updated frequently. As the ZEUS Name Server and Facilitator agents already provide these services to the market participants, we did not need to re-solve the problem of information discovery during the development of our marketplace.

• The Communication Problem. In order to perform negotiations and transactions, the marketplace agents must communicate using a common language via a common protocol. Whilst protocols like TCP/IP can facilitate the transfer of information between the host machine of each agent, the lack of a standard language to express messages is an obstacle to developing an agent marketplace. As all agents created using the ZEUS tool-kit share the same communication mechanism, we have a means of moving information between agents. However, whilst our KQML-based language has been adequate for the exchange of transaction information, the challenge in the future will be for our agents to interact with those developed by other researchers; this requires the adoption of a standard agent communication language, such as FIPA’s ACL.

• The Ontology Problem. Even if a universal communication language were to be adopted, the participating agents would still only be using a common syntax. Equally important are the semantics of the language: the terms used, and knowledge that relates to these terms’ definitions, attributes, relationships and constraints. Our local solution to the Ontology Problem has been to create a small ontology of the concepts the market supports and supply each agent with a copy when it joins the market. A future challenge will be the adoption of a universal ontology, or a means of translating between different ones.

• The Co-ordination Problem. Given our agents can communicate and understand each other, the problem remains of how they co-ordinate their activities. For example, on initiating an auction an agent has the opportunity to set the ‘house rules’: parameters that describe when bids are expected, when negotiation will occur and the conditions for closing a deal. These rules must then be communicated to the other agents participating in the auction so that they know when and how to bid. Whilst these strategies could be encoded into each agent, this would be time-consuming to implement, as well as being inflexible as new strategies could not be defined at run-time.

Consequently all agents created using ZEUS have a generic Co-ordination Engine; this allows the run-time behaviour of agents to be customised declaratively by providing new state-transition graphs. This avoids the need to re-implement the Co-ordination Engine when new behaviour is desired. During the development of our agent marketplace we created new protocols that implement the conventions of several types of auction; e.g. English/Vickery/Dutch auctions. With these new protocols, new types of agent behaviour are possible. As a result, the generic agents provided by the tool-kit can now offer items to others, participate in auctions, and propose and counter-propose bids.

In summary, we attribute the rapid development of our agent-based marketplace to the substantial amount of code reuse, made possible by the ZEUS tool-kit. This has only been useful because the components provided by the tool-kit were generic enough in nature to be used in our prototype electronic marketplace application with little modification. A comparison with other agent building tool-kits is difficult however, since at time of writing no others seem to have been used to implement a marketplace.

Now that the framework used to build our agent-based marketplace has been introduced, we shall discuss the features of our experiments.

3. Ongoing Experiment – A Broker-less Marketplace

In this scenario, each agent will have the ability to contact every other agent and negotiate to buy and sell directly. This means there is no role for intermediary agents such as brokers. The objective is to test the existing agent electronic commerce framework, using a relatively small number of agents. This arrangement is illustrated in Figure 3 below.

• Figure 3 : A Fully Connected Marketplace

We have implemented this market first because it consists of only one type of agent, which has not been difficult to create given the peer-to-peer communication protocol provided by the ZEUS tool-kit. The characteristics of this experiment are summarised in Table 1.

Scenario Every participant is given an item, and an equal amount of virtual money, which can be used to trade with other participants.

User Objectives The goal for participants is to sell the item they begin with, and to buy at least one other item from someone else. The participant with the most virtual money at the end of the experiment will be declared the winner.

Agent Distribution Agents are spread across local area network as applications on separate machines. They will communicate using the peer-to-peer messaging facility of ZEUS.

Experiment Length Agents to run continuously, experiments are likely to take several hours.

User Participation  Users will set their buying and selling strategies.  Bids may be evaluated and awarded manually or automatically depending on

user preferences.

Experiment Objectives

 The evaluate the feasibility of the ZEUS tool-kit for e-commerce applications  To demonstrate how agent behaviour could be changed by the addition of

new co-ordination protocols  To investigate the ability and willingness of human users to participate in an

electronic marketplace through the use of agents  To investigate the potential scalability of a society of ZEUS agents

• Table 1 – A Summary of the features of our ‘Fully Connected’ Marketplace Experiment

The marketplace application provides a useful means for evaluating the scalability of ZEUS agents. Thus far most applications created with ZEUS have involved a relatively small number of agents running for short periods of time – whereas this experiment will consist of a larger number of agents that will run for extended periods of time. However, the scalability of this arrangement is limited, as the number of potential buyers or sellers with whom each agent must communicate will quickly become unmanageable as new agents enter the market. This problem should be alleviated through the addition of brokers as discussed in Section 5.

AGENT

AGENT

AGENTAGENT

3.1 Agent User Interface

New user interfaces are necessary in order to issue commercial instructions to our generic agents. Together with the auction conventions, these parameters will determine how an agent behaves in response to market conditions. We have aimed to make the agent interfaces easy to learn and use in an effort to attract as many non-expert users as possible. With a large number of users, we will be better able to simulate complex, realistic marketplaces. In order to facilitate unfamiliar users, a specialised user interface has been created for this experiment. Our intention has been to hide the underlying complexity of the marketplace agents from the people that use them.

3.1.1 The Marketplace Window

This window provides an overview of the current state of the market. Items offered for sale are listed, together with details of the vendor, the current market price, and the time remaining for bids. All offer information is colour-coded to represent its current state, e.g. on offer, changed, expired, deal struck etc. State information provides a means of filtering so, for instance, only offers that have changed recently can be displayed.

New items can be offered for sale by choosing the ’Sell Item’ button, which brings up the Selling Window. If an existing offer is double-clicked the Buying Window appears, unless the item in question is owned by the user, in which case the Selling Window re-appears allowing them to change the offer parameters. A sample marketplace window is shown in Figure 4.

• Figure 4 – The Marketplace Window of a ZEUS Agent, showing the state of all current bids

3.1.2 The Selling Window

To offer an item for sale a user needs to tell their agent the opening price, the length of time available to complete the transaction, and how many times over this period the price will be recalculated. The agent must also be instructed how the asking price will change in response to offers, or the lack of them. To describe the change of a price we have adopted the approach used described in [Moukas et al 97] – as a graph with three distinct portions:

• an initial static period, this represents an ’ideal price’ where the agent will not alter its selling price

• a dynamic period, when the agent will progressively increase or decrease its price according to demand

• a final static period, this ’plateau’ corresponds to the floor price, this is only present when the vendor is not desperate to sell and wants to prevent the price free-falling below the pre-set reserve price

The vendor’s graph depicts the change in price (downwards) that occurs over time if the asking price is not met. For convenience users can choose the shape of this graph from a library of predetermined graphs. One such example is ‘cool-headed’ – this graph remains static for a short period, and then gradually falls. Alternatively, the user can change the graph parameters using the slider bars provided, giving the user the flexibility to customise their own transaction policy. The window through which the current selling strategy is displayed and configured

is shown on the left in Figure 5. The two other parameters necessary to form the selling strategy are the initial asking price and the auction duration; these values are entered through the main Selling window, shown on the right in Figure 5. Once the strategy and its parameters have been specified the agent’s asking price can be automatically recalculated in response to market conditions.

• Figure 5 – The Selling Strategy Window, with pop-up Price Function Window (left)

The Selling Window above also shows the other parameters the vendor can specify, such as the exception policy. This compels the agent to perform some action if the highest bid received by some point in time is below a certain threshold. This allows the user to be alerted or withdraw the offer if no sufficient bids are received. The user can also set an authorisation policy – if the ’prompt me to accept’ option is chosen, the agent will ask its user before agreeing to any transactions. Alternatively, choosing the ’auto accept’ option trusts the agent to perform transactions when a reasonable offer is received.

3.1.3 The Buying Window

Items are bought through potential buyers making bids. To formulate a bid an agent needs to be told the initial price and the highest price the user is willing to pay. If the item must be bought quickly, the user can also specify a deadline time. The user then specifies a graph to reflect how bids will increase over time until the vendor’s selling price is reached. Finally the user can set an authorisation and exception policies, these have a similar effect to those of the selling window. A sample Buying Window is shown in Figure 6.

• Figure 6 – The Buying Strategy Window with pop-up Bid Function Window (left)

Currently the buying and selling strategies are unidirectional, i.e. bidding prices commence low and increase whilst asking prices start high and decrease. It is possible for a vendor to increase their asking price if more than one acceptable bid is received, although this option is not available from the windows shown. The bidding price is not expected to fall because currently there is only one supplier for each bid. If the scenario represented a true market with multiple suppliers we would expect the bid price to fall according to the supply. This issue is being investigated as brokers are added and the system evolves into a true marketplace.

3.2 How it works

Our marketplace does not operate in true real-time; instead it consists of a series of rounds whose length is set by the vendor. Our use of fixed-length rounds stems from the fact that agents created using the ZEUS tool-kit operate in discrete time-grains of arbitrary length. As our scenario has many potential buyers interacting with a single seller, the time-grain of the vendor agent is used to synchronise transactions. At the end of each round the vendors and any interested bidders re-evaluate their offers and bids respectively. Over time these changes form a graph, as shown in Figure 7.

• Figure 7 – How Transactions are Agreed

The interpretation of this graph is as follows. Trading starts when the vendor offers an item for sale and sets an opening price. Agents may enter an auction at any time, and during the next round the offer is detected by a potential buyer, who enters an opening bid. Any change in the vendor’s asking price is governed by its selling strategy, and in this case the asking price is maintained at its opening level for six rounds. However the bidder is keen to purchase and so begins to raise its bid after the third round.

By the seventh round the vendor is beginning to drop its asking price. The relaxing of the asking price is only known by the vendor, who is under no obligation to reveal that the asking price is falling. Instead the seller will continue to inform the buyer that their bids are insufficient. Eventually in the tenth round the buyer’s bid exceeds the price the seller is willing to accept, whereupon the transaction is agreed, (subject of course to the agents’ users’ agreement, if needed).

From Figure 7 we can see that the seller got a good deal, with the buyer paying a higher price than the seller was privately willing to accept. This is due to the negotiation protocol used, where the seller could conceal its asking price and wait for bids before re-evaluating its position. This provides an example of how the ‘auction rules’ influence the market – this is one of the factors of our experiment that is discussed in the next section.

TIME (in rounds)

PRICE

1 2 3 4 5 6 7 8 9 10

Opening Price

Initial Bid

Purchase Price

4. Experiment Discussion

At this early stage we have insufficient results from which to draw conclusions, nevertheless there are several interesting issues raised by this experiment that are worth discussing.

Auction Conventions

It is desirable to provide sellers with a variety of auction conventions so that they can choose the convention that best suits their requirements. For instance, the ‘Vickery’ auction tends to conclude quickly, ensuring a quick sale, whilst other auction conventions can earn near the optimal market value under certain circumstances.

An example of the impact of the auction convention used is shown in Figure 7. In this case the selling agent did not need to reveal its asking price, and could wait until all bids were received before re-evaluating it. As a result, the buyer’s final bid was higher than the seller’s minimum price of the last round and considerably higher than the price the seller would have dropped to in the tenth round had there been no bids. Other ‘auction rules’ govern who wins the auction if more than one agent bids above the asking price in the same term – possibilities include the highest bid or continuing the auction until all but one party drop out.

From this example we can see that the auction protocol used may have a considerable effect on the final price agreed between parties. Thus if the item for sale is unique, the user might choose an open auction with a low starting price in order to encourage competitive bidding. This is one of the advantages of using ZEUS agents, as new behaviour can be added by providing new state-transition graphs that implement new auction conventions.

The Implementation of Time

In a ‘real-time’ marketplace the synchronisation of agents becomes an issue. We have avoided potential synchronisation problems by creating auctions that consist of discrete intervals, or rounds. As our market consists of one seller and many buyers, the length of each round is set equal to the time-grain of the selling agent. In order to hide the functionality of agents from the users, the time-grain duration is set indirectly by the seller when they enter the duration of the auction and the frequency that the selling strategy will be revised, (which is equal to the number of rounds). If the time-grain is sufficiently small, the auction will provide the illusion of a real-time market.

By using time-grain synchronisation there is no need for a common clock that time-stamps bids as they are made. Hence all bids received by a seller are evaluated on a ‘first come – first served’ basis. Whilst this could mean that a bidder loses out because their bid was delayed on route to the seller, this is not a serious issue whilst our agents remain on a local area network, where transmission latencies are low.

Agent Autonomy

In our experiment all agents are under the ultimate control of a human user, although the user can choose to delegate decision making to their agent. But the simplicity of the market means the scope for intelligent autonomous action is limited, although there may be potential for agents to assess their rivals’ bids and infer their intentions.

But whether users would actually trust their agents to autonomously spend real money is an important issue. Perhaps to convince sceptical users of the merits of automated trading we should perform the electronic commerce equivalent of the ‘Turing Test’, where the performance of autonomous agents can be compared with those directly under human control.

The Trading Ontology

In order to facilitate automated trading, we have restricted trade to limited ontology of items; for instance, one of the items supported is ‘coffee’. This is because our agents are not smart enough to determine what exactly the user wants to buy; of those agents with this ability, the Jango1 ‘ShopBot’ is one of the best examples. Our limited ontology is thus preferable to allowing users the freedom to describe their products in plain text, such as ‘1 kilo of roasted Brazilian coffee beans’.

1 Jango can be seen in action at http://www.excite.com/channel/shopping/

A trading ontology operates on the assumption that any particular item has the same intrinsic value as another item of the same class – i.e. that the items are commodities. This is not to say that all items of a particular class will have the same price – the buyers and sellers will set this dynamically in the marketplace according to supply and demand. The advantage of a limited trading ontology is that it avoids potential complications, like attempting to distinguish between ‘good’ quality and ‘bad’ quality items. However traders will be reluctant to employ a system with a small trading ontology, for reasons that are discussed next.

Product Differentiation and Market Stability

Traditionally traders attempt to attract customers using the “5 P’s”: product, price, place, position and promotion. These attributes allow traders to differentiate themselves from their competition through factors like physical proximity to the customers, transport costs, value-added services (like warranties), and lures such as loss leaders. These differentiation factors can be represented in an electronic marketplace, but only if the trading ontology is rich enough. The problem is that detailed trading ontologies are time-consuming and difficult to build.

Nevertheless, the provision of differentiation is vital because it allows vendors to avoid ‘commoditisation’, a situation where identical items from different retailers become perfectly substitutable, (i.e. equally as good as each other). Ultimately the danger is that without differentiation the market can become “frictionless”. In economics the term ‘friction’ refers to the factors that keep markets from working according to the textbook model of perfect competition, [Case 96]. In a theoretically frictionless market the only differentiation possible between vendors is price.

Shopping agents can facilitate the emergence of a frictionless market by visiting every vendor and analysing only price to find the lowest possible value. As a result vendors may be drawn into a price-cutting war to attract customers; however they risk being caught in a discounting feedback loop, which will ultimately lead to a ‘price crash’. This will initially benefit the buyer, but only until the point where the lack of competition means prices stop falling and begin to soar. Consequently we consider some means of differentiation as vital to maintaining market stability.

The need for differentiation was highlighted by the experiences of the ‘BargainFinder’1 project. Its creators, researchers from Andersen Consulting, found that many companies did not want to be compared on price, and so attempted to block the agent from their sites. However, at the same time the agent’s creators received messages from many other companies asking to be visited. The moral of the story is that vendors are only likely to participate in electronic marketplaces if they can appear sufficiently different from their competitors. If vendors are compared on price alone, we may find only ‘discount’ retailers participating.

Hence to maximise differentiation a comprehensive trading ontology must be created. This will enable buying agents to take into account the additional costs of any goods they consider. For example this might be a delivery cost, or weighting dependent on the quality and speed of service provided by that particular vendor in the past. Whether this approach is sufficient to ensure market stability will have to be verified by future experiments.

Market Prices and the Role of Brokers

The market price of a commodity is its value, the amount it will fetch on the market at a particular point in time. Market prices fluctuate according to supply and demand, and so it is very difficult for individual agent to estimate the market rate from their local view of the marketplace. Hence to determine an accurate market price value, a global picture of production and consumption is required. This is possible through the use of dedicated ‘Broker’ agents who will monitor all offers, bids and transactions in order to derive the current market rate.

As most real world marketplaces have evolved without exact models of supply and demand, it will be interesting to observe the effect of accurately knowing the market price on the trading policies of both buyers and sellers. For instance, what form will inflation take in a marketplace where supply and demand can be accurately monitored for emerging trends? If there is a run on a commodity, will a corresponding increase in supply, and hence competition, be sufficient to constrain prices? Could supply gluts be anticipated and avoided by vendors co-operating and not saturating the market to the point where it collapses? Or will producers collaborate to form de facto cartels? And will vendor profits suffer if the market rate is accurately known?

Brokers can also be responsible for more than just the calculation of a market rate, as the next section explains. 1 For more information on the BargainFinder project, see http://bf.cstar.ac.com/bf/

5. Future Work – A Broker Facilitated Marketplace

Our next stage of development will be to introduce an intermediary ‘Broker’ agent to our experiments. This will serve as a facilitation service, with any agents wishing to buy or sell contacting the broker to discover an agent with whom they may be able to trade; this arrangement is shown in Figure 8.

• Figure 8 : A Marketplace based around a single broker

Initially the broker will serve as a notice board or ‘classified ads’ service, providing a list of agents and the items that they are attempting to buy and sell. This frees agents from having to poll every other agent in the society in order to determine what items are available to trade. Ultimately once all transactions pass through a single entity, a global picture of supply and demand is possible, allowing a ‘market price’ to be calculated. This will allow potential buyers to base their buying strategy on the recent price history of a commodity, giving a more accurate perception of the true worth of what they are buying.

However, in case of high demand, having no broker may suit the vendor, who can continue to accept sealed bids until the sale deadline, and then choose the highest offer. Hence for brokers to be practical they must also be useful to vendors; hence they may advertise the vendor’s products in an attempt to attract new custom.

We intend to test the hypothesis that a broker-facilitated marketplace is best implemented using the client-server approach, with the clients being the trading agents and the broker the server. It is expected that there will be several advantages to having a single server centrally process all transactions, as it should provide a consistent record for accounting and billing, as well as making it easier to enforce transaction security. It will also being interesting to compare the profits made without brokers, to the profits made when a broker is present and an accurate market rate is known.

Ultimately we would expect the marketplace to possess more than one broker, and there are several reasons why this may be desirable:

• scalability – because of their centralised nature, brokers are the potential bottlenecks of the marketplace, and there is a danger that as the number of trading agents increases the load on the broker will become too great for it to manage

• redundancy – a market dependent on a single broker will collapse if it ceases

• competition – to ensure that the brokers’ charges remain competitive

• distribution – trading agents may be widely dispersed and employ their own local brokers, this is the case with global commodity markets

Our scalability experiments will determine how many agents a single broker can comfortably support under particular conditions. Once this point is reached we would expect to have to introduce extra brokers in order to reduce the computational load experienced by the individual broker agents.

AGENT

AGENT

AGENTAGENT BROKER

6. Evaluation

A recent survey paper by the MIT Agents group [Guttman et al 97] referred to consumer buying behaviour as a process with six fundamental stages. The first stage, Need Identification, leads to Product Identification, then Vendor Identification, and then to the Purchase decision. The latter stages concern the actual purchase and delivery, and the evaluation of the product or service. This model of buying behaviour was used to differentiate current agent-based e-commerce systems by the facilities offered. The three categories used for comparison were product brokering, merchant brokering and negotiation, of which the latter is most appropriate to our initial experiments, as they concern the auction of commodities without the use of brokers.

A search of the ‘Yahoo!’ index reveals a considerable number of on-line auction services, although few could claim to truly employ ‘agent’ technology. It is felt that the most similar systems to the ZEUS marketplace are Fishmarket1, [Rodríguez 97], AuctionBot2, [Wurman 97], and Kasbah3, [Chavez 97]. A brief comparison of the features of each is shown in Table 2.

Feature $XFWLRQ%RW )LVKPDUNHW .DVEDK =(86�0DUNHW 3URWRW\SH

Distribution of Agents

Web-based client, server side agents

Network based with centralised seller and distributed buyers

Web based client, server based virtual market

Buyer and Seller agents distributed across a LAN

User defined price functions

Configurable via HTML form or programs using API

Function parameters configurable via GUI

Limited to choice from a list

Strategies and function parameters configurable via GUI

Two-way bargaining

Yes Not relevant to auction scenario

Yes Yes

Provides Active and Pro-active agents

Yes Yes Yes Yes

Multiple auction types possible

Yes Yes No Yes

Transactions have many sellers and many buyers

No – transactions involve an item from a single seller

No – each transaction involves goods from a single seller

Yes – can choose amongst several potential vendors

No – currently only one seller to many buyers

Merchant Brokering

Users choose vendors from category index

‘Auctioneer’ chooses which goods to offer for sale from a lot

Facilitated by dedicated broker agents

Users choose vendors from publicised offers

• Table 2 – A Comparison of the features of some Agent-based Marketplaces

The criteria used for comparison in Table 2 are as follows: the “Distribution of Agents” category describes the organisational architecture of the marketplace, and whether the users’ agents are autonomous processes with their own embedded features or ‘thin’ clients that call services on the server side. “User defined price functions” relates to how the user exerts control over their agent’s behaviour, and “Two-way bargaining” refers to the ability to make offers and counter-offers.

1 http://www.iiia.csic.es/Projects/fishmarket/newindex.html 2 http://auction.eecs.umich.edu 3 http://kasbah.media.mit.edu

Of the other categories, “Active Agents” in this context refers to processes that react to market conditions, and “Pro-active Agents” to processes capable of autonomously initiating offers. “Multiple auction types” refers to the support for different co-ordination protocols. “Transactions have many sellers and many buyers” refers to individual transactions where there may be multiple buyers and sellers in competition. Finally “Merchant Brokering” refers to the process whereby users identify who has a desired item for sale, and at what price.

In summary, AuctionBot implements a server-side auction whose participants can configure their strategies through an API that is accessible through a web interface. Kasbah is also web-based, consisting of server-side agents that enable users to buy and sell; whilst it is less configurable, it provides a better support infrastructure, providing brokers to match buyers to sellers.

The Fishmarket system also differentiates buyers from sellers, although the auction is not conducted through the web. A significant feature of Fishmarket is that its conventions can be readily customised, this has been used to simulate a real-world fish-market where the auctioneer chooses what to offer and invites bids from interested parties. Like Fishmarket, the conventions implementing the market in the ZEUS prototype can be changed by reconfiguring the finite state machine that represents the auction rules. The unique feature of the ZEUS market is that the participants are distributed client-side agents that have the ability to both buy and sell. Significantly, all these systems allow users to differentiate their agents from their rivals by configuring the buying and selling parameters, and all provide a means to react to market conditions.

7. Conclusions

This paper has described the creation of an electronic marketplace whose agents are capable of both buying and selling. But is it worth implementing a market using agents? The inherent social ability of agents makes them well suited to negotiations over transactions, and as they are autonomous the agents can react to market conditions on behalf of their users. One potential disadvantage of complex concurrent software entities like agents is their high development overhead, but with our prototype market we hope to have shown that an agent building tool-kit can expedite development and supply the necessary functionality for a marketplace.

To turn the generic agents created by the ZEUS tool-kit into marketplace participants has involved modifying how agents behave and interact. By using the new user interface windows created for this experiment, a user can send instructions to their agent that will modify its behaviour. For instance, the agent’s buying strategy can be configured; this is necessary because the agents are currently not sufficiently intelligent to derive these strategies themselves. We have also added several co-ordination strategies that enable agents to participate in auctions by dynamically setting bidding, negotiation and finalisation strategies. Before this work, the ZEUS tool-kit contained only a few simple strategies, like master-slave and contract-net, now the more sophisticated auction protocols are part of the ZEUS co-ordination strategy library.

However we have only begun to explore the possibilities of agent-based marketplaces, hence our discussion of future plans. One development that would provide scope for agent intelligence would be the introduction of broker agents. A broker would provide a global model of supply and demand, allowing transactions to be based on a true market price, and overcoming the current artificial restriction of only having one buyer per commodity.

Looking to the future, a relatively recent document from the European Commission [EC 96] has predicted that by the year 2000, the majority of the world’s financial transactions will take place online, with 14 million buyers spending an estimated $24 billion through the Internet alone. Another prediction is that by the year 2000 46m consumers in the U.S alone will be buying goods and services online, spending an average of $350 a year each, [Anderson 97]. Hence as electronic commerce becomes ubiquitous, we would not be surprised if the descendants of today’s experimental agent marketplaces become a significant technology.

Acknowledgements

Thanks to Hyacinth Nwana, Divine Ndumu, Haydn Haynes and Barry Crabtree for their contributions to the project and their feedback regarding this document. This work was funded by BT Laboratories.

References

[Anderson 97] C. Anderson. “In Search of the Perfect Market”, Economist Magazine, September 1997. http://www.economist.com/editorial/freeforall/14-9-97/

[Case 96] J. Case, “The Friction-Free Economy”, Inc. Magazine, June 1996, page 27. Http://www.inc.com/incmagazine/archives/06960271.html

[Chavez 97] A. Chavez, D. Dreilinger, R. Guttman, P. Maes. “A Real Life Experiment in Creating an Agent Marketplace” Proceedings of PAAM ’97, p159-178, April 1997. Available from : http://ecommerce.media.mit.edu/

[EC 96] European Commission, “Information Engineering 1999-2005: A Vision of the Future”. VOOGEN, June 1996.

[Finin and Labrou 97] T. Finin, Y. Labrou. “KQML as an agent communication Language”, in Software Agents, J.M. Bradshaw, (editor) MIT Press, Cambridge, Mass., p291−316, 1997.

[Guttman et al 97] R. Guttman, A. Moukas, P. Maes. “Agent-mediated Electronic Commerce: a Survey”. To appear in the Knowledge Engineering Review, June 1998. Available from : http://ecommerce.media.mit.edu/

[Moukas et al 97] A. Moukas, R. Guttman, G. Zacharia, P. Maes. “Multi-Agent Systems and Electronic Commerce: a PDA-based system for comparison shopping”. To appear. Available from : http://ecommerce.media.mit.edu/

[Ndumu and Nwana 97] D.T. Ndumu, H.S. Nwana. “Research and Development Challenges for agent-based systems”. IEE Proceedings On Software Engineering, Volume 144(1), p2-10, 1997.

[Nwana 96] H.S. Nwana, “Software Agents: An Overview”, The Knowledge Engineering Review, Volume 11(3), p205−244, 1996.

[Nwana et al 98] H.S. Nwana, D.T. Ndumu, L.C. Lee. “ZEUS: An Advanced Tool-Kit for Engineering Distributed Multi-Agent Systems”. Proceedings of PAAM ’98, p377-391, March 1998.

[Rodríguez 97] J.A. Rodríguez, P. Noriega, C. Sierra, J. Padget. “FM96.5 A Java-based Electronic Auction House” Proceedings of PAAM ’97, p207-224, April 1997.

[Wurman 97] P. R. Wurman, M.P. Wellman, and W. E. Walsh. The Michigan Internet AuctionBot: A Configurable Auction Server for Human and Software Agents. Available from: http://www-personal.engin.umich.edu/~pwurman/Papers/


Comments are closed.