From 60344b51d7e6c505492183b79b96b76216c95072 Mon Sep 17 00:00:00 2001 From: Alexis Darrasse Date: Sat, 11 Mar 2006 21:30:36 +0000 Subject: [PATCH] Added tie-breaking rules and multicandidate elimination of weak candidates before the first round in IRV. Renamed runoff to irv. git-svn-id: svn://rubyforge.org/var/svn/rubyvote/trunk@12 1440c7f4-e209-0410-9a04-881b5eb134a8 --- lib/rubyvote.rb | 2 +- lib/rubyvote/irv.rb | 225 +++++++++++++++++++++++++++ lib/rubyvote/runoff.rb | 88 ----------- test.rb | 32 ++-- test/{runoff_test.rb => irv_test.rb} | 17 +- 5 files changed, 263 insertions(+), 101 deletions(-) create mode 100644 lib/rubyvote/irv.rb delete mode 100644 lib/rubyvote/runoff.rb rename test/{runoff_test.rb => irv_test.rb} (80%) diff --git a/lib/rubyvote.rb b/lib/rubyvote.rb index 1585389..2f11561 100644 --- a/lib/rubyvote.rb +++ b/lib/rubyvote.rb @@ -3,6 +3,6 @@ require File.dirname(__FILE__) + '/rubyvote/election' require File.dirname(__FILE__) + '/rubyvote/condorcet' require File.dirname(__FILE__) + '/rubyvote/positional' -require File.dirname(__FILE__) + '/rubyvote/runoff' +require File.dirname(__FILE__) + '/rubyvote/irv' require File.dirname(__FILE__) + '/rubyvote/range' diff --git a/lib/rubyvote/irv.rb b/lib/rubyvote/irv.rb new file mode 100644 index 0000000..3851738 --- /dev/null +++ b/lib/rubyvote/irv.rb @@ -0,0 +1,225 @@ +class InstantRunoffVote < ElectionVote + def initialize(votes=nil) + @candidates = Array.new + votes.each do |vote| + @candidates = vote.uniq if vote.uniq.length > candidates.length + end + super(votes) + @candidates.each do |candidate| + @votes[candidate] = [0, Hash.new] unless @votes.has_key?(candidate) + end + end + + def result(params={}) + InstantRunoffResult.new(self, params) + end + + protected + def tally_vote(vote) + votecopy = vote.dup + candidate = votecopy.shift + votes[candidate] = [0, Hash.new] unless votes.has_key?(candidate) + votes[candidate][0] += 1 + if votes[candidate][1].has_key?(votecopy) + votes[candidate][1][votecopy] += 1 + else + votes[candidate][1][votecopy] = 1 + end + end + + def verify_vote(vote=nil) + vote.instance_of?( Array ) and + vote == vote.uniq + end +end + +class InstantRunoffLogicVote < InstantRunoffVote + def result(params={}) + InstantRunoffLogicResult.new(self, params) + end +end + +class InstantRunoffFirstRoundVote < InstantRunoffVote + def result(params={}) + InstantRunoffFirstRoundResult.new(self, params) + end +end + +class InstantRunoffAllVote < InstantRunoffVote + def result(params={}) + InstantRunoffAllResult.new(self, params) + end +end + +class InstantRunoffRandomVote < InstantRunoffVote + def result(params={}) + InstantRunoffRandomResult.new(self, params) + end +end + +class InstantRunoffResult < ElectionResult + attr_reader :ranked_candidates + + def initialize(voteobj=nil, params={}) + unless voteobj and voteobj.kind_of?( InstantRunoffVote ) + raise ArgumentError, "You must pass an InstantRunoffVote array.", caller + end + super(voteobj) + + votes = @election.votes.clone + candidates = @election.candidates + votes_sum = votes.inject(0) {|n, value| n + value[1][0]} + @majority = votes_sum/2 + 1 + @ranked_candidates = Array.new() + ranked_candidates = Array.new() + losers = Array.new() + + if params.has_key?('candidate_count') + apply_candidate_count(votes, params['candidate_count']) + end + if params.has_key?('vote_minimum') + apply_vote_minimum(votes, params['vote_minimum']) + end + if params.has_key?('percent_minimum') + apply_vote_minimum(votes, votes_sum * params['percent_minimum']) + end + if params.has_key?('percent_retention') + apply_retention(votes, votes_sum * params['percent_retention']) + end + + begin + ranked_candidates = votes.sort do |a, b| + b[1][0] <=> a[1][0] + end.collect {|i| i[0]} + @winners = ranked_candidates.find_all do |i| + votes[i][0] >= @majority + end + end while not self.winner? and next_round(votes, ranked_candidates) + @ranked_candidates.unshift(*ranked_candidates) + end + +protected + def apply_candidate_count(votes, candidate_count) + if votes.size > candidate_count + losers = votes.sort do |a, b| + b[1][0] <=> a[1][0] + end.collect {|i| i[0]}.last(votes.size - candidate_count) + @ranked_candidates.unshift(losers) unless losers.empty? + losers.each { |loser| remove_candidate(votes, loser) } + end + end + + def apply_vote_minimum(votes, vote_minimum) + losers = votes.find_all do |i| + i[1][0] < vote_minimum + end.collect {|i| i[0]} + if losers.length == votes.size + votes.clear + else + @ranked_candidates.unshift(losers) unless losers.empty? + losers.each { |loser| remove_candidate(votes, loser) } + end + end + + def apply_retention(votes, retention) + losers = votes.sort do |a, b| + b[1][0] <=> a[1][0] + end.collect {|i| i[0]} + partial_sum = 0 + while partial_sum < retention + partial_sum += votes[losers.shift][0] + end + @ranked_candidates.unshift(losers) unless losers.empty? + losers.each { |loser| remove_candidate(votes, loser) } + end + + def next_round(votes, ranked_candidates) + loser = ranked_candidates[-1] + if votes.empty? or votes[loser][0] == votes[ranked_candidates[-2]][0] + false + else + @ranked_candidates.unshift(loser) + remove_candidate(votes, loser) + true + end + end + + def remove_candidate(votes, loser) + votes.each_pair do |candidate, morevotes| + hash = morevotes[1] + hash.each_pair do |vote, count| + hash.delete(vote) + vote.delete(loser) + hash[vote] = count + end + end + votes[loser][1].each_pair do |vote, count| + candidate = vote.shift + votes[candidate][0] += count + if votes[candidate][1].has_key?(vote) + votes[candidate][1][vote] += count + else + votes[candidate][1][vote] = count + end + end + votes.delete(loser) + end +end + +class InstantRunoffLogicResult < InstantRunoffResult + def next_round(votes, ranked_candidates) + losers = ranked_candidates.find_all do |i| + votes[i][0] == votes[ranked_candidates[-1]][0] + end + if losers.inject(0) {|n, loser| n + votes[loser][0]} >= @majority + false + else + @ranked_candidates.unshift(losers) + losers.each do |loser| + remove_candidate(votes, loser) + end + true + end + end +end + +class InstantRunoffFirstRoundResult < InstantRunoffResult + def next_round(votes, ranked_candidates) + losers = ranked_candidates.find_all do |i| + votes[i][0] == votes[ranked_candidates[-1]][0] + end + loser = losers.sort do |a, b| + @election.votes[a][0] <=> @election.votes[b][0] + end.last + @ranked_candidates.unshift(loser) + remove_candidate(votes, loser) + end +end + +class InstantRunoffAllResult < InstantRunoffResult + def next_round(votes, ranked_candidates) + losers = ranked_candidates.find_all do |i| + votes[i][0] == votes[ranked_candidates[-1]][0] + end + if losers.length == ranked_candidates.length + false + else + @ranked_candidates.unshift(losers) + losers.each do |loser| + remove_candidate(votes, loser) + end + true + end + end +end + +class InstantRunoffRandomResult < InstantRunoffResult + def next_round(votes, ranked_candidates) + losers = ranked_candidates.find_all do |i| + votes[i][0] == votes[ranked_candidates[-1]][0] + end + loser = losers[rand(losers.length)] + @ranked_candidates.unshift(loser) + remove_candidate(votes, loser) + end +end diff --git a/lib/rubyvote/runoff.rb b/lib/rubyvote/runoff.rb deleted file mode 100644 index 8a69a4e..0000000 --- a/lib/rubyvote/runoff.rb +++ /dev/null @@ -1,88 +0,0 @@ -class InstantRunoffVote < ElectionVote - def initialize(votes=nil) - @candidates = Array.new - votes.each do |vote| - @candidates = vote.uniq if vote.uniq.length > candidates.length - end - super(votes) - @candidates.each do |candidate| - @votes[candidate] = [0, Hash.new] unless @votes.has_key?(candidate) - end - end - - def result - InstantRunoffResult.new(self) - end - - protected - def tally_vote(vote) - votecopy = vote.dup - candidate = votecopy.shift - votes[candidate] = [0, Hash.new] unless votes.has_key?(candidate) - votes[candidate][0] += 1 - if votes[candidate][1].has_key?(votecopy) - votes[candidate][1][votecopy] += 1 - else - votes[candidate][1][votecopy] = 1 - end - end - - def verify_vote(vote=nil) - vote.instance_of?( Array ) and - vote == vote.uniq - end -end - -class InstantRunoffResult < ElectionResult - attr_reader :ranked_candidates - - def initialize(voteobj=nil) - unless voteobj and voteobj.kind_of?( InstantRunoffVote ) - raise ArgumentError, "You must pass an InstantRunoffVote array.", caller - end - super(voteobj) - - votes = @election.votes.clone - candidates = @election.candidates - majority = votes.inject(0) {|n, value| n + value[1][0]}/2 + 1 - @ranked_candidates = Array.new() - ranked_candidates = Array.new() - - loop do - ranked_candidates = votes.sort do |a, b| - b[1][0] <=> a[1][0] - end.collect {|i| i[0]} - @winners = ranked_candidates.find_all do |i| - votes[i][0] >= majority - end - - loser = ranked_candidates[-1] - break if self.winner? or votes[loser][0] == votes[ranked_candidates[-2]][0] - - @ranked_candidates.unshift(loser) - runoff(votes, loser) - end - @ranked_candidates.unshift(*ranked_candidates) - end - - def runoff(votes, loser) - votes.each_pair do |candidate, morevotes| - hash = morevotes[1] - hash.each_pair do |vote, count| - hash.delete(vote) - vote.delete(loser) - hash[vote] = count - end - end - votes[loser][1].each_pair do |vote, count| - candidate = vote.shift - votes[candidate][0] += count - if votes[candidate][1].has_key?(vote) - votes[candidate][1][vote] += count - else - votes[candidate][1][vote] = count - end - end - votes.delete(loser) - end -end diff --git a/test.rb b/test.rb index e8c03a1..6b0b5c1 100755 --- a/test.rb +++ b/test.rb @@ -126,8 +126,8 @@ def approval_test1 print_winner( ApprovalVote.new(vote_array).result ) end -def runoff_test1 - puts "USING RUNOFF..." +def irv_test1 + puts "USING IRV..." puts "The winner shold be: A" vote_array = Array.new @@ -139,8 +139,8 @@ def runoff_test1 print_winner( InstantRunoffVote.new(vote_array).result ) end -def runoff_test2 - puts "USING RUNOFF..." +def irv_test2 + puts "USING IRV..." puts "The winner shold be: D" vote_array = Array.new @@ -152,8 +152,8 @@ def runoff_test2 print_winner( InstantRunoffVote.new(vote_array).result ) end -def runoff_test3 - puts "USING RUNOFF..." +def irv_test3 + puts "USING IRV..." puts "The winner shold be: C" vote_array = Array.new @@ -180,6 +180,19 @@ def runoff_test3 print_winner( InstantRunoffVote.new(vote_array).result ) end +def irvlogic_test1 + puts "USING IRV LOGIC..." + puts "The winner shold be: B" + + vote_array = Array.new + 42.times {vote_array << "ABCD".split("")} + 26.times {vote_array << "BCDA".split("")} + 15.times {vote_array << "CDBA".split("")} + 15.times {vote_array << "DCBA".split("")} + + print_winner( InstantRunoffLogicVote.new(vote_array).result ) +end + def range_test1 puts "USING RANGE..." puts "The winner shold be: B" @@ -200,7 +213,8 @@ ssd_test3() borda_test1() plurality_test1() approval_test1() -runoff_test1() -runoff_test2() -runoff_test3() +irv_test1() +irv_test2() +irv_test3() +irvlogic_test1() range_test1() diff --git a/test/runoff_test.rb b/test/irv_test.rb similarity index 80% rename from test/runoff_test.rb rename to test/irv_test.rb index d153dd6..640824c 100644 --- a/test/runoff_test.rb +++ b/test/irv_test.rb @@ -6,7 +6,7 @@ require 'election_test_helper' class TestRunoffVote < Test::Unit::TestCase include ElectionTestHelper - def test_runoff + def test_irv vote_array = Array.new 142.times {vote_array << "ABCD".split("")} 26.times {vote_array << "BCDA".split("")} @@ -16,7 +16,7 @@ class TestRunoffVote < Test::Unit::TestCase test_winner( "A", InstantRunoffVote.new(vote_array).result ) end - def test_runoff2 + def test_irv2 vote_array = Array.new 42.times {vote_array << "ABCD".split("")} 26.times {vote_array << "BCDA".split("")} @@ -26,7 +26,7 @@ class TestRunoffVote < Test::Unit::TestCase test_winner( "D", InstantRunoffVote.new(vote_array).result ) end - def test_runoff3 + def test_irv3 vote_array = Array.new 42.times {vote_array << "ABCD".split("")} 26.times {vote_array << "ACBD".split("")} @@ -50,5 +50,16 @@ class TestRunoffVote < Test::Unit::TestCase test_winner( "C", InstantRunoffVote.new(vote_array).result ) end + + def test_irv_logic1 + vote_array = Array.new + 42.times {vote_array << "ABCD".split("")} + 26.times {vote_array << "BCDA".split("")} + 15.times {vote_array << "CDBA".split("")} + 15.times {vote_array << "DCBA".split("")} + + test_winner ( "B", InstantRunoffLogicVote.new(vote_array).result ) + end + ###TODO: test all the other variants end -- 2.39.5