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) that
#  stores the pairwise tally results.  
#
#  $self->{'tally'}[$candx][$candy] is the number of votes that $candx
#  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 identical
        # ballots we are considering at this time.

	my(@votelist)=@{$ballot->{'rankings'}};
	    
	foreach $tier (@votelist) {	  # For each preference listed...
            # 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 number:
    $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 by
                                # 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 be
    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 of
    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 business,
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--