Combining Opinion Pooling and Evidential Updating for Multi-Agent Consensus

1 Introduction and Background

In agent-based systems individuals receive information from at least two distinct sources; either as direct evidence from their environment, e.g. directly from different sensor modalities or by running tests or experiments, or from other individuals in the population. More specifically, we envisage agents as holding beliefs about a set of hypotheses of interest and then adapting those beliefs, either on the basis of direct evidence, or by taking account of the beliefs of the other agents that they are interacting with. Assuming that the agents' beliefs take the form of probability distributions over the hypotheses, we can model evidential updating in a Bayesian manner and then allow a form of probability pooling so that agents can combine their distributions with those of others.

This paper investigates the relationship between the two processes, updating based on direct evidence and probability pooling, in a dynamic setting in which agents adapt their beliefs over time. The motivating assumption is that pooling operators should provide a mechanism by which a limited amount of direct evidence can be efficiently propagated through the agent population so that an appropriate consensus is reached. This effect has already been studied in the context of social epistemology where the focus is on the overall knowledge of the group or population [Douven et al., 2017]. For example, Douven and Kelp [Douven and Kelp, 2011] argue that dialogue between scientists is an important aspect of scientific research which complements experimental work. They support their case with simulation studies in which a population of agents receive occasional evidence, in this case the true value of a real-valued parameter, as well as pooling opinions by taking weighted linear combinations of values from other agents. The results suggest that the population converges much faster to the true parameter value when both pooling and evidential updating are employed, than it does when there is only evidential updating.

In the sequel we investigate probability pooling combined with updating based on direct evidence. We also adopt a Bayesian approach to pooling in which it is viewed as a form of second order updating on the basis of evidence consisting of the probability values of agents in the pool. From this perspective we provide a clear interpretation of a particular pooling operator and show the assumptions underlying it. We then introduce the properties of evidence dilution, preservation and amplification for pooling operators as a way of gauging the extent to which they enable direct evidence to be propagated across the agent population. Simulation experiments will be carried out to investigate a single parameter family of pooling operators which can be evidence diluting, preserving or amplifying depending on the parameter value. We consider the effectiveness of these operators at evidence propagation for different parameter values, different pool sizes and where the evidence is received at different rates. We focus on two mutually exclusive and exhaustive hypotheses denoted H1 and H2 so that each agent's beliefs can be characterised by a real number x ∈ [0, 1] indicating that P(H1) = x and P (H2) = 1 - x.

Probability pooling operators have been proposed as a means for combining a group of expert opinions to obtain a single probability distribution, with early work dating, at least, back to DeGroot [DeGroot, 1974] and Stone [Stone and others, 1961]. As in both of these papers a common approach is simply to take the pooled distribution as a weighted linear combination of all the distributions of the agents in the cohort. For the two hypotheses case, if there are k agents with probabilities x1, . . . , xk, then the pooled probability of H1 is ∑ki=1 wixi where wi > 0 : i = 1, . . . , k and ∑ki=1 wi = 1. The weights wi then quantify a relative level of confidence in the different agents. A general definition of a pooling operator is simply as follows:

Definition 1.1 (Pooling Operator): A pooling operator for k agents is a function c : [0, 1]k → [0, 1], so that for agents A1, . . . ,Ak with probabilities PAi (H1) = xi for i = 1, . . . , k then c(x1, . . . , xk) is the pooled probability of H1.

In this paper we focus on three related geometric pooling operators which have clear Bayesian justifications and which it turns out have interesting evidence propagation properties. A summary of these is given in definition 1.2.

Definition 1.2 (LogOp, SProdOp and ProdOP Pooling Operators): The following are the pooling operators that we consider in this paper;

• The Log-Linear Operator (LogOp):

for wi ≥ 0.

• The Scaled Product Operator (SProdOp): This is a special case of LogOp in which wi = . . . = wk = w > 0 so that,

• The Product Operator (ProdOp): This is a special case of SProdOp in which w = 1 so that,

LogOp has been widely discussed in the literature (see Genest and Zidek [Genest and Zidek, 1986] for an early overview), with a variety of possible justifications for the operator being presented. For instance, it is known to be the operator which minimizes the weighted Kullback-Leibler divergence between the pooled probability distribution and the agents' distributions [Abbas, 2009]. Pennock [Pennock and Wellman, 1999] shows that LogOp preserves Markov independence and can therefore be useful in graphical probability models. Most recently Pettigrew [Pettigrew, 2017] has considered LogOp as a way of pooling incoherent probabilities. More specifically, agents are deemed to be incoherent if their probabilities do not sum to one. Such distributions can be 'fixed' by renormalisation and [Pettigrew, 2017] suggests that fixing before pooling and fixing after pooling should yield the same result. Indeed if standard renormalisation is employed

(i.e. dividing by the sum of the non-normalised probabilities) then LogOp is shown to satisfy this property.

ProdOp, a special case of LogOp, has been proposed as an effective tool for classifier combination [Hinton, 1999] and also for expert pooling in the management sciences [Bordley, 1982]. Other applications include natural language processing [Osborne and Baldridge, 2004].

An outline of the remainder of the paper is as follows. Section 2 will consider a Bayesian interpretation for LogOp under certain assumptions including agent independence. In section 3 we consider the combination of pooling and direct evidence and in particular, we introduce the properties of evidence preservation, amplification and dilution as means of classifying the extent to which the pooling process propagates evidence. In section 4 we present simulation experiments into the convergence properties of SProdOp for different values of w and k, and at different evidence rates. Finally, in section 5 we give some discussions and conclusions.

2 A Bayesian Interpretation of Opinion Pooling

In this section we consider pooling as being a type of conditioning based on second order evidence in the form of agents' beliefs. For this we adopt a Bayesian approach and show that it provides clear justifications for LogOp. In this context we introduce the notion of an oracle as an arbitrator who performs Bayesian updating given the probabilities from all k agents in the pool.

Given a pool of k agents suppose that the aggregated probability corresponds to the conditional probability of H1 of an 'oracle' O, given the evidence provided by the probabilities of the agents in the pool. Here the oracle is an abstract entity which we might choose to interpret in a number of different ways. For instance, O might be a kind of independent arbitrator tasked with identifying a single shared probability which takes account of the beliefs of the other agents. Alternatively, we could think of O as an aggregate representation of the whole pool. The idea of opinion pooling as based on the judgement of an oracle is well-known, with [Hogarth, 1975] and [Keeney and Raiffa, 1976] referring to O as a 'synthetic personality' and a 'supra Bayesian' respectively. Furthermore, early work by [Winkler, 1968] and [Morris, 1974] shows that from a Bayesian perspective, the pooling operator c can then be understood to be O's posterior distribution determined along the following lines. Suppose that O has a prior probability of H1, denoted PO(H1), then this is conditioned on the evidence B = ∧ki=1 (PAi (H1) = xi) representing the beliefs of the k agents, according to Bayes' theorem as follows;

We now consider two assumptions that O might make concerning the distribution of PAi (H1) for i = 1, . . . , k.

This assumes that learning H1 holds provides O with the same information about the agents' probabilities of H2 as learning H2 holds provides about their probabilities of H1.

Definition 2.2 (Independent Agents): The agents A1, . . . , Ak are independent if ∀xi,

The agents are deemed to be independent if the random variables PA1 (H1), . . . , PAk (H1) are conditionally independent of each other given either H1 or H2.

In the following theorem we consider the situation in which given H1, O considers each agents' probability to be distributed according to a Beta distribution with parameter values ai and bi for i = 1, . . . , k.

Theorem 2.1. If given H1, ∀i, PAi (H1) has a Beta distribution with parameters ai and bi where ai ≥ bi so that PO(PAi (H1) = xi|H1) ∝ xai-1 i (1 - xi)bi-1 , and if we assume likelihood symmetry, independent agents and that PO(H1) = 0.5 then c is LogOp with wi = ai - bi for i = 1, . . . , n.

Proof. By independence and assuming

it follows that;

Also, by independence and likelihood symmetry it holds that;

Hence, since PO(H1) = 12 then substituting into Bayes' theorem gives,

PO(H1|B) =

Dividing top and bottom by ∏ki=1 xbi-1 i (1-xi)bi-1 gives PO(H1|B) =

as required.

For a Beta distribution with parameters ai ≥ bi the skewness value is negative. This means that the conditional probability density for PAi (H1) given H1 is skewed towards 1.

Furthermore, the skewness can be expressed as a function of wi = ai - bi and bi, which for any fixed bi is a strictly decreasing function of wi. Hence, in this case as wi increases the distribution of PAi (H1) becomes increasingly skewed towards 1. Negative skewness and hence wi, in this context, is arguably an indicator of the capability of Ai when predicting which hypothesis holds, since if H1 is true then we would expect that the probability PAi (H1) of a capable agent would tend to be close to 1 (see figure 1).

In the next section we consider the combination of probability pooling with evidential updating on the basis of direct evidence e.g. from sensors or other sources, either obtained passively or through exploration and experimentation.

3 Combining Pooling Operators with Direct Evidence

Direct evidence is assumed to correspond to an assertion that one of the hypotheses holds i.e. evidence E is a variable taking value H1 or H2. An agent then updates their probability of H1 from x to x|E using Bayes' theorem as follows:

Definition 3.1 (Evidential Updating): For x ∈ [0, 1], E ∈ {H1,H2} and α ∈ [0, 12 ], then x|E ∈ [0, 1] such that;

where δH1 = 1 - α and δH2 = α.

The rationale behind definition 3.1 is that, according to Bayes' theorem, an agent with prior probability x should update their beliefs given evidence E such that;

We then make the further assumption that the likelihood of E is given by:

Here α quantifies the (agent's belief about the) reliability of the source of the evidence. For α = 0 the source is absolutely reliable and will only provide E if and only if E is true. For α = 0.5 the source is totally unreliable and is just as likely to provide E if it is false as if it is true. Notice that when α = 0.5, x|E = x. This seems to be intuitive since if an agent has absolutely no faith in a source of evidence, they should not change their beliefs on the basis of evidence that it provides. Notice in the case that α = 0, then 1|H2 and 0|H1 are undefined.

We now introduce three possible properties concerning the extent to which existing direct evidence is propagated through the pooling process. In each case only probabilities in the open interval (0, 1) are considered so as to avoid any cases in which conditional probabilities (definition 3.1) are undefined.

Definition 3.2 (Evidence Preservation): [Dietrich et al.,

Definition 3.3 (Evidence Dilution): ∀xi ∈ (0, 1) : i = 1, . . . , k, ∀i ∈ {1, . . . , k}, ∀α ∈ [0, 12 );

c(x1, . . . , xi, . . . , xk)|H1 and

c(x1, . . . , xi, . . . , xk)|H2.

Furthermore, there exists (x1, . . . , xk) ∈ (0, 1)k such that the above inequalities are strict.

Definition 3.4 (Evidence Amplification): ∀xi ∈ (0, 1) : i =

c(x1, . . . , xi, . . . , xk)|H2.

Furthermore, there exists (x1, . . . , xk) ∈ (0, 1)k such that the above inequalities are strict.

Evidence preservation was recently proposed by Dietrich and List [Dietrich et al., 2016] who refer to it as 'Individual Bayesianism'. It requires that if a single agent receives evidence then that evidence is preserved by the pooling process. More specifically, it should make no difference whether the evidence is presented to any one of the agents prior to pooling or if it is presented after pooling. This property could be appropriate if different agents receive evidence from independent sources. To see this notice that for an evidence preserving operator;

In other words, if each agent receives the same evidence this has a strong reinforcement effect on the pooled probabilities. The evidence dilution and amplification properties then claim that pooling should respectively dilute or amplify the effect of evidence presented to any one of the agents. We now consider evidence dilution, preservation and amplification in detail so as to obtain an insight into the evidence propagation properties of the pooling operators introduced in section 1. Indeed, the following theorem due to [Dietrich et al., 2016] shows that evidence preservation is a sufficiently strong property to characterise ProdOp.

Theorem 3.1. [Dietrich et al., 2016] A pooling operator c satisfies evidence preservation and c(0.5, . . . , 0.5) = 0.5 if and only if ∀xi ∈ (0, 1) : i = 1, . . . , k, c is ProdOp.

We now extend this result to show that SProdOp is evidence diluting, preserving or amplifying depending only on the value of the parameter w. In section 4 we will use this property of SProdOp to investigate optimal levels of evidence propagation for varying evidence rates.

Theorem 3.2. SProdOp is evidence diluting if w < 1, evidence preserving if w = 1 and evidence amplifying if w > 1.

Proof. W.l.o.g let E = H1. Then for the scaled product operator we have that;

For evidence dilution we require that for some (x1, . . . , xk) ∈ (0, 1)k , c(x1, . . . , xi|E, . . . , xk) < c(x1, . . . , xk)|E. From the above this implies that;

Nowα < 1 2 ⇒ 1-α > α ⇒ (1-α)w-1 < αw-1 if and only if w - 1 < 0 if and only if w < 1. Similarly, for evidence amplification we require that c(x1, . . . , xi|E, . . . , xk) > c(x1, . . . , xk)|E which then holds if and only if w > 1. Finally, taking w = 1 corresponds to the product operator which is evidence preserving by theorem 3.1.

4 Experimental Results

In this section we describe simulation experiments exploring the consensus attainment properties of SProdOp when implemented in a multi-agent system. The aim of these experiments is to investigate SProdOp using different values of w in order to better understand the system-level behaviour of evidence diluting, preserving and amplifying operators.

A population of 100 agents is initialised with probabilities of H1 randomly chosen from [0, 1]. At each iteration, the population is permuted to emulate movement, this approach being consistent with the well-stirred assumption as described in [Parker and Zhang, 2009]. A pool of k agents are then chosen at random from the population. Their probabilities are combined using SProdOp with each agent then adopting the resulting pooled probability. In addition to pooling, every agent also has a probability ϵ of directly receiving the evidence E = H1, in which case they use Bayesian updating to obtain a posterior probability as given in definition 3.1. We take α = 0.1 indicating that agents have a high-level of trust in the sources of direct evidence, but which falls short of absolute confidence. In multi-agent systems or robot swarms we might envisage this set-up as modelling a scenario in which agents explore their environment and receive direct sensory evidence from time-to-time. Subsets of the population would then also regularly come together to pool their beliefs. This is a common formulation for the best-of-n problem in swarm robotics, in which the population must identify the true hypothesis in a distributed manner [Valentini et al., 2017].

We judge that consensus has been reached in a simulation experiment if 90% of the agents in the population have a probability for H1 greater than 0.9, in which case the simulation is terminated and the time to consensus recorded. In the case that consensus is not reached then a simulation is automatically terminated after 10, 000 iterations, which is for practical purposes then recorded as the consensus time. In this context, failure to reach consensus can occur for a number of reasons. This includes polarisation in which a subset of the population converges to a probability close to 1, while the remaining agents converge to a probability close to 0. However, it also includes the possibility that all agents converge on a probability close to 0.5. Although, there is agreement about the probability of H1 in this case, there is clearly a failure to effectively propagate the direct evidence that H1 holds provided to individual agents. In the following, for each set of parameter values, 100 independent runs of the simulation were carried out. Results are averaged over those 100 runs.

We compare the time to consensus for a combination of pooling and updating with that for evidential updating alone, across a range of values for ϵ, k and w. For all values of k and ϵ we find that there is an interval of values of w in which the combination of pooling & updating outperforms updating alone. Figure 2 illustrates this, showing the average time to consensus plotted against w for k = 3 and ϵ = 2%. The solid line is the consensus time for pooling & updating, while the dotted horizontal line is the consensus time for updating alone. The interval in which the solid line lies below the dotted line, therefore identifies the range of w values for which pooling provides some additional advantage when used in addition to updating from direct evidence. The characteristic shape of these curves suggests a number of metrics which may provide insight into the evidence propagation properties of SProdOp. We take gain to be the maximum gain in convergence time resulting from using pooling in addition to updating. Robustness corresponds to the length of the interval of w values for which pooling provides some benefit. This gives us an indication of the sensitivity of the choice of w for a particular combination of k and ϵ values. We also identify the optimal value of w, denoted w∗ , resulting in the shortest time to consensus. Taken in conjunction with theorem 3.2 this quantifies the extent to which the optimal form of SProdOp should be evidence diluting, preserving or amplifying.

Figure 4 shows gain, w∗ and robustness plotted against k and ϵ. Figure 4a suggests that there is an optimal value of k for any given evidence rate ϵ, and that for larger k values performance then declines. As might be expected gain decreases as the evidence rate increases for all k values, since for higher evidence rates updating from direct evidence dominates (see figure 4d). It should also be noted that for higher values of k there is increased sensitivity concerning the choice of w, with a narrower interval of values in which pooling & updating outperforms updating only. This can be seen in figure 4c in which robustness decreases with k. Robustness tends to increase with evidence rate (figure 4f), although this is against a backdrop of decreasing gain. Balancing between gain and robustness, figures 4a and 4c would seem to provide a case for smaller pool sizes.

From figure 4b we can see that w∗ decreases with k, so that the larger the size of the pool the more diluting the operator should be. In contrast w∗ tends to increase with ϵ, although this increase levels off for higher evidence rates (see figure 4e). In general, all w∗ values identified lie in the range (0, 1] with w∗ = 1 only for k = 2 and evidence rates greater than or equal to 4%. Hence, the results suggest that evidence diluting operators may be optimal for evidence propagation particularly when evidence rates are relatively low. Furthermore, for higher values of ϵ the gain from pooling is lower (figure 4d).

The variation of consensus time with w, as illustrated by figure 2, suggests that consensus is not achieved either for very low (close to 0) or for very high parameter values. For low evidence rates the system dynamics are significantly influenced by the properties of the pooling operator.We can gain insight into this by considering the fixed points of SProdOp i.e. those values of x for which c(x, . . . , x) = x. For SProdOp with w > 0, the only fixed points are at x = 0, x = 0.5 and x = 1. For w ≥ 1k only 0 and 1 are stable fixed points and 0.5 is unstable. For w < 1k all three fixed points are stable. Furthermore, as w tends to 0, SProdOp tends to a uniform value of 0.5, while as w tends to infinity SProdOp tends to a step function. This is illustrated in figure 3, which shows c(x, x, x) for several values of w. From this we might hypothesise that for very high values of w, where SProdOp is extremely evidence amplifying, the population will quickly polarise with some holding probability 0 and others probability 1. On the other hand, for very low values of w, where SProdOp is extremely evidence diluting, we would expect the population to quickly converge on a shared probability of 0.5.

5 Conclusions

In this paper we have investigated the relationship between direct evidential updating and probability pooling in multiagent systems. We have presented a Bayesian interpretation of LogOp which considers pooling to be a form of second order updating where the weight wi quantifies the competency of the agent Ai by influencing the skew of an oracles' distribution on PAi (H1) (theorem 2.1). We have then introduced the properties of evidence dilution, preservation and amplification as a way of gauging the evidence propagation properties of pooling operators. Furthermore, in this context we have shown that SProdOP is either diluting, preserving or amplifying depending only on the weight parameter w (theorem 3.2). This then provides a single parameter for varying the degree of evidence propagation of an operator, which we have then studied in detailed simulation experiments.

The simulation experiments presented in section 4 suggest that probability pooling using an appropriate operator can significantly improve the propagation of direct evidence across an agent population. As is to be expected this improvement is greatest for relatively low evidence rates. Results suggest that there is an optimal pool size k for any given evidence rate, but as k increases robustness decreases, implying that it is more difficult to identify a suitable value of w. For example, in the experiments in section 4, the optimal value of k is approximately 7 for all of the error rates investigated. However, for k = 7 robustness is relatively low i.e. between 0.1 and 0.3.

Hence, when taking account of both gain and robustness, our results suggest that lower values of k are preferable.

For all the error rates considered, the optimal value of w is between 0 and 1 and hence evidence diluting operators are more effective at evidence propagation for the type of agentbased system considered. This is partly due to the fact that SProdOp with large w tends towards a step function (figure 3), resulting in too fast convergence to either 0 or 1. In accordance with theorem 2.1, this corresponds to an assumption that agents are only moderately competent, since assuming higher levels of competence does not allow sufficient time for the population to take account of direct evidence before reaching an agreed belief.

Future work will attempt to generalise the results presented from two to multiple hypothesis i.e. to where opinions are probability distributions over H1, . . . ,Hn for n ≥ 2. In this case, pooling operators are functions defined on a cartesian product of k (n - 1)-dimensional probability simplexes. Furthermore, more detailed analytical studies should be conducted into the underlying dynamics of agent-based systems which combine both pooling and updating. This should then provide more insight into the simulation results described in section 4. We will also consider other operators such as linear pooling. Furthermore, we will consider non-Bayesian approaches such as imprecise probabilities and DempsterShafer theory.

Acknowledgements

This research was partially funded by an EPRSC PhD studentship as part of the Centre for Doctoral Training in Future Autonomous and Robotic Systems (grant number EP/L015293/1).

All underlying data is included in full within the paper.