Here is a popular account by Itai Benjamini and Elchanan Mossel from 2000 written shortly after the 2000 US presidential election. Elchanan and Itai kindly agreed that I will publish it here, for the first time, 20 years later! I left the documents as is so affiliations and email addresses are no longer valid.
This is a popular report by Dr. I. Benjamini and Dr. E. Mossel from
Microsoft Research at Redmond on some recent mathematical
studies which are relevant to the U.S. presidential elections.
For More information contact:
Dr. Itai Benjamini, Microsoft Research
Sensitivity of voting schemes to mistakes and manipulations
Do the results of the recent election accurately reflect public opinion?
Or are they the result of some minor local manipulations, and a few random
mistakes such as voters confusion, or counting errors.
There are many potential schemes for electing a president, each with its
own features. One important feature of a scheme is the agreement of the
actual outcome of the election with the outcome of the ideal
implementation of the election which disregards potential mistakes and
mischief. If it is probable that the ideal and the actual outcomes differ,
then frequently the outcome of the election will be in doubt.
In recent years, some mathematical efforts have been devoted to trying to
understand which procedures are “stable” to these potential perturbations
and which are “sensitive”. While the motivation for these studies came
from questions in probability and statistical physics, These mathematical
studies can shed some light on the current presidential election. In
particular, a recent paper by Professors Itai Benjamini and Oded Schramm
from Microsoft research and the Weizmann Institute and Gil Kalai from the
Hebrew University of Jerusalem, soon to be published in the prestigious
French journal Publication I.H.E.S., suggests that the “popular vote”
method is much more stable against mistakes than other voting method.
One example of a decision procedure that we encounter in nature is the
neuron. The neuron has to make its decisions based on many inputs; each
represents the strength of electrical currents at the synapses entering
the neuron. Based on these inputs, the neuron should decide whether to
fire its axon going out of the neuron. It is quite likely that some small
perturbations occur at each of the input synapses. It is therefore
expected that the decision procedure of the neuron will be “stable” to
Experimental evidence indicates that neurons may be modeled as the
following simple procedure. The neuron looks at some weighted sum of its
inputs and makes a decision according to how large this sum is . If the
sum is large, then one decision is made , while if it is small another
decision is made .
The counterpart of this procedure for elections would be counting the
votes and deciding according to the majority of the votes. Mathematical
proofs have been given to show that this decision procedure is the most
stable among all decision procedures.
More complicated neural networks consist of a hierarchy of neurons where
the outputs of neurons in lower levels of the hierarchy are the inputs to
neurons in the higher levels. Some of these networks have been proven to
be much more sensitive to noise than a single neuron.
The counterpart of neural network in the political system may sound
familiar: The voters are divided into groups (states) and each group
chooses its candidate based on the majority vote. Then some weighted
majority of the votes of the states is taken to be the elected president.
The mathematical theorems imply that this system is much more sensitive to
If the overwhelming majority of the population is voting for the same
candidate then it doesn’t really matter which voting scheme we use. All of
the natural schemes are “stable”. On the other hand, when the population
is almost evenly split, different schemes behave differently.
The mathematical reasoning behind the stability of the majority vote goes
back to Abraham DeMoivre and Pierre-Simon Laplace (18th century). This
reasoning implies, for example, that in a population of 98,221,798 votes,
if there is a bias of 222,880 for one candidate, then this candidate will
be chosen, even if for each voter there is a small chance that his or her
vote is not counted or counted wrongly (the results of the last election
as of 11/13/00). As long as mistakes for both sides are equally likely,
the result will correctly reflect the bias in the public opinion.
Thus, in this presidential election while the gap between the two
candidates is only 0.2% of the votes it is still large enough so that the
outcome is immune even if a fairly large percent (10% for example) of the
votes were counted mistakenly (assuming the mistakes were random and
On the other hand the gap of a 388 votes among the 6,000,000 million votes
in Florida (about 0.05% of the votes) may well be too small to overcome
the effect of random mistakes in counting the votes, even if the chance
for a mistake is fairly small (1%, say). It can well be argued that just
because of the (unavoidable) mistakes in counting the votes in Florida
(putting aside all other controversies surrounding the vote there) we will
never be able to know who got the majority of votes among the voters of
Florida. To understand why the picture is so different as far as the
popular vote is concerns in the entire nation and the popular vote in the
state of Florida we should note that the stability against mistakes
increases dramatically as the number of voters rise. (And also, of course,
as the gap between the candidates rise.)
The discrepancy between our ability to call the winner in the popular vote
and disability to call the winner in the electoral college (which is the
winner of the election according to the constitution) is not unexpected.
The new results by Benjamini, Schramm and Kalai show that for many models
majority is the scheme which is least sensitive to noise. In these models
it is assumed that voters make their decisions independently and the
mistakes are symmetric and independent for different voters. It is shown
then that for models resembling the current voting scheme in the U.S.A, if
the population is almost evenly split, the scheme is much more sensitive
to noise than the majority scheme. In particular a tiny fraction of
mistakes is very likely to reverse the ideal outcome of the election.
Moreover, if the elections are almost balanced, then the results are too
close to call.
If the outcomes do not show significant bias towards one of the candidates
then in the “popular-vote” method the probability of random independent
mistakes which effect one in every A votes has a chance of one in the
square-root of A to switch the outcome of the elections. In a method like
the “electoral college” the chance is increased to something like one in
the fourth root of A.
If the popular vote is significantly tilted towards one of the candidates
than the effect of mistakes becomes smaller for all voting methods but
much more so for the popular-vote method.
The study of the sensitivity of voting procedures to small errors for such
models is based on mathematical tools from “harmonic analysis”, and
provides a classification of the voting schemes which are very sensitive
to small amounts of noise and those which are more stable. In particular
among all symmetric voting procedures (i.e., all voters have the same
power), the popular majority is the most robust.
For further technical reading and the precise formulation of the
mathematical theorems see http://front.math.ucdavis.edu/math.PR/9811157
A word of warning is in place. The precise expected effect of mistakes
will depend on the specific statistical model for the voting patterns and
for the noise created by counting errors and biases. For example, more
recent work by Claire Kanyon from Orsay university, Elchanan Mossel from
Microsoft research and Yuval Peres from Berkeley and the Hebrew
University, gives quite a different picture for different models based on
the famous “Ising model” from Physics. We expect that the qualitative
conclusion of the research by Benjamini, Kalai and Schramm applied to the
case of U.S. presidential elections and that the popular vote method is
much more stable to noise and biases than the electoral college method.
For definite conclusions, however, some statistical work on actual voting
data should be carried out. Choosing the most appropriate voting method
involve, of course, many, primarily non-mathematical considerations.
Itai Benjamini, Microsoft Research and the Wizmann Institute for Science
Elchanan Mossel, Microsoft Research