To support negotiation and economic transactions among UMDL agents, we need to define protocols for reaching agreements and specifying the terms of deals between agents, for managing these commitments, and for enforcing and executing the agreements when possible.
The current version of KQML does not provide any high-level negotiation constructs, and so if we wish to define our negotiation protocols in terms of KQML message types, we require an expanded set of types designed to support negotiation.
The primary extension we propose is a new KQML performative, called offer. An offer is supposed to represent an agent's expression of willingness to engage in some deal. In general, the deal can be any exchange of goods and services (henceforth, we include "services" within "goods") describable in the system. For example, it can be an offer to sell some particular amount of a particular price, or a complex barter of services.
One key issue is the level of commitment represented by an offer. For simplicity, we propose that an offer represents a binding commitment, that is, an agent is obliged to live up to any outstanding offer (which is not to say that the UMDL can necessarily enforce this rule). Given this interpretation, it will also be necessary to include a mechanism to withdraw an offer, whereby an agent can invalidate a previously outstanding offer. This can be accomplished, for example, by submitting a superseding NULL offer.
We envision a hierarchy of offer types, each of which constrains some feature of the offer's structure. Some examples:
Other features on which offer types might differ:
Note that it may be somewhat of an exaggeration to use the term "negotiation protocol" for communications involving making and accepting offers. Typically negotiations also involve generating potential deals and persuading other agents to make favorable offers, two types of activity that are beyond the scope of offer.
A central issue in implementing negotiation and pricing will be how we represent the goods exchanged. We will undoubtedly have some mixture of standard (relatively homogeneous) goods, and other customized one-of-a-kind goods. In either case, goods might have atomic names, or structured and parametrized descriptors. We assume for now that there will be some good description language; the design of such a language is currently underway.
The advantages of defining a formal, expressive good description language are several. One of the most interesting is that we can define goods as variations of one another, and then automatically generate agents able to perform the necessary transformations.
A UMDL mediator is any agent that deals exclusively with other agents, rather than end-users or collections. It is useful to distinguish those mediators who exist only to bring together other agents. Such mediator agents are called facilitators.
The registry agent might be considered a facilitator, as its sole purpose is to maintain information about other agents in the UMDL. We propose another subclass of facilitators, called market facilitators, or auctions, consisting of facilitators that operate by collecting offers and determining agreements among agents. For example, one simple kind of auction collects bids and settles them by some market-clearing process. Other auctions might perform a more complicated matching and search process, or implement a more sophisticated allocation mechanism.
An auction announces its scope by issuing an advertise message:
(advertise (bid ... X ... Y ... ))
where X, Y, etc. describe the features of bids (e.g., the goods involved) that this auction can handle. Presumably, the registry agent will be the one interested in such advertisements, so they can tell interested agents where they go to make or review offers involving the goods they care about. Such agents will also want to subscribe [is this right?] to the results of auctions, e.g., information about the status of the bidding process.
In addition to specializing in particular goods, auctions might differ in other respects. For example, among the auctions that process bid offers and find clearing prices, distinguishing features include:
Protocols involving auctions will specify how the offers become accepted and executed. This means that the auctions have the authority to decide what offers can go through, and thus what deals are committed to. The protocol will specify a sequence of message informing the agents of the results of their offers (both positive and negative), and replacing and deleting offers as appropriate.
The offer performative and auction concept are very broad. They are intended to accommodate any negotiation mechanism that we may want to explore in the UMDL. Our next step will be to specify in greater detail the protocols and messages required to implement some specific cases. At first we will concentrate on supporting the bidding process used by our previously developed WALRAS algorithm (essentially the competitive mechanism), since that is a particularly simple and well-understood protocol.
The basic-auction facilitator agent we define is based on the way auctions currently work in the WALRAS system. Each auction is dedicated to a specific good, g. The auction entertains bid offers for good g, and based on the bids received, determines a price for good g and the quantity allocated to each bidder.
Bid offers are in the form of demand curves. Although various formats may be supported, the bids must specify a demand schedule, that is, a function from prices to quantities demanded. A negative quantity denotes a bid to supply the good at that price. In the simplest scheme, the bid represents a binding commitment for the bidder to purchase (or sell, if q is negative) exactly q units of g at the corresponding price. (We have considered and are continuing to investigate more flexible and elaborate schemes, and intend to incorporate these into UMDL auctions as they are developed).
Given a set of bids received by the auction, the excess demand for a given price is the sum of quantities demanded at that price, taken over all bids. We define a going price to be a price minimizing the absolute value of excess demand. If excess demand at the going price is exactly zero, we call that price a clearing price. The main function of the auction is to calculate and report going prices.
A basic-bid message is an offer sent by a UMDL agent A to a basic-auction for good g, where the terms specify the good, g, and a demand schedule. If the good specified in the message and the good handled by the auction match, then the effect of the message is that the auction associates agent A with the demand schedule specified. (If the goods do not match, then the message has no effect.) If the auction already had a bid associated with A, then the new one replaces the old. Note than A can effectively withdraw its outstanding bid, if any, by submitting a null bid.
At any time, the auction has a set of current bids, with possibly a queue of incoming bids to process. It may, at any time, calculate a going price for the current set of bids. If the going price has changed since the last time reported, it sends, to all current bidders, a tell message informing them of the current going price. This message must include the good and the going price, and optionally, a time stamp and an indication of whether the price is clearing. In specifying the protocol, we may dictate a maximum time interval between receipt of a new bid by an auction and report of new going prices. (Note that if an agent is interested in receiving these reports, it need only send a null bid to the auction.)
From the perspective of bidding agents, their bids are binding commitments, and may be called at any time. This gives them an incentive to keep their outstanding offers as up-to-date as possible. When the auction actually clears, all pending bids are processed (no new ones are accepted), the going price is calculated, and the result is implemented. Let us assume for now that the going price is a clearing price. The good is exchanged (if the system can implement this transfer), and payment is rendered. We will provide three methods for specifying when the market will actually clear.
The first of these appears to be the most amenable to manipulation by strategic bidding. One remedy would be to specify the clearing time as a random variable (e.g., following a geometric distribution). The third method, as specified, is also risky, as it may not terminate. By combining criteria for clearing, the designer can balance simplicity, competitiveness, predictability, and other qualities of interest.
If the going price is not a clearing price, then the auction implements a rationing policy. If the excess demand is positive, then the total amount supplied (i.e., sum over bids with negative quantities at the going price) is rationed proportionately to the buy bids. If the excess demand is negative, rationing is performed over sellers. (We acknowledge that rationing technically violates the interpretation of a bid as a willingness to exchange exactly q units at the specified price. It can be reconciled with an alternate interpretation where the bidder is willing to exchange up to q units.) If the good is indivisible (one common reason there may not be a clearing price), then rationing may be implemented by a lottery, dividing probability of obtaining the good rather than dividing the good itself.
Although the protocol actually implementing the exchange is beyond the scope of this specification, we require that it to include some kind of acceptance notification to the bidders, specifying the terms of the exchange agreed to.
For simplicity, basic-auctions may restrict the form of bids handled. Restrictions may be according to format (i.e., the language of bid schedules), or may impose more substantive constraints. The most useful of these will probably to restrict demand schedules to be downward-sloping, that is, nonincreasing functions of price. This would simplify the calculation of going prices. Stronger restrictions, such as continuity, may be imposed to ensure the existence of clearing prices.
To summarize, we have specified the communication protocol as a pattern of bid messages from agents to auctions, and tell messages from auctions to agents, culminating in an actual exchange. The timing of bid generation is completely unconstrained. Auctions must base their reports of going prices on the latest available (processed) bids, and must disseminate these reports with some regularity. At termination of the bidding process, the price is determined using the latest bids, and the resulting exchange is implemented.
Comments or questions may be sent to: UMDL.INFO@umich.edu