MULTI-AGENT GRAPHICAL DECISION MODELS IN MEDICINE

Abstract

Many practical applications in the medical domain require a cooperative decision with multiple entities (agents). These applications are instances of a multi-agent decision problem. This complex decision problem often concerns a large knowledge domain and involves some agency properties. It disables traditional methods on probabilistic graphical decision models. In this article, we propose a new representation including multiply sectioned influence diagrams (MSIDs) and hyper relevance graphs (HRGs). An MSID represents decision problems involving multiple agents in a distributed and flexible fashion, while an HRG encodes organizational relationships in a multi-agent system. Subsequently, a symbolic method is extended to facilitate the model verification with the aim of building a valid decision model. An evaluation algorithm based on the junction tree algorithm is developed to solve an MSID. Some relevant evaluation strategies are analyzed. The decision problem on the Severe Acute Respiratory Syndrome (SARS) control is illustrated with our proposed methodologies throughout this article.

Severe Acute Respiratory Syndrome (SARS) is a serious infectious disease that could potentially develop into an epidemic or even an endemic. Its uncertain and various sources have frustrated the medical community and policymakers. Its outbreak causes unexpected loss everywhere in the world. Beyond all doubt, to relieve this loss needs a collaborative effort of multiple nations concerning their own local as well as global benefits.

The decision problem on SARS involves many nations or communities, even those without the outbreak of SARS. These involved nations are collectively seeking good solutions to control SARS in the whole community in order to avoid more loss. This kind of decision problem is a distributed one involving multiple agents. It is referred to as a multi-agent decision problem in this article. Some characters of this decision scenario as follows: 1) Agents are distributed geographically or physically. Each nation or community is an independent entity in the world. It is not easy and reasonable to merge them into a single object. 2) Agents are cooperative. Although an agent is an independent entity, it still needs cooperation for solving a certain decision problem. The cooperation is based on public information they share. In the above decision scenario, these nations would share some valuable information such as the available SARS reports. 3) Agents' privacy is protected. Although agents are in a cooperative setting, they intend to retain their privacy. For example, the involved nations could not release all of their own information such as their hospital facilities. 4) Agents' decisions and observations are interleaved; however, their interactions follow a sequential order. In a distributed environment, agents need some observations from their adjacent agents to support the decision-making. For instance, in the decision scenario previously mentioned, a nation needs to be informed of the SARS report from its adjacent nation in order to adopt some actions. 5) Agent's organizational relationships exist. In a cooperative decision problem, an agent may need requisite information for its decision-making while this information could be only obtained from its adjacent agents. Hence, a certain organizational relationship exists among these agents. Meanwhile, this kind of organizational relationship could be described by the relation between the information and the supported decisions. 6) Agents seek their individual objectives while they expect a cooperative solution. In a distributed decision problem, every agent has its own goal since it is selfish. It wants to make the best decision on its own through the cooperation in which it could access some requisite information. For a cooperative solution globally, agents contribute by releasing the honest and up-to-date information by which they wish to help decision-making in their adjacent agents. Hence, in this kind of decision scenario, what cooperative agents are concerned with is the shared information. They are unwilling to compromise their own utility with the consideration of others' decision-making. Intuitively, a multi-agent decision problem always relates to a large knowledge domain since it concerns a complex decision problem involving multiple agents. The aim of this article is to represent and solve this kind of decision problem. The potential approach for solving multi-agent decision problems should extend traditional graphical decision models as well as exploit characteristics of multiple agents.

The aforementioned decision scenario could not be solved using traditional methods on probabilistic graphical decision models such as influence diagrams (Howard and Matheson 1984). These mature model representations were originally developed to solve decision problems for the single agent paradigm. Much formalism has also been proposed to cope with some special decision problems, such as the dynamic influence diagrams (Tatman and Shachter 1990), the time-critical dynamic influence diagrams (Xiang and Poh 1999), the unconstrained influence diagrams (Jensen and Vomlelova 2002), and the sequential influence diagrams (Jensen, Nielsen, and Shenoy 2004). The dynamic influence diagrams and time-critical dynamic influence diagrams emphasize the solving of decision problems encoding time series through concise representations. The unconstrained influence diagrams and sequential influence diagrams try to solve asymmetric decision problems by relaxing usual constraints of influence diagrams. However, this work was not aimed at the multi-agent decision problem until the framework of the multi-agent influence diagrams (MAID) (Koller and Milch 2001) was initiated to represent and solve a game problem. Extending from a single agent-based influence diagram, the MAID still lacks the ability to deal with a large knowledge domain and overlooks some agency features. Furthermore, the situation we intend to address involves decision problems for every interacted agent which has obtained beneficial information from its adjacent agents in a distributed and unpredictable environment. This situation is quite different from games; hence, many methodologies in decision theory could be utilized. Recently, some progresses (Xiang 2002; Gmytrasiewicz 2003; Portinale, Magro, and Torasso 2004) have been made on the multi-agent reasoning system. They focus on reasoning and planning involving multiple agents; however, they do not consider agents' decision-making. Hence, a piece of new work is required to address the multi-agent decision problem.

In this article, we propose a new framework of multiply sectioned influence diagrams (MSIDs) and hyper relevance graphs (HRGs) to solve a multi-agent decision problem. An MSID encodes agency features and represents a large and complex decision problem with the divide and conquer strategy. An HRG, on the other hand, spells out various organizational relationships that bind multiple agents in an organization evolving over time. They are interrelated to provide a reliable and compact framework. Accordingly, the MSID and HRG together are a reusable and coherent framework that can be utilized to address a general decision problem.

Methods for the verification of models built on MSID and HRG are discussed and illustrated in this article. The symbolic verification method extending our past work (Zeng and Poh 2003) is proposed. Furthermore, an indirect method to evaluate an MSID is formulated when an MSID is transformed into a multiple rooted cluster tree. The relevant evaluation strategies are also analyzed.

This article is organized as follows. Firstly, we propose the representation of MSID and HRG, Then, the issue of model verification on MSID and HRG is illustrated. After that, we discuss an indirect method to evaluate an MSID. Finally, we conclude the article with some possible applications of our proposed methodologies and some remarks about future work.

GRAPHICAL REPRESENTATION

In this section, a new representation will be proposed to address the multi-agent decision problem. As a prelude to this major discussion, a concise review on some basic concepts of graphical decision models is provided in the preceding parts of this section.

Basic Concepts

Influence diagram (Howard and Matheson 1984) is a basic probabilistic graphical decision model for representing the single-agent decision-making in an uncertain environment. It is composed of chance nodes, decision nodes, and value nodes all of which together represent a decision scenario in a directed acyclic graph (DAG). In influence diagrams, chance nodes describe agent's observations, including both agent's knowledge on its environment and agent's beliefs on its interacting entities; decision nodes represent agents' decision alternatives and value nodes specify an agent's utility function.

Recently, much of the research work (Nielsen 2001; Shachter 1998, 1999) on graphical decision models is concerned with such a kind of problem: what is the required information for the decision-making in influence diagrams? To answer this question, firstly, two types of chance nodes, called requisite probability node and requisite observation node, are defined (Shachter 1998, 1999). The requisite probability nodes for a particular decision are those nodes whose (conditional) probability distributions might be needed to evaluate the decision problem starting with that decision. The requisite observation nodes for a particular decision are those nodes that should be observed before the decision in order to evaluate the decision problem starting with that decision. Secondly, the procedure Decision Bayes-ball (Shachter 1998, 1999) was proposed to identify this requisite information in influence diagrams. The procedure Decision Bayes-ball utilizes the concept of D-separation (Pearl 1988) to determine whether Bayes-ball bounces back or passes through the way when it meets different types of nodes in different directions from which the Bayes-ball comes. Later, an outstanding piece of research work (Nielsen 2001) tries to refine the procedure Decision Bayes-ball to obtain a minimal set of information being required for a particular decision. It first specifies the relevant utility functions for a particular decision node. Then it detects required nodes for this decision node using some rules based on D-separation. We shall refer to this new procedure as refined Decision Bayes-ball. (In the succeeding context, the Decision Bayes-ball procedure will be used to denote both the basic Decision Bayes-ball procedure and the refined Decision Bayes-ball procedure.)

Figure 1 shows an example of influence diagrams. The influence diagram represents an uncertain decision problem involving a single agent. It consists of a single decision node d, a set of chance nodes {a, b, c, e}, and a single value node v. Through the procedure Decision Bayes-ball, it is found that node e and node b are a requisite probability node and a requisite observation node for decision node d, respectively. Thus, these two nodes compose the requisite information for decision d in this decision problem.

FIGURE 1 An example of influence diagrams.

In a multi-agent decision problem, multiple agents cooperate with each other to obtain desirable decisions while they share some common information. Here, it is assumed that an agent could release the information on its observations. Accordingly, only chance nodes are shared among adjacent agents. Currently, another piece of work most relevant to our theme in this article is the representation of multiply sectioned bayesian networks (MSBNs) (Xiang 2002). In fact, an MSBN is a collection of Bayesian networks (BNs) (Pearl 1988) which are similar to influence diagrams but without decision nodes and value nodes. An MSBN is also a DAG having only chance nodes. Each local Bayesian network in an MSBN representing a single agent's reasoning engine. All together, an MSBN provides a coherent framework for probabilistic reasoning in a cooperative multi-agent distributed interpretation system.

One important concept, called D-Sepnode (Xiang 2002), gives some constraints to subnets (local Bayesian networks) in an MSBN. A node contained in more than one subnet in an MSBN is a D-Sepnode if there is one subnet that contains all of its parents. In an MSBN, all pairwise intersections between subnets should be D-Sepset which is composed of D-Sepnodes. Through D-Sepsets, agents communicate with each other to arrive at a consistent coordination in a distributed reasoning system. Hence, D-Sepsets are also called agent interface in an MSBN.

Figure 2 shows an example MSBN. The MSBN is a DAG that comprises two local BNs, namely, B ₀ and B ₁. Each BN represents an individual agent's reasoning engine. Through the set of common nodes {a, b, c} representing their public information, these two agents communicate with each other to obtain a full and consistent reasoning in the multi-agent system. In Figure 2, common nodes {a, b, c} are D-Sepnodes since all of their parents reside in one local BN. For example, parents of node b and node d are nodes {d, a} and node d, respectively. All the parents are in B ₁, while parents of node c are nodes {b, g} residing in B ₀. Hence, these common nodes form the D-Sepset between B ₀ and B ₁ in the MSBN.

FIGURE 2 An example of MSBN.

D-Sepsets are the only communication channels among agents in an MSBN. In this article, the D-Sepset concept is extended to represent every intersection among adjacent subnets, not just between each pair of subnets. Moreover, an irreducible D-Sepset is defined here. An irreducible D-Sepset is a set of D-Sepnodes that encode the necessary information. Due to the privacy protection matter, agents are not willing to release all of their own information so that they just share the necessary information which does benefit adjacent agents' decision-making. The necessary information may include the requisite information and the supporting information for agents' decision-making. The requisite information is encoded in either required probability nodes or required observation nodes and is required for the decision-making. The supporting information is not required for agents' decision-making; however, this information supports adjacent agents' decision-making. For example, an agent may give the complementary information to its adjacent agents who cannot access this information by themselves. Thus, an irreducible D-Sepset not only provides a concise representation, but also indicates the most economical information for supporting decision-making in a multi-agent decision problem.

Definition of MSID

The previous work on graphical decision models fails to deal with a multi-agent decision problem such as influence diagrams and their evolutionary representations. Two major reasons are stated. Firstly, those formalisms emphasize the single agent-based decision problem. Thus, they do not consider cooperation among agents and properties of multiple agents such as agents' privacy and organizational relationships. Secondly, those graphical models are not scalable. The multi-agent decision problem is a large and complex decision problem so that it is hard to concisely represent a bulk of elements and their relationships within a single model.

As an extended model from Bayesian networks, an MSBN provides a coherent framework for multiple agents reasoning. However, it does not address agents' decision-making problems. This pioneering work lays out a foundation for the concept of MSID.

Definition 1

An MSID I is a set of influence diagrams I _j such that each diagram I _j represents an agent j and the shared chance nodes among adjacent diagrams I _i , I _j ,…, I _k comprise an irreducible D-Sepset S _ij…k .

For instance, for agent i and agent j, the MSID is denoted by I = I _i  ∪ I _j . The D-Sepset between influence diagram I _i and influence diagram I _j is denoted by S _ij (i ≠ j). It can be seen that an MSID, defined as I = ∪ _j I _j , involves two concepts: an agent-based influence diagram I _j and an irreducible D-Sepset S _ij…k .

In brief, an MSID is a set of local influence diagrams that reflect an individual agent's knowledge, actions, and preference. These agents communicate with each other through a D-Sepset that indicates public information. Except for the shared information in a D-Sepset, other information is protected in each local influence diagram. The shared information indicates agents' beliefs on an uncertain environment. It may be affected by agents' actions. The public information can also exert its influence on agents’ behavior. To make a consistent representation in an MSID, Bayesian networks representing an agent, which is only an information-collecting entity without actions or behaviors, are called degenerated influence diagrams. Consequently, an MSID is a hybrid graphical decision model that is a combination of Bayesian networks and influence diagrams. In this sense, an MSBN is a special case of MSID in which all agents do not make decisions and are represented by local Bayesian networks.

The definition of MSID implies that an MSID should comply with three constraints: DAG structure, D-Sepset of agent interface, and irreducible D-Sepset. The first constraint prohibits any directed cycle in an MSID. This is a graphical structure requirement in probabilistic decision models following logical thinking in decision analysis (Robert and Terry 2001). An MSID is a huge decision model that is a set of influence diagrams or Bayesian networks characterizing a large and complex knowledge domain. Multiple agents have consistent thinking including causal relationships on the same observation, which ensures an MSID defines a coherent decision model. Although agents' observations and decisions are interleaved with each other, their interactions follow a sequential order. The second constraint requires that nodes in a D-Sepset shared by local influence diagrams should be D-Sepnodes, which means that all parents of a public node should be included in one of local influence diagrams. This constraint allows agent's privacy and indicates that an agent can decide its decisions using local information only when the information in the D-Sepset is known. Moreover, like assumptions in an MSBN, adjacent agents hold consistent common information that is encoded into the same conditional probability distribution in D-Sepnodes as in an MSID. The final constraint is to ensure the compactness of MSID and HRG, and to remove any redundant information. The information, including requisite information and supporting information encoded in a D-Sepset, is just what adjacent agents are willing to share. Unnecessary information would complicate a model representation and confound the necessary information.

In the aforementioned SARS decision problem, each nation or community can be considered as an individual agent that is modeled as a local influence diagram. Figure 3 shows the MSID that represents this multi-agent decision problem concerning the SARS control. The MSID is defined as I = ∪ _{j=1, 2, 3} I _j . In this MSID, there are three local influence diagrams (I _j , j = 1, 2, 3) that represent three agents (A _j , j = 1, 2, 3), respectively (Agent A ₁: Nation 1; Agent A ₂: Nation 2; and Agent A ₃: Nation 3). Each local influence diagram describes an individual agent's knowledge that formalizes an agent's judgments on the situation. The three agents share some public information represented as grey color nodes {a, b, c} such as the World Health Organization (WHO) report on the SARS, Status of Transmission Customers, and the SARS report from a certain nation (not all involved nations would like to disseminate this information). The information {a, b, c} indicates agents' common beliefs on the same observation. Among this information, the information {a, b} is not affected by agents' decisions while the information c is affected by agent A ₁' decision d ₂. Furthermore, their privacy, like the SARS report from its own nation and states of hospital facilities (some nations have to hide this information for their own benefit), is protected in local influence diagrams such as g in I ₁, k in I ₂, and l in I ₃. The actions of agents, as in Temperature Checking at Entries (d ₁ in I ₁), Home Quarantine Policy (d ₂ in I ₁), Experiments of SARS virus (d ₁ in I ₂), and Overseas Tour Policy (d ₁ in I ₃), are represented as decision nodes in corresponding local influence diagrams in the MSID. The benefit for each agent is defined as utility functions represented by utility nodes in the MSID. In Figure 3, some agents can make decisions independently with the known information in the D-Sepset. For example, with the known information c between I ₁ and I ₃, A ₃ will make the decision d ₁ without considering any effect of A ₁'s actions.

FIGURE 3 MSID for the SARS control.

Definition of HRG

An MSID has the ability of representing a multi-agent decision problem concerning the six characters of the decision scenario. However, it does not explicitly describe the property of organizational relationships among multiple agents such as the required information for decision-making. Moreover, in an uncertain and dynamic environment, agents have to be regrouped in order to adapt to new surroundings. In this process, it is the organizational relationship that guides multiple agents to compose an updated multi-agent system. In Zambonelli's work (Zambonelli, Jennings, and Wooldridge 2001), five types of organizational relationships Control, Peer, Benevolence, Dependency, and Ownership—between agents were discussed. However, from the viewpoint of decision-making and information flow in a multi-agent system, these relationships can be classified into two types: Control and Communication. Hence, the concept of a HRG is introduced to represent the information implicated in the relationships between them.

Definition 2

A HRG H is composed of three types of nodes: rectangular, triangular and oval nodes, and arcs between them. A rectangular node denotes an individual agent A _j associated with local influence diagram I _j in an MSID. A triangular node denotes the shared information C in a D-Sepset S that is required for an agent's decision D. An oval node denotes the shared information C in a D-Sepset S that is not required by any agent's decision D.

With the elements in an HRG, two kinds of basic relevance graphs, called a control relevance graph and a communication relevance graph, are built as shown in Figure 4. Each is associated with a function that implicates an organizational relationship in the multi-agent system.

	A control relevance graph is associated with a function Req(A i , A j , d k ) = {c 1,…, c m }, which indicates that the set of requisite information {c 1,…, c m } agent A i provides, is required for agent A j 's decision d k . It signifies the Control relationship.
	A communication relevance graph is associated with a function sup(A i , A j ) = {c 1,…, c n } which indicates that the set of supporting information {c 1,…, c n } flows between agent A i and agent A j ; however, this information is not required for any of their decisions. It signifies the Communication relationship.

FIGURE 4 Two basic relevance graphs.

In a control relevance graph, the set of information {c ₁,…, c _m } flows from agent A _i to agent A _j in the direction of the triangular node in Figure 4(a). This information is required for agent A _j 's decision-making. The information, called requisite information, is encoded in a subset of either required observation nodes or requisite probability nodes for decision d _k in influence diagram I _j . Hence, in a control relevance graph, it is said that agent A _i controls agent A _j 's decision d _k with the information {c ₁,…, c _m }, but not vice versa. In a communication relevance graph, the information {c ₁,…, c _n } indicated in the oval node implies common beliefs between agents A _i and A _j ; however, this information is not required for their decision-making.

An HRG can be driven and built based on the structural representation of MSID and the organizational relationships in the problem domain. Figure 5 shows the HRG obtained from the MSID in Figure 3. The HRG clearly shows that agent A ₁ controls agent A ₃'s decision d ₁ with the information c, representing that the nation 1's SARS report affects overseas tour policies in nation 3. Furthermore, the information c is affected by agent A ₁'s decision d ₂. Hence, it is said that agent A ₁' decision d ₂ exerts an influence on agent A ₃'s decision d ₁. The HRG also shows that agent A ₂ controls agent A ₁'s decision d ₁ with the information b, representing that temperature-checking decisions at nation 1's border crossing are affected by the status of citizens from nation 2. In this case, agent A ₂ influences agent A ₁'s decision d ₁ by its judgment that is not affected by agent A ₂'s decision d ₁. Besides the public information {b, c}, these nations share the information a that conveys the indication of the WHO report on the SARS. However, this information is not the requisite one for agents' decision-making. In other words, the HRG gives a full picture of the relationships among the three nations modeled as agents A ₁, A ₂, and A ₃.

FIGURE 5 The HRG for the MSID in Figure 3.

The HRG in Figure 5 indicates that multiple nations are able to arrive at a good decision on the SARS control with some cooperation, even without a central control from the WHO.

MSID and HRG

An MSID represents both knowledge of an environment and properties of intelligent agents, while an HRG characterizes organizational relationships in a multi-agent system. Evolving over time, multiple agents are regrouped according to new relationships represented in the HRG. Consequently, the MSID is rebuilt based on the updated HRG.

In an HRG, triangular and oval nodes have the exact chance nodes that can be obtained from a D-Sepset in an MSID. Hence, elements in the HRG could be driven from a well-built MSID through the Decision Bayes-ball procedure. This procedure is used to obtain required chance nodes, including required observation nodes and required probability nodes, for corresponding decision nodes. These required chance nodes and the corresponding decision nodes are elements in triangular nodes. With the exception of these nodes, other nodes in the D-Sepset belong to elements in oval nodes. Extracted from a knowledge domain, the organizational relationships related with two functions are confirmed in the HRG. On another aspect, when an HRG is reorganized because of dynamic organizational relationships in the multi-agent system, it will lead to a reconstruction of the MSID, like refining (decreasing or increasing) nodes in the D-Sepset or their relevance (adding or removing arcs) to decision nodes. Accordingly, the MSID and HRG are regulated with each other to arrive at an elaborate framework.

A compact MSID requires that a D-Sepset should be irreducible, which depends on relationships among intelligent agents. The necessary information, including requisite information and supporting information, flowing through a D-Sepset is just what multiple agents want to access according to their organizational relationships. An HRG is the exact model which encompasses all implications concerning the irreducibility of D-Sepset. Thus, an HRG is able to help the constraints (irreducibility of D-Sepset) checking and the reconstruction of an MSID.

MODEL VERIFICATION

From the definition of MSID, an MSID should satisfy three constraints: DAG structure, D-Sepet of agent interface, and irreducibility of D-Sepset. To ensure the validity of an MSID, the task of model verification has to be carried out.

Verification of the DAG Structure and D-Sepset

The first constraint, called DAG structure, means that there should be no directed cyclic paths in an MSID. The second constraint requires that every public node in an agent interface should be a D-Sepnode, indicating that all of its parents should be included in one of the local influence diagrams.

Theorem 1

An MSID without value nodes has the same DAG property as the original MSID.

Proof

An MSID includes three types of nodes: chance nodes, decision nodes, and value nodes. Since a value node is a sink node without outgoing arcs in an MSID, it cannot belong to any part of a directed cyclic path.□

With Theorem 1, in the verification process of DAG structure, value nodes in an MSID can be removed safely. When value nodes are removed and decision nodes are considered as chance nodes in an MSID, the MSID has the same structure as an MSBN. In addition, as only chance nodes in an MSID are public nodes, the method of the D-Sepset verification in an MSID is similar to that in an MSBN.

Theorem 2

An MSID without value nodes has the same D-Sepset property as the original MSID.

Proof

Since a value node in an MSID is a sink node without outgoing arcs, it is impossible for them to become parents of public nodes in an agent interface. Removing it causes the D-Sepset property to be still held in an MSID.□

In our past work on the verification in an MSBN (Zeng and Poh 2003), a symbolic method was proposed to deal with the verification problem. The symbolic method is based on an algebraic description of the joint probability distribution and its factorization in the form of conditional probability.

x is a chance node, including original chance nodes and transformed decision nodes in an MSID. Two constraints will be checked, respectively, following details in Zeng and Poh (2003). Take as an example—the MSID in Figure 3—that has no directed cycle and all the parents of public nodes {b, c} are in local influence diagram I ₁. (The parents of another public node a are empty.) Hence, the MSID satisfies the first two constraints.

Verification of the D-Sepset Irreducibility

The irreducibility of a D-Sepset is to ensure the compactness of an MSID and HRG, and to remove any redundant information in this model representation. The irreducibility of D-Sepset depends on organizational relationships among agents and information flowing through the D-Sepset. The information should be composed of requisite information and supporting information (for agents' decision-making), which indicate the control and communication relationships among agents, respectively. An HRG is just an effective framework that can be used to test this constraint. Hence, the verification of the two basic relevance graphs in an HRG is discussed as follows.

Control relevance graph: Figure 4(a) shows the Control relationship between agent A i and agent A j denoted by the function Req(A i , A j , d k ) = {c 1,…, c m }. To verify the irreducibility of a D-Sepset amounts to testing whether the information {c 1,…, c m } agent A i provides a subset of required information for agent A j 's decision d k .

It is known that the Decision Bayes-ball procedure could be used to obtain the required information for any decision node in a single agent-based influence diagram. Through these procedures, the information {c ₁,…, c _m } required for agent A _j 's decision d _k can be obtained. Assuming Control is a unique relationship between agent A _i and agent A _j and the D-Sepset is S _ij ; thus, S _ij  ⊆ ∪ _k Req(A _i , A _j , d _k ) ⇔ Irreducibility.

Communication relevance graph: Figure 4(b) shows the Communication relationship between agent A i and agent A j denoted by the function Sup(A i , A j ) = {c 1,…, c n }. The irreducibility of D-Sepset means that the information passing through a D-Sepset is just the supporting information that either agent A i or agent A j wants to access; however, this information is not the requisite for any of their decision-making. The verification depends on the domain knowledge. For example, domain expert could tell what kind of information is unavailable to one agent while its adjacent agents could provide such kind of information. Assuming Communication is the unique relationship between agent A i and agent A j , then D-Sepset is denoted as S ij ; therefore, S ij  ⊆ Sup(A i , A j ) ⇔ Irreducibility.

When mixed relationships (both control and communication) between agent A _i and agent A _j exist, an integrated verification is utilized as follows.

For example, concerning the MSID in Figure 3, the D-Sepsets are S ₁₂ = {a, b}, S ₂₃ = a and S ₁₃ = {a, c}. From the procedure Decision Bayes-ball, it is found that nodes b and c are required for agent A ₁'s and agent A ₃'s decision d ₁, respectively. Thus, cases are Req(A ₁, A ₃, d ₃) = c and Re q(A ₂, A ₁, d ₁) = b. Assuming the irreducibility of D-Sepset and according to Equation (1), it follows that Sup(A _i , A _j ) = a where i, j = 1, 2, 3 and i ≠ j. Based on this analysis, the HRG can be produced as shown in Figure 5.

At this time, the HRG could be evaluated by domain experts whether or not it realistically reflects the actual problem domain. If it does, the irreducibility of D-Sepset is verified; otherwise, the HRG will be modified. The modeling process is iterative until both the HRG and the MSID are acceptable.

In the SARS model, the organizational relationship is defined by the involved nations' intentions. For example, to make a decision on oversea tour policies in nation 3, the information from the nation 1's SARS report is required. Hence, the Control relationship exists. In some situations, nation 3 could make this decision based on the WHO SARS report instead of the nation 1's SARS report, which relaxes its dependence on nation 1. In general, in the initialization, an HRG can be driven from a well-built MSID representing the SARS situation. After that, some small modifications with the HRG may be done based on the knowledge elicitation of the SARS situation, especially on the organizational relationship among the affected nations. Finally, the accurate structure of the HRG and MSID is refined and developed. One advantage of this framework lies in its robustness and flexibility to dynamic situations. For example, when a nation is affected by the SARS virus and has to be considered in the whole community, only one new local influence diagram representing this nation is added into the model without damaging other parts of the existing MSID and HRG. This saves much effort on model reconstruction, which indicates that the framework of MSID and HRG is reusable.

MODEL EVALUATION

Evaluating a model is to determine an optimal policy for its decisions. The basic methods for solving an MSID are extensions of evaluation algorithms on a single agent-based influence diagram, such as reduction algorithms (Shachter 1986) and indirect methods (Jensen, Jensen, and Dittmer 1994). Reduction algorithms directly solve influence diagrams with some basic operations such as nodes removal and arcs reversal. Indirect methods (evaluating influence diagrams) transform an influence diagram into a rooted, strong junction tree and then solve the junction tree. As the process of transforming an MSID is similar to that in an MSBN, we would like to discuss indirect methods for solving an MSID. Furthermore, some relevant strategies to solve an MSID are investigated.

Decision Solutions for MSID

Solving a multi-agent decision problem is to seek the best decision for multiple agents in a cooperative and privacy protection setting. Every agent aims to obtain an optimal solution while it cooperates with its adjacent agents. An agent, without disclosing its privacy, wants to access the full and consistent public information in order to maximize its utility value. Here, the global optimal solution of the multi-agent decision problem is defined as the combination of the best decision solutions from multiple agents.

An MSID represents a multi-agent decision problem with a set of local influence diagrams. These local influence diagrams are connected with D-Sepsets. Through the information in a D-Sepset, local influence diagrams could affect their adjacent ones. Hence, in the evaluation process, we should adopt some relevant strategies to avoid the incomplete and inconsistent information in a D-Sepset. To achieve this goal, D-Sepnodes should follow a uniform elimination order in an evaluation algorithm so that they could be evaluated and removed from an MSID simultaneously. Through this way, it is ensured that an agent has obtained full, correct, and consistent information so that each agent's benefit is maximized in a distributed and unpredictable situation.

Evaluation Algorithms

Like solving influence diagrams, evaluation algorithms to solve an MSID follow two steps: transforming an MSID into a multiple-rooted cluster tree, which is a set of interconnected rooted cluster trees (Shachter 1999), and solving the multiple-rooted cluster tree.

Transforming an MSID: The methods to transform an MISD into a multiple-rooted cluster tree are combinations of evaluation algorithms in both influence diagrams and MSBN (Jensen et al. 1994; Shachter 1999; Xiang 2002). Firstly, to build a modified MSID for each local influence diagram, requisite observation nodes are identified using the Decision Bayes-ball procedure. Then arcs are added between identified required nodes and their corresponding decision nodes. Finally, a multiple-rooted cluster tree is built in a cooperative algorithm (Xiang 2002). The basic idea of this algorithm is to transform local influence diagrams into local rooted cluster trees as well as to transform D-Sepsets into linkage trees. The linkage trees connect the transformed local, rooted cluster trees together into a multiple-rooted cluster tree. In this process, an index is introduced to show a clique sequence in the local rooted cluster tree.

Solving a multiple rooted cluster tree: A multiple-rooted cluster tree is a tree structure for an MSID. It is a set of local rooted cluster trees connecting through the linkage trees. Thus, evaluating an MSID amounts to solving these local rooted cluster trees as well as the linkage trees. The local rooted cluster tree is evaluated following a partial decision order in a local influence diagram. The linkage tree among local rooted clusters coordinates the computation of adjacent cliques to make sure that D-Sepnodes are evaluated at the same time. Hence, D-Sepnodes in a linkage tree could be removed simultaneously. This has to concern a relative elimination order for D-Sepnodes in an MSID. The relative elimination order could be obtained by considering the clique index in local rooted cluster trees globally. A good relative index on cliques allows the linkage trees to be evaluated cooperatively among adjacent local rooted cluster trees.

In a word, an MSID is solved in a distributed way following the above two steps. In this article, we do not focus on the process of developing a multiple-rooted cluster tree since it could be found in detail in much literature (Jensen et al. 1994; Shachter 1999; Xiang 2002). We place more emphasis on the solving of linkage trees in a multiple-rooted cluster tree, which is illustrated in the following case.

Evaluation of the SARS Control Situation

In Figure 3, the three influence diagrams I ₁, I ₂, and I ₃ are transformed into three local rooted cluster trees T ₁, T ₂, and T ₃, respectively. The D-Sepsets are transformed into linkage trees. For the MSID in Figure 3, the D-Sepset transformation is simple because each chance node in a D-Sepset composes one linkage tree. These local rooted cluster trees and linkage trees compose a multiple-rooted cluster tree in Figure 6.

FIGURE 6 A multiple-rooted cluster tree. (Nodes without color denote cliques and nodes with grey color denote linkage trees.)

D-Sepnodes in the linkage tree adjust the solving of cliques in adjacent local cluster rooted trees since they have to be removed simultaneously. The removal of D-Sepnodes must follow an elimination order in a local cluster rooted tree. For example, in T ₁, nodes {a, c} have to be removed before node b, although there is no fixed elimination order for nodes {a, c}. However, in T ₃, the removal of node a precedes the removal of node c. Hence, a legal elimination order for D-Sepnodes in the computation of the multiple-rooted cluster tree exists: node a is removed before node c, which should be removed before node b. It is also noticed that the arc associated with the linkage tree including node c is from T ₁ to T ₃ in Figure 6. This follows the implication of the HRG in Figure 5. It indicates that agent A ₁ controls agent A ₃'s decision d ₁ by the information c. For the linkage tree among T ₁, T ₂, and T ₃, the arc direction depends on an elimination order for D-Sepnodes if this order exists; otherwise, it is optional.

Following the above procedures, the MSID for the SARS model is solved by evaluating local influence diagrams individually and combining all local optimal solutions. The consistent information, implicated in the D-Sepset in an MSID and restricted in organizational relationships in an HRG, is guaranteed throughout the evaluation process. If the shared information is inconsistent, the decision-making is prone to be wrong. For example, with reference to the MSID in Figure 3, if nation 1 deliberately hides its SARS report (represented by node c), decision d ₁ in nation 3 will be definitely wrong. Consequently, decisions in the whole community will lead to quite a large loss, which has been the case in SARS 2003. Accordingly, a true model of MSID and HRG not only provides good decisions for policymakers, but also allows a large number of simulations to report some alerts in order to avoid a destructive loss.

CONCLUSION

We have proposed a distributed and cooperative framework of MSID and HRG to represent a multi-agent decision problem such as the SARS control in the medical domain. It considers agency features such as the privacy protection and the dynamic organizational relationship. Model verification methods assisting to build a valid model are discussed in detail. At the same time, we solve an MSID in an indirect way by transforming it into a multiple-rooted cluster tree. Some useful strategies are analyzed to obtain global optimal solutions.

In fact, besides the SARS situations, more practical applications exist in the medical domain. For example, in the operation of body separation, a group of doctors or experts from different medical fields are needed. Every doctor is specialized in a certain medical field, in which his/her knowledge is private. Of course, they have the same knowledge on patients' states and some common diseases. Hence, they could and should cooperate with each other to make optimal decisions in the operation process. Our proposed methodologies should be able to address this task when the evaluation approach is extended.

In the real world, agents to make decisions always reside in a distributed and uncertain environment. Gathering them to hold a meeting for decision-making requires a hard coordination, such as the location and time selection. A distributed and agency modeling approach, such as the solving of MSID and HRG, has to be utilized to facilitate this decision-making. The MSID, together with the HRG, not only describes an uncertain setting of decision-making, but also characterizes properties of multiple agents. They should become important techniques to address a multi-agent decision problem.

This article has solved a multi-agent decision problem roughly in principle; however; much work is required to improve the existing work such as more efficient algorithms to solve an MSID. Further research on the value of information in an MSID will enrich its theory and applications.

The article was partially finished when Y. Z. completed his PhD study at the National University of Singapore. The authors would like to thank Dr. Tze-Yun Leong and members of the Biomedical Decision Engineering Research Group at the National University of Singapore for their helpful comments.