Persuasion among Agents: An Approach to Implementing a Group Decision System Based on Multi-Agent Negotiation

1 Introduction

Group decision support systems (GDSSs) [Desanctis and Gallupe, 1987] are being investigated very actively in the field of operations research. The GDSS aims to improve the process of group decision-making by removing com­ mon communication barriers, providing techniques for structuring decision analysis, and systematically direct­ ing the pattern, t iming or content of discussions.

We can classify GDSSs into three types according to their approach to supporting a group. Type 1 GDSSs improve the decision process by facilitating the exchange of information among members. Type 2 GDSSs provide decision-modeling and group-decision techniques aimed at reducing the uncertainty and noise that occur in the group's decision process. Type 3 GDSSs are character­ ized by machine-induced group communication support and often provide expert advice in the selection and ar­ rangement of rules to be applied during a meeting. If we introduce Artificial Intelligence (AI) methods into the Type 3 GDSSs, we can expect to further enhance the intelligence of their support. For this reason, and in keeping with the current high expectations for effec­ t ive GDSSs, we here implement a Type 3 GDSS using intelligent agents.

The term agent, used in a variety of ways, has recently commanded much attention in the field of AI. For pur­ pose of this paper, an agent can act autonomously and cooperatively in a network environment on behalf of its users. Agents have many crucial functors, one of the im­ portant being the attainment of consensus. Reaching a consensus also is a group decision process that should be supported by the Type 3 GDSS.

Agent negotiation for group decision support has been studied widely. In particular, multi-agent meet­ ing scheduling [Ephrati et al., 1994; Garrido and Sycara, 1996; Sen and Durfee, 1994] has been a ·current topic of research. [Sen and Durfee, 1994] has been focused on solving meeting scheduling problem using a central host agent. However, user preferences are not taken into account. [Ephrati et al., 1994] presented an alternative approach which is economic in flavor. They introduced the Clark Tax Mechanism as a method for removing ma­ nipulability from agents. [Garrido and Sycara, 1996] has been focused on decenterized meeting scheduling with user preferences taking into account. They did not, how­ ever, establish how to measure the subjective judgements of users. In this paper, in order to measure the judge­ ments of users, we employ the Analytic Hierarchy Pro­ cess (AHP) [Saaty, 1980].

In general, a group reaches consensus by use of a vote. But the result of voting are often inconsistent, largely due to the inconsistency of voting rules: Ma­ jority Rule, Single Voting Rule, etc. Arrow's impossi­ bility theorem has shown that no voting method exists which satisfies all of the following four conditions: posi­ tive association of social and individual values, indepen­ dence of irrelevant alternatives, citizen's sovereignty and no-dictatorship[Luce and Raiffa, 1985]. In this paper we propose a persuasion mechanism[Ito and Shintani, 1996a; 1996b] rather than voting methods for negotia­ tion among agents.

In agent negotiation, the persuasion mechanism can be defined as follows. When agent A persuades agent B, agent ~ sends a persuasion message to agent B. Then, acc_ordmg to the message, agent B tries to change its beh~f. ~f agent B is able to change its belief, the per­ ~uasw~ IS a success. However, if agent B cannot change Its behef, the persuasion is a failure. A concrete method for implementing the persuasion mechanism is given in section 3.3.

Our agents are known as software agents [Kautz et al. 1994]. Their activities include carrying out tasks on be~ half of their users, making suggestions to their users and so on. Reliability and the ability to depute are i~por­ tant qualities of the software agents. It can be said that our agents have a high ability to depute users, since our agents negotiate with each other by use of the persuasion mechanism on behalf of users. In addition, our agents have an explanation mechanism. They can explain to their users why they have been persuaded, when they are persuaded, who persuaded them and how they are persuaded by use of graphical user interface. Because of their explanation mechanism, our agents are more reli­ able.

The aim of this paper is to present the persuasion mechanism among agents and to implement a Group Choice Design Support System (GCDSS) based on the persuasion mechanism. The paper consists of five sec­ tions. In section 2, we show the architecture of our sys­ tem and the process of supporting a group decision. In section 3, we present an agent mechanism for our system. Our agent has a management mechanism for the user's hierarchy of AHP, a persuasion mechanism for negotiat­ ing with other agents, and an explanation mechanism for their reliability. In section 4, we show an implementa­ tion of the GCDSS using the persuasion mechanism and discuss the results of our current experiments. Some concluding remarks are presented in section 5.

2 Group Choice Design Support System

2.1 System Architecture

Figure 1 shows the architecture of our system. In our sys-

tern, users' computers are connected by a network. Each user's decision-making is supported by their own hierar­ chical decision support module in our system. Agents manage their particular user's hierarchical decision sup­ port module, and negotiate based on the information it supplies. The agent's tasks are described in section 3. The hierarchical decision support module has functions to help generate alternatives, to make judgements for pairwise comparisons, and to construct a hierarchy. In order to lighten users' work load, we realize these func­ tions using graphical user interfaces.

The process for supporting group decision-making in our system is described as follows: First, a host user proposes a topic to be decided. Second, users make and choose alternatives from alternative database they sha:e. In order to get alternatives, users can employ a vanety of methods, e.g., brainstorming. These methods are provided by the hierarchical decision support mod­ ule. Third, each user constructs a decision hierarchy for AHP using the module. The hierarchy clarifies elements which should be considered in the decision making pro­ cess. The module is used to quantify subjective judge­ ments of decision makers by using AHP based pairwise comparisons. Fourth, agents negotiate with each other based on their users' subjective weights and decision hi­ erarchy. Negotiation among agents is based on the per­ suasion mechanism described in section 3.2. Finally, the result of the negotiation is reported to all users.

2.2 Quantifying Subjective Judgements

In order to measure subjective judgements of users, we employ AHP in our system. The AHP is a method for making _decisions that are hard to analyze quantitatively. It combmes both systems approach and subjective judge­ ments, and its primary purpose is to maximize the user's intuition and experience.

In the AHP, users decompose the problem into a hi­ erarchy that consists of a goal, criteria (and possibly sub-criteria), and alternatives. The judgement of the pai~wise comparison between factors (in Figure 2, alter­ natives AI ,A2 and A3 ) on a certain level is made with respect to the criterion that is a factor (in Figure 2, cri­ tenon C1) on the upper level. By interpreting a set of values of judgements as a matrix (top left of Figure 2) , the weights (i.e., measurement of criteria) of factors are calculated analytically. To put it more concretely, we can achieve the weights of each factor as the eigen-vector for the max eigen-value of the pairwise comparison matrix. As a whole hierarchy, the weights of the alternatives can be calculated by composing the weights of the criteria.

A pairwise comparison matrix is characterized by the following: (1) diagonal values are 1; and (2) the values of elements in a matrix are aii = 1/aii· For judgements of pairwise comparisons in the AHP, we can use a 9 point scale consisting of five words (equally, slightly, strongly, very-strongly and extremely (Figure 3)) and four inter­ mediate levels (e.g., between slightly and strongly)

AHP provides a measure the inconsistency in each set of judgements. This measure is called the incon­ sistency ratio (I.R.) and is defined as follows: I.R. = (Ama:z:- n)/(n- 1). Here, Amaxis the max eigen-value described above and n is the size of the pairwise compar­ ison matrix. Ideally, a set of judgements in a pairwise comparison matrix will be consistent, and the inconsis­ tency ratio will be 0. If the inconsistency ratio is no more than 0.1, this means that the pairwise comparison matrix is consistent.

In general, relative judgements are easier for users to make than absolute judgements. In the AHP, in order to lighten their work load, users can make comparisons be­ tween criteria using verbal and fuzzy expressions. Thus, the value of a pairwise comparison in the AHP is not a strict expression of a user's subjective judgement, but rather a rough approximation of that judgement. In our system, it may safely be assumed that a user's subjective judgement expresses 2 intervals with a certain value as the center point of the intervals on the 9 point scale (Fig­ ure 3) . An interval is an unit of the 9 point scale. For example, while in the AHP the verbal expression "Very Strongly Important" means the value of 7 internally, in our system it means the values 6, 7, or 8.

In addition, we propose the expressions fixed and as­ sumed to describe a user's belief in a judgement of pair­ wise comparison. For example, if the judgement is la­ beled fixed by the user, this means that the judgement value itself is fixed (i.e., the value is reliable). On the other hand, if the judgement is labeled assumed by the user, this means that the judgement value is also as­ sumed (i.e., the value is unreliable). If an agent is per­ suaded in negotiation, the agent tries to adjust assumed judgements within 2 intervals in order to change the weights of the alternatives. These adjustments are made under the constraint of I.R. less than 0.1.

2.3 Public and Private Decision Hierarchy

In general, the AHP is employed in the common objec­ tive context (all users have the same objectives)[Dyer and Forman, 1992]. In this context, users decide one de­ cision hierarchy among them first, then each user judges pairwise comparisons individually based on the decision hierarchy. In this case, because all users have the same objectives , i.e., criteria, the existing systems support users to construct only one decision hierarchy and to judge pairwise comparisons. On the other hand, our sys­ tem supports group decision-making in the non-common objective context (each user has non-shared and some­ times hidden objectives). In the non-common objective context, it is difficult to construct a decision hierarchy among users, because the users have non-shared and hid­ den objectives (i.e., criteria) . In our system, each user may construct a decision hierarchy individually. How­ ever, when there are same criteria among users, if the users can notice this fact, each can construct a decision hierarchy more effectively. Therefore, in our system, a decision hierarchy has public parts and private parts in order to make an effective group decision. The public parts can be referenced by all users. The private parts are hidden from other users. In the concrete system, the whole decision hierarchy is basically public. Individual users can designate as public or private each new criteria they create. The goal and alternatives must be public.

3 Agent's Behavior

3.1 Reducing the Pairwise Comparisons

Each agent manages the decision hierarchy and the pair­ wise comparison matrix constructed by its user. In gen­ eral, the AHP requires too many judgements of its user. If there are n factors for a criterion, users have to make n(n- 1)/2 judgements. If the number of levels of the decision hierarchy or the number of factors of the level is increased, more and more judgements are required. Acting on the user's behalf, the user's agent effectively reduces the number of judgements, which leads the user to make consistent judgements dynamically using the fol­ lowing methods.

In general, users have to judge all pairwise compar­ isons in the AHP. In fact, it is very hard for a user to judge all pairwise comparisons. In our system, the initial value of the elements of all pairwise comparison matrixes is 1 (i.e., "Equally Important" ) as an assumed value. Be­ cause there are initial values, the user changes only the value that the user wants to judge.

In the AHP, the value of an element aii in the ma­ trix equals Wi/Wi. Here, the Wi expresses the weight of the factor i. If a pairwise comparison matrix is con­ sistent (i.e., I.R. = 0), a certain element can be inferred from the other two elements. For example, in a matrix, because the value of an element a12 is W1 /W2 and the value of an element a23 is W2/W3, we can infer that the value of an element a13 is a12 X a23 = wl /W2 X w2 /W3 = Wl/W3 · In the system, in order to reduce the number of judgements, agents infer the value of an element in a ma­ trix using this feature of the AHP. When the agent infers the value of an element, if the element was judged by the user , the agent asks the user to change the judgement. If the element has never been judged, the agent changes the value of the element to the new value inferred. In this case, the new value is labeled as assumed. In gen­ eral, in order to reduce the number of judgements, the Harker Method [Harker, 1987] is now widely employed. However, to use the Harker method, the covering condi­ tion must be satisfied on a matrix. In order to satisfy the covering condition, many judgements, from which all elements in the matrix must be inferred, are required. In a real system, it is also hard for the user to make judge­ ments with the covering condition. If the user has a chance to satisfy the covering condition, the system ex­ ploits the Harker method instead of the simple method mentioned above to omit some redundant pairwise com­ parisons and check the consistency of each comparison dynamically. In a pairwise comparison matrix, when the value of I .R. is more than 0.1, this means that the matrix is inconsistent and the user must remake all the judge­ ments. Naturally, this remaking creates additional work load for the user. In our system, while the user is making judgements in a matrix, the agent is watching the I .R. dynamically. When the I.R. is more than 0.1, the agent requests that the user remake the present judgement.

3.2 The Persuasion Process

In the. system, a negotiation among agents consists of persuasions between two agents. Figure 4 shows an ex-

ample of negotiation among agents a, b, c, d, and e in the system. First, agents pair-off into groups: agents a and b make a group and agents c and d make a group. Next, within each group one agent who selected randomly per­ suades the other. In Figure 4, agent a persuades agent b and agent c persuades agent d. If these individual persuasions succeed, the persuading agents assume the representation of their respective groups. In Figure 4, each persuasion succeeds, and agent a and agent c are representative of their groups. If the persuasions had failed, the agents would change places. For example, if the agent a failed to persuade the agent b, the agent b persuades the agent a next time. The groups are now a, b and c, d, and the representatives advance to negoti­ ate with each other singly. During negotiation between agents a, c, and e, agent a persuades agent e. So that the groups become a, b, e and c, d. Finally, agent c persuades agent a, and the agents reach a consensus.

Figure 5 shows the process of persuasion between two agents. Suppose that agent a1 and agent a2 are in a group and agent a1 persuades agent a2 . First, agent a1 sends a persuasion message to agent a2 . The persuasion message is the most preferable alternative that has the highest weight and is decided by agent a1 's user with the AHP. Secondly, agent a2 accepts or rejects this message according to the following process.

First, agent a2 checks whether its own most prefer­ able alternative is the same as that in the persuasion message. If this alternative is mutual, the agent a2 ac­ cepts the persuasion message and this persuasion is a success. If not, agent a2 does not accept the message and the persuasion process advances to the next step.

Second, agent a2 tries to change the preference order of alternatives by adjusting the judgements of matrixes in the decision hierarchy. Figure 6 shows an example. The top and bottom halves of Figure 6 show, respectively, the hierarchy before and after adjustment. In the top half of the figure, alternative A1 is more preferable than alternative A2 or A3 . Now, suppose that agent a1 pro­ poses alternative A3 as the persuasion message. Agent a2 tries to adjust the judgements in order to change the preference order so that alternative A2 is more preferable than alternative A1 .

The agents adjust the judgements in a matrix by em­ ploying the following method. From the feature of the AHP, in order to increase the weight of the alternative h we increase the value of elements at ith row except a diagonal element. In the system, the agents increase the value of assumed elements of ith row of the matrix ex­ cept a diagonal element within 2 intervals of the 9 point scale, in order to increase the weight of alternative l; and change the preference order of the alternatives. Fig­ ure 7 shows an example of such an adjustment. Suppose that all elements of the matrix are labeled assumed, and agent a2 wants to increase the weight of alternative A2. In this case, agent a2 increases 1 interval of the value of elements (i.e., judgements) on alternative A2 against the alternative A1 and A3 . By this adjustment, alternative A2 becomes most preferable. Agent a2 asks the user for permission to change the weights in practice. If the user permits, agent a2 changes the judgements. If not, agent a2 tries to adjust again.

Third, agent a2 checks whether the persuasion mes­ sage can be accepted using his new preference order. If the persuasion message can be accepted, this persuasion is a success. If not, this persuasion is a failure .

Fourth, the agent asks the user to change his or her judgements. If the user agrees, agent a2 indicates which judgement the user should change.

Fifth, agent a2 again checks whether or not the per­ suasion message can be accepted.

Note that the reliability of the system is best enhanced by the persuasion mechanism's second and fourth steps.

3.3 Reliability

The reliability is an important factor to implement a software agent. The agent briefs its users on the de­ tails of negotiation via graphical user interface during negotiation. The agent explains which agents persuaded, which element in a matrix should be changed, which group the agents participated in at the time, and so on. This explanation mechanism renders the agents more re­ liable.

4 An Example and Discussion

As an experiment, we used the system to choose a new computer for our laboratory. The number of members in our laboratory is 12, and each research group has dif­ ferent objectives. Therefore, the group decision-making context was a non-common objective context. The com­ mon objectives (i.e., criteria) were writing papers, pro­ gramming, and so on. The non-common objectives were playing games, music, and so on.

Figure 8 shows an example of the persuasion mecha­ nism of the system. Here, the agent received an alternative "PM7100" as a persuasion message. Then, the agent adjusted judgements and proposed the new judgements by showing the window at the bottom right of Figure 8. This shows the agent's explanation in the process of a persuasion. The agent asks the user's permission to change particular judgements. The user agrees by push­ ing the OK button, or disagrees by pushing the NO but­ ton. The top right window in Figure 8 gives a detailed explanation.

These experiments have yielded some interesting re­ sults that merit discussion. A consensus is sometimes disturbed by the user who makes arbitrary judgements. To deal with such cases, we must consider the following. (1) In the AHP, we generally make decisions construc­ tively. For this reason, arbitrary judgements should be prohibited. This idea can be applied to many cases of group decision making, but it also restricts the user's judgements. (2) An arbitrary judgement can be regarded as an opinion of the user. In this case, it will be worth reaching a consensus among a sub group that excludes this user. In addition, this idea can be applied to cases in which a group does not need consensus among all members. For example, in deciding the destination for a trip, we do not require consensus among all members. We can assume that the member who makes arbitrary judgements does not want to go on the trip, and can thus be disincluded.

Finally, the necessity of the explanation mechanism, particularly with regard to the persuasion mechanism, should be discussed. The successful persuasion of an agent requires the compliance of that agent's user. At first, we implemented a system in which the users were removed from the negotiation of their agents. In this case, we found that even if the users knew the system architecture and the process of agent negotiation in ad­ vance, the users who were persuaded were not satisfied. In other words, the reliability of agents is an important factor in realizing a multi-agent system. For this reason, in our system, as we have propl)sed in section 3.3, each agent explains to the user the details of the negotiation, in order to gain the user's consent and make agents more reliable.

5 Conclusion

In this paper, we proposed a persuasion mechanism among agents and implemented a group decision sup­ port system GCDSS to see how effectively the persua­ sion mechanism can be used. The GCDSS helps a group decision to make a reasonable choice from alternatives. We found useful characteristics of AHP for multi-agent based group decision support systems. The characteris­ tics are as follows. (1) We can quantify the subjective judgements of users by using AHP. Agents negotiate ef­ fectively based on the subjective judgements quantified. (2) The verbal and fuzzy measurement of AHP enables us to realize the persuasion protocol. Agents can adjust the decision hierarchy of their users. The results of our current experiments demonstrated that the persuasion protocol is a suitable method for reaching a consensus among agents in group decision support systems.