X-Git-Url: https://projects.mako.cc/source/selectricity/blobdiff_plain/1260415e640fec24f8c970ae8e61f4a7ab4594d4..560828ebdd364de4ca09d61764f19215a9e29e59:/lib/rubyvote/condorcet.rb

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