A Collaboration Mechanism on Positive Interactions in Multi-agent Environments

1 Introduction

In multi-agent environments where agents generate and execute plans which satisfy their own g~als , plans are generated independently, thus two rel~tiOnships [Mar­ tial 1992] exist among plans. The first IS called a nega­ tive' relationship and exists between plans which attempt to use the same resource at the same time. This re­ lationship will cause conflicts. Such conflicts. must be avoided or resolved because they prevent actiOns from being properly executed. The other relation is c~lle~ a positive relationship and exists between pl.an~ which m­ clude overlapping subplans, subplans consistmg of bot.h common actions and individual actions. When there IS a positive relationship and one agent delegates the ex~ cution of the overlapping subplan to the other agent, It can reduce the cost of execution.

A lot of research has been done on negative relation­ ships such as conflict avoidance, by using a social law [Shoham and Tennenholtz, 1992] and conflict resolution based on game theory [Zlotkin and Rosen~~hein , 19.90] . However , despite the importance of a positive relatiOn­ ship for the agents' effective execution of plans, not much has been made [Foulser et a/., 1991] to utilize this, ex­ cept to reduce costs by deleting the overlapping actions in a domain consisting of only one agent [Hayes, 1989] and for multi-agent systems where irrational agents dele­ gate and receive plans [Martial , 1992] and for multi-agent systems where agents mutually construct a collaborative plan [Osawa and Tokoro, 1991] .

· kei@mt.cs.keio.ac.jp

t mario@mt.cs.keio.ac.jp. Also affiliated with Sony Com­ puter Science Laboratory Inc.

In this paper we propose a collaboration mechanism by which rational agents can delegate and receive sub­ plans in a positive relationship so that t~e cost. of ex­ ecution is reduced. If an agent delegates Its actwns to the other agent , it can reduce the execution cost greatly and benefit from it . On the other hand, when an agent receives actions , the cost increases a little even though the reduction in the cost of the sender is larger than the gain in its own cost. As rational agents can delegate ac­ tions but may not be willing to receive, it is very ~ard to collaborate in a positive relationship. However, If an agent which receives actions is guaranteed to be ab.le to delegate some actions in the future, then even a ratwnal agent can collaborate in a positive relationship. We pro­ pose a mechanism based on a social law (the gu~antee) in which agents must balance the costs of received ac­ tions. With this mechanism, rational agents can collab­ orate through the expected cost based on game theory.

Moreover there are two other benefits arising from ' h ' this law: (1) just as agents ca.n ~xpect anot e~ agent s proposition (strategy) at negotiatiOn on delegatwn, they can avoid conflicts of strategies and can collaborate smoothly; and (2) the macroscopic problem that. arises when the load of the whole multi-agent system IS con­ centrated on an irrational agent can be solved with this microscopic cost-balancing law.

Although the image related to the bene~t of such a law is implicit in many AI works, the social law was only recently formalized and discussed [Shoham and ~en­ nenholtz, 1992] . However , this work does not consi?er agents which do not abide by the law . . w~en treatm.g a mult i-agent environment as an open distnbuted envi­ ronment, it is quite natural to think that such age~ts exist. Therefore, our mechanism considers collaboratiOn with self-centered agents. It is a very simple solution for agents to not collaborate with self-centered ag~nts . Nev­ ertheless , it is problematic that an agent which excep­ tionally did not abide by the law for some reason, cannot collaborate any more, and that agents could benefit by collaborating with the self-centered agents. Therefore, agents should collaborate in a more rational and flexible way: they collaborate if they can benefit and do not collaborate when they cannot. Our mechanism allows agents to collaborate in this way.

Simulation results show that with our mechanism, rational agents can reduce their cost by delegat­ ing/receiving actions. The results also show that the mechanism has the important properties of flexibility and guarantee cost-balancing.

The outline of the rest of the paper is as follows. In the next section, some of the assumptions are presented before discussion. Our mechanism is proposed in Sec­ tions 3 and 4. In Section 3, two evaluation functions are defined using the game theory. Also, the social law and the model of agents are described. In Section 4, the other part of our mechanism is described. In Section 5, some examples are presented. Experimental results are shown and discussed in sections 6 and 7, respectively.

2 Assumptions

Assumptions on the agents' plans and actions are as fol­ lows:

1. Each agent has a plan to achieve its own goal , and doesn't know the plans of other agents'.
2. Subplans (plans which achieve sub goals) consist of sequences of actions.
3. The meanings of actions and associated costs are predefined and common to all agents.

In order to concentrate on the algorithm of delega­ tion/reception decision, we assume the following:

1. Agents can find which parts (subplans) of their plan can be delegated.
2. Agents can discover other agents with which tone­ gotiate delegation.
3. Negotiation is carried out between two agents only.

Positive relationship that is implicitly contained be­ tween plans is divided into two relationships' [Martial, 1992]: a subsumption relationship and a favor relation­ ship.

If the actions of an agent's plan are the same or sub­ sume another agent 's actions, the plans are in a sub­ sumption relationship and one agent does not need to execute its plan if the other agent executes its own plan. If an agent 's plan partially overlaps with another agent's plan and is not in a subsumption relationship, the plans are in a favor relationship . In this case, an agent does not need to execute its plan if another agent is willing to receive the plan and to execute its own plan together with the non-overlapping part of the received plan.

Now, we assume the following 2 :

1. Agents collaborate when their plans are in a favor relationship .

1 Martial divided the relationships in more detail.

2 lt is not necessary for agents to collaborate in a subsump­ tion relationship because it is enough for an agent to check whether its actions were already done after execution of the other agent's plan.

3 Definitions

3.1 Change of cost by delegation

The change in agent A's subplan, which has a favor rela­ tionship to B's subplan and the associated cost through delegation/reception, is shown in Figure 1 where some actions are indicated as circles.

For instance, if a subplan of agent A (a) consists of three actions: "go to store" then "buy food" and finally "come back," and that of agent B consists of: "go to store" then "buy juice" and finally "come back," then the subplans are in a favor relationship (partly overlap­ ping) . If A receives the execution of B's subplan, the replanned sub plan (b) that A must execute is: "go to store" then "buy food" and "buy juice" (B's action) and finally "come back" and "hand B juice" (action to adjust A's initial plan) .

In order to express costs, we use the following nota­ tion:

• C,p(A) : A's cost for executing a subplan which has a favor relationship to B's subplan.
• Cdr(A) : The cost of A's actions when executed by B when delegated (e.g., "buy food").
• Cadj(A) : The cost of A's additional actions in the case of delegation/reception (e.g., "hand B juice").

If A receives the execution of B's actions, A's overall cost is the cost of its own actions (C,p(A)) plus the cost of the delegated actions from B (C,p(B)) and the cost of adjusting a plan to a new plan (Cadj(A)) .

On the other hand, if A delegates the execution of its subplan, the subplan will become (c) . In this case, A's overall cost is only the cost of adjusting a plan ( Cadj(A)) .

3.2 Social law for delegation

Social law is formalized in [Shoham and Tennenholtz, 1992] and is treated as the pair of actions and conditions about states that prohibit taking action. Intuitively, so­ cial law I is the law by which agents must balance the costs of the individual received actions.

Definition 1 (Social law for delegation) Social law I is defined to obey the next constraints.

• {a) If an agent receives more actions than the other agent, it cannot receive actions at the next negoti­ ation.
• (b) If an agent delegates more actions than the other agent, it cannot delegate actions at the next nego­ tiation.

When agents abide by this law, each agent can dele­ gate actions and benefits in the future according to (a), even if it receives actions and loses by that . Therefore, even a rational agent can propose the strategy "receive."

Though this law may not be the only one that makes agents collaborate on positive relationships, the search for such a law is beyond the scope of this paper. How­ ever, this law has the following two advantages: (1) as (a) and (b) are exclusive, agents can avoid the conflicts of strategies proposed in the negotiation, or collaborate smoothly, and (2) the microscopic law defined between two agents can balance the agents' costs of executing received actions in a whole system.

3.3 Expected payoff

We use payoff in game theory as the increase in cost aris­ ing when an agent proposes its strategy at negotiation and defines the expected payoff. The strate§Y consists of two propositions: "delegate" and "receive" . Therefore, agent A's strategy pis a mixed strategy (p1,p2) where P1 is A's probability of proposing strategy "delegate" and p2 = 1-p1 is that of the reception. Also, the other agent B proposes a mixed strategy q = ( q1, q2) expressing the same idea. Please note that the expected payoff is not the expected cost but the expected increase in cost .

Because of the existence of social law I, the strategy that is selected by A not only influences the strategy of B in the future, but also influences the cost of A in the future. Hence, the expected payoff is the sum of the expected payoff of current negotiation, present expected payoff(Ep(p, I)) and the negotiation in the future, future expected payoff (EF(P, 1)).

However, other agents (say, agent B) may not abide by the law. With the reliability of B (Pr(B)), i.e., the probability of B abiding by the law, the expected payoff, is defined as follows :

Definition 2 (Expected payoff of agent A)

where Ep(p,¢),EF(p,¢) is the value of Ep , EF when B does not abide by the law.

3.3.1 When the other agent abides by the law

If the other agent, B, abides by the law, A's payoff of current negotiation is expressed in the next payoff ma­ trix. Entries'-' (undefined) represent cases that cannot happen because both agents abide by the law.

3 There is also one other strategy: "do nothing," in which a.gents must execute the subplan for themselves. This strat­ egy is ta.ken when the expected payoff is not less than 0.

Also, A's payoff in the future is expressed in the same way. For example, if A proposes "receive" and B pro­ poses "delegate," A loses by receiving the actions of B. Nevertheless, in the future (or at the next negotiation), A's cost will be decreased -( -C.p(B) + Cadi( A)) as A can delegate its actions.

Therefore, Ep(p, I) and EF(P, I) are calculated by the following formulas:

3.3.2 When the other agent does not abide by the law

If the other agent does not abide by the law, both agents have the same strategies and conflict occurs. In such a case, we flip a coin to resolve conflict as will be mentioned in Section 4. Therefore, A's payoff will be Cadj(A) +(Cdr( B)- C.p(A))/2 regardless of whether A proposes "delegate" or "receive." That is because the payoff is dependent only on the flipping of a coin. How­ ever, a greater negotiation cost is needed to resolve con­ flicts because such resolution will need more communi­ cations for information. Agent must consider the cost Cneg· .

The payoff in the future is Cpenal, a cost that is de­ fined individually for each agent. Although Cpenal = 0 in general, if other laws exist that constrain the organi­ zation and the priority of agents, a collision of strategies will lead to high priority agents delegating more tasks to low. In such a case, we have Cpenal > 0.

Therefore, Ep(p, ¢)and EF(P, ¢)are calculated as fol­ lows:

3.4 The other agent's model

The behavior of the other agent, B, is modeled upon the following two points.

1. Strategy q = ( q1 , q2)

Before we define the other agent's strategy (q = (q1, q2)), we define ~(B), a relative amount of cost for executing received actions.

where Crec(i) is agent A's j-th cost of receiving a plan expressed as follows:

Then, the other agent's strategy is modeled as a function of ~(B) and the law I.

2. Reliability Pr(B)

This reliability means the probability of B abiding by the law. The reliability Pr at the n-th negotia­ tion of the delegation is defined as a function of hn, which is calculated by the last model of strategy qm and the actual, previous strategy of B, q' = (qL q~).

where h1(B) =a and the values of a,f] are defined for each agent 4 .

4 Negotiation Process

Based on the functions defined in Section 3, the negotia­ tion process is described below. As mentioned in Section 2, we assume that steps 1 and 2 are available.

1. Search for a subplan to delegate.

The agent searches for a subplan which can be del­ egated to another agent.

2. Search for an agent to which the subplan can be delegated.

The agent proposes a subplan to delegate and searches for an agent which can participate in the negotiation of delegation.

3. Decision on strategy

After receiving the subplan, the agent decides on the strategy which minimizes the expected pay­ off E(p, q, P,(B)) based on reliability P,(B) and B's strategy model q (which is obtained by q = s(~(B), l) according to the relative amount of costs for B (~(B)) and social law /). If, for all p, E(p, q, P,(B)) ~ 0, the agent executes the subplans by itself (and doesn't delegate them) and proposes "do nothing".

4. Proposition of strategy

Both agents propose their strategies to each other, including "do nothing."

5. Decision of behavior

The agent decides its behavior according to the other agent's strategy.

(a) If strategies do not conflict

They modify their plans according to the strategy.

(b) If strategies conflict

They decide which agents delegate and re­ ceive the actions by flipping a coin. However, if one of the strategies is "do nothing," the agreement is to "do nothing".

5 Example

As an example, we consider a negotiation where agent A and B have subplans consisting of three actions. The cost of agent A's subplan is 8,3,8, the cost of B's subplan is 7,4,7, and a= 5 and (3 = 0.14 for both agents.

We explain our mechanism based on this example.

4 These parameters can express the characteristics of the agent .

1 and 2.

As agent A can find a sub plan to delegate and agent B with which to negotiate the delegation/reception, A knows the change in its subplan (Figure 2) . Numbers in circles express costs. Therefore, C1p(A) = 8+3+8= 19, Cdr( A)= 3, C1p( B)= 7 +4+ 7= 18, Cdr( B) = 4. For simplicity, Cadj = Cneg = Cpenal = 0

1. According to the costs, the following present and future expected payoffs are obtained. Also, P1(B) is obtained by h1(B) =a= 5,f] = 0.14.

Ep(p, l) = 4p2q1 - 19p1 q2

EF(P, l) = -18p2q1 + 3p1q2

Ep(p,¢) = (4-19)/2

EF(P, ¢) = 0

As q = (q1, q2) = (1/2, 1/2) according to ~(B)= 0, the expected payoff, E(p, l, P,), is the following:

. The strategy which minimizes this is p = (1, 0).

1. Also, as agent B gets E(q, l, P,(A)) = ( -4q2 - 3.5qt)- 3.75, B proposes minimizing strategy q = (0, 1) .
2. As the strategies do not conflict , there is no need for more negotiation. The agents just modify their own plans according to the proposed strategy.

In this way, the first decision about delega­ tion/reception has finished. We will explain the second decision. For simplicity, the conditions are the same as before and we focus on the decision part of our mecha­ msm.

We get q = (1 , 0) according to ~(B) = -3, the present and future expected costs are obtained as the following. Also, P,(B) = 1 - e.xp( -6 · 0.14) = 0.57 is obtained by h2( B) = 6.

The expected payoff E(p, l, P,(B)) is the following:

The strategy which minimizes this is p = (0, 1).

As B gets E(q, l , P,(A)) = -7.98q1- 3.2, B proposes strategy q = (1, 0) . Then, the strategies do not conflict and no more negotiation is required.

6 Simulation

We simulated the execution of an agent using our mech­ anism as proposed in Sections 3 and 4 in the cases where it negotiates with various agents. We used parameters a = 15 and (3 = 0.07 for both agents, and used com­ pletely overlapping plans. The cost of the execution of each part of the plan was simulated according to table 3.

The costs for agent B are taken for the same table with B replacing A. However, the cost of the subplan (25-30) and the cost of the delegated part of the plan (5-12) was randomly selected and was not necessarily common to both agents. The results are the average of 5000 simu­ lations.

6.1 Reduction of cost

Figure 3 shows the relation between the cost for exe­ cuting a subplan and the frequency of negotiation for delegation.

Number of

delegatioD&

Curves in the figures are the result of the next condi­ tions ( C neg = 2 except for (iii b)).

• (i) B does not exist (agent A has to execute the actions alone).
• (ii) B uses our mechanism.
• (iii a) B is self-centered (B's strategy is only "dele­ gate")
• (iii b) B is self-centered (Cneg = 4) .
• (iv) B is the same as (iii a) till the 30-th negotia­ tion, after then, it is the same as (ii).

Although the cost doesn't decrease when agent A ex­ ecutes the actions alone (i), A can reduce the cost when the other agent uses our mechanism (ii). When the other agent is self-centered (iii), the cost is at first a little bit more than when the other agent uses our mechanism from the start . This is caused by a decision made by both flipping a coin when strategies collide and usage of the "do nothing" strategy when A cannot benefit from it. However, when the delegation precedes with Cneg = 4 (a cost-consuming negotiation), as the agent using our mechanism does not come to collaborate with the self­ centered agent, the cost approaches the cost of (i) . When negotiation is not cost-consuming ( C neg = 2), the agent continues to collaborate with the self-centered agent, be­ cause it can reduce its cost more than when doing it alone (i) but less than when in situation (ii).

In the case where the other agent changes its mind and decides to use our mechanism rather than being self-centered (iv), the same result obtained for the self­ centered agent is obtained at first. If the other agent has decided to use our mechanism, it returns the benefit obtained up till then in order to balance the individual received cost . Therefore, the cost is extremely reduced at that time, and approaches the cost of (ii).

Furthermore, we simulated the case when a and {3 are different from 15 and 0.07. With a less than 15, result (iii) presents the largest change among all simula­ tions. The agent decides not to collaborate with the self­ centered agent earlier. If {3 is greater than 0.07, result (iv) represents the largest change. The cost when the other agent has come to use our mechanism is smaller. The reason for this is that as {3 larger, P,(B) larger so that the agent comes to collaborate earlier on the social law. But if P,(B) is smaller, the agent will propose the "do nothing" strategy so that the "delegate" strategy would be less used and the cost is not reduced.

6.2 Cost balancing of received actions

Figure 4 shows the received cost of both agents. Curves (ii)-(iv) in the figure are the same conditions as before.

When both agents use our mechanism (ii), the costs received are balanced. When the other agent is self­ centered (iii), the agent receives too many actions be­ cause of the flexibility of the mechanism. However, this loss cannot continue to increase because A does not get to participate in the negotiation on delegation if A thinks that it cannot benefit from it. Also, in the case of the self-centered agent which changes its mind and decides to use our mechanism in the course of negotiation, the received costs are finally balanced (iv).

7 Discussion

We discuss some issues related to our mechanism.

The social law which guarantees that an agent can delegate its actions in the future even if it receives the actions of another agent, not only enables rational agents to reduce their cost by collaborating, but also enables our mechanism to have two important properties: a guaran­ tee of balanced costs for individually received actions and an avoidance of conflicts in strategies.

As our microscopic law, defined between two agents, enables the agents to balance the received costs between them so that the costs are macroscopically balanced in a whole multi-agent system. With this law, an irrational agent that may receive too many actions would not be a bottleneck of the whole system if other agents that delegated tasks to it waited until they finished.

With agents A and B abiding to this law, if A receives more than B (~(B) < 0, ~(A) > 0), A proposes "dele­ gate" and B proposes "receive." Therefore, the strate­ gies do not conflict, so that agents can easily reach an agreement . In [Shoham and Tennenholtz, 1992], social law is used to constrain actions to avoid conflicts. It became unnecessary for agents to negotiate for conflict resolution. However, agents must negotiate to exchange information about plans when they collaborate in a pos­ itive relationship. Our mechanism used the law to con­ strain the strategy of negotiation so as to avoid conflict .

Moreover, we considered self-centered agents, or agents that do not abide by the law. This is a case which is not considered in [Shoham and Tennenholtz , 1992] . It is very simple for agents not to collaborate with self-centered agents after they realize what kind of agents they are dealing with. However, it is problemati­ cal that an agent which exceptionally does not abide by the law for some reason, cannot collaborate any more. Also, problematical is the fact that agents do not col­ laborate with self-centered agents even when benefit can be obtained. Our mechanism is flexible: reliability Pt is gradually decreased every time the strategies conflict, so that the chance to collaborate with a real self-centered agent is decreased and agents collaborate only if they can benefit from it . However, agents with our mecha­ nism may receive a little more action than a self-centered agent because of this flexibility.

Here, we consider the situation where the bank and post office are in the same direction and both agents plan to go to both places. Because their plans are "go to bank" and "go to post office" and "return," the re­ sulting plan of our mechanism is that one agent goes to both places. Nevertheless , if the places are in different directions, the resulting plans are that each agent goes to a different place. The latter result is obtained through two negotiations because their plans are "go to bank" and "return" and "go to post office" and "return." Our mechanism also provides such an optimal solution.

In [Zlotkin and Rosenschein, 1990], flipping a coin is used to resolve conflicts , but the purpose for our work is to avoid conflict. Since the mentioned work is designed for collaboration in negative relationships, the conflict in goals must be resolved. On the other hand, as our work is directed to positive relationships, the conflicts are not necessarily resolved (in this case, agents cannot reduce costs).

In a related piece of research [Martial, 1992], the pro­ posed algorithm focuses on the optimization of plans of agents. Therefore, agents are willing to receive the ac­ tions even if they cannot benefit from them, and the received costs would not be balanced. Our mechanism does not require such irrational agents; each agent can rationally and flexibly select its own strategies.

8 Conclusion

The utilization of positive relationships has not received much attention in DAI. We proposed a mechanism using a social law by which rational agents can reduce the cost of their execution by delegating and receiving actions. With this law, agents can avoid conflicts of strategies in a negotiation and reach an agreement easily. Fur­ thermore, we considered the case in which agents do not abide by the law (self-centered agents) and the case in which agents that are self-centered at first come to abide by the law eventually. Simulation results show that by using our mechanism, rational and flexible collaboration is possible with these kinds of agents.

We intend to use a more complex model of agents, and consider communication costs and collaboration with multiple agents by introducing market mechanisms. Also, we will introduce a mechanism based on incom­ plete information for more detail, as stated in [Kakehi and Tokoro, !'993].

Acknowledgments

We would like to thank T. Hirotsu, R. Kakehi, V. Vas­ concelos and I. Satoh for their helpful comments.