|
|||||||
|
|
|
|||||
|
|
|||||||
|
|||||||
|
|
|
|||||
|
|
|||||||
My Voting Systems page—on Approval, Condorcet, STV, List Voting, and so on
Note: I'm not talking about voting machines and how theoretically some people can hack elections and other bullshit you read in Black Box Voting. Rather, I'm talking about electoral systems and strategies, analyzing as mathematically and apolitically as possible.
Okay, so obviously there's a lot to say about election systems (in other words, expect frequent updates). For now, I will concentrate on two things - definitions and the problems in some of the systems.
Single-Winner Systems—Definitions
Single-winner voting systems, as the name implies, are those systems concerned with elections in which only one candidate wins, for example elections for president, mayor, and governor. This distinguishes them from multiple-winner systems, in which more than one person is elected, for example elections for parliaments and city councils.
There are currently 4 single-winner voting systems in use in elections worldwide, plus 2 more I will discuss even though they're not used as far as I know. Those 4 are Plurality, Majority, IRV, and Approval; the 2 others are Borda and Condorcet.
Plurality vote is what is known in Britain and Canada as first-past-the-post
and is usually touted as the simplest electoral system. The idea is that there
are several candidates running for a single office, and the candidate who has
the largest vote total wins. This makes sense in elections with no more than 2
serious candidates, as in the USA and in some Parliamentary constituencies in
Britain, but the system completely breaks down when there are more than
2—as in the California recall, in which Bustamante is expected to win the
replacement vote with 25% of the vote total.
Formally, in plurality every voter casts a vote vector of (1,0,0,...,0,0),
or, in other words, every voter has exactly one vote and votes for one and only
one candidate. The winner is the one with the highest vote total.
It is said of someone that he has the plurality of something if he has
more of it than anyone else, even if he doesn't have more than 50% of it.
Plurality's simplicity is often attractive, but the system is full of
drawbacks and criteria it fails to comply with. Take the Florida presidential
election in 2000: Gore supposedly lost by 538 votes, but most of the 90,000
Nader voters surely preferred him to Bush. In other words, Gore lost because
Nader "spoiled"; the election in Bush's favor. The system is flawed
because it forces people to withdraw from the main race (in the Florida case it
was Bush vs. Gore) if they want to vote for their real preference, such as
Nader.
Majority or runoff vote is very similar to plurality, but it has
one crucial difference—namely, that the winner must have a majority of the
vote. If no one gets more than 50% of the total vote, then there is a second
round, in which only the top two candidates in the first round may participate,
and in which the winner is the one who receives more votes than the other (he's
guaranteed a majority in the second round because there's only one other
candidate).
Formally, in majority every voter casts a vote vector just like in plurality,
but if no one has more votes than everyone else combined, then there's a runoff
election between the top two vote-getters.
If we look at the Florida 2000 example above, we'll see that there wouldn't
have been a spoiler effect had there been majority vote. So, majority eliminates
the spoiler effect, right? Wrong. The French are so accustomed to the
first-round being mostly for show because of the large number of candidates, so
in the 2002 presidential they voted for the candidates they liked the most. The
result was that the top vote-getter, as expected, was incumbet Chirac (he got
about 19-20%, if I remember correctly), but number two was not social-democratic
Prime Minister Jospin, but rather anti-immigrant fascist Le Pen. Now, just to
illustrate how popular Le Pen was vis-à-vis Jospin, the polls predicted that the
runoff would be a close Chirac-Jospin race, whereas in the real second-round,
Chirac defeated Le Pen by a 4-to-1 margin. Jospin was left out of the runoff
because of the spoiler effect—his vote in the first-round was so hopelessly
spread among several other left-wing candidates that he lost to Le Pen, whose vote
was barely spread (in the second-round he got about 3% more votes than in the
first-round).
IRV, or Instant Runoff Vote, is a system that combines the single round of
Plurality with the supposed elimination of the spoiler effect of Majority. The
idea is that every voter ranks the candidates. Then, if no one gets a majority
of the first-place votes, then the candidate who has the fewest first-place
votes is eliminated and his votes are distributed to his voters' second-place
candidates. If no one gets a majority now, then this process continues until
someone does.
IRV doesn't suffer from the deficiency outlined above in Majority, but it
suffers something far worse, which exists in Majroity too but to a lesser
degree.
Suppose that there're 3 candidates in an IRV election—a liberal (L),
a moderate (M), and a conservative (C), and suppose that there're 100 voters
who rank candidates as follows:
42: L-M-C
31: C-M-L
21: M-C-L
6: M-L-C
M has the fewest votes and is thus eliminated, and now C defeats L 55 to 45.
However, a few L supporters decide to vote for M so that L won't be a spoiler
and M rather than C will win. If 5 voters change their preference from L-M-C to
M-L-C, then C will drop and M will defeat L. They won't get their first choice
elected, but they will get their second rather than third choice.
Now, suppose that the polls predict that 45 people will vote L-M-C, 25 will
vote C-M-L, 15 will vote M-C-L, and 15 will vote M-L-C. In that case, C will
drop and M will defeat L. Now, the L supporters have an even bolder strategy
than before: they will vote against their candidate in order to make him win.
If 6 L voters vote C-L-M, then they can ensure that M will drop rather than C,
and thus L will perform better once his second-place votes are added to his
total.
An alternative that's sometimes touted to the existent systems
is Borda count, which is used in many sports rankings. Like in IRV, the voters
get to rank the candidates. The votes, needless to say, are counted very
differently: on every ballot, the last-place candidate gets 0 points, the second
last gets 1 point, the third last gets 2, and so on, until the first gets n-1
points. Then, each candidate's points are summed and the one who gets the
highest score wins.
Formally, in this system the voter casts a vote vector of (n-1,n-2,n-3,...,2,1,0);
as in plurality, the voter can choose which one candidate gets which number of
points, and the candidate with the highest number of points wins.
While this system might sound attractive, it suffers from a huge strategy
problem. Take the California replacement vote—there are 135 candidates,
but there are two clear frontrunners, Bustamante and Schwarzenegger. Thus, if I
prefer Bustamante to the Terminator, I'll be tempted to give the first place to
Bustamante so that he gets 134 points and Arnold last so that he gets 0, even if
I think he's the second best. Since the main race is between Cruz and Arnold,
the most logical thing to do in this case is to rank the one of the two I prefer
in first place and rank the other in last place, in order to maximize my voting
power. Indeed, it will be very irrational of me to put Cruz first and Arnold
second, because this way my voting power will be reduced by an order of 134.
And this gets complicated even further. Suppose that a large majority of the
voters in the California replacement—say, 75%—supports Cruz or
Arnold for first place, the other of the two for second place, and someone else,
say McClintock, for third place. Almost all will rank McClintock second because
he's not a threat to their first choice; thus, McClintock will get 133 points
from 75% of the voters, whereas Cruz and Arnold, who are clearly preferred to
him, will get 134 from barely half as many voters. In other words, the feud
between the top two candidates can let the third most preferred candidate win.
Another alternative, touted mainly by professional mathematicians,
experts on voting, and economists, is Approval Vote. In Approval, every voter
can approve or disapprove of each candidate independently of the other candidates;
to put it in another way, every voter can vote for as many or as few candidates
as s/he wishes to vote for.
In Approval Vote, voters can cast any vote vector between (1,0,0,...0,0)
and (1,1,1,...,1,1,0). Note that the addition of a new candidate does not force
the voter to change his/her votes for the other candidates; this principle is
called Freedom from Irrelevant Candidates, which requires an electoral system to
be constructed in such a way that no candidate can change the result of an
election by running or not running unless s/he is the winner. Approval Vote
passes this criterion, but no other voting system from among the six presented
here does (Condorcet comes close, though).
The main problem with Approval is that it doesn't let voters fully express
their choices. Take the California replacement election, in which most candidates
I either liked (e.g. Camejo), hated (Bustamante, Schwarzenegger), or utterly
despised (McClintock). Approval would've forced me to put Cruz and Arnold in the
same category of either Camejo or McClintock, and in either case my vote wouldn't
be able to distinguish all preferences. On the other hand, Approval has a
strategy to maximize the distinction among candidates (until I explain it in my
own words, use this
article for an explanation). Furthermore, adding new categories to Approval
Vote—for instance, replacing it with giving each candidate any number of
points from 0 to 10—will be redundant because it is strategically better
to give every candidate either the highest or the lowest number of points than
(I'll tackle this statement mathematically later) to grade candidate sincerely.
The final voting single-winner voting system I will discuss here is Condorcet.
Like IRV and Borda Count, it requires voters to rank the candidates. This, however,
is where the similarity ends. Even the voting rules are different, because Borda
and IRV don't allow voters to tie candidates, whereas Condorcet does.
Condorcet counts the votes by breaking down the race into pairwise races;
in each such race, a voter is deemed to have voted for A over B if s/he ranked
A over B in the ranked ballot, and vice versa; if s/he tied the two, then the
vote isn't counted toward that particular race. Breaking down the race
seems like a tedious task, but in fact the number of such races is equal to
the number of unique pairs of candidates, which is manageable; even in the
California replacement election, 135 candidates would've translated into
135*134/2=9045 pairs, not that high a number considering the power of machine
counting (hand counts are obviously an entirely different matter). If one
candidate wins in all pairwise elections, then he is declared the winner.
Condorcet gets complicated when there is no such winner (it's possible:
if one voter voted A-B-C, one voted B-C-A, and one voted C-A-B then there's a
cyclical tie among A, B, and C). There are three ways to find the winner: Basic
Condorcet, Ranked Pairs, and Schwartz Sequential Dropping, from the simplest to
the most complex.
Basic Condorcet ranks the pairwise races from the one with the strongest vote
to the one with the weakest vote (the strongest vote is either the widest margin
or the one with the highest vote total for the defeat—not the same thing
when some voters abstain from some races by tying candidates). It then eliminates
the results of the races from bottom to top; if, at any point, one candidate wins
all remaining races, he is the winner. This is bound to happen at some point, as
more and more races are eliminated.
Ranked Pairs takes a completely different approach. It constructs
an actual ranking of the candidates from the results of the strongest races, and
declares the top-ranking candidate as winner. The idea is this: take the strongest
race, and lock it, i.e. if D defeats G, then in the final ranking D will appear
above G. Then, proceed to the next strongest race, and lock it, and so on. If at
any point a race contradicts the results of previous races, for example if the
second race puts C above D and the third puts G over C, then ignore this last race
because stronger races override it. Continue until you get a complete ranking
of the candidates. For a pro-Ranked Pairs site, look at www.condorcet.org.
Schwartz Sequential Dropping works just like Basic Condorcet, but with an
additional provision that makes it very complicated: all candidates outside the
Smith Set are dropped first. The Smith Set is the innermost unbeaten set,
i.e. the smallest set of candidates, each of whose members beats or ties all non-members.
For example, if A defeats B, D, E, and F; B defeats C, D, E, and F; C defeats A,
D, E, and F; D defeats E and F; and E defeats F; then the Smith Set consists
of A, B, and C (this set is smaller than A,B,C,D and A,B,C,D,E, both of which
are unbeaten sets). Finding the Smith Set requires ordering the candidates
according to the number of races they won; in an n-candidate election with a
k-size Smith Set, every candidate inside the Smith Set beats at least n-k+1
candidates (n-k for all candidates outside the set, 1 so that it's justified to
include the candidate), whereas every candidate outside beats at most n-k-1
(only candidates outside the set, minus the candidate him/herself). Then, the top
candidate should be checked for any defeats, then the top 3, then the top 4, etc.
This process will terminate in manageable time, namely O(n4), where n is the number of candidates and O(a) means that the maximum time the process takes is proportional to a. Note: if the Smith Set has
only one candidate, then that candidate clearly is the winner. For a pro-SSD site,
look at Election Methods.
One way to implement SSD is called Beatpath: A has a beatpath to B if A beats B or if A beats a candidate who has a beatpath to B; like with regualr chains, the strength of a beatpath is measured according to its weakest defeat, and given multiple beatpaths from A to B, the one with the highest strength (i.e. strongest weakest link) is chosen. A beats B in beatpath if the beatpath from A to B is stronger than the beatpath from B to A, and the winner is the candidate who beats all other candidates this way. It's possible to find the winner in beatpath in O(n3) time; the algorithm can be found in http://mail.gnu.org/archive/html/demexp-dev/2003-09/pdf00000.pdf.
More coming soon...
This site has gotten
hits since 2003-12-25.