Voting Methods and the DOS Voting Program

The DOS Voting Program

Just to show my students the power of the web in finding course related materials, I did a search with AltaVista on the string "voting methods" on the first day of class of semester 97S. It returned about 100 hits, and the first one had the title bar "Voting Methods", a link in the University of Arizona at Tucson Math Archives, which contains lots of math education goodies.

[Downloading a single zipped file, I unzipped it with pkunzip and ran the "runme" bat file which starts it. There was no documentation and the online help did not indicate how to enter ballots, but faking it, I finally figured it out. No documentation showed up in a search of the site for the string "voting" but a page did finally come up somewhere referring to the current textbook of our course: "Excursions in Modern Mathematics, 2nd Edition" by Peter Tannenbaum and Robert Arnold. What a coincidence. [I had sent an email to the authors requesting their voting program with no response until weeks later---they were busy!]. The ballot files have names like "TAN13EA.VOT" which eventually rings a bell: TAN as in TANnenbaum. But it took the course coordinator Tom Bartlow to decode the number/letter information: the first number is the page number in the first edition (!) and the second is the Example or Exercise number that occurs on that page, while the final A or B refers to two votes associated with the same problem. Now a Third Edition exists, and the name system is again shuffled! The program turns out to have been written by David Lovelock, a name I already recognized from his research work in general relativity, my own field of research.]

How to use the voting program

So on the student networks, at the DOS prompt (in a DOS window if Win95), find the depart/math/mat1220 directory tree on the VOL1 disk (drive letter varies, starting from F:, H:,...) and go into the examples/votpgrm subdirectory, and type the bat program name runme (followed by the enter key!) and the program starts. Respond with 2 <enter> for color monitor and you are in. [Ask a consultant or friend for DOS help if this is not obvious to follow. You exit the DOS program with the ESCape key which asks if you really want to exit or not. Hit the ENTER key to exit.]

run the DOS program:
on the default drive from the same subdirectory (to access its related files).

You can get some initial help in using the arrow keys and enter key to access the menus and options when you enter the program at this point. Standard DOS stuff. The escape key backs you out of the menus and the program itself. You can also use the mouse to select options.

Ballot operations

You toggle over to "ballot operations" with the right arrow key and bring down the menu with the enter key to enter a new set of ballots. The ESCape key backs you out of menus and finally out of the program. First you enter the number of choices in the election, for example, 4 for an election in which there are 4 choices A, B, C, D. The uppercase letters of the alphabet starting at the beginning are used to label the choices. A single ballot consists of a string like ABCD, or BCDA. The number of votes for this ordering of the candidates (a ballot) is asked before entering the actual ballot, if multiple votes for that ballot occur. The menu choice "enter multiple ballots" is used for entering more than one ballot at a time. And "enter one ballot" for a single ballot. [One drawback of this program is that the choices have to be the first consecutive N letters A,B,C,... of the alphabet, for N choices, so if you eliminate one candidate, you have to rename them to use this program, or put that candidate at the end of the ballot---see below.]

File operations

Once the ballot list has been entered, one can save it as a file in the menu "file operations". The first menu "voting options" then enables you to calculate the result of the vote using the 4 simplest methods.

You can also load the vote data files from that subdirectory using the "file operations" menu. You just select it from the filelist which pops up.

This is a lot simpler if someone shows you how to do this, but it is not difficult at all.

Decoding the filenames of preloaded ballot files (Third Edition)

All the ".VOT" files refer to the examples and exercises of the first chapter of the textbook. The file naming scheme is as follows TA3E1.VOT: TA3 for Tannenbaum and Arnold 3rd edition, E1 for example 1, or TA3X01.VOT: TA3 for Tannenbaum and Arnold 3rd edition, X01 for exercise 1 (the zero helps the directory listing order these correctly since there are many double digit problem numbers).

Example 1. The first vote on the MAS election. Interesting since it has 4 candidates and 4 different outcomes by the 4 voting methods discussed here. Useful as an example for the comparing the various fairness criteria.
Example 2. Plurality Method violates Condorcet criterion.
Example 3. Borda Count Method violates majority and Condorcet criteria.
Example 4. Plurality-with-Elimination Method (no majority candidate).
Example 5. Plurality-with-Elimination Method (majority candidate). [ rename WXYZ to ABCD to use this program]
Example 6A,B. Plurality with Elimination Method violates the monoticity condition. [A): C wins. A)->B): Switch ACB to CAB. B): B wins]
Example 7A,B. Pairwise Comparison Method violates the Independence of Irrelevant Alternatives Criterion. [A): A wins. A)->B): Drop C, recount. B): B wins. (rename ABDE to ABCD to use this program) ; one does not need to reevaluate from scratch here though, just look at the list of who beats or ties who and see what happens when you cross off all pair matches containing C]
Example 8. Pairwise Comparison Method tie vote [rename HPD to ABC to use this program]
Example 9. Recursive Plurality Method used on example 1. See explanation below. Round 2: remove 1st place Plurality winning candidate A from example 1 (put at end of ballot to continue using same remaining letters). Round 3: remove 2nd place Plurality winning candidate B (put next to last on ballot to continue using same remaining letters).
Example 10. Recursive Plurality-with-Elimination Method used on example 1. Round 2: remove 1st place Plurality-with-Elimination winning candidate D from example 1, no renaming necessary. (put D at end of ballot.) Round 3: remove 2nd place Plurality-with-Elimination winning candidate C (put next to last on ballot).
Old Example 5A,B replaced by 7A,B. Pairwise Comparison Method violates the Independence of Irrelevant Alternatives Criterion. [A): A wins. A)->B): Drop B C D, recount. B): E wins. (rename AE to AB to use the program)]
Exercise 1.
Exercises 3-6.

This program could stand some improvement but hey, we are lucky someone took the time to make it for us at all, right?

Recursive Ranking: Trick to Continue Using the Program without Renaming Letters

The voting program does not have a recursive ranking option. But we can fake it in the following way. After determining the winner in the first vote, we put that candidate last on all ballots (since it will then not affect the ranking of the remaining candidates: convince yourself that this is true!) so that we can still use the same letters without translating everything into a vote with one less candidate and a renaming of all candidates! We put the winner last so that it will not affect the outcome of the remaining votegetters at the next round. After each iteration we put the next candidate to the left of the previous winner (we could choose to put the successive winners to the right, as long as we are consistent: we ignore these candidates in the following rounds). Is that clear?

Preference Ballot Voting Method Notes

Summary of Preference Voting Methods and Fairness Criteria

We start with a raw vote, i.e., a list a ballots, each containing a preference ranking of the candidates. We then talley (?) the ballots to form a preference schedule which lists in table form the distinct preference rankings which occurred (in the columns, most liked to least liked from top to bottom: rows correspond to preference choices) ordered from left to right by the number of votes they received (decreasing from left to right).

The first analysis we can then do is to make a plurality count table, with the rows labeled by preference choice as in the preference schedule, and the columns by the candidates, with the entries giving the vote talley for each preference rank (first choice, second choice, etc). The first row gives the plurality method results for the outcome, while the last row gives the corresponding results for the "anti-outcome", which is good to keep in mind when a candidate wins both, especially with the larger vote count in the losing position, as noted in the example 2!

We can then apply the remaining 3 voting methods, to determine the corresponding outcomes. We can also check if the given vote with a particular voting method violates any of the four "fairness criteria":

Fairness Criteria:

Majority Criterion
Any candidate receiving a majority of 1st choice votes should win.
Condorcet Criterion
Any candidate who beats all others in pairwise comparisons should win.
Monotonicity Criterion
If a candidate wins an election, and in a re-election votes change only favorable to that candidate and no other, the candidate should still win again.
Independence of Irrelevant Alternatives Criterion
If a candidate wins an election, and some candidates are eliminated and a recount occurs, the candidate should still win again.

Arrow's Impossibility Theorem states that when choosing among 3 or more candidates, satisfying all the fairness criteria is a mathematical impossibility (not in a single concrete election where no violations may occur, but in every possible election). There is no ideal voting method.

Preference Voting Methods:

The four preference voting methods are (neglecting problems with ties):

Plurality method
The largest vote getter in the first choice category wins.
[satisfies Maj.C, violates C.C.]
Borda count method
All votes in the preference schedule are weighted by (N-m) points, where N is the number of choices, and m is the choice rank (i.e., last place gets 1 pt, next to last 2pts, and so on until first place gets N pts) . Then a weighted sum of all the vote counts received by a candidate in the preference schedule is evaluated. The largest such outcome wins. [All the point weights can be shifted down by 1pt without changing the ranking: why?]
[violates Maj.C., C.C., I.I.A.C.]
Plurality method with elimination
If a candidate wins a majority of 1st choice votes, that candidate is the winner. Otherwise the least vote getter (getters, if a tie) in the first choice category is eliminated. The preference schedule is then collapsed and a recount occurs. This precess is iterated until only 2 candidates are left. The largest votegetter wins (necessarily a majority at this point).
[satisfies Maj.C., violates C.C., Mon.C., I.I.A.C.]
Pairwise comparisons
All pairs of candidates are listed. For each pair, the preference schedule is collapsed by ignoring all other candidates. The pair winner is the largest vote getter. The candidate with the most number of wins, wins the election. If 1 pt is assigned to each pairwise win (split by two candidates in a tie), a number outcome is obtained. The largest number wins (most number of wins).
[satisfies Maj.C., C.C., Mon.C., violates I.I.A.C., often leads to tie.]

[Each voting method satisfies the criteria it does not violate, as noted above. You should be able to explain why each satisfies or violates a given criterion.]

Each of these methods can be used as an extended ranking procedure for all the candidates rather than just picking a winner, in a fairly obvious way for each method. [not completely obvious for Plurality with Eliminations, where the sequence of eliminated candidates provides a reverse ranking]. A recursive ranking procedure for each can also be used, eliminating the winner at each round and recounting to determine the winner among the remaining candidates, repeating until only one candidate remains (the recursive last placeholder).