From: Date: Wed, 16 Aug 2006 19:19:42 +0000 (-0400) Subject: Adding the rubyvote library to do the actually election-making. The only X-Git-Url: https://projects.mako.cc/source/selectricity-live/commitdiff_plain/560828ebdd364de4ca09d61764f19215a9e29e59 Adding the rubyvote library to do the actually election-making. The only method supported at the moment is CloneproofSSD. --- diff --git a/lib/rubyvote.rb b/lib/rubyvote.rb new file mode 100644 index 0000000..1585389 --- /dev/null +++ b/lib/rubyvote.rb @@ -0,0 +1,8 @@ +# Extra full path added to fix some require errors on some installations. + +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/range' + diff --git a/lib/rubyvote/condorcet.rb b/lib/rubyvote/condorcet.rb new file mode 100644 index 0000000..616de48 --- /dev/null +++ b/lib/rubyvote/condorcet.rb @@ -0,0 +1,235 @@ +# election library -- a ruby library for elections +# copyright © 2005 MIT Media Lab and Benjamin Mako Hill + +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, but +# WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +# General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +# 02110-1301, USA. + +################################################################# +## ==== condorcet.rb ==== +## +## This file contains Condorcet election methods. Currently this +## includes a pure condorcet and a CloneproofSSD implementation +## modeled after the Python-based Debian project election code and +## that gives the same results in several tested corner cases. +################################################################# + +################################################################## +## CondorcetVote Classes and SubClasses +## +## The CondorcetVote class is subclassed by the PureCondorcetVote and +## the CloneproofSSDVote classes but should not be used directly. + +class CondorcetVote < ElectionVote + + def tally_vote(vote=nil) + + vote.each_with_index do |winner, index| + # only run through this if this *is* preferred to something + break if vote.length - 1 == index + losers = vote.last( vote.length - index ) + + losers.each do |loser| + next if winner == loser + + @votes[winner] = Hash.new unless @votes.has_key?(winner) + @votes[loser] = Hash.new unless @votes.has_key?(loser) + + if @votes[winner].has_key?(loser) + @votes[winner][loser] += 1 + else + @votes[winner][loser] = 1 + end + + # make sure we have a comparable object + @votes[loser][winner] = 0 unless @votes[loser].has_key?( winner ) + + @candidates << loser unless @candidates.include?( loser ) + end + + @candidates << winner unless @candidates.include?( winner ) + end + end + + protected + def verify_vote(vote=nil) + vote.instance_of?( Array ) and + vote == vote.uniq + end + +end + +class PureCondorcetVote < CondorcetVote + def result + PureCondorcetResult.new( self ) + end +end + +class CloneproofSSDVote < CondorcetVote + def result + CloneproofSSDResult.new( self ) + end +end + + +################################################################## +## CondorcetResult Classes and SubClasses +## +## The CondorcetResult class is subclassed by the PureCondorcetResult +## and the CloneproofSSDResult classes but should not be used +## directly. + +class CondorcetResult < ElectionResult + def initialize(voteobj=nil) + unless voteobj and voteobj.kind_of?( CondorcetVote ) + raise ArgumentError, "You must pass a CondorcetVote array.", caller + end + super(voteobj) + end + + def defeats(candidates=nil, votes=nil) + candidates = @election.candidates unless candidates + votes = @election.votes unless votes + + defeats = Array.new + candidates.each do |candidate| + candidates.each do |challenger| + next if candidate == challenger + if votes[candidate][challenger] > votes[challenger][candidate] + defeats << [ candidate, challenger ] + end + end + end + + defeats + end + +end + +class PureCondorcetResult < CondorcetResult + def initialize(voteobj=nil) + super(voteobj) + self.condorcet() + end + + protected + def condorcet + votes = @election.votes + candidates = @election.candidates + + victors = Hash.new + candidates.each do |candidate| + victors[candidate] = Array.new + end + + self.defeats.each do |pair| + winner, loser = *pair + victors[winner] << loser + end + + winners = @election.candidates.find_all do |candidate| + victors[candidate].length == @election.candidates.length - 1 + end + + @winners << winners if winners.length == 1 + end +end + +class CloneproofSSDResult < CondorcetResult + def initialize(voteobj=nil) + super(voteobj) + @winners = self.cpssd() + end + + protected + def cpssd + votes = @election.votes + candidates = *@election.candidates + + def in_schwartz_set?(candidate, candidates, transitive_defeats) + candidates.each do |challenger| + next if candidate == challenger + + if transitive_defeats.include?( [ challenger, candidate ] ) and + not transitive_defeats.include?( [ candidate, challenger ] ) + return false + end + end + return true + end + + loop do + + # see the array with the standard defeats + transitive_defeats = self.defeats(candidates, votes) + + candidates.each do |cand1| + candidates.each do |cand2| + candidates.each do |cand3| + if transitive_defeats.include?( [ cand2, cand1 ] ) and + transitive_defeats.include?( [ cand1, cand3 ] ) and + not transitive_defeats.include?( [ cand2, cand3 ] ) and + not cand2 == cand3 + transitive_defeats << [ cand2, cand3 ] + end + end + end + end + + schwartz_set = Array.new + candidates.each do |candidate| + if in_schwartz_set?(candidate, candidates, transitive_defeats) + schwartz_set << candidate + end + end + + candidates = schwartz_set + + # look through the schwartz set now for defeats + defeats = self.defeats(candidates, votes) + + # it's a tie or there's only one option + break if defeats.length == 0 + + def is_weaker_defeat?( pair1, pair2 ) + votes = @election.votes + if votes[pair1[0]][pair1[1]] > votes[pair2[0]][pair2[1]] + return true + elsif votes[pair1[0]][pair1[1]] == votes[pair2[0]][pair2[1]] and + votes[pair1[1]][pair1[0]] > votes[pair2[1]][pair2[0]] + return true + else + false + end + end + + defeats.sort! do |pair1, pair2| + if is_weaker_defeat?( pair1, pair2 ) + +1 + elsif is_weaker_defeat?( pair2, pair1 ) + -1 + else + 0 + end + end + + votes[defeats[0][0]][defeats[0][1]] = 0 + votes[defeats[0][1]][defeats[0][0]] = 0 + + end + + return candidates + end + +end diff --git a/lib/rubyvote/election.rb b/lib/rubyvote/election.rb new file mode 100644 index 0000000..7fd8396 --- /dev/null +++ b/lib/rubyvote/election.rb @@ -0,0 +1,160 @@ +# election library -- a ruby library for elections +# copyright © 2005 MIT Media Lab and Benjamin Mako Hill + +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, but +# WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +# General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +# 02110-1301, USA. + +################################################################# +## ==== election.rb ==== +## +## This file contains the core ElectionVote and ElectionResults +## classes and the most common and simple election methods including +## plurality and approval voting. +################################################################# + +################################################################## +## ElectionVote Classes and SubClasses +## +## There classes are used to store, verify, and "tally" (i.e. count +## votes for the standard Election superclass and for the most common +## types of elections. + +class ElectionVote + attr_reader :votes + attr_reader :candidates + + def initialize(votes=nil) + @votes = Hash.new unless defined?(@votes) + @candidates = Array.new unless defined?(@candidates) + + if votes + if votes.instance_of?( Array ) + votes.each do |vote| + self.tally_vote(vote) if self.verify_vote(vote) + end + else + raise ElectionError, "Votes must be in the form of an array.", caller + end + end + end + + protected + # by default, this is set to look if the vote is defined. it should + # be overridden in each class + def verify_vote(vote=nil) + vote ? true : false + end + + # by default, this does nothing. it must be redefined in any subclass + def tally_vote + self.verify_vote(vote) + end +end + +class PluralityVote < ElectionVote + def result + PluralityResult.new(self) + end + + protected + def verify_vote(vote=nil) + vote.instance_of?( String ) + end + + def tally_vote(candidate) + if @votes.has_key?(candidate) + @votes[candidate] += 1 + else + @votes[candidate] = 1 + @candidates << candidate + end + end +end + +class ApprovalVote < PluralityVote + def result + ApprovalResult.new(self) + end + + protected + def verify_vote(vote=nil) + vote.instance_of?( Array ) and vote.length >= 1 + end + + def tally_vote(approvals) + approvals.each {|candidate| super(candidate)} + end +end + + +################################################################## +## Election Result Classes +## + +## There classes are used to compute and report the results of an +## election. In almost all cases, these will be returned by the +## #results method of a corresponding ElectionVote subclass. + +class ElectionResult + attr_reader :winners + + def initialize(voteobj=nil) + unless voteobj and voteobj.kind_of?( ElectionVote ) + raise ArgumentError, "You must pass a ElectionVote array.", caller + end + + @election = voteobj + @winners = Array.new + end + + def winner + @winners[0] if @winners.length > 0 + end + + def winner? + @winners.length > 0 + end + +end + +class PluralityResult < ElectionResult + attr_reader :ranked_candidates + + def initialize(voteobj=nil) + super(voteobj) + + votes = @election.votes + candidates = @election.candidates + + @ranked_candidates = votes.sort do |a, b| + b[1] <=> a[1] + end.collect {|a| a[0]} + + # winners are anyone who has the same number of votes as the + # first person + @winners = @ranked_candidates.find_all do |i| + votes[i] == votes[@ranked_candidates[0]] + end + end +end + +# this class is complete because results for approval are computed +# identically to results from plurality +class ApprovalResult < PluralityResult +end + +class ElectionError < ArgumentError +end + diff --git a/lib/rubyvote/positional.rb b/lib/rubyvote/positional.rb new file mode 100644 index 0000000..11e8a49 --- /dev/null +++ b/lib/rubyvote/positional.rb @@ -0,0 +1,74 @@ +# election library -- a ruby library for elections +# copyright © 2005 MIT Media Lab and Benjamin Mako Hill + +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, but +# WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +# General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +# 02110-1301, USA. + +################################################################# +## ==== positional.rb ==== +## +## This file contains positional election methods. Currently only +## includes an implementation of the Borda count election method. +################################################################# + +################################################################## +## BordaVote and BordaResult Classes +## +## These classes inherit from and/or are modeled after the classes in +## election.rb and condorcet.rb + +class BordaVote < ElectionVote + + def initialize(votes=nil) + @candidates = Array.new + votes.each do |vote| + @candidates = vote.uniq if vote.uniq.length > candidates.length + end + super(votes) + end + + def tally_vote(vote) + points = candidates.length - 1 + vote.each do |candidate| + @votes[candidate] = points + points -= 1 + end + end + + def verify_vote(vote=nil) + vote.instance_of?( Array ) and + vote == vote.uniq + end + + def result + BordaResult.new(self) + end +end + +class BordaResult < ElectionResult + def initialize(voteobj=nil) + super(voteobj) + votes = @election.votes + + @ranked_candidates = votes.sort do |a, b| + b[1] <=> a[1] + end.collect {|i| i[0]} + + @winners = @ranked_candidates.find_all do |i| + votes[i] == votes[@ranked_candidates[0]] + end + end + +end diff --git a/lib/rubyvote/range.rb b/lib/rubyvote/range.rb new file mode 100644 index 0000000..5c01f68 --- /dev/null +++ b/lib/rubyvote/range.rb @@ -0,0 +1,32 @@ +# Range voting as described in wikipedia. +# (http://en.wikipedia.org/wiki/Range_voting) + +class RangeVote < ElectionVote + def initialize(votes = nil, range = 1..10) + @valid_range = range + super(votes) + end + + def result + RangeResult.new(self) + end + + protected + def verify_vote(vote=nil) + vote.instance_of?(Hash) && vote.all?{|c,score| @valid_range.include?(score)} + end + + def tally_vote(vote) + vote.each do |candidate, score| + if @votes.has_key?(candidate) + @votes[candidate] += score + else + @votes[candidate] = score + @candidates << candidate + end + end + end +end + +class RangeResult < PluralityResult +end diff --git a/lib/rubyvote/runoff.rb b/lib/rubyvote/runoff.rb new file mode 100644 index 0000000..8a69a4e --- /dev/null +++ b/lib/rubyvote/runoff.rb @@ -0,0 +1,88 @@ +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