%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                %%%
%%%         .         .           ..           .         .         %%%
%%%                    The complexity of voting                    %%%
%%%                                                                %%%
%%%                         David A. Meyer                         %%%
%%%                                                                %%%
%%%                                                                %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                %%%
%%%                                                                %%%
%%%                       Typesetting notes                        %%%
%%%                                                                %%%
%%%                                                                %%%
%%% Plain TeX with a few simple macros at the beginning.           %%%
%%%                                                                %%%
%%% If AMS fonts are not loaded, comment the next line and         %%%
%%%  uncomment the following one.                                  %%%
\font\bbb=msbm10 \font\bbs=msbm7                                   %%%
%\def\bbb{\bf} \def\bbs{\bf}                                       %%%
%%%                                                                %%%
%%%                                                                %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\overfullrule=0pt

\magnification=1200


\def\C{\hbox{\bbb C}} \def\sC{\hbox{\bbs C}} 
\def\N{\hbox{\bbb N}} \def\sN{\hbox{\bbs N}} 
\def\R{\hbox{\bbb R}} \def\sR{\hbox{\bbs R}} 
\def\Z{\hbox{\bbb Z}} \def\sZ{\hbox{\bbs Z}} 


\def\AI{{\sl Artificial Intelligence}}
\def\AM{{\sl Advances in Math.}}
\def\AMM{{\sl Amer.\ Math.\ Monthly}}
\def\AnM{{\sl Ann.\ Math.}}
\def\AN{{\sl Amer.\ Nat.}}
\def\ANYAS{{\sl Ann.\ NY Acad.\ Sci.}}
\def\AP{{\sl Ann.\ Phys.}}
\def\APL{{\sl Appl.\ Phys.\ Lett.}}
\def\APS{{\sl Acta Physica Slovaca\/}}
\def\BAMS{{\sl Bull.\ Amer.\ Math.\ Soc.}}
\def\BLMS{{\sl Bull.\ Lond.\ Math.\ Soc.}}
\def\BSTJ{{\sl Bell System Tech.\ J.}}
\def\CACM{{\sl Commun.\ ACM\/}}
\def\CMP{{\sl Commun.\ Math.\ Phys.}}
\def\CPAM{{\sl Commun.\ Pure Appl.\ Math.}}
\def\CQG{{\sl Class.\ Quantum Grav.}}
\def\CS{{\sl Complex Systems\/}}
\def\CSL{{\sl Computer, Speech and Language}}
\def\Di{{\sl Dialectica\/}}
\def\DM{{\sl Discrete Math.}}
\def\DMJDMV{{\sl Doc.\ Math.\ J. DMV}}
\def\EJ{{\sl Econom.\ J.}}
\def\EJC{{\sl European J. Combin.}}
\def\EL{{\sl Europhys.\ Lett.}}
\def\FP{{\sl Found.\ Phys.}}
\def\Gp{{\sl Geophysics\/}}
\def\GRG{{\sl Gen.\ Relativ.\ Grav.}}
\def\HN{{\sl Hum.\ Nature\/}}
\def\IEEEJSAC{{\sl IEEE J. Selected Areas Commun.}}
\def\IEEETAC{{\sl IEEE Trans.\ Automatic Control}}
\def\IEEETAES{{\sl IEEE Trans.\ Aerospace and Electronic Systems}}
\def\IEEETIT{{\sl IEEE Trans.\ Inform.\ Theory}}
\def\IJCS{{\sl InterJournal Complex Systems}}
\def\IJMPB{{\sl Int.\ J. Mod.\ Phys.\ B}}
\def\IJMPC{{\sl Int.\ J. Mod.\ Phys.\ C}}
\def\IJTP{{\sl Int.\ J. Theor.\ Phys.}}
\def\IPL{{\sl Info.\ Processing Lett.}}
\def\IM{{\sl Invent.\ math.}}
\def\JACM{{\sl J. ACM\/}}
\def\JAP{{\sl J. Appl.\ Phys.}}
\def\JASA{{\sl J. Acoustical Soc.\ Amer.}}
\def\JCP{{\sl J. Comput.\ Phys.}}
\def\JCSS{{\sl J. Comp.\ Syst.\ Sci.}}
\def\JEL{{\sl J. Econom.\ Lit.}}
\def\JET{{\sl J. Econom.\ Theory}}
\def\JFI{{\sl J. Franklin Inst.}}
\def\JFM{{\sl J. Fluid Mech.}}
\def\JLMS{{\sl Proc.\ Lond.\ Math.\ Soc.}}
\def\JMM{{\sl J. Math.\ Mech.}}
\def\JMO{{\sl J. Mod.\ Optics\/}}
\def\JMP{{\sl J. Math.\ Phys.}}
\def\JPA{{\sl J. Phys.\ A:  Math.\ Gen.}}
\def\JPC{{\sl J. Phys.\ C:  Solid State Phys.}}
\def\JPCh{{\sl J. Phys.\ Chem.}}
\def\JPSJ{{\sl J. Phys.\ Soc.\ Jpn.}}
\def\JSP{{\sl J. Statist.\ Phys.}}
\def\JTB{{\sl J. Theor.\ Biol.}}
\def\LAS{{\sl Los Alamos Science\/}}
\def\MA{{\sl Math.\ Ann.}}
\def\MST{{\sl Math.\ Systems Theory\/}}
\def\Na{{\sl Nature\/}}
\def\Naw{{\sl Naturwissenschaften}}
\def\NPB{{\sl Nucl.\ Phys.\ B}}
\def\Or{{\sl Order\/}}
\def\Ph{{\sl Physics\/}}
\def\PAMS{{\sl Proc.\ Amer.\ Math.\ Soc.}}
\def\PCPS{{\sl Proc.\ Camb.\ Phil.\ Soc.}}
\def\PA{{\sl Physica A\/}}
\def\PD{{\sl Physica D\/}}
\def\PJM{{\sl Pacific J. Math.}}
\def\PLA{{\sl Phys.\ Lett.\ A\/}}
\def\PLB{{\sl Phys.\ Lett.\ B\/}}
\def\PNAS{{\sl Proc.\ Nat.\ Acad.\ Sci.\ U.S.A.}}
\def\PNAW{{\sl Proc.\ Nederl.\ Akad.\ Wetensch.}}
\def\PNAWA{{\sl Proc.\ Nederl.\ Akad.\ Wetensch., Ser.\ A}}
\def\PRp{{\sl Phys.\ Rep.}}
\def\PR{{\sl Phys.\ Rev.}}
\def\PRA{{\sl Phys.\ Rev.\ A\/}}
\def\PRB{{\sl Phys.\ Rev.\ B\/}}
\def\PRD{{\sl Phys.\ Rev.\ D\/}}
\def\PRE{{\sl Phys.\ Rev.\ E\/}}
\def\PRL{{\sl Phys.\ Rev.\ Lett.}}
\def\PRSLA{{\sl Proc.\ Roy.\ Soc.\ Lond.\ A\/}}
\def\PRSLB{{\sl Proc.\ Roy.\ Soc.\ Lond.\ B\/}}
\def\PS{{\sl Philos.\ Sci.}}
\def\PSAM{{\sl Proc.\ Symp.\ Appl.\ Math.}}
\def\PT{{\sl Parasitol.\ Today\/}}
\def\PhT{{\sl Phys.\ Today\/}}
\def\PTP{{\sl Prog.\ Theor.\ Phys.}}
\def\PTRSLA{{\sl Phil.\ Trans.\ Roy.\ Soc.\ Lond.\ A\/}}
\def\RMP{{\sl Rev.\ Mod.\ Phys.}}
\def\Sc{{\sl Science\/}}
\def\SIAMJC{{\sl SIAM J. Comput.}}
\def\SIAMJNA{{\sl SIAM J. Numer.\ Anal.}}
\def\SIAMR{{\sl SIAM Rev.}}
\def\SIGACTN{{\sl SIGACT News\/}}
\def\SPAWPM{{\sl Sitzungsber.\ Preuss.\ Akad.\ Wiss., Phys.-Math.}}
\def\SPJETP{{\sl Sov.\ Phys.\ JETP\/}}
\def\SRO{{\sl Sociological Research Online}}
\def\SSc{{\sl Surface Science\/}}
\def\TAMS{{\sl Trans.\ Amer.\ Math.\ Soc.}}
\def\TIEICEJE{{\sl Trans.\ IEICE Japan E\/}}
\def\TMP{{\sl Theor.\ and Math.\ Phys.}}
\def\UMN{{\sl Uspekhi Mat.\ Nauk}}
\def\YMJ{{\sl Yokohama Math.\ J.}}
\def\ZP{{\sl Z. Physik\/}}
\def\ZPC{{\sl Z. Phys.\ C---Particles and Fields\/}}


\def\dajm{\hbox{D. A. Meyer}}
\def\luca{\hbox{L. Bombelli}}
\def\rds{\hbox{R. D. Sorkin}}
\def\ljdr{\hbox{\luca, J. Lee, \dajm\ and \rds}}
\def\brosl{\hbox{B. Hasslacher}}
\def\bd{\hbox{\brosl\ and \dajm}}

\def\baxter{\hbox{R. J. Baxter}}
\def\boghosian{\hbox{B. M. Boghosian}}
\def\deutsch{\hbox{D. Deutsch}}
\def\feynman{\hbox{R. P. Feynman}}
\def\frisch{\hbox{U. Frisch}}
\def\gz{\hbox{G. Gr\"ossing and A. Zeilinger}}
\def\hpdp{\hbox{J. Hardy, Y. Pomeau and O. de Pazzis}}
\def\hdpp{\hbox{J. Hardy, O. de Pazzis and Y. Pomeau}}
\def\pitowsky{\hbox{I. Pitowsky}}
\def\rothman{\hbox{D. H. Rothman}}
\def\shiyi{\hbox{S. Chen}}
\def\teich{\hbox{W. G. Teich}}
\def\vonneumann{\hbox{J. von Neumann}}
\def\schrodinger{\hbox{E. Schr\"odinger}}
\def\kitaev{\hbox{A. Yu.\ Kitaev}}
\def\gottesman{\hbox{D. Gottesman}}
\def\grover{\hbox{L. K. Grover}}
\def\rains{\hbox{E. M. Rains}}
\def\steane{\hbox{A. M. Steane}}

\def\hfb{\hfil\break}

\catcode`@=11
\newskip\ttglue

\font\tenrm=cmr10   \font\ninerm=cmr9    \font\eightrm=cmr8   \font\sixrm=cmr6
\font\tenbf=cmbx10  \font\ninebf=cmbx9   \font\eightbf=cmbx8  \font\sixbf=cmbx6
\font\tenit=cmti10  \font\nineit=cmti9   \font\eightit=cmti8  
\font\tensl=cmsl10  \font\ninesl=cmsl9   \font\eightsl=cmsl8  
\font\tenmi=cmmi10  \font\ninemi=cmmi9   \font\eightmi=cmmi8  \font\sixmi=cmmi6
\font\tentt=cmtt10  \font\ninett=cmtt9   \font\eighttt=cmtt8

\font\bigten=cmr10 scaled\magstep2 

\def\ninepoint{\def\rm{\fam0\ninerm}%
  \textfont0=\ninerm \scriptfont0=\sixrm
  \textfont1=\ninemi \scriptfont1=\sixmi
  \textfont\itfam=\nineit  \def\it{\fam\itfam\nineit}%
  \textfont\slfam=\ninesl  \def\sl{\fam\slfam\ninesl}%
  \textfont\bffam=\ninebf  \scriptfont\bffam=\sixbf
    \def\bf{\fam\bffam\ninebf}%
  \tt \ttglue=.5em plus.25em minus.15em
  \normalbaselineskip=11pt
  \setbox\strutbox=\hbox{\vrule height8pt depth3pt width0pt}%
  \normalbaselines\rm}

\def\eightpoint{\def\rm{\fam0\eightrm}%
  \textfont0=\eightrm \scriptfont0=\sixrm
  \textfont1=\eightmi \scriptfont1=\sixmi
  \textfont\itfam=\eightit  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf  \scriptfont\bffam=\sixbf
    \def\bf{\fam\bffam\eightbf}%
  \tt \ttglue=.5em plus.25em minus.15em
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \normalbaselines\rm}

\def\sfootnote#1{\edef\@sf{\spacefactor\the\spacefactor}#1\@sf
      \insert\footins\bgroup\eightpoint
      \interlinepenalty100 \let\par=\endgraf
        \leftskip=0pt \rightskip=0pt
        \splittopskip=10pt plus 1pt minus 1pt \floatingpenalty=20000
        \parskip=0pt\smallskip\item{#1}\bgroup\strut\aftergroup\@foot\let\next}
\skip\footins=12pt plus 2pt minus 2pt
\dimen\footins=30pc

\def\ie{{\it i.e.}}
\def\eg{{\it e.g.}}
\def\etc{{\it etc.}}
\def\etal{{\it et al.}}

\def\groebner{G{\eightpoint ROEBNER}}
\def\xor{{\eightpoint XOR}}
\def\or{{\eightpoint OR}}
\def\and{{\eightpoint AND}}

\def\complex{1}
\def\BarYam{2}
\def\Condorcet{3}
\def\smv{4}
\def\chaos{5}
\def\Italy{6}
\def\Arrow{7}
\def\BarYampaper{8}
\def\Swarm{9}
\def\ANT{10}
\def\genetic{11}
\def\robots{12}
\def\alloc{13}
\def\spatial{14}


\input epsf.tex

\dimen0=\hsize \divide\dimen0 by 13 \dimendef\chasm=0
\dimen1=\hsize \advance\dimen1 by -\chasm \dimendef\usewidth=1
\dimen2=\usewidth \divide\dimen2 by 2 \dimendef\halfwidth=2
\dimen3=\usewidth \divide\dimen3 by 3 \dimendef\thirdwidth=3
\dimen4=\hsize \advance\dimen4 by -\halfwidth \dimendef\secondstart=4
\dimen5=\halfwidth \advance\dimen5 by -10pt \dimendef\indenthalfwidth=5
\dimen6=\thirdwidth \multiply\dimen6 by 2 \dimendef\twothirdswidth=6
\dimen7=\twothirdswidth \divide\dimen7 by 4 \dimendef\qttw=7
\dimen8=\qttw \divide\dimen8 by 4 \dimendef\qqttw=8
\dimen9=\qqttw \divide\dimen9 by 4 \dimendef\qqqttw=9
%\dimen10=\chasm \multiply\dimen10 by 10 \dimendef\fivein=10
\dimen10=2.25truein \dimendef\sciencecol=10

\parskip=0pt\parindent=0pt

\line{\hfil 2 December 2000}
%\line{\hfill quant-ph/yymmnnn}
\vfill
\centerline{\bf\bigten THE COMPLEXITY OF VOTING}
\bigskip\bigskip
\centerline{\bf David A. Meyer}
\bigskip 
\centerline{\sl Project in Geometry and Physics,
                Department of Mathematics}
\centerline{{\sl University of California/San Diego,
                 La Jolla, CA 92093-0112\/};}
\smallskip
\centerline{{\sl Institute for Physical Sciences,
                 Los Alamos, NM 87544\/};}
\smallskip
\centerline{and {\sl New England Complex Systems Institute,
                     Cambridge, MA 02138}}
\smallskip
\centerline{\tt dmeyer@chonji.ucsd.edu}
\vfill
\centerline{ABSTRACT}
\bigskip
%--------|---------|---------|---------|---------|---------|---------|
\noindent Voting, or more generally, aggregating preferences, makes 
systems complex.  Consequently, their dynamics can be chaotic and 
hence difficult to predict or control.  These statements are equally 
true for artificial multi-agent systems as for real political systems, 
counterindicating unreflexive use of such tools by policy makers.  
Similar analysis applies to systems with a continuum of alternatives, 
like election campaigns, and explains the ambiguity of candidates'
platforms.

\bigskip\bigskip
%--------|---------|---------|---------|---------|---------|---------|
\global\setbox1=\hbox{Key Words:\enspace}
\parindent=\wd1
\item{Key Words:}  decision theory, chaos, Arrow's theorem, 
                   multi-agent simulations, agent-based modelling, 
                   political campaigns, platform ambiguity.

\vfill
\hrule width2.0truein
\medskip
\noindent Based on a talk presented at the RAND Workshop on 
Complexity and Public Policy, {\sl Complex Systems and Policy 
Analysis:  New Tools for a New Millennium}, held in Arlington, VA, 
27--28 September 2000.
\eject

\headline{\ninepoint\it Complexity of voting    \hfill David A. Meyer}

\parskip=10pt
\parindent=20pt

\noindent{\bf 1. Overview}

%--------|---------|---------|---------|---------|---------|---------|
This talk is not about the difficulty of deciding how to 
vote---although I will have something to say about that at the 
end---but rather about the sense in which voting, or more generally, 
aggregating preferences, creates complex systems $\ldots$ and some
consequences of this fact.  Furthermore, I want to explain several 
reasons policy makers should care:  Underlying their tasks is the 
basic problem of understanding (and influencing) group decision 
making.  Advances in such understanding have implications for real 
social systems and for multi-agent tools, as well as for interpreting
simulations of either.  The approach I take is motivated by a lesson 
from physics:  for many situations minimal models abstracting only
crucial features provide useful insights into the behavior of real
systems.

\medskip
\noindent{\bf 2. Complex systems}

%--------|---------|---------|---------|---------|---------|---------|
For our purposes a complex system is one composed of multiple 
subsystems interacting in such a way that efficient descriptions 
differ at different scales [\complex].  Larger scale properties which 
differ from smaller scale ones are often described as `emergent' 
[\BarYam].  Let's consider two examples:

\itemitem{(1)}
%--------|---------|---------|---------|---------|---------|---------|
A barbell with 90{\it lbs\/} of weight added:  Suppose the 
45{\it lbs\/} on each side consist of nine 5{\it lb\/} weights.  
Efficient description of a subsystem---5{\it lbs\/} of weight---is of
the same kind as of the whole---45{\it lbs\/} of weight; only the 
number changes.  This is a {\sl simple\/} system.

\itemitem{(2)}
%--------|---------|---------|---------|---------|---------|---------|
A hurricane:  At a small scale it is composed of the molecules of the
air, which are efficiently described by their positions and momenta.
But at a (much) larger scale the hurricane is a vortex, which is 
efficiently described by the latitude and longitude of its center, and
by its angular momentum.  These descriptions are of different kinds,
so this is a {\sl complex\/} system.

%--------|---------|---------|---------|---------|---------|---------|
Of course, sometimes winds blow in a single direction even at very 
large scales so that larger and larger volumes of air are efficiently 
described by position and momentum.  Conversely, there are actually 
differences between loading a barbell with different sets of weights 
totalling the same amount---the bar vibrates differently and this 
matters when a lifter is at the limit of his/her strength.  In fact, 
all real (classical) systems are complex, although they may be simple 
in special circumstances.

\medskip
\noindent{\bf 3.  Social systems}

%--------|---------|---------|---------|---------|---------|---------|
Policy makers are concerned with social systems---political, economic,
military, \etc\ \ These consist of multiple people with individual
preferences which are aggregated by institutional mechanisms---voting,
markets, and command, respectively.  Efficient description changes at 
the scales of aggregation/decision making; thus these are complex 
systems.  Voting exemplifies this phenomenon, which was noticed over 
200 years ago by Condorcet [\Condorcet].  

%--------|---------|---------|---------|---------|---------|---------|
He considered a situation with 60 voters, each having consistent 
preferences among three alternatives, $a$, $b$ and $c$, as listed in 
Table~1:

\medskip
\midinsert
$$
\vbox{\offinterlineskip
\hrule height 0.8pt
\halign{%
\vrule#width 0.8pt&\strut\quad\hfil#&%
\vrule#width 0.8pt&\strut\quad\hfil#\hfil\quad&%
\vrule#width 0.4pt&\strut\quad\hfil#\hfil\quad&%
\vrule#width 0.4pt&\strut\quad\hfil#\hfil\quad&%
\vrule#width 0.8pt\cr
height2pt&\omit&&\omit&&\omit&&\omit&\cr
& &&$a > b$&&$b > c$&&$c > a$&\cr
height0pt&\omit&&\omit&&\omit&&\omit&\cr     % was height2pt
\noalign{\hrule height 0.8pt}
height2pt&\omit&&\omit&&\omit&&\omit&\cr
&23 prefer $a>b>c$\quad&&23&&23&& &\cr
height2pt&\omit&&\omit&&\omit&&\omit&\cr
\noalign{\hrule}
height2pt&\omit&&\omit&&\omit&&\omit&\cr
&17 prefer $b>c>a$\quad&& &&17&&17&\cr
height2pt&\omit&&\omit&&\omit&&\omit&\cr
\noalign{\hrule}
height2pt&\omit&&\omit&&\omit&&\omit&\cr
& 2 prefer $b>a>c$\quad&&  &&$\phantom{0}2$&&  &\cr
height2pt&\omit&&\omit&&\omit&&\omit&\cr
\noalign{\hrule}
height2pt&\omit&&\omit&&\omit&&\omit&\cr
&10 prefer $c>a>b$\quad&&10&& &&10&\cr
height2pt&\omit&&\omit&&\omit&&\omit&\cr
\noalign{\hrule}
height2pt&\omit&&\omit&&\omit&&\omit&\cr
& 8 prefer $c>b>a$\quad&&  &&  &&$\phantom{0}8$&\cr
height2pt&\omit&&\omit&&\omit&&\omit&\cr
\noalign{\hrule height 0.8pt}
height2pt&\omit&&\omit&&\omit&&\omit&\cr
&majorities:\quad&&33&&42&&35&\cr
height2pt&\omit&&\omit&&\omit&&\omit&\cr
}
\hrule height 0.8pt}
$$
\vbox{\eightpoint{%
\centerline{{\bf Table 1}.  Condorcet's example of a preference 
                            cycle.}}}
\endinsert

%--------|---------|---------|---------|---------|---------|---------|
\noindent Note that if the voters are asked to choose between $a$ and
$b$ a majority prefer $a$, between $b$ and $c$ a majority prefer $b$,
but between $a$ and $c$ the majority does not prefer $a$, but rather 
$c$.  We can summarize the situation by the directed graph on the left
in Figure~1, where the vertices represent alternatives and the 
direction of edges indicates majority preference.  Compare this with 
the directed graph on the right in Figure~1 which describes the 
consistent preferences $c > a > b$.  These graphs differ 
{\sl topologically\/}:  the former contains a {\sl cycle\/} (like a 
hurricane) while the latter does not.  Thus efficient description at 
the group level differs from the individual level and the system is 
complex.

\midinsert
%\null\vskip-4\baselineskip
$$
\epsfxsize=\twothirdswidth\epsfbox{f1.3alt.eps}%
$$
%\vskip-1.5\baselineskip
\eightpoint{%
{\narrower\noindent{\bf Figure 1}.  Directed graphs representing the
aggregated choices of two different groups.  On the left, the group
preferences contain a cycle; on the right they do not.\par}
}
\endinsert

\medskip
\noindent{\bf 4.  Dynamics}

%--------|---------|---------|---------|---------|---------|---------|
To understand the consequences of this complexity, consider the 
following dynamics:  Suppose the voters are successively presented 
with a choice between the {\it status quo\/} and a new alternative.
If the group preferences contain the cycle shown on the left in 
Figure~1, a typical sequence of choices is $bbaccbaa\ldots$.  In 
contrast, the acyclic preferences on the right lead to sequences of 
the form $bbaccccc\ldots$.  In the latter case, once alternative $c$ 
is chosen, the sequence becomes constant, but in the former case, the 
group never settles on a single alternative.

%--------|---------|---------|---------|---------|---------|---------|
The difference between these two situations can be quantified [\smv]:
To a directed graph associate a transition matrix $T$ with entries
defined by
$$
T_{ab} = \cases{1 & if $a \leftarrow b$; \cr
                0 & otherwise.           \cr
               }
$$
Labelling the rows and columns $a$, $b$, $c$, in that order, the
transition matrices for the directed graphs shown in Figure~1 are:
$$
T_1 = \pmatrix{ 1 & 1 & 0 \cr
                0 & 1 & 1 \cr
                1 & 0 & 1 \cr
              }
\qquad{\rm and}\qquad
T_2 = \pmatrix{ 1 & 1 & 0 \cr
                0 & 1 & 0 \cr
                1 & 1 & 1 \cr
              },
$$
respectively.  The number of admissible sequences of $N$ choices is 
${\rm Tr}\,T^N$, where Tr denotes the sum of the diagonal entries.  
The {\sl topological entropy\/} normalizes this quantity:
$$
S[T] := \lim_{N\to\infty}{1\over N}\log{\rm Tr}\,T^N
      = \log(\hbox{largest eigenvalue of $T$}).
$$
Thad Brown and I have show that this entropy is positive exactly when
there are preference cycles and that in this case the dynamics of the
system is chaotic [\smv].  Recall that the technical meaning of 
{\sl chaotic\/} is that the system displays [\chaos]:
\vskip6pt

\parskip=0pt
\itemitem{(1)}
topological transitivity;

\itemitem{(2)}
a dense set of periodic orbits;

\itemitem{(3)}
sensitive dependence on initial conditions.

\vskip6pt
%--------|---------|---------|---------|---------|---------|---------|
\noindent Concentrating on the last of these properties, notice that
$S[T_1] = 1 > 0$.  Even when sequences of choices admissible with the
cyclic preferences in Figure~1 start out the same, once a difference 
occurs the sequences diverge:  \eg, $bbaccbaa\ldots$, 
$bbaccbbb\ldots$, $bbacbaac\ldots$.  Contrast this with the acyclic 
situation in Figure~1 for which $S[T_2] = 0$ and initial differences 
are erased once the sequence settles down to alternative $c$:  \eg, 
$bbaccccc\ldots$, $bbaaaacc\ldots$, $bacccccc\ldots$.

\parskip=10pt
\medskip
\noindent{\bf 5. Real systems}

%--------|---------|---------|---------|---------|---------|---------|
To see how this plays out in real systems, let's consider two 
examples:

\itemitem{(1)}
Postwar Italy.  Italy is notorious for the frequency with which it
changes govenments, having averaged more than one government per year
since the end of World War II.  Figure 2 crudely illustrates the
history [\Italy].  Since Italy is a parliamentary democracy, the 
ruling government is often a coalition of several parties.  The height 
of each rectangle in Figure~2 represents the number of participating 
parties; since the Christian Democrats are the dominant party, the 
color codes the secondary party in the ruling coalition.  The sequence 
of choices is consistent with cyclic rather than acyclic group 
preferences.

\midinsert
%\null\vskip-4\baselineskip
$$
\epsfxsize=\twothirdswidth\epsfbox{f2.italy.eps}%
$$
%\vskip-1.5\baselineskip
\eightpoint{%
{\narrower\noindent{\bf Figure 2}.  A crude representation of the
governments in post-war Italy:  {\it Democrazia Cristiana\/} (purple);
{\it Partito di Rifondazione Comunista\/} (red); {\it Partito 
Socialista Lavoratori Italiano}, {\it Partito Socialista Democratico
Italiano\/} (yellow); {\it Partito Republicana Italiano\/} (navy);
{\it Partito Socialista Italiano\/} (green); {\it Partito Socialista
Unificato} (light blue).\par}
}
\endinsert

\itemitem{(2)}
U. S. Presidents 1960--1980.  This provides a more familiar (to 
Americans) example which I've excerpted in Table~2.  Not only does 
this history display the same alternation between parties (in this
case, Democrat and Republican), but the details indicate that the
larger social dynamics in which the presidential elections are 
embedded must also be sensitive to small perturbations:  Had any of a 
number of things occurred differently, even the binary sequence of 
governing parties could easily have been different.

$$
\vbox{
\settabs\+1960&\quad&Nixon (R) beats Humphrey by 500,000 votes out of 
                     72,000,000&\cr
\+1960&&
 Kennedy (D) beats Nixon by 118,000 votes out of 78,000,000\hfill&\cr
\+&&
 \qquad Nixon loses campaign time to a car accident\hfill&\cr
\+&&
 \qquad Daly delivers crucial precints---hence IL---for Kennedy\hfill&\cr
\smallskip
\+1963&&
 \qquad Johnson becomes President after Kennedy assassination\hfill&\cr
\+1964&&
 Johnson (D) re-elected\hfill&\cr
\smallskip
\+1968&&
 Nixon (R) beats Humphrey by 500,000 votes out of 72,000,000\hfill&\cr
\+&&
 \qquad near election, polls shifting towards Humphrey\hfill&\cr
\+&&
 \qquad Wallace gets 9,900,000 votes in Democratic South\hfill&\cr
\smallskip
\+1972&&
 Nixon (R) re-elected over McGovern\hfill&\cr
\smallskip
\+1973&&
 \qquad Ford becomes VP after Agnew kickback conviction\hfill&\cr
\+1974&&
 Ford (R) becomes President after Nixon's resignation\hfill&\cr
\smallskip
\+1974&&
 \qquad Ford pardons Nixon\hfill&\cr
\+1976&&
 Carter (D) beats Ford by 57 electoral votes out of 538\hfill&\cr
}
$$
\noindent\centerline{\eightpoint{\bf Table 2.}  Two decades of U. S. 
                                                Presidents.}


\medskip
\noindent{\bf 6. Arrow's theorem}

%--------|---------|---------|---------|---------|---------|---------|
A reasonable question at this point is:  Could changing the decision
procedure eliminate chaos?  Each of voting rules I've discussed has 
been majority rule.  Perhaps requiring supermajorities, or some more
complicated rule, would eliminate the possibility of cyclic group
preferences.  That this is {\sl impossible\/} is the content of 
Arrow's theorem [\Arrow].  More precisely, he showed that any voting
rule which is
\vskip6pt

\parskip=0pt
\itemitem{(1)}
preference preserving ($a>b$ for all voters implies $a>b$ for the 
group), and

\itemitem{(2)}
independent of irrelevant alternatives (the ranking of $a$ and $b$ for
the group depends on the voters' rankings only of $a$ and $b$),

\vskip6pt
%--------|---------|---------|---------|---------|---------|---------|
\noindent is either dictatorial (\ie, there is a single voter whose
preferences dictate the group preferences) or there is a set of voter
preferences so that the group preferences are cyclic $\ldots$ and 
hence the dynamics is chaotic as described in \S4.

\parskip=10pt
%--------|---------|---------|---------|---------|---------|---------|
The topological entropy defined in \S4 can be used to quantify the
in/stability of a voting rule, or more generally, an institution, by
averaging over a set of possible preferences for the voting 
population.  Conversely, averaging the entropy over a class of voting
rules quantifies the in/stability of a specific voting population 
[\smv].

\medskip
\noindent{\bf 7.  Policy implications}

%--------|---------|---------|---------|---------|---------|---------|
There are several immediate implication for policy makers:

%--------|---------|---------|---------|---------|---------|---------|
{\sl Predicting\/} outcomes of decisions into the future is 
exponentially difficult.  For example, it's already hard to predict 
the winner of the next presidential election, and an answer to a 
question like, ``Will the winner of the 2020 presidential election be 
a Democrat or a Republican?'' can hardly be more than a guess.

%--------|---------|---------|---------|---------|---------|---------|
{\sl Controlling\/} outcomes is at least as difficult.  This, of 
course, is something often attempted by the U. S. government $\ldots$ 
usually with unforseen results.  The upheavals in the Balkans in the
5 years since the Dayton Accords illustrate this, as does the 
post-1953 history of Iran and the last quarter century of events in 
Indonesia.

%--------|---------|---------|---------|---------|---------|---------|
Analogous statements hold for any complex system.  Important examples
include financial markets, ecosystems and the global climate.  All of 
these are domains in which future events are of great importance and 
over which some control is desirable or necessary.  But the complexity
of these systems makes small scale prediction and control intractable.

%--------|---------|---------|---------|---------|---------|---------|
So what is a policy maker to do when faced with such a complex system?
{\sl Concentrate on system properties on scales at which they can be 
described, measured or manipulated, \eg, entropy/instability.}  
Detailed understanding at smaller scales requires exponentially 
increasing commitment of resources:  data gathering and computational
power, for example.

\medskip
\noindent{\bf 8.  Modelling and simulation}

%--------|---------|---------|---------|---------|---------|---------|
The alternative to expending exponentially increasing effort is to
create the kind of minimal models I mentioned in \S1, and only expect 
them to provide certain kinds of macroscopic information.  They should
include all and only the interactions relevant to the scale of 
description desired [\BarYampaper].  This is not always 
straightforward and many realistic simulations (including some of 
those described at this workshop) include too much or too little 
detail.

%--------|---------|---------|---------|---------|---------|---------|
The voting model I've discussed describes people by preference orders.
This is a minimal model which seems very reasonable to physicists, but
has been much debated by social scientists.  There are contexts, 
however, in which such a model is unarguable.  These include three 
modern problem solving techniques:
\vskip6pt

\parskip=0pt
\itemitem{(1)}
multi-agent simulations, \eg, Swarm [\Swarm];

\itemitem{(2)}
multi-agent (\eg, ANT [\ANT] or genetic [\genetic]) algorithms;

\itemitem{(3)}
robots, \eg, [\robots].

\vskip6pt
%--------|---------|---------|---------|---------|---------|---------|
\noindent It is important for policy makers, who are increasingly 
often presented with one of these systems as a putative tool, to 
recognize that they have the same strengths and weaknesses as we have
demonstrated in human group decision making:  sensitivity to initial
conditions, resilience to manipulation, and inescapable 
inefficiencies.  Each of these deserves elaboration, but I do not have
time in this talk to provide it.

\parskip=10pt
\medskip
\noindent{\bf 9.  Campaign physics}

%--------|---------|---------|---------|---------|---------|---------|
The last two sections contain the punchlines for this talk, but I 
promised at the beginning to say something about the difficulty of 
voting.  This requires generalizing the system with discrete 
alternatives considered in \S3--\S6 to the common situation in which 
alternatives form a continuum [\alloc], \eg, `left' and `right' on a 
`political spectrum'.  If multiple issues are at stake, as in an 
election, they form a multi-dimensional `policy space'.  This is the 
arena for spatial voting models [\spatial].

%--------|---------|---------|---------|---------|---------|---------|
\moveright\secondstart\vtop to 0pt{\hsize=\halfwidth
\vskip -1.5\baselineskip
$$
\epsfxsize=\thirdwidth\epsfbox{f3.prefs.eps}
$$
\vskip -0.75\baselineskip
\eightpoint{%
\noindent{\bf Figure~3}.  Three ideal points and a candidate's current
position.
}}
\vskip -\baselineskip
\parshape=16
0pt \halfwidth
0pt \halfwidth
0pt \halfwidth
0pt \halfwidth
0pt \halfwidth
0pt \halfwidth
0pt \halfwidth
0pt \halfwidth
0pt \halfwidth
0pt \halfwidth
0pt \halfwidth
0pt \halfwidth
0pt \halfwidth
0pt \halfwidth
0pt \halfwidth
0pt \hsize
%--------|---------|---------|---------|---------|---------|---------|
As a minimal model, suppose there are two dimensions (say domestic
economy and civil rights) and voters who have `ideal points' in this
space, meaning each prefers a candidate who is closer to rather than
further from his/her ideal point.  Figure~3 shows three ideal points
and a candidate's current position.  Moving into any of the 
lens-shaped regions improves the candidate's ranking by two of the 
three voters.  Assume a candidate always wants to increase his/her 
appeal to a majority.  How will s/he campaign?

%--------|---------|---------|---------|---------|---------|---------|
The analogue of the transition matrix defined in \S4 is an operator
$$
T(z,w) := \cases{1 & if $z \leftarrow w$; \cr
                 0 & otherwise,           \cr
                }
$$
for $z$, $w$ points in the policy space.  Now define the {\sl relative
entropy\/} to be
$$
S[T] := \lim_{N\to\infty}\log\int T^N(z,z){\rm d}z - \log({\rm area})
$$
which is again log(largest eigenvalue of $T$), rescaled by the area of
the policy space.  Recall that the eigenvalues $\lambda$ of $T$ solve 
the integral equation
$$
\lambda f(z) = \int T(z,w) f(w) {\rm d}w.
$$
If an eigenfunction $f$ is concentrated at a single point (the ideal 
point of a single voter, say), the largest eigenvalue $\Lambda = 0$
and the relative entropy is negative infinity.  If there are cycles,
however, $f$ is not concentrated, $\Lambda > 0$, the relative entropy
is finite, and the system is chaotic.  The eigenfunction corresponding
to $\Lambda$ describes the relative frequency with which the candidate
takes different positions in policy space.  For the example of 
Figure~3, Figures~4 and 5 illustrate this frequency distribution.

%--------|---------|---------|---------|---------|---------|---------|
\midinsert
%\null\vskip-4\baselineskip
$$
\epsfxsize=\halfwidth\epsfbox{f4.density.eps}\hskip1.5\chasm%
\epsfxsize=\thirdwidth\epsfbox{f5.contour.eps}\hskip0.5\chasm
$$
%\vskip-1.5\baselineskip
\hbox to\hsize{%
\vbox{\hsize=\halfwidth\eightpoint{%
\noindent{\bf Figure~4}.  The distribution of positions a candidate
takes for the exampe of Figure~3.
}}
\hfill%
\vbox{\hsize=\halfwidth\eightpoint{%
\noindent{\bf Figure~5}.  The `contours of ambiguity'; another view of
the same distribution.
}}}
\endinsert

%--------|---------|---------|---------|---------|---------|---------|
{}From these figures we see that a candidate is motivated to campaign
by making a sequence of position statements which end up distributed
over policy space according to the eigenfunction $f$.  Thus this 
minimal model provides an explanation for the fuzziness of candidates'
platforms---and hence why it's so hard for us as voters to discern
exactly for what they stand.  In the 2000 U. S. presidential campaign,
for example, Gore gave speaches in DC and in LA admitting of different 
interpretations for his position on movie violence, while Bush did the
same thing with race relations at Bob Jones University and before the
NAACP.

%--------|---------|---------|---------|---------|---------|---------|
I'll conclude with a remark written after the election:  This model 
applies equally well to a two candidate campaign in which the 
candidates iteratively try to outpoll each other.  Absent any 
ideological constraints, their optimal distribution of positions is 
the same and voters have little to choose between.  In fact, if both
candidates run optimal campaigns---something which developments in 
polling and communications technologies are continually making easier 
to do---one should expect the voters to split equally between the 
candidates which is, of course, what happened this year $\ldots$ so it 
seems unjustified to criticize either candidate for running a poor 
campaign.  Unfortunately, this analysis does not tell us how to 
resolve the resulting tie!

\medskip
\noindent{\bf Acknowledgements}

%--------|---------|---------|---------|---------|---------|---------|
\noindent I thank Thad Brown, Bruce Driver and Ronnie Mainieri for 
useful discussions.  This work has been partially supported by NSF
grant DMS-0083885.

\medskip
\global\setbox1=\hbox{[00]\enspace}
\parindent=\wd1

\noindent{\bf References}
\bigskip

\parskip=0pt
\item{[\complex]}
\dajm,
``Towards the global:  complexity, topology and chaos in modelling,
  simulation and computation'',
%{\tt chao-dyn/9710005};
%\IJCS, Article [123] (1997),
%{\tt http://interjournal.org/InterJournal/};
in Y. Bar-Yam, ed., 
{\sl Unifying Themes in Complex Systems}, 
Proceedings of the International Conference on Complex Systems, 
Nashua, NH, 21--26 September 1997
(Cambridge, MA:  Perseus Books 2000) 343--356.

\item{[\BarYam]}
Y. Bar-Yam,
{\sl Dynamics of Complex Systems\/}
(Reading, MA:  Addison-Wesley 1997).

\item{[\Condorcet]}
M. J. A. N. de Caritat, Marquis de Condorcet,
{\it Essai sur l'application de l'analyse \`a la probabilit\'e des 
     d\'ecisions rendues \`a la pluralit\'e des voix\/}
(Paris:  {\it l'Imprim\`erie Royale\/} 1785).

\item{[\smv]}
\dajm\ and T. A. Brown,
``Statistical mechanics of voting'',
%{\tt cond-mat/9806359};
\PRL\ {\bf 81} (1998) 1718--1721.

\item{[\chaos]}
T. Li and J. Yorke,
``Period three implies chaos'',
\AMM\ {\bf 82} (1975) 985--992;\hfb
%
M. Misiurewicz,
``Horseshoes for continuous mappings of an interval'',
in C. Marchioro, ed.,
{\sl Dynamical Systems}, proceedings of the CIME session,
Bressanone, Italy, 19--27 June 1978
(Napoli, Italy:  {\it Liguori Editore\/} 1980) 125--135.

\item{[\Italy]}
M. F. Gilbert and K. R. Nilsson,
{\sl Historical Dictionary of Modern Italy}, European Historical
Dictionaries, No.\ 34 (Lanham, MD:  The Scarecrow Press 1999).

\item{[\Arrow]}
K. J. Arrow,
{\sl Social Choice and Individual Values\/}
(New York:  Wiley 1951).

\item{[\BarYampaper]}
Y. Bar-Yam,
NECSI preprint (2000).

\item{[\Swarm]}
N. Minar, R. Burkhart, C. Langton and M. Askenazi,
``The Swarm simulation system:  a toolkit for building multi-agent
  simulations'',
SFI working paper 96-06-042 (1996).

\item{[\ANT]}
E. Bonabeau, M. Dorigo and G. Theraulaz,
``Inspiration for optimization from social insect behaviour'',
\Na\ {\bf 406} (6 July 2000) 39--42.

\item{[\genetic]}
J. H. Holland,
{\sl Adaptation in Natural and Artificial Systems:  An Introductory 
  Analysis with Applications to Biology, Control, and Artificial 
  Intelligence\/} 
(Ann Arbor: University of Michigan 1975).

\item{[\robots]}
M. J. B. Krieger, J.-B. Billeter and  L. Keller,
``Ant-like task allocation and recruitment in cooperative robots'',
\Na\ {\bf 406} (31 August 2000) 992--995.

\item{[\alloc]}
\dajm,
``Complexity of allocation processes:  chaos and path dependence'',
\IJCS, Article [264] (1998),
{\tt http://interjournal.org/}.

\item{[\spatial]}
J. M. Enelow and M. J. Hinich,
{\sl The Spatial Theory of Voting:  An Introduction}
(New York:  Cambridge University Press 1984).



\bye