# Mixed Deffuant Dynamics

Hsin-Lun Li<EMAIL_ADDRESS>
###### Abstract.

The original Deffuant model consists of a finite number of agents whose
opinion is a number in $[0,1]$. Two socially connected agents are uniformly
randomly selected at each time step and approach each other at a rate
$\mu\in[0,1/2]$ if and only if their opinions differ by at most some
confidence threshold $\epsilon>0$. In this paper, we consider a variant of the
Deffuant model, namely the mixed model, where the convergence parameter $\mu$
and the social relationship can vary over time. We investigate circumstances
under which asymptotic stability holds or a consensus can be achieved. Also,
we derive a nontrivial lower bound for the probability of consensus which is
independent of the number of agents.

###### Key words and phrases:

Mixed Deffuant dynamics, asymptotic stability, consensus, social network

###### 1991 Mathematics Subject Classification:

05C40, 05C90, 37N99, 60G42, 91C20, 91D25, 91D30, 93D50, 94C15

Hsin-Lun Li

##  1\. Introduction

The original Deffuant model comprises a finite number of agents whose opinion
is a number in $[0,1]$. Two socially connected agents are uniformly randomly
selected at each time step and approach each other at a rate $\mu\in[0,1/2]$
if and only if their opinions differ by at most some confidence threshold
$\epsilon>0$. Interpreting in graph, two types of graphs are involved–the
social graph and the opinion graph. The social graph depicts a social
relationship, such as a friendship, whereas the opinion graph indicates an
opinion relationship. Both graphs have a common vertex set in which each
vertex stands for an agent. The edge of the social graph exists if and only if
the two vertices are socially connected, whereas the edge of the opinion graph
exists if and only if the two vertices are at a distance of at most $\epsilon$
apart. Two vertices are neighbors if and only if the edge connecting the two
exists. The social relationship is assumed constant. The model is as follows:

$\begin{array}[]{rcl}\displaystyle
x_{i}(t+1)&=&x_{i}(t)+\mu(x_{j}(t)-x_{i}(t))\mathbbm{1}\\{\|x_{i}(t)-x_{j}(t)\|\leq\epsilon\\}\vspace{2pt}\\\
\displaystyle
x_{j}(t+1)&=&x_{j}(t)+\mu(x_{i}(t)-x_{j}(t))\mathbbm{1}\\{\|x_{i}(t)-x_{j}(t)\|\leq\epsilon\\}\end{array}$

where

$\begin{array}[]{l}\displaystyle x_{i}(t)=\hbox{opinion of agent $i$ at time
$t$},\vspace{2pt}\\\ \displaystyle\hbox{Agents}\ i\ \hbox{and}\ j\ \hbox{are
socially connected and selected at time}\ t,\vspace{2pt}\\\
\displaystyle\mu=\hbox{convergence parameter}.\end{array}$

The authors in [2] assume that the social graph is constant and connected and
demonstrate that asymptotic stability holds for the Deffuant model in all
finite dimensional real number systems. Now, we consider a variant of the
Deffuant model, namely the mixed model, where the opinion space can be high
dimensional, say $\mathbf{R^{d}}$, and the social relationship among all
agents and the convergence parameter can vary over time. That is, all agents
can decide their social relationship with each other and the two selected
social neighbors can decide their approach rate at all times. The mixed model
is as follows:

$\begin{array}[]{rcl}\displaystyle
x_{i}(t+1)&=&x_{i}(t)+\mu(t)(x_{j}(t)-x_{i}(t))\mathbbm{1}\\{\|x_{i}(t)-x_{j}(t)\|\leq\epsilon\\}\vspace{2pt}\\\
\displaystyle
x_{j}(t+1)&=&x_{j}(t)+\mu(t)(x_{i}(t)-x_{j}(t))\mathbbm{1}\\{\|x_{i}(t)-x_{j}(t)\|\leq\epsilon\\}\end{array}$

where

$\begin{array}[]{l}\displaystyle x_{i}(t)=\hbox{opinion of agent $i$ at time
$t$},\vspace{2pt}\\\ \displaystyle\hbox{Agents}\ i\ \hbox{and}\ j\ \hbox{are
socially connected and selected at time}\ t,\vspace{2pt}\\\
\mu(t)=\hbox{convergence parameter at time}\ t.\end{array}$

In particular, the mixed model reduces to the Deffuant model if the social
graph and convergence parameter are constant, i.e., $G(t)=G$ and $\mu(t)=\mu$
at all times. Say vertices $i$ and $j$ are opinion-connected at time $t$, or
edge $(i,j)$ is opinion-connected at time $t$ if
$\|x_{i}(t)-x_{j}(t)\|\leq\epsilon.$ Denote $G=(V,E)$ as a graph $G$ with
vertex set $V$ and edge set $E$. The social graph at time $t$ and the opinion
graph at time $t$ are

$G(t)=(V,E(t))\quad\hbox{and}\quad\mathscr{G}(t)=(V,\mathscr{E}(t))$

where

$\begin{array}[]{rcl}\displaystyle E(t)&=&\\{(i,j):\hbox{vertices}\ i\
\hbox{and}\ j\ \hbox{are socially connected}\\}\vspace{2pt}\\\
\displaystyle\mathscr{E}(t)&=&\\{(i,j):\|x_{i}(t)-x_{j}(t)\|\leq\epsilon\\}.\end{array}$

The opinion update occurs if and only if the selected social edge is opinion-
connected. Therefore, we define a _profile_ at time $t$ as the intersection of
a social graph and an opinion graph at time $t$, namely
$G(t)\cap\mathscr{G}(t)$. Note that the edges in $G(t)\cap\mathscr{G}(t)$ are
both opinion-connected and socially connected. Prior to showing asymptotic
stability holds for the mixed model, we introduce some terms. A graph is
$\delta$-_trivial_ if any two vertices are at a distance of at most $\delta$
apart. The _convex hull_ generated by
$v_{1},v_{2},\ldots,v_{n}\in\mathbf{R^{d}}$ is the smallest convex set
containing $v_{1},v_{2},\ldots,v_{n}$, i.e.,

$C(\\{v_{1},v_{2}\ldots,v_{n}\\})=\\{v:v=\sum_{i=1}^{n}\lambda_{i}v_{i}\
\hbox{where}\ (\lambda_{i})_{i=1}^{n}\ \hbox{is stochastic}\\}.$

The author in [1] has indicated that an opinion graph is nonincreasing and
preserves $\delta$-triviality for all $\delta>0$ over time.

##  2\. The model

######  Lemma 1.

For all $c\in\mathbf{R^{d}}$,

$\begin{array}[]{rcl}\displaystyle\|x_{i}(t+1)-c\|+\|x_{j}(t+1)-c\|&\leq&\|x_{i}(t)-c\|+\|x_{j}(t)-c\|,\vspace{2pt}\\\
\displaystyle\|x_{i}(t+1)-c\|+\|x_{j}(t+1)-c\|&\leq&\|x_{i}(t)-c\|+\|x_{j}(t)-c\|\vspace{2pt}\\\
&&-2\|x_{i}(t)-x_{i}(t+1)\|+2\|c_{ij}(t)-c\|\end{array}$

where $c_{ij}(t)=(x_{i}(t)+x_{j}(t))/2$.

###### Proof.

It is clear that the two inequalities hold if $(i,j)\in E(t)$ is not selected
at time $t$. Assume that $(i,j)\in E(t)$ is selected at time $t$, then,

$\displaystyle\|x_{i}(t+1)-c\|=\|(1-\mu(t))(x_{i}(t)-c)+\mu(t)(x_{j}(t)-c)\|$

therefore by the triangle inequality, we derive the first inequality. To show
the second inequality, applying the triangle inequality,

$\displaystyle\|x_{i}(t+1)-c\|$
$\displaystyle\leq\|x_{i}(t+1)-c_{ij}(t)\|+\|c_{ij}(t)-c\|$
$\displaystyle=\|x_{i}(t)-c_{ij}(t)\|-\|x_{i}(t)-x_{i}(t+1)\|+\|c_{ij}(t)-c\|.$

Also,

$\begin{array}[]{rcl}\displaystyle\|x_{i}(t)-c_{ij}(t)\|+\|x_{j}(t)-c_{ij}(t)\|&=&\|x_{i}(t)-x_{j}(t)\|\leq\|x_{i}(t)-c\|+\|x_{j}(t)-c\|,\vspace{2pt}\\\
\displaystyle\|x_{i}(t)-x_{i}(t+1)\|&=&\|x_{j}(t)-x_{j}(t+1)\|\end{array}$

therefore we have the second inequality. ∎

For all $c\in\mathbf{R^{d}}$, let

$Z_{c}(t)=\sum_{i\in V}\|x_{i}(t)-c\|.$

From Lemma 1, $Z_{c}(t)$ is nonincreasing with respect to $t$ and

$Z_{c}(t)-Z_{c}(t+1)\geq 2(\|x_{i}(t)-x_{i}(t+1)\|-\|c_{ij}(t)-c\|)$ (1)

for $(i,j)\in E(t)$ selected at time $t$. Let $\bar{B}(x,r)=\\{v:\|x-v\|\leq
r\\}$, a closed ball centered at $x$ of radius $r$. Next, we study
circumstances under which The distance between any two social and opinion
neighbors is at most $\delta$ in finite time for all $\delta>0$.

######  Theorem 2.

Assume that $\liminf_{t\to\infty}\mu(t)>0$. Then for all $\delta>0$, all
opinion edges of a profile are of length at most $\delta$ in finite time
almost surely, i.e.,

$\tau_{\delta}:=\inf\\{t\geq 0:\|x_{i}(t)-x_{j}(t)\|\leq\delta\ \hbox{for
all}\ (i,j)\in E(t)\cap\mathscr{E}(t)\\}<\infty\ \hbox{almost surely}.$

###### Proof.

If $E(t)$ is empty for some $t\geq 0$, then we are done. Assume that $E(t)$ is
nonempty for all $t\geq 0$. Since $\liminf_{t\to\infty}\mu(t)>0$, there is
$(u_{k})_{k\geq 0}\subset\mathbf{N}$ increasing such that
$\mu(u_{k})\geq\tilde{\mu}>0$ for some $\tilde{\mu}$ and for all $k\geq 0$.
Assume that this is not the case. Then, there are

$(t_{k})_{k\geq 0}\subset(u_{k})_{k\geq 0}\quad\hbox{and}\quad(i,j)\in
E(t_{k})\cap\mathscr{E}(t_{k})$

such that

$\|x_{i}(t_{k})-x_{j}(t_{k})\|>\delta\ \hbox{for all}\ k\geq 0.$

Let $E_{k}$ be the event that the edge $(i,j)$ is selected at time $k$. Then,
all $E_{t_{k}}$ are independent and

$\sum_{k\geq 0}P(E_{t_{k}})\geq\sum_{k\geq 0}1/\binom{|V|}{2}=\infty$

therefore by the second Borel-Cantelli Lemma,
$P(\limsup_{k\to\infty}E_{t_{k}})=1.$ Hence, there is $(s_{\ell})_{\ell\geq
0}\subset(t_{k})_{k\geq 0}$ such that $E_{s_{\ell}}$ holds for all $\ell\geq
0$. From (1),

$Z_{c}(s_{\ell})-Z_{c}(s_{\ell}+1)>2(\mu(s_{\ell})\delta-\|c_{ij}(s_{\ell})-c\|)\geq
2(\tilde{\mu}\delta-\|c_{ij}(s_{\ell})-c\|)\geq\tilde{\mu}\delta$

for all $c\in\bar{B}(c_{ij}(s_{\ell}),\tilde{\mu}\delta/2)$. Since
$C\big{(}(x_{i}(t))_{i\in V}\big{)}$ is bounded by $C\big{(}(x_{i}(0))_{i\in
V}\big{)}$, it can be covered by finitely many cubes of length
$\tilde{\mu}\delta/(2\sqrt{2})$, therefore existing a cube containing
infinitely many $c_{ij}(s_{\ell})$. Hence, there is
$I\subset(s_{\ell})_{\ell\geq 0}$ infinite with $\bigcap_{t\in
I}\bar{B}(c_{ij}(t),\tilde{\mu}\delta/2)$ containing some cube of length
$\tilde{\mu}\delta/(2\sqrt{2})$. Pick $c_{0}\in\bigcap_{t\in
I}\bar{B}(c_{ij}(t),\tilde{\mu}\delta/2)$,

$\infty>\sum_{t\in I}(Z_{c_{0}}(t)-Z_{c_{0}}(t+1))\geq\sum_{t\in
I}\tilde{\mu}\delta=\infty,\ \hbox{a contradiction}.$

∎

It turns out that any two social and opinion neighbors are at a distance of at
most $\delta$ apart in finite time as long as there are infinitely many times
that the two selected social neighbors approach each other at a rate no less
than some positive number. It follows that asymptotic stability holds for the
mixed model if the two selected social neighbors at all times approach each
other at a rate no less than some positive number.

######  Corollary 3.

Assume that $\inf_{t\geq 0}\mu(t)>0$. Then, all edges of a profile are of
length at most $\delta$ after some almost surely finite time for all
$\delta>0$, i.e.,

$\|x_{i}(t)-x_{j}(t)\|\leq\delta\ \hbox{for all}\ (i,j)\in
E(s)\cap\mathscr{E}(s)\ \hbox{for some}\ t\ \hbox{and for all}\ s\geq t.$

Therefore, asymptotic stability holds for the mixed model.

###### Proof.

Let $\mathscr{A}=\\{t\geq 0:E(t)\neq\varnothing\\}$. If $\mathscr{A}$ is
finite, then we are done. Assume that $\mathscr{A}$ is infinite and that there
is an edge $(i,j)$ of a profile of length larger than $\delta$ for infinitely
many times for some $\delta>0$. Let $\mu=\inf_{t\geq 0}\mu(t)$,

$\mathscr{B}=\\{t\in\mathscr{A}:\|x_{i}(t)-x_{j}(t)\|>\delta\\}\ \hbox{and}\
E_{k}=\\{(i,j)\ \hbox{is selected at time}\ k\\}.$

By the second Borel-Cantelli Lemma,

$\sum_{t\in\mathscr{B}}P(E_{t})\geq\sum_{t\in\mathscr{B}}1/\binom{|V|}{2}=\infty\quad\hbox{implies}\quad
P(\limsup_{t\in\mathscr{B},t\to\infty}E_{t})=1.$

Therefore, almost surely infinitely many $E_{t}$ hold for $t\in\mathscr{B}$,
say $(t_{k})_{k\geq 0}$. Similarly as the proof in Theorem 2, there is
$I\subset(t_{k})$ infinite with

$\bigcap_{t\in I}\bar{B}(c_{ij}(t),\mu\delta/2)\ \hbox{containing some cube of
length}\ \mu\delta/(2\sqrt{2}).$

Pick $c_{0}\in\bigcap_{t\in I}\bar{B}(c_{ij}(t),\mu\delta/2)$,

$\infty>\sum_{t\in I}(Z_{c_{0}}(t)-Z_{c_{0}}(t+1))\geq\sum_{t\in
I}\mu\delta=\infty,\ \hbox{a contradiction}.$

To show the asymptotic stability of $(x_{i})_{i\in V}$, let the convex hull of
a component $G$ be

$Cv(G)=C(\\{x_{j}:j\in V(G)\\}).$

All edges of a profile are of length at most $\delta/|V|$ after some time $t$
for all $\delta>0$. For all $s\geq t$ and $i\in V$, $x_{i}(s)\in Cv(G)$ for
some component $G$ of $G(s)\cap\mathscr{G}(s)$ and

$\operatorname{diam}(Cv(G))\leq(|V|-1)\delta/|V|<\delta.$

Therefore, the asymptotic stability holds for the mixed model. ∎

##  3\. Probability of consensus

Assume that all initial opinions $x_{i}(0)$, $i\in V$, are independent and
identically distributed random variables on the bounded convex opinion space
$\Delta\subset\mathbf{R^{d}}$, and let $X$ be the random variable with
distribution

$P(X\in B)=P(x_{i}(0)\in B)\ \hbox{for all}\ i\in V\ \hbox{and all Borel
sets}\ B\subset\Delta.$

Let $\mathbf{c}=\arg\inf_{c\in\mathbf{R^{d}}}\sup_{z\in\Delta}\|z-c\|$ be the
center of $\Delta$ and $\mathbf{r}=\sup_{z\in\Delta}\|z-\mathbf{c}\|$. Then,
$\mathbf{c}$ uniquely exists and $d/2\leq\mathbf{r}\leq\sqrt{3}d/2$ for
$d=\operatorname{diam}(\Delta)$. Let $\mathscr{C}$ be the collection of all
sample points that lead to a consensus, i.e.,

$\mathscr{C}=\\{\limsup_{t\to\infty}\max_{i,j\in
V}\|x_{i}(t)-x_{j}(t)\|=0\\}.$

Assume that the social graph is connected for infinitely many times. Define

$\displaystyle T_{\delta}=$ $\displaystyle\inf\\{t\geq
0:G(t)\cap\mathscr{G}(t)\ \hbox{is connected and all edges of}\
G(s)\cap\mathscr{G}(s)\ $ $\displaystyle\hskip 20.0pt\hbox{are of length at
most $\delta$ for all}\ s\geq t\\},$

the earliest time that a profile is connected, all edges of which are of
length at most $\delta$ afterward. Thus, $T_{\delta}$ is almost surely finite
if $\inf_{t\geq 0}\mu(t)>0$. The following lemma indicates circumstances under
which a consensus can be achieved.

######  Lemma 4.

Assume that $\inf_{t\geq 0}\mu(t)>0$ and $\epsilon>\mathbf{r}$. Then, there is
$\delta$ such that

$A=\\{\|x_{i}(T_{\delta})-\mathbf{c}\|\leq\epsilon-\mathbf{r}-\eta\ \hbox{for
some}\ i\in V\\}\subset\mathscr{C}\ \hbox{for all}\
0<\eta<\epsilon-\mathbf{r}.$

###### Proof.

Take $\delta=\eta/|V|$. For all $j\in V$, $\|x_{j}(T_{\delta})-c\|\leq r$
therefore by the triangle inequality,
$\|x_{i}(T_{\delta})-x_{j}(T_{\delta})\|\leq\epsilon-\eta$. Thus,
$(i,j)\in\mathscr{E}(T_{\delta})$. In particular,

$\|x_{i}(T_{\delta})-x_{j}(T_{\delta})\|\leq\delta\quad\hbox{if}\quad(i,j)\in
E(T_{\delta})\cap\mathscr{E}(T_{\delta}).$

We claim that $\|x_{j}(T_{\delta})-x_{k}(T_{\delta})\|\leq\delta$ for all
$(j,k)\in E(T_{\delta})$. For all $k\in V$, there is an $i,k$-path in
$G(T_{\delta})$, say $i=i_{0}i_{1}\ldots i_{n-1}i_{n}=k$, of length at most
$|V|-1$. Argue by induction that

$\|x_{i_{\ell}}(T_{\delta})-x_{i_{\ell-1}}(T_{\delta})\|\leq\delta\ \hbox{for
all}\ \ell=1,2,\ldots,n.$

Clearly, $\|x_{i_{1}}(T_{\delta})-x_{i_{0}}(T_{\delta})\|\leq\delta$. Suppose
that it is true for $\ell=1,2,\ldots,m-1$. Assume by contradiction that
$(i_{m},i_{m-1})\notin\mathscr{E}(T_{\delta})$. Then,
$\|x_{i_{m}}(T_{\delta})-x_{i_{m-1}}(T_{\delta})\|>\epsilon$. Thus, by the
triangle inequality,

$\displaystyle\|x_{i_{m}}(T_{\delta})-x_{i}(T_{\delta})\|$
$\displaystyle\geq\|x_{i_{m}}(T_{\delta})-x_{i_{m-1}}(T_{\delta})\|-\|x_{i_{m-1}}(T_{\delta})-x_{i_{m-2}}(T_{\delta})+\ldots+x_{i_{1}}(T_{\delta})-x_{i}(T_{\delta})\|$
$\displaystyle>\epsilon-(m-1)\delta>\epsilon-\eta,\ \hbox{a contradiction.}$

For all edges $(j,k)\in E(T_{\delta})$, we can always construct a path
starting from $i$ that contains $(j,k)$, therefore verifying the claim. Also,
via the triangle inequality and connectedness of $G(T_{\delta})$,

$\|x_{j}(T_{\delta})-x_{k}(T_{\delta})\|\leq(|V|-1)\delta<\eta<\epsilon\quad\hbox{for
all}\quad j,k\in V.$

An opinion graph preserves $\epsilon$-triviality; therefore
$G(s)\cap\mathscr{G}(s)=G(s)$ for all $s\geq T_{\delta}$. Also, a social graph
is connected for infinitely many times; hence $G(s)$ is connected for infinite
many $s\geq T_{\delta}$. From Corollary 3, a consensus is achieved eventually.
∎

It follows that the probability of consensus has a nontrivial lower bound if
the two selected social neighbors approach each other at a rate no less than
some positive number at all times.

######  Theorem 5.

Assume that $\inf_{t\geq 0}\mu(t)>0$ and $\epsilon>\mathbf{r}$. Then,

$P(\mathscr{C})\geq
1-\frac{\mathbf{E}(\|X-\mathbf{c}\|)}{\epsilon-\mathbf{r}}.$

In particular, $P(\mathscr{C})=1$ if
$\epsilon\geq\operatorname{diam}(\Delta)$.

###### Proof.

Via Lemma 4, there is $\delta$ such that

$A=\\{\|x_{i}(T_{\delta})-\mathbf{c}\|\leq\epsilon-\mathbf{r}-\eta\ \hbox{for
some}\ i\in V\\}\subset\mathscr{C}\ \hbox{for all}\
0<\eta<\epsilon-\mathbf{r}.$

Since $Z_{\mathbf{c}}(t)$, $t\geq 0$, is a bounded supermartingale and
$T_{\delta}$ is almost surely finite, by the optional stopping theorem and
conditional expectation restricting to $A^{c}$,

$\displaystyle|V|\ \mathbf{E}(\|X-\mathbf{c}\|)=\mathbf{E}(Z_{\mathbf{c}}(0))$
$\displaystyle\geq\mathbf{E}(Z_{\mathbf{c}}(T_{\delta}))$
$\displaystyle\geq\mathbf{E}(Z_{c}(T_{\delta})|A^{c})P(A^{c})\geq|V|(\epsilon-\mathbf{r}-\eta)P(A^{c})$

Therefore,

$P(\mathscr{C})\geq P(A)\geq
1-\frac{\mathbf{E}(\|X-\mathbf{c}\|)}{\epsilon-\mathbf{r}-\eta}.$

Letting $\eta\to 0$, we have

$P(\mathscr{C})\geq
1-\frac{\mathbf{E}(\|X-\mathbf{c}\|)}{\epsilon-\mathbf{r}}.$

∎

It turns out that the lower bound for the probability of consensus is
independent of the size and topology of a graph and the convergence rate, but
depends on the confidence threshold, the radius, the norm, the distribution of
an initial opinion and the center. In particular for the Deffuant model with
$\mu(t)=\mu$ at all times, $P(\mathscr{C})=P(\hbox{a consensus is achieved at
time $0$})$ if $\mu=0$; else $P(\mathscr{C})\geq
1-\mathbf{E}(\|X-\mathbf{c}\|)/(\epsilon-\mathbf{r})$. The following is a
demonstration of the probability of consensus given that $\inf_{t\geq
0}\mu(t)>0$, $\|\,\|$ is the Euclidean norm and $X$ is uniformly distributed
on the opinion space $\Delta$, denoted by $X=\operatorname{uniform}(\Delta)$.

######  Example 6.

For $\Delta=B(\vec{0},r)$, the open ball centered at $\vec{0}$ of radius $r$,
we have $\mathbf{c}=\vec{0}$, $\mathbf{r}=r$ and
$\|X-\vec{0}\|=\operatorname{uniform}\big{(}(0,r)\big{)}$, therefore

$P(\mathscr{C})\geq
1-\frac{r/2}{\epsilon-r}=\frac{2\epsilon-3r}{2\epsilon-2r}.$

Observe that $\Delta=[0,1]$ is equivalent to $\Delta=B(0,1/2)$, therefore
$P(\mathscr{C})\geq\frac{4\epsilon-3}{4\epsilon-2}.$ Observe that the larger
the confidence threshold is, the more likely a consensus can be achieved.

##  4\. Conclusion

For the mixed model, all agents can decide their social relationship with each
other, and the two selected social neighbors can decide their approach rate at
all times. Some social relationships, such as a friendship, may not last for
ever. The approach rate depicts the degree of cooperation among the two
selected social neighbors. The larger the approach rate is, the more likely
they cooperate. The variation of the social relation and the approach rate
over time for the mixed model is much closer to real world circumstances. It
turns out that asymptotic stability holds for the mixed model if the social
graph is connected for infinitely many times and the two selected social
neighbors approach each other at a rate no less than some positive number at
all times. Also, we derive a lower bound for the probability of consensus,
independent of the size and topology of a graph and the convergence parameter.

## References

  * [1] H Li,  Mixed Hegselmann-Krause Dynamics,  _Discrete and Continuous Dynamical Systems-B_ , (2021), https://arxiv.org/abs/2010.03050
  * [2] N Lanchier and H Li,  Probability of consensus in the multivariate Deffuant model on finite connected graphs,  _Electronic Communications in Probability_ , 25 (2020), https://doi.org/10.1214/20-ECP359


# Polite Emotional Dialogue Acts for Conversational Analysis
in Daily Dialog Data

Chandrakant Bothe
https://bothe.in
PhD, University of Hamburg
Chief AI Officer, Foviatech GmbH
<EMAIL_ADDRESS>

###### Abstract

Many socio-linguistic cues are used in the conversational analysis, such as
emotion, sentiment, and dialogue acts. One of the fundamental social cues is
politeness, which linguistically possesses properties useful in conversational
analysis. This short article presents some of the brief findings of polite
emotional dialogue acts, where we can correlate the relational bonds between
these socio-linguistics cues. We found that the utterances with emotion
classes Anger and Disgust are more likely to be impolite while Happiness and
Sadness to be polite. Similar phenomenon occurs with dialogue acts, Inform and
Commissive contain many polite utterances than Question and Directive.
Finally, we will conclude on the future work of these findings.

##  1 Introduction

Conversational analysis can potentially be enhanced with the help of
politeness socio-linguistic cues Danescu-Niculescu-Mizil et al. (2013) along
with other linguistic cues. It is also highlighted in the concluding remarks
of the PhD thesis Conversational Language Learning for Human-Robot Interaction
Bothe (2020). This article111This article is written and published by the
author in his own interest and capacity, without any responsibility and
conflict of interest of mentioned affiliation. focuses on a brief extension of
the experiments provided in the mentioned thesis, primarily by adding
linguistic politeness cues to conversational analysis along with emotion
states and dialogue acts.

In this brief experiment, we will explore DailyDialog dataset Li et al.
(2017), a multi-turn dialogue dataset, and it is already annotated with
emotion and dialogue act labels. We will find how this dialogue dataset is
annotated with a pre-trained politeness recognizer Bao et al. (2021) that
provides values from 1 to 5 on a politeness scale. We discover that the
utterances with certain emotion classes are more polite or impolite than
others. At least most of the time, it seems natural to use polite utterances
in a happy emotional state, whereas to use impolite utterances in an angry
state. This phenomenon is precisely the motivation behind this experiment;
find some utterance examples given in Figure 1. The conversation in this
example shows how an impolite utterance is used in the Anger emotion state and
then ends with a polite utterance in the Happiness emotion state. We find out
such phenomenon statistically occurring quite often in the given dataset, and
the results are also available in the GitHub repository
bothe/politeEDAs222https://github.com/bothe/politeEDAs.

Figure 1: Polite Emotional Dialogue Acts labels from the DailyDialog dataset, Example shows Anger with very Impolite and Happiness with very Polite Emotions | Dialogue Acts
---|---
| Utt | % total | % Emo | Inform | Question | Directive | Commissive
Anger | 1022 | 1.00 | 5.87 | 615 | 174 | 132 | 101
Disgust | 353 | 0.34 | 2.03 | 291 | 30 | 18 | 14
Fear | 174 | 0.17 | 1.00 | 106 | 27 | 21 | 20
Happiness | 12885 | 12.61 | 74.02 | 7830 | 2158 | 1476 | 1421
Sadness | 1150 | 1.13 | 6.61 | 809 | 190 | 95 | 56
Surprise | 1823 | 1.78 | 10.47 | 1122 | 565 | 72 | 64
no_emotion | 85572 | 83.78 | – | 36316 | 26549 | 15542 | 7165
Total | 102979 | – | – | 47089 | 29693 | 17356 | 8841
Table 1: Statistics of utterances with Emotion and Dialogue Act classes in the
DailyDialog dataset

##  2 Related Work

Perceiving emotions in conversation provides affective information of the
conversation partners; similarly, perceiving politeness in conversation
provides cues about their social manners. The emotional states and dialogue
acts have unique relations which is presented by Bothe et al. in Emotional
Dialogue Acts Lakomkin et al. (2017); Bothe et al. (2018b, 2020). For example,
Accept/Agree and Thanking dialogue acts often occur with the Joy emotion,
Apology with Sadness, Reject with Anger, and Acknowledgements with Surprise.
Similarly, politeness and emotion together are evidently discussed a lot in
the literature as some of the most critical social cues Langlotz and Locher
(2017); Renner (2020); Culpeper and Tantucci (2021). Some computational
linguistic study shows how machines learn politeness, for example, please and
could you words signals on the heatmaps of sentences Aubakirova and Bansal
(2016).

In fact, Brown and Levinson (1987) mentions that the display of emotions or
lack of control of emotions as positive politeness strategies or potentially
face-threatening acts. Thus this study fosters analysis of linguistic
politeness by understanding how ‘appropriate levels of affect’ are conveyed in
the conversational interaction Langlotz and Locher (2017). In human-robot
interaction, politeness as a social cue plays a vital role to drive engaging
social interaction with robots Steinfeld et al. (2006); Srinivasan and
Takayama (2016); Bothe et al. (2018a). However, this article explores
relations between the socio-linguistic cues, finding out how polite the
utterances are against their respective emotion and dialogue act classes.

##  3 Approach

Our goal is to analyze the socio-linguistic cues to find meaningful relations
between them, for which we are going to perform the tasks in the following
order:

  * •

explore the dataset, DailyDialog, which is already annotated with emotion and
dialogue act labels,

  * •

annotate the utterances with politeness values using politeness analyzer, more
precisely each utterance with a degree of politeness,

  * •

analyze the annotated utterances with politeness against the emotion and
dialogue act classes in the dataset, and

  * •

conclude with the results and findings and provides future conversational
analysis work to extend this experiment.

##  4 Resources

###  4.1 Dataset: DailyDialog

As the name suggests, the DailyDialog dataset contains conversation topics of
daily life ranging from ordinary life to financial topics. It contains bi-turn
dialogue flow such as Question-Inform and Directive-Commissive; thus, the
dataset is annotated with those four fundamental dialogue acts to follow
unique multi-turn dialogue flow patterns Li et al. (2017). This dataset is
manually labelled with six emotion classes and no_emotion class. The
statistics of the dataset is presented in Table 1, we can see that the
no_emotion class dominates the total number of utterances. However, Happiness
dominates within emotion classes, whereas Fear contains the least number of
utterances. Table 1 also presents the number of utterances for the dialogue
act classes in the dataset for their corresponding emotion classes.

Figure 2: Politeness histograms for the Emotion categories in the DailyDialog
dataset

###  4.2 Politeness Analyzer

We will use a politeness analyzer from the recent work of Bao et al. (2021),
where they combine two datasets from Danescu-Niculescu-Mizil et al. (2013) and
Wang and Jurgens (2018). The politeness regressor model is obtained on these
datasets by pre-training a BERT-based model Devlin et al. (2019) on Reddit
data using masked language modelling. The final model is obtained at an
average Pearson of 0.66 with human judgments from both the datasets and made
available online333https://github.com/wujunjie1998/Politenessr/ by authors.
The model provides a degree of politeness on the scale in [1, 5], where around
3 indicates neutral.

##  5 Results and Analysis

We annotate all utterances in the DailyDialog dataset for politeness values in
the range [1, 5] using the politeness analyzer mentioned above. Then we plot
histograms of the politeness values of the utterances against the emotion
categories shown in Figure 2. As we can see in these histograms, utterances in
the emotion classes Anger and Disgust are neutral and impolite on the
politeness scale. On the other hand, many utterances in the Happiness and
Sadness emotion classes are polite. Fear and Surprise classes are mostly
neutral on the politeness scale than other emotion classes.

Figure 3: Politeness Histograms for the Dialogue Acts in the DailyDialog
dataset Figure 4: Polite Emotional Dialogue Act labels from the DailyDialog
dataset focused on Surprise and Sadness emotion utterances, the utterance with
Surprise shows an immediate reaction which becomes impolite, interestingly
most of the Sadness utterances are polite

We also plot the histograms of the politeness values of the utterances against
the dialogue act classes shown in Figure 3. We can see that most of the
utterances are neutral or polite on the politeness scale for all the dialogue
acts. However, we find that the Inform and Commissive dialogue act classes
contain many polite utterances compared to Question and Directive dialogue
acts. Interestingly, we discovered that speakers often tend to use polite
utterances when answering, thanking, and agreeing (and the utterances that
come under Inform and Commissive). Whereas when asking, guiding, directing,
ordering (under Question and Directive), the utterances are primarily neutral
or polite.

DoP | Dialogu Act | Emotion | Utterances
---|---|---|---
Polite utterances |
4.63 | INFORM | HAPPINESS | OK! Thank you very much!
4.63 | INFORM | HAPPINESS | Sure, that would be great! Thank you!
4.63 | COMMISSIVE | HAPPINESS | That would be great! Thanks a lot!
4.62 | INFORM | HAPPINESS | Thank you, thank you, thanks again.
4.62 | INFORM | HAPPINESS | This is exciting! Thank you so much!
Neutral utterances |
3.34 | INFORM | HAPPINESS | I went to the tutoring service centre on campus today.
3.34 | INFORM | HAPPINESS | I never knew there were so many fun things to do on a farm.
3.34 | INFORM | no_emotion | Just a minute. It’s ten to nine by my watch.
3.34 | INFORM | no_emotion | You may check out books or videos.
3.34 | QUESTION | no_emotion | That’s a small fee?
Impolite utterances |
1.59 | INFORM | DISGUST | Don’t dress like that. You’ll make fool yourself.
1.51 | COMMISSIVE | ANGER | Make it work, Geoff. You would say that, wouldn’t you.
1.47 | DIRECTIVE | no_emotion | Get up, you lazybones!
1.46 | DIRECTIVE | SURPRISE | You idiot! Don’t say that! Do you want this job, or not?
1.37 | DIRECTIVE | ANGER | Get out of my store, you jerk!
Table 2:  Examples from the DailyDialog dataset showing 5 utterances extreme
DoP (degree of politeness)

Table 2 presents top polite, neutral and impolite utterances from the
DailyDialog dataset annotated with the politeness analyzer. There are five
examples from the top 10 in each of the range of extreme values (only 5
examples are shown out of the top 10 to eliminate similar or repeated
utterances). We can see that most of the utterances with “Thank you” phrases
are recognized with a significantly higher degree of politeness. In contrast,
most Anger and Disgust utterances are recognized with a significantly lower
degree of politeness. Figure 4 provides two conversation examples of Surprise
and Sadness emotion utterances.

##  6 Conclusion

Recognizing politeness in conversation is an essential aspect of
conversational analysis, and we discover how politeness flows in a dialogue.
Moreover, socio-linguistics features relatedness provide an additional
dimension for behavioural analysis of conversation partners and their use in
the virtual assistant and human-robot interaction fields.

In this short paper, we discover how politeness is related to emotions and
dialogue acts in the given dataset. Specifically, we discover that the
utterances are mostly polite in Happiness and Sadness emotion classes and
Inform and Commissive dialogue acts. Similarly, the utterances are primarily
neutral or impolite in Anger and Disgust emotion classes. We find that the
utterances in the Question and Directive dialogue acts are mostly neutral;
however, many are also polite.

The continuing work under this experiment is planned to extend to other
dialogue datasets to prove the discovered phenomenon. The politeness analyzer
used in this experiment provided fair annotations for the degree of politeness
linguistically. However, the next step would be to use more than one analyzer
for more robust detection of politeness or annotate the utterances manually.
Future work could also be extended to learn the social behaviours using
analyzed linguistic cues with the help of deep learning techniques.

## References

  * Aubakirova and Bansal (2016) Malika Aubakirova and Mohit Bansal. 2016.  Interpreting Neural Networks to Improve Politeness Comprehension.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2035–2041. Association for Computational Linguistics.
  * Bao et al. (2021) Jiajun Bao, Junjie Wu, Yiming Zhang, Eshwar Chandrasekharan, and David Jurgens. 2021\.  Conversations Gone Alright: Quantifying and Predicting Prosocial Outcomes in Online Conversations.  In _The Web Conference 2021 - Proceedings of the World Wide Web Conference, WWW 2021_ , pages 1134–1145. Association for Computing Machinery, Inc.
  * Bothe (2020) Chandrakant Bothe. 2020.  _Conversational Language Learning for Human-Robot Interaction_.  Ph.D. thesis, Staats-und Universitätsbibliothek Hamburg Carl von Ossietzky, University of Hamburg.
  * Bothe et al. (2018a) Chandrakant Bothe, Fernando Garcia, Arturo Cruz-Maya, Amit Kumar Pandey, and Stefan Wermter. 2018a.  Towards Dialogue-based Navigation with Multivariate Adaptation driven by Intention and Politeness for Social Robots.  In _Proceedings of the International Conference on Social Robotics_ , pages 230–240. Springer.
  * Bothe et al. (2018b) Chandrakant Bothe, Sven Magg, Cornelius Weber, and Stefan Wermter. 2018b.  Discourse-Wizard: Discovering Deep Discourse Structure in your Conversation with RNNs.  _Computation and Language_.
  * Bothe et al. (2020) Chandrakant Bothe, Cornelius Weber, Sven Magg, and Stefan Wermter. 2020.  EDA: Enriching Emotional Dialogue Acts using an Ensemble of Neural Annotators.  In _Proceedings of The 12th Language Resources and Evaluation Conference, LREC 2020_ , pages 620–627. European Language Resources Association (ELRA).
  * Brown and Levinson (1987) Penelope Brown and Stephen C Levinson. 1987.  _Politeness: Some Universals in Language Usage_ , volume 4.  Cambridge University Press.
  * Culpeper and Tantucci (2021) Jonathan Culpeper and Vittorio Tantucci. 2021.  The principle of (im)politeness reciprocity.  _Journal of Pragmatics_ , 175:146–164.
  * Danescu-Niculescu-Mizil et al. (2013) Cristian Danescu-Niculescu-Mizil, Moritz Sudhof, Dan Jurafsky, Jure Leskovec, and Christopher Potts. 2013.  A Computational Approach to Politeness with Application to Social Factors.  In _Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 250–259. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers forLanguage Understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1_ , pages 4171–4186. Association for Computational Linguistics.
  * Lakomkin et al. (2017) Egor Lakomkin, Chandrakant Bothe, and Stefan Wermter. 2017.  GradAscent at EmoInt-2017: Character and Word Level Recurrent Neural Network Models for Tweet Emotion Intensity Detection.  In _Proceedings of the 8th Workshop on Computational Approaches to Subjectivity, Sentiment and Social Media Analysis at the Conference EMNLP_ , pages 169–174. Association for Computational Linguistics.
  * Langlotz and Locher (2017) Andreas Langlotz and Miriam A. Locher. 2017.  _(Im)politeness and Emotion_, pages 287–322. Palgrave Macmillan UK, London.
  * Li et al. (2017) Yanran Li, Hui Su, Xiaoyu Shen, Wenjie Li, Ziqiang Cao, and Shuzi Niu. 2017.  DailyDialog: A manually labelled multi-turn dialogue dataset.  In _Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 986–995, Taipei, Taiwan. Asian Federation of Natural Language Processing.
  * Renner (2020) Bernd Renner. 2020.  _(In) directness as an (im) politeness strategy in the contact between german and Brazilian portuguese as additional languages._ Ph.D. thesis, Universidade de Brasília, Brasília.
  * Srinivasan and Takayama (2016) Vasant Srinivasan and Leila Takayama. 2016.  Help Me Please: Robot Politeness Strategies for Soliciting Help From People.  In _Proceedings of the Conference on Human Factors in Computing Systems_ , pages 4945–4955. ACM.
  * Steinfeld et al. (2006) Aaron Steinfeld, Terrence Fong, David Kaber, Michael Lewis, Jean Scholtz, Alan Schultz, and Michael Goodrich. 2006.  Common Metrics for Human-Robot Interaction.  In _Proceedings of the 1st ACM SIGCHI/SIGART Conference on Human-robot Interaction_ , pages 33–40. ACM.
  * Wang and Jurgens (2018) Zijian Wang and David Jurgens. 2018.  It’s going to be okay: Measuring access to support in online communities.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 33–45, Brussels, Belgium. Association for Computational Linguistics.