A few days ago, a redditor asked the people of /r/TheWire to rank the five seasons of the HBO television show “The Wire”, and several people posted their rankings. I wanted to take their individual rankings and uncover one aggregate ranking that captured the overall preferences of the entire group of posters. In other words, I wanted to implement a preferential voting scheme.

I was aware of Arrow’s theorem, which says that no voting scheme can satisfy a certain small set of reasonable criteria when voters are ranking three or more alternatives. However, I was also aware that a number of countries employ preferential voting systems. So, I didn’t give up, and I searched for a preferential voting system that would fit the bill.

I found one that worked: the ranked pairs voting scheme. In the ranked pairs voting system, you first count all the times that voters ranked Alternative X ahead of Alternative Y, for all pairs of alternatives (X, Y). If voters ranked Alternative X ahead of Alternative Y more often, then Alternative X is a *majority* over Alternative Y.

Next you sort the majorities. For example, say that voters ranked Alternative X ahead of Alternative Y three times and that they ranked Alternative A ahead of Alternative B five times. Then the latter majority comes before the former majority in the sort.

But what if the list of majorities creates a cycle? For example, say that we have [(A, B), (B, C), (C, A)]. Then A is a majority over B and B is a majority over C. But C is a majority over A. So, by transitivity, A is a majority over A. But an alternative X can be a majority over an alternative Y only if X was ranked ahead of Y, and A can’t be ranked ahead of itself.

So, here’s how you resolve that issue. You treat the list of majorities like a directed acyclic graph where the dag includes a directed edge from X to Y if X is a majority over Y. And you just go down the sorted list of majorities. For each majority, you try to add a corresponding edge to the dag. If adding that edge would produce a cycle, then you don’t add it. If it wouldn’t produce a cycle, then you do add it, and that majority gets locked in to the final list of majorities.

The winner of the election is the source of the dag, i.e., the vertex that doesn’t have any incoming edges. But I didn’t want to know just the winner. I wanted to know the aggregate ranking. So, I sorted the alternatives by the number of outgoing edges that their corresponding vertices have in the dag. The number of outgoing edges of a vertex corresponds to the number of alternatives that an alternative is a majority over.

I collected the data on the night of September 1. I simply scrolled down the list of comments and recorded the rankings that commenters reported. The only complication was that a couple of commenters expressed indifference between some seasons. So, for example, one person wrote, “4 > 1 > 3/2 > 5”. In such a case, I ranked seasons in the order that they were written. So, in this particular case, I placed Season 3 before Season 2.

Then I ran the program, and the result was 4 > 1 > 2 > 3. Season 5 didn’t even make the list.

You can find my program up at my GitHub.

Further references:

https://users.cs.duke.edu/~conitzer/comsocchapter.pdf

http://www.geeksforgeeks.org/detect-cycle-in-a-graph/