The Labs.Com Issue_03_Voting

TPJ: Issue_03_Voting

This is a collection of programs published by The Perl Journal. You can download all source-code also from TPJ: Programs.

1. pairwise
2. pairwise~
3. finally~
4. condorcet.pl
5. More Samples on Voting

Download pairwise

sub pairwise_tally {

my ($self, $votelist)=@_;

#  $self is an object (ala Perl 5) that stores all basic pairwise

#  election data

#

#  @self->{'tally'} is a two-dimensional array (also ala Perl 5) th\

at

#  stores the pairwise tally results.

#

#  $self->{'tally'}[$candx][$candy] is the number of votes that $ca\

ndx

#  received over $candy.

#

#  $votelist is a string that is essentially a raw text file that

#  contains all of the ballots.

for(split(/\n/,$votelist)) {

#  $loservec-a boolean vector with a flag set for all "losers"

#  reset with every new ballot.  All are losers until they are

#  listed on a ballot.

my($loservec)=$self->{'candvec'};

# Parse ballot.  Skip if no ballot is returned.

(!(my($ballot)=new ballot_obj($self, $_))) && next;

# @{$ballot->{'rankings'}} is an array of integers

# representing the candidates this voter (or voters) voted

# for, in order of preference.

# In addition, $ballot->{'quantity'} is the number of ident\

ical

# ballots we are considering at this time.

my(@votelist)=@{$ballot->{'rankings'}};

foreach $tier (@votelist) {          # For each preference lis\

ted...

# Remove the chosen candidate(s) from the loser vector.

foreach $peer (@{$tier}) {

vec($loservec, $peer, 1) = 0;

}

# For all candidates...

for ($i = 0; $i<= $#{$self->{'candidate'}}; $i++) {

# If said candidate hasn't been listed yet...

if(vec($loservec,$i,1)) {

# ...they've been beat by the chosen candidate.

# Increment their "votes for the other guy"

# counter by the appropriate number of ballots

foreach $peer (@{$tier}) {

if(defined($self->{'tally'}[$peer][$i])) {

$self->{'tally'}[$peer][$i]

+=$ballot->{'quantity'};

} else {

$self->{'tally'}[$peer][$i]

=$ballot->{'quantity'};

}

}

}

}

}

$self->{'total_vote'}+=$ballot->{'quantity'};

}

}

Issue_03_Voting 2. pairwise~

Download pairwise~

sub pairwise_tally {

my ($self, $votelist)=@_;

#  $self is an object (ala Perl 5) that stores all basic pairwise

#  election data

#

#  @self->{'tally'} is a two-dimensional array (also ala Perl 5) th\

at

#  stores the pairwise tally results.

#

#  $self->{'tally'}[$candx][$candy] is the number of votes that $ca\

ndx

#  received over $candy.

#

#  $votelist is a string that is essentially a raw text file that

#  contains all of the ballots.

for(split(/\n/,$votelist)) {

#  $loservec-a boolean vector with a flag set for all "losers"

#  reset with every new ballot.  All are losers until they are

#  listed on a ballot.

my($loservec)=$self->{'candvec'};

# Parse ballot.  Skip if no ballot is returned.

(!(my($ballot)=new ballot_obj($self, $_))) && next;

# @{$ballot->{'rankings'}} is an array of integers

# representing the candidates this voter (or voters) voted

# for, in order of preference.

# In addition, $ballot->{'quantity'} is the number of ident\

ical

# ballots we are considering at this time.

my(@votelist)=@{$ballot->{'rankings'}};

foreach $tier (@votelist) {          # For each preference lis\

ted...

# Remove the chosen candidate(s) from the loser vector.

foreach $peer (@{$tier}) {

vec($loservec, $peer, 1) = 0;

}

# For all candidates...

for ($i = 0; $i<= $#{$self->{'candidate'}}; $i++) {

# If said candidate hasn't been listed yet...

if(vec($loservec,$i,1)) {

# ...they've been beat by the chosen candidate.

# Increment their "votes for the other guy"

# counter by the appropriate number of ballots

foreach $peer (@{$tier}) {

if(defined($self->{'tally'}[$peer][$i])) {

$self->{'tally'}[$peer][$i]

+=$ballot->{'quantity'};

} else {

$self->{'tally'}[$peer][$i]

=$ballot->{'quantity'};

}

}

}

}

}

$self->{'total_vote'}+=$ballot->{'quantity'};

}

}

Note that what is great about this is that I don't have to pre-declare

the size of $self->{'tally'}, the array in which I'm storing the

pairwise results.  This makes it possible to have as many candidates

as the host computer will allow, without predeclaring a ridiculously

large array or creating my own dynamic structure.  This keeps the code

relatively simple (though, admittedly, the quasi-object oriented stuff

I'm doing makes it more complex to read a chunk out of context).

The next stage involves figuring out the winners.  For this I create

what is in essence a database of the candidates, with separate fields

denoting the number of wins, losses, ties, and worst defeat, as

measured by total number of votes against that candidate.  Sadly, I

wasn't feeling particularly programmer friendly the day I was writing

this, and so I made a goofy two-dimensional array rather than an

associative array or one-dimensional array with better names.

Fortunately, the code below isn't too difficult to grok.

Here is the meaning of each of the fields, where $i is the candidate n\

umber:

$edata->{'results'}[$i][0]        # Number of defeats for $i

$edata->{'results'}[$i][1]        # Number of ties for $i

$edata->{'results'}[$i][2]        # Number of victories for $i

$edata->{'results'}[$i][3]        # Worst defeat, as measured b\

y

# total votes against $i

All pairwise tallies are considered as this is filled in.  This gives

us the data we need to calculate the Condorcet, Smith, and Copeland

winners.

I'll leave it to you to fetch the code if you want to see how all of

the methods are calculated, but to give you a taste, here's the code

for calculating the Copeland winners:

sub rank_copeland {

my($self, $edata)=@_;

# A Copeland score is computed by doubling the number of victories

# and adding the number ties a candidate received.

my(@copeland_rankings)=sort {-(($self->{'results'}[$a][2]*2

+ $self->{'results'}[$a][1])

<=>

($self->{'results'}[$b][2]*2

+ $self->{'results'}[$b][1]))}

$edata->candnum_array;

$self->{'copeland_rankings'}=\@copeland_rankings;

}

Passing an anonymous function to the sort routine, I'm able to quickly

get a listing of the candidates in order of their Copeland scores,

picking the winners off of the top.

Using CGI to Spit It All Out

The best thing about using Perl is that, in combination with CGI, it's

a piece of cake to generate nice looking output, even with copious

amounts of complicated data.  Given the ballots in Figure A, I'm able

to generate the following output from my program.

Insert Figure F

The really great news about this program is that I do have it

installed on a publicly available web server, and so you don't need

to try to set it up yourself to actually see what it does for

yourself.  Just browse to the following URL:

http://www.eskimo.com/~robla/politics/condorcet.html

There is still plenty of work to be done with this program.

*  A much more user-friendly front end would be really nice.

*  A "voting booth" program could be written to generate data for use\

with

this program.

*  There are also many common election methods out there that could b\

e

implemented along with this program for comparison reasons.  Hare

and Borda functions, for example, would be great to compare with

Condorcet, Copeland, and Smith.

*  It would also be nice to compute not just the winner, but a list o\

f

winners, in order of preference, for each election method.

*  A future version could allow one to combine methods view their

properties.  For example, a method very popular on the

election-methods-list is Smith//Condorcet (compute the Smith

winner, and break ties using Condorcet).  An interface for

arbitrarily chaining these methods together would be great.

Random Thoughts

Versatile and robust election systems have applications beyond the

traditional role of government.  Local elections, local decision

making, and shareholder elections are all obvious applications for

such creations.  Perhaps there is a role for election methods in

computer science or specifically artificial intelligence (for

instance, one could imagine a genetic algorithm that generates a pool

of voters who submit "preference ballots" to make decisions).

Sadly, our education system, rather than teaching us anything about

good decision-making methods, indoctrinates us into believing that the

American system is the finest in the world and need not be questioned.

The vote-for-only-one ballot would be okay if there were only one

issue spectrum and only two points of view, but society is a bit more

complex than that.

Many pundits and armchair activists talk about how the American system

of politics is broken, and then can only offer up ways of restricting

"the bad guys" as a solution to the problems, be the bad guys big busi\

ness,

labor unions, or special-interest coalitions.  Yet few people are

actually really putting the system itself under scrutiny.  This is a

shame, because we really should be considering the consequences of

having such a simplistic feedback mechanism to our government.

References

Anderson, Lowell Bruce, "Voting Theory".  From _Handbooks in OR & MS,

Vol.6_ editors S.M. Pollock, et al.  Elsevier Science B.V., 1994.

Barrett, Laurence I., "Give Me Your Tired Parties." AllPolitics.

March 1, 1996 (http://allpolitics.com/news/email/9603/01/index.shtml)

Fishburn, Peter C. and Steven Brams, "Paradoxes of Preferential

Voting." Mathematics Magazine, Vol. 56, No. 4, Sept. 1983,

p. 207-214.

Levin, Jonathan and Barry Nalebuff, "An Introduction to Vote-Counting

Schemes." The Journal of Economic Perspectives.  Vol. 9, No. 1,

p. 3-26, Winter 1995.

Niemi, Richard G. and William H. Riker, "The Choice of Voting

Systems."  Scientific American.  Vol. 234, No. 6, p. 21-27.

Riker, W.H., "The Two-party System and Duverger's Law: An Essay on the

History of Political Science." The American Political Science

Review. Vol. 76, p. 753-766, 1982.

Sites

*  The Condorcet's Method Home Page

(http://www.eskimo.com/~robla/politics/condorcet.html)

This is a home page that I put together from various pieces I've

found on the 'net, and includes programs written by other people in

other computer languages.

*  The Election Methods Mailing List

(http://www.eskimo.com/~robla/cpr/election-methods.html)

This list discusses the technical details of election methods.  It

involves the sort of gritty details this article covers.  Much of

the work above owes a huge debt of gratitude to the members of this

list (special thanks to Mike Ossipoff, Steve Eppley, and Bruce

Anderson).

*  The Center for Voting and Democracy

(http://www.igc.apc.org/cvd)

This is an organization which is working toward all forms of

election reform.  Though their primary focus has been on advancing

proportional representation, they do advocate single-winner reform

as well.

--------------45A665BC72CD--

Issue_03_Voting 3. finally~

Download finally~

From robla@eskimo.com Thu Aug  1 05:10:51 1996

Date: Thu, 01 Aug 1996 02:06:28 -0700

From: Rob Lanphier <robla@eskimo.com>

Reply-To: robla@eskimo.com

X-Mailer: Mozilla 3.0b5aGold (Win95; I)

Mime-Version: 1.0

To: orwant@media.mit.edu

Cc: landerso@ida.org, seppley@alumni.caltech.edu, dfb@bbs.cruzio.com

Subject: Final Draft (sans figures)

Content-Type: multipart/mixed; boundary="------------45A665BC72CD"

This is a multi-part message in MIME format.

--------------45A665BC72CD

Content-Type: text/plain; charset=us-ascii

Content-Transfer-Encoding: 7bit

Hi Jon,

Margaret will be working on some figures tomorrow, but I think the res\

t

of this is a done deal.  I'm more than willing to do more editing as

needed (and I could continue to work on this forever and still not be

satisfied), but I at least have something here that I've run the spell

checker over :)

Bruce, Steve, and Mike, thank you for all of your help.  I think this \

is

a much stronger article for it.

--

Rob Lanphier

robla@eskimo.com

http://www.eskimo.com/~robla

--------------45A665BC72CD

Content-Type: text/plain; charset=us-ascii; name="pjarticle.txt"

Content-Transfer-Encoding: 7bit

Content-Disposition: inline; filename="pjarticle.txt"

Perl, Politics, and Pairwise Voting:  Perl as the Activist's Friend

The U.S. Presidential elections once again draw near, and once again

we see that it will come down to one of two men, each representing the

two major U.S. political parties.  So it goes with the two-party

system.

What is it that makes the two-party system a two-party system? The two

party system is a direct consequence of plurality voting, the

predominant form of balloting used in the United States where the

highest vote getter wins an election.  This relationship between the

two-party duopoly and plurality voting is known as "Duverger's Law",

after the 20th century political scientist who had the guts to call it

a "law" (Riker, 1982).

Duverger's Law has some disturbing consequences which leaves many

voters dissatisfied with the status quo.  Politicians will always

claim to "feel our pain", but at least in the U.S., two-party skeptics

abound.  Recent polls have shown that nearly 60% of the American

people would support the formation of a new major party (Barrett, 1996\

).

The main reason Duverger's Law rings so true is that we have a binary

ballot that groups people into two categories: a winner and one or

more losers.  The resulting dilemmas that voters are faced with in

siding with a winner manifest themselves several ways:

*  Because you can't please all of the people all of the time, it is

in politicians' best interest to build divisions, and then build

consensus among slightly over 50% of the electorate, giving them

roughly 49% of the electorate to use as a convenient scapegoat.

*  Along the same line, specific-issue-oriented voters are encouraged

to ally with just enough people to give themselves a majority.  Thi\

s

gives politicians a "path of least resistance" toward which they

can target their campaigns.

*  Ultimately, since voters are powerless to state any more than one

preference, they are forced to take sides even when they stand in

the middle.

The bottom line is that the ballot doesn't let people state what they

really feel.  They can only make a crude approximation of their

preference, and then hope that somehow, the politicians will "get

it".

Voters are often forced into a choice between the lesser of two

evils.  They may not like either candidate, but rather than make a

principled stand and vote for none of the above or perhaps a lesser

known candidate with no chance of winning, they make the strategically

correct decision and vote.

Have the strategy problems above ever demonstrably taken the

electorate where it didn't want to go?  Yes it has.  Abraham Lincoln

is widely considered to be the best U.S. president in history.  Yet,

for better or worse, it was largely a function of the strategic error

of his foes that he won the gnarled four-way 1860 election with the

smallest plurality of any president (39% of the vote), and the result

of that election led to U.S. Civil War.  (However, the numbers

probably would have been substantially different had slaves the right

to vote).

In our century, the most famous three-way strategy dilemma was when

Theodore Roosevelt, angry from losing the Republican nomination, split

the Republican Party vote for their 1912 Nominee (and incumbent

president) Howard Taft by creating the Bull Moose Party.  This allowed

Woodrow Wilson to win handily with a mere 42% of the vote (as opposed

to Roosevelt's 27% and Taft's 23%).  This inspired many states to

create "sore loser" laws that keep candidates who fail to win major

party nominations from forming third parties, and by making

third-party ballot access much more difficult.

Even recently, presidential politics were affected by the three-way

split.  In 1966, Thomas Finan and Carlton Sickles, two relatively

liberal candidates from the left-of-center state of Maryland split the

vote within the state Democratic party nominations for governor.  This

led to conservative George P. Mahoney winning the Democratic

nomination, only to be beaten by Spiro Agnew, who went on to be Vice

President under Richard Nixon.  When Agnew resigned in 1973, it opened

the door for Gerald Ford to be appointed Vice President, and then

later President.  A tenuous connection to the presidency, albeit, but

a very real one, nonetheless. (Anderson, 1994)

Much more serious threats to democracy have been the candidacies that

"might have been".  Since our system discourages anything but a

two-candidate race, we seldom see more.  Rosenstone, Behr, and Lazarus

point out that that few qualified candidates would run under a

third-party label because of the disadvantages they are often faced

with (1984).  For instance, they point out the bias that third-party

candidacies face in the media by quoting James M. Perry of The Wall

Street Journal:

We base [our decision] on the simple proposition that readers

don't want to waste their time on someone who won't have a role in

the campaign.  We're not going to run a page-one spread on a fring\

e

candidate.  We don't have a multiparty system.  Until we do,

nobody's going to cover these candidates.  (Rosenstone, et. al,

1984).

With such biases built into the system, it is little wonder that third\

-

party candidates can't gain the critical mass of support necessary to

become a credible threat.  A pragmatic, intelligent potential

candidate might look at the seemingly insurmountable odds and not run

as a third-party candidate.  Thus, the dearth of credible third-party

candidates becomes the self-fulfilling prophecy, and the two-party

duopoly maintains control of the system.

The Preference Ballot

The key to breaking this lock is to allow voters the ability to vote

for candidates regardless of their perceived odds of winning.  To do

this, we must expand the power of the ballot.  This can be done many

ways, but the method that I will discuss here is the ranked ballot, or

"preference ballot" as shown below:

<table>

<tr><td rowspan=2>2</td><td>Fred Flintstone&\

lt;/td></tr>

<tr><td>Wilma Flintstone</td></tr>

<tr><td>3</td><td>Barney Rubble</td>&l\

t;/tr>

<tr><td>1</td><td>Betty Rubble</td><\

;/tr>

</table>

The great thing about preference votes is that preference votes

express a voter's thoughts much better than a vote-for-one ballot,

allowing them to "bargain for a compromise" should their top choice

not be very popular.  This allows people greater flexibility in

casting protest votes, while not throwing the election to the evilest

candidate (not that Wilma Flintstone is evil; this is just an

example).

The ranked ballot does a great job at limiting strategy, but it

doesn't eliminate it completely, no matter which way you count it.

Political scientists have debated the relative merits of ranked

ballots for years, and many of the discussions have centered around

Arrow's Impossibility Theorem.

Impossibility Theorems

Political scientists have been debating for some time now about

whether or not it's even possible to come up with a way to tally

preference votes.  Most of the debate started with Arrow's

Impossibility Theorem, which claims that any system where people are

allowed to freely and exactly list their preferences has a major

defect in it.  Arrow proves this by showing a series of conditions for

fairness, not all of which may be satisfied simultaneously.

Arrow's criteria are a bit too complicated to be easily summarized

here, but other mathematicians have tweaked and fiddled with the

conditions, and have come up their own sets of conditions.  Fishburn

and Brams (1983) came up with a particularly concise set, which are

listed below:

<U>No-Show Paradox</U>: The addition of identical ball\

ots with

candidate x ranked last may change the winner from another

candidate to x.

<U>Thwarted-Majorities Paradox</U>: A candidate who ca\

n defeat

every other candidate in direct-comparison majority votes may lose

the election.  [This is also known as the <i>Condorcet

criterion</i>, named after the 18th century election theoris\

t who

popularized it.]

<U>Multiple-Districts Paradox</U>: A candidate can win\

in each

district separately, yet lose the general election in the combined

districts.

<U>More-is-less Paradox</U>: If the winner were ranked\

higher by

some voters, all else unchanged, then another candidate might have

won.

Fishburn and Brams maintain in their 1983 paper that at least one of

these four paradoxes will be possible in any election method that uses

a ranked ballot.  One may make the case that since all voting systems

are vulnerable to at least one of these paradoxes, that a perfect

system doesn't exist.  However, there are those that question just how

reasonable satisfying all of possible criteria are, and thus question

the pragmatic value of this line of reasoning.  (Anderson, 1994).

In preference voting as in anything else, it's not going to be

possible to please all of the people all of the time.  This means we

are stuck with the task of merely minimizing the sticking points

rather than pursuing the holy grail of a perfect system.  There are

many (myself included) who believe that we can reduce the flaws to

rare circumstances.

The Borda Method

This is probably the best known method within the United States for

tallying ranked ballots.  It is used by the Associated Press and the

United Press International to determine the champions in NCAA college

sports.  Sports writers or coaches are asked to rank the 25 best

teams, and then the top team on each ballot gets 25 votes, the second

team gets 24, and so on.  The top vote getters are ranked by votes

received.

This relatively simple method is easy to understand, hence, its

appeal.  However, it discourages people from ranking anything but

their top preference, thus making it difficult to derive compromise

candidates from their vote.  Consider a three way election between Joe

Left, Sally Middle, and Martha Right.  I will use this example to

describe an election where a reasonable compromise (Sally Middle)

exists between two somewhat popular extremes.  Given that the seat in

question must go to one person and only one, it seems reasonable that

the middle candidate be chosen.  Let's say the sincere wishes of these

voters are shown in Figure A:

Insert rl-FigA.gif here:

Figure A

If Borda's method is used, where the first place candidate on the

ballot receives two points per ballot, and the second place candidate

receives one point per ballot, then the following result will occur:

Borda Points Awarded

Joe       Sally      Martha

Left      Middle     Right

================================

+---------------------+

40     |       Joe Left      |

ballots  | 2     Sally Middle  |              40         80

| 1     Martha Right  |

+---------------------+

+---------------------+

9     |       Joe Left      |

ballots  | 1     Sally Middle  |              18          9

| 2     Martha Right  |

+---------------------+

+---------------------+

16     | 2     Joe Left      |

ballots  | 1     Sally Middle  |    16        32

|       Martha Right  |

+---------------------+

+---------------------+

35     | 1     Joe Left      |

ballots  | 2     Sally Middle  |    70        35

|       Martha Right  |

+---------------------+

===============================

86       125         89

Figure B

The good news here is that Borda's method does indeed choose the

compromise <i>when everyone votes sincerely</i>.  However,

strategically speaking, if Martha Right supporters have a good idea of

what the poll numbers are, they can (and should) drop Sally Middle off

of their ballot.  If all Martha Right supporters do this, they cause a

40 point drop in Sally Middle's Borda score, causing Martha Right to

win.

Even if some Martha Right supporters don't do this, it is likely many

Joe Left supporters will do the same thing in absence of 100% accurate

polling numbers. (i.e. if they think that Joe Left has a shot at

winning.)  Thus Borda picks a compromise when voters naively list all

of their preferences, but fails when voters catch on to how to "game"

the system.

The biggest problem with Borda's method is that it fails to meet the

"thwarted majorities" criterion that Fishburn and Brams listed.  This

is arguably one of the most important criterion in determining the

winner in a single-winner method, and thus, many examples like the one

above can be created.

The "Hare" Method

The Hare method is perhaps the best known method for tabulating

"preference ballots" outside of the United States.  It was invented in

1860 by Thomas Hare. It's used in Australia and Ireland for

single-office elections.  Preference ballots are tabulated counting

only the first-place candidate on each ballot.  The candidate with the

fewest number of first place votes is eliminated, and these ballots

are transferred to their second place counterparts.

The Hare method is a popular way of eliminating primaries and allowing

people to vote for potentially unpopular alternatives to the two

"major" candidates without fear of "wasting" one's vote.  It does a

pretty good job of eliminating strategy and in many ways is a

substantial improvement over winner-takes-all.

Using Hare to tally the results from Figure A, we tally the first

choices to find that Martha Right receives 40% of the vote, Joe Left

receives 35% of the vote and Sally Middle is eliminated with only 25%

of the vote. The votes for Sally Middle are redistributed based on the

second choice of those voters and Joe Left then wins with 51% of the

vote.

Thus, Hare falls short when considering popular compromises, such as

Sally Middle, also because it fails the Condorcet criterion.

Pairwise Election Methods

Under a class of election methods known as "pairwise" methods the

election above would result in a different winner.  The relative

election results of every possible combination of two candidates is

tallied and the winner of every relevant pairwise election is declared

winner of the overall election.

In the above example, the results of the pairwise elections would be

as follows:

Joe Left (51%) vs Martha Right (49%)

Sally Middle (60%) vs Martha Right (40%)

Sally Middle (65%) vs Joe Left (35%)

Sally Middle beats both Joe Left and Martha Right, and therefore wins

the election overall.

What distinguishes the different pairwise election methods from one

another is how they deal with circular preferences.  A circular

preference is one where the outcome results in one candidate defeating

another who in turn defeats our original winner.  This isn't

necessarily a flaw in pairwise systems.  One may say that this is a

sign that the electorate is ambivalent about who should be the winner.

Some theorists, such as Charles Dodgson (a.k.a. Lewis Carroll, author

of _Alice in Wonderland_), claim that if a single winner can't be

found, then the election should be called off (Levin and Nalebuff,

1995).

Nonetheless, many pairwise methods have been designed to deal with

this problem.  This is a list of descriptions of pairwise elections,

and how the various methods deal with that case:

*   Condorcet's Method

Condorcet's method is probably the most well known of these

methods. Each voter's list is used to simulate how that voter

would have voted in pairwise elections between each of the

candidates listed on the ballot, and between those listed on the

ballot and those that aren't. Separate tallies of every possible

two-way election are kept, and the winner is the candidate that

wins all two-way elections.  Circular preferences are resolved in

Condorcet's method by choosing the candidate whose largest

pairwise defeat is the smallest, as measured by how many voters

explicitly voted for another candidate over said candidate.

The reason why many election reformers prefer this method is that,

under most plausible circumstances, it solves the "lesser of two

evils" problem described above, which many consider to be

<i>the</i> litmus for determining a good pairwise meth\

od.

However, as Bruce Anderson, a mathematician for the Institute for

Defense Analyses notes, in presumably rare circumstances, it may

produce unexpected results.

*   Smith's Method

Smith's Method isn't so much pairwise tie breaker as it is a

method of determining which candidates should qualify to be in a

tie-breaker.  The "Smith Set" is the smallest non-zero set of

candidates who beat all the candidates outside the set in all

pairwise elections.  Not all pairwise methods will pick a member

of the Smith Set (most notably, Condorcet's method) yet

intuitively, one would hope that the winner is picked from this

set.  Smith's method, therefore, makes a good precondition to a

tie-breaker such as Condorcet's.

*   Copeland's Method

Copeland's Method computes the winner of the election by

counting the number of pairwise wins, losses, and ties for each

candidate.  The candidate with the best "record" wins the

election, much in the same way that a sports team with the best

record gets the top seed in that sport's playoffs.  The easy

analogy to sports makes this method much easier to explain and

comprehend than other methods.

One problem with Copeland's Method, much like Smith's method, is

prone to ties, and so is often paired with another tie breaker.

Also, it is vulnerable to a problem where if there are three

parties that are locked in a three-way tie, the party that has the

most candidates on the ballot will probably have the winning

candidates.  This is because they win the most pairwise matchups,

even though many of their victories will come from intraparty

matchups.  This may encourage parties with sufficient funds to

run very large numbers of similar candidates in order to skew the

election in their favor.

There are several other methods that exist for choosing a winner in a

preference balloted election, many of which provide a defensible set

of criteria which they satisfy.  For those of us trying to educate

people on alternative election methods, our goal has been to come up

with the most important criterion and find the election method which

best meets those criteria.

What's this got to do with Perl?

For many of us who aren't mathematicians by trade, it becomes

difficult to debate the relative merits of the different methods

without a way of visualizing some examples.  The solution was to write

a program which shows the data in an easy to understand format.

Now it's time to do a little preaching to the choir.  I chose to write

this program in Perl for several reasons, many of which are all too

familiar to Perl affectiondos.  However, they bear repeating in the

context of programs for elections:

* Perl is freely available, with source code - This is a particularly

crucial feature for something that may serve in the public sphere.

Though there are relatively few voters with the knowledge or

initiative to dig down into the source code, there is a certain

peace-of-mind that can be derived from knowing that anyone can dig

into the underbelly of this vote-counting machine at any time (or

pay for someone to do it on their behalf.)

* Perl is available on many platforms - Since Perl is available on so

many platforms, very few people with a computer are shut out from

using it.  This means election results can be verified on a very

wide range of computers.  Having the source available also ensures

that it will be possible to port it to new platforms as they become

available.

* Limitless arrays - Since array sizes don't need to be

predetermined, I was able to easily write this such that it will

accept as many candidates and votes as the host computer will

allow.

* CGI Standard - CGI programming has become today's standard in

cross-platform GUI development, and Perl is the standard for

writing CGI programs.  Using HTML tables made this task so much

easier, since most web browsers that support tables can be counted

on to display the information produced by my program clearly.

* Speed of development - My initial prototype really wasn't that

tough to write, and constituted very little source