How to tabulate ranked voting in C#

[example]

New York City’s recent election used a ranked voting ballot. This example shows how you might find the winner in a ranked voting election.


What Is Ranked Voting?

In ranked voting (aka ranked-choice voting or preferential voting), each voter ranks the candidates into first, second, third, and other choices. To decide the winner, you repeat these steps:

  1. For each voter, find the highest ranked candidate that is still in the running and add one to that candidate’s tally.
  2. If a candidate has more than 50% of the total votes, then that candidate is the winner.
  3. If no candidate has more than 50% of the total votes, you find the candidate(s) with the fewest votes and eliminate them from the running.

You repeat those steps until you find a winner.

Note that you might eliminate multiple candidates in a single round if they have exactly the same smallest number of votes.

It is also possible to end in a tie. This happens if two or more candidates split the vote exactly evenly. For example, if there are 3,000 ballots and three remaining candidates, each of whom has exactly 1,000 votes, then you cannot determine the last place candidate to eliminate.

Both eliminating multiple candidates in a single round and a tie are very unlikely if there are many voters.

Note also that, if there are N candidates, then there can be at most N – 1 rounds. During each round, at least one candidate is eliminated, so after N – 1 rounds there can be at most one candidate remaining. (Often there will be a winner earlier.)

Why?

You can read about the pros and cons of ranked voting on Wikipedia and other places, but here’s one important advantage.

Ranked voting avoids penalizing similar candidates who split the vote. For example, suppose an election has four candidates, three of whom (Anderson, Baker, and Campbell) have similar peace-and-harmony platforms and one of whom (Zantos) is very different, running on a conquer-the-world platform. Now suppose 71% of the people prefer the peace-and-harmony platform and the votes come out as: Anderson 24%, Baker 21%, Campbell 26%, and Zantos 29%.

In a plurality voting system where the candidate with the most votes wins, Zantos would win even though 71% of the voters oppose the conquer-the-world platform.

There are several ways you could avoid an outcome where a minority candidate wins. You could have a runoff election between the two most popular candidates. In this example, Campbell would win. Note that this might not be the “best” outcome either if all of the Baker voters prefer Anderson as their second choice. In that case, a majority might prefer Anderson to Campbell, but at least they have some input in the runoff.

Ranked voting is another strategy for handling this issue. It also has the advantage that you can perform the rounds without going back to the ballot box, which takes extra time and effort.

The Ballot Class

The example uses the following Ballot class to hold a voter’s choices.

public class Ballot
{
    // Choices holds the candidate numbers in ranked order.
    public int[] Choices;
    public Ballot(int num_candidates)
    {
        Choices = Extensions.RandomArrangement(num_candidates);
    }

    // Find this ballot's top non-disqualified choice.
    public int TopChoice(bool[] disqualified)
    {
        for (int i = 0; i < disqualified.Length; i++)
        {
            int candidate = Choices[i];
            if (!disqualified[candidate]) return candidate;
        }
        return -1;
    }
}

The Choices array holds the indices of the candidates in the voter’s ranking. For example, if the array holds 1, 3, 2, 0, then the voter’s first choice is candidate 1, the second choice is candidate 3, and so forth.

The TopChoice method returns the voter’s top choice given an array showing which candidates have been disqualified in earlier rounds. For example, disqualified[2] is true if candidate number 2 has been eliminated.

This method simply loops through the voter’s choices in rank order. When it finds a candidate that has not been eliminated, it returns that candidate’s index.

The method should not fail to find a candidate, because as you will see the program will not eliminate all of the candidates.

Tabulating Votes

When you click the Tabulate button, the following code executes.

private void btnTabulate_Click(object sender, EventArgs e)
{
    int num_ballots = Ballots.Length;
    int num_candidates = Ballots[0].Choices.Length;
    int needed_to_win = (int)(num_ballots / 2.0 + 1);

    lvwVotes.Columns.Clear();
    lvwVotes.Columns.Add("Round");
    for (int i = 0; i < num_candidates; i++)
    {
        lvwVotes.Columns.Add("Can " + i.ToString());
    }
    lvwVotes.Columns.Add("Notes");
    lvwVotes.Items.Clear();

    // Make an array indicating which
    // candidates have been disqualified.
    bool[] disqualified = Enumerable.Repeat(false, num_candidates).ToArray();

    // Repeat rounds until we have a winner.
    // Note that there can be at most num_candidates - 1 rounds,
    // and round num_candidates - 1 could end in an exact tie.
    for (int round_num = 0; round_num < num_candidates - 1; round_num++)
    {
        // Count the votes.
        int[] votes = new int[num_candidates];
        foreach (Ballot ballot in Ballots)
        {
            // Add to this ballot's top candidate's total.
            votes[ballot.TopChoice(disqualified)]++;
        }

        // Display the totals.
        ListViewItem item = new ListViewItem(round_num.ToString());
        for (int candidate = 0; candidate < num_candidates; candidate++)
        {
            if (disqualified[candidate])
                item.SubItems.Add("---");
            else
                item.SubItems.Add(votes[candidate].ToString());
        }
        lvwVotes.Items.Add(item);

        // See if there is a winner.
        int winner = -1;
        for (int candidate = 0; candidate < num_candidates; candidate++)
        {
            if (votes[candidate] >= needed_to_win)
            {
                winner = candidate;
                break;
            }
        }

        if (winner >= 0)
        {
            // We have as winner!
            item.SubItems.Add(winner.ToString() + " wins!");
            break;
        }

        // Find the smallest vote total(s).
        string notes = "";
        int max_votes = int.MinValue;
        int min_votes = int.MaxValue;
        for (int i = 0; i < num_candidates; i++)
        {
            if (!disqualified[i])
            {
                if (votes[i] < min_votes) min_votes = votes[i];
                if (votes[i] > max_votes) max_votes = votes[i];
            }
        }

        if (min_votes == max_votes)
        {
            // We have a tie.
            item.SubItems.Add("Tie");
            break;
        }

        // Disqualify last place candidate(s).
        for (int i = 0; i < num_candidates; i++)
        {
            if ((!disqualified[i]) && (votes[i] == min_votes))
            {
                disqualified[i] = true;
                notes += ", x" + i.ToString();
            }
        }
        notes = notes.Substring(2);

        item.SubItems.Add(notes);
    }
}

The code gets the number of ballots and candidates, and calculates the number of votes needed to win. That number is half of the total votes plus one.

The program then clears the lvwVotes ListView control and creates columns in it to represent the candidates and a final Notes column.

The code then initializes the disqualified array so no candidate is disqualified. It then enters a loop to perform the voting rounds.

During each round, the program loops through the Ballot objects, gets their preferred candidate, and increments that candidate’s count.

Next the code loops through the candidates and displays their counts in the lvwVotes ListView control. If a candidate has been eliminated, the program displays —.

The code then determines whether there has been a winner by checking whether any candidate received the needed number of votes. If there is a winner, the program displays the winning candidate number and exits the rounds loop.

If there is no winner, the code loops through the candidates and finds the largest and smallest numbers of votes that any candidate received.

If the largest and smallest numbers of votes are the same, then all of the remaining candidates have the same number of votes, so the vote ends in a tie. The program reports that and exits the rounds loop.

If we don’t have a tie, the program loops through the candidates again and disqualifies any that have the smallest number of votes. If there are many votes, then this will probably only be one candidate. If multiple candidates have exactly the same smallest number of votes, then they will be removed together.

The program displays a brief message indicating the candidates that it removed.

Now the program continues its main loop to perform the next round of voting.

Eventually the program will either find a winner with 50% + 1 votes, or all of the remaining candidates will have the same number of votes and we end in a tie. I’m not sure how you would handle that. A runoff election among the tied candidates would probably break things loose again (because some voters will probably change their voting strategy given another chance) so the algorithm could continue.

Conclusion

Ranked voting may have some problems with special cases (like ties) and voters may be reluctant to try a new system, but it does have some advantages. For example, it avoids a separate runoff election and prevents an unpopular candidate from winning when other candidates split the vote. Of course the electoral college is a whole different issue.

As always, download the example to see additional details such as how the user interface works and how the program generates random ballots. Note that the ListView control cannot handle huge numbers of items, so don’t try to display 1 million ballots. If you want to experiment with huge numbers of voters, modify the code so it does not display them all.


Download Example   Follow me on Twitter   RSS feed   Donate




About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in algorithms and tagged , , , , , , . Bookmark the permalink.