Background of the Invention Automated systems in which agents perform tasks and/or conduct negotiations are becoming increasingly important. In particular, systems involving numerous agents that can interact with one another are becoming increasingly important due to rapid advances in computer and networking technology.

The capability of allocating and reallocating tasks among agents is a key feature in such systems. In many domains, significant savings can be achieved by reallocating tasks among agents. Some tasks are inherently synergic, and should therefore be handled by the same agent. On the other hand, some tasks have negative interactions, in which case it is better to allocate them to different agents.

Furthermore, different agents may have different resources which leads to different capabilities and costs for handling tasks.

Accordingly, there is a need for a system for arriving at optimal, or at least improved, task allocation among agents.

Summary of the Invention The present invention involves contracting a system for agents, which system can be used in determining an optimal task allocation. In preferred embodiments of the present invention, individually rational (IR) self-interested agents contract tasks among themselves based on marginal costs.

Brief Description of the Drawings One or more embodiments of the present invention are described in connection with the following drawings, in which: FIG. 1 illustrates a task allocation graph in which the vertices represent task allocations and the edges represent O-contracts.

FIG. 2 illustrates an example of a cluster contract that can be used in connection with some embodiments of the present invention.

FIG. 3 illustrates an example of a swap contract that can be used in connection with some embodiments of the present invention.

FIG. 4 illustrates an example of a multiagent contract, involving three agents, that can be used in connection with some embodiments of the present invention.

Detailed Destription of Preferred Embodiment(s) 1. Embodiments and Contract Types This section describes embodiments of a task (re)allocation system where individually rational (IR) agents (re)contract tasks among themselves based on marginal costs. In this description, a task allocation graph is introduced as a tool for analyzing contract types. Traditional single task contracts always have a short path (sequence of contracts) to the optimal task allocation but an IR path may not exist, or it may not be short. An algorithm for finding the shortest IR path is described.

These embodiments are also described in connection with cluster contracts, swaps, and multiagent contracts. Each of the four contract types avoids some local optima that the others do not. Even if the protocol is equipped with all four types, local optima exist. To address this issue, we introduce OCSM-contracts which combine the ideas behind the four earlier types into an atomic contract type are used in same embodiments. If the protocol is equipped with OCSM-contracts, any sequence of IR contracts leads to the optimal task allocation in a finite number of steps: an oracle---or speculation---is not needed for choosing the path (no subset of OCSM-contracts suffices even with an oracle).

Definition 1. An example of a task allocation problem is defined by a set of tasks T, <BR> <BR> <BR> a set of agents A, a cost function ci : 2T # ##{#} (which states the cost that agent incurs by handling a particular subset of tasks), and the initial allocation of tasks among agents, #Tlinit, ..., T |A|init#where #iEATiinit = T, and Tiinit #Tjinit =# for i #j.

Many embodiments use a variant of the contract net approach--which is a distributed method for mutual selection of contractors and contractees -- for task allocation. Section 2 describes the use of marginal costs as a basis for making individually rational (IR) contracts. Classic contracts of one task at a time are described in Section 3. Then, three new contract types---cluster contracts, swaps, and

multiagent contracts--are described in Sections 4, 5 and 6, respectively. Finally, Section 7 discusses combinations of these contracts types.

2. IR Contracting Based On Marginal Cost Many embodiments of the present invention use a contract net protocol in which contracting decisions are based on marginal cost calculations. The concept of individual rationality on a per contract basis is used in connection with such embodiments. In other words, a contract is IR to an agent if that agent is better off with the contract than without it. This implies individual rationality of sequences of contracts.

Specifically, a contractee g accepts a contract if it gets paid more than its marginal cost.

MCadd(TcontractlTg) = Cg(TcOntTact uTg) - cg(Tg) of handling the tasks Contract of the contract. The marginal cost is dynamic in the sense that it depends on the other tasks Tg that the contractee already has.

Similarly, a contractor h is willing to allocate the tasks Contract from its current task set Th to the contractee if it has to pay the contractee less than it saves by not handling the tasks Contract itself: MC em°Ve(TC°ntraCtlTh) = ch(Th) - c (T Tcontract) In the protocol, agents then suggest contracts to each other, and make their accepting/rejecting decisions based on these marginal cost calculations. An agent can take on both contractor and contractee roles. It can also recontract out tasks that it received earlier via another contract. The scheme does not assume that agents know the tasks or cost functions of others.

With this domain independent contracting scheme, the task allocation can only improve at each step. This corresponds to hill-climbing in the space of task allocations where the height-metric of the hill is social welfare (-SiEA Ci (Ti)). The fact that the contractor pays the contractee some amount between their marginal costs (e.g. halfway between) causes the benefit from the improved task allocation to be divided so that no agent is worse off with a contract than without it.

The scheme is an anytime algorithm: contracting can be terminated at any time, and the worth (payments received from others minus cost of handling tasks) of each agent's solution increases monotonically, improvements are monotonic for each agent's solution, in a provable manner. It follows that social welfare increases monotonically.

The embodiments described herein are described in connection with FIGs. 1-4, which are described herein.

FIG. 1 shows a task allocation graph. Vertices 2, 4, 6, 8, 10, 12, 14, 16 and 18 represent task allocations, and edges 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52 and 54 represent O-contracts.

FIG. 2 shows an example of a cluster contract involving two agents. Agent 1 ' s tasks are shown at 102 and Agent 2's tasks are shown at 104.

FIG. 3 shows an example of a swap contract, which involves two agents.

Agent l's tasks are shown at 202 and Agent 2's tasks are shown at 204.

FIG. 4 shows an example of a multiagent contract. In the illustrated case, three agents are involved. Agent 1 's tasks are shown at 302. Agent 2's tasks are shown at 304. Agent 3's tasks are shown at 306.

Definition 1. Our task allocation problem is defined by a set of tasks T, a set of agents A, a cost function ci : 2T # ##{#}(which states the cost that agent i incurs by handling a particular subset of tasks), and the initial allocation of tasks among agents for all i + j.

We use a variant of the contract net approach-which is a distributed method for mutual selection of contractors and contractees [1 5for task allocation.

Section 2 presents the use of marginal costs as a basis for making individually rational (IR) contracts. Classic contracts of one task at a time are studied in Section 3. Then, three new contract types-cluster contracts, swaps, and multiagent contractvare studied in Sections 4, 5, and 6 respectively. Finally, Section 7 discusses combinations of these contracts types.

2 IR contracting based on marginal cost The original contract net [15] lacked a formal model for making bidding and awarding decisions. Such a model would allow one to develop methods that provably lead to desirable task allocations among agents. We follow the approach of [9], where contracting decisions are based on marginal cost calculations. In so doing we invoke the concept of individual rationality on a per contract basis. A contract is IR to an agent if that agent is better off with the contract than without it. This implies individual rationality of sequences of contracts.

Specifically, a contractee g accepts a contract if it gets paid more than its marginal cost MCadd(Tcontract|Tg) = cg (Tcontract # Tg)-cg(Tg) of handling the tasks TConXrac' of the contract. The marginal cost is dynamic in the sense that it depends on the other tasks Tg that the contractee already has.

Similarly, a contractor h is willing to allocate the tasks Tcontract from its current task set T, to the contractee if it has to pay the contractee less than it saves by not handling the tasks Tcontract itself: MCremove(Tcontract|Th) = Ch (Th)-ch(Th - Tcontract).

In the protocol, agents then suggest contracts to each other, and make their accepting/rejecting decisions based on these marginal cost calculations. An agent can take on both contractor and contractee roles. It can also recontract out tasks that it received earlier via another contract. The scheme does not assume that agents know the tasks or cost functions of others.

With this domain independent contracting scheme, the task allocation can only improve at each step. This corresponds to hill-climbing in the space of task allocations where the height-metric of the hill is social welfare The fact that the contractor pays the contractee some amount between their marginal costs (e.g. halfway between) causes the benefit from the improved task allocation to be divided so that no agent is worse off with a contract than without it.

The scheme is an anytime algorithm: contracting can be terminated at any time, and the worth (payments received from others minus cost of handling tasks) of each agent's solution increase monotonically. It follows that social welfare increases monotonically. Details on an asynchronous distributed implementation based on marginal costs can be found in [9].

3 Classic contracts of one task at a time (O-contracts) In most contract net implementations, each contract regards only one task [15, 14, 4]. We now formalize this contract type: Definition 2. An O-contract is definedbyapair (Tj pjV),where = 1. To is the task set (including one task) that agent i gives to agentj, and size is the contract price that i pays toj for handling the task set.

For any problem instance, the optimal task allocation can be reached via O-contracts: Proposition 3 (Path). A path ofO-contracts always exists from any task allocation to the optimal one. The length of the shortest such path is no greater than 171.

This means that if agents could carry out full lookaheaywhich is impossible in all but the smallest problem instances4-contracts would suffice to reach the optimal task allocation because agents would be willing to temporarily move to worse task allocations in order to finally reach the optimal one. However, when agents use

individual rationality as a criterion for contracting, they will not accept the temporary decrease in social welfare. It turns out that this leads to local optima-even if there were an oracle for choosing the sequence of IR contracts: Proposition 4 (IR path). In some instances ofour task allocation problem, no path ofIR O-contracts exists from the initial allocation to the optimal one. The length of <BR> <BR> <BR> <BR> the shortest JR path (if one exists) may be greater than |T|. However, the shortest IR path is never longer than tAgIr A TI.7 3.1 Computing the shortest IR path We mainly use the task allocation graph to analyze contract types. However, if the problem instance is not very large, the graph can actually be constructed and used to choose a sequence of contracts. To avoid unnecessary negotiations, it is desirable to minimize the number of contracts while still reaching the optimal task allocation. The approach is to first determine the optimal task allocation via a linear pass through the vertices. Next, breadth-first-search is run on the graph starting from the initial task allocation. The only difference is that when inserting children into the open list, the algorithm omits children that have lower social welfare than the parent (these contracts would not be IR). When the search reaches the optimal task allocation for the first time, the shortest IR path has been found. If the search terminates without reaching the optimal vertex, no IR path exists.

It is known that breadth-first-search runs in O(v + e) time, where v is the number of vertices and e is the number of edges in graph [2]. There is one vertex for each task allocation, so v = IA . The number of edges is the same at each vertex: 71 (lAl - 1). This is because in an O-contract, any task can be transferred to any agent <BR> <BR> <BR> except its current holder. So, e = 2' 171 (lAl - 1). Therefore, the total running time is 3.2 Sparseness of O-contracts To get an intuition about the search space in which contracting occurs, we show that the task allocation graph becomes arbitrarily sparse as the problem size increases:

Proposition 5. Let |A|#2 and |T|#2. Now e -> <BR> &num edges in fully connected graph<BR> <BR> <BR> 0 as |T| -># as well as when |A|->#. e<BR> Proof #edges in fully connected graph This approaches 0 when |A|#2 and |T|->#. It also approaches 0 when |T|#2 and |A| -> #.

4 Cluster contracts (C-contracts) Using one task per contract is insufficient: the agents may get stuck in a local optimum. We now formalize a contract type that addresses this problem: Definition 6. A cluster contract (C-contract) is defined by a pair #Ti,j, #i,j#, where |Ti,j|>1. Ti,j is the task set that agent i gives to agentj, and Pi, is the contract price that i pays to j for handling the task set.

C-contracts induce a set of edges in the task allocation graph that is disjoint from the set of edges induced by O-contracts. This leads to C-contracts avoiding some of the local optima of O-contracts. (O-contract also avoid some of the local optima of C-contracts): Proposition 7. Local optima exist where no transfer of a single task between agents enhances the global task allocation (and therefore there exists no IR O-contract), but transferring a larger set of tasks simultaneously does (i.e. an IR C-contract exists).

Proof Let there be two tasks: t1,t2, and two agents: 1, 2 (Fig. 2). Let the current task allocation be T, = {t1,t2 }, T2 = . Let the task handling costs be c, (8) = 0, c1({t1})= c1({t2})= 4, c1({t1,t2})= 5, c2(#)=0, c2({t1}) = c2({t2}) = 2, c2({t1,t2}) = 3.

So, the current global cost is 5. Moving t, to 2 would increase the global cost to 6.

So would moving t2 to 2. However, moving both t, and t2 to 2 would decrease the global cost to 3. So this C-contract is IR The need for larger transfers is well known in centralized iterative refinement optimization [5, 16], but has been historically ignored in automated negotiation.

Recently, the TRACONET system extended the contract net to handle task interactions by having the announcer cluster tasks into sets to be negotiated atomically

[9]. Alternatively, the bidder could have done the clustering by counterproposing.

Later, Sandholm has presented a protocol that generalizes this by allowing either party to do the clustering at any stage of the protocol [11].

In general, a cluster can encompass any number of tasks. A task allocation is called k-optimal if no beneficial cluster contract of any k tasks can be made between any two agents. Now, m-optimality does not imply n-optimality when m < n. More surprisingly, n-optimality does not imply m-optimality.

Global optimality implies k-optimality for all k. However, the reverse is not true (the proof of Proposition 11 will demonstrate an example where the solution is k- optimal for all k but not globally optimal). It also turns out that C-contracts may not lead to the optimal task allocation even if there were an oracle for choosing the path of C-contracts of any cluster size: Proposition 8 (Path). There are instances of the task allocation problem where no path of C-contracts leads from the initial task allocation to the optimal one.

Proof The example in the proof of Prop. 11 shows this. Each agent has only one task: no C-contract is possible. However, the task allocation is not optimal.

Corollary 9 (IR path). There are instances of the task allocation problem where no IR path of C-contracts leads from the initial task allocation to the optimal one.

Proof Immediate from Proposition 8.

Another problem is that without an oracle, contracting may get stuck in a local optimum even if some IR path from the initial allocation to the optimal one exists because that path may not be chosen.

5 Swap contracts (S-contracts) Sometimes there is no task set size such that transferring such a set from one agent to another (C-contract or O-contract) enhances the task allocation. Yet there may be a beneficial swap of tasks where the first agent subcontracts a task to the second and the second subcontracts another task to the first [11]. We now formalize this concept: Definition 10. A swap contract (S-contract) is defined by a 4-tuple #Ti,jTj,i,#i,j,#,j,i#, where |T B| = ITjjl = 1. Ti is the task set (including one task) that agent i gives to

agent j. Tj,i is the task set (including one task) that agentj gives to agent i. #i,j is the amount that i pays toj, and #j,i is the amount thatj pays to i.

S-contracts induce a set of edges in the task allocation graph that is disjoint from the sets of edges induced by 0- and C-contracts. This leads to S-contracts avoiding some of the local optima that 0- and C-contracts cannot resolve (0- and C- contracts in turn avoid some of the local optima of S-contracts): Proposition 11. Locally optimal task allocations exist where no IR O-contract or IR C-contract is possible, but an IR S-contract is (and this increases social welfare).

Proof Let there be two tasks: t1t2, and two agents: 1, 2 (Fig. 3). Let the current task allocation be T = (t1 ),T, = (t2 ). Let the task handling costs be c1 () = 0, c, ({t, }) = 2, c, ((t, = 1, c1((t1,t2}) = 5, c2(()) = 0, c2((t1}) = 1, c2({t2}) = 2, C2 ({t1 ,12 }) = 5. So, the current global cost is 4. Because each agent has only one task, no C-contract is possible. Moving t, to 2 would increase the global cost to 5. So would moving t2 to 1. Thus no O-contract is IR. However, moving t from 1 to 2 and simultaneously t2 from 2 to 1 would decrease the global cost to 2. So, this S- contract is IR.

The protocols needed for cooperative agents and those needed for self- interested agents differ. Cooperative agents can be assumed to take care of each others tasks without compensation whenever that is beneficial for the society of agents. Self-interested agents need some compensation to take care of some other agent's task. This compensation can be organized as barter trade: one agent takes care of some of another agent's tasks if the latter agent takes care of some of the former agent's tasks. Barter trades that benefit both agents (IR deals) do not always exist even if it were profitable to move a task from one agent to another. Secondly, identifying beneficial barter exchanges is more complex than identifying one way transfers of tasksespecially in a distributed setting. A finer resolution of cooperation among self-motivated agents can be achieved by a monetary compensation mechanism: an agent pays another agent to take care of some of its tasks. The need for swaps shows that payment based exchanges cannot replace all barter exchanges. What is needed is the monetary exchange method (that allows

infinitely divisible side-payments) but also a linking mechanism that allows swapping tasks atomically among agents (S-contracts).

Although the previous proposition shows that S-contracts are necessary, they are not sufficient for reaching the global optimum: Proposition 12 (Path). There are instances of the task allocation problem where no path ofS-contracts leads from the initial task allocation to the optimal one.

Proof If some agent has a different number of tasks in the initial task allocation than what that agent would have in the optimal allocation, then the optimal allocation cannot be reached. This is because S-contracts preserve the number of tasks that each agent has.

Corollary 13 (IR path). There are instances of the task allocation problem where no IR path ofS-contracts le ads from the initial task allocation to the optimal one.

Proof Immediate from Proposition 12.

Also, even if an IR path exists, the contracting agents may use some other path of IR contracts and get stuck in a local optimum. Furthermore, because S-contracts preserve the number of tasks that each agent has, they can only reach a very small subset of task allocations: Proposition 14. Let |A| # 2 and |T| # 2. As |T| -> #, or |A| -> #, the fraction of task allocations that are reachable via any (IR or not) S-contracts from any given initial vertex approaches zero.

This implies that the chance of reaching the optimal task allocation via any (even one with an oracle for picking the path) hill-climbing S-contracting algorithm vanishes.

6 Multiagent contracts (M-contracts) Even if negotiations have reached a local optimum with respect to mutual (0-, C-, and S-) contracts of any size, solution enhancements may be possible if tasks were transferred among more than two agents.

Definition 15. A multiagent contract (M-contract) is defined by a pair (T,p) of |A|x|A| matrices, where at least three elements of T are non-empty (otherwise this would be just a 2-agent contract), and for all i andj, 11;J < 1 An element T is the

set of tasks that agent i gives to agentj, and an element Pi,j is the amount that i pays toj.

Decentralized multiagent contracts can be implemented for example by circulating the contract message among the parties and agreeing that the contract becomes valid if every agent signs. M-contracts induce a set of edges in the task allocation graph that is disjoint from the sets of edges induced by O-, C-, and S- contracts. This leads to M-contracts avoiding some of the local optima that 0-, C-, and S-contracts cannot resolve. (0-, C-, and S-contracts in turn avoid some of the local optima of M-contracts): Proposition 16. Task allocations exist where no IR O-contract, IR C-contract, or IR S-contract is possible, but an IR M-contract is (and this increases social welfare).

Proof. Let there be three tasks: t1,t2,t3, and three agents: 1, 2, 3 (Fig. 4). Let the current task allocation be T1 = {t1}, T2 = {t2}), T3 = {t3 } . Say that the task handling <BR> <BR> <BR> <BR> costs are c1(#) = 0, c1({t1}) = 2, c1({t2}) = 5, c1({t3}) = 1, c1({t1,t2})= c1({t1,t3})= c1({t2,t3})=10, c1({t1,t2,t3})=15, c2(#)=0, c2((t1})=1, c2({t2})= 2, C2({t3})= 5, c2({t1,t2}) = c2((t1,t3}) = c2((t2,t3}) = 10, c2((t1,t2,t3}) = 15, C3(#)=0, c3({t1})= 5, c3((t3}) = 2, c3({t2}) = 1, c3((t1,t2}) = c3((t1,t3}) = c3({t2,t3}) = 10, c3({t1,t2,t3}) = 15. So, the current global cost is 2 + 2 + 2 = 6. C-contracts are impossible here because no agent has more than one task. Any one of the six possible O-contracts would increase global cost to 0 + 2 + 10 = 12. Any one of the three possible swaps would increase global cost to 1 + 2 + 5 = 8. Therefore, no O-, or S- contract is IR. However, moving t, from 1 to 2, t2 from 2 to 3, and t3 from 3 to 1 would decrease the global cost to 3. So, this M-contract is IR.

Although Proposition 16 shows that M-contracts are necessary, they are not sufficient: Proposition 17 (Path). There are instances of the task allocation problem where no path ofM-contracts leads from the initial task allocation to the optimal one.

Proof. The example in the proof of Prop. 7 shows this. There is no possible M- contract (there are only two agents), and the task allocation is suboptimal.

Corollary 18 (IR path). There are instances of the task allocation problem where no IR path of M-contracts leads from the initial task allocation to the optimal one.

Proof. Immediate from Proposition 17.

Another problem is that contracting may get stuck in a local optimum even if some IR path from the initial allocation to the optimal one exists because the agents may choose some other path of IR contracts.

7 Merging the types: OCSM-contracts No one of the presented four contract types is sufficient for reaching the global optimum via IR contracts--even if there were an oracle for choosing the path of contracts-because no IR path need exist to the optimal task allocation. The proof of Prof. 11 showed that cluster contracts are not sufficient, and the proof of Prof. 16 showed that swap contracts are not. Finally, the example in the proof of Prop. 7 shows that multiagent contracts are not sufficient, and that O-contracts are not.

Even if the contracting protocol is equipped with all four of the contract types, the optimal task allocation may not be reached via IR contracts--even with an oracle: Proposition 19 (IR path). There are instances of the task allocation problem where no IR path from the initial task allocation to the optimal one exists using O-contracts, C-contracts, S-contracts and M-contracts.

Proof. Think of a deal where one agent gives a task to another agent, and the other agent gives two tasks to the first agent. This can be made to be the only welfare increasing deal because we are free to pick the welfare values for different task allocations. However, this deal is not possible via an O-, C-, S-, or M-contract.

Clearly, no subset of the contract types suffices either: Corollary 20 (IR path). There are instances of the task allocation problem where no IR path from the initial task allocation to the optimal one exists using any pair or triple of the following contract types: O-contracts, C-contracts, S-contracts and M- contracts.

Proof. Prop. 19 shows that an IR path may not exist even with all four contract types.

Removing contract types can only remove edges from the task allocation graph.

Thus, removing contract types cannot introduce new paths.

Another problem is that without an oracle, contracting may get stuck in a local optimum even if some IR path exists because the agents may choose some other IR path.

To address these shortcomings, let us define a new contract type, OCSM- contract, that combines the characteristics of O-, C-, S-, and M-contracts into one contract type-where the ideas of the four earlier contract types can be applied simultaneously (atomically). <BR> <BR> <BR> <BR> <P>Definition 21. An OCSM-contract is defined by a pair (T, of (Al |A| x |A| IA matrices.

An element WJ is the set of tasks that agent i gives to agentj, and an element Pi,j is the amount that i pays toj.

OCSM-contracts induce a fully connected task allocation graph. On the other hand, 0- (Fig. 1), C-, S-, and M-contracts each induce disjoint sets of edges which are strict subsets of the edges of the fully connected graph. The union of the edge sets induced by O-, C-, S-, and M-contracts is a strict subset of the edges of the fully connected graph.

We could proceed to show that a path and an IR path always exist from any task allocation to the optimal one if the contracting protocol incorporates OCSM- contracts. However, we show something stronger. The following proposition states that OCSM-contracts are sufficient for reaching the global task allocation optimum in a finite number of contracts. The result holds for any sequence of IR OCSM- contracts, i.e. for any hill-climbing algorithm that uses OCSM-contracts: an oracle is not needed for choosing the path. This means that from the perspectives of social welfare maximization and of individual rationality, agents can accept IR contracts as they are offered. They need not wait for more profitable ones, and they need not worry that a current contract may make a more profitable future contract unprofitable.

Neither do they need to accept contracts that are not IR in anticipation of future contracts that make the combination beneficial. Furthermore, these hill-climbing algorithms do not need to backtrack.

Proposition 22. Let |A| and |T| be finite. If the contracting protocol allows OCSM- contracts, any hill-climbing algorithm (i.e. any path of JR contracts finds the globally optimal task allocation in finite number ofsteps (without backtracking).

Proof. An OCSM-contract can move from the current task allocation to any other in a single step. Thus the optimal task allocation can be reached from any task allocation: there are no local optima. Clearly the move to an optimal task allocation is IR because an optimal task allocation has higher welfare than any other. Thus the hill- climbing algorithm does not need to backtrack in order to reach the optimum.

Because agents only make IR contracts, every contract (strictly) improves social welfare. Therefore, no task allocation is visited more than once. Because there <BR> <BR> <BR> <BR> <BR> are a finite number of tasks T and agents A, the number of task allocations (|A|Ir (AI1) is finite. It follows that the global optimum is reached in a finite number of steps.

OCSM-contracts are also necessary: no weaker set of contract types suffices even if there were an oracle to choose the order in which to apply them: Proposition 23. If there is some OCSM-contract that the protocol does not allow, there are instances of the task allocation problem where no IR path exists from the initial allocation to the optimal one.

Proof. If some OCSM-contract is missing, the task allocation graph contains (at least) two vertices that do not share an edge. Let the initial and optimal allocations be these two. The social welfares can be chosen so that in all vertices adjacent to the initial one, welfare is lower than in the initial one. Thus no IR path can lead away from the initial task allocation.

Proposition 22 gives a powerful tool for problem instances where the number of possible task allocations is relatively small. On the other hand, for large problem instances, the number of contracts made before the optimal task allocation is reached may be impractically largc albeit finite. For example on a large-scale real-world distributed vehicle routing problem instance, TRACONET [9] never reached even a local optimum even with just O-contractswith multiple hours of negotiation time on five Unix machines. Another problem is that although any OCSM-contract can be represented in O(|A|² + |T|) space, the identification of welfare increasing contracts

may be complex especially in a distributed setting--because there are 2 = !AItlTl-IAIItI possible OCSM-contracts, and the evaluation ofjust one contract requires each contract party to compute the cost of handling its current tasks and the tasks allocated to it via the contract.

With such large problem instances, one cannot expect to reach the global optimum. Instead, the contracting should occur as long as there is time, and then have a solution ready: the anytime character of our contracting scheme is more important.

The presented marginal cost based (re)contracting method guarantees that the algorithm has a feasible solution even if terminated at any time (assuming that the initial solution was feasible). Furthermore, it guarantees that the worth of each agent's solution (payoffs received from others minus cost of handling tasks) increases monotonically. It follows that no agent is worse off after the negotiation than it was under the initial solution where it handled its own tasks. It also follows that the social welfare increases monotonically during the negotiation.

Certain embodiments of the present invention have been described in detail above. It will be understood by those skilled in the art that the present invention is defined solely by the claims, and that other embodiments and many modifications of the above-described embodiments are within the scope of the invention, as defined by the claims.

It will be understood by those skilled in the art that in many embodiments the agents are software agents.

It will also be understood by those skilled in the art that in many embodiments the agents communicate with one another over a computer network, in any conventional manner, to conduct the contracting described above.