Many forms of Government have been tried, and will be tried
in this world of sin and woe. No one pretends that democracy
is perfect or all-wise. Indeed, it has been said that democracy
is the worst form of Government, except for all those other
forms that have been tried from time to time...
Winston L. Spencer-Churchill (1874-1965)
(in the House of Commons, on 1947-11-11)
One man, one vote! That's conclusive only when there are just two options.
Essai sur l'application de l'Analyse à la probabilité des décisions
rendues à la pluralité des voix
(1785)
M. le Marquis de Condorcet, secrétaire perpétuel de l'Académie des Sciences
(2016-12-27) The Majority Rule decides between two options (only).
Whichever option is supported by the most people prevails.
It took a while for this simple assertion to emerge as the
fundamental principle
behind modern democracies.
At first, voting was reserved to wealthy males. Then all free men were included.
Then, there were no more slaves... Finally, women could vote too!
However, that's not the end of it when three options or more are put to a vote.
In that case the Majority Rule
is no longer directly applicable:
The Condorcet paradox goes to show
that the intention of the voters may not at all be
clear when there are at least 3 options to choose from.
Now, that's no reason to settle for any half-baked arbitrary procedure,
just to reach a quick decision, or any ersatz thereof.
The rest of this page will show that there are pretty good ways to proceed,
in the utmost respect of the Majority Rule.
It will also show how some popular methods are utterly unacceptable in the computer age.
The analysis of what's at stake was inaugurated by Condorcet in 1785
and vigorously revived by Kenneth Arrow in 1951.
It's now a whole academic field of study which goes well beyond this introduction.
However, the basics are fairly easy to grasp and dangerous to ignore.
Ultimately, the Will of the People
shouldn't be allowed to be distorted beyond recognition, for something as trivial as
a lack of understanding of the mathematical structure involved.
The only Good is knowledge, the only Evil is ignorance.
Attributed to Socrates (c.469-399 BC)
by Diogenes Laërtius.
(2010-03-06) The case for a rigorous approach:
Beware of simplicity. Don't rely on intuition alone.
Mathematics is like checkers in being suitable for the young,
not too difficult, amusing, and without peril to the state. Plato(427-347 BC)
Mathematics is the art of spelling out everything (as concisely as possible)
organizing patterns as they emerge. In practice, that's also
a great way to prevent costly mistakes: Measure twice, cut once...
By contrast, simple-minded methods are often impractical or too costly.
We can't build modern bridges by intuition or trial-and-error.
If anything, the construction of voting systems is more delicate than
the building of bridges, because the flaws are far less obviously revealed!
The eloquence of the ignorant may only serve the nefarious purpose of discrediting rigor in the public eye.
In particular, derision may undermine the unfolding of logical arguments for the greater good.
Ultimately, we may all suffer as a result.
It's true that reasonning alone isn't always able to unearth a complete solution to human problems.
However, when it can do so, the public good is never served by suppressing the rational approach.
Also, mathematical thinking helps counteract the dark side of propaganda.
Rushing something to a vote, before digesting it, is unconscionable.
That's true, in particular, when it comes to the adoption of the voting system itself.
The misguided use of raw arithmetic rules is but a powerful way to hide utterly unacceptable prejudices...
No voting system is perfect and none is valid for all purposes.
However some are extemely bad, according to objective criteria, and we should weed them out.
Let's not shove such things down the throat of the voters, for the sake of expediency.
More often that not, expediency just leads to an ersatz of decision without rartional
justification, drowned in decorum.
There's no excuse for accepting, at the core of the democratic process, any procedure,
or lack thereof, which promotes dishonesty or unfairness (whether this was the original intent or not).
The rest of this page provides the basic tools to do the right thing.
Whoever answers before pondering the question
is foolish and confused. Proverbs 18:13
(2017-01-08) The Simplest Case of Condorcet's Paradox A group of voters who prefer A to B and B to C may prefer C to A !
Enjoy your own life, without comparing it to that of another.
Nicolas de Caritat, Marquis de Condorcet (1743-1794)
With 3 options to choose from (A, B & C)
each voter may express his or her own preferences in one of 6
distinct ways (there would be 13
ways if indifference was allowed).
For the sake of future convenience,
we may tally the number of voters in each of those 6 categories
using the 6 quantities a,b,c,x,y,z introduced
in the following table. (x, y and z may be negative).
Notations
Order of preferences
Number of voters
C A B
a + x
B A C
a
A B C
b + y
C B A
b
B C A
c + z
A C B
c
Simplest paradoxical cases (3 voters)
A > B > C > A a=b=c=0 x=y=z=1
A > C > B > A a=b=c=1 x=y=z= -1
1
0
0
1
1
0
0
1
1
0
0
1
With those notations, the outcomes of the 3 head-to-head votes are:
When A is opposed to B
Breakdown
Total
Votes for A
[CAB] + [ABC] + [ACB]
(a+b+c) + x+y
Votes for B
[BAC] + [CBA] + [BCA]
(a+b+c) + z
When B is opposed to C
Breakdown
Total
Votes for B
[BAC] + [ABC] + [BCA]
(a+b+c) + y+z
Votes for C
[CAB] + [CBA] + [ACB]
(a+b+c) + x
When C is opposed to A
Breakdown
Total
Votes for C
[CAB] + [CBA] + [BCA]
(a+b+c) + x+z
Votes for A
[BAC] + [ABC] + [ACB]
(a+b+c) + y
Thus, the advertised paradoxical result (one of two)
occurs if and only if x, y and z verify strictly their
triangular inequalities
(which state that the sum of any pair of quantities is never less than the third).
In that case, those 3 triangular inequalities do imply that x,y,z are positive. For
example, we have
2x+y = x+(x+y) > x+z > y which implies x>0.
The three triangular inequalities are thus satisfied
iff x, y & z are the sides of a
Euclidean triangle (hence the name).
The other paradoxical case (B>A, A>C, C>B)
occurs when the three triangular inequalities are all
backwards, which implies that x,y,z are negative and that their opposites
verify the triangular inequalities. In all other cases,
there is no paradox (which is to say that the collective preferences of the
voters are consistent).
How frequent is the paradox ?
Sometimes, ranking three options really boils down to a simple choice between
two options (whenever the third choice is either clearly inferior or
clearly superior). The paradox will occur with vanishing probability
in such cases, since a vote between two options is never paradoxical.
To evaluate the situation when the three options offered
to the voters are a priori on the same footing,
we shall determine the probability of the above paradoxical situation
when all preferences are assumed to be equiprobable...
The number of (ordered) triples of integers forming the sides of
a triangle of perimeter n is equal to:
(n+2)(n+4)/8 if n is even.
(n-1)(n+1)/8 if n is odd.
Curiously, that's also exactly the number of ordered triples of integers forming
the sides of a triangle of nonzero area and perimeter n+3.
Number of triples (x,y,z) forming a triangle of perimeter n = x+y+z
The paradoxical situation A>B>C>A among v voters is obtained
by choosing a positive n of the same parity as v
and three nonnegative integers
a,b,c which add up to m = (v-n)/2.
(2016-12-21) Tallying votes using additive preference points.
Such a tally can always conceal the true preference of voters.
Although the above shows that
voters may not always have a clear collective preference, any tallying method which is unable
to properly detect a clear choice, when there is one, is either dubious or fraudulent.
Surprisingly enough, that applies to the popular method of translating the ranks
given by every voter into amounts of points to be added
based on a nonincreasing sequence of coefficients
c1 ≥
c2 ≥
c3 ≥ ...
It won't do to just add c1 for every first choice,
c2 for every second choice,
cn for every n-th choice.
Let's prove that :
According to Condorcet
(or any rational person) a choice is clear among voters
when some option is preferred to every possible one by a majority vote
head-to-head (by universal agreement, a majority vote is the only democratic way to decide
between two options).
When that happens,
the preferences of voters are said to obey Condorcet's criterion
and the option which is then clearly the best one is called a Condorcet winner.
A tallying method which picks the Condorcet winner, whenever there is one, is said
to be a conform Condorcet method.
With that in mind, we may restate the above claim:
Theorem : No tallying based on additive preference points
can be conform (assuming the voters have at least three options to choose from).
Proof :
We only need to establish that inadequacy in cases
where just three options are available (with more than three options, it may well be
that all voters happen to prefer three of those over any other).
If c1 = c2 = c3
then the tally of points is utterly inconclusive, as the Condorcet winner
(if there is one) always ties the other two by points.
Otherwise, we may assume, without loss of generality, that:
c1 = 1
c2 = q
c3 = 0
where 1 ≥ q ≥ 0
That is so because we obtain an equivalent system of coefficients by subtracting the smallest
one from all of them and, then, by dividing all coefficients into the largest one, which is necessarily
nonzero.
To establish the claim, all we need is a paradoxical example for every value of q.
Consider first a special case where
only two of the six preference types are present:
Let's say u voters have one order of preference and the v others all
agree on a different one, according to the following table:
Preference
Number of voters
Points to A
Points to B
Points to C
A > B > C
u
u
q u
0
B > C > A
v
0
v
q v
Total
u + v
u
q u + v
q v
If u > v , then option A is clearly a Condorcet winner
because it wins over either B or C by u votes against v.
However, the tally of points does designate B (never C)
as the winner over A if we also have:
q u + v > u
or, equivalently,
v > (1-q) u
Thus, A is the clear Condorcet winner but loses the point tally
if and only if the following double inequality holds:
u > v > (1-q) u
As the vote counts are integers,
the largest value of v which satisfies the left inequality is v = u-1
in which case the right inequality becomes:
u-1 > (1-q) u
which is equivalent to
q u > 1
So, if q is nonzero, we obtain two integers meeting our requirements
by letting u be any integer greater than 1/q (since q is
at most 1, u is at least 2)
while v is equal to u-1.
That yields examples where the clear Condorcet winner doesn't prevail according to point totals.
For q = 0, we use the case below,
where A is the Condorcet winner (garnering 4 or 5 votes out of 7, against B or C)
but B wins by points.
Preference
Number of voters
Points to A
Points to B
Points to C
A > B > C
2
2
0
0
B > A > C
3
0
3
0
C > A > B
2
0
0
2
Total
7
2
3
2
All told, for any possible q, there are always cases where
the clear Condorcet winner loses by points.
(2016-12-26) Plurality Voting (voter's first choice gets whole vote)
It's just a special case of voting by points. Only worse.
Plurality is the voting system whereby each voter gets to vote for
only one candidate. The candidate with the most votes wins.
The French call this majorité relative. This is a misnomer,
since the winner isn't necessarily supported by the Majority Rule.
The French call majorité absolue the special case when
the winner of a plurality vote happens to garner more than half the votes.
That's exactly what you'd get with points
if you count one point for the first choice of each voter and zero for the other choices.
(Incidentally, that forced single-mindedness would be even more damaging to the election of an
ordered list than it is to the election of a single candidate.)
Thus, the theorem proven above fully applies
to discredit plurality voting. More specifically,
the case "q = 0" (singled out in our proof)
is directly applicable. So is the 7-voter example which we put forth to resolve it
(just a plurality vote thinly disguised).
Let's modify that example slightly to make flaws even more obvious.
We simply add two more voters who support C, and obtain the situation
presented in the following table:
An Example of a Paradoxical Plurality Vote
Preference
Number of voters
Votes for A
Votes for B
Votes for C
A > B > C
2
2
0
0
B > A > C
3
0
3
0
C > A > B
4
0
0
4
Total
9
2
3
4
Option A is still the clear Condorcet winner
(beating respectively B and C head-to-head with 6 and 5 votes out of 9).
Likewise, C is still the definite Condorcet loser
(losing to either A or B, by 4 votes against 5).
Yet, the dubious result of the plurality vote is the exact opposite:
C wins with 4 votes (but would lose head-to-head against A or B).
B gets 3 votes.
A is last with 2 votes (in spite of being preferred to either B or C).
Real-life electoral commentators might say that B robbed the votes of A.
Would a primary between A and B have helped avoid the disastrous victory of C?
Well, surely, but what kind of primary do you have in mind?
A would have won an open primary by 6 votes against 3.
B would have won a closed one by 3 to 2 (among opponents to C).
This goes to show that closed primaries can help conceal the best choice
when there's a clear one.
They may go against the greater public good.
On the other hand, open primaries
are best integrated into the voting system itself,
according to transparent criteria compatible with the absolute democratic requirement
of conformity with the Condorcet criterion.
(Separate open primaries are notoriously prone to tactical voting.)
The above example can also be used as an argument against any form of
runoff election, including
instant-runoff voting (IRV).
Indeed, the clear democratic choice of the voters (namely, A) arrives last
in the first round and is thus eliminated from the runoff.
(2016-12-27) Runoff Elections: The Art of Elimination
The result is compelling only if the last round opposes just two options.
Some runoff elections do not insist on having just two candidates in the final round.
One example is French legislative elections, in which a candidate need not
be first or second in the first round to qualify for the final round.
When that happens, a tactical decision (whether to fold or not)
must be made between the two rounds by all qualified candidates.
Such decisions are made more complex by the fact that those elections are
not isolated. The political parties of the candidates may
trade one position in one district against another one in another district.
Here's one example:
(2016-12-27) Qualifying for an Election
A necessary feature prone to abuse.
When the possibility exists that a large number of candidates would be
tempted to run for office,
some legal prerequisites may be helpful to avoid swamping the actual election.
(2016-12-26) Why are point systems so popular? (e.g., Borda counting)
Why equate a relative preference to an arbitrary number of points?
Time and time again, people have adopted quickly such tallying methods
for the sake of expediency. Counting points doesn't seem evil at first and most people will trust
the familiarity with points which they've acquired in irrelevant non-electoral contexts,
including academic grades, games, sports and entertainment
(e.g., Eurovision Song Contest).
Voting by points was abandoned by the Roman Senate early in the second century (AD)
not at all for any mathematical reasons but because such voting methods proved far
too prone to unsavory manipulations
(including political cloning).
Jean-Charles de Borda (1733-1799)
advocated his own version of the thing in 1770 (the so-called Borda count
of an option on a ballot is the number of options ranked below it on that ballot).
Borda understood the validity of Condorcet's objections and recognized the lack of fairness
of his own method, but he kept advocating it "for the sake of simplicity"
(which was indeed a serious consideration before the advent of computers).
Unfortunately, the Borda method endures to this day,
especially for fairly casual elections to the boards of many associations in the United States.
It's being gradually replaced by more rational methods (like
the Schulze method) at least at national levels
where computerized ballot counting makes it untenable to retain the Borda method
"for the sake of simplicity".
Some people would rather die than think... Many do. Bertrand Russell (1872-1970)
(2017-01-04) Cardinal Voting : Grading candidates
Aggregating the scores given to candidates by a panel of judges (voters).
Each judge attributes nonnegative scores to the candidates for a total of k>0 points
(there may be additional constraints on the scoring to encourage judges to spread their votes).
This unusual type of voting is very different from the more common ordinal voting systems
which most of this presentation is concerned with
(using only relative preferences without quantifying their strengths).
Interestingly, the well-known impossibility theorems
only apply to ordinal voting and the cardinal voting discussed here
may help circumvent their conclusions.
In that spirit, cardinal voting is worth considering,
possibly as part of a composite systems.
Let A be the rectangularmatrix whose element
Aij (at line i and column j) is the score cast by judge j for candidate i.
We define two symmetric square matrices using A and its transpose A*...
The candidate matrixC = A A*
The judge matrixJ = A* A
The row sums of C are used to rank the candidates.
(2016-12-25) Conform Condorcet methods:
They correctly produce the voters' intended choice, whenever it's clear.
Fortunately, there are many ways to tally preference ballots which always produce
the Condorcet winner if there is one.
(Plurality voting and any other form of counting by
points are just not among those methods.)
Such methods are said to be [conform] Condorcet methods,
in the weak sense (that's the way
the term Condorcet method is understood in the literature,
unless otherwise specified).
Some tallying methods achieve that conformity by using adequate scores
and ranking the options from highest to lowest score.
(The conform voting system devised by Ramon Llull in 1299 doesn't rely on scoring.)
Before the advent of computers, such conform scores were tedious to compute
(much more so than the aforementioned expedient additive points).
For example, we may give to each option a score equal to the number of victories
obtained in head-to-head matchups (counting a tie as a fraction of a victory).
This is obviously a conform scoring system because, with N options to choose from,
the Condorcet winner would have scored N-1 victories and all others N-2 or less.
That's called Copeland scoring.
Strong Condorcet conformity :
When we ask a voting system to yield an ordered list of the various options,
it's reasonable to demand that such a system would produce the perfect
Condorcet order whenever it exists.
A Condorcet order is an ordering of the options such that the first one
is the Condorcet winner, the second one is the Condorcet winner among all other options,
the third one is the Condorcet winner among all options but the first two, etc.
In the present work,
we say that a tallying method is strongly conform
(or that it's a [conform] Condorcet method in the strong sense)
when the following conditions are met:
The Condorcet winner, if there is one, is produced at the first place.
The Condorcet loser, if there is one, is produced at the last place.
The Condorcet order, if there is one, is obtained as the full result.
So stated, the last condition is fairly weak, since a Condorcet order is
a rare thing. However, it suits our purposes well enough at this time.
We'll see that
Copeland scoring is strongly conform.
So is any method of breaking ties between options having equal Copeland scores.
I advocate as a tie-breaker, the total number of votes
garnered by an option in all pairwise confrontations.
(The remaining ties have to be broken with arbitrary time-honored
methods, for example using the ages of the candidates.)
Also, it's very important to note that Llull's procedure transforms
a strongly-conform method into another strongly-conform one
(because any Llull switch has this property).
That's true for either the normal procedure
of Llull (increasing zig)
or the backward one. (decreasing zag).
It also holds for any concatenation of zigs and/or zags.
Those lemmas will ultimately allow us to construct
a complete voting system which
is strongly conform in the above sense and also
stable, which is a requirement of paramount
political importance (although it's almost always ignored).
By contrast, a single Lull zig-zag appended to an arbitrary
voting system will produce a voting system which satisfies
the first and the second of the above conditions, but not necessarily the third!
(2016-12-22) Llull's Procedure (Raymond Lull = Ramon Llull, 1299)
Turning any preliminary order into a conform Condorcet voting system.
Left
Right
Winner
Loser
Let's use the following graphical convention to describe how a left-to-right
ordering of two options is corrected by a possible switch,
according to the result of the head-to-head vote
symbolized by the checkbox.
First
Last
An important convention is that no switch takes place in case of a draw,
so the initial left-to-right ordering is effectively a tie-breaking rule.
The figure shown at left then describes graphically
one way to turn an arbitrary preliminary ordering of any number of options (top)
into a conform Condorcet tallying method (bottom).
Bowlers will recognize the structure used in the finals of major bowling tournaments,
as pairwise matches amend an otherwise established ranking.
Using some arbitrary preliminary order,
the above was proposed as a voting system for the Church in 1299
(De arte
eleccionis) by Ramon Llull
(1232-1316) a
Franciscan tertiary.
His name used to be anglicized as Raymond Lully or Raymond Lull.
He published in Latin as Raimondus Lullus
and is known to the French as Raymond Lulle.
He was beatified in 1857 and is revered as a saint in his native
Catalonia.
He is the dominant author of medieval
Catalan literature.
Llull's system is a conform Condorcet method,
as it always elects the clear Condorcet winner, whenever there is one.
Back in the thirteenth century, Llull may or may not have realized that there need not
always be such a clear winner, in which case the outcome depends
on the preliminary order.
Originally, voters only had to reveal their preferences as needed
and they could very well vote for C over A for tactical
reasons, even if they secretly preferred A to B and B to C...
(Llull assumed they would vote sincerely.)
We may as well disallow this type of
manipulation by specifying
that voters cast their ballots only in the form of a linear list of preferences
(which, incidentally, allows voting by mail).
According to the terminology used in the literature,
this is equivalent to stating that all voters are rational.
(It's rather pointless to study the cases when they're allowed not to be.)
If a spreadsheet (Excel) is used to tally such preference ballots automatically
(see example) then
each step of Lull's procedure is implemented by a single line which normally
reproduces the previous one except for a pair of cells identified by a colored
background. The programming of those colored pairs ought to make them
equivalent (i.e., any such pair can be
cut-and-pasted from any other).
Only one pair has to be programmed from scratch. A typical fragment looks like this:
In this, the numbers represents the numerical identifiers assigned to every option (or candidate).
A colored pair may either reproduce the cells above it (as in the
case of [4 vs. 7] or [9 vs. 4] in the above screenshot)
or switch them
(like [5 vs. 7] or [2 vs. 4] are switched).
The latter is done only when the voters positively prefer the right option to the left one.
Doing nothing in case of equality means that the preliminary order stands
(left to right) unless contradicted by a vote, which reduces it to a tie-breaker.
(2017-01-02) Tallies are the relevant summaries of the votes.
Tallies are sufficient data: Identical tallies yield identical outcomes.
Obtaining tallies is the time-consuming operation.
After that, the computation of the outcome
doesn't depend on the number of voters.
Many voting systems may share the same tallying process.
With manual counting of the ballots, the simplicity of the tallying was an important
consideration. That's a key aspects which made plurality voting so popular.
(In a plurality vote, the only tally needed is a running count of the votes garnered by each option.)
For related point systems, the tally can be the running total of the points
garnered by each option, but it's computationally better to update
a tallying matrix, telling how many times
a given candidate is attributed a given rank. The total garnered by each option
can easily be obtained from that matrix.
For ranked voting systems (with ballots consisting of linear lists of preferences)
the tally we need is a matrix which gives
at line i and column j the number of votes Vij
in favor of j in a head-to-head confrontation with i.
(Some authors interchange the rôles of i and j.
The two conventions are related to each other by transposition.)
If there are N options to be ranked and M voters to rank them, then
the above tallying can be obtained in a time proportional to M N2.
Alternatively, if the number of options is so small that the number
W of
possible ranking choices
is substantially smaller than the number of voters, then the tallying can be done in a time
at most proportional to MN+WN2
by first recording (in a tallying array of size W)
what type of preference each voter expressed. The results are then used
as coefficients in a weighted sum of the W matrices
corresponding to every type of preferences.
(2016-12-27) Nefarious manipulations of the electoral process:
Taking advantages of the weaknesses of a voting system.
Back in the thirteenth century, Ramon Llull
insisted on a certain decorum in his voting proposal (for Church functions).
He prescribed two things:
Every elector would take an oath that he would vote according only to his best
judgment of the qualifications of each candidate.
The vote was public, so everyone could see how every elector was
discharging the duty he was sworn to.
In those days, an oath meant something and that was a good enough way to prevent a type of
manipulation of the voting system which I like to call tactical misvoting
(it's a perverse form of tactical voting).
I find the proposed term of bribery
rather unfortunate, as the cause of intentional misvoting need not be a bribe.
Manipulations are not necessarily related to outright corruption.
There are two widely-recognized ways of manipulating a voting system:
Strategic nominations : Adding or withdrawing candidates.
Tactical misvoting : Voting against one's true preferences.
In this context, misvoting (or perverse voting)
consists of casting an insincere vote
to take advantage of the idiosyncrasies of the voting system.
It's essentially the practice of voting for an inferior candidate just to increase the chances
of one's overall favorite in the final decision.
To do such a thing, the voter must know something (not necessarily much)
about the intentions of the other voters.
Misvoting is opposed to more palatable forms of tactical voting,
like mere compromising
(which consists in supporting a moderate option in order to defeat an extreme view opposed to one's own).
Misvoting is immoral in the sense any student of
Immanuel Kant
will instantly recognize:
If everyone misvoted, the whole system would collapse and one of the worst options
could triumph, against the true will of an overwhelming majority of voters
(possibly, even against unanimity).
A weaker Kantian
argument also applies to open primaries; if both camps
always vote for the weaker candidate in the other camp, the best candidates
will never get elected, in either camp.
Here's one of the simplest examples of tactical misvoting, which works
like a charm in the case of Llull's system
(at least in the thirteenth century version where the voters were not constrained
by a rational order of preferences a priori):
The supporters of two serious contenders may figure out that
one very good candidate stands in the way of both of their respective favorites.
So, with or without premeditation,
they decide to cast their votes in favor of an inferior fourth candidate
to block the good one in the early stages of a Llull vote.
After that nefarious elimination,
everyone forgets about the inferior candidate and the road is wide
open for the other contenders... Bad.
Unfortunately, it has been shown that no ordinal voting system
is completely immune to manipulations.
At least, that's one way to interpret some of the classical
impossibility theorems pertaining to voting.
A fairly recent fashion has been to observe that,
at least with some robust voting systems,
the computation of manipulations
is provably hard in the convincing sense of NP-completeness.
NP-completeness means this:
If there was an efficient algorithm to compute all
possible manipulations available to a small number ot voters
(assuming a decent voting system)
then there would be an equally efficient way to break the current security
of all electronic banking transactions.
(Here "efficient" means a computing time less than some
polynomial function of the
size of the input; that's not always a practical
criterion but it often is.)
By itself however, this fact provides little solace, since all such
analyses are ultimately concerned only with worst-case scenarios.
In the above theoretical sense, manipulation procedures which are effective
in almost all configurations may still be computed fairly efficiently...
For example, the NP-completeness of some
voting systems is strictly based on the possibility of pairwise ties,
which are extremely unlikely in general elections (but then, again,
the fewer the voters, the more effective the voting manipulations).
(2016-12-30) The Impossibility Theorems (lowering expectations)
Voting systems can be downright unacceptable or darn good, not perfect.
Condorcet's intransitivity of pairwise voting decisions,
can be construed as the earliest impossibility theorem:
Although pairwise voting is arguably the only sound basis for a democracy,
it's not adequate tu run government on a daily basis.
It would be theoretically impossible to put every decision to a vote, even if it was practical to so so.
In modern times, other impossibility theorems
have been established which show the incompatibility of various desirable features of voting systems.
We're stuck with imperfection, but that's no reason to settle for mediocrity!
(2016-12-28) Composite Voting Systems
Thinking out of the box.
Most vote theorists will consider only the problem of
aggregating lists of preferences provided by the voters,
without considering the possibility of requesting additional information from them.
In the late 1990's, I was instrumental in the adoption of a system
(for primaries meant to form slates in French senatorial elections)
which required two ballots from each voter.
One was a linear preference list, the other allowed voters to
distribute
(with a few constraints) a total of 12 points to the candidates.
That allowed the voters to give a clue about the strengths of their relative preferences.
The system lasted for nearly 20 years and helped form successful
French senatorial slates.
Points were tallied first, to obtain a preliminary
ranking order with a modicum of legitimacy.
To that preliminary order, the Llull procedure was applied,
which made the voting system conform.
There was a provision which made it stable with respect
to the first three positions (with manual counting,
it was difficult to go much beyond that and the rest of the slate was of
limited importance).
The resulting system accommodated mail voting (that was a key requirement)
and it was quite resistant to manipulations.
To my eternal shame, the earliest version of that voting system was only
cardinal.
Unlike later versions, that was neither conform nor
robust enough.
At the time, the very concept of any type of structured primaries
was already difficult enough for incumbents to accept.
Any lack of aesthetic appeal could have resulted in a stillborn initiative.
Generally speaking, such a two-ballot system is considered unwieldy, in spite of
its ability to circumvent some impossibility theorems.
The above system survived until 2014, when the left-wing government elected in 2012
(and openly irresponsive to the plea of French expatriates) changed the electoral rules.
The artificial increase in the size of the electoral college for senatorial
elections gave back control to the upper management of political parties,
rather than entrust exclusively the representatives of said political parties within the community
of French expatriates.
That made this type of carefully-designed primaries less relevant, if at all.
(2016-12-09) Stability is desirable in an aggregation of preferences:
No majority should ever contradict the order of two consecutive options!
Stability so defined is especially important in real-life political primaries
(where the voting system is agreed upon, rather than imposed by law).
Primaries are useless unless a good number of participants rally behind the result
and third parties find the result compelling (not just by itself but also because of the way it was obtained).
Therefore, the outcome of slate primaries ought to be justifiable by something other than the arcane
peculiarities of a newly-adopted voting system.
Only justifications based on the Majority Rule
are universally accepted in that context.
If the outcome is stable in the above sense,
then any potential disgruntled candidate ends up being ranked just below a predecessor
against whom he or she is known to be unable to garner a majority of votes.
Any claim for a better position would thus infringe on the rights of that legitimate predecessor
and that doesn't seem fair...
That's one way to to put an end to bickering and encourage rallying behind the result.
Stabilization by zig-zag :
If a normal application of Llull's procedure (in ascending order of pair matching)
is called a zig, then the backward procedure (in descending order of pair matching)
may be called a zag.
A single zig need not yield a stable order in the above sense.
The only guarantee after one zig is that the top pair is correctly ordered.
Likewise, one zag only guarantees that the bottom pair is correctly ordered.
Now, if we apply zigs and/or zags repeatedly,
then we shall obtain a stable ordering after finitely many steps.
Proof :
Let's call an inversion,
with respect of the current ordering, any pair of options (not necessarily consecutive)
whose relative order would be disavowed by a majority vote
(a tied vote doesn't disavow anything).
Clearly, either a full traversal (zig or zag)
doesn't switch anything (which shows that the ordering is now stable)
or it reduces the number of inversions by at least one unit...
Starting with finitely many inversions, a stable ordering
must thus be obtained after finitely many traversals.
We can be more definite than that
(and obtain a more efficient procedure) if we always alternate zigs and zags.
We'll always start with a zig.
It's more natural to do so, because a
Condorcet winner, if there's one, is thus detected as early as possible
(after just one zig).
The Condorcet loser, if there's one, is usually of lesser importance to onlookers,
in case of public manual counting. Also, truncating the procedure just after
the beginning of the first zag makes the first three positions
stable in the sense discussed here.
(2016-12-18) Encouraging or Discouraging Multiple Political Terms
About incumbents.
Incumbents have a vested interest to preserve the status quo
which got them elected in the first place, if they want to run again. Less cynically,
consecutive terms may be beneficial to the general public as it gives us
more experienced elected officials.
In any case, it stands to reason that incumbents shouldn't be judged on the same scale as
newcomers. They have an actual record to defend, which may be an asset or a liability.
Newcomers have to prove their worth and/or their ability to do better
than an incumbent. The criteria are very different.
At the time of the aforementioned
two-ballot primaries, I had devised a preliminary ratification
of incumbents, which they had to win by a strict majority to take part in the primaries.
For completeness, the rules called for a vote among the incumbents so ratified,
using a rule similar to what was specified for newcomers, if there was more than
two ratified incumbents (which never happened).
The rules stated that the leading ratified incumbent would lead the slate.
This particular clause won the incumbents over to the new set of rules.
One added bonus is that a majority vote is far more predictable (for the incumbent)
than a vote with more than two options (regardless of the voting system).
Thus, an incumbent who was tempted to run again could renounce honorably rather
than face the humiliation of being formally disavowed by the majority of his or her supporters.
That's precisely what one incumbent did (after being ratified unanimously for the previous term).
However, that clause was eventually
repelled as unfair to newcomers, in part at the instigation of said newcomers
(which was probably a misguided effort on their part, as the next edition seemed to
imply that an incumbent capable of winning a ratification could easily compete successfully
among newcomers, supposedly on an equal footing).
(2017-01-04) Voter Transition Matrix
From a primary to a general election.
(2016-12-28) Aggregating Linear Lists of Voting Preferences
How to make the best of preferences lists when that's all we have.
The double-ballot procedure mentioned above
is a luxury. In practice, it's only applicable to motivated voters insensitive to
Downs paradox.
Failing that, it's best to accept the conventional wisdom and request from the
voters only the linear order of their preferences.
Even if the counting of the votes is computerized,
it's important to be able to describe the procedure in as few words as possible.
This does influence the choice among equally rational methods
(e.g., Schulze's method is difficult to fully describe
in just a few words). For that reason, I advocate the voting method described as follows
(which is strongly conform and stable):
A Set of Instructions for a Fair and
Robust Aggregation of Preference Lists
Ballots are printed with short instructions and a list of candidates in
a unique order (predetermined randomly).
The voters are instructed to put different ranks
(positive integers which need not be consecutive)
in front of the candidates they choose (the lower the rank, the more esteemed the candidate).
Unranked candidates are considered ranked last, at the same level.
The ballots will be tallied by first establishing a
preliminary order among the candidates according to the
number of victories each would have won in
pairwisemajority votes against each other
(a tie being worth half a win). The total number of votes garnered
in those confrontations is used as a tie-breaker (if the tie remains,
the older candidate prevails).
That preliminary order is then corrected by the following procedure:
In increasing order, starting with the candidate now ranked last, every candidate is
matched against his/her current predecessor and their order is switched if it contradicts
a majority vote between them.
The same is done in decreasing order, starting with a match-up between the candidates now
ranked second and third.
The above two steps are iterated alternately until one entails no switch.
The stable ordering so obtained is the final outcome of the vote.
It is essentiial that the tie-breaking method be rigorously specified in advance.
One advantage of the type of stabilization described here
is that the tie-breaking method is an essential part of the preliminaries a priori.
It's not a vague afterthought subject to bickering!
(2016-12-21) Copeland Scoring (A. H. Copeland, 1951)
How many times would an option prevail in head-to-head matchups?
When ballots are linear preference lists among N options (or candidates)
we may oppose the options pairwise in a majority vote and record the results.
(There are N(N-1)/2 of them.)
The balanced Copeland score of an option is defined as
the number of other options against which it would win a two-way vote minus
the number of options it would lose a vote against
(ties don't contribute to either number).
Alternately, we may count one point for a win, half-a-point for
a tie and nothing for a loss.
Those are just two different ways of measuring the same reality,
just like Celsius and Fahrenheit
are two different ways of measuring temperature.
The conversion between the two flavors of Copeland scores is obtained from a simple observation:
A given candidate is involved in just N-1
majority votes. Therefore, its number of wins (W) ties (T)
and losses (L) verify:
W + T + L = N-1
Adding the balanced Copeland score (W-L) to both sides, we obtain:
2 (W + T/2) = (W - L) + (N-1)
That's a fixed relation between the two score flavors,
which may serve as a conversion formula.
For the sake of programming simplicity, we could also use a third equivalent
type of scoring by assigning two points for a win, one point to a tie and zero to a loss.
Ranking according to Copeland scores (in whichever flavor you choose)
provides a conform voting system.
More precisely, the Condorcet winner, if there is one,
will be the only option achieving the highest possible Copeland score.
The Condorcet loser, if there is one,
will be the only option achieving the lowest possible Copeland score.
The most severe limitation is that only 2N-1 different Copeland scores can occur.
In cases where ties are rare or ruled out, all but N of those are unlikely or utterly impossible.
(Ties are rare when there are many ballots and they are impossible when there is an odd number of
valid ballots, assuming the rules demand definite preferences on every ballot.)
Originally, A.H. Copeland counted only wins and discarded ties and/or losses,
which made only N scores possible (from 0 to N-1).
For completeness, there are infinitely many non-equivalent scoring methods which differ from
[any flavor of] the above only by the weight t attributed to every tie.
They are all conform when t is between 0 and 1.
When t is irrational, (N+1)(N+1)/2 different scores are possible.
For any choice of t other than 0, 1 and ½
manipulations are provably difficult to compute
(cf. reference below).
This is, however, no guarantee against fraudsters, since the
heuristic which ignores the possibility of ties
can still compute reasonably fast a manipulation which takes advantage of most weaknesses
(albeit not in the worst case). I'll ignore all that, since better voting methods
are provided by more decisive scoring methods
(including second-order Copeland scoring).
It's often reported that Copeland scores were put forth by
Ramon Llull in the thirteenth century.
To the best of my knowledge, that's not so.
The second-order Copeland score of a candidate is the sum of the
Copeland scores of all the candidates he would defeat
face-to-face (and half the Copeland scores of the candidates he would tie with).
So defined, Second-order Copeland scoring does depend on the particular flavor
of first-order Copeland scoring it is based on.
What remains invariant is the entire class
of second-order Copeland scoring where the score of an option is defined
as a fixed linear combination of its first-order score and the associated second-order
Copeland score defined above.
In that class, the conform scoring methods form
a convex set.
The scoring methods on the border
of that set are said to be purely second-order.
(2016-12-29) The Schulze Method
Deriving a transitive relation between options from preference lists.
The fact that voting preferences are not transitive
is equivalent to the Condorcet paradox in the form stated above.
Therefore, a good basis for the design of a rational voting system would be
to derive from the wishes expressed by the voters a
transitive relation between the options they have to choose from.
Once such a relation is obtained, the ordering of the options is trivial
(unless ties subsist).
(2013-09-18) Are Quotas a Good Thing?
The dangers of slicing the citizenry into categories.
Ideally, quotas are only a temporary mean to repair a grave
injustice due to a long discrimination toward a group of people.
It's a way to forcibly end the effects of that discrimination.
Once enough time has passed to distance the heirs of that discrimination
from its effects, there is no longer any justification
for maintaining any legal distinction between this group and the rest of society.
The normal state of the law is that all individuals should be treated
equally. Any deviation from that norm can only be temporary.
(2013-09-18) Clienteles and Coalitions
Minorities may triumph.
(2013-09-18) The Evils of Dogmas and Agendas
Dogmatism reduces or eliminates the tossing of ideas.
(2013-09-18) Weighting Conflicting Interests
The proper political domain is only the boundary of a convex set.
Very often, choices have to be made between incommensurable things.
To simplify, let's say we have just two such incommensurable criteria
against which possible decisions could be measured.
Financial considerations and human lives at stake, for example.
Obviously, when a decision is inferior to another according to both
criteria, it should be ruled out.
However, other decisions can be ruled out too, because...
(2013-09-18) Ranking Options According to Multiple Criteria
On the relative size of the convex hull in many dimensions.
(2017-01-02) Apportioning Integers in lieu of Fractional Values
This ubiquitous political conundrum has a simple mathematical solution.
The practical apportionment problem is to divide a given integer P
(number of seats, say) into B integers corresponding to as many buckets
(e.g., political parties, running slates, territories to be represented, etc.)
so that each gets a number Pi [roughly] proportional to
its merit Mi (e.g., number of votes received, total population)
under the constraint:
P = P1 + P2 + P3
+ ... + PB
The Largest-Remainder Method :
That simplistic method,
defined below, has no theoretical justification.
It was once popular, in spite of its many flaws.
The rule was abandoned in 1911 for the apportionment of U.S. representatives,
mostly because it allows the unconscionableAlabama paradox.
The Alabama paradox is the name now given to an anomaly of the largest-remainder method
which was observed about the number of U.S. representatives to be allotted to the state of Alabama
after the U.S. Census of 1880:
C.W. Seaton (chief clerk of the
U.S. Census Bureau)
pointed out that Alabama would have 8 seats in a House of 299 representatives,
but only 7 seats in a larger House of 300...
This dubious apportionment rule also goes by several other names,
referring to various people who once advocated it
"for the sake of simplicity":
Hare-Niemayer method,
Hamilton-Vinton method, etc.
The largest-remainder rule consists of the following three steps:
Let Q be the total voting population M divided by P.
First assign to bucket i (e.g., i-th state or slate) the quotient
Mi/ Q rounded down, denoted
[ Mi/ Q ].
This leaves k unassigned seats. Assign one of them to each of the
k buckets yielding the highest remainders in the above divisions.
When all divisions are exact, k is zero.
This isn't an exception to the above wording if "one of zero" is understood to mean "none".
There may be a need for an arbitrary tie-breaking rule in the third step.
The procedure seems fairly innocent until you are aware of its many flaws,
including the fatal Alabama paradox mentioned above.
The French call it proportionnelle au plus fort reste
(it was once part of the French electoral code but it's now outlawed in favor of the method introduced next).
The deprecated largest remainder method is classified as a ranking method.
All such methods are considered inferior for apportionment,
in part because they allow the Alabama paradox.
A Rational Approach :
Instead of looking too hard at the problem at hand (for a fixed number P
of seats to assign) we ignore the particular value of P and see how
the apportionment changes when the divisor Q varies from very large values
(when no seats are assigned) down to tiny ones (for which too many seats are assigned).
If we denote by [x] the largest integer not exceeding x
(the value of x rounded down) then we assign this many seats:
That sum takes on nonnegative integer values (from zero to infinity)
as Q varies as stated.
Some values can be skipped (which correspond to the possible existence of ties)
Otherwise, this sum is equal to the given
P for some value of Q (known in this context as the largest divisor).
When that happens, the right number of seats has been assigned according to what's known as
Jefferson's method
(which is immune to the Alabama paradox).
It's also called method of the largest divisor.
The French call it proportionnelle à la plus forte moyenne
(it's now the only legal apportionment system in France).
It's very effectively described as an unending sequence of seat assignments:
Once k seats have been assigned (starting with k = 0)
the (k+1)-st seat is assigned to whatever bucket yields the highest value for the
following expression of the average
(moyenne in French)
which depends on the number ki of seats assigned so far to that particular bucket:
Mi/ (ki+1)
The French legal rules are entirely equivalent to that method but they save
some time, on election day, by apportioning the first seats quickly with the
same first two steps as the deprecated largest-remainder method.
Because of convexity considerations,
the same shortcut could be used with other ways of defining an average
(there are many, the arithmetic mean
underlying the above is just the simplest).
Apportionment methods based on variants of the above scheme
are sometimes collectively known as rounding methods. (All
rounding methods avoid the Alabama paradox.)
They can differ in two respects:
Rounding up is ideally suited when there is a legal requirement to apportion at least
one seat to every bucket. The U.S. Constitution does impose at least one
representative per state.
The resulting method (with arithmetic averaging)
is called Adam's method or the smallest-divisor method.
It has never been used.
(2016-12-25) Purpose.
On the necessity of proper elections.
If you are right and you know it, speak your mind.
Even if you are a minority of one, the truth is still the truth. Mahatma Gandhi (1869-1948)
The best argument against democracy is a five-minute conversation with the average voter. Winston Churchill (1874-1965)
What voting should not be used for :
Putting things to a vote is first and foremost an admission of failure.
At the very least, a failure to reach a consensus.
However. it could also be a failure to grasp the fact that a complicated issue
has components which can be optimized without infringing on the interests of anyone.
It's rarely the case that human affairs can be settled by reasoning alone,
but when that happens it's a darn shame not to do so.
