# Quantum coherence in mutually unbiased bases

Yao-Kun Wang  College of Mathematics, Tonghua Normal University, Tonghua,
Jilin 134001, China  Research Center for Mathematics, College of Mathematics,
Tonghua Normal University, Tonghua, Jilin 134001, China  Li-Zhu Ge  The Branch
Campus of Tonghua Normal University, Tonghua, Jilin 134001, China  Yuan-Hong
Tao  Department of Mathematics College of Sciences, Yanbian University, Yanji
133002, China

###### Abstract

We investigate the $l_{1}$ norm of coherence of quantum states in mutually
unbiased bases. We find that the sum of squared $l_{1}$ norm of coherence of
the mixed state single qubit is less than two. We derive the $l_{1}$ norm of
coherence of three classes of $X$ states in nontrivial mutually unbiased bases
for $4$-dimensional Hilbert space is equal. We proposed “autotensor of
mutually unbiased basis(AMUB)” by the tensor of mutually unbiased bases, and
depict the level surface of constant the sum of the $l_{1}$ norm of coherence
of Bell-diagonal states in AMUB. We find the $l_{1}$ norm of coherence of
Werner states and isotropic states in AMUB is equal respectively.

##  I Introduction

Quantum coherence is a special feature of quantum mechanic like entanglement
and other quantum correlations. Quantum coherence is an essential factor in
quantum information processing Jha ; Bagan ; Kammerlander , quantum optics
Glauber ; Sudarshan ; Mandel , quantum metrology Giovannetti ; Demkowicz ;
Giovannetti1 , low-temperature thermodynamics Lostaglio ; Lostaglio1 ; Vazquez
; Wacker ; pati ; aberg ; Narasimhachar ; Oppenheim  and quantum biology Lloyd
; Li ; Huelga ; levi ; Plenio ; Rebentrost . Recently, a structure to quantify
coherence has been proposed Baumgratz , and various quantum coherence
measures, such as the $l_{1}$ norm of coherence Baumgratz , trace norm of
coherence shao , relative entropy of coherence Baumgratz , Tsallis relative
$\alpha$ entropies Rastegin  and Relative Rényi $\alpha$ monotones Chitambar ,
have been defined. With the help of of the coherence measures, a variety of
properties of quantum coherence, such as the relations between quantum
correlations and quantum coherence Ma ; Streltsov ; Radhakrishnan ; Yao ; Xi ,
the freezing phenomenon of coherence Bromley ; Yu , have been studied.

Mutually unbiased bases are used in detection of quantum entanglement Spengler
, quantum state reconstruction Wootters , quantum error correction Gottesman ;
Calderbank , and the mean king s problem Vaidman ; Englert . Many features of
mutually unbiased bases are reviewed in reference Durt . When d is power of a
prime number, maximal sets of $d+1$ mutually unbiased bases have been built
for the case. Maximal sets of MUBs are an open problem Durt , when the
dimensionality is another composite number. Entropic uncertainty relations for
$d+1$ mutually unbiased bases in d-dimensional Hilbert space were obtained in
references Ivanovic ; sanchez . The fine-grained uncertainty relation for
mutually unbiased bases is derived in ren . The relation between mutually
unbiased bases and unextendible maximally entangled is investigated in chen .

In this article, we investigate the $l_{1}$ norm of coherence of quantum
states in mutually unbiased bases. We evaluate analytically the sum of squared
$l_{1}$ norm of coherence of the mixed state single qubit. We derive the
relation of the $l_{1}$ norm of coherence of three classes of $X$ states in
nontrivial mutually unbiased bases for $4$-dimensional Hilbert space. We
propose “autotensor of mutually unbiased basis(AMUB)” by the tensor of
mutually unbiased bases, and depict the level surface lang  of constant the
sum of the $l_{1}$ norm of coherence of Bell-diagonal states in AMUB. We
obtain the relations of the $l_{1}$ norm of coherence of Werner states and
isotropic states in AMUB respectively.

##  II The $l_{1}$ norm of coherence of quantum states in $2$ dimension
mutually unbiased bases

Under fixed reference basis, the $l_{1}$ norm of coherence of state $\rho$ is
defined by

$\displaystyle C_{l_{1}}(\rho)=\sum_{i\neq j}|\rho_{i,j}|,$ (1)

and the relative entropy of coherence is given by

$\displaystyle C_{r}(\rho)=S(\rho_{diag})-S(\rho),$ (2)

where $S(\rho)=-Tr{\rho\log\rho}$ is von Neumann entropy.

A set of orthonormal bases $\\{B_{k}\\}$ for a Hilbert space $H=C^{d}$ where
$\\{B_{k}\\}=\\{|0_{k}\rangle,\cdot\cdot\cdot,|d-1_{k}\rangle$ is called
mutually unbiased (MU) iff

$\displaystyle|\langle i_{k}|j_{l}\rangle|^{2}=\frac{1}{d},\forall
i,j\in\\{0,\cdot\cdot\cdot,d-1\\},$ (3)

holds for all basis vectors $|i_{k}\rangle$ and $|j_{l}\rangle$ that belong to
different bases, i.e. $\forall k\neq l$.

In dimension $d=2$, a set of three mutually unbiased bases is readily obtained
from the eigenvectors of the three Pauli matrices $\sigma_{z}$, $\sigma_{x}$
and $\sigma_{y}$:

$\displaystyle\alpha_{1}$ $\displaystyle=$
$\displaystyle\\{\alpha_{11},\alpha_{12}\\}=\\{|0\rangle,|1\rangle\\},$
$\displaystyle\alpha_{2}$ $\displaystyle=$
$\displaystyle\\{\alpha_{21},\alpha_{22}\\}=\\{\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle),\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\\},$
$\displaystyle\alpha_{3}$ $\displaystyle=$
$\displaystyle\\{\alpha_{31},\alpha_{32}\\}=\\{\frac{1}{\sqrt{2}}(|0\rangle+i|1\rangle),\frac{1}{\sqrt{2}}(|0\rangle-i|1\rangle)\\}.$

In dimension $d=3$, there are four mutually unbiased bases as fowllow:

$\displaystyle\beta_{1}$ $\displaystyle=$
$\displaystyle\\{\beta_{11},\beta_{12},\beta_{13}\\}=\\{|0\rangle,|1\rangle,|2\rangle\\},$
$\displaystyle\beta_{2}$ $\displaystyle=$
$\displaystyle\\{\beta_{21},\beta_{22},\beta_{23}\\}=\\{\frac{1}{\sqrt{3}}(|0\rangle+|1\rangle+|2\rangle),\frac{1}{\sqrt{3}}(|0\rangle+\omega|1\rangle+\omega^{2}|2\rangle),\frac{1}{\sqrt{3}}(|0\rangle+\omega^{2}|1\rangle+\omega|2\rangle)\\},$
$\displaystyle\beta_{3}$ $\displaystyle=$
$\displaystyle\\{\alpha_{31},\alpha_{32},\alpha_{33}\\}=\\{\frac{1}{\sqrt{3}}(|0\rangle+|1\rangle+\omega^{2}|2\rangle),\frac{1}{\sqrt{3}}(|0\rangle+\omega^{2}|1\rangle+|2\rangle),\frac{1}{\sqrt{3}}(|0\rangle+\omega|1\rangle+\omega|2\rangle)\\},$
$\displaystyle\beta_{4}$ $\displaystyle=$
$\displaystyle\\{\alpha_{41},\alpha_{42},\alpha_{43}\\}=\\{\frac{1}{\sqrt{3}}(|0\rangle+|1\rangle+\omega|2\rangle),\frac{1}{\sqrt{3}}(|0\rangle+\omega|1\rangle+|2\rangle),\frac{1}{\sqrt{3}}(|0\rangle+\omega^{2}|1\rangle+\omega^{2}|2\rangle)\\},$

where $\omega=e^{i\frac{2\pi}{3}}$.

An arbitrary density matrix for a mixed state single qubit may be written as

$\displaystyle\rho_{s}=\frac{I+\overrightarrow{r}\cdot\overrightarrow{\sigma}}{2}$

where $\overrightarrow{r}=(x,y,z)$ is a real three-dimensional vector such
that $x^{2}+y^{2}+z^{2}\leq 1$, and
$\overrightarrow{\sigma}=(\sigma_{x},\sigma_{y},\sigma_{z})$. In particular,
$\rho$ is pure if and only if $x^{2}+y^{2}+z^{2}=1$.

Next, we will consider the relation of the $l_{1}$ norm of coherence among
$\rho_{s}$ in three mutually unbiased bases
$\alpha_{1},\alpha_{2},\alpha_{3}$.

The density matrix of mixed state single qubit $\rho_{s}$ in base
$\alpha_{1}=\\{\alpha_{11},\alpha_{12}\\}=\\{|0\rangle,|1\rangle\\}$ is

$\displaystyle\rho_{s}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left(\begin{array}[]{cc}1+z&x-iy\\\ x+iy&1-z\\\
\end{array}\right)$ (6) $\displaystyle=$
$\displaystyle\frac{1}{2}(1+z)|0\rangle\langle
0|+\frac{1}{2}(x-iy)|0\rangle\langle 1|+\frac{1}{2}(x+iy)|1\rangle\langle
0|+\frac{1}{2}(1-z)|1\rangle\langle 1|,$ (7)

Using Eq. (1) directly, the $l_{1}$ norm of coherence of state $\rho_{s}$ in
base $\alpha_{1}$ is

$\displaystyle
C_{l_{1}}(\rho_{s})_{\alpha_{1}}=|\frac{1}{2}(x-iy)|+|\frac{1}{2}(x+iy)|=\sqrt{x^{2}+y^{2}}.$
(8)

The density matrix of $\rho_{s}$ in base
$\alpha_{2}=\\{\alpha_{21},\alpha_{22}\\}$ is

$\displaystyle\rho_{s}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}a_{11}&a_{12}\\\ a_{21}&a_{22}\\\
\end{array}\right)$ (12) $\displaystyle=$ $\displaystyle
a_{11}\alpha_{21}\alpha^{{\dagger}}_{21}+a_{12}\alpha_{21}\alpha^{{\dagger}}_{22}+a_{21}\alpha_{22}\alpha^{{\dagger}}_{21}+a_{22}\alpha_{22}\alpha^{{\dagger}}_{22}$
$\displaystyle=$
$\displaystyle\frac{1}{2}(a_{11}+a_{12}+a_{21}+a_{22})|0\rangle\langle
0|+\frac{1}{2}(a_{11}-a_{12}+a_{21}-a_{22})|0\rangle\langle 1|$
$\displaystyle+\frac{1}{2}(a_{11}+a_{12}-a_{21}-a_{22})|1\rangle\langle
0|+\frac{1}{2}(a_{11}-a_{12}-a_{21}+a_{22})|1\rangle\langle 1|.$

As $\rho_{s}$ in Eq. (6) and Eq. (12) is the same, using the method of
undeterminated coefficients, we obtain

$\begin{cases}\frac{1}{2}(a_{11}+a_{12}+a_{21}+a_{22})=\frac{1}{2}(1+z)\\\
\frac{1}{2}(a_{11}-a_{12}+a_{21}-a_{22})=\frac{1}{2}(x-iy)\\\
\frac{1}{2}(a_{11}+a_{12}-a_{21}-a_{22})=\frac{1}{2}(x+iy)\\\
\frac{1}{2}(a_{11}-a_{12}-a_{21}+a_{22})=\frac{1}{2}(1-z)\end{cases}.$

The solution of the equation is

$\begin{cases}a_{11}=\frac{1+x}{2}\\\ a_{12}=\frac{z+iy}{2}\\\
a_{21}=\frac{z-iy}{2}\\\ a_{22}=\frac{1-x}{2}\end{cases}.$ (13)

The $l_{1}$ norm of coherence of state $\rho_{s}$ in base $\alpha_{2}$ is

$\displaystyle
C_{l_{1}}(\rho_{s})_{\alpha_{2}}=|\frac{1}{2}(z+iy)|+|\frac{1}{2}(z-iy)|=\sqrt{z^{2}+y^{2}}.$
(14)

The density matrix of $\rho_{s}$ in base
$\alpha_{3}=\\{\alpha_{31},\alpha_{32}\\}$ by the above method is

$\displaystyle\rho_{s}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left(\begin{array}[]{cc}1+y&z-ix\\\ z+ix&1-y\\\
\end{array}\right)$ (17)

The $l_{1}$ norm of coherence of state $\rho_{s}$ in base $\alpha_{3}$ is

$\displaystyle
C_{l_{1}}(\rho_{s})_{\alpha_{3}}=|\frac{1}{2}(z-ix)|+|\frac{1}{2}(z+ix)|=\sqrt{z^{2}+x^{2}}.$
(18)

As $x^{2}+y^{2}+z^{2}\leq 1$,
$[C_{l_{1}}(\rho_{s})_{\alpha_{1}}]^{2}+[C_{l_{1}}(\rho_{s})_{\alpha_{2}}]^{2}+[C_{l_{1}}(\rho_{s})_{\alpha_{3}}]^{2}\leq
2.$

##  III The $l_{1}$ norm of coherence of $X$ states in the tensor of $3$
dimension mutually unbiased bases

For the three classes of $X$ states in base
$\beta_{1}=\\{\beta_{11},\beta_{12},\beta_{13}\\}=\\{|0\rangle,|1\rangle,|2\rangle\\}$

$\displaystyle\rho_{X}=\left(\begin{array}[]{ccc}x&0&z\\\ 0&1-x-y&0\\\
z&o&y\\\ \end{array}\right),$ (22)

where $x,y,z$ are all real number, we will consider the $l_{1}$ norm of
coherence of $\rho_{X}$ in the $3$ dimension mutually unbiased bases
$\beta_{2},\beta_{3},\beta_{4}$.

Let the density matrix of $\rho_{X}$ in base
$\beta_{2}=\\{\beta_{21},\beta_{22},\beta_{23}\\}$ be

$\displaystyle\rho_{X}=\left(\begin{array}[]{ccc}b_{11}&b_{12}&b_{13}\\\
b_{21}&b_{22}&b_{23}\\\ b_{31}&b_{32}&b_{33}\\\ \end{array}\right),$ (26)

and
$\rho_{X}=b_{11}\beta_{21}\beta_{21}^{{\dagger}}+b_{12}\beta_{21}\beta_{22}^{{\dagger}}+b_{13}\beta_{21}\beta_{23}^{{\dagger}}+b_{21}\beta_{22}\beta_{21}^{{\dagger}}+b_{22}\beta_{22}\beta_{22}^{{\dagger}}+b_{23}\beta_{22}\beta_{23}^{{\dagger}}+b_{31}\beta_{23}\beta_{21}^{{\dagger}}+b_{32}\beta_{23}\beta_{22}^{{\dagger}}+b_{33}\beta_{23}\beta_{23}^{{\dagger}}$.
As $\rho_{X}$ in Eq. (22) and Eq. (26) is the same, using the method of
undeterminated coefficients, we obtain

$\begin{cases}\frac{1}{3}(b_{11}+b_{12}+b_{13}+b_{21}+b_{22}+b_{23}+b_{31}+b_{32}+b_{33})=x\\\
\frac{1}{3}(b_{11}+\omega^{2}b_{12}+\omega
b_{13}+b_{21}+\omega^{2}b_{22}+\omega b_{23}+b_{31}+\omega^{2}b_{32}+\omega
b_{33})=0\\\ \frac{1}{3}(b_{11}+\omega b_{12}+\omega^{2}b_{13}+b_{21}+\omega
b_{22}+\omega^{2}b_{23}+b_{31}+\omega b_{32}+\omega^{2}b_{33})=z\\\
\frac{1}{3}(b_{11}+b_{12}+b_{13}+\omega b_{21}+\omega b_{22}+\omega
b_{23}+\omega^{2}b_{31}+\omega^{2}b_{32}+\omega^{2}b_{33})=0\\\
\frac{1}{3}(b_{11}+\omega^{2}b_{12}+\omega b_{13}+\omega
b_{21}+b_{22}+\omega^{2}b_{23}+\omega^{2}b_{31}+\omega b_{32}+b_{33})=1-x-y\\\
\frac{1}{3}(b_{11}+\omega b_{12}+\omega^{2}b_{13}+\omega
b_{21}+\omega^{2}b_{22}+b_{23}+\omega^{2}b_{31}+b_{32}+\omega b_{33})=0\\\
\frac{1}{3}(b_{11}+b_{12}+b_{13}+\omega^{2}b_{21}+\omega^{2}b_{22}+\omega^{2}b_{23}+\omega
b_{31}+\omega b_{32}+\omega b_{33})=z\\\
\frac{1}{3}(b_{11}+\omega^{2}b_{12}+\omega b_{13}+\omega^{2}b_{21}+\omega
b_{22}+b_{23}+\omega b_{31}+b_{32}+\omega^{2}b_{33})=0\\\
\frac{1}{3}(b_{11}+\omega
b_{12}+\omega^{2}b_{13}+\omega^{2}b_{21}+b_{22}+\omega b_{23}+\omega
b_{31}+\omega^{2}b_{32}+b_{33})=y\end{cases}.$ (27)

The solution of the equation is

$\begin{cases}b_{11}=\frac{1+2z}{3},b_{12}=\frac{(3x+z-1)-\sqrt{3}(x+2y+z-1)i}{6},b_{13}=\frac{(3x+z-1)+\sqrt{3}(x+2y+z-1)i}{6},\\\
b_{21}=\overline{b_{12}},b_{22}=\frac{1-z}{3},b_{23}=\frac{(3x-2z-1)-\sqrt{3}(x+2y-2z-1)i}{6},\\\
b_{31}=\overline{b_{13}},b_{32}=\overline{b_{23}},b_{33}=\frac{1-3z}{3}.\end{cases}$
(28)

The $l_{1}$ norm of coherence of state $\rho_{X}$ in base $\beta_{2}$ is

$\displaystyle C_{l_{1}}(\rho_{X})_{\beta_{2}}=2(|b_{12}|+|b_{13}|+|b_{23}|).$
(29)

Similarly, the density matrix of $\rho_{X}$ in base $\beta_{3}$ is

$\displaystyle\rho_{X}=\left(\begin{array}[]{ccc}b_{22}&\overline{b_{12}}&b_{23}\\\
b_{12}&b_{11}&b_{13}\\\ \overline{b_{23}}&\overline{b_{13}}&b_{33}\\\
\end{array}\right),$ (33)

The $l_{1}$ norm of coherence of state $\rho_{X}$ in base $\beta_{3}$ is

$\displaystyle C_{l_{1}}(\rho_{X})_{\beta_{3}}=2(|b_{12}|+|b_{13}|+|b_{23}|).$
(34)

The density matrix of $\rho_{X}$ in base $\beta_{4}$ is

$\displaystyle\rho_{X}=\left(\begin{array}[]{ccc}b_{22}&b_{12}&\overline{b_{23}}\\\
\overline{b_{12}}&b_{11}&\overline{b_{13}}\\\ b_{23}&b_{13}&b_{33}\\\
\end{array}\right),$ (38)

The $l_{1}$ norm of coherence of state $\rho_{X}$ in base $\beta_{4}$ is

$\displaystyle C_{l_{1}}(\rho_{X})_{\beta_{4}}=2(|b_{12}|+|b_{13}|+|b_{23}|).$
(39)

At last, we find that the $l_{1}$ norm of coherence of state $\rho_{X}$ in
base $\beta_{2},\beta_{3},\beta_{4}$ is equal, i.e

$\displaystyle
C_{l_{1}}(\rho_{X})_{\beta_{2}}=C_{l_{1}}(\rho_{X})_{\beta_{3}}=C_{l_{1}}(\rho_{X})_{\beta_{4}}.$
(40)

Furthermore, let

$\displaystyle\rho_{\vartriangle}=\left(\begin{array}[]{ccc}1-x-y&0&0\\\
0&x&z\\\ 0&z&y\\\ \end{array}\right),$ (44)

and

$\displaystyle\rho_{\triangledown}=\left(\begin{array}[]{ccc}x&z&0\\\ z&y&0\\\
0&0&1-x-y\\\ \end{array}\right),$ (48)

where $x,y,z$ are all real number, using above method, we can find that the
$l_{1}$ norm of coherence of state $\rho_{\vartriangle}$ and
$\rho_{\triangledown}$ in base $\beta_{2},\beta_{3},\beta_{4}$ is also equal
respectively.

##  IV The $l_{1}$ norm of coherence of Bell-diagonal states in the tensor of
$2$ dimension mutually unbiased bases

In this section, we extend the concept of mutually unbiased basis by the
tensor.

_Definition_. For the set of mutually unbiased bases $\\{B_{k}\\}$ for a
Hilbert space $H=C^{d}$ where
$\\{B_{k}\\}=\\{|0_{k}\rangle,\cdot\cdot\cdot,|d-1_{k}\rangle\\}$, we call the
set $\\{\gamma_{k}\\}=\\{|i\rangle_{k}\otimes|i\rangle_{k}|\forall
i,j\in\\{0,\cdot\cdot\cdot,d-1\\}\\}$ _autotensor of mutually unbiased
basis_(AMUB) if

$\displaystyle|(\langle i|_{k}\otimes\langle
j|_{k})(|m\rangle_{l}\otimes|n\rangle_{l})|=\frac{1}{d},$ (49)

where $k\neq l$. Furthermore, we can construct a set of AMUB by $d=2$
dimension mutually unbiased bases. For example, let

$\displaystyle\gamma_{1}$ $\displaystyle=$
$\displaystyle\\{\gamma_{11},\gamma_{12},\gamma_{13},\gamma_{14}\\}=\\{\alpha_{11}\otimes\alpha_{11},\alpha_{11}\otimes\alpha_{12},\alpha_{12}\otimes\alpha_{11},\alpha_{12}\otimes\alpha_{12}\\},$
$\displaystyle\gamma_{2}$ $\displaystyle=$
$\displaystyle\\{\gamma_{21},\gamma_{22},\gamma_{23},\gamma_{24}\\}=\\{\alpha_{21}\otimes\alpha_{21},\alpha_{21}\otimes\alpha_{22},\alpha_{22}\otimes\alpha_{21},\alpha_{22}\otimes\alpha_{22}\\},$
$\displaystyle\gamma_{3}$ $\displaystyle=$
$\displaystyle\\{\gamma_{31},\gamma_{32},\gamma_{33},\gamma_{34}\\}=\\{\alpha_{31}\otimes\alpha_{31},\alpha_{31}\otimes\alpha_{32},\alpha_{32}\otimes\alpha_{31},\alpha_{32}\otimes\alpha_{32}\\}.$

Next, we will consider the relation of the coherence of quantum states in
above AMUB.

A two-qubit Bell-diagonal states can be written as

$\displaystyle\rho_{B}=\frac{1}{4}(I\otimes
I+\sum_{i=1}^{3}c_{i}\sigma_{i}\otimes\sigma_{i}),$ (50)

where $\\{\sigma_{i}\\}_{i=1}^{3}$ are the Pauli matrices, and
$c_{1},c_{2},c_{3}\in[-1,1]$. The density matrix of $\rho_{B}$ in base
$\gamma_{1}=\\{\gamma_{11},\gamma_{12},\gamma_{13},\gamma_{14}\\}=\\{|00\rangle$,
$|01\rangle$, $|10\rangle$, $|11\rangle\\}$ is:

$\displaystyle\rho_{B}=\frac{1}{4}\left(\begin{array}[]{cccc}1+c_{3}&0&0&c_{1}-c_{2}\\\
0&1-c_{3}&c_{1}+c_{2}&0\\\ 0&c_{1}+c_{2}&1-c_{3}&0\\\
c_{1}-c_{2}&0&0&1+c_{3}\end{array}\right)$ (55)

The $l_{1}$ norm of coherence of state $\rho_{B}$ in base $\gamma_{1}$ is

$\displaystyle
C_{l_{1}}(\rho_{B})_{\gamma_{1}}=2(|\frac{1}{4}(c_{1}-c_{2})|+|\frac{1}{4}(c_{1}+c_{2})|)=\frac{1}{2}(|(c_{1}-c_{2})|+|(c_{1}+c_{2})|).$
(56)

Let the density matrix of $\rho_{B}$ in base
$\gamma_{2}=\\{\gamma_{21},\gamma_{22},\gamma_{23},\gamma_{24}\\}$ is

$\displaystyle\rho_{B}=\left(\begin{array}[]{cccc}d_{11}&d_{12}&d_{13}&d_{14}\\\
d_{21}&d_{22}&d_{23}&d_{24}\\\ d_{31}&d_{32}&d_{33}&d_{34}\\\
d_{41}&d_{42}&d_{43}&d_{44}\end{array}\right),$ (61)

and
$\rho_{B}=d_{11}\gamma_{21}\gamma_{21}^{{\dagger}}+d_{12}\gamma_{21}\gamma_{22}^{{\dagger}}+d_{13}\gamma_{21}\gamma_{23}^{{\dagger}}+d_{14}\gamma_{21}\gamma_{24}^{{\dagger}}+d_{21}\gamma_{22}\gamma_{21}^{{\dagger}}+d_{22}\gamma_{22}\gamma_{22}^{{\dagger}}+d_{23}\gamma_{22}\gamma_{23}^{{\dagger}}+d_{24}\gamma_{22}\gamma_{24}^{{\dagger}}+d_{31}\gamma_{23}\gamma_{21}^{{\dagger}}+d_{32}\gamma_{23}\gamma_{22}^{{\dagger}}+d_{33}\gamma_{23}\gamma_{23}^{{\dagger}}+d_{34}\gamma_{23}\gamma_{24}^{{\dagger}}+d_{41}\gamma_{24}\gamma_{21}^{{\dagger}}+d_{42}\gamma_{24}\gamma_{22}^{{\dagger}}+d_{43}\gamma_{24}\gamma_{23}^{{\dagger}}+d_{44}\gamma_{24}\gamma_{24}^{{\dagger}}.$
As $\rho_{B}$ in Eq. (55) and Eq. (61) is the same, using the method of
undeterminated coefficients, we obtain

$\begin{cases}d_{11}+d_{12}+d_{13}+d_{14}+d_{21}+d_{22}+d_{23}+d_{24}+d_{31}+d_{32}+d_{33}+d_{34}+d_{41}+d_{42}+d_{43}+d_{44}=1+c_{3}\\\
d_{11}-d_{12}+d_{13}-d_{14}+d_{21}-d_{22}+d_{23}-d_{24}+d_{31}-d_{32}+d_{33}-d_{34}+d_{41}-d_{42}+d_{43}-d_{44}=0\\\
d_{11}+d_{12}-d_{13}-d_{14}+d_{21}+d_{22}-d_{23}-d_{24}+d_{31}+d_{32}-d_{33}-d_{34}+d_{41}+d_{42}-d_{43}-d_{44}=0\\\
d_{11}-d_{12}-d_{13}+d_{14}+d_{21}-d_{22}-d_{23}+d_{24}+d_{31}-d_{32}-d_{33}+d_{34}+d_{41}-d_{42}-d_{43}+d_{44}=c_{1}-c_{2}\\\
d_{11}+d_{12}+d_{13}+d_{14}-d_{21}-d_{22}-d_{23}-d_{24}+d_{31}+d_{32}+d_{33}+d_{34}-d_{41}-d_{42}-d_{43}-d_{44}=0\\\
d_{11}-d_{12}+d_{13}-d_{14}-d_{21}+d_{22}-d_{23}+d_{24}+d_{31}-d_{32}+d_{33}-d_{34}-d_{41}+d_{42}-d_{43}+d_{44}=1-c_{3}\\\
d_{11}+d_{12}-d_{13}-d_{14}-d_{21}-d_{22}+d_{23}+d_{24}+d_{31}+d_{32}-d_{33}-d_{34}-d_{41}-d_{42}+d_{43}+d_{44}=c_{1}+c_{2}\\\
d_{11}-d_{12}-d_{13}+d_{14}-d_{21}+d_{22}+d_{23}-d_{24}+d_{31}-d_{32}-d_{33}+d_{34}-d_{41}+d_{42}+d_{43}-d_{44}=0\\\
d_{11}+d_{12}+d_{13}+d_{14}+d_{21}+d_{22}+d_{23}+d_{24}-d_{31}-d_{32}-d_{33}-d_{34}-d_{41}-d_{42}-d_{43}-d_{44}=0\\\
d_{11}-d_{12}+d_{13}-d_{14}+d_{21}-d_{22}+d_{23}-d_{24}-d_{31}+d_{32}-d_{33}+d_{34}-d_{41}+d_{42}-d_{43}+d_{44}=c_{1}+c_{2}\\\
d_{11}+d_{12}-d_{13}-d_{14}+d_{21}+d_{22}-d_{23}-d_{24}-d_{31}-d_{32}+d_{33}+d_{34}-d_{41}-d_{42}+d_{43}+d_{44}=1-c_{3}\\\
d_{11}-d_{12}-d_{13}+d_{14}+d_{21}-d_{22}-d_{23}+d_{24}-d_{31}+d_{32}+d_{33}-d_{34}-d_{41}+d_{42}+d_{43}-d_{44}=0\\\
d_{11}+d_{12}+d_{13}+d_{14}-d_{21}-d_{22}-d_{23}-d_{24}-d_{31}-d_{32}-d_{33}-d_{34}+d_{41}+d_{42}+d_{43}+d_{44}=c_{1}-c_{2}\\\
d_{11}-d_{12}+d_{13}-d_{14}-d_{21}+d_{22}-d_{23}+d_{24}-d_{31}+d_{32}-d_{33}+d_{34}+d_{41}-d_{42}+d_{43}-d_{44}=0\\\
d_{11}+d_{12}-d_{13}-d_{14}-d_{21}-d_{22}+d_{23}+d_{24}-d_{31}-d_{32}+d_{33}+d_{34}+d_{41}+d_{42}-d_{43}-d_{44}=0\\\
d_{11}-d_{12}-d_{13}+d_{14}-d_{21}+d_{22}+d_{23}-d_{24}-d_{31}+d_{32}+d_{33}-d_{34}+d_{41}-d_{42}-d_{43}+d_{44}=1+c_{3}\end{cases}.$
(62)

The solution of the equation is

$\begin{cases}d_{11}=\frac{1+c_{1}}{4},d_{12}=0,d_{13}=0,d_{14}=\frac{c_{3}-c_{2}}{4},\\\
d_{21}=0,d_{22}=\frac{1-c_{1}}{4},d_{23}=\frac{c_{3}+c_{2}}{4},d_{24}=0,\\\
d_{31}=0,d_{32}=\frac{c_{3}+c_{2}}{4},d_{23}=\frac{1-c_{1}}{4},d_{24}=0,\\\
d_{41}=\frac{c_{3}-c_{2}}{4},d_{42}=0,d_{43}=0,d_{44}=\frac{1+c_{1}}{4}.\\\
\end{cases}$ (63)

So, the density matrix of $\rho_{B}$ in base
$\gamma_{2}=\\{\gamma_{21},\gamma_{22},\gamma_{23},\gamma_{24}\\}$ is

$\displaystyle\rho_{B}=\frac{1}{4}\left(\begin{array}[]{cccc}1+c_{1}&0&0&c_{3}-c_{2}\\\
0&1-c_{1}&c_{3}+c_{2}&0\\\ 0&c_{3}+c_{2}&1-c_{1}&0\\\
c_{3}-c_{2}&0&0&1+c_{1}\end{array}\right).$ (68)

The $l_{1}$ norm of coherence of state $\rho_{B}$ in base $\gamma_{2}$ is

$\displaystyle
C_{l_{1}}(\rho_{B})_{\gamma_{2}}=2(|\frac{1}{4}(c_{3}-c_{2})|+|\frac{1}{4}(c_{3}+c_{2})|)=\frac{1}{2}(|(c_{3}-c_{2})|+|(c_{3}+c_{2})|).$
(69)

Similarly, the density matrix of $\rho_{B}$ in base
$\gamma_{3}=\\{\gamma_{31},\gamma_{32},\gamma_{33},\gamma_{34}\\}$ is

$\displaystyle\rho_{B}=\frac{1}{4}\left(\begin{array}[]{cccc}1+c_{2}&0&0&c_{3}-c_{1}\\\
0&1-c_{2}&c_{3}+c_{1}&0\\\ 0&c_{3}+c_{1}&1-c_{2}&0\\\
c_{3}-c_{1}&0&0&1+c_{2}\end{array}\right).$ (74)

The $l_{1}$ norm of coherence of state $\rho_{B}$ in base $\gamma_{3}$ is

$\displaystyle
C_{l_{1}}(\rho_{B})_{\gamma_{3}}=2(|\frac{1}{4}(c_{3}-c_{1})|+|\frac{1}{4}(c_{3}+c_{1})|)=\frac{1}{2}(|(c_{3}-c_{1})|+|(c_{3}+c_{1})|).$
(75)

Figure 1: (Color online) The $l_{1}$ norm of coherence of Bell-diagonal states
$\rho_{B}$ in base $\gamma_{1}$ as a function of $c_{1}$ and $c_{2}$.

In Fig. 1, the $l_{1}$ norm of coherence of Bell-diagonal states $\rho_{B}$ in
base $\gamma_{1}$ as a function of $c_{1}$ and $c_{2}$ is depicted. When
$c_{1}=c_{2}=0$, the coherence reach minimal value $0$. As $|c_{1}|$ and
$|c_{2}|$ increase, the coherence increase. When $|c_{1}|=1$ or $|c_{2}|=1$,
the coherence obtain maximum value. Similar situation also appear in the
coherence in bases $\gamma_{2}$ and $\gamma_{3}$.

Next, we denote the sum of the $l_{1}$ norm of coherence of Bell-diagonal
states $\rho_{B}$ in bases $\gamma_{1}$, $\gamma_{2}$, $\gamma_{3}$ by
$C_{l_{1}}(\rho_{B})_{\gamma}$, i. e

$\displaystyle
C_{l_{1}}(\rho_{B})_{\gamma}=C_{l_{1}}(\rho_{B})_{\gamma_{1}}+C_{l_{1}}(\rho_{B})_{\gamma_{2}}+C_{l_{1}}(\rho_{B})_{\gamma_{3}}.$
(76)

In Fig. 2, we plot the surfaces lang  of the sum of the $l_{1}$ norm of
coherence $C_{l_{1}}(\rho_{B})_{\gamma}$ of Bell-diagonal states $\rho_{B}$ in
bases $\gamma_{1}$, $\gamma_{2}$, $\gamma_{3}$ in (a), (b), and (c). It show
that the surface of the sum of the coherence is tetrahexahedron. As the sum
increase, its volume expand, i. e. $|c_{1}|$, $|c_{2}|$, $|c_{3}|$ increase
simultaneously.

(a)

(b)

(c)

Figure 2: Surfaces of constant of the sum of the $l_{1}$ norm of coherence
$C_{l_{1}}(\rho_{B})_{\gamma}$ for Bell-diagonal states $\rho_{B}$ in bases
$\gamma_{1}$, $\gamma_{2}$, $\gamma_{3}$ : (a)
$C_{l_{1}}(\rho_{B})_{\gamma}=0.5$; (b) $C_{l_{1}}(\rho_{B})_{\gamma}=1$;
$C_{l_{1}}(\rho_{B})_{\gamma}=2$.

In Eq. (55), let $c_{1}=c_{2}=c_{3}=\frac{4p}{3}-1$, where $0\leq p\leq 1$
,Bell-diagonal states $\rho_{B}$ turn into Werner state

$\displaystyle\rho_{W}=\left(\begin{array}[]{cccc}\frac{p}{3}&0&0&0\\\
0&-\frac{p}{3}+\frac{1}{2}&\frac{2p}{3}-\frac{1}{2}&0\\\
0&\frac{2p}{3}-\frac{1}{2}&-\frac{p}{3}+\frac{1}{2}&0\\\
0&0&0&\frac{p}{3}\end{array}\right).$ (81)

We denoted the $l_{1}$ norm of coherence of Werner states $\rho_{W}$ in bases
$\gamma_{1},\gamma_{2},\gamma_{3}$ by
$C_{l_{1}}(\rho_{W})_{\gamma_{1}},C_{l_{1}}(\rho_{W})_{\gamma_{2}},C_{l_{1}}(\rho_{W})_{\gamma_{3}}$
respectively. By Eqs. (56), (69), (75), we find that
$C_{l_{1}}(\rho_{W})_{\gamma_{1}}=C_{l_{1}}(\rho_{W})_{\gamma_{2}}=C_{l_{1}}(\rho_{W})_{\gamma_{3}}=|\frac{4p}{3}-1|$.

In Eq. (55), let
$c_{1}=\frac{4F-1}{3},c_{2}=-\frac{4F-1}{3},c_{3}=\frac{4F-1}{3}$, where
$0\leq F\leq 1$ ,Bell-diagonal states $\rho_{B}$ turn into isotropic state

$\displaystyle\rho_{iso}=\left(\begin{array}[]{cccc}\frac{F}{3}+\frac{1}{6}&0&0&\frac{2F}{3}-\frac{1}{6}\\\
0&\frac{1}{3}-\frac{F}{3}&0&0\\\ 0&0&\frac{1}{3}-\frac{F}{3}&0\\\
\frac{2F}{3}-\frac{1}{6}&0&0&\frac{F}{3}+\frac{1}{6}\end{array}\right).$ (86)

We denoted the $l_{1}$ norm of coherence of isotropic states $\rho_{iso}$ in
bases $\gamma_{1},\gamma_{2},\gamma_{3}$ by
$C_{l_{1}}(\rho_{iso})_{\gamma_{1}},C_{l_{1}}(\rho_{iso})_{\gamma_{2}},C_{l_{1}}(\rho_{iso})_{\gamma_{3}}$
respectively. By Eqs. (56), (69), (75), we find that
$C_{l_{1}}(\rho_{iso})_{\gamma_{1}}=C_{l_{1}}(\rho_{iso})_{\gamma_{2}}=C_{l_{1}}(\rho_{iso})_{\gamma_{3}}=|\frac{4F-1}{3}|$.

##  V summary

In this work, we studied the $l_{1}$ norm of coherence of quantum states in
mutually unbiased bases. We have found the sum of squared $l_{1}$ norm of
coherence of the mixed state single qubit is less than two. We have obtained
the $l_{1}$ norm of coherence of three classes of $X$ states in nontrivial
mutually unbiased bases for $4$-dimensional Hilbert space is equal. We have
proposed “autotensor of mutually unbiased basis(AMUB)” by the tensor of
mutually unbiased bases, and given the level surfacelang  of constant the sum
of the $l_{1}$ norm of coherence of Bell-diagonal states in AMUB. We have
found the $l_{1}$ norm of coherence of Werner states and isotropic states in
AMUB is equal respectively.

## References

  * (1) P. K. Jha, M. Mrejen, J. Kim, C. Wu, Y. Wang, Y. V. Rostovtsev, and X. Zhang, Phys. Rev. Lett. 116, 165502 (2016).
  * (2) E. Bagan, J. A. Bergou, S. S. Cottrell, and M. Hillery, Phys. Rev. Lett. 116, 160406 (2016).
  * (3) P. Kammerlander and J. Anders, Sci. Rep. 6, 22174 (2016).
  * (4) R. J. Glauber, Phys. Rev. 131, 2766 (1963).
  * (5) E. C. G. Sudarshan, Phys. Rev. Lett. 10, 277 (1963).
  * (6) L. Mandel and E. Wolf, _Optical Coherence and Quantum Optics_ (Cambridge University Press, Cambridge, UK, 1995).
  * (7) V. Giovannetti, S. Lloyd, and L. Maccone, Science 306, 1330 (2004).
  * (8) R. Demkowicz-Dobrzański and L. Maccone, Phys. Rev. Lett. 113, 250801 (2014).
  * (9) V. Giovannetti, S. Lloyd, and L. Maccone, Nat. Photonics 5, 222 (2011).
  * (10) M. Lostaglio, D. Jennings, and T. Rudolph, Nat. Commun. 6, 6383 (2015).
  * (11) M. Lostaglio, K. Korzekwa, D. Jennings, and T. Rudolph, Phys. Rev. X 5, 021001 (2015).
  * (12) H. Vazquez, R. Skouta, S. Schneebeli, M. Kamenetska, R. Breslow, L. Venkataraman, and M. S. Hybertsen, Nat. Nanotechnol. 7, 663 (2012).
  * (13) O. Karlström, H. Linke, G. Karlström, and A. Wacker, Phys. Rev. B 84, 113415 (2011).
  * (14) A. Misra, U. Singh, S. Bhattacharya, and A. K. Pati, Phys. Rev. A 93, 052335 (2016).
  * (15) J. Aberg, Phys. Rev. Lett. 113, 150402 (2014).
  * (16) V. Narasimhachar and G. Gour, Nat. Commun. 6, 7689 (2015).
  * (17) P. Ćwikliński, M. Studziński, M. Horodecki, and J. Oppenheim, Phys. Rev. Lett. 115, 210403 (2015).
  * (18) S. Lloyd, J. Phys: Conf. Ser. 302, 012037 (2011).
  * (19) C.-M. Li, N. Lambert, Y.-N. Chen, G.-Y. Chen, and F. Nori, Sci. Rep. 2, 885 (2012).
  * (20) S. F. Huelga and M. B. Plenio, Contemp. Phys. 54, 181 (2013).
  * (21) F. Levi, and F. Mintert, New J. Phys. 16, 033007 (2014).
  * (22) M. B. Plenio and S. F. Huelga, New J. Phys. 10, 113019 (2008).
  * (23) P. Rebentrost, M. Mohseni, and A. Aspuru-Guzik, J. Phys. Chem. B 113, 9942 (2009).
  * (24) L.-H. Shao, Z. Xi, H. Fan and Y. Li, Phys. Rev. A 91 042120 (2015).
  * (25) T. Baumgratz, M. Cramer, and M. B. Plenio, Phys. Rev. Lett. 113, 140401 (2014).
  * (26) A. E. Rastegin, Phys. Rev. A 93 032136 (2016).
  * (27) E. Chitambar and G. Gour, Phys. Rev. A 94 052336 (2016).
  * (28) J. Ma, B. Yadin, D. Girolami, V. Vedral, and M. Gu, Phys. Rev. Lett. 116, 160407 (2016).
  * (29) A. Streltsov, U. Singh, H. S. Dhar, M. N. Bera, and G. Adesso, Phys. Rev. Lett. 115, 020403 (2015).
  * (30) C. Radhakrishnan, M. Parthasarathy, S. Jambulingam, and T. Byrnes, Phys. Rev. Lett. 116, 150504 (2016).
  * (31) Y. Yao, X. Xiao, L. Ge, and C. P. Sun, Phys. Rev. A 92, 022112 (2015).
  * (32) Z. Xi, Y. Li, and H. Fan, Sci. Rep. 5, 10922 (2015).
  * (33) T. R. Bromley, M. Cianciaruso, and G. Adesso, Phys. Rev. Lett. 114, 210401 (2015).
  * (34) X.-D. Yu, D.-J. Zhang, C. L. Liu, and D. M. Tong, Phys. Rev. A 93, 060303 (2016).
  * (35) C. Spengler, M. Huber, S. Brierley, T. Adaktylos, B. C. Hiesmayr, Phys. Rev. A 86, 022311 (2012).
  * (36) W. K. Wootters, B. D Fields, Ann. Phys. 191, 363 (1989).
  * (37) D. Gottesman, Phys. Rev. A 54, 1862 (1996).
  * (38) A. R. Calderbank, E. M. Rains, P.W. Shor, N. J. A. Sloane, Phys. Rev. Lett. 78, 405 (1997).
  * (39) L. Vaidman, Y. Aharonov, D. Z. Albert, Phys. Rev. Lett. 58, 1385 (1987).
  * (40) B.-G. Englert, Y. Aharonov, Phys. Lett. A 284, 1 (2001).
  * (41) T. Durt, B.-G. Englert, I. Bengtsson, K. Zyczkowski, Int. J. Quantum Inf. 8, 535 (2010).
  * (42) I. D. Ivanovic, J. Phys. A: Math. Gen. 25, L363 (1995).
  * (43) J. Sánchez, Phys. Lett. A 173, 233 (1993).
  * (44) L-. H Ren, H. Fan, Phys. Rev. A 90, 052110 (2016).
  * (45) B. Chen, S.-M. Fei, Phys. Rev. A 88, 034301 (2013).
  * (46) M. D. Lang and C. M. Caves, Phys. Rev. Lett. 105, 15051 (2010).


# The Effect of Iterativity on Adversarial Opinion Forming

Konstantinos Panagiotou  Simon Reisser

($1^{\text{st}}$ December, 2021)

###### Abstract

Consider the following model to study adversarial effects on opinion forming.
A set of initially selected experts form their binary opinion while being
influenced by an adversary, who may convince some of them of the falsehood.
All other participants in the network then take the opinion of the majority of
their neighbouring experts. Can the adversary influence the experts in such a
way that the majority of the network believes the falsehood? Alon et al. [2]
conjectured that in this context an iterative dissemination process will
always be beneficial to the adversary. This work provides a counterexample to
that conjecture.

##  1 Introduction

Understanding how opinions are formed is as important as ever, as the spread
of misinformation becomes more prevalent every day. Assume there is some new
innovation being either good or bad that is introduced to a group of people
who want to form their (binary) opinion about it. Following a key insight by
Rogers [22], the opining forming process can be modelled as follows. At first,
a small set of so-called early adopters, or experts, forms their opinion about
the newly introduced innovation. Afterwards, they disseminate their opinion to
all other non-experts in the network.

When looking at that network from the outside an observer wants to infer the
quality of the new innovation by observing the opinion of all individuals, but
without taking the actual structure of the network into consideration (maybe
by doing a poll). One popular method to achieve this is using the _wisdom of
the crowd_. In this case that corresponds to a simple majority rule, that is,
the observer takes the majority of opinions as an estimate. Wisdom of the
crowd has been shown to have a plethora of useful applications in decision
making, see e.g. [9, 19, 21, 5, 8, 18].

Assume furthermore that there is an adversary who can influence the opinion of
some early adopters so as to falsely convince the observer of the new
innovation’s quality. Let us look at some examples. Consider the so-called
Black-Hat ASIN Piggybacking on Amazons Marketplace [17]. This is the method of
hijacking the listing of an Amazon vendor to sell counterfeit products under
the (dis-)guise of a genuine listing. Some customers then buy the real product
and some buy the fake one. This results in the vendor to lose profit as well
as him getting negative reviews that do not correspond to the actual product.
The second example is a newly opened restaurant, that in its opening phase
invites food critics to try and rate the restaurant. However, when those
critics dine at the restaurant, the restaurant puts in more effort than it
would when catering to a regular customer, e.g., by providing better quality
food and service. Lastly, consider the common practice of online vendors to
buy positive reviews for their products by either giving directly monetary
incentives to reviewers or providing them with free products. In particular,
on Amazon in certain product categories, like Bluetooth speakers and
headphones, ReviewMeta [20] finds more than half of reviews to be fake [11].

### A Model for Opinion Forming

In the previous examples we saw three different sorts of adversaries: the
hijacking seller influenced negatively the opinions of some customers; the
restaurant owner could actively choose which critics to influence; finally,
the seller that bought his reviews could select the reviewers as well as
guarantee their opinion. Alon et al. [2] introduced a model that implements
the ideas outlined above. Given a graph $G=(V,E)$ on $n$ vertices and
parameters $0\leq\mu<1/2,0<\delta\leq 1/2$ we define the set of experts as a
set $\mathcal{E}\subseteq V$ with the property that $|\mathcal{E}|=\mu|V|=\mu
n$. Let $\mathcal{E}$ be furthermore divided into two subsets: the experts
that know the truth $\mathcal{E}_{1}\subseteq\mathcal{E}$ and the experts that
are convinced of the falsehood
$\mathcal{E}_{0}=\mathcal{E}\setminus\mathcal{E}_{1}$. The sets
$\mathcal{E}_{1},\mathcal{E}_{0}$ are chosen in three different ways that
correspond to the various adversaries described in the previous paragraphs.

The _random_ adversary has actually no choice. He chooses the expert set
$\mathcal{E}$ uniformly at random among all sets of size $\mu|V|$. Then
$\mathcal{E}$ is in turn partitioned into $\mathcal{E}_{1}$ and
$\mathcal{E}_{0}$ by adding each vertex in $\mathcal{E}$ to $\mathcal{E}_{1}$
independently with probability $1/2+\delta$ and to $\mathcal{E}_{0}$
otherwise. The _weak_ adversary is allowed to choose the expert set with the
restriction that $|\mathcal{E}|=\mu|V|$; the selected set is then partitioned
into $\mathcal{E}_{1}$ and $\mathcal{E}_{0}$ like in the random adversary.
Finally, the _strong_ adversary chooses $\mathcal{E},\mathcal{E}_{1}$ and
$\mathcal{E}_{0}=\mathcal{E}\setminus\mathcal{E}_{1}$ arbitrarily such that
$|\mathcal{E}|=\mu|V|,|\mathcal{E}_{1}|=(1/2+\delta)|\mathcal{E}|$ and
consequently $|\mathcal{E}_{0}|=(1/2-\delta)|\mathcal{E}|$. We will ignore
rounding issues througout to facilitate the presentation.

All vertices that know the truth in a graph are assigned the label ‘1’,
including all vertices in $\mathcal{E}_{1}$, and all vertices that believe a
falsehood are labeled ‘0’. Vertices without an opinion bear no label. The
experts disseminate their opinions to the non-experts $V\setminus\mathcal{E}$
by a majority rule, that is, every vertex in $V\setminus\mathcal{E}$ takes the
opinion of the majority of its neighbouring experts. To be completely
explicit, a non-expert is labeled ‘1’/’0’ if more that half of its
neighbouring experts are labeled ‘1’/’0’. Vertices at which there is no
majority – because of a tie of ‘1’s and ‘0’s or because they have no expert
neighbours – decide upon their opinion uniformly at random, i.e., each of
these vertices is independently labeled ‘1’ with probability 1/2 and ‘0’
otherwise.

We say that a graph is _robust_ against the random/ weak/ strong adversary if
with high probability, for any choice of the expert set, after the
dissemination process more than half of the vertices are labeled ‘1’. ’With
high probability’ means with probability approaching 1 as $n$ approaches
infinity, which we sometimes abbreviate with whp. In [2] the authors studied
which properties of a graph make it robust. They discovered that all graphs
with maximal degree being sub-linear in $n$ are robust against the weak
adversary. Furthermore, they showed that certain well-connected networks are
robust against the strong adversary. In particular, such networks are either
Erdős-Rényi random graphs having edge probability $p$ greater than $c/n$ for a
suitable constant $c>0$, or expander graphs, with $d,\lambda_{2}$ being the
largest and second largest eigenvalue of its adjacency matrix, satisfying
$d\geq\lambda_{2}/(\delta\sqrt{\mu(1-\mu+2\delta\mu)}).$

Figure 1: This figure shows an example from [2]. The colors red/blue
correspond to the experts labeled ‘1’/’0’. The dotted vertices indicate their
label after the dissemination process, the unmarked vertices are decided
randomly. In the first line graph we consider the iterative strong adversary,
where only the rightmost blue vertex determines the label of all remaining
vertices. In the second line we consider the non-iterative setting, each blue
expert can at most convince two non-experts. If $1/2+\delta>3(1/2-\delta)$ and
$n$ is large, the adversary can not hope to convince more that half of all
vertices.

### Iterative Dissemination

In [2] the authors also introduced an iterative version of the model with a
more dynamic dissemination process. The _iterative model_ also starts with
labeled experts and all non-experts are labeled according to the majority of
their neighbouring experts. Ties that involve at least one expert are broken
uniformly at random. All non-experts without any expert neighbours, however,
do not form their opinion right away, but remain unlabeled. This process is
then iterated by considering all vertices with label ‘1’ and all vertices with
label ‘0’, until all vertices are labeled.

A natural question is whether iterativity helps or hinders the adversary.
Intuitively, iterativity ought to be beneficial for the adversary. If a graph
is not robust against a non-iterative adversary, then there is a choice of
expert sets such that after one round of dissemination there are more vertices
that are labeled ’0’ than ’1’. The remaining vertices without expert
neighbours are then either decided randomly (non-iterative) or there are
subsequent rounds of dissemination (iterative). As there now are more ’0’
labeled vertices that ’1’ labeled vertices, deciding the label of the
remaining vertices by dissemination should be beneficial for the adversary.
Indeed, the authors of [2] provided examples where this is the case. For
example, they showed that for suitable values of $\mu$ and $\delta$, a line
graph is robust against the non-iterative strong/weak adversaries, but not
against their iterative versions, see Fig. 1.

However, in [2] an additional example, where for the weak adversary the
opposite is true, was constructed. Consider a graph that is a disjoint union
of a star and a $d$-regular expander graph. Place one expert in the center of
the star and distribute the other experts as evenly as possible on the
expander. In the non-iterative setting, each expert in the expander will
spread its label to $d$ many non-experts. If the expert in the center of the
star is labeled ‘0’, all vertices in the star are labeled ‘0’ as well,
outweighing the difference between ‘1’s and ‘0’s in the expander. In the
iterative setting however, each expert does not only spread its label to $d$
many other vertices, but all vertices in the expander will be labeled at the
end of the dissemination, roughly in the same ratio as that of the experts in
the beginning. Now the difference in ‘1’s and ‘0’s is so large that even if
all vertices in the star were labeled with ‘0’ can sway the majority.

Guided by the intuition described previously, it seems that no such
construction can work for a strong adversary. In the previous example of the
graph consisting of an expander and a star the adversary can place all
’1’-labeled experts on the star and all others in the expander. Then, all
vertices in the expander will be labeled ’0’ resulting in a clear majority.
Consequently, in [2] the following conjecture concerning the effect of
iterativity in that case was made.

######  Conjecture 1.1 ([2]).

In the case of a strong adversary an iterative propagation can never harm the
adversary.

Equivalently, the conjecture states that there is no graph that is robust
against the iterative strong adversary and simulaneously not robust against
the non-iterative version – in this precise sense iterativity does not
harm/can only help the adversary.

### Related Results

Besides of [2], where this model for opinion formation was introduced, there
is one more work that studies questions in this precise framework. In his
doctoral thesis [10], Daknama studied resilience properties of random graphs.
’Local resilience’ in this context refers to the largest number of edges,
which are adjacent to any vertex, that can be removed so that the graph still
is robust against the strong adversary. In [10] it was shown that one can
delete up to a fraction of $2(1-\mu+2\delta\mu)\delta/(1+2\delta)$ of all
edges at each vertex without affecting robustness.

There are also other directly related studies in opinion forming, which,
however, do not use the exact model presented here. These papers include
studies on word of mouth [24], group recommendation [3, 15, 16, 12] and
informational cascades [6, 7, 23, 1, 13]. For further references see also [2].

### Result

The contribution of this paper is to refute Conjecture 1.1. The idea is to
consider a graph that has non-robustness against the non-iterative strong
adversary in a very weak way. More concretely, the majority for ’0’ labeled
vertices is only achieved if a majority of vertices without expert neighbours
is labeled ’0’. If we consider iterativity, then the adversary has no clear
advantage in a subsequent round of the dissemination, as there are roughly
equally many ’1’- and ’0’-labeled vertices. Additionally, we can construct the
graph in a way such that the vertices without expert neighbours are connected
to vertices that are labeled ’1’ in the first round of the dissemination, so
that the adversary _gets harmed_.

I \raisebox{-.9pt} {1}⃝ J \raisebox{-.9pt} {1}⃝ P \raisebox{-.9pt} {1}⃝ O
\raisebox{-.9pt} {1}⃝ D \raisebox{-.9pt} {0}⃝
$p_{IJ}$$p_{JP}$$p_{IP}$$1$$1$$1$$1\textbf{ : }1$
Figure 2: This figure shows the graph $G$. The numbers on the edges and in the
vertices give the probability that an edge is present between/in the
components. For example, any edge with one vertex in $I$ and one in $J$ exists
independently with probability $p_{IJ}$. Every vertex in $D$ has exactly one
distinct neighbour in $J$ and no other neighbours, i.e., every vertex in $D$
has degree 1 and no two vertices in $D$ have a common neighbour.

Consider the following graph that implements these ideas. Let
$0<\mu,\delta<1/2$ and $0<\varepsilon_{1}<2\delta/(1/2+\delta)$,
$0<\varepsilon_{2}<(1/2-\delta)/(1/2+\delta)$ as well as
$0<d<(1-\mu-2\delta\mu)/3$. Then the graph $G=(V,E),\ |V|=n$ is given by
$V=I\leavevmode\nobreak\ \dot{\cup}\leavevmode\nobreak\ J\leavevmode\nobreak\
\dot{\cup}\leavevmode\nobreak\ O\leavevmode\nobreak\
\dot{\cup}\leavevmode\nobreak\ P\leavevmode\nobreak\
\dot{\cup}\leavevmode\nobreak\ D$ such that

$|I\cup J|=|O\cup
P|=(1-d)\frac{n}{2},\quad|D|=dn,\quad|I|=\mu\left(\frac{1}{2}+\delta\right)n\quad\text{and}\quad|O|=\mu\left(\frac{1}{2}-\delta\right)n.$

The subset $D$ forms an independent set. In contrast, $I,J,O$ and $P$ each
form a clique. Every vertex in $O$ is connected to all other vertices except
to those in $D$. Between $I$ and $J$, $I$ and $P$ and $J$ and $P$ are random
bipartite graphs with edge-probabilities $p_{IJ}$, $p_{IP}$ and $p_{JP}$
respectively. Every vertex in $D$ has degree one, with the unique neighbor
being in $J$; moreover, no two vertices in $D$ have the same neighbour. There
are no more edges. Set

$p_{IJ}=p_{JP}=\frac{1/2-\delta}{1/2+\delta}+\varepsilon_{1}\qquad\text{and}\qquad\qquad
p_{IP}=\frac{1/2-\delta}{1/2+\delta}-\varepsilon_{2}.$

See Fig. 2 for a depiction of $G$.

Assume for now that the adversary chooses $\mathcal{E}_{1}=I$ and
$\mathcal{E}_{0}=O$. Then whp all vertices in $P$ will have
$\approx\varepsilon_{2}|I|$ more neighbours in $O$ than in $I$ by choice of
$p_{IP}$, thus they will be labeled ’0’ independently of iterativity. In
contrast, vertices in $J$ have $\approx\varepsilon_{1}|I|$ more neighbours in
$I$ than in $O$ and will consequently be labeled ’1’. Summarizing, we have
that all vertices in $I\cup J$ are labeled ’1’ and all vertices in $O\cup P$
are labeled ’0’. As both unions have by construction the same size, the labels
of vertices in $D$ decide whether the adversary succeeds or not. This is where
(non-)iterativity comes into play. In the non-iterative setting, vertices in
$D$ will choose uniformly at random, as they have no neighbours in $I\cup O$.
So, with positive probability there will be more vertices labeled ’0’ than ’1’
in $D$, consequently granting a majority of ’0’-labeled vertices. In the
iterative setting however, all vertices in $D$ will be labeled ’1’, as they
are exclusively connected to vertices in $J$. Thus, when choosing
$\mathcal{E}_{1}=I$ and $\mathcal{E}_{0}=O$ the iterative adversary fails,
while the non-iterative adversary succeeds. Choosing the proportions of
$I,O,J$ and $P$ and the edges between them suitably, we can make sure that
choosing $\mathcal{E}_{1}$ and $\mathcal{E}_{0}$ differently is not
advantageous for the adversary and therefore $G$ is indeed robust against the
iterative strong adversary. The main result of this paper is to show that the
graph $G$ has indeed the properties outlined above.

######  Theorem 1.2.

For all $0<\mu<1/2$ and $1/6<\delta<1/2$ there are
$\varepsilon_{1},\varepsilon_{2},d>0$ such that $G$ is whp robust against the
iterative strong adversary, but not against the non-iterative strong
adversary.

Note that $\delta>1/6$ is a necessary constraint for our construction, but we
are certain that there is an example for smaller $\delta$ as well. Permissible
values in Theorem 1.2 are, e.g. $\mu=\delta=1/5,\ \varepsilon_{1}=10^{-2},\
d=10^{-4}$ and $\varepsilon_{2}=10^{-6}.$ The remainder of this paper will
consist of the proof of Theorem 1.2. We first state and prove a well known
description of the edge distribution of random graphs and then show the
claimed (non-) robustness.

##  2 Proof

For a graph $G=(V,E)$ let $N(v)=\\{w\in V\mid(v,w)\in E\\}$ be the set of
neighbours of $v$. We begin with a statement about the distribution of edges
in random graphs.

######  Lemma 2.1.

Let $\varepsilon>0$. The Erdős-Rényi random graph $G(n,p)$ with vertex set $V$
and $p\geq\varepsilon$ has whp the following property. For any set $S\subseteq
V$ of size $|S|\geq\varepsilon n$ there is a set $X_{S}\subset V\setminus S$
of size at most ${4\varepsilon^{-3}(\ln\varepsilon^{-1}+2)}$ such that

$\forall v\in(V\setminus S)\setminus X_{S}:\big{|}|N(v)\cap
S|-p|S|\big{|}\leq\varepsilon p|S|.$

Similar versions of Lemma 2.1 with (somehow) different bounds exist in the
literature, see for example [14, Lem. IV.1 and IV.3]. However, as we did not
find the exact statement we will need in the literature we include a proof. We
will utilize the following Chernoff bound.

######  Theorem 2.2 ([4], Cor 7.11).

Let $X$ be a binomially distributed random variable. Then

${P}\Big{(}|X-\mathbb{E}[X]|>\delta\mathbb{E}[X]\Big{)}\leq
2\exp\left(-\min\\{\delta^{2},\delta\\}\mathbb{E}[X]/4\right),\qquad\delta>0.$

###### Proof of Lemma 2.1.

Let $S\subseteq V,|S|\geq\varepsilon n$ and let

$X_{S}=\big{\\{}v\in V\setminus S\bigm{|}\big{|}|N(v)\cap
S|-p|S|\big{|}>\varepsilon p|S|\big{\\}}$

be the set of vertices not satisfying the claim of the lemma. The number of
neighbours of any vertex $v\in V\setminus S$ is a binomially distributed
random variable, $|N(v)\cap S|\ =\text{Bin}(|S|,p)$, and the expected number
of neighbours of $v$ in $S$ is $p|S|$. Thus the probability of $v\in X_{S}$
can be bounded with Theorem 2.2 by

${P}\big{(}\big{|}|N(v)\cap S|-p|S|\big{|}>\varepsilon
p|S|\big{)}\leq\exp\left(-\varepsilon^{2}p|S|/4\right).$

Let furthermore $t\in\mathbb{N}$; the probability that $t$ distinct vertices
are in $X_{S}$ is at most $\exp(-\varepsilon^{2}p|S|/4\cdot t)$ as the events
of vertices being elements of $X_{S}$ are independent. There are
$\binom{n}{k}\leq\left(\frac{en}{k}\right)^{k}$ possibilities to choose $S$, a
set of size $k\geq\varepsilon n$. Hence the probability that for fixed
$k\geq\varepsilon n$ there is a set $S,|S|=k$ such that $|X_{S}|=t$ is by
union bound at most

$\displaystyle\exp\left(k\ln(en/k)-\frac{\varepsilon^{2}pk}{4}\cdot
t\right)\leq\exp\left(k\left(-\ln\varepsilon+1-\frac{\varepsilon^{3}}{4}\cdot
t\right)\right),$

where we used the assumption that $p\geq\varepsilon$. Thus, if
$t\geq{4{\varepsilon^{-3}}(\ln\varepsilon^{-1}+2)}$ this expression is $\leq
e^{-k}$ and summing over $k\geq\varepsilon n$ yields the claim. ∎

This concludes the preparations. Next we prove the main theorem, by proving
the two claims separately. We show the robustness of $G$ against the iterative
strong adversary first.

######  Lemma 2.3.

For all $0<\mu<1/2$ and $1/6<\delta<1/2$ there are values
$\varepsilon_{1},\,\varepsilon_{2},\,d>0$ such that $G$ is whp robust against
the iterative strong adversary.

###### Proof.

Let $0<\mu<1/2,\ 1/6<\delta<1/2$ and $\varepsilon_{1},\varepsilon_{2},\ d>0$
such that

$\displaystyle\varepsilon_{1}<\min\left\\{\frac{\delta\mu}{2},\frac{4\delta}{1/2+\delta}-1\right\\}$
(2.1)

and furthermore

$\displaystyle
d<\min\left\\{\frac{\varepsilon_{1}\delta}{1/2+\delta},\frac{\varepsilon_{1}\delta\mu}{4},\frac{1-\mu-2\delta\mu}{3}\right\\}$
(2.2)

as well as

$\displaystyle\varepsilon_{2}<\min\left\\{\frac{d}{6}\left(\frac{4\delta}{1/2+\delta}-1-\varepsilon_{1}\right),\frac{1/2-\delta}{1+2\delta}\right\\}.$
(2.3)

We will show that for any choice of experts, at the end of the dissemination
the majority will be labeled ’1’ thus proving robustness. Let therefore
$\mathcal{E}=\mathcal{E}_{1}\cup\mathcal{E}_{0}$ be any set of experts as
chosen by the iterative strong adversary and define

$i_{1}:=|I\cap\mathcal{E}_{1}|,\quad j_{1}:=|J\cap\mathcal{E}_{1}|,\quad
o_{1}:=|O\cap\mathcal{E}_{1}|,\quad p_{1}:=|P\cap\mathcal{E}_{1}|,\quad
d_{1}:=|D\cap\mathcal{E}_{1}|$

as well as

$i_{0}:=|I\cap\mathcal{E}_{0}|,\quad j_{0}:=|J\cap\mathcal{E}_{0}|,\quad
o_{0}:=|O\cap\mathcal{E}_{0}|,\quad p_{0}:=|P\cap\mathcal{E}_{0}|,\quad
d_{0}:=|D\cap\mathcal{E}_{0}|.$

By definition of the model we have that
$|\mathcal{E}_{1}|=\left({1}/{2}+\delta\right)\mu n$ as well as
$|\mathcal{E}_{0}|=\left({1}/{2}-\delta\right)\mu n$ and therefore

$\displaystyle
i_{1}+j_{1}+o_{1}+p_{1}+d_{1}=\left(\frac{1}{2}+\delta\right)\mu
n\quad\text{and}\quad
i_{0}+j_{0}+o_{0}+p_{0}+d_{0}=\left(\frac{1}{2}-\delta\right)\mu n,$ (2.4)

which readily implies that

$\displaystyle 2\delta\mu
n=\frac{2\delta}{1/2+\delta}(i_{1}+j_{1}+p_{1}+o_{1}+d_{1}).$ (2.5)

We will see that the iterative dissemination will be finished after two rounds
only. We start by determining the label of each vertex in the different
components after the first round of dissemination. This is decided by the
difference in ‘0’/‘1’ labeled expert neighbours. Consider the difference

$\Delta(v):=|N(v)\cap\mathcal{E}_{1}|-|N(v)\cap\mathcal{E}_{0}|,\quad v\in V.$

In particular, $\Delta(v)>0$ means that $v\in
V\setminus(\mathcal{E}_{1}\cup\mathcal{E}_{0})$ will be labeled ‘1’ and
$\Delta(v)<0$ means it will be labeled ‘0’. Note that vertices $v$ with
$\Delta(v)=0$ could be either labeled randomly (if they have the same positive
number of ’0’/’1’ labeled neighbours) or not at all in this round.

We begin with a vertex $v\in O$. Using the construction of $G$ and (2.4) we
get

$\displaystyle|N(v)\cap\mathcal{E}_{1}|$
$\displaystyle=i_{1}+j_{1}+p_{1}+o_{1}=\left(\frac{1}{2}+\delta\right)\mu
n-d_{1}$

and similarly

$\displaystyle|N(v)\cap\mathcal{E}_{0}|$
$\displaystyle=i_{0}+j_{0}+p_{0}+o_{0}=\left(\frac{1}{2}-\delta\right)\mu
n-d_{0}.$

Combining these two equations, $d<\varepsilon_{1}<\delta\mu/2$ given by (2.2)
and (2.1) implies

$\Delta(v)=2\delta\mu n-(d_{1}-d_{0})>0\qquad\forall\leavevmode\nobreak\ v\in
O.$

We continue with $v\in J$. Using Lemma 2.1, we get that for all
$\varepsilon>0$ whp there is $J_{P}\subset J,\leavevmode\nobreak\ |J_{P}|\leq
4\varepsilon^{-3}(\ln\varepsilon^{-1}+2)$ such that

$\big{|}|N(v)\cap P\cap\mathcal{E}_{1}|-p_{JP}\cdot
p_{1}\big{|}\leq\varepsilon\cdot p_{JP}\cdot p_{1}+\varepsilon n\quad\text{for
all }v\in J\setminus J_{P}.$

As $\varepsilon>0$ is arbitrary we infer that

$|N(v)\cap P\cap\mathcal{E}_{1}|=p_{JP}\cdot p_{1}+o(n)\quad\text{for all
}v\in J\setminus J_{P}.$

Completely analogous calculations for $I$ and $\mathcal{E}_{0}$ yield that whp
there is $J^{\prime}\subset J,\leavevmode\nobreak\
|J^{\prime}|\leavevmode\nobreak\ =o(n)$ such that for all $v\in J\setminus
J^{\prime}$

$\displaystyle|N(v)\cap\mathcal{E}_{1}|$ $\displaystyle=p_{IJ}\cdot
i_{1}+j_{1}+p_{JP}\cdot p_{1}+o_{1}+o(n)$
$\displaystyle=\left(\frac{1}{2}+\delta\right)\mu
n-(1-p_{IJ})i_{1}-(1-p_{JP})p_{1}-d_{1}+o(n)$

and

$\displaystyle|N(v)\cap\mathcal{E}_{0}|$ $\displaystyle=p_{IJ}\cdot
i_{0}+j_{0}+p_{JP}\cdot p_{0}+o_{0}+o(n)$
$\displaystyle=\left(\frac{1}{2}-\delta\right)\mu
n-(1-p_{IJ})i_{0}-(1-p_{JP})p_{0}-d_{0}+o(n).$

Computing the difference of the above expressions we get for all $v\in
J\setminus J^{\prime}$

$\displaystyle\Delta(v)$ $\displaystyle=2\delta\mu
n-(1-p_{IJ})(i_{1}-i_{0})-(1-p_{JP})(p_{1}-p_{0})-(d_{1}-d_{0})+o(n)$
$\displaystyle=2\delta\mu
n-\left(\frac{2\delta}{1/2+\delta}-\varepsilon_{1}\right)\Big{(}(i_{1}-i_{0})+(p_{1}-p_{0})\Big{)}-(d_{1}-d_{0})+o(n)$
$\displaystyle=2\delta\mu
n-\frac{2\delta}{1/2+\delta}\Big{(}(i_{1}-i_{0})+(p_{1}-p_{0})\Big{)}+\varepsilon_{1}\Big{(}(i_{1}-i_{0})+(p_{1}-p_{0})\Big{)}-(d_{1}-d_{0})+o(n).$

Applying (2.5) and (2.4) we can obtain a lower bound for $\Delta(v),v\in
J\setminus J^{\prime}$

$\displaystyle\Delta(v)$
$\displaystyle\geq\frac{2\delta}{1/2+\delta}(j_{1}+o_{1}+d_{1}+i_{0}+p_{0})+\varepsilon_{1}\Big{(}(i_{1}-i_{0})+(p_{1}-p_{0})\Big{)}-d_{1}+o(n)$
$\displaystyle\geq\varepsilon_{1}(i_{1}+j_{1}+p_{1}+o_{1}+d_{1})+\left(\frac{2\delta}{1/2+\delta}-\varepsilon_{1}\right)(i_{0}+p_{0})-d_{1}.$

According to (2.1) and (2.2) we have $\varepsilon_{1}<2\delta/(1/2+\delta)$ as
well as $d<\varepsilon_{1}\delta\mu/4$ and therefore

$\displaystyle\Delta(v)\geq\varepsilon_{1}\cdot 2\delta\mu
n-dn>0\qquad\forall\leavevmode\nobreak\ v\in J\setminus J^{\prime}.$

Next we look at $v\in I.$ Using again Lemma 2.1 and (2.4) we infer that whp
there is $I^{\prime}\subset I,\leavevmode\nobreak\
|I^{\prime}|\leavevmode\nobreak\ =o(n)$ such that for all $v\in I\setminus
I^{\prime}$

$\displaystyle|N(v)\cap\mathcal{E}_{1}|$ $\displaystyle=i_{1}+p_{IJ}\cdot
j_{1}+p_{IP}\cdot p_{1}+o_{1}+o(n)$
$\displaystyle=\left(\frac{1}{2}+\delta\right)\mu
n-\left(1-p_{IJ}\right)j_{1}-\left(1-p_{IP}\right)p_{1}-d_{1}+o(n)$

and

$\displaystyle|N(v)\cap\mathcal{E}_{0}|$ $\displaystyle=i_{0}+p_{IJ}\cdot
j_{0}+p_{IP}\cdot p_{0}+o_{0}+o(n)$
$\displaystyle=\left(\frac{1}{2}-\delta\right)\mu
n-\left(1-p_{IJ}\right)j_{0}-\left(1-p_{IP}\right)p_{0}-d_{0}+o(n).$

By combining those bounds we obtain for all $v\in I\setminus I^{\prime}$

$\displaystyle\Delta(v)$ $\displaystyle=2\delta\mu
n-\left(1-p_{IJ}\right)(j_{1}-j_{0})-\left(1-p_{IP}\right)(p_{1}-p_{0})-(d_{1}-d_{0})+o(n)$
(2.6) $\displaystyle=2\delta\mu
n-\frac{2\delta}{1/2+\delta}\Big{(}(j_{1}-j_{0})+(p_{1}-p_{0})\Big{)}-(d_{1}-d_{0})+\varepsilon_{1}(j_{1}-j_{0})-\varepsilon_{2}(p_{1}-p_{0})+o(n).$

Before we conclusively determine $\Delta(v)$ for $v\in I\setminus I^{\prime}$
we look at vertices $v\in P$. Using once more Lemma 2.1 and (2.4) we infer
that whp there is $P^{\prime}\subset P,\leavevmode\nobreak\
|P^{\prime}|\leavevmode\nobreak\ =o(n)$ such that for all $v\in P\setminus
P^{\prime}$

$\displaystyle|N(v)\cap\mathcal{E}_{1}|$ $\displaystyle=p_{IP}\cdot
i_{1}+p_{JP}\cdot j_{1}+p_{1}+o_{1}+o(n)$
$\displaystyle=\left(\frac{1}{2}+\delta\right)\mu
n-\left(1-p_{IP}\right)i_{1}-\left(1-p_{JP}\right)j_{1}-d_{1}+o(n)$

and

$\displaystyle|N(v)\cap\mathcal{E}_{0}|$ $\displaystyle=p_{IP}\cdot
i_{0}+p_{JP}\cdot j_{0}+p_{0}+o_{0}+o(n)$
$\displaystyle=\left(\frac{1}{2}-\delta\right)\mu
n-\left(1-p_{IP}\right)i_{0}-\left(1-p_{JP}\right)j_{0}-d_{0}+o(n).$

Together these two expressions yield for all $v\in P\setminus P^{\prime}$

$\displaystyle\Delta(v)$ $\displaystyle=2\delta\mu
n-\frac{2\delta}{1/2+\delta}\Big{(}(i_{1}-i_{0})+(j_{1}-j_{0})\Big{)}-(d_{1}-d_{0})+\varepsilon_{1}(j_{1}-j_{0})-\varepsilon_{2}(i_{1}-i_{0})+o(n).$
(2.7)

We argue next, that either “$\Delta(v)<0\text{ for some }v\in I\setminus
I^{\prime}\,$” or “$\Delta(v)<0\text{ for some }v\in P\setminus P^{\prime}\,$”
but never both. To see this, observe that

$\text{``}\Delta(v)<0\text{ for some }v\in I\setminus
I^{\prime}\quad\text{and}\quad\Delta(v)<0\text{ for some }v\in P\setminus
P\,\text{''}$

implies that

$\displaystyle(i_{1}-i_{0})+(j_{1}-j_{0})\quad\text{and}\quad(j_{1}-j_{0})+(p_{1}-p_{0})\quad\text{are
both}\quad\geq((1/2+\delta)\mu-\varepsilon_{1})n.$ (2.8)

Otherwise (2.2) and (2.3) assert that $\varepsilon_{2}<d/6$ as well as
$d<\varepsilon_{1}\delta/(1/2+\delta)$ and therefore either by (2.6)

$\displaystyle\Delta(v)$
$\displaystyle\geq\frac{2\delta}{1/2+\delta}\varepsilon_{1}n-dn-\varepsilon_{2}n>0,\qquad\text{for
all }v\in I\setminus I^{\prime}$

or by (2.7)

$\displaystyle\Delta(v)$
$\displaystyle\geq\frac{2\delta}{1/2+\delta}\varepsilon_{1}n-dn-\varepsilon_{2}n>0,\qquad\text{for
all }v\in P\setminus P^{\prime}.$

However, as $(i_{1}-i_{0})+(p_{1}-p_{0})\leq(1/2+\delta)\mu n$ we obtain from
(2.8) that $j_{1}-j_{0}\geq(\delta\mu-\varepsilon_{1})n$. Then (2.1),(2.2) and
(2.3) imply that $\varepsilon_{1}<\delta\mu/2,\,d<\varepsilon_{1}\delta\mu/$
and $\varepsilon_{2}<d/6$ and thus (2.6) yields

$\displaystyle\Delta(v)$
$\displaystyle\geq\varepsilon_{1}\cdot(\delta\mu-\varepsilon_{1})n-dn-\varepsilon_{2}n>0,\qquad\text{for
all }v\in I\setminus I^{\prime}.$

Summarizing, we have shown that $\Delta(v)>0$ for all $v\in(J\setminus
J^{\prime})\cup O$ and either $\Delta(v)>0$ for all $v\in I\setminus
I^{\prime}$ or $\Delta(v)>0$ for all $v\in P\setminus P^{\prime}$.

In the rest of the proof we consider the second round of the iterative
dissemination process. We will distinguish two cases. Assume first that
$j_{0}+d_{0}<(d/2-\varepsilon_{2})n$. As $\Delta(v)>0$ for all $v\in
J\setminus J^{\prime}$ we infer that at most $(d/2-\varepsilon_{2})n+o(n)$
vertices in $D$ will be labeled ‘0’ after the second round of the
dissemination process, all other vertices in $D$ will be labeled ‘1’. Thus
counting the total number of vertices labeled ‘1’ after the process, we get in
this case for $n$ large enough

$\displaystyle\\#(\text{vertices labeled `1'})$ $\displaystyle>|I\setminus
I^{\prime}|\ +\ |J\setminus J^{\prime}|\ +\ |O|\
+\left(\frac{d}{2}+\varepsilon_{2}-o(1)\right)n-|\mathcal{E}_{0}|$
$\displaystyle=(1-d)\frac{n}{2}+\frac{dn}{2}+\varepsilon_{2}n-o(n)>\frac{n}{2}.$

We are left with the case $j_{0}+d_{0}\geq(d/2-\varepsilon_{2})n$. Observe
that $d_{1}<(d/2+\varepsilon_{2})n$ as otherwise the conclusion of the
previous case applies. We revisit $\Delta(v),\ v\in P\setminus P^{\prime}$
using (2.7) and (2.5)

$\displaystyle\Delta(v)$
$\displaystyle=\frac{2\delta}{1/2+\delta}(p_{1}+o_{1}+d_{1}+i_{0}+j_{0})-(d_{1}-d_{0})+\varepsilon_{1}(j_{1}-j_{0})-\varepsilon_{2}(i_{1}-i_{0})+o(n)$
$\displaystyle\geq\left(\frac{2\delta}{1/2+\delta}-\varepsilon_{1}\right)j_{0}+d_{0}-\left(1-\frac{2\delta}{1/2+\delta}\right)d_{1}-\varepsilon_{2}i_{1}+o(n).$

Using the assumptions $j_{0}+d_{0}\geq(d/2-\varepsilon_{2})n$ and
$d_{1}<(d/2+\varepsilon_{2})n$, this simplifies to

$\displaystyle\Delta(v)$
$\displaystyle>\left(\frac{4\delta}{1/2+\delta}-1-\varepsilon_{1}\right)dn/2-3\varepsilon_{2}n+o(n).$

Assumption (2.3) guarantees that $\Delta(v)>0,\ v\in P\setminus P^{\prime}$
and thus in this case for $n$ large enough

$\displaystyle\\#(\text{vertices labeled '1'})$ $\displaystyle>|I\setminus
I^{\prime}|\ +\ |J\setminus J^{\prime}|\ +\ |O|\ +\ |P\setminus P^{\prime}|\
-\ |\mathcal{E}_{0}|$ $\displaystyle=(1-d)n-\left(\frac{1}{2}-\delta\right)\mu
n-o(n)>\frac{n}{2},$

and the proof is completed. ∎

The next lemma together with Lemma 2.3 implies Theorem 1.2.

######  Lemma 2.4.

For all $0<\mu<1/2$ and $1/6<\delta<1/2$ there are values
$\varepsilon_{1},\varepsilon_{2},d>0$ such that whp $G$ is not robust against
the non-iterative strong adversary.

###### Proof.

Let $0<\mu<1/2$ and $1/6<\delta<1/2$ and
$\varepsilon_{1},\,\varepsilon_{2},\,d>0$ as given in (2.1) to (2.3). We show
that $G$ is indeed not robust by giving a suitable choice of the expert set.
Set $\mathcal{E}=\mathcal{E}_{1}\cup\mathcal{E}_{0}$ with $\mathcal{E}_{1}=I$
and $\mathcal{E}_{0}=O$. By definition, these sets have matching
cardinalities. We compute the quantity

$\Delta(v)=|N(v)\cap\mathcal{E}_{1}|-|N(v)\cap\mathcal{E}_{2}|$

for vertices $v\in P$ to find their labels. Using
$\varepsilon_{2}<(1/2-\delta)/(1+2\delta)$ by (2.3) and Theorem 2.2 we readily
obtain that whp for all $v\in P$

$\displaystyle\Delta(v)\leq(p_{IP}+o(1))|\mathcal{E}_{1}|-|\mathcal{E}_{0}|=\left(\frac{1/2-\delta}{1/2+\delta}-\varepsilon_{2}+o(1)\right)|\mathcal{E}_{1}|-|\mathcal{E}_{0}|=-(\varepsilon_{2}+o(1))|\mathcal{E}_{1}|<0.$

Therefore the set of vertices labeled ‘0’ contains $O\cup P$ which has
cardinality $(1-d)\frac{n}{2}$. However, vertices in $D$ do not have any
expert neighbours and as we are in the non-iterative setting, those vertices
will be decided uniformly at random. Hence with probability $1/2$ there will
be at least $dn/2+1$ vertices labeled ‘0’ in $D$ and therefore $G$ is not
robust against the non-iterative strong adversary. ∎

## References

  * [1] N. Alon, M. Babaioff, R. Karidi, R. Lavi, and M. Tennenholtz.  Sequential voting with externalities: herding in social networks.  In Proceedings of the 13th ACM Conference on Electronic Commerce (EC). ACM, 2012.
  * [2] N. Alon, M. Feldman, O. Lev, and M. Tennenholtz.  How Robust Is the Wisdom of the Crowds?  In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), pages 2055–2061, 2015.
  * [3] R. Andersen, C. Borgs, J. Chayes, U. Feige, A. Flaxman, A. Kalai, V. Mirrokni, and M. Tennenholtz.  Trust-based recommendation systems: an axiomatic approach.  In Proceedings of the 17th International Conference on World Wide Web, pages 199–208, 2008.
  * [4] S. Arora and B. Barak.  Computational complexity: a modern approach.  Cambridge University Press, 2009.
  * [5] W. Aspinall.  A route to more tractable expert advice.  Nature, 463(7279):294–295, 2010.
  * [6] S. Bikhchandani, D. Hirshleifer, and I. Welch.  A theory of fads, fashion, custom, and cultural change as informational cascades.  Journal of Political Economy, 100(5):992–1026, 1992.
  * [7] S. Bikhchandani, D. Hirshleifer, and I. Welch.  Learning from the behavior of others: Conformity, fads, and informational cascades.  Journal of economic perspectives, 12(3):151–170, 1998.
  * [8] D. V. Budescu and E. Chen.  Identifying expertise to extract the wisdom of crowds.  Management Science, 61(2):267–280, 2015.
  * [9] R. M. Cooke and L. L. Goossens.  Tu delft expert judgment data base.  Reliability Engineering & System Safety, 93(5):657–674, 2008.
  * [10] R. Daknama.  Theoretical runtime bounds for information spreading and a new vehicle routing algorithm.  PhD thesis, lmu, 2018.
  * [11] E. Dwoskin and C. Timberg.  How merchants use Facebook to flood Amazon with fake reviews, 2018.  https://www.washingtonpost.com/business/economy/how-merchants-secretly-use-facebook-to-flood-amazon-with-fake-reviews/2018/04/23/5dad1e30-4392-11e8-8569-26fda6b404c7_story.html?, visited 02.11.21.
  * [12] P. Faliszewski, J. Rothe, and H. Moulin.  Control and Bribery in Voting, page 146–168.  Cambridge University Press, 2016.
  * [13] M. Feldman, N. Immorlica, B. Lucier, and S. M. Weinberg.  Reaching consensus via non-bayesian asynchronous learning in social networks.  Approximation, Randomization, and Combinatorial Optimization, pages 192–208, 2014.
  * [14] N. Fountoulakis, A. Huber, and K. Panagiotou.  Reliable broadcasting in random networks and the effect of density.  In 2010 Proceedings IEEE INFOCOM, pages 1–9. IEEE, 2010.
  * [15] U. Grandi and P. Turrini.  A network-based rating system and its resistance to bribery.  In Proceedings of the 25th International Joint Conference on Artificial Intelligence, pages 301–307, 2016.
  * [16] O. Lev and M. Tennenholtz.  Group recommendations: Axioms, impossibilities, and random walks.  arXiv preprint arXiv:1707.08755, 2017.
  * [17] K. Masters.  The New Black Hat Tactics Amazon Sellers Are Using To Take Out Their Competition, 2019.  https://www.forbes.com/sites/kirimasters/2019/02/19/the-new-black-hat-tactics-amazon-sellers-are-using-to-take-out-their-competition/#5440a8c53f58, visited 02.11.21.
  * [18] B. Mellers, L. Ungar, J. Baron, J. Ramos, B. Gurcay, K. Fincher, S. E. Scott, D. Moore, P. Atanasov, S. A. Swift, et al.  Psychological strategies for winning a geopolitical forecasting tournament.  Psychological Science, 25(5):1106–1115, 2014.
  * [19] M. G. Morgan.  Use (and abuse) of expert elicitation in support of decision making for public policy.  Proceedings of the National academy of Sciences, 111(20):7176–7184, 2014.
  * [20] T. Noonan.  ReviewMeta, 2016.  https://reviewmeta.com, visited 02.11.21.
  * [21] T. I. Oprea, C. G. Bologa, S. Boyer, R. F. Curpan, R. C. Glen, A. L. Hopkins, C. A. Lipinski, G. R. Marshall, Y. C. Martin, L. Ostopovici-Halip, et al.  A crowdsourcing evaluation of the nih chemical probes.  Nature chemical biology, 5(7):441–447, 2009.
  * [22] E. M. Rogers.  Diffusion of innovations (5th ed.).  Free Press, 2003.
  * [23] D. Watts.  A simple model of global cascades on random networks.  Proceedings of the National Academy of Sciences, 99(9):5766–5771, 2002.
  * [24] H. P. Young.  Innovation diffusion in heterogeneous populations: Contagion, social influence, and social learning.  American economic review, 99(5):1899–1924, 2009.