Condorcet ranking and Rcpp

Published by on March 13, 2014 | 9 Responses

Preferential ballot

I had the opportunity recently to be asked to join a committee which had to select candidates for an upcoming election. In the candidate selection phase, the members of the committee use preferential voting to rank the candidates. Prior to the meeting, I did some research on preferential voting systems. I found two main classes of methods used to determine winners-those based on some form of Borda count and those based on some form of Condorcet method.

In previous years, this committee selected the order of the candidates purely on an average rank basis, which is functionally equivalent to a Borda count (although not a modified Borda count). Being informed that I was going to be the tabulator and calculator, I decided that this year I also wanted to use a Condorcet method and compare it with the average rank. I decided that my Condorcet method was going to take the following path:

  1. Calculate if there is a pure Condorcet method
  2. If there is a cycle (no Condorcet winner) use the Schulze method
  3. If there is no unique member of the Schwartz set (the Schulze winner) then select one of a number of tiebreakers

I will gloss over the embarrassing details of how I missed an edge case while checking for stopping conditions and ended up in an infinite while loop, and focus on how I used Rcpp to greatly speed up the process. Condorcet methods require making a pairwise comparison between every candidate. This is slow—\mathcal{O}(n^2). The Schulze method has a rather simple implementation , but it is even slower—\mathcal{O}(n^3).

Here is a sample ballot:

Here is some simple code to calculate the average rank of the candidates:

The above ballot would result in the following ranking:

Here is some (simplified) code to calculate Condorcet and Schulze winners:

The pairwise matrix would be:

The beatpath matrix for rank 1 (all ballots) would be:

and just for completeness, the full Condorcet ranking (selecting a winner, removing that entry from the ballot, and repeating on the smaller set) would be:

When profiling this code, 81% of the time was spent in the Schulze algorithm, another 12% was spent in the PairCount algorithm, and the remaining 7% was spent on everything else (the actual ranking had multiple steps to handle cases when there was no Schulze winner). To speed up the procedure, I ported the Schulze and PairCount functions to C++ using Rcpp. Below is the C++ code:

First, we need to check that the functions return the same values:

Now let's compare the functions' speed:

The PairCount function is over 25 times faster in C++ and the Schulze function is over 120 times as fast! Moreover, the PairCount algorithm reads more logically in C++, as the way R handles vectors and matrices, when subtracting the current rank, the resulting matrix ended up transposed with the candidates across the columns.

So with easy-to-read code that results in speed gains of multiple orders of magnitude, what's not to like?!

9 Responses

  1. Leite, mel e abelh…digo, biscoito | Nepom - Núcleo de Estudos de Política Monetária
    Leite, mel e abelh…digo, biscoito | Nepom - Núcleo de Estudos de Política Monetária March 13, 2014 at 6:24 PM |

    […] pode ser feita neste programa super-flexível? Pois é. Vejam, portanto, esta aplicação da famosa regra de Condorcet. Não sabe do que se trata? Seja esperto: Wikipedia em língua […]

  2. anspiess
    anspiess March 14, 2014 at 4:27 AM |

    Great post, I love the Rcpp implementation, one can learn a lot from these! Do you think that a combination of ‘outer’, ‘pmax’ and ‘ifelse’ might make some of your loops obsolete and vectorizable?
    Cheers, Andrej

    1. Avraham
      Avraham March 14, 2014 at 10:18 AM |

      Thanks, anspiess! I’m not sure these functions are more easily vectorizable in R than what I’ve already done. For example, in PairCount, we have to count the number of times Candidate “X” had more pairwise wins than Candidate “Y” for all combinations of X and Y, and that is not a symmetric function, so the simplest way of doing that requires stepping through each cell. I’ve already used R’s overloading of subtraction to subtract vectors from matrix rows. I am not sure how to create m sets of mxn matrices, each one reflecting the net wins of the candidate, outside of a for loop stepping through the candidate sets. As for the Schulze routine, perhaps if I understood the Floyd–Warshall algorithm better, I’d be able to vectorize it in R. However, I’m not sure that is easily done as it needs to compare the “shortest found to date” with the current edge as it steps through all edges. If you come up with any ideas, I’d love to see them!

      1. anspiess
        anspiess March 15, 2014 at 6:47 AM |

        What I immediately spot in ‘PairCount’ is that you can take t(Votes) out of the loop because it is static and define tVotes <- t(Votes) beforehand and Pref_Cur_Cand <- tVotes – CandRank in the loop so you don't transpose NumCandidates times.
        Cheers,
        Andrej

        1. Avraham
          Avraham March 15, 2014 at 10:38 PM |

          Great point; looks like I’ll need to do a follow up post one of these days.

  3. Seth
    Seth March 14, 2014 at 6:49 AM |

    Awesome! I love alternate voting systems (big fan of approval voting).

    Just out of curiosity did you try using the compiler package? I’d be curious to see how the timing compares.
    PairCount_cmp<-cmpfun(PairCount)
    Schulze_cmp<-cmpfun(Schulze)

    1. Avraham
      Avraham March 14, 2014 at 10:35 AM |

      Thanks, Seth! I don’t know if the formatting will work in replys, but here is your answer. It’s on a different computer, so the actual timing won’t be the same, but the relative timings should still be accurate.

      So while compiling the function shows a significant 40% increase in the paircount routine and a stunning 215% increase in the Schulze routine, that pales in comparison to the 2670% and 9870% speed increase moving to C++. In the actual committee meetings, we had ballots with over 25 people, so the speed gains are even more dramatic as the algorithm is O(n³)!

  4. Erik
    Erik March 16, 2014 at 3:16 PM |

    Very cool, I wrote an R package based on ranking data (available here: https://github.com/Errrriikkkk/RMallow), and have been meaning to port some the necessarily-iterative computations to C++. If I get to that, I may request/modify your code for pair_count.

    Also, for comparison of results (my package is slower and uses a different algorithm, so not worth the speed benchmark)

    datas <- t(BallotMatrix[, 2:ncol(BallotMatrix)])
    dimnames(datas)[[2]] <- as.character(BallotMatrix[,1])
    rnks <- ranking$new(datas)
    m.1 <- Mallows(rnks, G = 1)
    m.1
    Mallows model with modes:
    Modes:
    [1] "Albert, Charles, Edward, Bruce, David"

    Thetas:
    [,1] [,2] [,3] [,4]
    [1,] 0.4462629 0.4462629 0.4462629 0.4462629

    Proportions:
    1

  5. Alfred Beit
    Alfred Beit March 7, 2017 at 7:38 AM |

    Thanks for the great post, Avraham. We used the Schulze method practically on a competition (with an Excel spreadsheet). Reading this post in the rcpp gallery helped understanding the mechanics of the method.

    I am trying to currently focus on tie-breaking (of winners) explained in section 5 of the original Schulze paper and this seems more complicated than the basics of the method.
    Regarding your post, I am having two questions:

    1) Have you thought of implementing “margins” as explained in http://m-schulze.9mail.de/schulze1.pdf

    2) Have you thought of possible caveats of sequential dropping (your while loop, as I understand it). Basically, given N candidates, we calculate (using Condorcet and/or Schulze scheme) a winner. Then we drop the winner and compute the next winner from N-1 candidates. We proceed till there is one member left.
    I have tried to find clear indications of this procedure in the 1st Schulze paper but couldn’t. Would you have any comment on this?

    Thanks.

    Alfred

Comments are closed.