Voting systems can become very complex, and some of them are easy to manipulate by tactical voting. Joe takes a couple of voting systems and wonders how you would implement them in SQL. He's even more curious as to how you, the reader, would do so.

Right now we in the States are being bombarded with Republican Presidential candidates debating on television, immediately followed by public opinion polls. You do not known how many candidates are in the game from week to week, nor who is the front runner unless you follow the debates every day.

This kind of voting appears in a lot of business situations, even though we do not usually think of it as a ballot. Any purchase choice among several products is a vote, pushing the buttons on your television remote is a vote for one program out of the gazillion channels on your satellite dish and so many other decisions.

The voting problem has been around for centuries, but the modern answer was given by Economist Kenneth Arrow. He won the Nobel Memorial Prize in Economics and National Medal in Science (2004), so we know he is smart. His theorem is known as “Arrow’s Impossibility Theorem” in the literature. He started with some simple assumptions about rules we want in a “fair election system” and then he shows that things don't work like you think they should. Given at least two voters and at least three candidates, it is impossible to aggregate individual preferences without violating some of the desirable conditions.

The desired conditions are:

1. Every voter has a strictly monotonic ordered preference function. In symbols, P(c1, c2) returns the best-liked candidate of the pair. Again, in symbols, P(c1, c2) Ù P(c1, c2) Þ P(c1, c3). Or in English there is no “scissors, paper, stone” circular rankings or ties.
2. Every voter votes his conscience and locks in his preference function. That means given candidates X and Y, and a preference of X over Y, then the voter cast his vote this way in every ballot. There is no political game playing allowed.
3. There is no dictator. No one voter holds enough votes to control the outcome by himself. You will also see this expressed as “one man, one vote”, but this condition can be weaker than that. For example, in a stock holder's meeting, one shareholder can have more votes (shares) than another.
4. Majority rules. If every voter prefers candidate X over candidate Y, then the electorate prefers X over Y.

This seems to be a reasonable voting system. We can see that if there are two candidates, then we will get either a tie or a winner; let's ignore ties for the rest of this article. The problems start with three candidates and three voters. Here is a look-up table of the preference functions.

If you look at the table for a bit, you will see a “scissors, paper stone” relationship in this. There is no clear mandate from the electorate. This is called the Condorcet Paradox, named after the Marquis de Condorcet (1743 – 1794) who first wrote about it. It is easier to see with an election made up of pair-wise ballots.

If we hold an election between candidates c1 and c2, the winner is c1 by two votes from voters A and C. We now face off with c1 and c3 on a second ballot. The winner is c3.

Now let's have another election. But this time the first ballot pairs c1 and c3, with an come for c3. The second ballot pairs the winner, c3 against c2. The winner is c2.

Finally, let's hold a third election. The first ballot pairs c2 and c3 to get a victory for c3. The second ballot pairs the winner, c3 against c1. The winner is c1.

As a practical matter, a voter could have falsely cast a ballot for a weaker candidate in the first ballot so that his favorite would win in the final ballot. If that is not clear, look at the first election that starts with c1 and c2. Voter B falsely cast his first vote for c2, who wins. The second ballot of the election is now between c2 and c3 so the winner is c2, not the original winner c3. This is why we made rule #2 about voting your conscience.

Voting Systems

Let's consider a few different voting systems. We will give examples from a nine member electorate and a four candidate slate.

Plurality Voting

The winner is a simple Plurality Voting system is the candidate that got the most votes. Not a majority, mind you. So if one candidate has a small but loyal voter bloc, the most unpopular candidate will win.

Hare Voting

This is a “last man standing” system in which least popular candidate is removed from the next ballot until there is a winner. The two places this is used in the real world are television reality show where we vote a contestant “off the island” each week and the ballot for the Science Fiction Hugo awards.

Borda Counts

John Claude de Borda was another French mathematician who was interested in voting system. His approach was to have voters assign a number of votes to each candidate and total them. Even if there was no clear winner, the candidate with the best total of votes would be the winner. The weights assigned start at zero for the least liked candidate and increment to (n-1) votes for your favorite.

The names of the voters are not important; we really care about the number of votes that each preference function has in a given election.

Examples

We are looking at blocs of votes. Now look at a four way race with a total of nine votes in play:

If you use a plurality vote, sum up the First place column. The winner is Candidate c1 who does not have a majority, but holds a large bloc vote.

The Hare system gives us Candidate c3. Here is how each ballot works:

Now let's do a Borda vote on the same electorate. The winner is Candidate c2, 15 points. It is easier to arrange the array a little differently. Here is the vote totals.

If you arrange the pair-wise votes in the sequence c1, c2, c3, c4 the winner is c4

SQL and Voting Experiments

Now that I have destroyed any hope of having a provably fair voting system, we get to write code. Let's start with tables for voters and for candidates, but not worry too much about the details since their existence is all we need for holding an election.

The preference function is a relationship, so it gets its own table.

Now we need queries and views for the various voting methods. It would also be nice to have some data with more than two candidates. Let's try a simple plurality vote to get things started

This will give us ties. How do we want to handle them? Skipping that question, let's write a simple function to do pair-wise ballots.

There are other voting systems and you might want to research them. I happen to like the Russian system where you vote against candidates, not for them. Yes, it is possible for any or all candidate to go negative.

I used to favor adding “None of the above”, but then I realized that the government printing office would put this option on the first line of the ballots.

Homework

Now it is time for homework assignments:

1. Write a Borda voting procedure.
2. Write a Hare voting procedure.

The best answer gets a copy of the Fourth edition of SQL FOR SMARTIES and a $100 Amazon Voucher. Start your SQL engines, Gentlemen!

The best answer will be given a prize of a $100 Amazon voucher. A month after the challenge is sent out, the judge's decision and comments will be sent out in the newsletter, and published on the site.

Joe Celko will judge the answers to this puzzle. Your answer should :
   1) Solve the problem -- Duh!
   2) Avoid proprietary features in SQL Server that will not port or be good across
        all releases, present and future.
   3) Be clever but not obscure.
   4) Explain how you got your answer.