\documentclass{elsart}
\usepackage{graphicx,amssymb}
\begin{document}
\begin{frontmatter}
  
  \title{Unity and Discord in Opinion Dynamics} \author{E.
    Ben-Naim$^{\dag}$, P. L. Krapivsky$^{\ddag}$, F. Vazquez$^{\dag}$, and
    S.~Redner$^{\ddag}$}
  
  \address{$^{\dag}$Theoretical Division and Center for Nonlinear Studies,
    Los Alamos National Laboratory, Los Alamos, New Mexico, 87545}
  
  \address{$^{\ddag}$Center for BioDynamics, Center for Polymer Studies, and
    Department of Physics, Boston University, Boston, MA, 02215}

\begin{abstract}
  
  We study opinion dynamics models where agents evolve via repeated pairwise
  interactions.  In the compromise model, agents with sufficiently close
  real-valued opinions average their opinions.  A steady state is reached
  with a finite number of isolated, noninteracting opinion clusters
  (``parties'').  As the initial opinion range increases, the number of such
  parties undergoes a periodic bifurcation sequence, with alternating major
  and minor parties.  In the constrained voter model, there are leftists,
  centrists, and rightists.  A centrist and an extremist can both become
  centrists or extremists in an interaction, while leftists and rightists do
  not affect each other.  The final state is either consensus or a frozen
  population of leftists and rightists.  The evolution in one dimension is
  mapped onto a constrained spin-1 Ising chain with zero-temperature Glauber
  kinetics.  The approach to the final state exhibits a non-universal
  long-time tail.

\end{abstract}
\keyword{opinion dynamics, bifurcations, voter model, Glauber kinetics
\PACS 02.50.Cw, 05.45.-a, 64.60.My,  75.40.Gb, 89.65.-s,}}
\end{frontmatter}
  
\section{Introduction}

Opinions of individuals in a heterogeneous society evolve due to influences
of acquaintances.  In principle, opinions could evolve forever, consensus
could emerge, or a population could condense into a finite set of distinct
opinion clusters, or ``parties''.  The modeling of such phenomena, both by
social scientists \cite{F74,axelrod,weid} and by statistical physicists
\cite{galam,CMV,szn,holyst,stauffer} is a vibrant area.  In this contribution
to the Randomness and Complexity conference in honor of Shlomo Havlin's
$60^{\rm th}$ birthday, we discuss two simple models for this type of opinion
evolution.

In the {\it compromise model\/} \cite{opinion,opinion-bkr}, the opinion of
each individual is a real-valued variable on a finite range.  In an
interaction, two compatible agents average their current opinions, while
there is no interaction between agents whose opinion difference exceeds a
specified threshold.  These rules model the competition between compromise
and conviction as a function of the opinion difference of two individuals.
To implement the dynamics, two agents are picked at random and they interact
if compatible.  This basic step is repeated {\it ad infinitum}.

A simplified stochastic version of this process is the {\it constrained voter
  model} \cite{VKR}.  Here, each individual has three states --- leftist,
centrist, and rightist.  In an event, an agent adopts the opinion of a
randomly-chosen neighbor, as in the voter model \cite{voter}, but with the
proviso that leftists and rightists do not interact.  Due to this constraint,
the outcome can be either consensus or a frozen mixture of extremists with no
centrists.

\section{Compromise Model}

In an interaction, agents with opinions $x_1$ and $x_2$ (with $|x_2-x_1|<1$)
average their opinions: $(x_1,x_2)\to
\frac{1}{2}\left(x_1+x_2,x_1+x_2\right)$; if $|x_2-x_1|>1$, no interaction
occurs.  Let $P(x,t)\,dx$ be the fraction of agents with opinions in the
range $[x,x+dx]$ at time $t$.  This distribution evolves according to
\cite{opinion-bkr}
\begin{eqnarray}
\label{pxt}
{\partial\over \partial t}P(x,t)=\!\int\!\!\!\int
dx_1dx_2P(x_1,t)P(x_2,t)\left[\delta\left(x\!-\!{x_1+x_2\over 2}\right)\!
-\!\delta(x-x_1)\right],
\end{eqnarray}
where the integration is over all $|x_1-x_2|<1$.  When all agents can
interact, namely, when $\Delta<1/2$, the rate equations are integrable
\cite{bk,bal}.  In particular, the second moment vanishes as
$M_2(t)=M_2(0)\,e^{-M_0t/2}$, with $M_0=2\Delta$, where $M_k(t)\equiv\int
dx\,x^k\,P(x,t)$ is the $k^{\rm th}$ moment.  The distribution itself
approaches consensus as $P(x,t)\propto M_0/\left[w(1+z^2)^2\right]$
\cite{bal}, with variance $w=M_2^{1/2}/M_0$ and scaling variable $z=x/w$.

For larger values of $\Delta$, the opinion distribution does not condense
into a single cluster, but rather the distribution evolves into ``parties''
that are separated by distances larger than one.  This behavior results from
an instability that propagates from the boundary toward the center
(Fig.~\ref{evol}).  Once each party is isolated, it then separately evolves
into a delta function so that the final distribution consists of a series of
non-interacting delta-function clusters.

Numerical integration of the rate equations reveals \cite{opinion-bkr} a
striking bifurcation sequence in the cluster (party) locations
(Fig.~\ref{evol}).  There are three types of clusters: major (mass $M>1$),
minor (mass $m<10^{-2}$), and a central cluster located exactly at $x=0$.
When $\Delta<1$, the final state is a single peak located at the origin.
When $\Delta>1$, two new clusters are born at the extreme edges, $x\approx
\pm\Delta$.  As $\Delta$ increases, three basic bifurcations occur:

\begin{enumerate}
\item Nucleation of a symmetric cluster pair: $\emptyset\to \{-x,x\}$ with
  $x\approx 1$.
\item Annihilation of the central cluster and simultaneous nucleation of a
  symmetric cluster pair: $\{0\}\to \{-x,x\}$ with $x\approx 0.75$.
\item Nucleation of a central cluster: $\emptyset\to\{0\}$.
\end{enumerate}

\begin{figure}[ht] 
\begin{center}
\vspace*{0.cm} \includegraphics*[width=0.45\textwidth]{fig1a.eps}
\includegraphics*[width=0.5\textwidth]{fig1b.eps}
\caption{(Left) Early-time evolution of the opinion distribution $P(x,t)$ 
  for $\Delta=4.3$. (Right) Location of final state clusters versus initial
  opinion range $\Delta$ (red: clusters via type-1 bifurcations, blue:
  type-2, green: type-3).  The color coded vertical arrows indicate the
  location of the first 3 bifurcations.}
\label{evol}
\end{center}
\end{figure}

The cluster masses vary periodically in $\Delta$ and organize in an
alternating major-minor pattern.  The major clusters contain nearly the
entire system mass, while the minor clusters are much smaller
(Fig.~\ref{cluster-mass}).  Near a type-3 bifurcation, a central cluster
nucleates with infinitesimal mass, initially grows slowly, then explosively
until its mass becomes of order one.  Finally, its mass grows linearly with
$\Delta$.  At the next type-2 bifurcation threshold, the central cluster then
splits into two major clusters (Fig.~\ref{cluster-mass}).  This
birth-and-death pattern repeats.


The minor clusters exhibit two subtle features.  First, the mass of the most
extreme cluster saturates to a mass $m'$ that is approximately one order of
magnitude greater than all other minor clusters.  Second, the mass of the
minor clusters varies non-monotonically with $\Delta$, and there is a small
range of $\Delta$, where the mass of a newly-born minor cluster suddenly
drops (Fig.~\ref{cluster-mass}) before the mass saturates.

At type-1 and type-3 bifurcations, the mass of the nascent clusters varies as
$m\sim (\Delta-\Delta_n)^{\alpha_n}$ as $\Delta\to\Delta_n$.  The exponent
depends only on the type $n$ of the bifurcation point; numerically we find
$\alpha_1\approx 3$ and $\alpha_3\approx 4$.  To understand the behavior near
a type-1 bifurcation, consider the first one at $\Delta_1=1$.  Let
$\Delta=1+\epsilon$ with $\epsilon\to 0$.  It is convenient to divide the
opinion range $(-\Delta, \Delta)$ into a central subinterval $(-1,1)$ and two
boundary subintervals: $\pm(1,1+\epsilon)$.  Let $m(t)$ be the mass in a
boundary subinterval.  This mass decays due to the interaction with agents in
the central subinterval.  As a result, $\dot m=-m$, which together with the
initial condition $m(0)=\epsilon$, gives $m(t)=\epsilon\,e^{-t}$.

\begin{figure}[ht] 
\begin{center}
 \vspace*{0.cm}
 \includegraphics*[width=0.6\textwidth]{fig2.eps}
\caption{Cluster mass versus opinion range (same color scheme 
  as Fig.~1).  The central clusters (green) and the major clusters (blue) are
  shown on a linear scale (top), while the minor clusters (red) are shown on
  a logarithmic scale (bottom).}
\label{cluster-mass}
\end{center}
\end{figure}
 
On the other hand, the mass of the central subinterval is concentrated in a
region about the origin whose width $w(t)$ decreases with time.  At some
moment $t_f$ the separation between the masses in the central and boundary
subintervals exceeds unity.  If we assume that the mass in the boundary
subinterval is at its center, $x=1+\epsilon/2$, the separation criterion is
$w(t_f)\sim \epsilon/2$.  For $t\gg t_f$, the interaction between the two
subintervals stops and the mass of the emerging minor cluster freezes at
$m_f\sim \epsilon\,e^{-t_f}$.

We estimate the width $w(t)$ by noting that, to zeroth order in $\epsilon$,
(i) the central subinterval is not affected by boundary subintervals, and
(ii) all agents are eventually within the interaction range.  Therefore the
asymptotic time dependence of $w(t)$ is the same as in the case $\Delta<1/2$.
Thus $w(t)\sim M_2^{1/2}\sim e^{-t/2}$, since $\Delta=1+\epsilon\cong 1$.
Using the stopping criterion, $w(t_f)\sim e^{-t_f/2}\sim \epsilon$, the final
minor cluster mass is $m_f\sim \epsilon\,e^{-t_f}\sim \epsilon^3$, leading to
$\alpha_1=3$.  For a type-3 bifurcation, a similar argument yields
$\alpha_3=4$ \cite{opinion-bkr}.

\section{Constrained Voter Model}

The constrained voter model is a simple discrete-state version of the
previous compromise model in which each agent can have one of the three
opinions of leftist, centrist, and rightist.  Similar to the compromise
model, agents with nearby opinions can interact, while agents with distant
opinions cannot.  Thus in an interaction, a centrist and an extremist (either
on the left or the right) can both become centrists or both become extremists
of the same persuasion as the initial extremist.  Notice that this
interaction is not compromise, but rather one agent convinces the other, as
in the classic voter model.  The three-state model is the simplest discrete
system that embodies the constraint of the compromise model.

The constrained voter model is also equivalent to a constrained spin-1 Ising
system with $T=0$ Glauber kinetics \cite{glauber}.  Leftist, centrist, and
rightist opinions are equivalent to the respective spin states $-$, 0, and
$+$.  By the incompatibility of leftists and rightists, neighboring $+$ and
$-$ spins do not interact.  Thus an arbitrary initial state could evolve to a
static final state that contains only $+$ and $-$ spins (Fig.~\ref{map}).

If we temporarily disregard the difference between leftists and rightists,
the resulting binary system of centrists and extremists reduces to the voter
model, for which one of two absorbing states --- either all centrists or all
extremists --- is eventually reached.  In the context of the three-opinion
system, the latter is either consensus of extremists or a frozen state of
leftists and rightists.

\begin{figure}[ht]
\begin{center}
\begin{minipage}[b]{0.44\textwidth}
\includegraphics*[width=1.0\textwidth]{fig3a.eps}
\end{minipage}
\hspace{2em}
\begin{minipage}[b]{0.41\textwidth}
\includegraphics*[width=1.0\textwidth]{fig3b.eps}
\end{minipage}
\caption{(Left) Typical frozen final state of $+$ and $-$ on a
  $100\times 100$ square for $\rho_0=0.1$.  Notice the nested enclaves
  of opposite opinions.  (Right) Probability for the occurrence of a
  given final state as a function of $\rho_0$ for $\rho_+=\rho_-$.  }
\label{map}
\end{center}
\end{figure}

% \begin{figure}[ht] 
% %\vspace*{-0.7cm}
% \hspace*{0.3cm} \includegraphics*[width=0.4\textwidth]{map.eps}
% \hspace*{0.3cm}\includegraphics*[width=0.4\textwidth]{final-state-mf.eps}
% \caption{(Left) Typical frozen final state on a $100\times 100$ 
%   square for $\rho_0=0.1$.  Black and white squares represent $+$ and $-$
%   states.  Notice the cluster and nested enclaves of opposite
%   opinions.(Right) Probability for the occurrence of a given final state as a
%   function of $\rho_0$ for $\rho_+=\rho_-$.  Here $P_+$ is the probability
%   that $+$ consensus is reached and $P_{+-}$ is the probability that the
%   final state is a frozen mixture of $+$ and $-$. }
% \label{map}
% \end{figure}

Because of the underlying voter dynamics, the average density of each species
is globally conserved in any spatial dimension \cite{voter}.  Thus $\langle
\rho_i(t)\rangle =\rho_i(t=0)$, where $i$ refers to one of the states
$(+,0,-)$ and the angle brackets denote an average over all dynamical
trajectories and all initial states with the specified densities.  By the
conservation of the magnetization, the final state consists of all centrists
with probability $P_0=\rho_0$, where $\rho_0$ is the initial density of
0-spins, and with probability $1-\rho_0$ there are no centrists in the final
state.  In the latter case, there can be either a consensus of $+$ (with
probability $P_+(\rho_0)$), consensus of $-$ (probability $P_-(\rho_0)$), or
a frozen mixed state (probability $P_{+-}(\rho_0)$).  Figure \ref{map} shows
the dependence of these final state probabilities on $\rho_0$ in the
mean-field limit in the symmetric case $\rho_+=\rho_-=(1-\rho_0)/2$; nearly
identical results occur in one and two dimensions.

A good way to visualize the dynamics in one dimension is in terms of domain
walls (Fig.~\ref{dw}).  There are three types of walls: diffusing walls
between $+0$ and between $-0$, respectively denoted by $M_+$ and $M_-$, and
stationary domain walls $S$ between $+-$.  The mobile walls evolve by
\begin{eqnarray}
\label{MM}
M_\pm+M_\pm \to \emptyset, \qquad
M_\pm+M_\mp\to S.
\end{eqnarray}  
When a mobile wall hits a stationary wall, the former changes its sign while
the latter is eliminated via the reaction
\begin{eqnarray}
\label{MSM}
&&M_\pm+S\to M_\mp.
\end{eqnarray}  


Any initial opinion state forces two important topological constraints in the
domain wall arrangement: (i) an {\em even} number of mobile walls between
each pair of stationary wall, and (ii) prohibition of domain wall sequences
of the form $\ldots M_+M_-M_+\ldots$.  These constraints play a crucial role
in the kinetics; related kinetic constraints arise in models of glassy
dynamics \cite{glassy}.

\begin{figure}[ht] 
\begin{center}
 \vspace*{0.cm}\hspace*{0.1in}
 \includegraphics*[width=0.6\textwidth]{fig4.eps}
\caption{Space-time representation of the domain wall dynamics.  Time
  runs vertically downward.  The spin state of the domains and the identity
  of each domain wall are indicated.}
\label{dw}
\end{center}
\end{figure}

Simulations show that the stationary domain wall density decays extremely
slowly: $S(t)\sim t^{-\psi}$ with $\psi(\rho_0)\to 0$ as $\rho_0\to 0$
\cite{VKR}.  To understand this slow decay, consider the rate equation for
the stationary domain wall density
\begin{equation}
\label{Idot}
\dot S = - k\, M\,S\,.
\end{equation}
While such a rate equation is generally inapplicable in low spatial
dimension, we can adapt it to one dimension by employing an effective
time-dependent reaction rate: $k\simeq \sqrt{2/\pi t}$ \cite{VKR,redner}.
This is the time-dependent flux to an absorbing point due to a uniform
initial density of diffusing particles; such a rate phenomenologically
accounts for spatial fluctuations in one dimension.

As $\rho_0\to 0$, the system initially consists of long strings of stationary
walls that are interspersed by pairs of more closely-spaced mobile walls.
Their survival probability is proportional to their initial separation, so
that the asymptotic density of mobile walls is $M\simeq 2\rho_0/\sqrt{\pi t}$
\cite{VKR}.  Substituting this expression for $M(t)$ and the above reaction
rate into this rate equation, the density of stationary walls decays as
$t^{-\psi}$ with $\psi(\rho_0)=\sqrt{8}\,\rho_0/\pi$ as $\rho_0\to 0$.  A
more compelling approach in terms of the persistence in the $q$-state Potts
model \cite{sire,der} gives $\psi(\rho_0)\to 2\rho_0/\pi$ as $\rho_0\to 0$,
in excellent agreement with our numerics \cite{opinion-bkr}.

\section{Outlook}

Minimalist opinion dynamics models exhibit a variety of intriguing
properties.  The competition between interaction among compatible individuals
and rigidity among incompatible individuals leads to rich dynamics and to
complex final states.  The preliminary results reported here suggest many
avenues for future research.  For example, what types of bifurcation patterns
emerge with different initial conditions in the compromise model?  What
happens when the opinion space is multidimensional?  What is the overall
approach rate to the final state?  In the constrained voter model, even simpler
questions are still not well understood.  Most notably, what is the
probability of reaching a given final state as a function of the initial
condition?  More quantitatively, what are the dependences of $P_+(\rho_0)$
and $P_{+-}(\rho_0)$ on the initial density of 0-spins $\rho_0$?

\section{Acknowledgements} 

We are grateful to grants from the DOE (W-7405-ENG-36) and the NSF
(DMR9978902) for financial support of this research.


\begin{thebibliography}{99}
  
\bibitem{F74} H. F\"ollmer, J. Math.\ Econ.\ {\bf 1}, 51 (1974); J. Kobayashi,
  J. Math.\ Sociology {\bf 24}, 285 (2001); R.~Hegselmann and U.~Krause, J.
  Artif.\ Soc.\ Soc.\ Simul.\ {\bf 5}, no.\,3 (2002) and references therein.

\bibitem{axelrod} 
  R.~Axelrod, J. Conflict Resolution {\bf 41}, 203 (1997);
  R.~Axelrod, {\it The Complexity of Cooperation}, (Princeton University
  Press, 1997).
 
\bibitem{weid} 
   W.~Weidlich, {\it Sociodynamics: A Systematic Approach to Mathematical
   Modelling in the Social Sciences}
   (Harwood Academic Publishers, 2000).
   
\bibitem{galam} S. Galam, Y. Gefen, and Y. Shapir, Math.\ J. of Sociology
 {\bf 9}, 1 (1982); S. Galam, Physica A {\bf 274}, 132 (1999); {\it
   cond-mat}/0211571.

\bibitem{CMV} C. Castellano, M. Marsili, and A. Vespignani, Phys.\ Rev.\ 
  Lett.\ {\bf 85}, 3536 (2000); D. Vilone, A. Vespignani, and C. Castellano,
  {\it cond-mat}/0210413.
  
\bibitem{szn}
   K.~Sznajd-Weron and J.~Sznajd, Int.\ J. Mod.\ Phys.\ C {\bf 11}, 
   1157 (2000). 

\bibitem{holyst}
   J.~Holyst, K.~Kacperski, and F.~Schweitzer, in: 
    {\it Annual Reviews of Computational
    Physics IX}, ed. D. Stauffer (World Scientific, Singapore 2001), 
    pp.~253-273. 

\bibitem{stauffer} 
    D.~Stauffer, J. Artif.\ Soc.\ Soc.\ Simul.\ {\bf 5},
    no.\,1 (2002). 
  
\bibitem{opinion} 
   G.~Weisbuch, G.~Deffuant, F.~Amblard, and J.~P.~Nadal, 
   {\it cond-mat}/0111494; D.~Neau, Ph.D. thesis, unpublished. 
   
\bibitem{opinion-bkr} E. Ben-Naim, P. L. Krapivsky, and S. Redner,
   cond-mat/0212313 (submitted to Physica D).
   
\bibitem{VKR} F.~Vazquez, P.~L.~Krapivsky, and S.~Redner, J. Phys.\ A {\bf
     36}, L61 (2003).
   
\bibitem{voter} T.~M.~Liggett, {\it Interacting Particle Systems}
   (Springer-Verlag, New York, 1985).

\bibitem{bk}
   E.~Ben-Naim and P.~L.~Krapivsky, 
   Phys. Rev. E {\bf 61}, R5 (1999). 

\bibitem{bal}
   A.~Baldassarri, U.~M.~B.~Marconi, and A.~Puglisi, 
   Europhys.\ Lett. {\bf 58}, 14 (2001). 

\bibitem{glauber} 
   R.~J.~Glauber, J.\ Math.\ Phys. {\bf 4}, 294 (1963).
   
 \bibitem{glassy} For a recent review, see F. Ritort and P. Sollich,
   cond-mat/0210382 (to appear in Advances in Physics).
   
\bibitem{redner} 
   S.~Redner, {\it A Guide to First-Passage Processes},
   (Cambridge University Press, New York, 2001).
   
\bibitem{sire} 
   C.~Sire and S.~N.~Majumdar, Phys.\ Rev.\ E {\bf 52}, 244 (1995).  
   
\bibitem{der} 
   B.~Derrida, V.~Hakim, and V.~Pasquier, Phys.\ Rev.\ Lett. 
   {\bf 75}, 751 (1995).  


\end{thebibliography}
\end{document}

\bibitem{per} B.~Derrida, A.~J.~Bray, and C.~Godr\`eche, J. Phys.\ A {\bf
     27}, L357 (1994); D. Stauffer, J. Phys.\ A {\bf 27}, 5029 (1994).


% J.~J\"ackle and S.~Eisinger, Z. Phys.\ B {\bf 84}, 115
%    (1991); J.~Reiter and J.~J\"ackle, Physica A {\bf 215}, 311 (1995);
%    P.~Sollich and M.~R.~Evans, Phys.\ Rev.\ Lett.\ {\bf 83}, 3238 (1999);
%    D.~Aldous and P.~Diaconis, J.\ Stat.\ Phys. {\bf 107}, 945 (2002);
%    S.~N.~Majumdar, D.~S.~Dean, and P.~Grassberger, Phys.\ Rev.\ Lett.\ {\bf
%      86}, 2301 (2001); A.~Crisanti, F.~Ritort, A.~Rocco, and M.~Sellitto, J.\ 
%    Chem.\ Phys. {\bf 113}, 10615 (2000); J. Phys.\ Cond.\ Matter {\bf 14},
%    1523 (2002).

% \bibitem{melzak} 
%     Z.~A.~Melzak, {\it Mathematical Ideas, Modeling and Applications,
%     Volume II of Companion to Concrete Mathematics} (Wiley, New York,
%     1976), p.\ 279.  

% \bibitem{Hammersley}
%     J.~M.~Hammersley, in: {\it Proc. Sixth Berkley
%     Symp. Math. Statist. Probab., Vol.~1} (University of California Press,
%     1972), pp.~345--394.

% \bibitem{aldous}
%     D.~Aldous and P.~Diaconis,
%     Probab.\ Theor.\ Rel.\ Fields {\bf 103}, 199 (1995).

% \begin{figure}[ht] 
%  \vspace*{0.cm}\hspace*{-0.1in}
%  \includegraphics*[width=0.5\textwidth]{S-density.eps} \includegraphics*[width=0.48\textwidth]{exponent.eps}
% \caption{(Left) Stationary wall density versus time on a double logarithmic 
%   scale for the initial conditions $\rho_0= 0.02$, 0.04, 0.10, 0.20, and 0.40
%   (top to bottom).  The respective exponent estimates are 0.013, 0.026,
%   0.065, 0.13, and 0.29.  Data are based on 100 realizations on a $5\times
%   10^5$-site chain.  Inset: Density for initially uncorrelated walls for
%   $\rho_0= 0.02$, 0.10, and 0.40 (top to bottom).  The solid line has slope
%   $-3/8$, as expected from classical persistence \cite{per}.  (Right)
%   Comparison of the exponent $\psi$ from Eq.~(\ref{theta}) and from the
%   simulation data.  This suggests that topological constraints in the domain
%   wall arrangement controls the dynamics.  }
% \label{S-density}
% \end{figure}




