class Object
Public Instance Methods
baldwin(votes)
click to toggle source
# File lib/systems/baldwin.rb, line 1 def baldwin votes votes, options = normalize votes while true # calculate scores using Borda counts scores = borda_counts votes, options # group and sort the options by score groups = options.group_by {|option| scores[option]} sorted = groups.sort_by {|score, tied| -score} # puts # sorted.each {|score, tied| puts "#{score.to_f} #{tied}"} # find the options with the lowest score leasts = sorted.last[1] # if all remaining options are tied, they are the winners return leasts if leasts.size == options.size # remove the options with the lowest score votes.collect! {|count, ranking| [count, ranking.collect {|tied| tied - leasts}] } options -= leasts end end
borda(votes)
click to toggle source
# File lib/systems/borda.rb, line 1 def borda votes votes, options = normalize votes # calculate scores using Borda counts scores = borda_counts votes, options # sort the results and return the winner/s groups = options.group_by {|option| scores[option]} sorted = groups.sort_by {|score, tied| -score} # sorted.each {|score, tied| puts "#{score.to_f} #{tied}"} sorted.first[1] end
borda_counts(votes, options)
click to toggle source
# File lib/util.rb, line 1 def borda_counts votes, options # calculate the Borda count of each option scores = Hash.new 0 votes.each {|count, ranking| # add to the scores remaining = options.size ranking.each_with_index {|tied, i| # each tied option gets the average of their possible ranks average = remaining - (tied.size - 1) / 2r tied.each {|option| scores[option] += count * average} remaining -= tied.size } raise unless remaining == 0 # sanity check } scores end
bucklin(votes)
click to toggle source
# File lib/systems/bucklin.rb, line 23 def bucklin votes votes, options = normalize votes sum_of_counts = votes.transpose[0].inject 0, :+ (1..options.size).each {|places| # count the votes up to places scores = scores_for_places votes, places # find the winners groups = options.group_by {|option| scores[option]} # p groups best = groups.max_by {|score, tied| score} # if the best group has a majority, it is the winner return best[1] if best[0] > sum_of_counts / 2r } raise # should never get here, by the pigeonhole principle end
convert_legrand(legrand)
click to toggle source
# File lib/util.rb, line 18 def convert_legrand legrand # format from https://www.cse.wustl.edu/~legrand/rbvote/calc.html legrand.each_line.collect {|line| comment = line.index '#' line = line[0...comment] if comment fields = line.strip.split ':' case fields.size when 0 then next when 1 # no count provided, so default to 1 count = 1 ranks = fields[0] when 2 count = fields[0].to_i ranks = fields[1] else raise 'only one colon allowed per line' end groups = ranks.split '>' ranking = groups.collect {|group| group.split '='} [count, ranking] }.compact end
coombs(votes)
click to toggle source
# File lib/systems/coombs.rb, line 1 def coombs votes # this implements the version of Coombs in which elimination proceeds # regardless of whether a candidate is ranked first by a majority of voters votes, remaining = normalize votes while true votes.each {|count, ranking| ranking.delete []} # p votes # see how many times each option was ranked last scores = Hash.new 0 votes.each {|count, ranking| tied = ranking.last tied.each {|option| scores[option] += count.quo tied.size} } # find the options which were ranked last the most groups = remaining.group_by {|option| scores[option]} # p groups mosts = groups.max_by {|score, tied| score}[1] # if all remaining options are tied, they are the winners return mosts if mosts.size == remaining.size # remove options which were ranked last the most votes.collect! {|count, ranking| [count, ranking.collect {|tied| tied - mosts}] } remaining -= mosts end end
copeland(votes)
click to toggle source
# File lib/systems/copeland.rb, line 1 def copeland votes # implements standard Copeland (pairwise victories minus pairwise defeats) votes, options = normalize votes scores = winning_votes votes # how many times each option beat each other option # puts "scores: #{scores}" # calculate pairwise victories and pairwise defeats victories, defeats = {}, {} options.each {|option1| victories[option1] = options.select {|option2| scores[[option1, option2]] > scores[[option2, option1]] } defeats[option1] = options.select {|option2| scores[[option1, option2]] < scores[[option2, option1]] } } # puts "victories: #{victories}" # puts "defeats: #{defeats}" # calculate results groups = options.group_by {|option| victories[option].size - defeats[option].size } sorted = groups.sort_by {|margin, tied| -margin} # puts 'results:' # sorted.each {|margin, tied| puts " #{tied} --> #{margin}"} sorted.first[1] end
instant_runoff(votes)
click to toggle source
# File lib/systems/instant_runoff.rb, line 1 def instant_runoff votes votes, remaining = normalize votes while true votes.each {|count, ranking| ranking.delete []} # p votes # see how many times each option was ranked first scores = Hash.new 0 votes.each {|count, ranking| tied = ranking.first tied.each {|option| scores[option] += count.quo tied.size} } # find the options which were ranked first the least groups = remaining.group_by {|option| scores[option]} # p groups leasts = groups.min_by {|score, tied| score}[1] # if all remaining options are tied, they are the winners return leasts if leasts.size == remaining.size # remove options which were ranked first the least votes.collect! {|count, ranking| [count, ranking.collect {|tied| tied - leasts}] } remaining -= leasts end end
normalize(votes)
click to toggle source
# File lib/util.rb, line 41 def normalize votes # normalize votes and return along with all options that appeared votes = convert_legrand votes if votes.is_a? String raise 'votes must contain at least one option' if votes.empty? raise 'each vote must have the form [count, ranking]' if votes.find {|vote| vote.size != 2} options = votes.transpose[1].flatten.uniq votes = votes.collect {|count, ranking| raise 'ranking must be an array' unless ranking.is_a? Array # treat missing options as tied for last place missing = options - ranking.flatten ranking = ranking + [missing] unless missing.empty? # make sure no options appear twice raise 'duplicate option in ranking' unless ranking.flatten.size == options.size # normalize single ranks as singleton ties ranking = ranking.collect {|x| x.is_a?(Array) ? x : [x]} # remove empty ties ranking = ranking.select {|tied| not tied.empty?} [count, ranking] } [votes, options] end
ranked_pairs(votes)
click to toggle source
# File lib/systems/ranked_pairs.rb, line 48 def ranked_pairs votes votes, options = normalize votes scores = winning_votes votes # how many times each option beat each other option return options if scores.empty? # every vote ranked all the options the same # group and sort the pairs by winning votes groups = scores.keys.group_by {|key| scores[key]} sorted = groups.sort_by {|winning_votes, pairs| -winning_votes} # puts # p sorted sorted_pairs = sorted.transpose[1] # puts # puts 'sorted pairs:' # sorted_pairs.each {|tied| p tied} # puts # puts 'calculating results...' results = results_from_pairs sorted_pairs results.first.to_a end
results_from_pairs(sorted_pairs)
click to toggle source
# File lib/systems/ranked_pairs.rb, line 19 def results_from_pairs sorted_pairs graph = RGL::DirectedAdjacencyGraph.new sorted_pairs.each {|tied| # puts # puts "graph is: " # puts graph # puts "tied is #{tied}" keep = tied.select {|winner, loser| # keep if there is no path from loser to winner, meaning that this edge # will not create a cycle next true if not graph.has_vertex? loser not graph.bfs_iterator(loser).include? winner } # puts "keep is #{keep}" keep.each {|winner, loser| graph.add_edge winner, loser} } # puts "final graph is: " # puts graph # puts condensed = graph.condensation_graph # puts "condensed is " # condensed.edges.each {|edge| p edge.to_a} # puts results = condensed.topsort_iterator.to_a # should be unique # puts "results is " # p results results end
scores_for_places(votes, places)
click to toggle source
# File lib/systems/bucklin.rb, line 1 def scores_for_places votes, places # Add up votes for each option, including 1st-place votes, 2nd-place votes, # and so on up to k-place votes, where k = places. scores = Hash.new 0 votes.each {|count, ranking| remaining = places ranking.each {|tied| if remaining > tied.size # each tied option uses up one "place" tied.each {|option| scores[option] += count} remaining -= tied.size else # not enough remaining "places" to go around, so give each tied option # an equal fraction of what there is tied.each {|option| scores[option] += count * (remaining.quo tied.size)} break end } } scores end
winning_votes(votes)
click to toggle source
# File lib/util.rb, line 63 def winning_votes votes # see how many times each option beat each other option scores = Hash.new 0 votes.each {|count, ranking| (0...ranking.size).each {|i| (i+1...ranking.size).each {|j| ranking[i].each {|option1| ranking[j].each {|option2| scores[[option1, option2]] += count } } } } } scores end