University of Minnesota
Magnet: Multi AGent NEgotiation Testbed

In recent years, many researchers and practitioners have focused on the design of market architectures for electronic commerce, and on protocols governing the interaction of self-interested agents engaged in such transactions. While providing support for direct agent negotiation, the existing architectures for multi-agent virtual markets usually lack explicit facilities and infrastructure for handling multiple and varied negotiation protocols. Since existing market architectures do not provide such protocols as an integrated part of the framework, they will have to be extended in order to provide such support.

We have developed MAGNET (Multi AGent NEgotiation Testbed), and architecture that provides support for complex agent interactions, such as in automated contracting, as well as other types of negotiation protocols. In particular, we are interested in business-to-business situations in which a company outsources production to outside contractors and needs to automate as much as possible the management of the supply-chain.

Agents in MAGNET negotiate and monitor the execution of contracts among multiple suppliers. Each agent is an independent entity, with its own structure, goals, and resources. In general, the resources under control of an individual agent are not sufficient to satisfy that agent's goals, and so the agent must negotiate with other agents in its environment in order to meet its goals.

We distinguish between two agent roles, the Customer and the Supplier. A Customer is an agent who needs resources outside its direct control in order to carry out his plans. In response to a Request for Quotes, some set of Supplier agents may offer to provide the requested resources or services, for specified prices, over specified time periods. Once the Customer agent receives bids, it evaluates them based on cost, risk, and time constraints, and selects the optimal set of bids which can satisfy its goals. Suppliers are then notified of their commitments, and the Execution Manager is called to oversee completion of the plan. Plan maintenance includes re-negotiating existing commitments, re-bidding portions of the plan, re-planning, and abandoning the goal.

Here is a screen shot of the Plan/RFQ generation screen. The current TaskPlan is represented by a Table view (in the upper left-hand corner) and a Gantt chart view (in the upper right-hand corner). The thin line trailing each Gantt object depicts the amount of schedule slack each task has allotted to it. The lower half of the screen allows for editing of the TaskPlan, as well as specifying RFQ-related parameters before submitting an RFQ.


We have developed various search algorithms for winner determination (A*, IDA*, integer programming, and simulated annealing). The Customer agent's objective is to maximize utility, which requires minimizing cost and risk of not accomplishing the goal. To determine which bids (or parts of bids) to accept, the Customer agent considers coverage (we assume that there is no point in accomplishing only a part of the goal), temporal feasibility (the time windows for tasks must allow to compose them in a feasible schedule), cost, and risk. Risk factors include elements such as availability of suppliers, supplier reliability, profit margin, expected cost of recovering from supplier decommitment or delay, loss of value if the end date is delayed, cost of plan failure.

Below is a screen shot of the Bid Evaluation portion of the customer GUI. When a bid is highlighted in the table, the corresponding tasks in the TaskPlan table (upper left-hand corner) are highlighted, and Gantt objects representing those bid components are superimposed over those Gantt objects. Both Bids and Tasks can have slack tails representing flexibility in execution timing.


Material based upon work supported by the National Science Foundation under Grants No. IIS-0084202 and IIS-0414466. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.