9 Responses

  1. Leite, mel e abelh…digo, biscoito | Nepom - Núcleo de Estudos de Política Monetária

    […] 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.