]> projects.mako.cc - selectricity/commitdiff
Adding the rubyvote library to do the actually election-making. The only
author<mako@atdot.cc> <>
Wed, 16 Aug 2006 19:19:42 +0000 (15:19 -0400)
committer<mako@atdot.cc> <>
Wed, 16 Aug 2006 19:19:42 +0000 (15:19 -0400)
method supported at the moment is CloneproofSSD.

lib/rubyvote.rb [new file with mode: 0644]
lib/rubyvote/condorcet.rb [new file with mode: 0644]
lib/rubyvote/election.rb [new file with mode: 0644]
lib/rubyvote/positional.rb [new file with mode: 0644]
lib/rubyvote/range.rb [new file with mode: 0644]
lib/rubyvote/runoff.rb [new file with mode: 0644]

diff --git a/lib/rubyvote.rb b/lib/rubyvote.rb
new file mode 100644 (file)
index 0000000..1585389
--- /dev/null
@@ -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 (file)
index 0000000..616de48
--- /dev/null
@@ -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 (file)
index 0000000..7fd8396
--- /dev/null
@@ -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 (file)
index 0000000..11e8a49
--- /dev/null
@@ -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 (file)
index 0000000..5c01f68
--- /dev/null
@@ -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 (file)
index 0000000..8a69a4e
--- /dev/null
@@ -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

Benjamin Mako Hill || Want to submit a patch?