Communications of the ACM
Communications of the ACM
Automated Negotiation
Negotiation is a key component of e-commerce. In automated negotiation, computational agents find and prepare contracts on behalf of the real-world parties they represent. This automation saves human negotiation time, and computational agents are often better at finding deals in combinatorially and strategically complex settings. Such benefits need not involve a cost to the other contracted parties, because negotiation is more than just constant-sum bargaining over price. When different users have different preferences, automated negotiation can rapidly find solutions that improve the utility for all parties.
The most promising application areas for automated negotiation include retail e-commerce, electricity markets, bandwidth allocation, manufacturing planning and scheduling in subcontracting networks, distributed vehicle routing among independent dispatch centers, and electronic trading of financial instruments.
Task reallocation among agents is a key type of negotiation. Reallocation is beneficial when tasks are not initially allocated to the agents that handle them least expensively. That's why I developed a marginal cost-based method for automated task reallocation negotiation that helps reallocate all types of items (beside tasks), such as financial instruments and hours of electricity.
In this method, each agent willingly takes on a task from another agent as long as it is paid more by the other agent than it costs the first agent to handle the task itself. Similarly, an agent willingly gives out a task to another agent as long as it does not have to pay the other agent more than it would cost the first agent to handle the task itself. Using this method in 1990, I built the TRAnsportation COoperation NET (TRACONET) system for automated delivery of task reallocation among freight companies. To my knowledge, this was the first distributed implementation of automated negotiation among self-interested agents. Each software agent, executing in its own Unix process, represents a single company in the negotiation. An agent can take on delivery tasks from some agents and give out tasks to others. Each agent can also recontract-out tasks it had previously contracted-in.
However, negotiation can get stuck in a local optimum where task allocation is suboptimal but where no original (O) contract (transferring one task and a payment) is profitable. To escape such local optima, I introduced into automated negotiation several new contract types: cluster (C) for exchanging multiple tasks for a payment; swap (S) for swapping a task for another task and a sidepayment; multiagent (M) when more than two parties are involved in the same contract; and OCSM for combining these ideas into an atomic contract, guaranteeing that globally optimal allocation is achieved through a finite number of contracts.
While my original implementations of such contracting were based on agent-to-agent negotiation, my colleagues and I recently built an auction server implementing a centrally mediated variant. Agents send bids and tasks for combinations of items to the server (see the Figure). Unlike traditional auctions, these combinatorial auctions allow users to express interrelated valuations of the itemsa particularly important function in illiquid, highly volatile, and noncommoditized markets where a participant is unsure whether he or she can buy the items in a desired bundle one at a time.
This auction server is part of eMediator, our e-commerce server, which also provides services other than auctions. To my knowledge, eMediator is the first Internet auction to support combinatorial bidding, bidding via price-quantity graphs, and mobile agents. eMediator determines the winners of the combinatorial auction, identifying profitable contracts for the participating agents. But because optimal winner determination is computationally so complex, we added a highly optimized search-based matching algorithm to work through the problem.
Price-quantity graphs allow users to express continuous preferences. Mobile agents allow users to have their agents participate in the auction while these users are disconnected from the Internet. Mobile agents execute on the agent dock on or near the auction host to reduce network latencya key issue in time-critical bidding. eMediator uses Mitsubishi's Concordia agent dock to give mobile agents a safe execution platform from which to bid, set up auctions, travel to other auction sites, and observe the activity at various auctions (see Koblick's "Concordia" in this issue).
eMediator also provides an HTML interface through which users specify what they want their agents to do, automatically generating Java code for the corresponding mobile agents before launching them.
Contracts are usually binding in automated negotiation systems for self-interested agents. Such contracts do not allow agents to undo old commitments to accommodate new events, such as tasks that turn out to be more costly than anticipated or the arrival of more lucrative offers later on. To circumvent these problems, I devised a leveled commitment contracting protocol that allows agents to accommodate future events by offering the option of unilateral decommit. The commitment level is chosen by assigning a decommitment penalty to each contract party; to be freed from the contract, the agent pays the penalty to the other parties.
One concern is that rational agents are reluctant to decommit; there is a chance another party will also decommit, in which case the first agent is freed from the contract, does not have to pay a penalty, and collects a penalty from the breacher. However, despite insincere decommitting, the leveled commitment feature increases each contract party's expected payoff, enabling contracts in settings where no full commitment contract is beneficial to all parties.
Footnotes
Supported by NSF CAREER Award IRI-9703122, NSF grant IRI-9610122, and NSF grant IIS-9800994.
Figures
Figure. A combinatorial bid in eMediator. Here, a refinery operator needs three consecutive hours of electricity, preferring to start at 8 a.m., because running the plant then requires the least electricity; starting at 6 a.m. or 7 a.m. would also be acceptable.
©1999 ACM 0002-0782/99/0300 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 1999 ACM, Inc.
No entries found