A model of multi-agent consensus for vague and uncertain beliefs

Abstract

Consensus formation is investigated for multi-agent systems in which agents’ beliefs are both vague and uncertain. Vagueness is represented by a third truth state meaning borderline. This is combined with a probabilistic model of uncertainty. A belief combination operator is then proposed, which exploits borderline truth values to enable agents with conflicting beliefs to reach a compromise. A number of simulation experiments are carried out, in which agents apply this operator in pairwise interactions, under the bounded confidence restriction that the two agents’ beliefs must be sufficiently consistent with each other before agreement can be reached. As well as studying the consensus operator in isolation, we also investigate scenarios in which agents are influenced either directly or indirectly by the state of the world. For the former, we conduct simulations that combine consensus formation with belief updating based on evidence. For the latter, we investigate the effect of assuming that the closer an agent’s beliefs are to the truth the more visible they are in the consensus building process. In all cases, applying the consensus operators results in the population converging to a single shared belief that is both crisp and certain. Furthermore, simulations that combine consensus formation with evidential updating converge more quickly to a shared opinion, which is closer to the actual state of the world than those in which beliefs are only changed as a result of directly receiving new evidence. Finally, if agent interactions are guided by belief quality measured as similarity to the true state of the world, then applying the consensus operator alone results in the population converging to a high-quality shared belief.

1 Introduction

Reaching an agreement by identifying a position or viewpoint that can ultimately be accepted by a significant proportion of the individuals in a population is a fundamental part of many multi-agent decision making and negotiation scenarios. In human interactions, opinions can take the form of vague propositions with explicitly borderline truth values, i.e. where the proposition is neither absolutely true nor absolutely false (Keefe & Smith, 2002). Indeed, a number of recent studies (Balenzuela, Pinasco, & Semeshenko, 2015; Crosscombe & Lawry, 2015; de la Lama, Szendro, Iglesias, & Wio, 2012; Perron, Vasudevan, & Vojnovic, 2009; Vazquez & Redener, 2004) have suggested that the presence of an intermediate truth state of this kind can play a positive role in opinion dynamics by allowing compromise and hence facilitating convergence to a shared viewpoint.

In addition to vagueness, individuals often have uncertain beliefs, owing to the limited and imperfect evidence that they have available to them about the true state of the world. In this paper, we propose a model of belief combination by which two independent agents can reach a consensus between distinct and, to some extent, conflicting opinions that are both uncertain and vague. We show that, in an agent-based system, iteratively applying this operator under a variety of conditions results in the agents converging on a single opinion which is both crisp (i.e. non-vague) and certain.

However, beliefs are not arrived at only as the result of consensus building within a closed system, but are also influenced by the actual state of the world. This can arise both by agents updating their beliefs given evidence, and by them receiving different levels of payoff for decisions and actions taken on the basis of their beliefs. In this paper, we model both of these processes when combined with consensus formation. We consider the case in which a population of agents interact continually at random, forming consensus where appropriate, but occasionally receiving direct information about the state of the world. Defining a measure of belief quality, taking account of the similarity between an agent’s belief and the true state of the world, we then record this quality measure in simulations that combine both consensus building and belief updating from evidence and compare these with simulations in which only evidence-based updating occurs. In these studies, we observe that combining evidence-based updating and consensus building results in faster convergence to higher quality beliefs than when beliefs are only changed as a result of receiving new evidence. This would seem to offer some support for the hypothesis put forward by Douven and Kelp (2011), that scientists may gain by taking account of each others’ opinions as well as by considering direct evidence.

In addition to direct evidence, there are also indirect mechanisms by which agents receive feedback on the quality of beliefs. For example, when agents make decisions and take actions based on their beliefs, they may receive some form of reward or payoff. In such cases, it is reasonable to assume that the higher the quality of an agent’s beliefs, i.e. the closer the beliefs are to the true state of the world, the higher the payoff that the agent will receive on average. Here we investigate a scenario in which the quality of an agent’s beliefs influences their visibility in the consensus building process. This is studied in simulation experiments in which interactions between agents are guided by the quality of their beliefs, so that individuals holding higher quality opinions are more likely to be selected to combine their beliefs.

The remainder of the paper is structured as follows. The next section gives an overview of related work in this area. Then we introduce a propositional model of belief, which incorporates both vagueness and uncertainty, and proposes a combination operator for generating a compromise between two distinct beliefs. A set of simulation experiments are then described, in which agents interact at random and apply the combination operator, provided that they hold sufficiently consistent beliefs. Next, we combine random agent interactions and consensus formation with belief updating, based on direct evidence about the true state of the world. After this, we describe simulation experiments in which agent interactions are dependent on the quality of their beliefs. Finally, we present some conclusions and discuss possible future directions.

2 Background and related work

A number of studies in the opinion dynamics literature exploit a third truth state to aid convergence and also to mitigate the effect of a minority of highly opinionated individuals. For example, de la Lama et al. (2012) and Vazquez and Redener (2004) study scenarios in which interactions only take place between agents with a clear viewpoint and undecided agents. Alternatively, Balenzuela et al. (2015) define the three truth states by applying a partitioning threshold to an underlying real value. Updating is pairwise between agents and takes place incrementally on the real values, except that the magnitude and sign of the increments depends on the current truth states of the agents involved. An alternative pairwise three-valued operator is proposed by Perron et al. (2009), and is applied directly to truth states. In particular, this operator assigns the third truth state as a compromise between two opinions with strictly opposing truth values. The logical properties of this operator and its relationship to other similar aggregation functions are investigated by Lawry and Dubois (2012). For a language with a single proposition and assuming unconstrained random interactions between individuals, Perron et al. proves convergence to a single shared Boolean opinion. This framework is extended by Crosscombe and Lawry (2015) to languages with multiple propositions and to include a form of bounded confidence (see Hegselmann & Krause, 2002), in which interactions only take place between individuals with sufficiently consistent opinions. Furthermore, Crosscombe and Lawry (2015) also investigate convergence when the selection of agents is guided by a measure of the quality of their opinions and shows that the average quality of opinions across the population is higher at steady state than at initialization.

One common feature of most of these studies is that, either explicitly or implicitly, they interpret the third truth value as meaning ‘uncertain’ or ‘unknown’. In contrast, as stated in our introduction, we intend the middle truth value to refer to borderline cases resulting from the underlying vagueness of the language. So, for example, given the proposition ‘Ethel is short’, the intermediate truth value means that Ethel’s height is on the borderline between short and not short, rather than meaning that Ethel’s height is unknown. This approach allows us to distinguish between vagueness and uncertainty, so that, for instance, based on their knowledge of Ethel’s height, agents could be certain that she is borderline short. A more detailed analysis of the difference between these two possible interpretations of the third truth state is given by Ciucci, Dubois, and Lawry (2014).

The idea of bounded confidence (Deffuant, Amblard, Weisbuch, & Faure, 2002; Hegselmann & Krause, 2002) has been proposed as a mechanism by which agents limit their interactions with others, so that they only combine their beliefs with individuals holding opinions that are sufficiently similar to their current view. A version of bounded confidence is also used in our proposed model, where agents each measure the relative inconsistency of their beliefs with those of others, and are then only willing to combine beliefs with agents whose inconsistency measure is below a certain threshold.

The aggregation of uncertain beliefs in the form of a probability distribution over some underlying parameter has been widely studied with work on opinion pooling dating back to Stone (2004) and DeGroot (1974). Usually the aggregate of a set of opinions takes the form of a weighted linear combination of the associated probability distributions. However, the convergence of alternative opinion pooling functions has been studied by Hegselmann and Krause (2005) and axiomatic characterizations of different operators are given by Dietrich and List (2016). All of these approaches assume Boolean truth states; indeed, there are very few studies in this context that combine probability with a three-valued truth model. One such is that of Cho and Swami (2014), who adopt a model of beliefs in the form of Dempster–Shafer functions. The combination operators proposed by Cho and Swami, however, are quite different from those described in this paper and result in quite different limiting behaviour. The operator investigated in this paper was first proposed by Lawry and Dubois (2012) as an extension of the approach of Perron et al. (2009) to take account of probabilistic uncertainty; to our knowledge, it has not, up to this point, been studied in an agent-based setting. Hence, in contrast with the work of Lawry and Dubois (2012), the focus of this paper is on the system-level behaviour of the proposed operator rather than on its theoretical properties.

3 A consensus operator for vague and uncertain beliefs

We consider a simple language consisting of n propositions $\mathcal{L}=\{p_1,\dots ,p_n\}$ . Each can have one of three truth values: 0, denoting false, $\frac{1}{2}$ , denoting borderline and 1, denoting true. A valuation of ℒ corresponds to an allocation of a truth value to each of the propositions. Consequently, a valuation is naturally represented as an n-dimensional vector $\mathbf{v}\in \{0,\frac{1}{2},1{\}}^n$ . We let $\mathbf{v}(p_i)$ denote the ith dimension of $\mathbf{v}$ as corresponding to the truth value of the proposition $p_i$ in the valuation $\mathbf{v}$ . In the absence of any uncertainty, we assume that an agent’s opinion is represented by a single valuation. For two agents with distinct and possibly conflicting opinions ${\mathbf{v}}_1,{\mathbf{v}}_2\in \{0,\frac{1}{2},1{\}}^n$ to reach a compromise position or consensus, we propose an operator introduced by Perron et al. (2009) and Lawry and Dubois (2012), and based on the truth table given in Table 1, which is applied to each proposition independently so that

$${\mathbf{v}}_1\odot {\mathbf{v}}_2=({\mathbf{v}}_1(p_1)\odot {\mathbf{v}}_2(p_1),\dots ,{\mathbf{v}}_1(p_n)\odot {\mathbf{v}}_2(p_n))$$

Table 1.

Truth table for the consensus operator.

⊙	1	$1/2$	0
1	1	1	$1/2$
$1/2$	1	$1/2$	0
0	$1/2$	0	0

The intuition behind the operator is as follows: in the case that the two agents disagree, if one agent has allocated a non-borderline truth value to $p_i$ , while the other has given $p_i$ a borderline truth value, then the non-borderline truth value is adopted in the agreed compromise. In other words, if one agent has a strong view about $p_i$ while the other is ambivalent, then they will both agree to adopt the strong viewpoint. In contrast, if both agents have strong but opposing views, i.e. with one valuation giving $p_i$ truth value 0 and the other 1, then they will agree on a compromise truth value of $\frac{1}{2}$ .

Here we extend this model to allow agents to hold opinions that are uncertain as well as vague. More specifically, an integrated approach to uncertainty and vagueness is adopted, in which an agent’s belief is characterized by a probability distribution w over $\{0,\frac{1}{2},1{\}}^n$ so that $w(\mathbf{v})$ quantifies the agent’s belief that $\mathbf{v}$ is the correct valuation of ℒ. This naturally generates lower and upper belief measures on ℒ, quantifying the agent’s belief that a given proposition is true and that it is not false respectively (Lawry & Tang, 2012). That is, for $p_i\in \mathcal{L}$ ¹

$$\underset{¯}{\mu }(p_i)=w(\{\mathbf{v}:\mathbf{v}(p_i)=1\})$$

and

$$\overline{\mu }(p_i)=w(\{\mathbf{v}:\mathbf{v}(p_i)\ne 0\})$$

The probability of each of the possible truth values for a proposition $p_i$ can be recaptured from the lower and upper belief measures, such that the probabilities that $p_i$ is true, borderline and false are given by $\underset{¯}{\mu }(p_i)$ , $\overline{\mu }(p_i)-\underset{¯}{\mu }(p_i)$ and $1-\overline{\mu }(p_i)$ , respectively. Hence, we can represent an agent’s belief by a vector of pairs of lower and upper belief values for each proposition as

$$\mathit{\mu }=((\underset{¯}{\mu }(p_1),\overline{\mu }(p_1)),\dots ,(\underset{¯}{\mu }(p_n),\overline{\mu }(p_n)))$$

Here we let $\mathit{\mu }({\mathbf{p}}_{\mathbf{i}})$ denote $(\underset{¯}{\mu }(p_i),\overline{\mu }(p_i))$ , the pair of lower and upper belief values for $p_i$ . In the case that a belief $\mathit{\mu }$ gives probability zero to the borderline truth value for every proposition in ℒ, so that $\underset{¯}{\mu }(p_i)=\overline{\mu }(p_i)=\mu (p_i)$ for $i=1,\dots ,n$ , then we call $\mathit{\mu }$ a crisp belief.

The following definition expands the consensus operation ⊙ from three-valued valuations to this more general representation framework.

Definition 1. Consensus operator for belief pairs.

$$\begin{array}{l}{\mathit{\mu }}_{\mathbf{1}}\odot {\mathit{\mu }}_{\mathbf{2}}=(({\underset{\_}{\mu }}_1\odot {\underset{\_}{\mu }}_2(p_1),{\overline{\mu }}_1\odot {\overline{\mu }}_2(p_1)),\dots ,\\ ({\underset{\_}{\mu }}_1\odot {\underset{\_}{\mu }}_2(p_n),{\overline{\mu }}_1\odot {\overline{\mu }}_2(p_n)))\end{array}$$

where

$$\begin{array}{cc}\multicolumn{1}{c}{{\underset{¯}{\mu }}_1\odot {\underset{¯}{\mu }}_2(p_i)=}& {\underset{¯}{\mu }}_1(p_i)\times {\overline{\mu }}_2(p_i)+{\overline{\mu }}_1(p_i)\times {\underset{¯}{\mu }}_2(p_i)\hfill \\ \multicolumn{1}{c}{}& -{\underset{¯}{\mu }}_1(p_i)\times {\underset{¯}{\mu }}_2(p_i)\hfill \end{array}$$

and

$$\begin{array}{cc}\multicolumn{1}{c}{{\overline{\mu }}_1\odot {\overline{\mu }}_2(p_i)=}& {\underset{¯}{\mu }}_1(p_i)+{\underset{¯}{\mu }}_2(p_i)+{\overline{\mu }}_1(p_i)\times {\overline{\mu }}_2(p_i)\hfill \\ \multicolumn{1}{c}{}& -{\overline{\mu }}_1(p_i)\times {\underset{¯}{\mu }}_2(p_i)-{\underset{¯}{\mu }}_1(p_i)\times {\overline{\mu }}_2(p_i)\hfill \end{array}$$

If ${\mathit{\mu }}_1$ and ${\mathit{\mu }}_2$ are generated by the probability distributions $w_1$ and $w_2$ on $\{0,\frac{1}{2},1{\}}^n$ , respectively, then ${\mathit{\mu }}_1\odot {\mathit{\mu }}_2$ corresponds to the lower and upper measures generated by the following combined probability distribution on $\{0,\frac{1}{2},1{\}}^n$ (Lawry & Dubois, 2012)

$$w_1\odot w_2(\mathbf{v})=\sum _{{\mathbf{v}}_1,{\mathbf{v}}_2:{\mathbf{v}}_1\odot {\mathbf{v}}_2=\mathbf{v}}{w}_1({\mathbf{v}}_1)\times w_2({\mathbf{v}}_2)$$

In other words, assuming that the two agents are independent, all pairs of valuations supported by the two agents are combined using the consensus operator for valuations and then aggregated. Interestingly, this operator can be reformulated as a special case of the union combination operator in Dempster–Shafer theory (see Shafer, 1976) proposed by Dubois and Prade (1988). To see this, notice that, given a probability distribution w on $\{0,\frac{1}{2},1\}$ , we can generate a Dempster–Shafer mass function m on the power set of $\{0,1\}$ for each proposition $p_i$ such that

$$\begin{array}{c}m(\{1\})=w(\{\mathbf{v}:\mathbf{v}(p_i)=1\})=\underset{¯}{\mu }(p_i)\hfill \\ m(\{0\})=w(\{\mathbf{v}:\mathbf{v}(p_i)=0\})=1-\overline{\mu }(p_i)\hfill \\ m(\{0,1\})=w(\{\mathbf{v}:\mathbf{v}(p_i)=\frac{1}{2}\})=\overline{\mu }(p_i)-\underset{¯}{\mu }(p_i)\hfill \end{array}$$

In this reformulation then, the lower and upper measures $\underset{¯}{\mu }(p_i)$ and $\overline{\mu }(p_i)$ correspond to the Dempster–Shafer belief and plausibility of $\{1\}$ , as generated by m, respectively. Now, in this context, the union combination operator is defined as follows. Let $m_1$ and $m_2$ be two mass functions generated as before by probability distributions $w_1$ and $w_2$ . Also let c be a set combination function defined as

$$c(A,B)=\{\begin{array}{c}A\cap B:A\cap B\ne \varnothing \hfill \\ \multicolumn{1}{c}{A\cup B:\mathrm{otherwise}}\end{array}$$

Then the combination of $m_1$ and $m_2$ is defined by

$$m_1\odot m_2(D)=\sum _{A,B\subseteq \{0,1\}:c(A,B)=D}{m}_1(A)\times m_2(B)$$

The belief and plausibility of $\{1\}$ generated by $m_1\odot m_2$ then correspond to ${\underset{¯}{\mu }}_1\odot \underset{¯}{\mu }(p_i)$ and ${\overline{\mu }}_1\odot \overline{\mu }(p_i)$ , respectively, as given in Definition 1.

Example 1. Suppose two agents have the following beliefs about proposition $p_i$ : ${\mathit{\mu }}_1(p_i)=(0.6,0.8)$ and ${\mathit{\mu }}_2(p_i)=(0.4,0.7)$ . The associated probability distributions on valuations, $w_1$ and $w_2$ , are then such that

$$\begin{array}{c}{w}_1(\{\mathbf{v}:\mathbf{v}(p_i)=1\})=0.6\hfill \\ w_1\left(\{\mathbf{v}:\mathbf{v}(p_i)=\frac{1}{2}\}\right)=0.8-0.6=0.2\hfill \\ w_1(\{\mathbf{v}:\mathbf{v}(p_i)=0\})=1-0.8=0.2\hfill \end{array}$$

and

$$\begin{array}{c}{w}_2(\{\mathbf{v}:\mathbf{v}(p_i)=1\})=0.4,\hfill \\ w_2\left(\{\mathbf{v}:\mathbf{v}(p_i)=\frac{1}{2}\}\right)=0.7-0.4=0.3,\hfill \\ w_2(\{\mathbf{v}:\mathbf{v}(p_i)=0\})=1-0.7=0.3\hfill \end{array}$$

From this, we can generate a probability table (Table 2). Here, the corresponding truth values are generated as in Table 1 and the probability values in each cell are the product of the associated row and column probability values. From this table, we can then determine the consensus belief in $p_i$ by taking the sum of the probabilities of the cells with truth value 1 to give the lower measure and the sum of the probabilities of the cells with truth values of either 1 or $\frac{1}{2}$ to give the upper measure. That is

$$\begin{array}{c}{\underset{¯}{\mu }}_1\odot {\underset{¯}{\mu }}_2(p_i)=0.24+0.08+0.18=0.5\hfill \\ {\overline{\mu }}_2\odot {\overline{\mu }}_2(p_i)=0.24+0.08+0.18+0.18+0.06+0.08\hfill \\ =0.82\hfill \end{array}$$

Table 2.

Probability table for the consensus operator.

⊙	$1:0.6$	$\frac{1}{2}:0.2$	$0:0.2$
$1:0.4$	$1:0.24$	$1:0.08$	$\frac{1}{2}:0.08$
$\frac{1}{2}:0.3$	$1:0.18$	$\frac{1}{2}:0.06$	$0:0.06$
$0:0.3$	$\frac{1}{2}:0.18$	$0:0.06$	$0:0.06$

We now introduce three measures that will subsequently be used to analyse the behaviour of multi-agent systems applying the operator given in Definition 1.

Definition 2. A measure of vagueness.

The degree of vagueness of the belief $\mathit{\mu }$ is given by

$$\frac{1}{n}\sum _{i=1}^n(\overline{\mu }(p_i)-\underset{¯}{\mu }(p_i))$$

Definition 2 is simply the probability of the truth value $\frac{1}{2}$ averaged across the n propositions in ℒ. Since, in this model, vagueness is associated with borderline truth values, this provides an intuitive measure of the degree of vagueness of an opinion. Accordingly, the most vague belief has $(\underset{¯}{\mu }(p_i),\overline{\mu }(p_i))=(0,1)$ for $i=1,\dots ,n$ .

Definition 3. A measure of uncertainty.

The entropy of the belief $\mathit{\mu }$ is given by

$$\frac{1}{n}\sum _{i=1}^{n}H(p_i)$$

where

$$\begin{array}{cc}\multicolumn{1}{c}{H(p_i)=}& -\underset{¯}{\mu }(p_i)\underset{2}{\log }(\underset{¯}{\mu }(p_i))\hfill \\ \multicolumn{1}{c}{}& -(\overline{\mu }(p_i)-\underset{¯}{\mu }(p_i))\underset{2}{\log }(\overline{\mu }(p_i)-\underset{¯}{\mu }(p_i))\hfill \\ \multicolumn{1}{c}{}& -(1-\overline{\mu }(p_i))\underset{2}{\log }(1-\overline{\mu }(p_i))\hfill \end{array}$$

Definition 3 corresponds to the entropy of the marginal distributions on $\{0,\frac{1}{2},1\}$ , averaged across the n propositions. Hence, according to this measure, the most uncertain belief allocates probability $\frac{1}{3}$ to each of the truth values for each proposition so that

$$\mathit{\mu }=\mathbf{(}\mathbf{(}\frac{1}{3},\frac{2}{3}\mathbf{)},\dots ,\mathbf{(}\frac{1}{3},\frac{2}{3}\mathbf{)}\mathbf{)}$$

The most certain beliefs then correspond to those for which for every proposition $(\underset{¯}{\mu }(p_i),\overline{\mu }(p_i))=(0,0)$ , $(0,1)$ or $(1,1)$ .

Definition 4. A measure of inconsistency.

The degree of inconsistency of two beliefs ${\mathit{\mu }}_1$ and ${\mathit{\mu }}_2$ is given by

$$\frac{1}{n}\sum _{i=1}^n({\underset{¯}{\mu }}_1(p_i)\times (1-{\overline{\mu }}_2(p_i))+(1-{\overline{\mu }}_1(p_i))\times {\underset{¯}{\mu }}_2(p_i))$$

Definition 4 is the probability of a direct conflict between the two agents’ beliefs, i.e. with agent 1 allocating the truth value 1 and agent 2 the truth value 0 or vice versa, this being then averaged across all n propositions.

4 Simulation experiments with random selection of agents

We now describe simulation experiments in which pairs of agents are selected to interact at random. A model of bounded confidence is applied according to which, for each selected pair of agents the consensus operation (Definition 1) is applied if and only if the measure of inconsistency between their beliefs, as given in Definition 4, does not exceed a threshold parameter $\gamma \in [0,1]$ . Notice that with $\gamma =0$ we have a very conservative model in which only entirely consistent beliefs can be combined, while for the case that $\gamma =1$ we have a model that is equivalent to a totally connected interaction graph, whereby any pair of randomly selected agents may combine their beliefs. In the following, results are presented for a population of 1000 agents and for the language sizes $|\mathcal{L}|\in \{1,3,5\}$ . Agents’ beliefs are initialized by sampling at random from the space of all possible beliefs $\{(x,y)\in [0,1{]}^2:x\le y{\}}^n$ . Each run of the simulation is terminated after $50,000$ iterations and the results are averaged over 100 independent runs. (We found $50,000$ iterations sufficient to allow simulations to converge across a range of parameter settings.)

Figure 1 shows that the mean number of unique beliefs after $50,000$ iterations decreases with $\gamma$ and that for $\gamma \ge 0.5$ there is, on average, a single belief shared across the population. Furthermore, Figure 2 shows that the vagueness of beliefs, as given in Definition 2, averaged both across the different agents and across the independent simulation runs, also decreases with $\gamma$ , so that for $\gamma \ge 0.5$ the population has converged to crisp beliefs, i.e. those with a vagueness measure value of 0. Similarly, from Figure 3 we can see that the entropy of beliefs, as given by Definition 3, decreases with $\gamma$ , and that for $\gamma \ge 0.5$ the population hold beliefs with mean entropy 0 at the end of the simulation. Hence, summarizing Figures 1 to 3, we have that, provided the consistency restrictions are sufficiently relaxed, i.e. for $\gamma \ge 0.5$ , then a population with beliefs initially allocated at random and with random interactions will converge to a single belief that is both crisp and certain. Unsurprisingly, given the random nature of the agent interactions, the $2^n$ beliefs of this form occur with a uniform distribution across the 100 independent runs of the simulation.

Figure 1.

Number of unique beliefs after $50,000$ iterations for varying inconsistency thresholds $\gamma$ and various language sizes $|\mathcal{L}|$ .

Figure 2.

Average vagueness after $50,000$ iterations for varying inconsistency thresholds $\gamma$ and various language sizes $|\mathcal{L}|$ .

Figure 3.

Average entropy after $50,000$ iterations for varying inconsistency thresholds $\gamma$ and various language sizes $|\mathcal{L}|$ .

In addition to the overall consensus reached between agents when $\gamma \ge 0.5$ , intermediate values of $\gamma$ between 0.15 and 0.35 tend to result in a population with highly polarized opinions. To see this, consider Figure 4, which shows the average pairwise inconsistency measure value between agents at the end of this simulation and plotted against $\gamma$ . For example, consider the case when $|\mathcal{L}|=1$ , shown as the full black line in Figures 1 to 4. In this case, we see that the mean inconsistency value is a maximum of 0.5 at around $\gamma =0.28$ . Furthermore, from Figures 1 to 3, we see that for this value of $\gamma$ the average number of unique beliefs, vagueness and entropy are all relatively low. Consequently, we are seeing a polarization of opinions, where individuals hold a small number of highly inconsistent beliefs that are also relatively crisp and certain. Such behaviour, while still present, is less pronounced for language sizes $|\mathcal{L}|=3$ and 5. This may be because, since Definition 4 is an average of inconsistency values across the propositions in ℒ, increasing the language size reduces the variance of the inconsistency values in the initial population. Furthermore, as $|\mathcal{L}|$ increases, the distribution of inconsistency values is approximately normal with mean $\frac{2}{9}$ . Hence, for $\gamma \ge \frac{2}{9}$ , the probability that a randomly selected pair of agents will have an inconsistency value exceeding $\gamma$ decreases as $|\mathcal{L}|$ increases. This will in turn increase the probability of agreement in any interaction, reducing the likelihood of opinion polarization for $\gamma \ge \frac{2}{9}$ .

Figure 4.

Average pairwise inconsistency after $50,000$ iterations for varying inconsistency thresholds $\gamma$ and various language sizes $|\mathcal{L}|$ .

5 Simulation experiments involving consensus formation and belief updating

Hegselmann and Krause (2005) investigated an opinion model in which agents receive direct evidence about the state of the world, perhaps from an ongoing measurement process, as well as pooling the opinion of others with similar beliefs. Their original model involved real valued beliefs but has been adapted by Reigler and Douven (2009) to the case in which beliefs and evidence are theories in a propositional logic language. The fundamental question under consideration is whether or to what extent dialogue between individuals, for example scientists, helps them to find the truth, or whether they are instead better off simply to wait until they receive direct evidence. In this section, we investigate this question in the context of vague and uncertain beliefs, where consensus building is modelled using the combination operator in Definition 1. Direct evidence is then provided to the population at random instances when individuals are told the truth value of a proposition. These agents then update their beliefs by adopting a compromise position between their previous opinions and the evidence provided.

We assume that the true state of the world is a Boolean valuation ${\mathbf{v}}^{*}$ on ℒ so that ${\mathbf{v}}^{*}(p_i)\in \{0,1\}$ for $i=1,\dots ,n$ . Now, given the discussion earlier in this paper about interpreting the third truth value as meaning ‘borderline’, this is clearly a simplification from that perspective. For example, consider the proposition ‘Ethel is short’; an experiment could involve measuring Ethel’s height according to some mechanism, and then comparing it with the experimenter’s definition of the term ‘short’ to determine the truth value of the proposition. If that definition is three-valued, the outcome of the experiment could well be to identify a borderline truth value for the proposition. However, the convention in science is to establish an agreed crisp definition of all the terms used to express a hypothesis so that the resulting proposition is falsifiable. This would then be consistent with our identification of the true state of the world with a Boolean valuation. In the following definition we propose a measure of belief quality that quantifies the similarity of an agent’s beliefs to the true state of the world. This will subsequently be used to assess the extent to which the population has converged to the truth. Furthermore, it will also be employed as a mechanism for providing indirect information about the state of the world.

Definition 5. A quality measure.

Let $f:L\to \{-1,1\}$ be such that $f(p_i)=2{\mathbf{v}}^{*}(p_i)-1$ is the payoff for believing that $p_i$ has truth value 1 and $-f(p_i)$ is the payoff for believing that the truth value of $p_i$ is 0. Furthermore, it is always assumed that believing that $p_i$ has truth value $\frac{1}{2}$ has payoff 0. Then we define the quality or payoff for the belief $\mathit{\mu }$ by

$$\sum _{i=1}^n(f(p_i)(\underset{¯}{\mu }(p_i)+\overline{\mu }(p_i)-1))$$

Notice that

$$\begin{array}{c}f(p_i)(\underset{¯}{\mu }(p_i)+\overline{\mu }(p_i)-1)=\hfill \\ f(p_i)\underset{¯}{\mu }(p_i)+(-f(p_i))(1-\overline{\mu }(p_i))\hfill \end{array}$$

corresponding to agents’ expected payoff from their beliefs about proposition $p_i$ . Definition 5 then takes the sum of this expected payoff across the propositions in ℒ.

The simulations consist of 1000 agents with beliefs initially picked at random from $\{(x,y)\in [0,1{]}^2:x\le y{\}}^n$ , as before. Furthermore, the true state of the world ${\mathbf{v}}^{*}$ is picked at random from $\{0,1{\}}^n$ prior to the simulation and the payoff f is calculated as in Definition 5. Each run of the simulation is terminated after $50,000$ iterations and the results are averaged over 100 runs. At each iteration, two agents are selected at random and apply the consensus operator (Definition 1) provided that the inconsistency level of their current beliefs does not exceed $\gamma$ . Furthermore, at each iteration there is a fixed $\alpha \%$ chance of direct evidence being presented to the population. In the case that it is, an agent is selected at random and told the value of ${\mathbf{v}}^{*}(p_i)$ for some proposition also selected at random from those in ℒ. The agent’s beliefs are then updated from $\mathit{\mu }$ to $\mathit{\mu }\prime$ , where

$$\mathit{\mu }\prime =\mathit{\mu }\odot ((0,1),\dots ,(v^{*}(p_i),{\mathbf{v}}^{*}(p_i)),\dots ,(0,1)\mathbf{)}$$

In other words, the agent adopts a new set of beliefs formed as a compromise between previously held beliefs and the evidence, the latter being interpreted as a set of beliefs where $\mathit{\mu }(p_i)=({\mathbf{v}}^{*}(p_i),{\mathbf{v}}^{*}(p_i))$ and $\mathit{\mu }(p_j)=(0,1)$ for $j\ne i$ . That is, they form a consensus with an alternative opinion that is certain about the truth value of $p_i$ and is neutral about the other propositions. Notice that in this case it follows from Definition 1 that $\mathit{\mu }\prime (p_i)=(\overline{\mathit{\mu }}(p_1),1)$ if ${\mathbf{v}}^{*}(p_i)=1$ , $\mathit{\mu }\prime (p_i)=(0,\underset{¯}{\mathit{\mu }}(p_i))$ if ${\mathbf{v}}^{*}(p_i)=0$ and $\mathit{\mu }\prime (p_j)=\mathit{\mu }(p_j)$ for $j\ne i$ . The combined consensus and evidential belief updating approach can then be compared with simulations in which only this belief updating model is applied and in which there is no consensus building.

In this section, we focus on evidence rates of $\alpha =5,15$ and 30% and we assume that the language size is $|\mathcal{L}|=5$ . For these parameter settings, Figure 5 shows that for $\gamma \ge 0.4$ , all three cases in which evidential updating is combined with consensus formation converge on a shared belief across the population. Furthermore, the higher the evidence rate $\alpha$ , the greater the convergence for any given threshold value $\gamma$ . It is also clear from Figure 5 that combining consensus building with evidential updating leads to much better convergence than evidence-based updating alone. For instance, we see that for evidential updating alone it is only with an evidence rate of 30% that there is a large reduction in the number of distinct beliefs in the population after $50,000$ iterations, with the population still containing over 900 different opinions for both the 5% and 15% rates. Furthermore, Figure 6 shows a typical trajectory for the average number of unique beliefs against iterations when $\gamma =0.8$ . Notice that after $25,000$ iterations all three of the combined models have converged to a single shared belief. By contrast, the evidence-only approaches have still not converged after $50,000$ iterations, where even with a 30% evidence rate there are still over 600 distinct opinions remaining in the population.

Figure 5.

Number of unique beliefs after $50,000$ iterations for varying inconsistency thresholds $\gamma$ , $|\mathcal{L}|=5$ and evidence rates $\alpha =5,15$ and 30%. Solid lines refer to evidential updating combined with consensus building while dotted lines refer to evidential updating only.

Figure 6.

Number of unique beliefs over $50,000$ iterations for $\gamma =0.8$ , $|\mathcal{L}|=5$ and evidence rates $\alpha =5,15$ and 30%. Solid lines refer to evidential updating combined with consensus building while dotted lines refer to evidential updating only.

Taken together with Figure 5, Figures 7 and 8 show that, assuming a sufficiently high threshold value $\gamma \ge 0.4$ , the combined consensus building and updating approach results in convergence to a shared belief that is both crisp and certain. Again, increasing the evidence rate leads to a reduction in both average vagueness and average entropy for any given threshold value and evidence-based updating alone results in much higher values for the same evidence rate. The overall convergence of the population is also shown by the average pairwise inconsistency values in Figure 9. The convergence of the combined approach to a shared opinion for all evidence rates and thresholds $\gamma \ge 0.4$ is reflected in a zero average inconsistency level for this range of parameters. Notice, however, that, for all evidence rates, the average inconsistency for the combined approach has a peak value in the range $0<\gamma <0.4$ , suggesting that there is some polarization of opinion for thresholds in this range. For evidence updating, only the level of inconsistency is relatively higher than for the combined approach, for all evidence rates, suggesting that there is a much higher level of disagreement remaining between agents after $50,000$ iterations. Finally, Figure 10 shows the average payoff values calculated as in Definition 5 and given as a percentage of the maximum possible value, in this case, 5. These values reflect the extent to which the population have converged to a set of beliefs close to the true state of the world. For each of the three evidence rates, given a sufficiently high threshold value, the combined approach results in an average payoff that is significantly higher than for evidential updating alone. Indeed for a 30% evidence rate and $\gamma \ge 0.3$ , the combination of consensus building and belief updating results in close to the maximum payoff value on average, i.e. the population has learnt the state of the world with an average accuracy of close to 100%.

Figure 7.

Average vagueness after $50,000$ iterations for varying inconsistency thresholds $\gamma$ , $|\mathcal{L}|=5$ and evidence rates $\alpha =5,15$ and 30%. Solid lines refer to evidential updating combined with consensus building while dotted lines refer to evidential updating only.

Figure 8.

Average entropy after $50,000$ iterations for varying inconsistency thresholds $\gamma$ , $|\mathcal{L}|=5$ and evidence rates $\alpha =5,15$ and 30%. Solid lines refer to evidential updating combined with consensus building while dotted lines refer to evidential updating only.

Figure 9.

Average pairwise inconsistency after $50,000$ iterations for varying inconsistency thresholds $\gamma$ , $|\mathcal{L}|=5$ and evidence rates $\alpha =5,15$ and 30%. Solid lines refer to evidential updating combined with consensus building while dotted lines refer to evidential updating only.

Figure 10.

Average payoff after $50,000$ iterations for varying inconsistency thresholds $\gamma$ , $|\mathcal{L}|=5$ and evidence rates $\alpha =5,15$ and 30%. Solid lines refer to evidential updating combined with consensus building while dotted lines refer to evidential updating only.

6 Simulation experiments with agent selection influenced by belief quality

In this section, we consider a scenario in which agents receive indirect feedback about the accuracy of their beliefs in the form of payoff or reward obtained as a result of actions that they have taken on the basis of these beliefs. Furthermore, we assume that the closer that an agent’s beliefs are to the actual state of the world then the higher their rewards will be, on average. Hence, we use the payoff measure given in Definition 5 as a proxy for this process so that agent selection in the consensus building process is guided by the payoff or quality measure of the agent’s beliefs. More specifically, we now investigate an agent-based system in which pairs of agents are selected for interaction with a probability that is proportional to the product of the quality of their respective beliefs. For modelling societal opinion dynamics, this captures an assumption that better performing agents, i.e. those with higher payoff, are more likely to interact in a context in which both parties will benefit from reaching an agreement. In biological systems, there are examples of a similar quality effect on distributed decision making. For instance, honeybee swarms collectively choose between alternative nesting sites by means of a dance in which individual bees indicate the direction of the site that they have just visited (List, Elsholtz, & Seeley, 2009). The duration of the dance is dependant on the quality of the site and this in turn affects the likelihood that the dancer will influence other bees. Artificial systems can, of course, be designed so that interactions are guided by quality, provided that a suitable measure of the latter can be defined, as is typically the case in evolutionary computing.

We now describe the results from running agent-based simulations mainly following the same template as before but with an important difference. Instead of being selected at random, agents were instead selected for interaction with probability proportional to the quality value of their beliefs, as given in Definition 5. The true state of the world ${\mathbf{v}}^{*}$ was chosen at random from $\{0,1{\}}^n$ prior to running the simulation and the payoff function f was then determined as in Definition 5. As in the previous sections, the population consisted of 1000 agents with initial beliefs selected at random from $\{(x,y)\in [0,1]:x\le y{\}}^n$ . All results in this section relate to the language size $|\mathcal{L}|=5$ .

Figure 11 shows the mean number of unique beliefs for the consensus operator after $50,000$ iterations plotted against the inconsistency threshold $\gamma$ . For $\gamma \ge 0.5$ , applying the consensus operator results in the population of agents converging on a single shared belief. Figures 12 and 13 show the average vagueness and entropy of the beliefs held across the population of agents at the end of the simulation. In Figure 12, we see that, for $\gamma \ge 0.5$ , the beliefs resulting from applying the consensus operator are crisp. Figure 13 shows that the mean entropy values decreases as $\gamma$ increases, resulting in an average entropy of 0 for $\gamma \ge 0.5$ . Overall then, as before, for $\gamma \ge 0.5$ , the population of agents converge on a single shared belief, which is both crisp and certain. Figure 14 shows the average pairwise inconsistency of the population increases at lower threshold values prior to exceeding the mean inconsistency value of $\frac{2}{9}$ . For inconsistency thresholds $\gamma \ge 0.3$ , the average pairwise inconsistency decreases in line with the number of unique beliefs (seen in Figure 11) as the population converges towards a single shared belief.

Figure 11.

Number of unique beliefs after $50,000$ iterations for varying inconsistency thresholds $\gamma$ and $|\mathcal{L}|=5$ .

Figure 12.

Average vagueness after $50,000$ iterations for varying inconsistency thresholds $\gamma$ and $|\mathcal{L}|=5$ .

Figure 13.

Average entropy after $50,000$ iterations for varying inconsistency thresholds $\gamma$ and $|\mathcal{L}|=5$ .

Figure 14.

Average pairwise inconsistency after $50,000$ iterations for varying inconsistency thresholds $\gamma$ and $|\mathcal{L}|=5$ .

Figure 15 shows the average quality of beliefs (Definition 5) at the end of the simulation, plotted against $\gamma$ and given as a percentage of the maximum possible quality value. For $\gamma \ge 0.5$ , the consensus operator converges on a single shared crisp and certain belief with a quality value that is, on average, over 80% of the maximum. Hence, unlike the previous experiments, in which convergence can be to any of the $2^n$ crisp and certain beliefs at random, agent interactions guided by relative quality converge with higher probability to those beliefs amongst the $2^n$ that are the closest to the actual state of the world. In comparison with the direct-evidence scenario described earlier in this paper, we see that the payoff shown in Figure 15 is similar to that obtained when combining a 15% direct evidence rate with consensus building based on random interactions (see Figure 10).

Figure 15.

Average payoff after $50,000$ iterations for varying inconsistency thresholds $\gamma$ and $|\mathcal{L}|=5$ .

7 Conclusions

We have investigated consensus formation for a multi-agent system in which agents’ beliefs are both vague and uncertain. For this, we have adopted a formalism that combines three truth states according to probability, resulting in opinions that are quantified by lower and upper belief measures. A combination operator has been introduced, according to which agents are assumed to be independent and in which strictly opposing truth states are replaced with an intermediate borderline truth value. In simulation experiments, we have applied this operator to random agent interactions constrained by the requirement that agreement can only be reached between agents holding beliefs that are sufficiently consistent with each other. Provided that this consistency requirement is not too restrictive, the population of agents is shown to converge on a single shared belief that is both crisp and certain. Furthermore, if combined with evidence about the state of the world, either in a direct or indirect way, consensus building of this kind results in better convergence to the truth than evidential belief updating alone.

Overall, these results provide some evidence for the beneficial effects of allowing agents to hold beliefs that are both vague and uncertain, in the context of consensus building. However, we have only studied pairwise interactions between agents, while in the literature it is normally intended that pooling operators should be used to aggregate beliefs across a group of agents (DeGroot, 1974; Dietrich & List, 2016). Hence, future work should extend the operator in Definition 1 so as to allow more than two agents to reach agreement at any step of the simulation. Probabilistic pooling operators can also take account of different weights associated with the beliefs of different agents; it will be interesting to investigate whether this can be incorporated in our approach. Another avenue for future research is to consider noisy evidence. Evidential updating is rarely perfect and, for example, experiments can be prone to measurement errors. It would be interesting, therefore, to ask how the combined consensus building and updating approach described in this paper copes with such noise. In the longer term, the aim is to apply our approach to distributed decision making scenarios such as, for example, in swarm robotics.