Note: Descriptions are shown in the official language in which they were submitted.
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
1
APPARATUS FOR NEGOTIATION
This invention concerns apparatus for negotiation and finds particular
application
in collaborative software agent systems, for instance for process management
or for
electronic trading.
In collaborative software agent systems, it is often necessary for the agents
to
collaborate either amongst themselves or on behalf of another entity. For
instance, in
process management a community of agents might between them control resources
for
running tasks and sub-tasks which together provide an overall process or
service. Each
resource may however be available to more than one agent, or to other
processes
altogether. Agents may therefore have to negotiate amongst themselves in order
to arrive
at an efficient way of exploiting the available resources to provide the
overall process.
Alternatively, in electronic commerce a community of agents might negotiate
amongst
themselves on behalf of other entities to arrive at an acceptable transfer of
resources
between the entities.
It is known for a set of collaborative software agents to negotiate by issuing
bids
in response to offers. The process may be reiterative so that a failed bid can
be reviewed
and a new bid issued.
Some negotiation/auction mechanisms do exist which involve exchange of more
complex bids rather than simple prices. US patents US05689652 and US05845266
describe a system that utilises bids expressed as 2-dimensional tables, with
the rows and
columns representing price and amount bins, and the entries denoting the
degree of
desirability of a transaction at the given number / price point. A central
mechanism
decides pair-wise transactions that maximise the mutual benefit as indicated
by the
entries in the table. Complex bids such as these allow the negotiation to
proceed in
parallel over a range of volumes, and allow more of the negotiation to be
performed by the
arbitration mechanism without recourse to the bidders.
These systems operate to deal with a very specific task; the matching of
traders
across a basket of transactions at different order sizes and prices. They are
particularly
designed for traders in securities.
However, in the broader view of negotiation for instance in process
management,
where the transaction might be for processing capacity, such a bid mechanism
is not
particularly appropriate.
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
2
Automated negotiation using a variety of strategies has been implemented in
various multi-agent systems. Many of these fall into the so-called contract
net family. Here
a purchaser (say) issues a call for bids and potential suppliers respond with
bids. The
purchaser evaluates the bids according to some criterion, and either selects
one or issues
a further call. Effectively this is a single auction mechanism with vendor
acting as its own
auctioneer, except that the acceptance criterion need not be based on price,
and it and
the strategies for revising calls and bids need to be defined on an
application by
application basis.
A number of research projects have developed decentralised control
mechanisms for distributed systems based on market analogies. Many of these
are based
on mathematical results of a branch of microeconomic theory. Here, the world
is divided
into customers/suppliers of goods, and producers (who can transform the types
of goods
by destroying some in order to create others). The levels of supply, demand
and
production are functions of the set of prices for the goods (known as utility
and production
functions respectively). These prices apply globally, that is all transactions
in a particular
good at a given time take place at the same price, which is known to all. The
set of prices
is determined by a mechanism that operates in between rounds of production and
trading.
This sets the prices to be those that minimise the difference between overall
supply and
demand (taking into account production and consumption by producers).
Thus operation proceeds in two alternating phases: one in which utility and
production functions are used to derive global prices using the current levels
of stocks of
the customer/supplier agents; the other in which trading and production levels
are
determined based on the prices. In this latter stage, or in a separate third
stage, goods
can also be introduced into the system from external sources, or removed, in
amounts
determined by external factors. The classical mechanism for this first stage
is known as
tatonnement (French for groping!). Here, a central agency quizzes agents for
their level of
demand for a particular good given a hypothetical set of prices. The central
agency totals
this demand, uses it to derive a revised set of prices, then quizzes the
agents regarding
demand for the same or another good. This procedure is repeated until an
optimal set of
prices is found. A variant on this is a mechanism originating with Wellman of
Michigan
University in which price-demand curves for a good, given a set of prices for
the other
goods, are returned rather than a simple demand level.
According to an embodiment of the present invention, there is provided a
method
of negotiation, for use in controlling exchange of one or more resources such
as goods or
services amongst at least two negotiating entities, the method comprising the
steps of
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
3
i) receiving provision bid data to represent conditions for provision of a
resource by a first negotiating entity;
ii) receiving receipt bid data to represent conditions for receipt of the
resource
by a second negotiating entity; and
iii) comparing the provision and receipt bid data to determine whether there
is
a negotiation solution between the first and second negotiating entities
wherein issued bid data represents one or more boundaries of an acceptable
region of
multidimensional deal space, and said comparison comprises determining whether
there
is an intersection of the regions defined by the boundaries of issued
provision bid data
and issued receipt bid data in the deal space to define a mutually acceptable
region from
which a negotiation solution can be determined.
Intersection of the regions might mean that there is intersection between the
boundaries of the bids but it may mean for instance that one region lies
wholly within the
other region, in which case the boundaries associated with the regions will
not themselves
intersect.
The boundaries may be surfaces or, in a two-dimensional deal space, the
boundaries might resolve to lines.
The boundaries may represent multiple components of a bid, such as price and
quantity, and/or time to delivery.
The issued bid data might comprise one or more sell bids and one or more buy
bids. Where there is a plurality of a first type of bid (sell or buy) but only
one of a second
type of bid (buy or sell), the method might further comprise the step of
comparing the bid
of the second type against each of the bids of the first type to identify a
preferred match,
such as a bid pairing which will result in a maximum amount of resource to be
exchanged.
Where there is a plurality of both types of bid, the method might further
comprise the step
of comparing several bids of the first type against several bids of the second
type to
identify a set of preferred bid pairings. A criterion for selecting preferred
bid pairings might
be for instance again that a maximum amount of resource will be exchanged.
There will
however be other criteria available, depending on the components of the bids,
such as
time to delivery.
According to a second aspect of the present invention, there is provided
apparatus
for use in controlling exchange of one or more resources, the apparatus
comprising an
input for receiving:
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
4
i) provision bid data to represent conditions for provision of a resource by a
first negotiating entity; and
ii) receipt bid data to represent conditions for receipt of the resource by a
second negotiating entity;
the apparatus further comprising comparing means for comparing the provision
and
receipt bid data to determine whether there is a negotiation solution between
the first and
second negotiating entities,
wherein issued bid data represents one or more boundaries of an acceptable
region of
multidimensional deal space, and said comparing means makes a comparison by
determining whether there is an intersection of the acceptable regions defined
by the
boundaries of issued provision bid data and issued receipt bid data in the
deal space to
define a mutually acceptable region from which a negotiation solution can be
determined.
The apparatus may further comprise bid pairing means for selecting one or more
preferred bid pairings from amongst a plurality of available bid pairings
between received
provision and receipt bid data. Such selection may be done against one or more
criteria,
usually related to components of a bid represented by the boundaries expressed
in the bid
data, such as maximum quantity of resource to be exchanged in a community of
negotiating entities, or minimum total time to delivery of resource to be
exchanged in the
community.
In embodiments of the invention, bid data as issued may comprise an
identifier,
with or without further parameters, to represent boundaries of an acceptable
region, which
identifier and any parameters can be interpreted to give the boundaries within
the bid
data, rather than defining the boundaries themselves.
Although embodiments of the invention may be used in the real time exchange of
resources, such as goods or services, it is also possible that the exchange of
resources
takes place in the future, according to a stored record of the negotiated
exchange. Hence
embodiments of the invention might be used in generating or amending stored
terms of
exchange to be acted on, or potentially renegotiated, at a later date.
According to a third embodiment of the present invention, there is provided
negotiating apparatus for use in controlling exchange of one or more
resources, said
negotiating apparatus comprising:
i) an input for resource-related data relating to a resource to be exchanged;
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
ii) bid data generation means for processing received resource-related data to
generate a bid for provision or receipt of said resource, said generated bid
comprising a
representation of one or more boundaries of an acceptable region of
multidimensional
deal space, such that said generated bid can be compared with another bid of
like type to
5 determine the presence or absence of a mutually acceptable region, defined
by the
boundaries in the compared bids, from which a negotiation solution can be
selected.
Looking more broadly across a system according to an embodiment of the
invention, according to a fourth embodiment of the present invention, there is
provided
apparatus for use in controlling exchange of a resource between pieces of
equipment,
which apparatus comprises:
i) input means for receiving bid data,
ii) output means for outputting bid data ,
iii) means for storing at least one multicomponent relationship with respect
to at
least one resource,
iv) monitoring means for monitoring availability data for said resource,
v) bid assembling means for assembling bid data comprising a multicomponent
relationship determined at least in part by the monitored availability data,
vi) bid receiving means for receiving bid data comprising a multicomponent
relationship, and
vii) comparing means for comparing multicomponent relationships relating to a
common resource but derived from different respective bid data to determine
whether a negotiation solution exists.
In such apparatus, a multicomponent relationship may for instance comprise
components selected from the following group:
~ Price
Quantity
Time to supply.
If the resource concerned is a service of some sort, such as a communications
service, then examples of components might include quality of service, or
security levels.
A record of exchange of resource may be made when a negotiation solution is
detected, either for acting on immediately or in the future. The record may be
in the form
of a contract term for the supply of a resource in the future. Alternatively,
the apparatus
may further comprise trigger means for triggering transfer of resource between
said
pieces of equipment in accordance with an output of the comparing means. The
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
6
comparing means may, having determined that a negotiation solution exists,
also select a
solution and the transfer of resource will be in accordance with that
solution.
The apparatus may be supported at one or more sites in a communications
network and bid messages may be transmitted between parts of the apparatus
located at
the same site or at different sites.
The monitoring means for monitoring availability data may monitor a local
supply
of the resource. There may be more than one monitoring means and more than one
bid
assembling means, first and second monitoring means providing different
availability data
to respective bid assembling means. Where bid data for the resource comprise a
relationship involving quantity as a component, this has the result that the
same resource
may have different relationships associated with it at different locations or
with respect to
different pieces of equipment for instance.
Bid data may be transferred in any relevant protocol and may for instance be
in
the form of messages, as used between software applications sited on separate
platform.
Each multi component relationship may define boundaries, or surfaces, in a
multi-
dimensional deal space. Taking a simple example, a quantity/price relationship
for
instance may comprise a partially bounded two-dimensional area, the comparing
means
determining that a negotiation solution exists when the partially bounded
areas of two
quantity/price relationships at least partially coincide, for instance (but
not necessarily) to
create a fully bounded two dimensional area. Alternatively, the boundaries may
extend
in three dimensions where more than two components are involved.
An electronic trading system will now be described as an embodiment of the
present
invention, by way of example only, with reference to the following Figures, in
which:
Figure 1 shows schematically a network arrangement for providing processing
capacity and communications to support the electronic trading system;
Figure 2 shows a functional block diagram of a software agent and a mechanism
the
agent acts for, for installation using the network arrangement of Figure 1;
Figure 3 shows a functional block diagram of an auction engine for use in a
software
agent as shown in Figure 2;
Figure 4 shows communication flows between agents of an electronic trading
system according to Figure 1;
Figure 5 shows a variation of the arrangement shown in Figure 4;
Figure 6 shows a further variation of the arrangement shown in Figure 4;
Figure 7 shows a more complex arrangement of software agents in an embodiment
of the electronic trading system of Figure 1;
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
7
Figure 8 shows a pair of curves representing a sell bid which might be
assembled by
a software agent of the system;
Figure 9 shows two pairs of curves representing sell and buy bids mapped onto
one
another by an auction engine as shown in Figure 3,
Figure 10 shows a stockpile of goods on which a bid might be at least partly
based;
Figure 11 shows curves assembled for the purpose of establishing a clearing
price;
Figures 12 to 14 show price time bid curves for use in finding a preferred
solution
between entities for which price and time to delivery are components of a bid;
and
Figure 15 shows the development of a mutually acceptable region for the
entities of
Figures 12 to 14.
The following definitions are given as an aid:
Arbitration: negotiation employing a trusted third party or agreed mechanism
to assist in
reaching agreement on the terms of a deal. The candidate deal resulting from
arbitration will typically be binding.
Arbitration mechanism: a mechanism that, given a set of bids from two or more
parties,
identifies potential deals, and selects one or more of these according to
agreed
criteria.
Bid: a statement by one party of the terms under which a deal would be
acceptable or
unacceptable to it. A bid forms part of a negotiation. It may specify
explicitly or imply
restrictions on conditions under which it is valid (e.g. only for a certain
time after it is
issued, or until a particular event occurs). Subject to these restrictions, a
bid is
binding until revoked or modified via an agreed mechanism. Defaulting on a bid
(or
deal) will generally result in some penalty or sanction, or may simply be
forbidden
(i.e. compliance is enforced).
Contract: Formal binding expression of a deal
Deal: an agreement between two or more parties concerning the terms of supply
of goods
or services and compensatory payment (using money or in kind)
Deal space: the (multi-dimensional) mathematical space defined by the allowed
values
of the parameters to a deal. A bid may be considered as defining a region or
regions
of deal space (or subspaces of it) that are acceptable or unacceptable to the
issuing
agent.
Deal sub-space: a space of lower dimensionality than the deal-space, and
defined by
the allowed values of a sub-set of the deal parameters
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
8
Negotiation: the process of determining a mutually acceptable deal and
committing to a
contract, or reaching the conclusion that such a deal is not possible. A
negotiation
can be viewed as a search for a region of deal space that is acceptable to all
parties
to a potential deal, with a view to selection of a specific point in deal
space within
this region
Partial bid: similar to a bid, except that the statement concerns only a sub-
set of the
terms of the deal.
The embodiment of the invention described below is an electronic trading
system
(i.e. a system to support electronic trading communities) incorporating an
arbitration
mechanism dealing with bids of a particular form. The system is suitable for
agent
communities which manage resources (which could be for instance either goods
or
services) and buying and selling may be done in kind or by means of a system-
based
currency rather than a recognised monetary currency.
Referring to Figure 1, an agent community managing transfer of goods between
resources may be supported by servers 110, 115, 120 and by desktop processing
capacity such as personal computers 100, 105. Although the system is
distributed, and
processing capacity may therefore be sited anywhere accessible, it will
usually be the
case that a software agent assembling, issuing and receiving bids on behalf of
a resource
will be sited near that resource, for instance on a personal computer or local
processing
capacity, while a software agent which receives and brokers bids, in the
nature of an
auctioneer, is more likely to be sited on a server where it will be accessible
to a large
number of bidding agents.
Referring to Figure 7, software agents managing transfer of goods between
resources may be of different types. For instance, they may comprise
trading agents 200 which assemble and issue bids on behalf of resources
supplying goods or services
trading agents 705, 710, 715, which receive and issue bids on behalf of
resources which convert incoming goods or services of one type to outgoing
goods or services of another type;
trading agents 720 which assemble and issue bids on behalf of resources
consuming received goods or services;
auction agents 220 for resolving buy and sell bids.
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
9
It can be seen in Figure 7 that auction functionality can be provided
separately
from the resource management agent functionality, ie as separate auction and
trading
agents, but it is also possible for trading agents to carry out an auction
directly,
incorporating auctioneering functions within, or closely associated with, a
trading agent
200, 705, 720.
Referring also to Figure 2, a trading system to be managed by an embodiment of
the present invention can be modelled as a collection of repositories of
goods, flows of
goods and task engines. Each trading agent 200, 750, 720 may be associated
with a
controlled mechanism 205 which has at least one repository 210 and,
optionally, at least
one task engine 230 for driving a process in respect of goods from the
repository 210.
The repositories hold commodity goods, all items of a different commodity
being regarded
as identical, and one repository 210 only holds one type of commodity. The
flows 235
between repositories 210 transfer commodities without changing their type or
commodity
number. Task engines 230 are pieces of technology which can perform a task,
effectively
taking an input commodity and either consuming it or converting it into an
output
commodity of a different type, effectively utilising resources and consuming
"money" 240.
In practice, it may be that goods or commodities themselves are not actually
transferred but agreement to transfer is recorded in a contract. The actual
transfer may
then take place later or become the subject of a further contract.
Systems which lend themselves to modelling in this way include workflow
applications and packet switching networks. In a workflow case, tasks involve
processing
of work items associated with orders. A task may involve taking paperwork, a
work item,
from an in-tray associated with the task, performing work to progress the
order, updating
the work item and putting it in an out tray. Processing the work item
generally requires
use of resources, both consumables and assets, and can incur a cost.
The basic building block of the electronic trading system is a unit comprising
a
software agent and the local region of the managed system for which it is
responsible, that
is, a collection of linked task engines 230 and repositories 210. All the
agents are
essentially similar and connected via an interaction mechanism. The
interaction
mechanism is intended, in conjunction with the behaviour rules of the agents,
to cause the
system to evolve to a state in which it is operating efficiently. Should
circumstances
change, the system should evolve to a state appropriate to the new conditions.
Referring to Figure 2, a simple trading agent 200 is shown, which is
responsible
for a controlled mechanism 205. The controlled mechanism 205 comprises at
least one
repository 210 and a task engine 230. The simple trading agent 200 puts
together and
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
issues bids to an auction agent 220 and the result of a deal achieved at the
auction agent
220 will be fed back to the controlled mechanism 205 which then implements the
result of
the deal directly with another mechanism 225 affected by the deal.
An important aspect of embodiments of the present invention is the nature of
the
5 bids issued by the trading agents 200, 705, 715, 720, 730 and matched by the
auction
agents 220. The form of bid concerns transactions in which an amount of some
commodity item or service is sold, and in which both the amount and unit price
are subject
to negotiation. Referring to Figure 8, each bid, whether a sell bid or a buy
bid, comprises
a pair of curves 800, 805 (or in higher dimensional deal spaces, surfaces).
10 In negotiation, an auction agent 220 will accept sell bids from supplying
trading
agents 200 and buy bids from buying trading agents 705. It is necessary for
the auction
agent 220 to resolve these bids to the benefit of the system as a whole and
the bid
structure is an important factor in this. The following is a discussion of the
bid structure.
Bid Structure
Referring to Figures 3, 8 and 9, the bids (to sell or buy goods or services)
specify
directed surfaces in a multi-dimensional deal space that are interpreted as
the boundaries
of the acceptable region 810 of deal space under the terms of the bid. When
matching
one or more sell bids with one or more buy bids, the auction mechanism 300
within an
auction agent 220 intersects the surfaces to find the boundaries of the
mutually
acceptable regions, then applies an algorithm to determine a specific point in
this region
as the basis of a potential deal. This algorithm is intended to produce the
same deal that a
fair negotiation between the two parties would reach. A related algorithm can
be applied to
produce a measure by vrhich the 'goodness' of possible bid pairings can be
ranked. This
can be used to select a set of bid pairings, then the first algorithm
determines a
corresponding set of potential deals. Alternatively, sets of sell bids or buy
bids may be
combined to form virtual or composite bids. Composite buy and sell bids may
then, for
example, be intersected in the same way as the original bids and an algorithm
applied to
obtain a local or global measure of current market price for the type of good.
In the case of
a 2 dimensional (price vs. amount) bid space, this price is then used in
combination with
individual bids to determine the amount bought or sold by the corresponding
agent.
Referring to Figure 9, one can consider a 2-dimensional bid space, with the
dimensions being unit price and amount of a given good. The buy and sell bids
each
include a pair of curves 900,905,800,805 representing the upper and lower
bounds on the
amount offered versus price. Intersecting the curves of a pair of bids (one
buy, one sell)
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
11
for a given good results in a finite region of deal space 810 that is
acceptable to both
parties (or else an empty region indicating that there is no mutually
acceptable deal). In
principle, a variety of algorithms could be used to select a point within the
mutually-
acceptable region 810. One way to do it is to select the point on the boundary
of the
region corresponding to greatest amount of goods sold 910. By putting
restrictions on the
allowed properties of the curves, this point can be made unique and will be
one of the
intersection points. The amount element of the selected point is then used as
the ranking
measure for candidate bid pairs.
Concerning the restrictions, the curves should be continuous and have exactly
one finite price value for every possible amount value and vice versa. This
implies
monotonicity, but goes a bit further. A rising and a falling curve will then
intersect at
exactly one point. Two falling or two rising curves can still intersect
multiple times (or not
at all), but the intersection points will have different amount values. The
upper sell and
lower buy curves should increase with price, and the upper buy and lower sell
curves
should decrease with price. There may be several allowed regions (or none),
but all will be
bounded, and the highest amount in each will be at an intersection point. The
highest
point in any allowed region will then be the highest intersection point that
is also an
allowed point. It is possible that restrictions on some (but not all) of the
curves could be
relaxed.
Various architectures for electronic trading systems are possible. One
distinction is
whether bids are posted to independent auction agents 220 or are sent directly
to trading
agents 200,705,710,715. In the latter case, instances of the auction mechanism
are
incorporated into the trading agents' software. Incoming bids can be compared
against
internally-generated 'bids' (single auction) or transactions can take place at
a price or
amount to suit the agent owning the auction mechanism (double auction). In the
interests
of fairness, the bidders should know in advance which of these alternatives is
used. The
single auction case compares a single sell (or buy) bid to multiple buy (or
sell) bids. The
double auction case treats arbitrary numbers of buy and sell bids.
Note that there may be more than one auction agent 220 for a given good.
Auction
agents may each operate in a single or double auction fashion, continuously,
periodically,
or in some other way.
In some variants, the auction mechanism can set a price at which all deals in
a
particular round take place. The amounts at this price are then simply read
off the bids. In
this mode the auction mechanism is effectively acting as a middleman, buying
from one
group of agents and selling to another. When the total amounts bought and sold
in a given
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
12
round are not equal, the surplus or deficit in goods and money must be carried
by the
auction agent which may in a subsequent round itself submit bids to buy or
sell to redress
the balance. To avoid this mismatch, the auction agent can aim to set the
price to be that
at which there is an exact match between the amounts bought and sold.
Note that in a particular application, bids will typically be instances of a
small
number of families of surface (i.e. in the case of a two dimensional space,
families of
curve). The surface relevant to a specific bid is distinguished by a small
number of
parameter values, and it is only these that need to be generated when making a
bid. This
is particularly important in facilitating bid decisions by human users. One
alternative then
is to transmit only the parameter values as part of the bid, and have the
auction
mechanism interpret these as denoting surfaces. This would require specialised
versions
of the arbitration mechanism for each family of functions, and matching
versions of the
trading agent software. The auction mechanism can be kept generic, however, by
including the surface generation function as well as the parameter values as
part of the
bid. Note that this does not mean the function is physically transmitted with
each bid. The
solution adopted in the embodiment described below is to implement a bid as an
instance
of an object-oriented software class defining suitable methods for
interrogating and
operating on bids of this class. The class definition can be known a priori to
the auction
mechanism, or else transmitted once, eg, the first time an instance of the
class is
encountered.
Advantages
Compared to mechanisms employing 'point bids', embodiments of the present
invention require fewer bid messages to be exchanged
~ The bid representation allows trading agents to express the important
factors in the bid
in a way that is semantically clear and largely independent of context.
In cases where human users control bid preparation directly, the bids can be
displayed
as curves on a graph, offering an intuitive interface. Direct manipulation
(i.e. click and
drag) of the graphs can be used to prepare and update bids.
~ The clear semantics mean that it is possible to derive the bid curves from
more
application domain oriented paremeters (such as stock levels, rates of sale,
production, purchase, etc.). This makes it easier to program software agents
to
prepare the bids, or to provide a more domain-oriented command interface to
assist
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
13
users in preparing bids. The semantics are consistent with economic theory and
lead
to characteristics in tune with intuitive expectations based on supply and
demand.
The bid representation and associated mechanisms for manipulating and
reasoning
about bids can be employed in a variety of trading system architectures. They
can
thus form part of a flexible toolkit from which custom trading systems may be
built.
The bid representation is compact. The bid surfaces can be generated using
parameterised functions, so that only the parameter values characterising the
specific
surfaces need to be altered or transmitted with each instance of bid.
The bids can be manipulated, combined and otherwise reasoned about in a
computationally efficient way.
The form of bids and the mechanisms for combining them are particularly suited
to
decentralised management using market-based multiagent systems.
Agents get feedback in a natural way on their own pro-active behaviour, and
also
information enabling them to react to other agents' behaviour. To appreciate
these
desirable properties a little, consider first an agent trading in an otherwise
static
environment, ie other agents keep their bids constant. The agent is able to
derive
information from the way the environment responds when it changes its bids in
order to
optimise its own internal parameters. The feedback from the environment is in
terms of
changes in quantities sold/bought and cashflow, etc. In the embodiment
described below,
increasing the amount offered for sale will result in more goods being sold
but at a lower
unit price. This could result in either an increase or a decrease in cash
flow. Observing
the change in cash flow yields information that helps the agent optimise its
parameters so
as eg to maximise profit.
Now consider a dynamic environment in which other agents also change their
bids.
The other agents can sense changes (in the same terms) caused by the first
agent
changing its bids and can respond. The system as a whole becomes highly
adaptive by
virtue of its constituent agents co-adapting in this way. The form of bids and
the
associated processing mechanisms proposed here are particularly suited to
promoting
this co-adaptive behaviour, and also facilitate its mathematical analysis.
Description of embodiment
The embodiment described here is an arbitration mechanism (or family of
mechanisms) able to support a variety of auction / negotiation styles in a 2-
dimensional
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
14
deal space (price vs. amount for a given commodity). It was originally devised
for use
within a market-based multi-agent system in which each agent manages a
controlled
mechanism 205. The agent is responsible for buying the resources consumed
during
production, selling the results of production, and controlling the level of
production. The
level of production affects the unit costs in a (non-linear) way that is not
known to the
agent, which only knows current costs. Trading, bidding and production proceed
concurrently. The bid format and arbitration mechanism are applicable to a
variety of
market schemes and applications, however.
A bid consists of two continuous price-versus-amount curves 800,805,900,905 as
shown in Figures 8 and 9, an identifier denoting the bidding agent, a flag
indicating
whether this is a bid to buy or to sell, plus other parameters such as a
validity time
interval. One of the curves 805,905 denotes an upper amount level for an
acceptable bid,
the other 800,900 denotes a lower amount level. These curves denote the
maximum and
minimum amounts that an agent is willing to buy or sell as a function of
price. The upper
amount curve 805 for a sell bid increases monotonically with price, as does
the lower limit
curve 900 for a buy bid. Conversely, the lower amount curve 800 for a sell bid
decreases
monotonically with price, as does the upper limit curve 905 for a buy bid. A
point on the
upper amount curve signifies that (subject to constraints imposed by the lower
amount
curve) the bidding agent is willing to agree a deal at this price for this
amount or less. A
point on the lower amount curve signifies that (subject to constraints imposed
by the
upper amount curve) the bidding agent is willing to agree a deal at this price
for this
amount or more. A pair of points (one from each curve) at the same price, with
the upper
amount greater than or equal to the lower amount signifies the acceptable
range of
amounts at this price. A similar pair in which the lower amount is the greater
signifies that
there is no acceptable amount at this price. A pair of curves signifies a set
of amount
ranges at various prices indicating that the bidder is willing to commit to a
trade at a point
in the region 810 of the deal plane above the lower amount curve and below the
upper
limit curve. Comparing a buy and sell bid yields a region of price-amount
space within
which a deal would be agreeable to both parties.
Effectively, this two curve structure allows a vendor to say: 'I will sell
this amount of
goods if I am paid at least this price' across the full spectrum of amounts.
The amount
corresponding to minimum sale price is the 'ideal' amount the vendor wants to
sell,
perhaps corresponding to the excess over some target stock level. It is
willing to sell more
or less than this, but requires monetary compensation for doing so. Similarly,
it allows a
purchaser to say: 'I will buy this amount of goods if I have to pay no more
than this price'.
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
The amount corresponding to maximum sale price is the 'ideal' amount the
vendor wants
to buy, perhaps corresponding to the deficit below some target stock level. It
is willing to
buy more or less than this, but requires monetary compensation for doing so.
It would, of course, be possible to amalgamate the upper and lower limit
curves to
5 form a single curve describing the boundary of the acceptable region. In the
case of a sell
(buy) bid this would describe the lowest (highest) acceptable amount, and
would have a
minumum (maximum) rather than being monotonic. However, the two curves tend to
reflect different concerns so it is useful to be able to manipulate them
separately.
In some cases, the minimum amount is not a significant consideration. One can
then
10 make do with bids containing only maximum amount curves, the minimum amount
curves
then being implicitly straight lines along the price axis (ie. the minimum is
0 amount at any
price). In essence there are still two curves, however. Depending on the
algorithm for
choosing the 'best' point, the approach may also work with the bid being
unbounded in
some directions, eg with no minimum curves at all, but then the system would
have to
15 deal with sale of negative amounts of goods.
In the example shown in Figures 8 and 9, the curves making up each bid cross
one
another, and the corresponding curves in different bids also cross, and this
is how a
bounded space is produced. Forming a fully bounded region is not essential as
long as it
is still possible to use to an algorithm for choosing the 'best' point in an
acceptable region,
for instance to provide the specific case of maximising the amount of goods.
In this case,
it is not necessary for the upper and lower curves within a given bid to cross
as long as
the upper buy and sell curves cross in such a way that a definite 'greatest
amount' point is
easily found.
Another variation on the pairs of bid curves format shown in Figure 9 would be
at
least one pair of curves wherein either both curves of one bid are rising or
both curves are
falling. Such curves would still be guaranteed to cross (exactly once) as long
as they rose
or fell consistently at different rates (i.e one always rises or falls more
rapidly than the
other). However, if we want a mutually acceptable region (if one exists) to be
bounded,
then we must impose similar constraints on pairs of curves from different bids
(e,g, the
upper curves from the sell bid and from the buy bid). This is much more
complex than
constraining the properties of individual curves, such as monotonicity of a
particular
sense.
Furthermore, having sell bids with rising upper curves and falling lower
curves, and
vice versa for buy bids makes intuitive sense from basic economic theory.
Consider the
(decreasing) lower curve of a sell bid. This is saying: 'the minimum
acceptable price for
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
16
small orders is greater than the minimum acceptable price for large orders',
which is
intuitively what one would expect. The (increasing) upper curve is saying: if
demand is
high, I will charge more than if demand is low', which is again in tune with
intuitive
expectations.
Assume the curves are continuous and have exactly one finite price value for
every
possible amount value and vice versa. This necessarily implies monotonicity,
but goes a
bit further. Then the directions of slope of the curves given in the last
paragraph almost
guarantee that a buy and a sell bid will define a single bounded acceptable
region, or no
acceptable region at all. To be absolutely certain one would have to impose
further
conditions on the relative properties of upper buy curve and lower sell curve
(which are
both falling) and upper sell curve and lower buy curve (which are both
rising). Without
these extra restrictions, we can still say that there may be several allowed
regions (or
none), but all will be bounded, and the highest amount in each will be at an
intersection
point. The highest point in any allowed region will then be the highest
intersection point
that is also an allowed point. This makes the algorithm to find the mutually
acceptable
point with highest amount relatively easy.
Referring to Figure 9, when considering a pair of bids, the arbitration
mechanism is
entitled to set up a deal at any point on the deal plane 810 compliant with
both bids.
However, the mechanism will usually employ some function to rank the points in
order of
desirability. One can envisage many such functions. One will now be described
by way of
an example.
Note that, under the reasonable assumption that each is attempting to maximise
profit, a buyer will always prefer a low price and a seller a high price.
These preferences
are clearly conflicting. However, if buy and sell bids are made such that all
items are
offered for sale / purchase at profitable prices, then the more items sold (at
a given price),
the better for both buyer and seller. The mechanism therefore maximises the
number of
items sold. If the auctioneer 220 too is considered an autonomous, profit
seeking agent,
then we can consider it as being motivated by a commission on each item sold.
The following is some clarification of what is meant by each item being
offered at a
profitable price, which also yields insight into a rationale for choice of bid
curves by a
trading agent 200,705,710,715. Referring to Figure 10, a trading agent
monitors its
stockpile 1000 of goods in its repository 210. It can generate a pair of bid
curves by
putting the monitored values into a predetermined equation. Alternatively, it
can adjust
the curve parameters dynamically to attain some target condition, e.g.
maintaining the
stockpile 1000 at some target level. To illustrate the second point, if its
stockpile level is
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
17
too high and increasing, then a selling agent lowers its selling prices in the
next auction
round to increase sales. In both cases the most significant parameters are
stock
levels/amounts sold and received, money levels/prices/costs and the rates of
change of
these parameters.
Referring to Figure 10, suppose the value of owning a stack 1000 of n items is
a
continuous differentiable function v(n). The value assigned to the n'th item
(from the
bottom) is then the derivative, v'(n). A deal is profitable if the unit price,
p, multiplied by the
(signed) amount acquired, a, is greater than the change in value, v(n+a) -
v(n). However,
it is not necessarily the case that all items in a deal that yields a net
profit are sold/bought
at a profit. Typically, for large n, v'(n) decreases with increasing n. This
is because once
the agent has enough stock for short-term needs, each increment of surplus has
decreasing value, for example as a contingency reserve. At small n, v'(n) may
be low if
there is some minimum useful amount of stock, or may be at its highest here.
Thus typical
simple v'(n) curves will decrease monotonically or will have a single maximum.
When
considering a potential deal at a given price, the profitability of selling or
buying the m'th
item depends on whether v'(m) is above or below this price. However, one can
clearly
only add items to or remove them from the top of the stack, so if n is the
current stack
height, one can only buy or sell item m if one also buys or sells items in the
interval n to
m.
Suppose the price in question, p, is less than v'(n). The agent can profitably
buy (or
sell) up to a items if v'(n+a) = p (a is negative for a sale). Thus the upper
amount curve of
the bid is the curve on the (p, a) plane such that v'(n+a) = p and
d/da(v'(n+a)) is negative.
Above this amount the deal may result in net profit, but each additional item
will be sold at
an increasing loss. However, if p > v'(n), depending on whether n is higher or
lower than
its maximal value and whether the agent is buying or selling, it is either not
possible to
deal at a profit, or else there is a threshold amount above which a profit is
made on
complete deals and incremental items. Thus the lower bid curve is defined by
v(n+a) -
v(n) = ap and d/da(v'(n+a))positive.
Here is an example derivation of an upper bid curve. Again, consider a vendor
selling
items from stock. Clearly, the vendor is willing to sell the items if the
price is greater than
the value of owning the item. How does the vendor determine the value? One
relevant
factor is the cost of obtaining/replacing the items. Suppose that in the last
time period, the
vendor has bought Bo items at average unit price Po, and that the stock level
the vendor
likes to maintain is No. PD can be taken as an estimate of the average value
of if the pile of
stock is at the desired level. If the number of items currently in stock, N,
is greater than No,
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
18
then the excess items can be considered less valuable. One way to deal with
this is to
discount the value of the excess items by a factor d, such that
value(n.No) = 6," (1/d)"-' value(No) = value(No).d/(d - 1) (1 - d~")
( 0-1 )
Although the argument was made with n being a positive integer, the formula
can be
continued to non-integer n values, so that the value of a stack of N items is
value(N) = value(No).d/(d - 1 ) (1 - d-N~NO)
(0-2)
and the value of the Nth item is
unit value(N) = d/dN value(N) = value(No)/No d In(d)/(d - 1 ) d~N~NO
( 0-3 )
Thus, even though the items are identical, if considered as a stack, with
items being sold
from the top of the stack, each item has a different value to the vendor.
Items at the top of
the stack will normally have a lower value than those lower down. The items
that can be
sold at a profit are the ones whose unit value is less than the price under
consideration.
Thus the maximum number that can be sold such that each is sold at a profit is
the height
of the stack minus the position of the item whose value equals the sale price.
Using the
same discounting policy as before yields a max curve that is a logarithmically
increasing
function of p.
max amount(N, p) = N + Noln(p/Po) - No In[d(Ind)2 /(d - 1 )]
(0-4)
Although the shape of this function depends on the discounting policy of the
vendor, the
argument shows more generally that:
it is possible to view the value of a item in a stack of identical items as a
function of its
position in the stack, and this gives a natural semantics for the maximum buy
and sell
amount curves.
a discounting policy (such that an item to be used in the future is worth less
than one to be
used now as is standard accounting practice) results in the max sell (buy)
curve being a
monotonically increasing (decreasing) function of price.
Similar arguments can be made for the minimum amount curves. These apply when
there
is some threshold amount below which a deal at a given price is uneconomical.
The most
obvious circumstance to which this applies is when there is some cost
associated with the
transaction itself. The deal is only profitable from the point of view of the
seller if these
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
19
costs are less than the payment received minus the value of owning the items.
The
minimum sell amount curve is then the function Sm~~(N, p) such that
transaction cost = S,~,~~p - value(N) - value(N - Smin)
( 0-5 )
Using this becomes
transaction cost = Sm~~p - value(No)d/(d-1 ) d-N~NO(d-Smin/NO - 1 )
( 0-6 )
which unfortunately is not easy to solve exactly for Smin. However, the
purpose here is only
to explain the semantics of the minimum curves and give an idea of how they
might be
determined in a particular application.
So, given a buy and a sell bid for the same good, we have a means of
determining the amount and price of the deal (choosing the point that
maximises amount
sold in the region of deal space acceptable according to both bids). This
forms the basis
upon which a variety of auction and negotiation models may be built. The model
used
here is one of mediated negotiation between 1 or more buyers and 1 or more
sellers.
These submit bids that are processed by a neutral mechanism (i.e. a mechanism
that
favours neither buyer nor seller, and is accepted by both). While the
mechanism is
neutral, it is not necessarily the case that a separate auction or mediation
agent is
required. For example in a contract-net-like system, each agent could
incorporate an
auction engine (an instance of an auction mechanism) for each type of
item/senrice it can
require. The agent enters its requirement for the service as the only buy bid;
multiple other
agents can submit sell bids. An analogous situation can be envisaged in which
the seller
incorporates the engine and there are multiple buyers. When there are multiple
buyers
and sellers involved, it is most natural to introduce a separate auctioneer or
negotiation
mediator in which the engine is incorporated.
An auction engine is basically a collection of bids plus a set of operations
that can be
performed on that collection. Associated with each bid is the definition of
the time interval
during which the bid is valid (i.e. during which it is a binding commitment on
the part of the
agent submitting it). Note that for simplicity, there is no provision for an
agent to retract a
bid once it has been made. The main operation takes the currently valid bids,
and
generates a set of deals. As a result, the set of bids is reduced by removing
those that
have been used up, and modifying any that have been partly used. Note that an
agent
may have more than one active bid in the collection.
A round of a single auction (one buyer and multiple sellers or vice versa) can
be
conducted by matching the single sell (or buy) bid against all the current buy
(or sell) bids,
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
with the deal (or leading candidate) being determined on the basis of greatest
amount. A
round of a double auction (multiple buyers and sellers) can be conducted by
matching all
combinations of current sell and buy bids, with the deal (or leading
candidate) again being
determined on the basis of greatest amount. Multiple deals can be determined
in a single
5 round by choosing the best n bid pairs. Multi-round auctions can be
conducted by
informing bidders of the current best bid pair, cancelling all other bids, and
inviting repeat
bids.
In this bid-pairing style of mechanism, deals are transacted between vendor
and
purchaser (though they may be selected / decided using an intermediary), and
in general
10 take place at different prices. As an alternative, the (agent acting as)
auctioneer 220 can
set a price at which transactions in a given round will take place. For a
given bid, the
amount bought or sold at a set 'market' price is simply the value of the upper
limit curve at
this price, provided it is greater than the lower amount at this price
(otherwise it is zero).
The (agent acting as) auctioneer now has to act as clearing house. In essence,
the deals
15 are between bidder and the auctioneer. Any surplus or deficit in goods or
money is carried
by the auctioneer. The auctioneer may itself bid in the attempt to rid itself
of said surplus
or deficit. To minimise such surpluses or deficits, the auctioneer may
calculate the market
price as being the 'clearing' price at which the total bought and sold are
equal. This may
be done quite simply.
20 First we define rules for adding buy or sell bids. The sum of two bids is a
bid whose
upper curve is obtained by summing the upper curves of the original bids at
corresponding
prices, and taking the lesser of the two lower curves at corresponding prices.
Referring to
Figure 11, the clearing price 1100 is obtained by summing all current sell
bids and all
current buy bids then matching the two resulting bids to obtain a price/amount
point. The
price component is then the clearing price, which is used in combination with
the
individual bids to determine the amounts bought and sold by each bidder. Note
that the
effect of the lower bid curves may mean that the market is not completely
cleared.
If a deal is agreed at a given price-amount point based on a given bid pair,
then the
bids must be reduced or deleted correspondingly. If the price-amount point
lies on the
upper curve, then the bid is completely used up and may be deleted. Otherwise
the upper
curve is scaled by multiplying all points by a factor obtained by dividing the
deal amount
by the upper curve value corresponding to the deal price. The lower curve is
set to zero at
all prices.
Bidders are informed of the results of their bids.
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
21
Note that nothing has been specified about how often the auctioneer executes
this
operation, whether it is on a regular schedule (and if so whether the bid
validity intervals
are aligned with the execution period), whenever a new bid is received, etc.
Similarly, it
does not say whether the owner of the auction mechanism solicits bids
actively, or just
waits for them to arrive. All these factors can be specified at a higher level
to create a
variety of auctions (single, double, periodic, continuous, etc.)
In the example embodiment bids are represented by Java objects. The class of
the
object implies a particular curve parameterisation and defines appropriate
operators for
combining (e.g. adding), manipulating and querying bids of this type. In this
case the bid
curves are characterised by ordered sets of points. The implied curves are
obtained by
linear interpolation between adjacent pairs of points and extrapolation to
infinity beyond
the pairs at each end.
Detailed description
The following describes an implementation in Java of the ideas described
above. The
main building blocks in this implementation are the following classes:
PolyLine: an PolyLine is an infinite piece-wise linear curve defined by a
sequence of
points
LinearBid: a LinearBid is a bid whose min and max curves are specified as
PolyLines
LinearBidPair: a LinearBidPair encapsulates a buy and a sell bid for the same
type of
item, and provides methods, for example, to obtain the max amount point.
CollectionOfLinearBids: this is the base class for implementing auction
engines.
1. Messages and related classes
The content of the messages in each case originates in the sender as a Java
software object, and similarly is used in the receiver as a Java software
object. Depending
on implementation, the content may remain in this form during transmission, or
else be
converted to, e.g. a textual form prior to transmission. On reception, the
receiver can then
instantiate an object based on this description and its own (or shared) class
libraries. The
descriptions given here assume that the content remains an object throughout,
though
some of the fields and/or procedures are only relevant to processing within
the auction
engine.
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
22
2. Auction messages
All messages are instances sub-classes of the AuctionMessage, possessing the
following data fields:
auctioneer: an identifier for the (agent embodying the) auction engine to
which the bid is
submitted;
bidder: an identifier for the trading agent submitting the bid;
commodity: an identifier for the type of goods or service involved;
serial: a serial number, that when combined with the bidder identifier,
uniquely identifies
the message instance
validity: a time interval defining the period over which the bid is valid.
Note that this also
identifies the clock with reference to which the interval is defined.
3. Sale notification
Objects of this class are used to notify bidders of sales resulting from their
bids.
They have the additional properties:
amount: giving the amount of commodity sold;
price: giving the unit price at which the sale takes place;
tradingPartner: an identifier for the trading agent to/from whom the items are
sold;
The auctioneer and tradingPartner fields will often refer to the same agent,
with the
agent embodying the auction engine either acting as intermediary or as the end
customer
/ vendor, but this need not necessarily be so. Both amount and price are
signed, with a
positive sign indicating flow of goods or money to the bidder.
4. Bid messages
These declare what a trading agent wants to buy or sell and on what terms. In
addition to those defined on AuctionMessage, the class Bid defines the
following data
fields:
buying: a binary flag indicating whether this is a buy or a sell bid;
aIIGone: a binary flag used by the auction engine. It indicates whether the
bid amount has
been used up.
The following functions by means of which the curves defining the bid may be
interrogated:
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
23
amount(price): this function returns a pair of numbers representing the upper
and lower
acceptable amounts at a stated price, or else an indication that there is no
acceptable amount at this price;
price(amount): this function returns a number representing the minimum
acceptable price
at which the stated amount will be sold;
acceptable(point): this function indicates whether the given price/amount
point lies within
the acceptable region;
crossOverPointQ: this function returns the price/amount point at which the two
bid curves
cross;
and the operator:
transact(point, timelnterval, otherParty): this generates and returns a
SaleNotification
for a transaction at the given price/amount point to/from the otherParty,
valid for the
given interval. It also reduces the bid to compensate for the proportion of
the bid
'consumed' by this transaction. The point must lie in the acceptable region of
the
bid. If the point lies on the maximum amount curve (as is usually the case),
the bid is
marked as used up. Otherwise, the residual amount is calculated as follows.
The
acceptable amount function is used to calculate the acceptable range at the
given
price. The maximum amount curve of the bid is scaled by the ratio of the
amount
sold to the upper amount of this range. The minimum mount curve is left
unchanged
as it is interpreted as the minimum amount for a single transaction.
The above fields and functions provide an interface that is independent of how
the
bid curves are represented. Clearly, a given implementation must choose one or
more
concrete representations defined by sub-classes of Bid. These all have the
additional data
fields: maxLine and minLine, containing the bid curves represented in
different ways (i.e
they are implemented as objects belonging to different classes). The
implementation of
the above-mentioned functions also varies depending on the class of the curve.
The
reference implementation uses a sub-class called LinearBid that represents the
curves as
instances of the class PolyLine. Whenever a class name includes the word
'linear', by
convention this means that it is specific to bid-curves represented as
PolyLines.
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
24
5. The PolyLine class
A PolyLine is piece-wise linear, that is the curves are continuous sequences
of
linear segments. The end segments are semi-infinite, i.e they extend to
positive or
negative infinity (remember the curves are monotonically increasing or
decreasing). A
PolyLine is defined by a sequence of price/amount points (held in data filed:
points in
ascending or descending order of x, i.e price) representing the vertices
between the
segments. The semi-infinite end segments are obtained by extrapolating the
segment
defined by the first/last pair of points. The PolyLine class defines a number
of operations
that are useful in processing bids, including:
y(x): returns the y (amount) value - obtained by interpolation/extrapolation -
corresponding to the given x (price);
x(y): returns the x (price)value corresponding to the given y (amount);
scaleBy(factor): this multiplies they (amount) coordinates of all vertex
points (an hence of
all points) on the PolyLine by the factor.
Intersections(another PolyLine): This returns a set of intersection points
with the given
PolyLine;
add(another PolyLine): This returns a new PolyLine obtained by adding the
original
PolyLine to the one supplied in the argument. Addition involves adding the y
(amount) coordinates at corresponding points on the two PolyLines. The
vertices of
the new PolyLine are obtained from the two original sets of vertices as
follows. The
vertices of each original line are added to the corresponding points on the
other line
(obtained by interpolation). The two new sets of points are combined,
duplicate
points removed, and reordered in ascending / descending sequence of x (price)
value.
Subtract(another PolyLine): As for add, but the argument PolyLine is scaled by
minus
one first.
Minumum(another PolyLine): Returns a new PolyLine which at all values of x
(price) is
the same as the input PolyLine with the lower y (amount) value).
6. Auction engine kernel
The base class for auction engines is CollectionOfBids. In the case of bids
based
on PolyLines this is specialised to CollectionOfLinearBids. As the name
suggests,
instances of this class encapsulate some form of database of bids. In the case
of the
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
reference implementation, this simply takes the form of a Java Vector each for
buy and
sell bids: buyBids and seIIBids. The other main data item is commodity, which
identifies
the type of item that this engine handles. Note that a give auction engine
instance handles
only one type of commodity, though it is possible for several auction engines
to be
5 grouped within one agent.
A CollectionOfLinear bids also has the following means of interrogating or
manipulating the bid collection and its contents:
addBidToCollection(Bid): adds the bid (which must refer to the correct
commodity) to
the collection;
10 purgeBids(time): This removes expired bids, i.e. ones that have been used
up or whose
validity interval ends prior to the given time, from the collection.
SumBuyBidsAt(price, time): This returns the amount range obtained by taking
the union
of acceptable amount ranges of buy bids valid at the stated time, at the
stated price.
This range represents the upper and lower bounds of the total amount available
for
15 sale at the current time;
sumSeIIBidsAt(price, time): As above, but for sell bids.
NetBidsAt(price, time): This returns the amount range obtained by taking the
intersection
of the summed buy and sell bids. It represents the upper and lower bounds on
the
amount that can actually be sold at the current time at the given price.
20 BestMatch(bid, time): returns (a reference to) the pair of bids (one buy
and one sell bid,
as an instance of LinearBidPair - see below) made up of the bid and the one
that
matches it best at the current time. The criterion for best match is defined
as part of
LinearBidPair. In the reference implementation, it is the maximum sale amount;
bestPair(time): returns (a reference to) the pair of bids (valid at the stated
time) ranked
25 best over all.
CrossOver(time): returns the price/amount point at which the sum of the buy
bid max
lines and the sell bid lines intersect. Only those bids valid at the stated
time are
used.
The following provide the implementation of the two alternative basic
mechanisms: 'market price' and 'pair-wise':
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
26
transactAIlAt(price, intermediary, time): This generates transactions (here,
generating
a transaction means creating sale notifications and reducing the bids
accordingly)
between bidders and the specified intermediary agent at the specified price,
using
the bids' transact functions, returning the corresponding SaleNotification
objects.
The intermediary will normally be the agent containing the auction engine, but
need
not be so. The amounts for the transactions are from the valid bids by taking
the
upper figure of the amount range returned by the bid's amount function. There
is no
transaction if the bid has no acceptable amount at this price.
CIearMarket(intermediary, time): This uses price coordinate of the point
returned by
crossover as the market price, i.e. the price at which all transactions take
place. If
only the maximum amount curves are considered then this is the price at which
the
total amount offered for sale equals the total demand. In this case, the
intermediary
will have no net change in its stock levels after implementing the sales. The
minimum amount curves may result is some net increase or decrease in the
intermediary's stock.
TransactPairWise(time): This implements transactions between pairs of bidders.
First
the best pair is selected, and the corresponding transaction is enacted.
Transactions
take place at the price/amount point determined by the bid pair object. This
is
repeated until there are no more transactions are possible. The
SaleNotifications are
returned.
7. LinearBidPair class
This is an important auxiliary class used by CollectionOfLinearBids. The main
data fields are: buyBid and seIIBid, which hold the bids. The main operations
provided
are:
transactionPoint(time): Provided both bids are valid at the given time, this
returns the
'best' price-amount point within the acceptable region of both bids, or else
an
indication that no acceptable point exists. In the reference implementation,
this is the
point corresponding to the maximum acceptable amount. This can easily be found
by calculating the intersection points of the two buy bid curves with the two
sell bid
curves, rejecting any that lie outside the acceptable region, then selecting
the
highest remaining point. Often this will be the intersection of the two
maximum
amount curves.
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
27
Transact(point, timelnterval): This generates a transaction between the two
bidders at
the specified price-amount point using the bids' transact methods. It returns
the two
SaleNotifications
8. Engine for periodic double aucfion
The above classes can be used to implement a variety of auction styles.
Referring to Figure 3, by way of illustration, this section describes how an
additional layer
or wrapper can easily be added to a CollectionOfLinearBids to form an engine
305 for a
periodic double auction. A double auction is one in which (multiple) buyers
and sellers bid,
there being a symmetry between the roles of buyer and seller. A continuous
double
auction is one in which bidding and resolution of bids into transactions takes
place as a
continuous parallel or interleaved process. A periodic double auction is
similar to a
continuous one, except that the bidding and/or bid resolution is performed at
regular
intervals rather than continuously. In this example, the bidding takes place
continuously,
but the bid resolution takes place at regular intervals known to the bidders.
The bidders
can thus take into account the periodicity of the auction when setting the
validity intervals
of the bids, effectively specifying which auction round or rounds the bid will
be considered
in. A bidder can for example submit a series of bids with each subsequent one
becoming
valid the round after the previous one expires.
Figure 3 shows a simple periodic double auction engine formed by adding a
wrapper 310 to a CollectionOfLinearBids 315. The wrapper 310 is made up of:
a register 320: this holds information on trading agents currently using the
service. It
receives and acknowledges registration and deregistration messages from
agents.
When a registration message is received, a message is sent to the trading
agent
giving details of the periodicity of the auction rounds. Should this
periodicity change,
a message is sent out to all registered agents with the new information.
Depending
on the availability of directory services, and the nature of the inter-agent
transfer
mechanism, the registration information may be used to relate agent
names/references to addresses.
A timer 325: This holds the definition of the auction periodicity. It signals
the auction
supervisor when a new auction round is due. It notifies the register when of
new
periodicity should this change.
An auction supervisor 300: This passes new bids to the collection as they
arrive. On
receipt of a signal from the timer 325, it signals the bid collection 315 to
perform a
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
28
round of the relevant type of auction and then to perform a purge. It then
routes the
resulting sale notifications to the appropriate agents.
This is a very basic engine, and many refinements are possible.
9. Trading Agents
The previous section described a simple periodic double auction engine 305.
Referring to Figure 2, this section describes, by way of an example, a simple
trading agent
200 that might trade via such an engine. This agent 200 sells a single
commodity via a
single auction forum. A simple buying agent would be similar except,
obviously, it buys
rather than sells. In general, an agent may buy and/or sell many commodities
via many
auction fora. It may also control means of production, i.e. of converting
among types of
commodity. Such means of production are described as 'technologies' and are
characterised by production and cost functions. However, this simple selling
agent 200
merely has a means of acquiring a set amount of its commodity per unit time at
a fixed
cost.
(In Figure 2, a task engine 230 is shown. In the trading agent 200 as
described
below, the task engine is not required as the agent is not processing,
producing,
consuming or converting goods.)
The trading agent 200 registers with its chosen auction engine 305 and
receives the
periodicity information from the auction engine's timer 325 in return. It
decides its initial bid
and submits it with the validity interval set to include one or more of the
times at which an
auction round will take place, making allowances for the time it may take for
a message to
be delivered. Let us say that the trading agent 200 uses a fixed validity
interval length. It
also decides how frequently it is going to submit bids. Let us say that the
bid frequency is
chosen to be the same as the auction frequency. It submits further bids at
this frequency,
adjusting the bids according to any new information received since the last
bid.
The trading agent 200 controls a mechanism 205 for storing and transferring
commodity items and money to designated other agents. The commodity items 210
are
stored in a stockpile 1000. When it receives a sale notification from the
auction engine
305, it signals 'authorisation to sell' to a transfer controller 215 of this
mechanism 205.
The authorisation to sell includes the sale notification. The mechanism 205
signals to a
corresponding mechanism 225 in a designated 'other agent' that it is 'ready to
transact'
(again enclosing the sale notification). If the corresponding mechanism 225
has received
an authorisation to sell (from its own agent) and a matching 'ready to
transact' and the
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
29
time is within the validity interval, then the controlled mechanism 205 sends
the
commodity items and accepts receipt of the money. If no, or too little money
arrives, an
exception is flagged.
The other thing that happens when an agent 200 receives a sale notification is
that
the price and amount are used to update the information on which the bid
calculation is
based. Thus there is a feedback loop (shown in bold in Figure 2) to an
"AdjustBid"
mechanism 245 consisting of the bid calculation by the agent 200 and auction
mechanism
220. The agent 200 uses this feedback to optimise its bid so as to maximise
profit. The
notion of profit includes both value of owning commodity items 210 and money
240. Note
that choosing the function expressing the 'value of ownership' is a skilled
exercise and is
also application dependent. In general, it is a function of the number of
items 210 currently
owned and their rate of change. In 'multi-commodity' agents the value
commodities that
can be inter-converted are coupled via the production/cost functions.
The following section gives examples of bid calculation using feedback.
10. Agent bid calculation behaviours
Normally an agent will not calculate its bid curves from scratch, but will use
predetermined parameterised functions, and adjust the parameters. A
logarithmic max
curve function was derived above, for example. Here we assume that the shape
of the
max curve is fixed, but that it can be translated in price-amount space by
adjusting the
value of a datum point. The minimum curve is taken to be zero everywhere (no
transaction cost).
Referring to Figure 6, the agent's behaviour is based on the assumption that
its
trading environment can be treated as a collection of trading agents, one per
commodity/auction forum that the agent trades in, and that these agents alter
their bids
relatively slowly. So our simple selling agent 200 acts as though it is
selling to a single
buying agent 720 with a monotonic max bid curve of otherwise unknown shape.
Given the
monotonicity of the two bid curves and that the auction mechanism will yield a
sale at their
intersection point, we can see that shifting the sell curve upward (increasing
the amount
datum) results in selling more items at a lower unit price. Shifting the sell
curve to the right
(increasing price datum) results in less being sold but at a higher unit
price.
The simple selling agent 200 in this example acquires/creates the items 210 it
sells
at a constant rate and cost. Its optimum steady state is characterised by a
sale rate equal
to this acquisition rate, i.e with a stockpile 1000 at a constant level. There
is no value in
holding stock for its own sake. The most desirable stock level will depend on
anticipated
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
sale fluctuations, and here we will take it as a given fixed value. The
agent's utility thus
decreases as the stock level deviates from this value and also as its rate of
change
deviates from zero. It can easily be shown that if changing some control
parameter, p,
results in a proportionate change in the rate of change of the stock level
then a control law
5 of the form:
3 p = a1'3 t + b(1 - lo)
where I represents stock level and I' its rate of change with time, results
(for well-chosen
values of a and b) in stabilisation of the level at lo. At least for small
shifts of the bid curve
either the price or amount datum of the bid curve (with the other held
constant) can be
10 used in this way, with I representing the level of commodity items 210. The
values of I and
I' are both readily available to the agent 200 either from measurements by the
controlled
mechanism 205 or by summing the quantities in the sale notifications. Note
that the
control law is not dependent on the external supply/cost, so that if these do
change, the
agent will adapt.
15 In this simple case, there is no question, e.g. of adjusting margins on
items sold to
maximise profit, as the amount sold automatically determines the unit price,
and the
purchase price is determined externally. This changes, however, if the agent
issues both
buy and sell bids (in different auction foray. There is now a choice of steady
state solutions
(i.e. buy and sell bids resulting yielding equal amounts bought and sold) at
varying levels
20 of throughput, and there is one such level of throughput yielding maximum
profit. There
are now four control parameters available, the datum coordinates of the buy
and sell bids,
but only two independent degrees of freedom (corresponding to the position of
the
transaction points on the other agents' bid curves).
A possible control strategy is to use the sell bid datum amount to control the
stock
25 rate/level using the same control law as in the simple case above. The buy
bid datum
amount is used to achieve a given profit margin. A similar law is used, but
now using the
rate of change of money level rather than the item stock level as the
monitored parameter,
and with b=0 (there is no optimum level of money).
This is justified as follows. A control law of the form:
30 3 p = a am'/ap
where m' is the rate of increase of money, will find the local maximum in the
profit rate
curve. However, c~m'/ap is difficult to estimate from the measurable
quantities. In steady
state, m' equals throughput (T) times profit margin, (M) which are both in
general functions
of p. Thus:
3 p = a am'/ap = a(T cdVl/ap + M c~T/op)
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
31
Profit is maximal when T/M = - c~T/c~Vl. T as a function of M is determined
only by the bid
curves of the 'other agents'. This still does not help as we do not know
wT/~fVl. However if
we hypothesise that a particular profit margin is close to optimal it is
straightforward to
adjust p using a rule of the form:
3p=a(M-Mo)3t
or equivalently:
3 p = a (m' - TMo) 3 t
Note that this control strategy only maximises profit if the (fixed) profit
margin
happens to be the optimal one. It would be nice also to have another rule by
which the
target margin is adjusted to the optimal value, but it has not proved possible
to define
such a rule using the quantities available to the agent.
The price datums are set so that their average equals the average of the
actual
transaction prices and their difference is constant.
This same strategy can be generalised to the case where items bought and sold
are
not of the same type, with one being converted to the other according to some
cost and
production function. Similar strategies can be developed for more complex
cases.
The strategy presented here is an illustration of how agent bid behaviour
rules may
be developed, and how they work as part of a feed-back loop through the
agent's
environment. For further information, reference might be made to the paper
"Decentralised Management of Business Process Networks" by PJ Kearney and J
Stark,
published at a conference (ICCSCI) in September 2000.
11. Multi-agent systems
The double auction mechanism and trading agent described above can be
combined to form a wide variety of multi-agent trading systems. First note
that it is often
the case that an agent combines attributes of both trader 200 and auction
engine 305, that
is it is able both to:
generate bids, participate in trading deals on receipt of SaleNotifications,
etc., and
receive bids, use them to determine deals, and send out the SaleNotifications.
Referring to Figures 4,5 and 6, when an agent does combine both sets of
attributes, the two are kept distinct within the overall agent. The auction
mechanism 405
treats its trading agent persona 400 in exactly the same way it does other
agents. Thus
the auction mechanism 405 remains neutral. The only difference is that bids
and sale
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
32
notifications can be transferred by intra-agent means (for example by Java
method calls)
rather than using inter-agent messages.
It has been noted above that it is in fact necessary to associate a trading
capability
with an auctioneer using the 'clearMarket' mechanism. (It would in fact be
possible to
delegate the 'trading' role to another agent) . Here, the agent acts as a
trading
intermediary: items sold and the payment for them go first to the auctioneer;
they are then
redistributed to the purchasers. Clearly, then the auctioneer needs a trading
mechanism
400 like that controlled by a trading agent 200. It also needs a trading
agent's bidding
mechanism, however, to handle residual amounts of items and money when the
bids do
not exactly clear. It submits bids to subsequent rounds of its 'auctioneer
persona' 405 to
try to clear the (positive or negative) residual amounts. Figure 4 shows as an
example a
basic double auction (clearMarket variant) with the auctioneer 410 acting as a
trading
intermediary, showing the roles of the auction 405 and trading personae 400 of
the
auctioneer 410.
In contrast, Figure 5 shows direct pairwise trading 500. In this case the
transactPairWise mechanism is used, and there is no need for the auctioneer
410 to have
a trading persona.
The above illustrations considered auctioneer agents possessing a trading
persona
400. It is also possible to give trading agents 200 an auction persona 405 in
order to build
systems in which negotiation between agents is direct rather than via a
distinct auctioneer.
Figure 6 shows a case reminiscent of the familiar 'contract net' frequently
used in multi-
agent systems. Here, selling agents 200 submit bids to a single buying agent
720
(incorporating an auction engine 305 in an auction persona 405). The buying
agent's
trading persona 400 submits a buy bid, and the auction persona 405 can use its
auction
engine 305 to determine the resulting trading deals.
More complex scenarios can be built by chaining these basic elements together
in
different ways. Figure 7 gives an illustration. Possession of the trading and
auction
personae is implied by the arrows and labelling. Only bid arrows 725 are
shown. The
labelling indicates the types of item bought and sold, thus a label of 2-3
indicates that the
agent 715 buys items of type 2 and sells items of type 3 (with an implied
ability to
transform type 2 into type 3).
In these examples, agents with a maximum of one input and one output type are
shown, but arbitrary n-m agents are possible. It is also possible to couple
trading agents
via constraints on their production functions (due for example to competition
for a shared
resource), so they form what can be regarded as composite agents. It should
also be
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
33
noted that the individual markets in different types of item can be coupled,
so that the
example systems form multi-commodity economic systems.
Embodiments of the present invention are described above mainly in terms of
bidding as a function of amount and price. It would however be perfectly
reasonable to
bid in terms of other parameters, for instance in time to delivery of goods or
services, or in
quality of goods or services, or rate of delivery once delivery has begun.
It would be possible to embed more than two parameters in the relationship
that a
bid contains although the comparison between bids would become more complex.
It
would also be possible to weight parameters in order of importance in a
comparison, and
perhaps to apply that weighting locally to take local factors into account in
relation to the
location where the bid is received and/or to the location where the bid has
been
assembled.
In an alternative to the embodiments of the invention as described above, the
following describes a way of identifying a pair of bids which together define
a mutually
acceptable region based on price versus time to delivery of a resource. This
would be
relevant where a resource, which could be equipment or even a person
("worker"), can
provide or receive goods or a service but has a preferred time period for
delivery.
Referring to Figure 12, it is possible to develop a utility function "U" which
represents a measure of whether an option is good or bad for an entity. A
utility function
can be expressed in terms of the components making up a bid, in this case
price and time
to delivery. A change in price and or time results in a change, 3 U, in the
utility function for
the entity concerned.
If the entity is for instance a worker willing to bid to take on a new job,
which is
equivalent to providing a resource where a piece of equipment is concerned, it
is possible
to consider 3 U as a result of taking on the new job:
3 U = U(C+cnew) - U(C)
Note that it isn't necessarily the case that 3 U = U(cnew). Since cnew is
parameterised by the new price p and time t which are being negotiated, it is
possible to
solve the above equation for p in terms of t. For a fixed value for 3 U , this
produces a
price-time curve as shown in Figure 12. This is the price-time curve for a
worker. The line
at p=1 denotes the lowest the worker can get paid before making a loss.
CA 02389828 2002-05-02
WO 01/35284 PCT/GB00/04293
34
Figure 13 shows a price-time curve for a work queue manager. The line at p=2
denotes the highest the work queue manager can pay before making a loss.
Figure 14 shows both price-time curves on the same plot, or deal space. It can
be
seen that the regions defined by the curves overlap to show a mutually
acceptable region
1400.
Referring to Figure 15, any price-time point in that region gives an increase
in
utility of 3 U to both the worker and the work queue manager. Stepping up the
value of
3 U eventually leaves only one point. This point defines a price-time point
that gives the
mutual maximum change in utility to both parties involved in the negotiation
and can be
selected as the price-time point to be recorded for a contract between the
worker and the
work queue manager.
