*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

e-mail: itai@microsoft.com

Tel: 1-425-7057024

## 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

these perturbations.

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

minor mistakes.

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

independent.)

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

Well, as some older people remember, the most stable vote is the voting for

“the block of the communists and those who are not members of the Party” (my clumsy translation from Russian).

Vladimir Hinich

Yes, dictatorship is noise stable, but it has various other weaknesses…

Sorry, I wanted to say something sarcastic. I have not read the original paper, but the “popular report” presented leaves a very bad feeling of a study of the sperical horse in vacuum:

the assumptions are never fulfilled.

V.H.

The result by Itay and Elchanan is plain and simple, but it presumes that the population is uniform with electoral preferences independently and randomly distributed across different states.

Nothing can be further from reality. Even the election laws differ from state to state (voter ID, recount rules, mail vote constraints e.a.). The voters know their neighbors and can design various mechanisms to make the outcome of the vote more robust locally, but they have no say in deciding for other states.

The popular vote may indeed be more robust, but not before the federally enforced uniform procedures of voting are legislated. Till then one has no choice but to accept the “weighted Pareto” solution: each sovereign state elects the president by its own rules, and the aggregated choice is a simple weighted vote.

BTW, I do not know, how the weights are assigned. By the population? by the number of registered voters? by the number of potential voters (adults of age by the recent census)?

And, of course, as an Israeli I am hugely curious about the way how the decimal fractions are rounded up to the integer numbers of electors. There is a nice mathematics about our system which might be worth discussing one day.

Dear Sergei and Vladimir, of course the model for voters behaviour is not a realistic model. The question is if the insights coming from this model are relevant to real-life elections. At the time we had a long discussion about it with Itai, Elchanan, Oded, Yuval, Russ, and others. (I tend to think that the insights from the model are relevant.)

As far as I know the weight is the number of representative in the congress. Each state has 2 representative in the senate and the number of representative in the house is roughly proportional to the population.

Dear Gil, as I wrote, the insights are obvious without much calculations to do. The electoral college magnifies small deviations from the mean, rendering the outcome “apparently unstable”. On the other hand, it is not immediately obvious, whether this is a drawback of the electoral system or a sort of advantage. Besides being “faithful to reality” (whatever this means in practice), the results must be convincing to the voters. If your tally is 50.001% vs. 49.999%, the victory looks more like a draw (which it really is, given inevitable counting errors) and hence can be contested. But if this vanishing advantage is represented by 60 or more electors in the college, it is a clear victory (and we know that one can even get a “landslide” victory in the college, loosing the popular vote, which does not mean that the electoral laws are bad).

The issue is so charged that it is somewhat dangerous to involve mathematics into discussion (this is a separate issue). Mathematicians prove accurate results based on clear assumptions, which may or may not hold in a given particular case, but there inevitably will appear people who don’t read and don’t understand mathematics, for them it is enough to cry “Two legs bad, four legs good, and mathematicians proved that, the science is settled!”. Because of my pedigree, I am very sensitive to this kind of misinterpretation of mathematics.