Top Level Namespace

Instance Method Summary collapse

Instance Method Details

#baldwin(votes) ⇒ Object 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
# 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) ⇒ Object 



1
2
3
4
5
6
7
8
9
10
 
# 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) ⇒ Object 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
# 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) ⇒ Object 



23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
# 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) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# 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) ⇒ Object 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
# 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) ⇒ Object 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
# 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) ⇒ Object 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# 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) ⇒ Object 



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
# 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) ⇒ Object 



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# 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) ⇒ Object 



19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# 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) ⇒ Object 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
# 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) ⇒ Object 



63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
# 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